Документ взят из кэша поисковой машины. Адрес оригинального документа : http://cluster.msu.ru/slides/slides-30-10-2000.pdf Дата изменения: Thu Dec 14 15:35:20 2000 Дата индексирования: Mon Oct 1 19:37:31 2012 Кодировка: Windows-1251

Динамическое распараллеливание программ на базе параллельной редукции графов НазначениеD функциональность и архитектура ТEсистемы
ВFАF Роганов АFФF Слепухин

`vrdmsuFrub `poohdmsuFrub

Центр телекоммуникаций и технологий Интернет МГУ имF МFВF Ломоносова


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide I

НазначениеD функциональность и архитектура ТEсистемы
ћ Назначение ТEсистемы ћ Функциональность ТEсистемы ћ Архитектура ПО ТEсистемы


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide P

Назначение ТEсистемы
ћ Какие задачи решает ТEсистема ћ Истоки и история создания ћ Перспективы развития


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide Q

Назначение ТEсистемы

T

T

system

T
ТEсистема " среда программирования с поддержкой автоматического динамичеE ского распараллеливания программ Для реализации концепции автоматического динамического распараллеливания программ в ТEсистеме предложена новая модель организации вычислительного процессаD основанная на следующих базовых принципахX В качестве основной парадигмы рассматривается функциональное программироваE ниеF Программа представляет собой набор чистых @без побочных эффектовA функE цийF Каждая функция может иметь несколько аргументов и несколько результатовF


В то же время тела функций могут быть описаны в императивном стиле @на языках типа pyexD g и тF пFA Важно толькоD чтобыX

ћ Всю информацию извне функция получала только через свои аргументыY ћ Вся информация из функции передавалась только через явно описанные реE
зультатыF Вызов функции qD производимый в процессе вычисления функции p выполняется нетрадиционным способом @тF нF сетевой вызов функцииAF При этом порождается новый процесс с несколькими входами @в соответствии с числом аргументов функции qA и несколькими выходами @в соответствии с числом результатов функции qAF Выходы нового процесса связываются с соответствующими переменными процесса p отношением ?поставщик " потребитель? D и тем самымD переменныеEпотребители принимают неготовые @не вычисленныеA значенияF Порожденный процесс q должен вычислить функцию q и заменить неготовые значения у всех своих потребителей на соответствующие результаты функции qF


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide R

Перспективы развития
Три базисных источника информацииD существующих до начала разработки новой @промышленнойA версии ядра ТEсистемыX

ћ ТEсистема @включая все ее компоненты на момент ISFHSFPHHHA ћ Находящееся в свободном доступе ПО для кластеров ћ Совокупность всех алгоритмов и идейD накопленных участниками Esystem group
на момент ISFHSFPHHH РаботыD которые должны быть выполнены на этапе разработки новой версии ядра ТEсистемыX Собственно ТEядроX

ћ Системные библиотекиD обеспечивающие ?Esystem sfe?Eвзаимодействия приE
кладных программ с ядром ОС vinuxF


ћ ћ ћ ћ ћ ћ ћ

Система управления памятью @в тF чF стекамиAD процессами и коммуникациями ТранспортноE и архитектурноEнезависимая версия Eсистемы Использование ws в качестве транспорта Использование wsEпрограмм в качестве вычислительных узлов Приоритеты задач и иерархическая структура вычF ресурсов @планировщикA Средства управления кластером для ТEсистемы @инициацияD рассылкаD FFFA Средства обеспечения отказоустойчивости вычислений

БиблиотекиX

ћ Основные прикладные параллельные вычислительные библиотеки ћ Параллельные прикладные библиотеки @вводGвыводD объекты и тF дFA
Базовые средства разработчикаX Графические интерфейсы @GtvA для администрированияGмониторинга Базовые средства для разработки ТEприложений @сборкаD запускD FFFA Параллельный отладчик @ТрассировкаD визуализация трассыD повторA Профилировщик приложений Система тестирования ядра ТEсистемы @набор тестов и демонстрF примеровA

ћ ћ ћ ћ ћ


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide S

Функциональность ТEсистемы
ћ ћ ћ ћ ћ ћ
?За? и ?против? функционального подхода Система инвариантов ТEсистемы Теоремы @ЧерчаEРоссера и дрFA Параллельная редукция графов Расширения классической схемы Мемоизация


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide T

?За? и ?против? функционального подхода

Счастливые билеты
tikets ds a @dsD foldl @n Eb IHBn C digitosnt A H dsA X @4@4CCldCCopCCrdCC4A4D f lv rvA | @opDfA `E @9C9D@CAAD@9E9D@EAAD@9B9D@BAAD@9G9D@divAAD n`EIFFlength dsEID @ldDlvA `E tikets @tke n dsAD @rdDrvA `E tikets @drop n dsAD op Ga 9G9 || @rv Ga H 88 lv mod rv aa HA hppy a mp fst F @filter @@aaAIHH F sndAA F tikets rugs session forX GusrGshreGhugsGliGreludeFhs tiketFhs ype Xc for help winb hppy 4QIRISW4 4@QC@IC@RB@ISCWAAAA4D4@QIC@@RBISACWAA4D4@@QCIAC@RB@ISCWAAA4D 4@@@QBIRAEIACSWA4D4@@QIC@RBISAACWA4D4@@QBIRAE@IESWAA4D 4@@QIBRAE@ISCWAA4D4@@@QIBRAEISAEWA4D4@@QEIAB@RC@IC@SBWAAAA4D 4@@QEIAB@@RCIAC@SBWAAA4 winb veving rugs


Расстановка ферзей
module ueens where import qofer queens numerofqueens a qu numerofqueens where qu H a qu @mCIA a pCCn | p`Equ mD n`EIFFnumerofqueensD sfe p n sfe p n a ll not hek @iDjA @mDnA | @iDjA `E zip IFF p where m a I C length p

hek @iDjA @mDnA a jaan || @iCjaamCnA || @iEjaamEnA q a puttr F lyn F mp show F queens


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide U

Система инвариантов ТEсистемы
ћ Редукция графов " меняет графD не меняет его значение ћ Стратегия вычислений " решаетD что вычислять в первую очередь ћ Распределение работы " решаетD какую задачу кому отдать


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide V

Теоремы @ЧерчаEРоссера и дрFA
Теорема ЧерчаEРоссера

Если R " отношениеD то пусть R означает его конечноEтранзитивное замыканиеF Пусть X Y означаетD что X редуцируется в Y F Обозначим X cnv Y X Y Y X F ТогдаX
X cnv Y N : X N Y N

Теорема о единственности нормальной формы @следствие из тF ЧEРA

Любые две нормальные формы лямбдаEвыражения алфавитноEэквивалентныF
Ромбическое свойство

Если выражение E может быть редуцировано к двум выражениям быть редуцированы E 1 и E 2F
Теорема стандартизации

E1

и

E2

D то существует N D в которое могут

Если выражение E имеет нормальную формуD то редукция самого левого из самых внешних редексов на каждом этапе редукции E гарантирует достижение этой нормальной формы с точностью до алфавитной эквивалентностиF


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide W

Параллельная редукция графов


Краткая теоретическая база параллельной редукции графов
Eисчисление

" это исчисление анонимных @безымянныхA функцийF Оно даетD воEпервыхD метод представления функций иD воEвторыхD множество правил вывода для синтаксического преобразования функцийF Редукция " это процесс упрощения EвыраженияF ћ Eредукция " это способ преобразования цепочек символовD являющихся функциональными константамиF ћ Eредукция заключается в переименовании свободных переменных ћ Eредукция " это процесс копирования тела абстракции с заменой всех вхождений связанной переменной на выражение аргументаF Редекс " это редуцируемое выражениеF Eвыражения могу быть представлены в виде графовF При этом множественные ссылки на одно и то же выражение аргумента представляются множеством дугD идущих к единственной разделяемой копии соответствующего графа аргументаF При редукции графа выражения вполне возможно присутствие в этом графе множества редексов в любой моментF Вследствии прозрачности ссылок мы знаемD что эти редексы будут всегда вычисляться с одинаковым результатом независимо от тогоD где и когда это вычисление имеет местоF Поэтому вполне возможно вычислять их одновременноD разместив на отдельных процессорахF Каждый процессор может затем приступить к редукции соответствующих редексовD возможно генерируя новые процессы иD таким образомD создавая новые параллельные задачиF Ниже приведен алгоритмD реализующий параллельную редукцию графовF


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide IH

Параллельная редукция графов
YY qrph node definition @defstrut @nA @inA @outA @funA @vlA @thredA @tA @dtAA YY win funtions @defun getfor @nA @ddElink BnodeB nA @queEput n BlBAA @defun forget @nA @delElink BnodeB nA @queEput n BolBAA @defun l @nA @or @null @nEout nAA @nEthred nA @setf @nEthred nA @strtEthred nAAAA @defun ol @nA @or @nEout nA @null @nEthred nAA @setf @nEthred nA @killEthred nAAAA @defun strt @nA @llEwithEnode n @ompute nAA @if @nEt nA @funll @nEt nA nAA @mpr 59killEthred @nEout nAAA @defun stop @nA @mpr 59killEthred @nEout nAA @if @nEdt nA @funll @nEdt nA nAA @llEwithEnode n @mpr 59forget @nEin nAAAA


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide II

Расширения классической схемы
ћ ћ ћ ћ ћ
Стратегии выбора и распределения работы Вызов по состоянию Подъем функциональной схемы Монотонные объекты Инкрементальные вычисления


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide IP

Стратегии выбора и распределения работы
При вызове ТEфункции имеется две возможностиD что считать дальшеX

ћ Сначала считать ?вширь?
Порождается больше пренатальных процессовD вычисления становятся более ?ленивыми? и может потребоваться больше памяти для стеков ћ Сначала считать ?вглубь? Экономия на стеках и на кэшеD вычисления становятся более ?энергичными? и порождается меньше пренатальных процессов


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide IQ

Вызов по состоянию
Результатом работы функции может быть некоторая фиктивная величинаD которая означаетD что над глобальными данными произведено некоторое преобразованиеF


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide IR

Мемоизация
Для чистых функций @не имеющих побочных эффектовA можно запоминать резульE тат их вычислений и затем при повторных вызовах от одних и тех же аргументов просто брать значение из таблицыF


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide IS

Архитектура ПО ТEсистемы
ћ ћ ћ ћ ћ ћ
Программный и пользовательский интерфейсы ТEсистемы Ядро параллельной редукции графов Кластерный уровень Компилятор @soureEtoEsoure onverterA Работа в качестве вычислительного сервера Приложения


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide IT

Программный и пользовательский интерфейсы ТEсистемы
ћ Библиотека классов gCC и интерфейс с другими языками ћ Гладкие Eрасширения языков g и portrn ћ Среда для разработкиD отладки и профилировки программ


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide IU

Библиотека классов gCC и интерфейс с другими языками
В качестве средства реализации ядра ТEсистемы выбран язык gCCF Это обеспечиE вает хорошую эффективность и переносимость кодаD а также упрощает достижение таких важных целейD как модульность и расширяемость ПОF В ряде случаев @наE примерD для многих невычислительных задачAD использование gCC также очень желательно и с точки зрения удобства разработки параллельных приложенийF Интерфейс ТEсистемы для разработчика ПОD программирующего на языке gCCD выглядит как совокупность классовD которые он может гармонично включить в диE зайн своего приложения и эффективно использовать все возможности ТEсистемы на всех уровнях распараллеливанияD начиная от динамического распределения выE числительной нагрузки и заканчивая интерфейсами с клиентской сторонойF


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide IV

Гладкие Eрасширения языков g и portrn
Важным достоинством новой версии ТEсистемы является тоD что она поддерживаE ет гладкое расширение языка gF Гладким оно названо потомуD что все необходимые конструкции для указания мест распараллеливания программы просто и естественE но погружены в синтаксис языка gF Компилятор преобразует программу на языке g в программу на языке gF При этом он производит необходимый анализ программы и вставляет в текст все необE ходимые обращения к ядру ТEсистемыF Затем gEпрограмма транслируется обычE ным оптимизирующим компиляторомF Ключевым свойством гладкого расширения языка является тоD что программа на этом языке превращается в программу на языке g и без специального компилятораD если определить ключевые словаD добавленные в язык g как макросыF ПредполагаетсяD что это удобство будет оценено пользователямиD которым будет проще начинать разработку и переделку своих программ под ТEсистемуF portrnX первая версия будет на базе fP " portrnEtoEg конвертораF


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide IW

Среда для разработкиD отладки и профилировки программ
Среда разработки для ТEсистемы является надстройкой над средой разработки обычных последовательных программF Дополнения будут сделаны в следующих пунктахX

ћ Поддержка расширенного синтаксиса @конструкций ТEрасширений языковA ћ ynlineEhelp по интерфейсным классам ТEсистемы ћ Запуск ТEзадачи
в нормальном режиме с профилировкой под отладчиком с трассировкой и возможностью повторения трассы ћ Вызов дополнительных утилит @визуализация статистикиD состояния и тF пFA

! ! ! !


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide PH

Ядро параллельной редукции графов
ћ ћ ћ ћ
Структура wEвычислителя Внешнее вычисление узлов графа Сопряжение с кластерным уровнем Отказоустойчивость


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide PI

Структура wEвычислителя
ћ Основные классы wEвычислителя ћ Диаграмма связей между объектами ћ Система управления памятью


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide PP

Структура wEвычислителя
shared memory worker 1 prenatal queue worker 2 calculator ... collector T-process resources pool T-process 1 ... T-process N

worker N


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide PQ

Основные классы wEвычислителя
gontinution " ТEпроцесс в пренатальном состоянии @функция с аргументамиA xode " Динамическая составляющая ТEпроцесса gomputtiontte " Динамические ресурсы ТEпроцесса r`vltb " Темплейтная обертка ТEпеременной es`vltb " Темплейтная обертка результата ТEфункции orker " Рабочий процесс wEвычислителя


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide PR

Диаграмма связей между объектами

in

out

continuation

node

computation state

arguments

results

function


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide PS

Система управления памятью
ћ Динамическое распределение памяти на основе mmp@A ћ Быстрые чанковые аллокаторы для структур фиксированного размера ћ Возможность реализации легковесных мигрируемых процессов @lightweight miE
grtle proessesA ћ Автоматическое обеспечение возможности создания ?контрольных точек? @hekpointingA


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide PT

Внешнее вычисление узлов графа
Внешнее вычисление узла графаX

ћ ћ ћ ћ

Не требует стека Не требует процессора @но имеет статус ?вычисляется?A Циклическое @для обеспечения отказоустойчивостиA Использует информацию о свободных ресурсах в кластере

ПримерыD где внешние вычисления возникаютX

ћ Асинхронный вводEвывод ћ Вычисление на удаленном узле кластера
По окончанию @или сбросуA вычисления узел графа вновь попадает в очередь к калькулятору @или коллекторуA


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide PU

Сопряжение с кластерным уровнем

Для повышения эффективности преобразование в транспортную форму произвоE дится по необходимостиF


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide PV

Сопряжение с кластерным уровнем
mylloc prev next prev next dlring< pren >

dlring< T > prev next Lock statistic_t prev next dlring< stk > used_stks free_stks

dlring< node >

gbl_lock

statistic

RawData

in out

_col_ _cal_

thread_spec

threads

allocated_stks

used_stks

_pren_

thread Msg next n Args node n

refs root childs parent def myp pren


mylloc

dlring< T > prev next Lock statistic_t prev next dlring< stk > used_stks free_stks

prev next prev next dlring< pren >

dlring< node >

gbl_lock

statistic

RawData

in out

_col_ _cal_

thread_spec

threads

used_stks

allocated_stks

_pren_

thread Msg next n Args node n

refs root childs parent def myp pren

Computation

hash

ComputationRef


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide PW

Отказоустойчивость
В ТEсистеме предусмотрена возможность динамического изменения конфигурацииF Исключение и подключение компьютера может происходить без остановки процесE са вычисленийD при условии что сетевой транспорт аппаратно это поддерживаетF Обеспечение отказоустойчивостиX В случае отказа узла соответствующие порталы терминируют внешнее вычисление узлов графаD с которыми они были связаныF После этого узлы повторяют цикл вычисленияD используя новую информациюD где отказавший узел уже отсутствуетF


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide QH

Кластерный уровень
ћ ћ ћ ћ ћ ћ ћ ћ
Вычислительные пространства и порталы Асинхронный вводEвывод Активные сообщения Сопряжение с реализациями wsGsws Распределенная мемоEтаблица Внешнее планирование Дерево вычислительных ресурсов Начало и окончание работы


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide QI

Вычислительные пространства и порталы

S1

S4

S2

S3

Два режима работыX реальный кластер и эмуляция кластера


RawData

Msg

next head tail send_head send_tail

Lock

mylock

send_lock

ComputationResource resource

resources

MsgQueue

mqs

ComputationPortal portals ComputationSpace cs_list cdev next next

ComputationDevice cd_list comp

Computer


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide QP

Асинхронный вводEвывод
ћ ВводEвывод как внешнее вычисление ћ Распараллеливание для одного и нескольких процессов


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide QQ

ВводEвывод как внешнее вычисление
Асинхронный вводEвывод рассматривается как внешнее вычисление


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide QR

Распараллеливание для одного и нескольких процессов
p обеспечивает распараллеливание вводаEвывода для одного процесса @soket sGy - wsA

ywsy " подсистема wsgrD обеспечивающая асинхронный вводEвывод для несколь ких одновременно работающих процессов


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide QS

Активные сообщения



T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide QT

Сопряжение с реализациями wsGsws

impirun Eserver `ountb Eport `portnumerb rereD `ountb is the numer of lient onnetions tht the server expets to seeF hen impirun is strted with the Eserver9 optionD it retes gGs soket for listening nd then prints oth the s ddress of the lol host @in stndrd dot nottionA nd the port numer of the soket @to stdoutD if on xs mhineAF sf the Eport9 option is speifiedD the server will ttempt to strt on the given `portnumerbF sf the Eport9 option is not givenD the server is free to hoose ny port numerF impirun Elient `rnkb `hostXportb `mdlineb `rnkb speifies where the proesses elonging to this lient should e pled in wsgywwyvh reltive to the other lients nd must e unique numer etween H nd ountEID inlusiveF `hostXportb is the hostXport string provided y the serverF `mdlineb is implementtionEspeifiF


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide QU

Распределенная мемоEтаблица
hw E histriuted rllel wemo le Глобальное разделяемое между вычислительными узлами отображение `функцияDаргументыb Eb вершина редуцируемого графа Сборка мусораX Каждую запись добавляем в список с индексомD равным целой части логарифма его времени вычисленияF Каждый список просматриваем через соответствующее времяF


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide QV

Внешнее планирование
В процессе динамического распараллеливания может образовываться большое коE личество готовых к исполнению задачD значительно превышающее количество акE тивных исполнителей @процессоровA в данном вычислительном узлеF Под внешним планированием понимается выбор узла кластераD на котором будет вычисляться данная функцияF Этот выбор осуществляется самим узлом графа на основе информации о произE водительности загруженности узлов кластераF


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide QW

Дерево вычислительных ресурсов
Информация о производительности и загруженности узлов кластера хранится в дереве ресурсовF При избытке готовых к исполнению вычислительных задач на одном вычислительE ном узле и недогруженности других узлов кластера происходит миграция задач на наиболее подходящий узелF Узлы кластера обмениваются информацией @через широковешательные посылкиA о своей загруженности и каждый узел лениво вычисляет статистику загрузки для каждого подкластера и всего кластера в целом @поддерживается иерархическая схеE ма организации кластераAF При избытке заданий узелD на который следует отпраE вить задачу @напримерD пренатальный ТEпроцессAD должен вычисляться за нескольE ко сотен инструкций процессораF Полная загруженность кластера должна обнаруE живаться за несколько инструкцийF


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide RH

Начало и окончание работы
Начало работы

ћ mpirun `userEtEexeutleb ћ Запрос клиента
Окончание работы

ћ Вывод результата ћ Сбор статистики и финализация


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide RI

Компилятор @soureEtoEsoure onverterA
ћ ћ ћ ћ
Синтаксис и семантика языка g Подсчет аттрибутов Оптимизация обращений к ТEядру Порождение gEкода и gEструктур


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide RP

Синтаксис и семантика языка g
ћ Язык g является гладким расширением языка g ћ Может быть откомпилирован как обычная gEпрограмма ћ Добавлены новые атрибуты переменных и функций tvr " ТEпеременная tptr " указатель на ТEзначение trry " ТEмассив tfun " ТEфункция tlzy " атрибут для ленивой семантики tmemo " мемоизуемая функция tin " параметр ТEфункции tout " результат ТEфункции ћ Добавлены новые функции@макросыA teomp tredy


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide RQ

Подсчет аттрибутов
Проход IX подсчет атрибутов


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide RR

Оптимизация обращений к ТEядру
Проход PX оптимизация обращений к ядру ТEсистемы


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide RS

Порождение gEкода и gEструктур
tfun fi @tin int nD tout intB resA { if @n ` PA res a nY else { tvr int resIY tvr int resPY fi@n E ID resIAY fi@n E PD resPAY Bres a resI C resPY } } GGEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE strut firgs { r`intb n Y }Y strut firess { es`intb res Y }Y void fi @firgs onstB rgsD firessB ressA if @rgsEbn ` PA ressEbres a rgsEbnY else { r`intb resIY r`intb resPY gontinution`firgsD firessbB ntI a new gontinution`firgsD firessb@ fiD new gomputtiontteptory`pstroessb AY ntIEbrgsEbn a rgsEbn E IY resI@ntID ntIEbressEbresAY prentlqueueEbputfront@@qenerigontinutionBAntIAY gontinution`firgsD firessbB ntP a new gontinution`firgsD firessb@ fiD new gomputtiontteptory`pstroessb AY ntPEbrgsEbn a rgsEbn E PY resP@ntPD ntPEbressEbresAY prentlqueueEbputfront@@qenerigontinutionBAntPAY ressEbres a resI C resPY } }


Тест на языке gCC с макросами @кодD взятый из прототипаA
vlt fi @vlt kA { dprintf@47pX fi@7dAn4D thisD kAY int resY if @k ` PA return kY if @k ` PHA GB gEll BG return fi@kEIA C fi@kEPAY else { GB Ell BG pren BkI a gevv@fiDkEIAY pren BkP a gevv@fiDkEPAY res a ev@kIA C ev@kPAY } return resY

}


Тестовый пример @прототип компилятораA
tfun flot x@int tvr uA { return uBPY } @A { return PY } int tfun min @int tvr eD int yA { tvr int Y if @eA { Ba @PAY GBCCYBG } else { min@UDAY X min@UDAY min@UDAY } printf@4rello 34AY } GGEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE GBtfunBG flot tfunx@int GBtvrBG uA { return eqigrigu@uABPY } GBfunBG flot x@int GBvrBG uA { return uBPY } @A { return PY } int GBtfunBG tfunmin @int GBtvrBG eD int yA { GBtvrBG int Y if @eqigrigu@eAA { eesqx@A a eqigrigu@AB@ @PAAY } else { tfunmin@UDeqigrigu@AAY X tfunmin@UDeqigrigu@AAY tfunmin@UDeqixygrigu@AAY } printf@4rello 34AY } int GBfunBG min @int GBvrBG eD int yA { GBvrBG int Y if @eA { a B@ @PAAY } else { min@UDAY X min@UDAY min@UDAY } printf@4rello 34AY }


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide RT

Работа в качестве вычислительного сервера
ћ Сопряжение с прикладными программами ћ Средства обеспечения безопасности


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide RU

Работа в качестве вычислительного сервера
Доступ к вычислительному ядру кластера осуществляется через выделенный комE пьютерD выполняющий роль шлюзаD и работающий под управлением доработанной версией ОС vinuxD в которой устранены наиболее узкие звенья в системе безопасE ностиF Доступ пользователей к шлюзу осуществляется через протокол и систему аутентификации rD по этому же протоколу происходит поступление небольших объемов входных и выходныхD а также управляющих данныхF Это обеспечивает хоE рошую защищенность передаваемых данныхD но накладывает ограничения на скоE рость обмена ввиду больших накладных расходов на криптостойкое кодирование и декодирование информацииF Для передачи больших массивов может использоE ваться другая схемаD основанная на пересылке данныхD закрытых высокоскоростE ным алгоритмом шифрования с автоматически генерируемым случайным ключом значительной длиныD который передается по хорошо защищенному протоколу rF


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide RV

Сопряжение с прикладными программами
ћ Esripting lnguges ћ Интерпретатор комбинаторной логики ћ Параллельная реализация языка РефалC


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide RW

Esripting lnguges
В некоторых случаях удобно иметь специальный язык для оперативного формироE вания вычислительных задачF На такое средство программирования можно смотE реть как на аналог shell9а в системе nixD из которого можно вызывать базовые системные и пользовательские функцииD написанные на языках ТgD portrn и тF дF По всему миру широко используются такие технологииD как gvD и данный подход можно рассматривать как распространение этого хорошо зарекомендовавшего себя подхода на кластерные вычисленияF Основными отличиями shell для кластеров являютсяX

ћ язык функциональныйD имеет ленивую модель вычислений и поддерживает

огромное количество параллельно выполняющихся потоков @вызовов функE цийAY ћ динамически распараллеливает программы в кластереD используя специальные расширения ТEсистемы @системные функции ядра ! комбинаторыAF


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide SH

Интерпретатор комбинаторной логики
Комбинатором называется лямбдаEвыражение без свободных переменныхF Любую чистую функцию можно представить в виде аппликативного выраженияD состоящего только из и u комбинаторов и примитивных функцийF
uxyax f g x a @f xA@g xA sxax sauu s x a @ u uA x a @u xA @u xA a x au@@u@@@uAAAAuA


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide SI

Параллельная реализация языка РефалC
ћ ћ ћ ћ
Реализован новый @непараллельныйA рантайм для РефалаC Зафиксирован интерфейс для компиляции из РефалаC в gCC Смена рантайма не влечет за собой изменения компилятора и РефалEбиблиотек При параллельной реализации РефалEрантайма значительное количество кода будет общим с рантаймом ТEсистемы


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide SP

Средства обеспечения безопасности
ћ Организация и ограничение доступа ћ Распределение ресурсов между пользователями


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide SQ

Организация и ограничение доступа
На управляющем компьютере находится также все основное и дополнительное ПОD которое может исполняться на вычислительных узлах кластераF Часть функций по администрированию кластера выполняется только локальноD причем для этого необходимы права суперпользователя на управляющем компьюE тереF К этим функциям относятся установка программных пакетов и библиотекD изменение распределения ресурсов для пользователей кластераD назначение адмиE нистраторовF В любой момент времени система может находится либо в штатномD либо в техE нологическом режимеF В штатном режиме на вычислительных узлах кластера не предусмотрено никаE кой возможности получить привилегии суперпользователяF В системе нет никаE ких setuidEзадачD и единственным управляющим элементом во время ее работы


является специализированное и системное ПОD которое позволяет пользователям дистанционно запускать свои задачи на счетD а администраторам выполнять ряд дополнительных функций по контролю и распределению ресурсов кластераF Переход в технологический режим осуществляется в несколько стадийF Сначала производится изменение статуса вычислительных узловD что отражается в таблицах вычислительных ресурсовF Все вычислительные процессы оповещаются об этом изменении и принимают решения о миграции в то или иное вычислительное проE странствоF Наименьший приоритет имеет вторичная памятьD поскольку у нее скоE рость исполнения программы равна нулюF По умолчанию система после загрузки находится в штатном режимеF В технологиE ческом режиме имеется возможность администрирования кластера из локальной сетиF


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide SR

Распределение ресурсов между пользователями
Всех пользователей можно условно разделить на две категории по уровню предоE ставляемого доступаX

ћ ПользователиD которые могут вызывать лишь некоторые @предопределенныеA
ТEподпрограммы ћ ПользователиD которые могут запускать свои собственные ТEGwsEпрограммы Если в первом случае ограничения на возможности накладываются путем аккуратE ного программирования удаленного ТEинтерфейсаD то во втором случае необходима тщательная доработка системы квотирования ресурсов в ядре ОС vinuxF


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide SS

Приложения
ћ ћ ћ ћ ћ
Отладка и трассировка ТEпрограмм Примеры вычислительных задач Примеры невычислительных задач Диаграмма классов ТEсистемы Аналоги ТEсистемы


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide ST

Отладка и трассировка ТEпрограмм
ТEпрограмма в режиме отладки прописывает в именованный pipe свой sh и ждет изменения некоторой своей переменнойD а из среды разработки удаленно запускаE ются отладчики по rD которые присоединяются к процессам и взаимодействуют со средой @визуализируют код программы и воспринимают команды пользователяAF Переключение между окнами отладчиков происходит через меню среды разработки imsF Поскольку ims взаимодействует с отладчиком строго через поток вводаEвыводаD то ему не важноD где и как запускается тот или иной отладчикF sh процессаF Оттестирован также и способD когда отладчик запускается только в случае проE граммной ошибкиF



T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide SU

Отладка и трассировка ТEпрограмм
Трассировка предполагает запись всех событий @обменD выборка из очередиD FFFAD которые влияют на ход работы программыF ТEсистема использует систему трассировки wsD добавляя к ней некоторую дополE нительную информацию @возникающую на wEуровнеA В книге Хоара ?Взаимодействующие последовательные процессы? приводится @несложнаяA теорема о томD что если на входы каждого последовательного проE цесса при двух прогонах системы приходят одни и те же событияD то поведение системы в целом будет также одинаковымF


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide SV

Примеры вычислительных задач


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide SW

Примеры вычислительных задач


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide TH

Примеры невычислительных задач


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide TI

Примеры невычислительных задач
qv ! qrph uery vnguge Различные операции над графамиX

ћ Вычисление значения рекурсивной функции на деревьях ћ Инкрементальное вычисление функций @используя мемоизациюA ћ Поиск подграфа в графе


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide TP

Диаграмма классов ТEсистемы
mylloc dlring< T > prev next Lock statistic_t prev next dlring< stk > used_stks free_stks prev next prev next dlring< pren >

dlring< node >

gbl_lock

statistic

RawData

in out

_col_ _cal_

thread_spec

threads

used_stks

allocated_stks

_pren_

thread Msg next n Args node n

refs root childs parent def myp pren

Computation

hash

ComputationRef


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide TQ

Аналоги ТEсистемы

gilk

5inlude 5inlude 5inlude 5inlude

`ilkFhb `ilkEliFhb `stdliFhb `stdioFhb

ilk int fi @int nA { if @n ` PA return @nAY else { int xD yY x a spwn fi@n E IAY y a spwn fi@n E PAY synY return @x C yAY } }

ilk int min @int rgD hr BrgvA { int nD resultY if @rg 3a PA { fprintf@stderrD 4sgeX fi `ilk optionsb `nbn4AY gilkexit@IAY } n a toi@rgvIAY result a spwn fi@nAY synY printf@4esultX 7dn4D resultAY return HY }


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide TR

Аналоги ТEсистемы

sev
ћ Язык с однократным присваиванием ћ Компиляция в две стадииX
Генерация промежуточного года на gGpyex с оптимизацией Генерация выполняемого файла @стандартный gGpyex компиляторA ћ Пример реализации быстрой сортировки на языке sevX
define win type snfo a rry integer funtion win @ht X snfo returns snfoA funtion plit @ ht X snfo for i in ht returns rry rry rry end for end funtion returns snfoD snfoD snfoA of i when i ` ht I of i when i a ht I of i when i b ht I 7 routine ody 7 if rrysize@ ht A b P then let vD widdleD Xa plit@ ht A in win@ v A || widdle || win@ A end let else ht end if end funtion 7 quiksort

! !


T

T

system

T

НазначениеD функциональность и архитектура ТEсистемы

slide TS

Аналоги ТEсистемы

qr
import rllel pf XX snt Eb snt Eb snt Eb snt pf x y | y E x b a fI pr @fP seq @fICfPAA | x aa y ax | otherwise a pf x m C pf @mCIA y where m a @xCyA div P fI a pf x m fP a pf @mCIA y pf XX snt Eb snt pf x y |x`y a | otherwise a where m a @xCyA Eb snt pf x m C pf @mCIA y x div P

prft x a pf I x