77319

СТРУКТУРА F-ЗАМЫКАНИЙ В СРЕДЕ RiDE

Научная статья

Информатика, кибернетика и программирование

Перечисление наборов глобальных имён блоков данных которое предполагалось давать в неком подобии дизъюнктивной нормальной формы: 1ый набор имён или 2ой набор. Такой момент наступает когда в ходе вычисления сформированы все блоки данных имена которых перечислены в одном из указанных наборов назовём такой набор готовым. C; аргументами для этого запуска служат уже сформированные блоки данных поименованные некоторым готовым набором. Мы называем блоки данных с перечисленными в S именами предпосылками для активации.

Русский

2015-02-02

36.5 KB

0 чел.

СТРУКТУРА F-ЗАМЫКАНИЙ В СРЕДЕ RiDE

М.О. Бахтерев ИММ УрО РАН, г. Екатеринбург

Предлагаемая нами система для поддержки распределённых вычислений RiDE построена вокруг простого формализма f-замыкания (f от future). Первоначально, каждое f-замыкание представлялось нам пятёркой следующих полей.

S. Перечисление наборов глобальных имён блоков данных, которое предполагалось давать в неком подобии дизъюнктивной нормальной формы: 1-ый набор имён, или 2-ой набор, или .., или n-ный набор. Это поле определяет момент времени, после которого система может активировать данное f-замыкание. Такой момент наступает, когда в ходе вычисления сформированы все блоки данных, имена которых перечислены в одном из указанных наборов (назовём такой набор готовым). Сама активация f-замыкания есть запуск процедуры из множества связанных с активируемым f-замыканием (см. C); аргументами для этого запуска служат уже сформированные блоки данных, поименованные некоторым готовым набором. «Дизъюнктивная» же альтернативность нужна для описания выполняющих роль мастеров f-замыканий: многие сценарии параллельных вычислений предполагают, что мастер должен запускаться при завершении любой из отслеживаемых им задач. Мы называем блоки данных с перечисленными в S именами предпосылками для активации.

lS. Описание соответствия между глобальными именами в S и локальными именами аргументов. Как сказано выше, глобальные имена используются для анализа возможности активации f-замыкания. А предназначение локальных в lS - быть ссылками в коде запускаемой во время этой активации процедуры на передаваемые ей в качестве аргументов блоки данных.

R. Описание набора глобальных имён блоков данных, каждый из которых будет сформирован в результате успешного выполнения процедуры, запущенной при активации f-замыкания. Будем называть такие блоки результатами активации.

lR. Описание соответствия глобальных имён в R и локальных имён результатов. Последние используются в коде запускаемой во время активации f-замыкания процедуры для того, чтобы ссылаться на результаты активации в ходе их формирования.

C. Описание набора процедур, одну из которых следует запустить при активации f-замыкания. Предполагается, что f-замыкание представляет некоторую операцию в параллельном алгоритме; и каждый элемент C указывает свою процедуру, выполняющую эту операцию на определённой вычислительной платформе (OpenCL, i686-pc-linux, llvm-posix, .Net и прочих).

Кроме этого, мы предполагали, что каждое f-замыкание, формируемое в процессе исполнения приложения RiDE должно проверяться на то, что все перечисленные в его поле R имена уникальны для всего вычисления. Выполнение этого условия необходимо для сохранения «графовости» потока данных.

Однако, продолжающийся теоретический анализ модели вычислений основанной на таких f-замыканиями показал, что она обладает рядом недостатков.

 1. Мы ожидали некоторый уровень простоты разделения потоков вычислений от ручного управления именами блоков данных, например, при помощи приписывания именам данных в различных потоках различных префиксов. Эти ожидания не оправдались. А способ такого отделения необходим для поддержки разработки библиотек подпрограмм, реализующих в среде RiDE те или иные параллельные алгоритмы.

 2. Описание предпосылок для активации f-замыканий в ДНФ оказалось как неудобным для написания генерирующего это описание кода (особенно для мастеров, запускающих и отслеживающих большое количество рабочих задач), так и неэффективным для обработки f-замыканий во время выполнения приложения для RiDE (особенно для таких мастеров - из-за объёма S).

 3. Указанная выше структура поля S f-замыкания не позволяет программировать реакции вычислительного процесс на внешние запросы. А возможность запрограммировать эти реакции будет необходима в случае использования RiDE для разработки высокопроизводительных систем массового обслуживания, таких как высоко нагруженные web серверы.

4. Проверки уникальности имён в поле R каждого f-замыкания могут внести существенные накладные расходы в исполнение RiDE приложения. Несмотря на возможность замаскировать эти расходы высокой степенью асинхронности исполнения программы для RiDE, их снижение до минимального уровня желательно: ведь, корректная программа будет генерировать только корректные f-замыкания во время своего выполнения.

В текущей работе мы с целью решения этих проблем рассматриваем две модели с модификацией первоначальной семантики f-замыканий: первая с ручным управлением именами и областями видимости; вторая с автоматическим управлением и механикой ссылок и списков. Обе модели расширены специальным видом именованных блоков данных - pin блоками. В новых моделях эти pin блоки данных в отличии от обычных для RiDE с уникальными именами (за которыми оставлена роль основного средства передачи данных) могут быть сгруппированы под одним именем; и могут быть выбраны из такой именованной группы строго по одному при активации f-замыкания, содержащего в предпосылках для активации имя этой группы. Данные в этих группах pin блоков могут появляться из внешних по отношению к RiDE-приложению источников. Этот механизм решает проблемы 3 и 2, существенно облегчая и обработку, и описание f-замыканий мастеров, благодаря возможности использовать для структуре поля S простые и часто короткие списки имён вместо ДНФ от этих имён.

Для решения проблем 1 и 4 в первой модели предложен механизм областей видимости. Области видимости, очевидно, позволяют разделять различные потоки вычислений и снизить сложность проверок уникальности каждого имени в поле R, ограничивая объём работы в большинстве случаев областью видимости, содержащей проверяемое f-замыкания.

Автоматическое управление именами во второй модели в основном направлено на решение проблемы 4, но естественным образом решает и проблему 1. Однако,  эта модель требует введения в язык f-замыканий дополнительных средств, позволяющих контролировать автоматический процесс именования. Такими средствами являются ссылки и списки.

На языках обеих моделей были выражены несколько традиционных параллельных алгоритмов. Это позволило сделать вывод о том, что первая модель уступает второй в удобстве использования. Сей вывод является основным результатом работы. Но вместе с ним получены и следующие потенциально полезные для теории и практики заключения.

Во-первых, вторая модель очень близка к некоторой смеси традиционных парадигм лямбда- и пи-вычислений. Что позволяет применить хорошо  изученные методы выполнения программ, написанных в соответствии с этими парадигмами, при реализации среды времени исполнения для второй модели.

Во-вторых, для определения семантики второй модели мы применяем не традиционную стратегию вычислений (evaluation strategy), которую можно классифицировать как вызов по ссылке на будущее (call by future reference).

Работа выполнена в рамках Программы фундаментальных исследований Президиума РАН № 14 "Интеллектуальные информационные технологии, математическое моделирование, системный анализ и автоматизация" при поддержке УрО РАН, проект  09-П-1-1003.


 

А также другие работы, которые могут Вас заинтересовать

57609. Передумови та початок національно-визвольної війни українського народу в середині XVII ст 288 KB
  Мета: зясувати передумови причини та характер війни; розкрити роль Богдана Хмельницького в підготовці та початку національновизвольної війни; розвивати вміння учнів аналізувати історичні джерела працювати над вивченням історичних подій за алгоритмом працювати самостійно з довідковою літературою...
57610. Війна радянської Росії з УНР і проголошення незалежності Української Народної Республіки 40 KB
  Очикувані результати: після уроку учні аналізуватимуть події кінця 1917 – початку 1918 рр.; дізнаються про плани більшовиків щодо долі України; за допомогою історичної карти зможуть відтворити хід першої ра дянсько–української війни...
57611. Історія як навчальний предмет і наука 569 KB
  Мета: створити початкове уявлення про історію як навчальний предмет і науку; зацікавити новим навчальним предметом; ознайомити школярів з видатними вченимиісторіками України...
57612. Україна в роки правління гетьмана Івана Виговського 76 KB
  Хмельницького визначити основні засади внутрішньої і зовнішньої політики гетьмана Івана Виговського; розвивати в учнів уміння працювати з картою аналізувати текстові та візуальні історичні джерела і на основі їх робити певні висновки...
57613. Велика Вітчизняна війна (1941-1945 рр.) – складова Другої світової війни 54.5 KB
  Мета: познайомити учнів з подіями Великої Вітчизняної війни політикою загарбників на окупованих українських територіях діяльністю руху Опору на території України; вдосконалювати навички роботи з картою...
57614. ВЕРБАЛІЗАЦІЯ СТРАХУ В СУЧАСНІЙ АНГЛІЙСЬКІЙ МОВІ 322.5 KB
  Мовні засоби вираження емоції страху, а також об’єкти, які викликають у людини цю емоцію. Новизна та вибір предмета дослідження обумовлюються відсутністю детального аналізу мовних засобів, які використовуються автором у художньому тексті для вираження мовлення персонажів, які перебувають у стані страху.
57615. КИРИЛЛО – МЕФОДИЕВСКОЕ БРАТСТВО 80.5 KB
  Цели урока: ознакомить учащихся с деятельностью первой украинской политической нелегальной организацией - Кирилло-Мефодиевским братством; провести исследование программных документов и общественно-политической деятельности Кирилло-Мефодиевского братства...
57616. Галицко-Волынское княжество во времена Даниила Галицкого 85.5 KB
  ЦЕЛЬ: сформировать представление о Галицко-Волынском княжестве как наследнике традиций Киевской Руси показать роль Даниила Галицкого в процессе создания государства охарактеризовать основы внутренний и внешней политики...
57617. Державотворчі процеси у 1994-2009 р 138.5 KB
  Мета: розкрити зміст перетворень в 1994-2009 р., сформувати політичну позицію щодо оцінки президентства Л.Д.Кучми, В.А.Ющенка, діяльності Верховної Ради, Кабінету Міністрів; перемогу демократичних сил,радикальні зміни у суспільстві; виховувати в дусі патріотизму, толерантності.