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.


 

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

75597. Театри в Великобританії. Бесіда по телефону, План-конспект уроку з англійської мови для учнів 9-х класів 70 KB
  Активізувати у мові учнів ЛО теми «Відвідування театру». Практикувати учнів у читанні тексту з метою отримання загального уявлення (skimming) з метою максимально повного й точного розуміння всієї інформації, що міститься в тексті (scanning). Повторити навчальний матеріал про ведення бесіди по телефону.
75598. ЦИФРОВАЯ ОБРАБОТКА КОРОТКИХ СИГНАЛОВ. ОПРЕДЕЛЕНИЕ ЧАСТОТЫ СИГНАЛА 140 KB
  Одной из важнейших задач цифровой обработки зашумленных сигналов является обнаружение информативного сигнала в потоке данных искаженных шумами и помехами и определение его параметров. Каждая из этих операций позволяет выполнять преобразования исходного сигнала например переход сигнала из временной области в частотную или наоборот причем при этом производится уменьшение уровня шумов в обработанном сигнале. В задачах обнаружения и определения параметров защумленных сигналов усиление эффекта подавления шумов и...
75599. ЦИФРОВАЯ ОБРАБОТКА КОРОТКИХ СИГНАЛОВ. ОПРЕДЕЛЕНИЕ ВРЕМЕННЫХ ИНТЕРВАЛОВ МЕЖДУ РАДИОИМПУЛЬСАМИ 189.5 KB
  Известный способ измерения расстояния до объекта основан на измерении времени задержки отраженного радиолокационного сигнала от возбуждающего радиоимпульса. По времени задержки отраженного сигнала от зондирующего определяется толщина металла. Однако увеличение количества накоплений позволяет улучшать отношение сигнал шум без искажения формы и уменьшения амплитуды накопленного отраженного сигнала лишь до некоторого предела. При ограничении времени проведения анализа количество возможных...
75600. ЦИФРОВАЯ ОБРАБОТКА НЕСТАЦИОНАРНЫХ СИГНАЛОВ. ПРЕОБРАЗОВАНИЕ ГИЛЬБЕРТА-ХУАНГА 140 KB
  Каждый из этих колебательных режимов может быть представлен функцией внутренней моды intrinsic mode function IMF. IMF представляет собой колебательный режим как часть простой гармонической функции но вместо постоянной амплитуды и частоты как в простой гармонике у IMF могут быть переменная амплитуда и частота как функции независимой переменной времени координаты и пр. Любую функцию и любой произвольный сигнал можно разделить на семейство функций IMF. Процесс отсева функций IMF.
75601. ПРЕОБРАЗОВАНИЕ ГИЛЬБЕРТА 30.5 KB
  Спектральный анализ Гильберта HS применяется для описания нестационарных сигналов т. Мгновенная частота может быть вычислена по формуле wt = d q t dt Цель применения преобразования Гильберта IMF определенные вышеприведенным способом допускают вычисление физически значимых мгновенных частот что дает возможность создать частотно-временное представление сигнала на основе преобразования Гильберта. ЦОС по методу Гильберта-Хуанга включает последовательное применение нескольких...
75602. ОБРАБОТКА ИЗОБРАЖЕНИЙ 345.5 KB
  Целью обработки может являться также улучшение качества изображения для лучшего визуального восприятия геометрические преобразования масштабирование поворот в общем нормализация изображений по яркости контрастности резкости выделение границ изображений автоматическая классификация и подсчет однотипных объектов на изображении сжатие информации об изображении. К основным видам искажений изображений затрудняющих идентификацию можно отнести: Недостаточную контрастность и яркость связанную с недостаточной освещенностью объекта;...
75603. МЕТОДЫ УЛУЧШЕНИЕ ВИЗУАЛЬНОГО КАЧЕСТВА ИЗОБРАЖЕНИЙ 1.67 MB
  MTLB предоставляет средства интерактивной работы с изображениями в различных графических форматах включая: Изменение масштаба изображения; Изменение яркости и контрастности; Поворот изображения; Многие виды фильтрации; Конвертирование графического формата...
75604. СРЕДСТВА ИДЕНТИФИКАЦИИ ОБЪЕКТОВ НА ИЗОБРАЖЕНИЯХ 1.07 MB
  Hассмотрен классический подход к решению задачи обнаружения сигнала приведенный ниже. либо сумму детерминированного сигнала Vt и шума. Будем считать что факт наличия сигнала Vt тоже случаен. Для решения вопроса о наличии сигнала в данный момент можно принять правило: сигнал присутствует если...
75605. ОСНОВЫ ПРОЕКТИРОВАНИЯ СИСТЕМ ЦОС. ВЫБОР АЦП 231.5 KB
  В системе ЦОС содержащей АЦП производится переход от непрерывного сигнала к числовому массиву с учетом шага квантования по уровню DX и шага дискретности по времени Dt. Выбор шага квантования по уровню Выбор шага квантования по уровню производится из условия достижения необходимой точности восстановления значений непрерывного измеряемого сигнала в ЭВМ по дискретным отсчетам. Количество уровней квантования N АЦП в диапазоне изменения входного сигнала Xmin Xmx равно а количество разрядов выходного кода n=log2N Расчет интервала дискретности по...