<<

стр. 2
(всего 4)

СОДЕРЖАНИЕ

>>

{
if flag[i+1]=2 then
{
b[i]=forleft[i+1];
forleft[i+1]=0;
}
if flag[i-1]=2 then
{
b[i]=forright[i-1]; forright[i-1]=0;
} }
for (i=1,i=n,i++) a[i]=b[i];
for (i=1,i=n,i++) cout<<a[i]; goto st;
Литература
Akl S. Parallel sorting. Academic Press, Orlando, FL, 1985.
Dijkstra E.W. A discipline of programming. Prentice Hall, Engle-wood Cliffs, NY, 1976.

ИТЕРАЦИОННОЕ ПЛАНИРОВАНИЕ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ МНОГОПРОЦЕССОРНЫХ СИСТЕМ
Д.И. Зимин, В.А. Фурсов
Институт систем обработки изображений, г. Самара
Введение
При организации обработки болынеформатных изображений [1] в распоряжении пользователя часто имеется достаточное число вычисли­тельных ресурсов, которые используются лишь часть времени. Естест­венно желание использовать мощности простаивающих ресурсов для существенного ускорения процесса обработки изображений.
Идея использования для указанных задач существующей инфра­структуры из персональных компьютеров и коммуникационной среды активно развивается в последние годы. Вместе с тем, оказалось, что при использовании многопроцессорной системы возникают серьезные труд­ности, связанные с разнородностью и неравномерной загрузкой частич­но свободных ресурсов отдельных узлов многопроцессорной системы.
В работе [2] решалась задача использования многопроцессорных систем без учета изменения во времени степени загрузки компьютеров. В настоящей работе приводится технология итерационного планирования распределения ресурсов с эпизодическим изменением плана включения и исключения узлов многопроцессорной системы при выполнении парал­лельной программы. Приводится пример реализации GRID-технологии итерационного планирования ресурсов.
1. Постановка задачи распределения данных
С вычислительной точки зрения основные алгоритмы обработки изображений в пространственной области допускают декомпозицию по данным и с этой точки зрения могут быть разбиты на три группы:
декомпозиция по данным, не требующая обменов между процессо­рами;
необходим обмен данными после завершения обработки всех фраг­ментов;
процесс обработки должен осуществляться итерационно, при этом необходимо осуществлять обмен данными после каждой итерации.
Последний из указанных класс алгоритмов является наиболее сложным с точки зрения организации вычислительного процесса в рас­пределенных (в особенности гетерогенных) системах. В настоящей ра­боте рассматривается только этот класс алгоритмов, поскольку первые два могут рассматриваться как его частный случай.
В данном случае важное значение имеет балансировка загрузки процессоров на каждой итерации. Для уменьшения расходов на межуз­ловые коммуникации в процессе обработки изображение разбивается на квадратные области [3] (рис. 1). При этом обмен данными целесообраз­но осуществлять в последовательности, указанной на рис. 2 а), б), в).












Рис. 1. Двумерная декомпозиция
Вследствие неоднородности многопроцессорной вычислительной системы, время обработки одинаковых фрагментов изображения в узлах будет различным. На время обработки фрагмента влияют многие пара­метры узла, в частности, частота процессора, частота системной шины и памяти, размер КЭШа, параметры коммуникационной среды и т.д.
Определить явную зависимость времени обработки изображения от его размера не представляется возможным, вследствие того, что для различных алгоритмов перечисленные параметры случайным образом взаимодействуют.
Поскольку на используемых для обработки фрагментов изображе­ния узлах одновременно могут выполняться другие виды работ (редак­тирование текстов, написание программ и др.) производительность вы­числительных узлов изменяется также и во времени. Если использовать простаивание узлов в «рабочее время» и полностью использовать «ноч­ное время», то часто можно обойтись без использования дорогостоящих кластеров и суперкомпьютеров.
2. Общая схема итерационного распределения ресурсов
Для распределения ресурсов многопроцессорной системы с характе­ристиками узлов, зависящими от времени, целесообразно применить про­цедуру итерационного планирования, обсуждавшуюся в работе [3]. Идея заключается в том, чтобы улучшать качество плана распределения ресур­сов по мере увеличения числа реальных запусков. Общая схема итераци­онного планирования ресурсов приведена на рис. 3. Процедура планиро­вания анализирует эффективность выполнения параллельной программы на предыдущих запусках и формирует новый план распределения.
Запуск прикладной программы
Выработка нового плана распределения ресурсов
Подсчет критерия качества распределения ресурсов
Исходные данные
Рис. 3. Схема итерационного планированияраспределенияресурсов
Для обеспечения равномерной нагрузки на узлы необходимо эпи­зодически уточнять план с учетом априорных моделей, характеризую­щих производительность узлов в различные периоды времени при раз­личных размерах обрабатываемых фрагментов болыпеформатного изо­бражения. Предлагается следующая модель временных затрат t на об­работку фрагмента отдельным узлом:
t(x, t) = K (t)-T (x) , (1)
где K (t) коэффициент, характеризующий зависимость степени загрузки компьютеров от текущего времени, T (x) зависимость времени обработ­ки фрагмента от его размера.
Задача определения зависимости (1) решается для каждого узла по результатам тестовых запусков параллельной программы обработки изображения для различных размеров фрагментов в разное время. Ко­эффициент K (t) обычно оказывается периодической функцией, с пе­риодом 24 часа, но в некоторых ситуациях период может изменяться, либо не проявляться вовсе.
В работе [2] показано, что для многих алгоритмов обработки зави­симость времени обработки от размеров фрагмента изображения хоро­шо описывается экспоненциальной функцией:
T (x) = a0eaix , (2)
где параметры a0 и a1 определяются путем решения соответствующей
задачи идентификации [1].
После определения параметров модели (1) для каждого узла зада­ча распределения фрагментов изображения по узлам сводится к опреде­лению параметров (x1,..., xn), удовлетворяющих системе уравнений (ус­ловиям балансировки процессоров):



* n ( xn, t ',

где N размер всего изображения, t * время обработки фрагмента на ка­ждом узле.
При итерационном распределении ресурсов на каждом шаге пла­нирования обычно необходимо решать вопрос о необходимости вклю­чения или исключения некоторого узла. В некоторых случаях включе­ние дополнительного узла не повышает быстродействия обработки изо­бражения. Это возможно, например, в ситуации, когда включение узла сопровождается существенным возрастанием коммуникационных рас­ходов в многопроцессорной системе в целом.
Для принятия решения необходимо решать систему (3) для не­скольких вариантов числа узлов и сравнивать прогнозируемое время обработки изображения. Если оцененное время, при выключенных из расчета узлах не меньше, чем при использовании этих узлов, такой план распределения ресурсов принимается на текущем шаге.
2. Результаты экспериментов
Были проведены вычислительные эксперименты по распределе­нию данных между узлами при решении задачи восстановления изо­бражения. Для различных размеров фрагмента получены зависимости T(x) (см. рис.4).
Исследованиями также установлена зависимость коэффициента K (t) от времени, она приближенно описывается как:
K(t)=\ 0.7;t^Е9,1^
W [1;t g [0,9)u(18,24]. (4)
Указанная зависимость отражает тот факт, что в «рабочее время» нагрузка на процессор и коммуникационную сеть возрастает.
Исходя из этих данных, найдено разбиение изображения размером 8192х8192 отсчетов. Обработка изображения происходила на 3-х различ­ных по производительности узлах. Время параллельной обработки изо­бражения составило 405,6 секунд. Результаты эксперимента приведены в таблице 1.

Puc. 4 Таблица 1

Узел
Размер обрабо­танного фраг­мента (пиксел)
Время последовательной обработки изображения (с)
Ускорение
N 1
45334528
592,8
1,46
N 2
13385728
1937,6
4,77
N 3
8388608
3158,4
7,82
Из таблицы 1 видно значительное уменьшение времени обработки изображения, при использовании описанного способа использовании свободных ресурсов.
Заключение
Проведенные вычислительные эксперименты подтверждают, что предлагаемые рекомендации по схеме декомпозиции и распределению ресурсов многопроцессорных гетерогенных систем могут эффективно использоваться в задачах обработки изображений.
Работа выполнена при поддержке российско-американской про­граммы Фундаментальные исследования и высшее образование и РФФИ (грант №03-01-00109).
Литература
1. Методы компьютерной обработки изображений / Под ред. Сойфера В.А., Москва, Физматлит, 2001.
Зимин Д.И., Фурсов В.А. Распределенная обработка болынеформатных изображений на многопроцессорных системах // Международная конферен­ция «Распределенные вычисления и Грид-технологии в науке и образовании», Дубна, 2004.
Фурсов В.А., Шустов В.А., Скуратов С.А. Технология итерационного планирования распределения ресурсов гетерогенного кластера // Труды Все­российской научной конференции «Высокопроизводительные вычисления и их приложения», Черноголовка, 2000.


МЕТОДЫ И ИНСТРУМЕНТАЛЬНЫЕ СРЕДЫ ПОСТРОЕНИЯ ПРОГРАММНЫХ СРЕДСТВ ДЛЯ УПРАВЛЕНИЯ РАСПРЕДЕЛЁННЫМИ СИСТЕМАМИ
А. Кардашич
Московский энергетический институт (ТУ), г. Москва
Введение
Распределенная система (PC) - это комплекс вычислительных и программных ресурсов, способных совместно выполнять информаци­онно-вычислительную работу.
Примерами PC являются информационно-вычислительные сети, кластеры и т.п. В отличие от аппаратных ресурсов, к которым мы отно­сим компьютеры, коммуникации, память и др., программные ресурсы обладают большей степенью свободы, они легко могут изменять место своего хранения, реплицироваться (т.е. копироваться) и модифициро­ваться в соответствии со спецификой решаемых задач.
Подобно социальным системам (фирмы, университеты, армия, го­рода и др.), PC могут иметь различные организационные структуры и управление, подверженные постоянным изменениям, вызванными требо­ваниями повышения их эффективности, быстрой реакции на катастрофи­ческого характера события и естественную деградацию со временем.
Основные проблемы, которые встают перед создателями PC сле­дующие:
поиск моделей и методов оптимального управления и распреде­ления ресурсов,
обеспечение их высокой надёжности,
создание технологий построения различных систем управления
PC,
- разработка инструментария, средствами которого можно быстро проектировать PC.
Организационные схемы управления PC
Будем предполагать, что с организационной точки зрения PC представляет собой распределенное в пространстве множество подсис­тем, предназначенных в общем случае для выполнения определенных функций, которые могут объединяться для решения общих задач.
В каждой такой подсистеме можно выделить относительно само­стоятельные две части: исполнительную и управление. Роль исполни­тельной части - выполнение возлагаемых управлением задач, роль управления - координация процесса функционирования элементов ис­полнительной части, и взаимодействие с другими подсистемами. В зави­симости от того, каким образом построено взаимодействие между управ­лением подсистем (у каждой системы в общем случае свое, отличное от других подсистем управление), их классифицируют следующим образом:
децентрализованное, когда управления подсистемами полностью самостоятельны и координация их работы происходит путем коллек­тивного согласования с целью принятия общих решений по управлению подчиненными подсистемами. В этом случае требуется высокая «ква­лификация» для управляющих узлов и обеспечение высокоскоростных коммуникаций для согласующих взаимодействий;
децентрализованное управление, когда управление подсистема­ми делегирует основные функции по управлению подсистемами и коор­динации их взаимодействия новому более высокого уровня узлу управ­ления. В этом случае требуется высокая квалификация для центрально­го узла управления, способность им быстро принимать решения (боль­шое быстродействие в реализации) и высокая скорость обмена данными с подчиненными узлами;
смешанное, в частности, иерархическое, управление, которое предполагает большую свободу в выборе структуры управления, спе­циализации функций управления и схемы подчинения между управ­ляющими узлами.
Мультиагентный подход к управлению[1] предполагает еще одну, более универсальную стратегию организации управления, когда нет же­сткой связи между подсистемой и ее управлением, сами блоки управле­ния распределены по различным компьютерам PC. В зависимости от выполняемых задач подсистема «заимствует» наиболее подходящее ей управление на определенное время, а затем меняет его на другое, соот­ветствующее другим обстоятельствам.
Ясно, что на уровне программных ресурсов естественно и доста­точно просто реализуется мультиагентный подход, ибо нет никаких проблем, чтобы программный ресурс сделать подвижным (перемещае­мым) и реплицируемым, более того, настраиваемым на условия соот­ветствующей задачи.
Существенно, и из этого надо исходить, что PC является системой с переменной структурой, в ней могут происходить отказы и восстанов­ления компонентов, масштабирование как на уровне подсистем, так и в самих подсистемах.
О ресурсах и их характеристиках
Мы уже сказали, что ресурсы целесообразно разделить на физиче­ские (компьютеры, память, коммуникации и т. п.) и программные. Каж­дый ресурс характеризуется:
типом, относящим его к конкретному виду физических или про­граммных ресурсов,
множеством функций, которые ресурс может выполнять,
местом своего размещения X (X может, например, быть точкой 3-х мерного пространства, если мы рассматриваем вычислительную систему, а ресурс R - есть конкретный компьютер в этой точке, или это место задается структурой именования, связанного с принадлежностью ресурса какой-то подсистеме, какому-то конкретному компьютеру в ней (к примеру, если речь идет о размещении базы данных),
дескриптором, характеризующим характеристики ресурса (для па­мяти - время обращения, для компьютера - быстродействие и объем опе­ративной и дисковой памяти и др., для программы, предназначенной для решения систем линейных уравнений - это метод, его точность, вычисли­тельная сложность, требуемая память и др.), возможность его адаптации к задаче (пример генетических алгоритмов), возможность репликации идр.,
разрешенным доступом к ресурсу, определяющим способ обра­щения к нему и круг других ресурсов, которым разрешено ресурс ис­пользовать.
О состоянии и использовании ресурса
Ресурс с позиций его использования помимо технических или «про­граммных» характеристик, отраженных в его описании, характеризуется:
способностью выполнять свои функции (компьютер работоспо­собен или отказал, находится в процессе диагностики, в программном ресурсе обнаружена ошибка и т.п.),
состоянием (ресурс занят или свободен),
загруженностью (у компьютера n задач, свободная память VCB, интенсивность обмена между дисковой и оперативной памятью 1д, ин­тенсивность обмена с другими элементами PC, например, с другими компьютерами 1об и др.). Кстати, у ОС Windows все эти характеристики измеряются, их можно получать автоматически,
использованным процессами процессорным временем, общим временем выполнения идр., что важно для программных ресурсов.
Для разделяемых программных ресурсов особенно важны данные о количестве (интенсивности) запросов к ним, приоритетах и времени их обслуживания, времени доступа к ним и др.
Естественно, что идеально, если ресурс сам может контролировать свое состояние и использование. Компьютер может многое делать сам, используя средства ОС. С программным ресурсом сложнее, эти характе­ристики приходится получать косвенно, как правило, обращаясь к управ­лению, которое через соответствующие «службы» выполняет эту работу.
Об основных функциях управления PC
Очевидно, что для того, чтобы управлять PC, необходимо иметь статическую информацию обо всех её ресурсах, содержащую данные о местоположении и характеристики, а также динамическую информа­цию, касающуюся состояния и использования. Помимо всего, рассмат­ривая управление в общем случае как децентрализованное или смешан­ное (т.е. также распределенное, как и сама система), необходимо опре­делить общие и частные (в зависимости от схемы управления) правила, по которым узлы управления взаимодействуют между собой при совме­стном решении задачи.
Рассмотри функции управления PC более детально, выделив в нём наиболее общего значения блоки.
Эти блоки целесообразно разделить на два подмножества: блоки управления системного уровня и блоки управления процессного уровня.
Первые ответственны за управление и поддержание целостности PC в целом, вторые - за управление «рабочими» процессами, проте­кающими в PC.
К системным блокам мы отнесём следующие блоки.
Блок администрирования PC, выполняющий функции по «ручно­му» конфигурированию PC и инсталляции на ней необходимых про­граммных средств.
Блок динамической реконфигурации, который подобно админист­ратору PC выполняет функции по изменению конфигурации PC (из-за отказов и восстановлений её компонентов, из-за необходимости мас­штабирования в процессе функционирования и т.п.) автоматически.
Блок отказоустойчивости, непосредственно взаимодействующий с блоком реконфигурации, который ответственен за поддержание работо­способности PC в случае отказов её компонентов. Для этой цели обычно применяются схемы резервирования, периодического запоминания на выделенных носителях памяти состояний (контекстов) программных компонентов PC, которые передаются для восстановления выполняемо­го процесса в случае отказа компьютера. Возможны другие, более эф­фективные методы обеспечения отказоустойчивости, например, осно­ванные на статистически или динамически устанавливаемой договорён­ности между компьютерами и подсистемами PC с целью взаимной ре­акции на отказы и восстановления.
Блок регулирования загрузки компонентов PC, основной целью ко­торого является её равномерное распределение. Этот блок взаимодейству­ет с блоком определения загруженности каждого компьютера PC, получая периодически от него контролируемые параметры загрузки. Наиболее важными из них являются: объём свободной оперативной памяти, частота обменов страницами между дисковой и оперативной памятью, величина трафика сообщений, которыми компьютеры PC обмениваются в процессе её работы, количество процессов, которые выполняет компьютер и др.
Блок регулирования загрузки (он рассматривается как часть управ­ления некоторой подсистемы PC), получая эти данные, определяет за­грузку подчинённой ему подсистемы, возможно, её девиацию, более точ­но характеризующую степень неравномерности загрузки компьютеров, а также определяет некоторый прогноз, как будет изменяться загрузка в ближайшее время [8]. По этой информации управление принимает реше­ние, какие компьютеры должны передать часть своих процессов другим компьютерам с тем, чтобы попытаться их загрузку сделать одинаковой. При иерархической организации общего управления PC может сущест­вовать множество специализированных подсистем управления: управле­ние компьютером, конкретной частью (подсистемой) PC, управление бо­лее высокого уровня, осуществляющее взаимодействие между подсисте­мами управления более низкого уровня и одновременно взаимодейст­вующее с управлением более высокого уровня, снабжая его необходимой информацией о загруженности подчинённых компонентов.
Интерфейсный блок, который обеспечивает согласование сообще­ний, передаваемых между компьютерами (сообщения могут быть на разных языках), собственно их приём и передачу.
Блок информационной безопасности, который ответственен за вы­полнение всех установленных правил использования ресурсов и их защи­ты от несанкционированных попыток обращения к ним, намеренного разрушения, внесения вирусов и т.п. Если блок отказоустойчивости в ос­новном реагирует на неполадки в аппаратуре, то данный блок имеет дело с программными ресурсами.
Информационный блок PC, который подобно адресной книге (или порталу), актуализирует все данные о ресурсах PC, их местонахожде­нии, использовании и др.
Блоки управления PC процессного уровня выполняют функции, непосредственно связанные с выполнением и синхронизацией «рабо­чих» процессов, индуцируемых при выполнении пользовательских про­грамм, а также запросов к базам данных, файловым системам и т.п.
Многие из этих функций, такие как сохранение и восстановление контекста при прерывании и активизации процесса, реакция на команды взаимодействия между процессами, собственно выполнение процесса по сложившейся схеме в компьютере и др., выполняются непосредственно ОС компьютера или сетевой ОС, если у процесса возникает необходи­мость обращаться, например, к удалённым web-службам, базам данных.
Сложнее обстоит дело, если пользователь хочет организовать па­раллельное выполнение своей программы, причём стандартные средст­ва ОС (процессы - нити, и т.п.) неадекватны его цели. В этом случае обычно необходим интерпретатор, который выявляет в программе мо­гущие одновременно выполняться фрагменты, необходим планиров­щик, который, взаимодействуя с интерпретатором, устанавливает при­оритеты для одновременно выполняемых фрагментов, а через блок на­значения ресурсов процессам (этот блок в отличие от системного блока регулирования загрузки решает не стратегические задачи в разделении ресурсов, а практические, назначая процессам необходимые ресурсы и соблюдая заданные им приоритеты).
Таким образом, и на процессном уровне появляется множество нестандартных блоков, вовлечённых в процесс управления PC, которые приходится создавать как определённое расширение ОС.
О реализации управления PC
В предыдущем пункте мы попытались вычленить основные (оче­видно, не все) имеющее самостоятельное значение блоки, предназна­ченные для организации управления PC. Разделение этих блоков на сис­темные и процессные вносит очевидное соподчинение между ними.
В PC должны поддерживаться различные, могущие динамически изменяться, схемы управления, и должна бать разработана технология их построения на основе определённой функциональной декомпозиции управления в целом.
Другая задача - это создание среды проектирования, которая по­зволяет, используя в основном стандартные программные средства бы­стро реализовать различные схемы управления PC.
Многоагентный подход к построению управления [1] позволяет объединить различные модели управления. Естественно, что перечис­ленные выше блоки управления PC могут рассматриваться как специа­лизированные агенты, предназначенные для этой цели.
Вполне очевиден и путь построения агентов, поскольку объектно-ориентированное программирование в большой степени упрощает реше­ние этой задачи [2]. Более того, сегодня уже существуют инструменталь­ные среды, которые упрощают реализацию многоагентного подхода [3-6].
Средства программирования многоагентных систем, основанные на понятии агента и на языке Java [4], сменяют более мощные среды с более проработанной технологией использованием объектно-ориенти­рованных языков для этой цели (к примеру, назовём IBM aglets work bench [6]).
Комплексное решение проблемы создания эффективных средств для управления PC, сетями и т.п. потребует большей интеграции с рабо­тами, которые активно ведутся в области создания web-сервисов [7], распределённых баз данных и др. Остаются актуальными и чисто мате­матические проблемы оптимизации управления распределения ресур­сов, распараллеливания программ, обеспечения надёжности PC [8].
Заключение
В настоящее время мы разрабатываем технологию построения программных средств для систем управления PC, которая нацелена на существенное сокращение времени их проектирования, которая учиты­вает естественную эволюцию PC, изменение их структуры и схем управления и которая базируется на указанных инструментальных сре­дах для их создания.
Работа выполнена при поддержке РФФИ, проект 03-01-00588
Литература
Городецкий В.И. и др. Многоагентные системы (обзор) // Новости ис­кусственного интеллекта. 1998. №2.
Буч Г. Объектно-ориентированный анализ и проектирование с приме­рами приложений на C++ // М.: Издательство «Бином», 1998.
Puliafito A. et all. MAP: Design and implementation of a mobile agent's platform // Journal of System Architecture, 2000. №46.
Lange D.B., Oshima M. Mobile agents with Java. IBM Tokyo research laboratory, 1998.
Lange D.B., Aridor Y. Agent design patterns: elements of agent application
design. ACM Press, 1998.
Oshima M., Karjoth G. Aglets specification 1.1 Draft. IBM Tokyo research laboratory, 1998.
Скотт Ш. Разработка XML web - сервисов средствами Microsoft.Net // СПБ.: БХВ - 2003.
Кутепов В.П. Об интеллектуальных компьютерах и больших компью­терных системах // Теория и системы управления, 1996. №5.

МОДИФИЦИРОВАННЫЙ ВЕЙВЛЕТ-АНАЛИЗ ИЗОБРАЖЕНИЙ С ПОМОЩЬЮ КОЛЬЦЕВОГО ПРЕОБРАЗОВАНИЯ РАДОНА

А.А. Ковалев , В.В. Котляр
1 Самарский государственный аэрокосмический университет, г. Самара, Институт систем обработки изображений РАН, г. Самара,
Рассмотрено направленное вейвлет-преобразование двумерных функций. Для более эффективного его выполнения предложено использо­вать кольцевое преобразование Радона как среднее по всем окружностям фиксированного радиуса на плоскости. Предложена схема вычислений для набора углов и масштабов направленного вейвлет-преобразования.
Введение
Вейвлет-анализ возник при обработке записей сейсмодатчиков в нефтеразведке и с самого начала был ориентирован на локализацию разномасштабных деталей. Выросшую из этих идей технику теперь обычно называют непрерывным вейвлет-анализом. Ее основные прило­жения: локализация и классификация особых точек сигнала, вычисле­ние его различных фрактальных характеристик, частотно-временной анализ нестационарных сигналов. Например, у таких сигналов, как му­зыка и речь, спектр радикально меняется во времени, а характер этих изменений - очень важная информация. Вейвлет-анализ также применя­ется в сжатии данных, фильтрации, системах распознавания образов, синтезаторах речи, медицине, метеорологии.
Вейвлет-преобразование является разложением функции по бази­су, образованному вейвлетами - солитонообразными функциями двух аргументов - масштаба и сдвига [1]. В отличие от преобразования Фу­рье, множество базисных функций имеет размерность 2, а не 1. Тогда при анализе двумерных функций множество базисных функций должно иметь размерность 4, что приводит к вычислительной сложности. Чтобы устранить этот недостаток, существует несколько подходов.
В [2] предлагается использовать тензорное произведение одно­мерных вейвлетов. То есть, по аналогии с традиционными спектраль­ными преобразованиями, двумерное вейвлет-преобразование выполня­ется как последовательность одномерных преобразований над строками и столбцами изображения.
В [3] предлагается «шахматная» схема вейвлет-преобразования изо­бражений, базис которой образован функциями с высокой степенью изо­тропии. Такой подход позволяет избежать крестообразного характера ба­зисных функций и появления на плоскости четырех выделенных направ­лений (по обеим осям и по диагоналям). Эта схема хорошо подходит для изображений, на которых преобладают изотропные элементы («пятна»).

Существует класс изображений с отсутствующими выделенными направлениями, и при этом объекты на изображении неизотропны. К такому классу относятся, например, медицинские изображения сосуди­стых систем. Объекты (сосуды) на таких изображениях могут иметь произвольное направление и для анализа их сечений можно применять одномерное вейвлет-преобразование под разными углами.
Направленное вейвлет-преобразование
Традиционное вейвлет-преобразование имеет вид:
-СО
F(a, b) = -= j f (x)Y — dx . (1)
V a j
Заменой переменной получим следующую форму вейвлет-преобразования:
F(a,b) = 4a j f (b + at)Y(t)dt
-Ґ . (2)
Определим направленное вейвлет-преобразование следующим об­разом:
F(a,9,X /n)=Va j f (X + at cos9 ,h + at sin e)Y(t)dt. (3)
-co
Очевидно, при e= о и е=л/2 выражение (3) будет являться соот­ветственно постолбцовым и построчным одномерным вейвлет-преобразованием двумерной функции.
Рассмотрим свертку двумерной функции f(x,y) со следующим ядром:
h(x,y)=_L5(xsine -ycose)pf- xcose + ysinel. (4)

В результате свертки будет получена следующая функция (при e *pkj2,k е Z ):
g(X,h) = ˜ajjf (X -x,h-y)5 (xsine -ycose)Y[ -xcose + ysine ^dxdy =
\a R2 V a J
= {x = w cos e, y = v sin e} =

sin e cos e
dudv ¦¦
^ u cos2e + vsin2 e ^
4= jj f (X - и cose ,h - v sine )5 [(и - v) sine cose ] Y
"V a r2
—j= j f (X - и cose ,h - и sin e ) YJ^ J du = {u = - at} =

л/a j f (X + at cose ,h + at sine)Y(t)dt
(5)
To есть для фиксированного масштаба a и угла e направленное вейвлет-преобразование является сверткой с импульсной характеристи­кой (4) и может быть эффективно вычислено с помощью Фурье-коррелятора.
Однако если используется целый набор углов 9 и масштабов a, для каждого угла и масштаба нужен свой пространственный фильтр и, следовательно, требуется отдельное выполнение преобразования Фурье. В данной работе предлагается вычислительно более эффективный под­ход, основанный на кольцевом преобразовании Радона (КПР) [4].
Кольцевое преобразование Радона
В данной работе под КПР будем понимать суммирование (усред­нение) по всем окружностям с фиксированным радиусом у ис центром в точке (x ,h):
2л-
R (Х ) 7 J f (X+ 7 C0SJ 'h+ 7 j) dj
R (X ,h) = 0 . (6)
В [4] показано, что КПР можно представить в виде Фурье-коррелятора, функция комплексного пропускания пространственного фильтра которого равна:


У = \). (7)
Можно показать, что кольцевым импульсным откликом обладают также Фурье-корреляторы с функцией комплексного пропускания про­странственного фильтра, имеющей следующий вид (в полярных коор­динатах):
HУ (р ,9) = exp (-ив) Jn (ур). (8)
Преобразование в таком Фурье-корреляторе имеет вид:
2 ж
Ry (X ,h ) = [ f (X + У cos j ,r\ + у sin j) exp (/np) dj
0 . (9)
Преобразование (9) будем называть кольцевым преобразованием Радона n -го порядка. Видно, что преобразование (6) соответствует ну­левому порядку.
Взвешенное кольцевое преобразование Радона
В [5] предлагается обобщение традиционного преобразования Радо­на - так называемое экспоненциальное преобразование Радона, имеющее следующий вид:
+СО
Rm (p, a) = Г f (p cos a +1 sin a, p sin a -1 cos a) exp (\xt) dt
-? . (10)

По аналогии, можно рассмотреть дальнейшее обобщение преобра­зования (6) - взвешенное кольцевое преобразование Радона (ВКПР), ин­тегрирование по окружности в котором происходит с некоторой весо­вой функцией (периодичной спериодом 2% ):

Rm(j) (X,r) = у j f (X + У cos j, r + у sin j) m (j) dp
0 , (11)
ВКПР может быть выражено через КПР разных порядков в виде
ряда:

Rym(j)(X ,r) = 2*уУ> i)n m nRyn (X ,r)
-СО

(12)

где Ryn(X,r) определяются из (9), mn - коэффициенты разложения m(j) в ряд Фурье:

1 2%
(13)


Выполнение направленного вейвлет-преобразования с помощью взвешенного кольцевого преобразования Радона
Выражение (3) можно преобразовать следующим образом:

F(a,9,X,r) = Va j f (р + at6)Y(t)dt = 4a j f (p +y61 + ate-y61)Y(t)dt

-СО
-СО



Va j f P +У 61 + Va2t2 +
-СО
at
.6

a
y
2t2 +y2
rQ1


00
Y(t )dt:













где
4a j f (p +y 61 +Va 2t2 +y2 ( sin j- 6 - cos j • 61))Y(t )dt
61 +4a
2t2 +y2
p+y
p
sin (j -9) cos (j -9) cos (л/2 -j+9)1^







(14)

at
2t2 +y2



cos j
Va 2t2 +y2

При t <<g И g>> 0 -у/а2t2 +g 2 »Y , sinф»ф И
место приближенное равенство: Y
at at r-p
= » —. 1огда имеет


F (a,9, X ,л) = 4-j /
cos (ж/2 +9 -ф)1^ sin(ж/2 +9 -ф)
0

Y| Yj I ф a 0



. (16)


y| ^(ж/2+9-ф') Iф'
= {ж/2 +9-ф=ф'} = ^ f f\p+y 61+y
Если функция Y(t) имеет компактный носитель, то при достаточ­но большом y можно считать Y^— +9 -ф')0 = 0 при ф'<ё[-ж,ж]. Тогда
F(a,9,X,ч) = 4= f f (X +Y sin9 +y аюф',ч -g cos9 +y sinф')?| ^(ж/ +9 -ф'УЦр'. (17)
Va -Ж I.aV 2 70
To есть направленное вейвлет-преобразование может быть пред­ставлено в виде ВКПР, причем для разных углов 9 и масштабов a ме­няется только весовая функция y .
Для выполнения направленного вейвлет-преобразования для од­ного угла 9 и масштаба a использование ВКПР не оправдано. Действи­тельно, при использовании Фурье-коррелятора требуется N2 умноже­ний и одно БПФ (порядка n2iog2 N операций). При использовании ВКПР с весом используется линейная комбинация из p КПР разных порядков (то есть около 2PN2 операций), где P - число используемых КПР-образов, по которым разложено исходное изображение. Например, при обработке изображения 512x512 отсчетов и использовании 21 КПР-образов (с -10 по 10 порядки) использование коррелятора требует по-
2 2
рядка 10 N операций, а использование ВКПР требует около 42N .
22
ц" = — |ц'(фУ"фф = — |ц(ф -аУ"фф
(18)
Однако при использовании набора углов 9 можно использовать более быстрые алгоритмы. Заметим, что при использовании ВКПР с ве­сом ц'(ф)= ц(ф-а) коэффициенты разложения в формуле (12) будут иметь вид:
= втац"
1 2ж 1
— |У(ф>мф <ф> = —
2ж 0 4 А 2ж
Легко заметить, что при а=ж ц' = (-1)" цn, то есть можно реализо­вать вычислительно более эффективную схему. Рассмотрим множества

dr- {n e Z : n = dk + r, к e Z} . Обозна-
(19)
(20)
чисел, делящиеся на d с остатком r: N чим
sdr (X ,л) = 2py2(-' )" m„R" )(X ,h).
neN„r
Тогда




S20 (X ,h)


i -i
_ S21 (X ,л)_

Аналогично, умножение на степень числа i выполняется триви­ально, поэтому можно проводить вычисления с расщеплением «по ос­нованию 4»:






R^-3"' 2)(X ,h)
1

1 1

1"
S40 (X ,h)
-i
S41 (X ,h)
-1
S42 (X ,h)
i
_S43 (X ,h)


(21)

Данный алгоритм более эффективен по сравнению с Фурье-корреляторами для каждого угла и масштаба. Например, при использо­вании алгоритма с расщеплением «по основанию 4», когда изображение имеет размеры 512x512 отсчетов, используются КПР-образы с -10-го по 10-й порядки и число углов 9 равно 32, мультипликативная сложность составляет 168N2 операций, в то время как при использовании Фурье-корреляторов около 32(n 2 + ^3 N2 log2 N)= 224N2.
Параллельное выполнение направленного вейвлет-преобразования с помощью взвешенного кольцевого преобразования Радона
для всех n e N4k. Затем та же машина вычисляет сумму S
Использование Фурье-коррелятора для каждого угла 9 и масштаба a может легко выполнятся параллельно. Можно, например, разделить вычисления для разных углов и масштабов по разным машинам. Вы­полнение направленного вейвлет-преобразования с помощью ВКПР также может вычисляться параллельно. Однако распределение вычис­лений по машинам должно быть не произвольным. Наиболее трудоем­ким этапом является выполнение КПР разных порядков R (X ,л). Логич­но производить вычисления для разных порядков на разных машинах, но тогда для избежания избыточной пересылки данных при вычислении сумм (19) для всех n e Ndr R (X ,h) должны вычисляться на одной маши­не. Например, в случае четырех машин алгоритм с расщеплением «по основанию 4» может быть следующим: к -я машина вычисляет R (X ,л)

(X ,л). Далее

115
все четыре суммы S4к (X ,л), к = 0,3 пересылаются на одну машину, на ко­торой по формуле (21) вычисляются rj1^-^2)(x,ч).
Заключение
В данной работе рассмотрено направленное вейвлет-преобразование двумерных функций. Для более эффективного его выполнения предложе­но использовать кольцевое преобразование Радона как среднее по всем окружностям фиксированного радиуса на плоскости. Введены кольцевое преобразование Радона произвольного порядка и взвешенное кольцевое преобразование Радона. Предложена схема вычислений для набора углов и масштабов направленного вейвлет-преобразования.
Благодарность
Работа выполнена при поддержке международного гранта CRDF REC-SA-O14-02 и президентского гранта РФ НШ-1007.2003.1.
Литература
1. Новиков Л.В. Основы вейвлет-анализа сигналов // Учебное пособие.
1999.
Lemarie P.-G., Meyer Y. Ondelettes et bases helbertiennes // Rev. Mat. Iberoamericana, 1986. V. 1. P. 1-17.
Толкова Е.И. Wavelet-анализ изображений // Оптический журнал, 2001. Т. 68. №3. С. 49-59.
Котляр В.В., Ковалев А.А. Кольцевое преобразование Радона // Компьютерная оптика. 2003. №25. С. 126-131.
Rullgard H. An explicit inversion formula for the exponential Radon transform using data from 180 // Research Reports in Mathematics, Stockholm University, 2002.


КЛЕТОЧНАЯ МАШИНА
И.Н. Кожин, В.А. Воробьёв, Г.В. Лозинская
Поморский государственныйуниверситет, г. Архангельск
Введение
В статье даётся введение в клеточные автоматы, затем понятие кле­точного автомата расширяется до клеточной машины, и описывается разра­батываемая авторами программа создания собственных клеточных машин.
Мало кто знает, что основоположник архитектуры современных ЭВМ, Джон Фон Нейман, помимо классической ЭВМ (куда входит вы­числительное устройство - процессор и оперативная память, в которой располагается программа для работы процессора, и данные, которые он обрабатывает; программа же определяет, как будут обрабатываться данные), разрабатывал альтернативную, параллельную архитектуру, со­единив понятие «вычислительное устройство» и данные, с которыми система оперирует. При этом вычислители и данные пространственно распределены и образуют собой решающее множество различной кон­фигурации - плоскость, кольцо, тор, трёх- и более мерные кубы. Дан­ные и вычислительные устройства собираются из одних и тех же струк­турных элементов. Такая архитектура эволюционировала в то, что мы теперь называем «Клеточные автоматы» (КА).
Чтобы представить себе КА, мысленно нарисуйте прямоугольную решётку, в каждой ячейке которой располагается конечный автомат (автомат с определённым количеством внутренних состояний и кон­кретным набором входных и выходных сигналов, причём в каждый мо­мент времени выходные сигналы однозначно определяются входными и внутренними состояниями). Выходы каждого из этих автоматов напря­мую соединены со входами своих соседей. То, какие ячейки соединены между собой, определяет шаблон соседства.
Более формально определение К А звучит так: клеточные автоматы являются дискретными динамическими системами, поведение которых полностью определяется в терминах локальных зависимостей.
Рассмотрим основные преимущества клеточного подхода в реше­нии научных и практических задач.
Очевидное преимущество КА перед классической архитектурой -это параллельность выполняемых операций. При этом не все известные на сегодняшний день параллельные алгоритмы обладают свойством масштабируемости (когда увеличение количества процессоров ведёт к пропорциональному уменьшению времени расчёта задачи в целом). Клеточные же алгоритмы по определению обладают этим свойством.
Очередное достоинство клеточных алгоритмов в том, что создав, например, поле 100x100, и отладив наш алгоритм, мы можем дробить это поле сколь угодно много (пока у нас хватает процессоров или пока не достигнем любой необходимой погрешности), т.е. алгоритм и время вычислений не изменяются, а точность расчётов увеличивается.
Мелкозернистость. Мелкозернистость означает, что количество вычислений в каждой клетке не зависит от размера задачи. Действи­тельно, для автомата каждой клетки не важно, сколько всего имеется ячеек в клеточном множестве, при увеличении размера клеточного множества количество вычислений в автомате не возрастёт.
КА по своей структуре близки к моделированию полей различной природы, жидкостей, газов. Действительно, рассмотрим, например лю­бую жидкость - в ней каждая молекула (ячейка КА) сама «знает» (лишь на основе информации от ближайших молекул), как ей взаимодейство­вать с соседями - отталкиваться или притягиваться, диффундировать и т.д. Таким образом, клеточная модель более естественна для близко­действующих динамических явлений.
Правила, по которым действует КА, значительно проще диффе­ренциальных уравнений, необходимых для описания того же явления обычным непараллельным алгоритмом, что даёт возможность упрощать и удешевлять процессоры в клетках.
Наглядность. Следующее преимущество КА - лёгкость визуализа­ции. Всегда можно сопоставить значения внутренних состояний клеток определённому цветовому диапазону. В этом случае человек одним взглядом может охватить всю картину в целом, например распределение температур при нагреве металла, зоны турбулентности, распределение плотности в пространстве, кроме того, запустив КА на выполнение, мож­но видеть, как меняется картина в динамике.
Применять клеточные алгоритмы в своей научной и профессио­нальной деятельности могут учёные и инженеры самых разных профес­сий. Рассмотрим основные сферы применения.
Моделирование физических, биологических, экологических, соци­альных и прочих процессов, в т.ч. непрерывных динамических систем, определенных уравнениями в частных производных. Сюда относятся, например, взаимодействие молекул вещества, газа, распространение вещества в среде, диффузия, моделирование лесных пожаров, распро­странения загрязнения в атмосфере, эрозия почвы.
В компьютерной графике и задачах искусственного интеллекта клеточные автоматы нашли своё применение в распознавании и обработ­ке изображений. В частности, к обработке изображений относится, на­пример, морфинг - плавное преобразование одной картинки в другую. На основе клеточных автоматов строятся клеточные нейронные сети.
Применяются клеточные автоматы и в области кодирования ин­формации. Здесь их используют для помехоустойчивого кодирования, для шифрования, (когда на основе данной картинки, зная только шиф­рующее правило, можно раскодировать изображение) и для сжатия (ес­ли из менее заполненной картинки можно получить за некоторое коли­чество тактов времени искомую, то можно хранить лишь первую кар­тинку и правила её преобразования).
В математике уже существует большое количество мелкозерни­стых локально-параллельных алгоритмов, применимых для различных областей наук.
Итак, применение КА довольно широко, но существуют некото­рые свойства, присущие КА по определению, которые сужают возмож­ные сферы использования КА. К таким свойствам относятся:
КА может иметь конечное количество внутренних состояний;
шаблон соседства одинаковый по всему полю;
алгоритм автомата жёстко задан и неизменен;
изменения переменных у соседей.
В связи с вышеописанными недостатками КА авторами предлага­ется новая архитектура ЭВМ - клеточная машина (КМ). Основное от­личие КМ от КА - то, что в каждом узле решающего поля расположен не автомат, а процессор, оперативная память и коммутационное устрой­ство для связи с соседями и управляющим устройством. В оперативной памяти находится изменяемая программа, по которой работает процес­сор. Причём процессор может отправлять запросы на чтение и запись соседним узлам.
Основное преимущество КМ перед КА в том, что первая работает по программе, (алгоритмические возможности программы зависят от набора команд конкретного процессора - это может быть привычная программа с циклами, ветвлениями, подпрограммами и классами), в то время как КА работает по строго заданному неизменяемому алгоритму. В связи с присутствием оперативной памяти количество внутренних со­стояний теперь ограничено лишь её размером, и в принципе, о внутрен­них состояниях уже говорить не приходиться - теперь можно пользо­ваться привычными для программистов переменными.
Если клеточный метод моделирования и решения задач подходит для вашей профессиональной или научной деятельности, то следующий вопрос - как создать КА или КМ. Здесь есть два варианта - либо реали­зовать КА аппаратно, либо использовать его в откомпилированном виде на ПК для расчёта и для просмотра результатов визуализации. Рассмот­рим второй путь, как наиболее простой в реализации. Для программиро­вания поточным способом существуют средства разработки программ. Задачи для клеточного подхода приходится решать с помощью универ­сальных языков, т.е. для решения конкретной задачи пишется новая про­грамма на каком-либо языке, что ставит определённые барьеры в использовании клеточного подхода - человек должен разбираться не только в изучаемом явлении, но и уметь довольно хорошо программировать. Поэтому авторы поставили перед собой задачу создать универсальный инструментарий для разработки, отладки, прогона и анализа результатов программ для КМ.
Создав и отладив подходящий для решения конкретной задачи КА или КМ (определив правила для клеток, топологию и пр.), в дальней­шем можно реализовать его аппаратно или использовать в откомпили­рованном виде на обычном компьютере.
В заключение кратко рассмотрим возможности нашей программы.
Данный программный продукт предназначен для учёных, инжене­ров, программистов, в деятельности которых может использоваться мо­дель клеточного автомата.
Возможности:
возможность задавать первоначальные конфигурации клеточного множества (параметры множества)
топология
тор, кольцо (вертикальное, горизонтальное), плоскость
задание любого шаблона соседства
отображение множества
выбор отображения для клеток класса
выбор отображаемых переменных и их количества
масштабирование.
Выбор языка для создания клеточной программы, с которым вы привыкли работать1. Планируется также поддержка DVM-технологии. Возможности программы для клетки:
может быть синхронной и асинхронной с алгоритмом перебора, задаваемым пользователем;
возможность обращаться к переменным из клеток-соседей в про­грамме для данной клетки;
запись рассчитанных множеств в файл с возможностью просмотра в любом направлении.
Литература
Тоффоли Т., Марголус Н. Машина клеточных автоматов // Москва: Мир, 1991.
Воробьёв В.А. Эффективность параллельных вычислений // Автометрия, 2001. №5.
Воробьёв В.А., Лаходынова Н.В., Ерёмина Н.Л. Отказоустойчивость однородных процессорных матриц // Томск: Изд. ТГАСУ, 2002.
Ачасова СМ., Бандман О.Л. Корректность параллельных вычислитель­ных процессов // Нововсибирск: Наука, 1990.


АВТОМАТИЗИРОВАННЫЙ АНАЛИЗ ПАРАЛЛЕЛИЗМА ПРОГРАММ

Н.Е. Козин, В.А. Фурсов
1 На данный момент к компилятору предъявляются следующие требования: он должен генерировать объектный код формата Win32 PE с экспортируемыми функциями (проще говоря, файлы Win32 dll), но и это ограничение, в принципе преодолимо - наша программа тестировалась и с клеточными функциями, написан­ными на Pascal для ДОС и VBScript.
Институт систем обработки информации, г. Самара
Введение
В последние годы усиливается внимание к использованию высоко­производительной вычислительной техники в научных исследованиях и образовании. Однако построение параллельных вычислительных процес­сов, обеспечивающих достижение высокой производительности, является серьезной проблемой. Перенос обычной программы на многопроцессор­ную вычислительную систему связан со значительными трудностями, свя­занными с нахождением параллельных участков программы.
В настоящей работе рассматривается учебная программная систе­ма автоматизированного анализа, предназначенная для использования в учебных целях при проведении лабораторных и учебно-исследовательских работ.
Программная система разработана на основе методик формально­го анализа алгоритмов, описанных в работе [1]. Краткое описание этих методик приведено в разделе 2 настоящей работы.
1. Методики анализа параллелизма программ
В любой программе можно выделить два типа операторов: логи­ческие и арифметические. Логические определяют связи по управле­нию. Они задают состав и порядок выполнения арифметических опера­торов. Арифметические же операторы могут выполняться только в по­рядке, определенном информационными связями между ними. Возмож­ность распараллеливания алгоритмов зависит не только от логической схемы алгоритма, но и от степени детализации операторов.
В любом случае степень детализации операторов должна учиты­вать архитектуру ВС. Определяющими при распараллеливании являют­ся два фактора:
информационная и логическая взаимосвязь операторов (исполь­зование одними операторами выходной информации других операто­ров);
объем работ в каждом операторе.
Связанные с объёмом работ временные характеристики операто­ров ti, i=1, N (где N - число операторов) называют их весом. Если ВС однородная, достаточно оценить время ti, выполнения каждого операто­ра на одном процессоре.
При составлении информационно-логической граф-схемы алго­ритма необходимо руководствоваться действительной зависимостью между операторами, обусловленной преемственностью информации.
Переход от обычной схемы алгоритма или программы к модели в виде граф-схемы дает более ясное представление о структуре алгорит­ма, его свойствах и возможности направленных преобразований.
Рис. 1. Примерматрицы следования S
Вершине (оператору) i графа ставят в соответствие i-ю строку и i-й столбец матрицы. Элемент (i, j) этой матрицы будем отмечать знаком • или цифрой 1, если между операторами с этими номерами существует какая-либо связь (по управлению или информации). Для различения ти­па операторов там, где это необходимо, связи по управлению будем от­мечать знаком •, а связи по информации - единицей (1) (см. рис. 1). Можно показать, что по графу без контуров может быть построена тре­угольная матрица следования с нулевыми элементами на главной диа­гонали, что упрощает некоторые задачи их анализа.
Для исследования матриц S необходимо отразить в них неявные связи между операторами, которые реально существуют и определяют­ся задающими связями. Их введение необходимо, во-первых, для выяв­ления контуров в графе. Кроме того, решение задач распараллеливания как раз и заключается в выявлении дополнительных, в явном виде не существовавших связей между операторами. Рассмотрим способы уста­новления этих связей.
Если существуют задающие связи Р®у и у®8, но нет задающей связи Р®8, то дополнение вычислительной схемы такими связями не меняет результата решения задачи, а лишь подтверждает недопусти­мость определенного порядка следования операций. Связи, которые введены направленно внутри всех пар операторов, принадлежащих од­ному пути в графе G и не связанные задающими связями, образуют множество транзитивных связей. Транзитивные связи могут быть вве­дены путем формальных преобразований матрицы S по следующему ал­горитму: строки матрицы просматриваются последовательно сверху вниз. В каждой (i-й) строке просмотр элементов производится в порядке увеличения номеров столбцов. Если в очередном (/-м) столбце имеется знак •, указывающий на существование связи по информации или управлению, одноименные элементы строк с номерами i и j складыва­ются по правилу дизъюнкции:
•u^=» ^и0=» 0u^=» 0kj0=0.
Возможности алгоритма по распараллеливанию можно также вы­явить, если использовать только информационные связи. Дело в том, что эти связи прямо указывают на то, что образующие их операторы не могут выполняться одновременно (параллельно). Такие операторы на­зываются логически несовместимыми. Для выявления таких операторов используется матрица L - логической несовместимости, которая формируется следующим образом.
Вначале по исходной треугольной матрице S, в которой связи по управлению отмечены знаком •, а связи по информации - 1, формиру­ются задающие связи логической несовместимости операторов по сле­дующим правилам: последовательно просматривают столбцы j=1, M, (где M - число вершин в графе) матрицы S. Если очередной элемент /)=•, и ранее в этом столбце также были зафиксированы элементы /)=•, k=1,m-1, то все элементы в i^-й строке с номерами (по столбцам) совпадающими с номерами строк, в которых ранее встречался знак •, заполняются единицами до -го столбца включительно.
Далее на основе заданных связей логической несовместимости оп­ределяется несовместимость для всех операторов схемы. Для этого вво­дятся транзитивные связи логической несовместимости по следующим правилам.
Последовательно просматривают строки треугольной матрицы следования S, дополненной транзитивными связями (нулевые строки пропускают). В очередной ненулевой i-й строке матрицы S анализируют множество ненулевых элементов. Из этого множества исключают номе­ра операторов, образующих входы матрицы S, т.е. обнуляют элементы в столбцах, номера которых совпадают с номерами нулевых строк. С ис­пользованием оставшегося множества номеров операторов формируют строки i . Для этого объединяют по операции конъюнкции строки мат­рицы L с номерами, соответствующими номерам столбцов, в которых остались ненулевые элементы. Если ненулевой элемент в строке один, то строку i полагают равной строке матрицы L с номером равным но­меру столбца ненулевого элемента в анализируемой строке. Далее фор­мируют новую i-ю строку в матрице L на основе ее старого значения и вновь сформированной строки i с помощью операции дизъюнкции i=iui . Наконец, i-й столбец матрицы L полагают равным вновь сфор­мированной i-й строке.
При распределении работ между процессорами важно установить множество тех операторов, внутри которого имеет смысл решать задачу распараллеливания выполнения операторов. Для этого необходимо объ­единить информацию о логической несовместимости операторов и их информационно-логической связи по следующим правилам.
Вначале по матрице S, дополненной транзитивными связями, строят матрицу следования S путем симметричного отображения эле­ментов матрицы S, относительно главной диагонали (или сложением матрицы с ее транспонированной). Далее на сформированную матрицу S' накладывают матрицу L, дополненную транзитивными связями. Каж­дый элемент новой матрицы M - матрицы независимости, формируется из одноименных элементов матриц S и L по правилу дизъюнкции. Ну­левые элементы полученной матрицы M указывают множество тех опе­раторов, каждый из которых при выполнении некоторых условий может быть выполнен одновременно с данным, т.е. он информационно или по управлению не зависит от этого оператора и не является с ним логиче­ски несовместимым.
Матрица независимости M (см. рис. 2) отражает информационно-логические связи между операторами без учета их ориентации, а также связи логической несовместимости операторов с учетом всех транзитив­ных связей.













Рис. 2. Матрица независимости M для матрицы следования S

При решении задач распараллеливания необходимо перебирать все возможные полные множества ВНО и находить максимально полное множество ВНО, содержащее максимальное число операторов. Для его нахождения используется тот факт, что если два оператора v взаим­но независимы, то при сложении по правилам дизъюнкции ц-й и v-й строк матрицы независимости M образуется строка, в которой элементы в ц-м и v-м столбцах обязательно нулевые.
Ранние и поздние сроки окончания выполнения операторов удоб­но определять с использованием матрицы следования. Общая процедура
анализа графа со скалярными весами вершин tj строится в виде сле­дующей последовательности шагов. Положив тп = т12 =... = t1m = 0, после­довательно обрабатывают строки матрицы S. Если очередная (/-я) стро­ка не содержит единичных элементов, полагают t1j = tj. Если j-я строка
содержит единичные элементы, из множества {тп,...,t1m} выбирают подмножество элементов } v = 1,kj, соответствующих номерам еди­ничных элементов j-й строки. В случае, когда все они отличны от нуля, полагают:
Т : = Т,: + t : .
1 v=1,...,kj Jv 1
Если же среди элементов множества {т1: } v = 1,k: есть хотя бы
один нулевой (т.е. данное значение раннего срока окончания выполне­ния оператора еще не определено), переходят к следующей необрабо­танной строке.
2. Описание программной системы автоматизированного анализа
При разработке программы авторы преследовали, прежде всего, учебные цели. Тем не менее, описываемая методика и программный комплекс (который далее мы будем называть «анализатор») могут ока­заться полезными и при анализе параллелизма программ, используемых при проведении научных исследований.
Нетрудно заметить, что описанные выше правила формирования матриц следования и независимости сами являются алгоритмами и, сле­довательно, могут быть реализованы программно. Использование инст­рументальных средств автоматизированного анализа последовательных программ позволяет существенно ускорить написание параллельной про­граммы. Ниже приводится описание программы и методики автоматизи­рованного анализа параллелизма алгоритмов.
Анализатор обрабатывает алгоритмы, написанные на языке C. На основе текста программы нумеруются отдельные блоки операторов, а также выявляются их явные и неявные связи по управлению и информа­ции. После этого выводятся матрицы следования, включающие и не включающие транзитивные связи, матрица информационной зависимо­сти и итоговая матрица зависимостей.
Рабочая область программы состоит из областей для просмотра исходного текста алгоритма, области отображения пронумерованных блоков операторов, а также области отображения матриц. Диалоговое окно программы представлено на рис. 3.
После построения матриц следования пользователь может полу­чить информацию о получившихся полных множествах и сохранить её в файле. В настоящее время анализатор пока не поддерживает автомати­ческое создание исходного текста параллельной программы. Тем не ме­нее, его использование существенно ускоряет процесс написания парал­лельной программы в автоматизированном режиме.
На первом этапе анализатор выявляет связи по информации между блоками операторов программы и после этого нумерует их таким обра­зом, что получившаяся матрица следования S принимает треугольный вид. Далее она дополняется транзитивными связями. После этого про­грамма нисходящим движением по графу выявляет несовместимость блоков операторов и строит матрицу логической несовместимости L, которая также дополняется транзитивными связями и симметрично ото­бражается относительно главной диагонали. Итоговая матрица незави­симости M получается сложением предыдущих двух матриц по правилу дизъюнкции, предварительно матрица следования также симметрично отображается относительно главной диагонали.
В результате реализации описанной технологии анализа последо­вательной программы осуществляется автоматическая нумерация неде­лимых блоков операторов.
Далее формируются матрица следования S, дополненная транзи­тивными связями, матрица логической несовместимости L и итоговая матрица независимости M, являющаяся объединением двух предыду­щих. С использованием полученной матрицы независимости, путём сложения строк по правилу дизъюнкции, можно выделить множества независимых операторов. Любой блок из каждого множества независи­мых операторов может выполняться параллельно с другими блоками из данного множества.
С теоретической точки зрения целесообразно выделять множества с наибольшим количеством элементов (по возможности полные множе­ства). Однако иногда использование оптимального решения может быть нецелесообразным. Например, небольшое дробление полных множеств значительно упрощает написание алгоритма и улучшает наглядность исходного текста.
На основе матрицы независимости легко строится ярусно-параллельная форма оптимизированного алгоритма. Число процессов в нём будет равно размерности полного множества, имеющего макси­мальное число элементов.
Особо следует отметить правила обработки вызовов функций. В случае, когда функция является библиотечной, её вызов считается от­дельным неделимым оператором. Если же анализатор находит тело функции, то на место её вызова вставляется программный код данной функции. Таким образом, функция будет «развёрнута» столько раз, сколько имеется её вызовов.
Описанный анализатор пока имеет ограниченные возможности. В настоящей версии отсутствует возможность анализа конструкций, со­держащих следующие операторы: цикла for, безусловного перехода goto и безусловного выхода из блока break. Распараллеливание циклических конструкций представляет собой отдельную задачу. Использование же оператора goto приводит к появлению ненулевых элементов на главной диагонали описанных матриц, которые в настоящей работе не рассмат­риваются.
В докладе будут подробно рассмотрены примеры распараллелива­ния конкретных задач с помощью описанного программного комплекса.
Благодарности
Работа выполнена при поддержке российско-американской про­граммы «Фундаментальные исследования и высшее образование» и РФФИ (грант № 03-01-00109).
Литература
1. Барский А.Б. Параллельные процессы в вычислительных системах //
Москва: Радио и связь, 1990.
2. Тоффоли Т., Марголус Н. Машины клеточных автоматов // М.:
Мир,1991.
Воеводин В.В., Воеводин Вл.В. Параллельные вычисления // СПб.: БХВ-Петербург, 2002.
Фурсов В.А., Шустов В.А., Скуратов С.А. Технология итерационного планирования распределения ресурсов гетерогенного кластера // Труды Все­российской научной конференции.


MPI: СТАНДАРТ И РЕАЛИЗАЦИОННАЯ ПРАКТИКА
А ЙЙ Й
А. Коновалов , А. Курылёв , А. Петушин
*ЗАО «Интел АО», Нижегородский Государственный Университет им. Лобачевского,
г. Нижний Новгород
Версия 1.0 стандарта MPI была принята в 1994-м году. Это был значительный шаг от «ни с чем не совместимых, и никуда не переноси­мых» коммуникационных интерфейсов первого поколения масс-параллельных суперЭВМ. За прошедшие 10 лет стандарт стал «средст­вом по умолчанию» индустрии высокопроизводительных вычислений: по-видимому, продать параллельную машину с неработающим MPI не­возможно, и, с другой стороны, пользователь, MPI не использующий, обычно объясняет, почему он выбрал другое средство распараллелива­ния. Большой опыт, накопленный как в прикладном программировании, так и в реализации MPI, позволяет указать некоторые нетривиальные пункты, где намерения разработчиков стандарта разошлись с реально­стью. Необходимо отметить, что зачастую это не ошибки проектирова­ния, а проявляющиеся таким неожиданным образом ограничения со­временных вычислительных архитектур.
Совмещение счёта и обменов
Прикладной программист может бороться с высокими коммуни­кационными задержками на нескольких уровнях. Самое замечательное, если к задержкам нечувствителен алгоритм, например, число операций на один обмен достаточно велико. Общеизвестно, что совмещение счёта и обменов - стандартный «технический» способ создания параллельных задач, терпимых к высоким коммуникационным задержкам. Однако реализационная реальность существенно расходится здесь с лозунгом «совмещайте счёт и обмены - и ваши каналы станут бесконечно быст­рыми». Как легко увидеть, 3 популярные свободные реализации MPI (MPICH, MPICH-2 и LAM) устроены одинаково и совсем не так. А именно, для достаточно больших сообщений применяется так называе­мый механизм progress engine, когда фоновые обмены происходят в ре­зультате синхронных вызовов процедур доставки. Таким образом, если счётная часть программы не вызывает функций MPI вовсе, никакого со­вмещения счёта и обменов не произойдёт.
В работе [Лацис] проблему предлагается решать за счёт введения специальной нити, выделенной для обеспечения коммуникаций. По на­шему мнению, окончательное решение этой проблемы возможно лишь если будет задействован интеллектуальный потенциал устройств ввода-вывода, ведь зачастую даже гигабитная EtherNet карточка может ис­пользоваться как универсальный процессор [EMP]. Значительным ша­гом здесь представляется стандартизация интерфейсов таких устройств (см. http://www.datcollaborative.org/). К сожалению, положенная проек­тировщиками в основу метафора удалённой очереди уже сейчас демон­стрирует свою ограниченность при реализации таких важных операций, как широковещание или редукция.
Ещё одной иллюстраций неоднозначности положения с совмеще­нием счёта и обменов является область коллективных операций. Как из­вестно, коллективные операции в стандарте MPI-1 - только блокирую­щие. MPI-2 попытался снять это искусственное ограничение за счёт введения «обобщённых запросов», что, по мысли авторов, позволяет реализовать такие операции на пользовательском уровне. Легко видеть, однако, что для случая, например, аппаратуры, поддерживающей широ­ковещание, никакого решения проблемы не произошло.
Параллельный ввод-вывод
Практика показывает, что существуют 3 группы задач, для кото­рых значим высокопроизводительный ввод-вывод:
задачи, создающие контрольные точки для счёта с продолжением,
задачи, которым требуется большой объём временной памяти,
источники больших объёмов данных для дальнейшей визуализации.
Понятно, что, особенно для 1 и 3, препятствием для совмещения записи и счёта будет только наличие свободных буферов, т.е. условия близки к идеальным. Неплохо смотрится здесь и MPI-2 - в отличие от, например, односторонних коммуникаций, работающая реализация стан­дарта (ROMIO) появилась одновременно со стандартом. К сожалению, ситуация в области совмещения счёта и обменов вновь нерадостная. А именно, ставшая стандартом в мире свободного ПО ROMIO, никакого совмещения счёта и обменов не представляет, совершенно синхронно и API популярной параллельной файловой системы PVFS. Здесь необхо­димо добавить, что развитие ROMIO фактически заморожено.
Управление процессами
Важным новшеством MPI-2 стала возможность динамического порождения процессов. Реализации этой возможности, по крайней мере, свободные, пока ещё не достигли уровня, когда их стоит критиковать. Но, на наш взгляд, важная проблема содержится в самом стандарте. И действительно, если обмен данными - внутреннее дело, в основном, па­раллельной задачи, то управление процессами требует существенного участия операционного окружения. Понятно, что его стандартизация -не дело MPI, но унифицированный язык запросов оказался бы очень кстати. Многообещающей в этом контексте выглядит работа [Gropp] по интерфейсам менеджеров процессов.
На эту же проблему можно посмотреть и с другой стороны, если обратиться к вопросам безопасности. В самом деле, любая развитая сис­тема коллективного использования суперЭВМ должна исчерпывающе решать эти вопросы. Нет никакого сомнения, что соответствующие компоненты реализаций MPI-2 нуждаются в серьёзной доработке в этой области. Но даже после такой доработки останется проблема универ­сальности, ведь система прохождения задач должна обеспечивать рабо­ту не только конкретной реализации MPI-2.
Тестирование асинхронных реализаций
Известно, что полноценный стандарт образует не только собст­венно текст стандарта, немаловажную часть составляет базовая реали­зация (reference implementation) и общедоступные наборы тестов, кото­рым доверяет соответствующее профессиональное сообщество. К сожа­лению, анализ доступных для MPI тестовых наборов (см., например, http ://www-unix.mcs. anl. gov/ mpi/mpi-te st/ tsuite. html) показывает, что именно в области тестирования корректности фоновых операций прове­ряется лишь малая часть проблемных мест. В то же время, ошибки тако­го сорта являются крайне коварными, т.к. проявляются на крупномас­штабных реальных задачах. Стандарт MPI известен своим большим объёмом, поэтому ручная реализация необходимых проверочных средств не выглядит привлекательной. Суть системного программиро­вания - в ориентации на создание средств решения проблем, а не на не­посредственное их решение; в данном случае это означает, что сущест­вует потребность в программном средстве, обеспечивающем автомати­ческую генерацию требуемых тестов. Это - также одно из направлений, где приложение сил оказывается востребованным.
Литература
Лацис Как построить и использовать суперкомпьютер // М.: изд-во Бестселлер, 2003. - 274 с.
Butler, Gropp, Lusk Components and Interfaces of a Process Management System for Parallel Programs // Workshop on Clusters and Computational Grids for Scientific Computing, Sept. 24-27, 2000, Le Chateau de Faverges de la Tour, France.
3. Shivam, Wyckoff, Panda EMP: Zero-Copy OS-Bypass NIC-Driven Gigabit Ethernet Message Passing // Proc. of the ACM/IEEE SC2001 Conference (SC'01), Nov. 10-16, 2001, Denver, Colorado.


УПРАВЛЕНИЕ КОНФИГУРАЦИЯМИ И ЗАГРУЗКОЙ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Д.В. Котляров
МЭИ(ТУ), г. Москва Введение
Как показано в [1] следующие две задачи имеют принципиальное значение при построении эффективных стратегий управления парал­лельными процессами на вычислительных системах (ВС): задача управ­ления конфигурацией ВС и задача управления загрузкой ВС.
Описывается подход к решению этих задач, и разрабатываемые для этой цели программные средства, которые являются составной ча­стью проекта «Разработка системы граф - схемного потокового парал­лельного программирования для кластерных ВС», реализуемого на ка­федре прикладной математики МЭИ (научный руководитель проф. В.П. Кутепов) [2, 3].
Управление конфигурацией ВС
Определим конфигурацию в узком смысле как структуру ВС, от­ражающую имеющие самостоятельное значение элементы ВС (компью­теры, каналы связи, организация памяти и т.п.) и связи между ними.
Будем структуру ВС обозначать S(t), где переменная t - момент времени, в который структура имеет место.
Конфигурация в широком смысле это пара:
K(t)=<Y(t), S(t)>,
где S(t) - структура ВС или конфигурация в узком смысле, a Y(t) - схема управления, которая реализуется в S(t) в момент времени t.
Управление конфигурациями - это функция F, осуществляющая отображение множества возможных (допустимых для рассматриваемых структур) схем управления Yb множество возможных структур S ВС:
F: Y-> S.
Рассмотрим множество допустимых (возможных) структур S. S может включать только структуры полученные добавлением или удале­нием одного или нескольких компьютеров, при сохранении общей орга­низации ВС, в частности её коммуникаций (обычно подобные изменения связывают с понятием масштабирование). При более общих допущениях структурные изменения могут включать не только количественные изме­нения компьютеров в ВС, но и коммуникационных узлов, коммуникаци­онных связей, блоков памяти и её организационной структуры и т.д.
Множество схем управления Y может включать помимо традици­онных моделей управления - централизованных, децентрализованных, иерархических и другие модели, например, основанные на многоагент-ной парадигме построения управления. Выбор той или иной схемы управления зависит от класса рассматриваемых наВС задач и критериев оценки эффективности работы ВС.
Управление конфигурированием ставится как задача нахождения такой функции K, которая обеспечивает максимальный эффект при вы­полнении заданного класса задач на ВС (например, времени выполне­ния задач этого класса, использования ресурсов ВС, возможно, и того и другого, также, возможно, ещё других дополнительных критериев).
В практическом плане решение этой задачи предполагает разра­ботку соответствующих алгоритмов и программных средств, которые позволят учитывать изменения, естественно возникающие в процессе функционирования ВС из-за неизбежных отказов и восстановлений или, в более общем случае, из-за необходимости динамического управления загруженностью ВС в процессе решения задачи (в частности, их парал­лельной работы). Так что алгоритмы управления конфигурациями в оп­ределённые моменты времени варьируют и структуру системы, и схему управления вычислительными процессами в ней.
В рамках выполняемого проекта разработаны программные сред­ства, которые позволяют динамически управлять конфигурацией кластерных ВС [4].
В реализации эти программные средства представляют собой в определённом смысле надстройку имеющимися стандартными средст­вами ОС (в частности, сетевых ОС), предназначенными для этой цели.
В них разработанные программные средства взаимодействуют, с од­ной стороны, с блоками управления загрузкой кластера и блоком отказо­устойчивости [1, 2]. С другой стороны, они «реагируют» на все события, обнаруживаемые средствами ОС (отказы и восстановления), в том числе, той её части, которая ответственна за администрирование кластера.
Программные средства позволяют визуализировать процессы из­менения конфигурации кластера, что важно с позиции «человеческого» вмешательства в этот процесс.
Управление загрузкой кластера
Одной из целевых функций, определяющих эффективность рабо­ты ВС, является достижение равномерной загрузки ее компонентов, в частности компьютеров.
Для решения этой задачи в системе управления кластерными ВС [1, 2, 3] предусмотрен программный блок, который по данным, измеряе­мым компьютерами ВС, и данным об их загруженности пытается пере­распределить выполняемые процессы таким образом, чтобы достичь ее равномерного распределения.
Три проблемы возникают при этом:
как измерять и какие параметры загруженности компьютеров;
каким образом определять необходимость перемещения процессов между компьютерами или, иначе, какие компьютеры считать пере­груженными, а какие недогруженными;
какие процессы стоит перемещать между компьютерами, если в этом возникает необходимость.
Третья проблема требует тонкого учета «поведения» процессов, использования ими ресурсов компьютера. Эту проблему решает плани­ровщик во взаимодействии с блоком выполнения - интерпретатором па­раллельных программ [2].
Остановимся на рассмотрении первых двух проблем. Начнем с па­раметров, по которым можно достаточно объективно судить о загру­женности компьютера. Наиболее важными из них являются:
количество процессов,
объем свободной памяти,
интенсивность обменов между дисковой и оперативной памятью,
интенсивность обмена данными с другими компьютерами. Второй и третий параметры взаимосвязаны, по ним можно судить
(особенно по третьему параметру) о непроизводительном времени, ко­торое процессор компьютера тратит на обмен между оперативной и дисковой памятью (напомним, что среднее обращение к дисковой памя­ти в современных компьютерах при страничном обмене равно 1,5 мс -среднему времени полуоборота дискового носителя).
В то же время измерение свободной памяти компьютера реализу­ется гораздо проще и требует гораздо меньших накладных расходов по сравнению с измерением интенсивности обменов между уровнями па­мяти. Известно, что в ранних компьютерах со страничной памятью за­дача управления страничным обменом была центральной.
Интенсивность обмена между компьютерами позволяет судить о загруженности каналов сетевого обмена ВС и косвенно показывают на­сколько часто взаимодействуют процессы, размещённые на различных компьютерах.
Параметр - количество процессов на компьютере полезен, когда решается вопрос о простаивающих компонентах ВС и возможности пе­ремещения части процессов. Хотя он менее информативен с позиций

регулирования загрузки по сравнению с другими перечисленными па­раметрами.
Заметим, что в ОС (например, Windows) есть специальные про­граммные средства для измерения указанных параметров.
Для оценки своей загруженности локальное управление компью­тером строит некоторый функционал (интегральную оценку, используя , например, линейный функционал, в котором параметры загруженности взвешены подобранными коэффициентами их важности). Одновремен­но вычисляется загруженность компьютера по памяти и по обмену с другими компьютерами, применяя нечёткую шкалу: недогружен, нор­мально загружен, перегружен.
На основе этих данных о загруженности компьютеров ВС управ­ление загрузкой кластера пытается её сделать равномерной, сравнивая по достаточно сложной системе эвристических правил степень загру­женности подчиненных компьютеров.
Схема на рис. 1 иллюстрирует эту модель управления загрузкой кластера и представляет самостоятельный блок в реализации управле­ния, предназначенного для эффективного выполнения граф - схемных потоковых параллельных программ на кластерах [1].





Сервер управления загрузкой и конфигурациями кластера получа­ет от каждого i-ro компьютера оценку его интегральной загруженности С/ (t) в момент времени t и её прогноз Cf (t + At1) в следующий момент времени t + At1, вычисляемый функцией P по изменению загрузки ком­пьютера на интервале [t - At11, t]: Cf (t + At1) = P(CI1 (x)|t - At11 < x < t).
По этим данным, которые сервер периодически получает от ком­пьютеров кластера, определяется средняя загрузка S(t) и девиация s (t), которая часто позволяет достаточно точно судить степени разброса в за­груженности компьютеров. В принципе сервер, также как и компьюте­ры, по их прогнозу о загруженности пытается предсказать изменения в загрузке кластера с тем, чтобы более точно управлять ею. Сервер выра­батывает для управления загрузкой и конфигурацией кластера управ­ляющие воздействия, которыми являются две функции: G1 (t) и Gu (t), первая из которых определяет текущую конфигурацию кластера, a G11 (t) -распределение процессов по его компьютерам.
Отметим, что в реализации сервера параметры, по которым ком­пьютер определяет свою загрузку, также передаются серверу для того, чтобы администратор имел возможность их контролировать. Для упро­щения контроля эти данные представлены в табличной форме с исполь­зованием стандартных средств визуализации ОС.
Заключение
В настоящее время завершены работы по разработке указанных программных средств управления конфигурациями и загрузкой класте­ра и начата их апробация на практике в рамках указанного во введении проекта.
Работа выполнена при поддержке РФФИ, проект 03-01-00588
Литература
Кутепов В.П. Об интеллектуальных компьютерах и больших компью­терных системах нового поколения // М: Теория и системы управления, 1996. №5.
Кутепов В.П., Котляров Д. В., Лазуткин В.А., Осипов М.А. Граф-схемное потоковое параллельное программирование и его реализация на кла­стерных системах // М: Программирование, 2004.
Кутепов В.П. Методы и инструментальные средства построения управленияраспределёнными системами. М.: 2004.
Котляров Д.В. Разработка программных средств контроля загрузки и управления конфигурациями кластерных систем // М.: 2004.
ИНТЕРПРЕТАЦИЯ ФУНКЦИОНАЛЬНО-ПАРАЛЛЕЛЬНЫХ ПРОГРАММ С ИСПОЛЬЗОВАНИЕМ КЛАСТЕРНЫХ СИСТЕМ
Д.А. Кузьмин, А.И. Леталов
Государственный техническийуниверситет, г. Красноярск
Введение
В работах [1, 2] предложен язык программирования «Пифагор», реализующий поддержку функциональной модели вычислений с управ­лением по готовности данных, обрабатываемых в бесконечных, дина­мически выделяемых ресурсах [3]. Для выполнения подобных программ на реально существующих параллельных вычислительных системах существует два основных подхода, каждый из которых обладает своими достоинствами и недостатками:
Преобразование функциональных параллельных программ (ФПП) в параллельные программы, соответствующие конкретной архитектуре. В этом случае возможно достижение производительности, близкой к харак­теристикам параллельной системы, если удастся обеспечить эффектив­ность процесса трансформации. Однако, для получения результата необ­ходимо тщательное исследование принципов перехода от одного вида параллелизма к другому. При этом не всегда удается получить эффек­тивные эквивалентные представления для результирующих программ и приходится заниматься динамической эмуляцией в ходе вычислений.
Непосредственная интерпретация ФПП с использованием специ­ально разработанного эмулятора. Несмотря на падение производитель­ности, такой подход допускает более простую реализацию и позволяет достаточно быстро приступить к разработке и отладке параллельных программ. Он является более удобным при решении задач исследова­тельского характера. Помимо этого потеря производительности будет невысокой, если операциями будут являться достаточно крупные про­граммные модули.
В рамках данной работы акцент сделан на разработку интерпрета­тора, обеспечивающего выполнение программ на кластерных архитек­турах. Это связано с предполагаемым первоначальным использованием языка как средства динамического управления длительными по времени вычислительными процессами. Создание интерпретатора обусловлено решением следующих задач:
исследование общих принципов построения и использования интерпретирующей среды для языка функционально-параллельного программирования «Пифагор»;
анализ методов повышения производительности в зависимости от состава и конфигурации используемой кластерной системы.
В настоящее время реализован и используется интерпретатор функционального языка, обеспечивающий последовательное выполне­ние написанных программ [4]. Однако развитие системы требует даль­нейших исследований принципов построения и использования средств, поддерживающих реальный, а не виртуальный параллелизм. Для прове­дения подобных работ имеются определенные предпосылки. В настоя­щее время широко используются кластерные системы, реализованные на основе обычных персональных компьютеров, взаимодействующих в рамках локальной вычислительной сети. Они легко создаются и мас­штабируются. Для организации кластерных систем разработаны про­граммные пакеты, функционирующие под управлением различных опе­рационных систем.
Среди существующих средств, обеспечивающих поддержку кла­стерных и распределенных вычислений можно выделить cncTeMe дина­мического распараллеливания Mosix [5], которая обеспечивает динами­ческое распределение процессов по узлам кластера. Порождение про­цессов осуществляется стандартными средствами ОС Linux, что позво­ляет запускать интерпретатор, как на кластере, так и на однопроцессор­ных системах, не использующих данный пакет. Помимо этого Mosix обеспечивает поддержку статического управления, что, при необходи­мости, позволяет явно накладывать ограничения на модель вычислений с целью достижения максимальной эффективности конкретной кластер­ной архитектуры.
Организация процесса интерпретации
Язык «Пифагор» позволяет описывать параллелизм задачи на уровне элементарных операций. Базовой операцией языка, является операция интерпретации, объединяющая функцию и обрабатываемые данные в единый операционный пакет, исполнение которого начинается по готовности того и другого. В идеальной ресурсно-независимой сис­теме каждый такой пакет выполняется на собственном вычислителе. Ре­альное выполнение под управлением ОС Linux, с поддержкой динами­ческого распараллеливания посредством Mosix осуществляется модели­рованием идеальных условий посредством использования механизма порождения процессов.
Отсутствие в современных архитектурах эффективной аппаратной поддержки параллельных вычислений на уровне элементарных опера­ций определяет иерархическое построения интерпретатора функцио­нальных программ. Таким образом, архитектура виртуальной машины, должна иметь многоуровневую структуру в рамках которой:
- низкоуровневые операции выполняются последовательно;
крупные информационные единицы выполняются параллельно на уровне отдельных процессов, а в общем случае, на уровне потоков и процессов (реализация крупноблочного распараллеливания);
возможно последовательное выполнение независимых процес­сов при наличии ресурсных ограничений.
Выполнение ФП программ осуществляется на множестве вирту­альных машин, каждая из которых выполняет собственную функцию.
Использование процессов для параллельного выполнения функ­ций требует решения ряда задач, связанных с передачей данных и полу­чением результатов. Проблема заключается в том, что функция и дан­ные, определяющие операционный пакет становятся известными только перед запуском операции интерпретации. Необходимо решить задачи, связанные с передачей составляющих операционного пакета от роди­тельского процесса дочернему, динамически порождаемому во время вычислений. Вариант, связанный с пересылкой функций и обрабаты­ваемых данных в моменты их формирования, особенно при рекурсив­ных вызовах, ведет к дополнительным временным задержкам. Альтер­нативой является явная передача процессу всех функций до начала его выполнения. Это решение может быть непосредственно поддержано моделью управления процессами ОС Linux. Каждый процесс наследует окружение процесса-родителя.
Наряду с проблемой передачей данных в интерпретируемый про­цесс, необходимо определиться с механизмами их доставки от потомков к родителям, обеспечивающими сборку результатов. В Linux системах имеются различные средства взаимодействия между процессами, кото­рые поддерживаются Mosix. Сборка результатов вычислений осуществ­ляется с использованием любого из них. Наиболее удобным представля­ется использование очередей, обладающих развитыми средствами син­хронизации, на уровне операционной системы. Поимо этого, данные в очереди типизированы, что позволяет родительскому процессу иденти­фицировать: от кого из потомков они получены. Для предотвращения конфликта по доступу к общему ресурсу можно использовать семафоры.
Наличие ресурсных ограничений ведет к необходимости введения дополнительного управления, обеспечивающего видимость бесконечных виртуальных ресурсов. Это управление подчиняется определенному набо­ру следующих правил:
интерпретация начинается в момент создания конкретного про­цесса;
интерпретирующий процесс может порождать новые процессы-потомки, неявно передавая им параметры, через механизм наследова­ния, поддерживаемый на уровне операционной системы;
процесс-потомок может порождать другие процессы интерпре­тации, тогда для передачи родителю результата вычислений, ему необ­ходимо дождаться результатов от своих потомков;
если процесс-потомок, при попытке выполнить следующую опе­рацию интерпретации получает отказ, то выполнение функциональной программы продолжается в текущем процессе;
если некоторый процесс-потомок начал передачу данных роди­тельскому процессу, то ни один из потомков последнего не может на­чать передачу данных, до окончания передачи данных этим процессом.
Реализация интерпретатора
Интерпретатор реализован в виде исполняемого файла, запускае­мого из командной строки, в которой передаются все необходимые па­раметры:
Файл на языке XML с промежуточным представлением, создан­ный транслятором.
Имя функции, запускаемой на интерпретацию.
Параметры, определяющие уровень параллелизма.
Процесс интерпретации начинается с разбора xml-файла и созда­ния объектного представления. В ходе выполнения для каждой опера­ции интерпретации происходит анализ данных и функций на наличии параллельного списка. Если аргумент или функция являются таковыми, то управление передается модулю интерпретации, который принимает решение о параллельном запуске.
Интерпретация функциональной программы начинается с порож­дения необходимого количества процессов. В каждом из процессов за­пускается интерпретатор со своим аргументом (или функцией) из парал­лельного списка. Процессы получают сегмент данных от родительского процесса. Поэтому отпадает необходимость явной передачи функцио­нальной программы порожденному процессу при отсутствии внутренних вычислений. Родительский процесс «засыпает» в ожидании результатов. Каждый дочерний процесс обрабатывает свою часть и передает результат родительскому процессу, после чего завершает свою работу. Для обмена результатами между родительским и дочерними процессами использует­ся модуль сборки результатов. После получения всех необходимых ре­зультатов родительский процесс продолжает свою работу.
Повышение эффективности работы интерпретатора
Поддержка интерпретатором модели с бесконечными ресурсами на уровне элементарных операций обеспечила выполнение функцио­нальных программ и позволила выявить узкие места, связанные с ре­сурсными ограничениями исполнительной среды (фиксированным чис­лом порождаемых процессов, очередей сообщений, семафоров и др.). Это, в свою очередь, помогло осуществить тестирование и отладку ин­терпретатора, а также улучшить алгоритмы функционирования, что по­высило эффективность и надежность системы в целом.
Вместе с тем, рассмотренная реализация не обеспечивает эффек­тивное выполнение функциональных программ. Это также связанно с тем, что время создания параллельного процесса для элементарных опе­раций много больше времени ее обычного последовательного выполне­ния. Для повышения эффективности необходимо обеспечить автомати­ческое ограничение числа процессов, связав их не с количеством опера­ций, а с особенностями архитектуры ПВС.
Отсутствие дополнительных ограничений обеспечивает паралле­лизм на уровне, определяемым языком, который включает параллельное выполнение всех элементарных операций (арифметических, операций сравнения и др.). Если выбирается этот вариант распараллеливания, то процессы будут создаваться для каждой из элементарных операций. Возможны следующие варианты дополнительных ограничений:
Использование распараллеливания только на уровне независимых данных, являющихся аргументами операций интерпретации. Они долж­ны быть параллельными списками. Функция, осуществляющая обработ­ку этих данных, не должна быть элементарной.
Распараллеливание проводится только на уровне функций посту­пающих на функциональные входы операций интерпретации. Они долж­ны быть представлены в виде параллельных списков, и не являться эле­ментарными операциями.
Еще одним фактором, влияющим на выполнение функциональных программ, является глубина распараллеливания рекурсивных функций. Параллельная рекурсия будет эффективна в том случае, если число про­цессов, порожденных в ходе интерпретации, не будут превышать количе­ства узлов кластера, а время выполнения каждого из этих процессов будет больше времени миграции порожденного процесса на свободный узел кластера. Параметр, ограничивающий глубину распараллеливания, может накладывать дополнительные ограничения на уровень распараллеливания.
Ввод параметров, ограничивающих распараллеливание и глубину параллельного выполнения рекурсивных функций до определенного уровня, позволяет настраивать интерпретатор на требуемый режим ра­боты. Это обеспечивает более эффективное выполнение функциональ­ных параллельных программ.
Заключение
Разработка интерпретатора обеспечила практическую поддержку экспериментов, связанных с исследованием параллельного выполнения функциональных программ, написанных на языке «Пифагор». Прове­денные эксперименты показывают, что даже при простых алгоритмах динамического распределения ресурсов использование кластерных сис­тем позволяет повысить производительность вычислений. Вместе с тем, полученные данные позволяют определить направления дальнейших работ по повышению эффективности интерпретатора, улучшению транслятора и модификации языка программирования. Работа выполне­на при поддержке РФФИ № 02-07-90135.
Литература
Kuzmin D.A., Kazakov F.A., Legalov A.I. Description of parallel-functional programming language // Advances in Modeling & Analysis, A, AMSE Press, 1995. Vol.28. №3. P. 1-17.
Легалов А.И., Кузьмин Д.А., Казаков Ф.А., Привалихин Д.В. На пути к переносимым параллельным программам // Открытые системы, 2003. № 5 (май). С. 36-42.
Легалов А.И., Казаков Ф.А., Кузьмин Д.А. Водяхо А.И. Модель парал­лельных вычислений функционального языка // Известия ГЭТУ. Вып. 500. Структуры и математическое обеспечение специализированных средств. С.­Петербург, 1996. С. 56-63.
Легалов А.И. Инструментальная поддержка процесса разработки эво-люционно расширяемых параллельных программ // Проблемы информатиза­ции региона. ПИР-2003/ Материалы 8-й Всероссийской научно-практической конференции. Красноярск, 2003. С. 132-136.
Barak A., La'adan O. The MOSIX Multicomputer Operating System for High Performance Cluster Computing // Journal of Future Generation Computer System, 1998. №13.


РАСПАРАЛЛЕЛИВАНИЕ В КЛАСТЕРЕ ПОЛУЭМПИРИЧЕСКИХКВАНТОВО-ХИМИЧЕСКИХ МЕТОДОВ ПРИ ПРЯМОМ ВЫЧИСЛЕНИИ МАТРИЦЫ ПЛОТНОСТИ ДЛЯ БОЛЬШИХ МОЛЕКУЛЯРНЫХ СИСТЕМ

М.Б. Кузьминский, В.В. Бобриков, A.M. Чернецов, О.Ю. Шамаева
Институт органической химии РАН, г. Москва Московский энергетический институт, г. Москва
Введение
Задачей работы было распараллеливание в кластере программы прямого построения матрицы плотности для полуэмпирических расче­тов больших молекул методами нулевого дифференциального перекры­вания (НДП). Актуальность работы определяется потребностями в тео­ретическом исследовании электронной структуры больших молекуляр­ных систем, в т.ч. биомолекул (включая протеины и ДНК) и нанострук­тур. Практическое значение таких исследований связано, в частности, с задачами конструирования лекарств.
Применение неэмпирических методов расчета даже для неболь­ших протеинов сегодня практически нереально. Например, расчет моле­кулы цитохром-С, содержащей 1738 атомов, по программе, специализи­рованной для расчетов больших молекул, методом DFT в гетерогенном кластере с использованием 15 микропроцессоров Alpha 21x64, требует около суток на итерацию и свыше месяца - на весь расчет без оптими­зации геометрии [1].
Не только строгие неэмпирические методы, но и даже более про­стые полуэмпирические методы при расчете сверхбольших молекул требуют неприемлемо высоких затрат вычислительных ресурсов. Для методов НДП время расчета растет как N, где N-размерность базиса, пропорциональная размеру молекулы. Это обусловлено необходимо­стью решения симметричной проблемы на собственные значения с на­хождением всех собственных векторов, из которых затем строится мат­рица плотности.
Распараллеливание расчета матрицы плотности
В работе в рамках полуэмпирической схемы AM/1 использован альтернативный диагонализации численный метод прямого вычисления матрицы плотности с применением полиномов Чебышева [2]. При ис­пользовании технологии разреженных матриц этот метод обеспечивает линейное масштабирование времени расчета с ростом N. До настоящего времени распараллеленных программ, реализующих данный метод, в мире не имелось.
Авторами создана распараллеленная версия экспериментальной программы на языке Фортран-95, реализующей данный метод, с исполь­зованием средств MPI. При оценке минимального и максимального соб­ственных значений использован метод Гершгорина. Для нахождения корня нелинейного уравнения, определяющего химический потенциал, применен метод Ньютона, а для расчета коэффициентов разложения мат­рицы плотности по полиномам Чебышева - подпрограмма dfcost из сво­бодно доступной библиотеки FFTPACK [3], реализующая дискретное преобразование Фурье. Для умножения матриц (в первой версии про­граммы технология разреженных матриц не использована) применяется BLAS-подпрограмма dgemm из библиотеки Atlas-3.6.0, также свободно доступной. Выбор данных программных средств обусловлен потребно­стями в разработке мультиплатформенных программных средств с от­крытым кодом.
Созданные программные средства работают в среде операцион­ных систем Windows и Linux для х86 (использованы компиляторы Com­paq Visual Fortran-6.1 и Intel ifc-7.1, соответственно). Однако тестирова­ние было осуществлено в Linux-кластере на базе Myrinet 2000 и SMP-узлов, использующих процессоры Xeon/2.6 ГГц и материнские платы с набором микросхем iE7500 c оперативной памятью DDR266.
Для профилирования при измерениях процессорного времени выполнения применялся высокоточный таймер на основе счетчика RDTSC [4]. Найдено, что лимитирующей стадией расчетов является вычисление матричных полиномов Чебышева. Матрица плотности целиком хранится в памяти узлов, поскольку исходная полуэмпири­ческая программа не предполагает распределенного хранения. В про­грамме реализовано поблочное умножение матриц, так что каждый процесс рассчитывает только свой блок, а затем осуществляется об­мен рассчитанными блоками.
Результаты работы программы иллюстрирует пример молекулы полипептида, содержащей около 1800 атомов (N=4500), см. рис. 1. Дос­тигнутое нами ускорение расчета матрицы плотности (без построения фокиана) по сравнению с последовательной программой составляет при 3 процессорах 2,3 раза, при 6 процессорах - 4,1 раза.
5
У
с
Е
? 4 Р
Е
Н
И 3
е

2
Оценка предельного ускорения по закону Амдала при бесконеч­ном числе процессоров близка к 11 (9% последовательных кодов).
Для сравнения, в лучшей на сегодня коммерческой полуэмпириче­ской программе MOPAC2002, использующей другую линейно масшта­бируемую с ростом N численную схему на основе локализованных ор-биталей, на многопроцессорном сервере SGI Origin 300 с процессорами R14000/500 МГц для молекулы C960y с близким размером базиса

(N=3840) оценки достигнутого ускорения близки к полученным нами. Они составляют 2,5 и 4,1 для 3 и 6 процессоров соответственно [5]. При этом процессоры в Origin 300 медленнее, чем используемые нами, а межсоединение узлов - наоборот, существенно быстрее, что повышает достигаемое в MOPAC2002 ускорение.
Приведенные результаты относятся к запуску на SMP-узлах кла­стера по 1 процессу. При запуске по 2 процесса на узел время расчета существенно возрастает, что связано, вероятно, с ограничениями пропу­скной способности системной шины и конфликтами процессоров по доступу в оперативную память.
Нами были протестированы также схемы обмена данными с ис­пользованием широковещательных рассылок, вместо применявшихся в указанных выше расчетах MPISEND/MPIRECEIVE. Несмотря на до­вольно эффективную реализацию, MPIBCAST в использованной в ра­боте MPICH-GM v.1.2.4-8, суммарное время обменов в этом случае воз­растает на 30% (для 6 процессоров).
Использованная схема распараллеливания отвечает крупнозерни­стому параллелизму, поэтому от межсоединения узлов кластера требу­ется в первую очередь высокая пропускная способность. Достигнутая нами в MPISEND/MPIRECEIVE пропускная способность при переда­че блоков матрицы составила около 210 Мбайт/с, что уже достаточно близко к пиковой величине 250 Мбайт/с.
Литература
Sato F., Yoshihiro Т., Era M., Kashiwagi H. Chem. Phys. Letters, 2001. V. 341. P. 645.
Goedecker S., Colombo L. Phys. Rev. Letters // 1994. V. 73. P. 722.
http://netlib.org/fftpack
Кузьминский M.E., Мендкович A.C., Аникин H.A., Чернецов A.M. «Пути модернизации программных и аппаратных кластерных ресурсов для задач вычислительной химии» // Высокопроизводительные параллельные вычисле­ния на кластерных системах. Материалы второго международного научно-практического семинара. Изд-во Нижегородского госуниверситета, Н. Новго­род, 2002. С. 169.
SGI Computational Chemistry Applications Performance Report. Spring 2002, Silicon Graphics, Inc., 2002.

ФУНКЦИОНАЛЬНОЕ ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ: ЯЗЫК, ЕГО РЕАЛИЗАЦИЯ И ИНСТРУМЕНТАЛЬНАЯ СРЕДА РАЗРАБОТКИ ПРОГРАММ

В.П. Кутепов, СЕ. Бажанов
Энергетический Институт (ТУ), г. Москва
Введение
Доклад посвящен описанию реализуемого на кафедре прикладной математики МЭИ проекту создания системы функционального парал­лельного программирования для кластерных систем [1, 2].
Проект содержит три независимые части: высокоуровневый язык композиционного функционального параллельного программирования, инструментальные средства программирования на нем и систему управ­ления процессом параллельного выполнения функциональных программ на кластерных системах.
1. Язык FPTL
Язык FPTL (Functional Parallel Typified Language) - это язык функционального композиционного параллельного программирования [1]. Его отличительными особенностями являются:
композиционный стиль программирования, в основе которого лежит универсальный набор операций композиции функций и их определе­ние через системы функциональных уравнений;
схемный характер задания функций, структурированность определений;
возможность определения различных типов данных, строгая типиза­ция и статический контроль типов;
полиязычность, заключающаяся в возможности использования в нем функций, определяемых на других языках программирования;
асинхронная вычислительная семантика, основанная на формальной мо­дели свертывания и развертывания деревьев - состояний вычислитель­ного процесса, индуцируемого при применении функции к аргументам.
Теоретическую базу языка FPTL составляют исследования по функциональной схемотологии и функциональным системам [3], кото­рые обобщены в теории направленных отношений, объединяющей функциональный и логический стили программирования [4, 5].
Основными семантическими объектами, представляемыми в язы­ке, являются данные, функции, функционалы и реляционалы - парамет­ризованные функции и типы данных соответственно.
Функции в FPTL, следуя [1, 3], рассматриваются как типизиро­ванные соответствия между множествами (данными). В общем случае, в

Работа выполнена при поддержке РФФИ, проект 03-01-00588 качестве аргументов и значений функций в языке FPTL выступают кор­тежи произвольной длины m>0, элементами которых могут быть син­таксически определенные объекты различной структуры.
Данные и функции в языке FPTL определяются в общем случае посредством системы реляционных или функциональных уравнений [1], которые трактуются как операторы «взятия» минимальной фиксирован­ной точки или минимального решения (для соответствующих интерпре­таций) для этих систем реляционных и функциональных уравнений.
В языке FPTL для построения функций используются следующие четыре простые операции композиции (интерпретация операции компо­зиции задается как график функции, определяемой через эту операцию):
операция последовательной композиции •
f (m,n) =f(m,k) ^k,n) @ {( ^ )|3y (( ^ ) e f (m,k) л( ^ ) e f2k,n;
операция конкатенации *
f(m,n) =f1(m,n1) * f2m,n2) @ {(а^р1р2 )| (ад) e m,n1) л(аД ) e f2m,n2)} ;
операция условной композиции ®
f(m,n) =f1(m,k) ® f2m,n) @ {()|() e f2m,n) л 3y ((aj) e f1(m,k))} ;
операция объединения графиков ортогональных функций ©
f(m,n)=f1( m,n) © f2m,n) @ {(a>p )|( a?p) e f1( m,n) v (a>p) e f2( m,n)}.
Запись fm n) означает, что функция f имеет арность (m, n), m>0, n>0, m и n - длина кортежей входных и выходных значений функции.
Для задания рекурсивных функций используется специальный оператор минимальной фиксированной точки или минимального реше­ния определенного вида системы функциональных уравнений. Пара­метризованные функции (функционалы) определяются системой функ­циональных уравнений, содержащей свободные переменные.
В качестве примера приведем программу вычисления факториала:
Functional Program Factorial
Scheme Factorial
{
Factorial = (id*<0>).eq -> <1> + (id*<0>).ne -> (id * (id*<1>).minus.Factorial). mult;
}

Application %factorial (6)

В этом примере функция вычисления факториала определена с помощью одного функционального уравнения, содержащего только встроенные в язык функции (id - тождественная функция, eq - функция равенства и т.д.). Программа также содержит задание на вычисление функции (от аргумента 6).
1.1. Модель вычисления значений функций
Модель асинхронного вычисления значений функций определяет процесс вычисления как процесс преобразования деревьев [3]. На каждом шаге состояние вычисления представляется бинарным размеченным дере­вом особого вида. Вычисление значения функции представляется в виде последовательности состояний. Переходы из состояния в состояние опре­деляются правилами преобразования деревьев, разделенными на два под­множества: правила развертывания и правила свертывания деревьев.
Данная модель является недетерминированной, поскольку в общем случае возможно применение нескольких правил к дереву - состоянию вычислений, и поэтому в зависимости от применяемого правила будут по­лучаться различные последовательности вычислений. Также модель явля­ется параллельной, т.к. возможно одновременное применение нескольких правил к несвязным кустам дерева состояния. Источником параллелизма являются свойства операций *, ®, ©.
Важно отметить, что не всякий порядок применения правил пре­образования состояний приводит к корректному вычислению значения функции. Например, такой случай имеет место, если при вычислении значения (t1©t2)(d) сначала делается попытка вычисления значения t1(d), которое не определено и процесс вычислений продолжается бесконеч­но, а значение t2(d) определено. Таким образом, условием корректности реализации модели является параллельное (или квазипараллельное) вы­числение значений функций, соединяемых операцией ©.
Кроме этого, модель предоставляет возможность повышения эф­фективности вычислений за счет вычислений с упреждением. Если име­ется достаточное количество ресурсов, то при вычислении значения (t1®t2)(d) можно значение t1(d) вычислять одновременно с t2(d), стре­мясь максимально распараллелить процесс вычислений.
Эти особенности модели вычислений являются принципиальными при ее реализации на вычислительных системах и при разработке эф­фективных алгоритмов планирования параллельного выполнения функ­циональных программ.
2. Реализация языка FPTL
В реализации любого современного языка программирования непременно присутствуют два основных компонента: инструментальная среда, предназначенная для автоматизации процесса программирования на языке и операционные средства управления, предназначенные для эффективного управления процессом выполнения программы на соот­ветствующих вычислительных установках (компьютерах, компьютер­ных системах, кластерах и т. п.) [1].
Важными аспектами в реализации языка FPTL, отличающими ее от реализации широко известных языков программирования (Лисп, Пролог, Паскаль, Си и др.), является включение в нее ряда механизмов разработки функциональных программ и управления процессом их выполнения, в ча­стности механизмы планирования, которые позволяют существенно повы­сить эффективность этих процессов.
2.1. Инструментальная среда
Инструментальная среда состоит из двух частей. Одна часть отвеча­ет за правильность программы: синтаксический и типовой контроль, ве­рификация программы. Другая часть включает технологические средства, упрощающие процесс разработки программ: редактор программ, систему управления проектом, систему поддержки декомпозиции программ и др. Среди этих средств следует выделить средства анализа структуры про­граммы и ее вычислительной сложности и средства осуществления целе­направленных эквивалентных преобразований программ. Эти два элемен­та, а также система верификации программ основаны на теоретических ре­зультатах работ [3, 5]. Опишем их немного подробнее.
Задачей системы верификации является поиск ошибок и доказательство правильности функциональных программ. Данная задача включает в себя следующие подзадачи:
поиск противоречий в спецификациях,
доказательство тотальности и функциональности программных функций,
поиск ошибок в объекте верификации,
доказательство соответствия объекта верификации и его спецификаций.
В указанных работах предложено исчисление эквивалентности функциональных программ, что дает возможность осуществлять экви­валентные преобразования программ. Целью таких преобразований мо­жет быть улучшение некоторых качеств программы, например:
преобразование к форме с минимальным временем параллельного вычисления,
преобразование к форме без повторных вычислений значений функций,
преобразование к форме без вычислений с упреждением.
Также были предложены методы оценки вычислительной и струк­турной сложности программы. Методы оценки вычислительной слож­ности позволяют получить числовые характеристики сложности выпол­нения функциональных программ по сложностным оценкам элементар­ных функций, используемых при их написании. Методы оценки струк­турной сложности рассматривают функциональную программу с точки зрения таких понятий как рекурсивность, цикличность, взаимная рекур-сивность, вложимость. Существует также метод графического пред­ставления структурных характеристик схем функциональных программ.
2.2. Средства управления выполнением программ
Средства управления должны обеспечить эффективное выполнение функциональных программ, как на кластерных установках, так и на од­ном компьютере [1, 4]. Основой для реализации управляющих средств является модель асинхронного вычисления значений функций (см. вы­ше). Сами управляющие механизмы должны обеспечить эффективную реализацию этой модели (управление индуцируемыми при выполнении функциональных программ параллельными процессами) на кластерных установках различной конфигурации и с различным количеством компь­ютеров в них, в том числе и на отдельном компьютере.
Предполагается, что вычислительная система, на которой должны выполняться функциональные программы, строится как масштабируемая кластерная система, основным строительным блоком которой является узел кластера. Узел кластера - хорошо сбалансированная по быстродейст­вию компьютеров и пропускной способности каналов вычислительная система, в частности это может быть локальная сеть. Именно по такой схеме сегодня строятся все большие масштабируемые компьютерные сис­темы, например, наиболее интересные из них SPP, SP, ASCI WHITE и др.
Задача сервера каждого узла - определение его загрузки в процес­се выполнения функциональной программы и управление ею путем пе­ремещения процессов между узлами вычислительной системы. Эта за­дача известна как задача межузлового планирования процессов с целью достижения баланса в их загрузке. С другой стороны, эту же задачу сер­вер решает, но уже применительно к компьютерам узла, которые ему подчинены. Все компьютеры узла при выполнении функциональной программы работают независимо по одной и той же схеме, реализуя процессы свертывания и развертывания деревьев, лежащие в основе мо­дели асинхронного вычисления значений функций. При этом каждый компьютер узла имеет свой планировщик, алгоритм работы которого существенно учитывает семантику задания функциональных программ на FPTL, в частности семантику операций композиции функций.
Интерпретатор, работающий на отдельном компьютере, является базовым блоком системы управления выполнением программ. В одно­машинном варианте реализации, которая выполнена на данный момент, интерпретатор включает в себя транслятор, систему типового контроля и систему выполнения (рис. 1).
Наиболее важная часть интерпретатора - система выполнения. Система выполнения непосредственно управляет процессом выполне­ния функциональных программ и осуществляет моделирование процес­сов свертывания и развертывания деревьев.

исходный текс^ программы

Транслятор
внутреннее представление^
программы
Система типового контроля внутреннее представление программы
Система выполнения
результат выполнения
программы


Рис. 1. Основные блоки интерпретатора
Модель вычисления по своей сути является параллельной и одной из основных задач реализации интерпретатора является обеспечение кор­ректности реализации модели.
На каждом шаге выполнения программы дерево состояния вычис­ления содержит в общем случае множество кустов (или редексов), к ко­торым можно применить правила преобразования. В силу последова­тельного характера процесса выполнения программы возникает задача планирования вычислений, т.е. выбора редекса для преобразования на каждом шаге. Эта задача непосредственно связана с обеспечением кор­ректности и эффективности реализации модели.
Для решения задачи планирования вводится список редексов, ди­намически изменяемый в процессе выполнения программы. Планирова­ние вычислений сводится к выбору одного из редексов из этого списка и добавлению новых редексов, появившихся в результате преобразова­ния деревьев. Можно доказать, что организация работы с данным спи­ском по принципу FIFO обеспечивает корректность реализации модели вычислений.
Для повышения эффективности вычислений используется два подхода.
Разбиение множества всех вычислений на подмножество вычис­лений, заведомо необходимых для получения конечного результата и подмножество вычислений, необходимость результатов которых зави­сит от результатов других вычислений. Сделав вычисления из первой группы более приоритетными можно заметно повысить эффективность выполнения программы.
Второй подход основан на соображении о том, что простые вы­числения более приоритетны по отношению к сложным. Априорно можно предположить, что некоторые из преобразований деревьев явля­ются сложными. Выполняя простые преобразования без откладываний можно быстрее осуществить свертывание дерева.
Заключение
Описанная выше версия интерпретатора реализована и успешно опробована. При сравнении с интерпретаторами других языков (Haskell, SML, Lisp, Prolog) он показал на одном компьютере схожие, а в отдель­ном случае (в случае сложной рекурсивной программы) и лучшие ре­зультаты по времени.
Система управления параллельным выполнением функциональ­ных программ для кластеров и находятся в стадии отладки. Результаты предварительных экспериментов, касающиеся эффективности работы системы управления, обсуждаются в докладе [7].
Литература
Бажанов С.Е., Кутепов В.П., Шестаков Д.А. Язык функционального параллельного программирования и его реализация на кластерных системах // Теория и системы управления (в печати).
Бажанов С.Е., Кутепов В.П., Шестаков Д.А. Разработка и реализация системы функционального параллельного программирования на вычисли­тельных системах // Доклад на четвертом Международном научно-практическом семинаре «Высокопроизводительные параллельные вычисле­ния на кластерных системах».
Кутепов В.П., Фальк В.Н. Функциональные системы: теоретический и практический аспекты // Кибернетика, 1979. №1. С. 46-58.
Кутепов В.П. Об интеллектуальных компьютерах и больших компью­терных системах нового поколения // Изв. РАН. Теория и системы управле­ния, 1996. №5. С. 97-114.
Кутепов В.П., Фальк В.Н. Направленные отношения: теория и прило­жения // Изв. РАН. Техническая кибернетика, 1994. №4, 5.
Кутепов В.П., Фальк В.Н. Теориянаправленных отношений и логика // Изв. РАН. Теория и системы управления, 2000. №5.
Кутепов В.П., Шестаков Д.А. Анализ структурной сложности функ­циональных программ и его применение для планирования их параллельного выполнения на вычислительных системах // Доклад на четвертом Междуна­родном научно-практическом семинаре «Высокопроизводительные парал­лельные вычисления на кластерных системах».


ГРАФ-СХЕМНОЕ ПОТОКОВОЕ ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ И ЕГО РЕАЛИЗАЦИЯ НА КЛАСТЕРНЫХ СИСТЕМАХ

В.П. Кутепов, Д.В. Котляров
МЭИ(ТУ) Кафедра ПМ, г. Москва
Введение
В докладе обсуждается реализуемый на кафедре прикладной мате­матики проект создания системы граф - схемного потокового параллель­ного программирования для кластерных вычислительных систем [1].
Первая версия языка граф-схем, которая была создана в начале 70-х годов на волне активных исследований по параллелизму и параллель ­ным системам, задумывалась как «мягкое» развитие структурных (блочно-схемных) форм описания последовательных программ с пред­полагаемой реализацией на многомашинных и (или) многопроцессор­ных системах [1-3].
Следующие принципиального характера требования ставились при формулировке языка:
модульный принцип построения параллельной программы, при­чем с возможностью программирования модулей как многовходовых-многовыходовых процедур на последовательных языках программиро­вания;
наглядное граф-схемное описание структуры параллельной про­граммы в виде двух компонентов: граф-схемы и интерпретации, одно­значно сопоставляющей каждому модулю (блоку граф-схемы) подпро­грамму (или процедуру) на соответствующем языке программирования;
интерпретация связей между модулями как связей по данным (а не по управлению), правда, с таким ограничением, чтобы у корректных, т.е. однозначных граф-схем [4] на каждом входе модуля не накаплива­лось более одного данного (естественное наследование принципа вы­полнения любой команды или оператора последовательной программы);
экспликация параллелизма как информационной независимости различных модулей граф-схемы.
Уже первая попытка реализации такого граф-схемного модульно­го языка параллельного программирования [5] на многомашинных ком­плексах М6000/М7000 по принципу децентрализованного управления оказалась вполне успешной, особенно в сравнении с популярными в то время системами параллельных вычислений Сумма и Минимакс [6], по­зволявшими описывать параллелизм более примитивными и ограничен­ными средствами.
Затем эта же версия языка граф-схем была реализована в центра­лизованном варианте на многомашинных комплексах СМ1/СМ2, при­чем в этой реализации существенное развитие получила система ма­шинной поддержки процесса конструирования граф-схемных парал­лельных программ, их модификации и отладки.
В [3] в язык граф-схем было введено простое, но весьма важное по практическим соображениям расширение, касающееся векторного дина­мического параллелизма и возможности его компактного параметрическо­го схемного отражения.
В работе [7] был сделан радикальный шаг в развитии граф-схемного языка, состоящий в интерпретации информационных связей между модулями как буферов с FIFO (первое поступившее данное счи-тывается первым) дисциплиной их обслуживания. Как следствие, про­странственная (информационно-независимая) и основанная на времен­ном совмещении выполнения различных частей программы по принци­пу конвейера, формы параллелизма могли быть одинаково представле­ны в граф-схемной модели. Утвердившийся затем термин «потоковые вычисления» [8] объединяет эти различные формы параллелизма, а классификационное разделение принципов функционирования парал­лельных систем по типу SIMD (один поток команд и много потоков данных), MIMD (много потоков команд и много потоков данных) и др. отражает особенности реализации потоковых схем.
Эта версия граф-схемного языка интересна еще и тем, что она ба­зируется на строгом понятии асинхронной вычислительной сети и опи­сании процесса функционирования сети как композиции процессов, ин­дуцируемых конечно-автономной интерпретацией процессов выполне­ния модулей граф-схемы. Естественно, что формализм сетей Петри ока­зался наиболее подходящей моделью для формального описания про­цесса выполнения граф-схем [7].
Реализация этой версии граф-схемного языка, выполненная на многопроцессорных и многомашинных комплексах ЕС ЭВМ [9], - пер­вая профессионально выполненная разработка системы параллельного программирования для подобной универсальной организации вычисли­тельных систем на базе серийных ЭВМ. Во-первых, в этой реализации максимально использовались средства операционной системы ЕС ЭВМ для выполнения программ модулей граф-схемы, для организации меж­машинных обменов и др. Управление параллельным выполнением граф-схемных программ в этой реализации построено по строго децентрали­зованному принципу, причем предварительно граф-схема разрезается на n подсхем, где n - количество машин в системе, таким образом, чтобы после «назначения» подсхем на n ЭВМ достигался определенный ба­ланс их загрузки и загрузки каналов обмена между машинами. Подоб­ное статическое планирование параллельных вычислений, не допус­кающее динамического перераспределения работ между ЭВМ в процес­се их функционирования, является ограничительным, однако оказалось достаточно простым в реализации.
В [10] средства управления параллельным выполнением граф-схем были расширены введением специальных программ реакции на отказы и сбои в системе и управления реконфигурированием системы, это существенно повысило ее значение, особенно в сфере военных при­ложений. Вместо традиционно применяемого механизма резервирова­ния параллельная работа обеспечивала большее суммарное быстродей­ствие и одновременно способность продолжения работы, если в ней ос­тавалась работоспособной хотя бы одна ЭВМ.
Данный доклад посвящен описанию реализуемого научной груп­пой под руководством проф. В.П. Кутепова на кафедре прикладной ма­тематики МЭИ проекта создания системы граф-схемного потокового параллельного программирования для кластерных систем.
Широкие возможности, которые сегодня предоставляет вычисли­тельная техника в части организации вычислительных систем на базе стандартных аппаратных средств - персональных компьютеров и сете­вых коммуникаций актуализировали работы в области параллельных и распределенных вычислений [11]. Активно ведутся работы по созданию программных средств для эффективной организации параллельных и распределенных вычислений на кластерах. Кроме известных расширений последовательных языков программирования (High performance C и C++, mpC, DVM, параллельный ФОРТРАН, CHARM++, Mosix и др.), сегодня широко используются стандартизированные API-средства (Application Parallel Interface) и библиотеки: MPI, PVM и др. (см. сайт parallel.ru и др.).
Внимательный анализ этого уже достаточно обширного арсенала программных средств для кластеров показывает [12], что они обычно базируются на расширениях языков последовательного программирова­ния (Фортрана, C, C++ и др.), а в реализации для организации парал­лельного выполнения программ используются специальные библиотеки функций, позволяющие описывать межпроцессное (и межкомпьютер­ное) взаимодействие. При этом за программистом остается основная ра­бота не только в написании корректной и эффективной программы, но также и ее реализация (распределение процессов на компьютеры кла­стера). Из программных систем для кластеров, возможно, только в про­екте Mosix задача управления параллельными процессами рассматрива­ется как центральная, от решения которой прямо зависит эффектив­ность работы кластера [13] (см. также сайт mosix.tcs.huji.ac.il).
В нашем проекте три главных составляющих, определяющих эф­фективность параллельных вычислений на кластере: язык программи­рования, инструментальная среда разработки параллельных программ и программные средства управления параллельным выполнением про­грамм рассматриваются и реализуются комплексно.
Язык граф-схемного потокового параллельного программирования
(ЯГСПП)
ЯГСПП ориентирован на крупноблочное (модульное) потоковое программирование задач, он также может эффективно применяться для программного моделирования распределенных систем, систем массово­го обслуживания и др., информационные связи между компонентами которых структурированы и управляются потоками данных, передавае­мых по этим связям.
Язык позволяет эффективно и единообразно представлять в про­граммах три вида параллелизма:

- параллелизм информационно-независимых фрагментов;
потоковый параллелизм, обязанный своим происхождением конвейерному принципу обработки данных;
параллелизм множества данных, реализуемый в ЯГСПП через механизм тегирования, когда одна и та же программа или ее фрагмент применяются к различным данным;
Другими, важными с позиции программирования, особенностями ЯГСПП являются:
возможность визуального графического и текстового представ­лений программ;
возможность простого структурирования программы и отраже­ния декомпозиционной иерархии при ее построении путем использова­ния отношения «схема-подсхема»;
использование традиционных последовательных языков при программировании модулей.
Особенности «устройства» языка и программирование на нём де­тально обсуждается в [16].
Для программирования на ЯГСПП разработан комплекс про­граммных средств (названный инструментальной средой [16]), который предназначен для повышения эффективности их разработки.
Реализация ЯГСПП на кластерных системах
Мы исходим из того, что локальная сеть (в том числе сеть персо­нальных компьютеров) является основным «строительным блоком» или узлом вычислительной системы или кластера (рис. 1)
СЕРВЕР






К - компьютер

Рис. 1. Узел кластера
Узел кластера - хорошо сбалансированная по отношению, к быст­родействию компьютеров, их количеству и пропускной способности коммуникации вычислительная система, так что на ней можно эффект­но осуществлять реализацию параллельных вычислений в достаточно широком диапазоне вариаций степени распараллеливания программ [11] от «крупнозернистого» до «мелкозернистого» параллелизма.
Задача сервера на рис. 1, как важного логического элемента узла кластера, - обеспечение на программном уровне механизма масштаби­рования кластера, реализация интерактивных взаимодействий между узлами, управление их загрузкой и др. (см. далее). Путем введения со­ответствующей стратегии соподчинения серверов кластера можно легко построить различные схемы управления в системе: от строго централи­зованной, до иерархической, полностью децентрализованной и др.
Расширение системы достигается путем объединения кластерных узлов, как правило, через более медленные коммуникации. По сути, эта идеология построения больших масштабируемых вычислительных структур, продиктованная также техническими и технологическими со­ображениями, прослеживается в архитектуре всех самых мощных ком­пьютерных систем: SPP, Hewlett Packard и Convex [14], SP1 и SP2, ASCI WHITE IBM [15] идр.
В них в качестве узла обычно выступает 8, 16 или 32 - процессор­ная подсистема, в которой используются самые быстрые коммуникации (коммутаторы, переключательные матрицы и т.п.). Для межузловых со­единений применяются менее дорогие и скоростные коммуникации. Эта особенность в организации вычислительной системы требует, чтобы при вычислениях более частые обменные взаимодействия происходили внутри узла, так как в нем можно планировать вычисления с большей степенью распараллеливания, т.е. реализовывать мелкозернистый па­раллелизм. В то же время на межузловом уровне планирование загрузки (ее реализует сервер узла, рис. 1) должно осуществляться на более вы­соком уровне сложности частей программы, пересылаемых между уз­лами, с целью уменьшения времени, затрачиваемого на обмены [11].
Отметим также, что компьютеры узла могут быть многопроцессор­ными, иметь векторные сопроцессоры, что так же должно учитываться как на программном уровне, так и при планировании параллельных вычисле­ний на кластере.
Управление параллельными вычислениями на кластере
Собственно задача управления параллельными вычислениями фор­мулируется, как задача минимизации времени выполнения параллельной программы, и используемых при этом ресурсов (обычно количества ис­пользуемых компьютеров или процессорных элементов в вычислительной системе). Ее практическое решение осуществляется через механизмы пла­нирования и требует тонкого учета специфики задания выполняемой па­раллельной программы, степени ее распараллеливания, загруженности различных элементов вычислительной системы (компьютеров, коммуни­каций и др.), времени их безотказной работы и др. [1, 10, 11].
Эта проблема требует специального анализа, поэтому далее рас­сматриваются, в основном, организационные аспекты реализации управления параллельным выполнением ГСПП на кластерах.
В организационной структуре управления можно выделить два относительно самостоятельных уровня: общесистемный, в задачу кото­рого входит управление конфигурированием кластера, контроль и пла­нирование загрузки (узлов, компьютеров), реакция на отказы компонен­тов кластера и др., и уровень собственно управления параллельными процессами, индуцируемыми при выполнении ГСПП.
На рис. 2 представлена структура и основные блоки управления процессом выполнения ГСПП на кластерных системах.
I Блоки системного уровня I

УК

ин

от

ОБ

УЗ

АД



КО

: Г


Г !


УБ

УП
1 1
! Интерпретатор 1





ОС

Блоки процессного уровня


Рис. 2. Структура и основные блоки управления процессом выполнения ГСПП
Кратко опишем функции указанных на этом рисунке блоков.
УК - блок управления конфигурациями, в задачу которого входит конфигурирование узла кластера (или кластера в целом), и его реконфи-гурирование в процессе функционирования в связи с отказами и восста­новлениями компонентов кластера (компьютеров, коммуникаций и др.).
ИН - блок инициализации выполнения ГСПП.
ОТ - блок отказоустойчивости, его функции: реакция на отказы компонентов кластера и реализация принятой стратегии периодического сохранения состояний компонентов кластера на случай их отказа. Стра­тегия может быть или простейшей, предусматривающей периодическое сохранение состояния компьютера или другого контролируемого ком­понента кластера на общем носителе памяти (например, дисковой памя­ти сервера узла), или более сложной, например, основанной на той или иной схеме «договоренности» между компьютерами о периодическом сохранении компьютерами состояний других компьютеров на случай отказапоследних [10]. Отказы или восстановления компонентов класте­pa, фиксируемые блоком ОТ, также передаются блоку УК в качестве информации для изменения конфигурации кластера.
ОБ - блок реализации по соответствующему протоколу интер­фейсных взаимодействий между компьютерами кластера.
УЗ - блок контроля загрузки компонентов кластера, ее прогнози­рования и перераспределения параллельных процессов между компью­терами узла или между узлами кластера с целью достижения макси­мальной эффективности его работы.
АД - блок администрирования, в функции которого входят ин­сталляция программных средств для управления на кластере, оператив­ное получение информации о функционировании (например, загрузке) кластера, «вмешательство» в его работу администратора, если это ока­зывается необходимым.
Блок координации (КО) представляет из себя в программном смыс­ле монитор и осуществляет все взаимодействия друг с другом перечис­ленных блоков.
Блоки процессного уровня непосредственно связаны с определе­нием готовности и идентификацией индуцируемых при выполнении ГСПП процессов (блок управления буферами - УБ), их организацией и контролем состояний (блок управления процессами УП) и планирова­нием выполнения (блок планирования - ПЛ).
Блок УП также реализует, путем обращения к операционной сис­теме (ОС) функции, связанные с постановкой процессов в очередь для выполнения на процессоре компьютера и идентификацией команд об­ращения к блоку управления буферами.
Блоки, реализующие эти действия, образуют интерпретатор ЯГСПП.
Заключение
В настоящее время на языке Java разработан комплекс программ­ных средств управления параллельным выполнением граф - схемных программ на кластере, который базируется на описанной схеме по­строения управления кластером и выделенных в ней блоках.
В настоящее время идут работы по отладке разработанных про­граммных средств на кластере кафедры.
Работа выполнена при поддержке РФФИ, проект 03-01-00588
Литература
Кутепов В.П. Организация параллельных вычислений на системах // М:, МЭИ, 1988.
Kutepov V.P., Falk V. Integrated tools for functional logical and data flow parallel programming and controlling parallel computations on computer systems //
Proceedings of International conference on parallel computing technologies, No­vosibirsk, 1991.
Арефьев A.A. и др. Язык граф-схем параллельных алгоритмов и его расширения // Программирование, 1981, №4.
Кораблин Ю.П. Проблема корректности граф-схем параллельных алго­ритмов // Программирование, 1978, №5.
Кораблин Ю.П. Языки параллельных алгоритмов и принципы их реали­зации // Автореферат канд. диссертации. М.: МЭИ, 1977.
Дмитриев Ю.К., Хорошевский ВТ. Вычислительные системы из мини ЭВМ // М:, «Радио и связь», 1982.
Строева Т.М., Фальк В.Н. Асинхронные вычислительные сети (ABC): ABC-модель и ABC система программирования // Кибернетика, 1981. №3.
Dennis J.B. First version of data flow language // In Proc. Colloque sur la Programmation, vol.19 (Lecture notes in computer science), 1974.
Строева T.M. Асинхронные вычислительные сети и их применение в системах параллельного программирования // Автореферат кандидатской диссертации. М.: МЭИ, 1981.
10. Лобанов В.П. Разработка алгоритмов и программных средств обеспе-
чения надежности параллельных вычислений на вычислительных комплексах
// Авторефераткандидатскойдиссертации. М.: МЭИ, 1985.
Кутепов В.П. Об интеллектуальных компьютерах и больших компью­терных системах нового поколения // Теория и системы управления, 1996. №5.
Воеводин В.В., Воеводин Вл.В. Параллельные вычисления // Санкт-Петербург, «БХВ-Петербург», 2002.
Amnon Barak et. A Scalable cluster computing with Mosix for Linux: In­stitute of Computer Science // The Hebrew University of Jerusalem, 1999.

Шнитман В. Системы Exemplar SPP1200 // Открытые системы, 1991. №6.
Шмидт В. Системы IBM SP2 // Открытые системы, 1995. №6.
16. Кутепов В.П., Котляров Д.В. и др. Граф-схемное потоковое парал-
лельное программирование и его реализация на кластерных системах // Про-
граммирование (в печати).


СИСТЕМА ГРАФ-СХЕМНОГО ПОТОКОВОГО ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ: ЯЗЫК И ИНСТРУМЕНТАЛЬНАЯ СРЕДА ПОСТРОЕНИЯ ПРОГРАММ
В.П. Кутепов, Д.В. Котляров, В.А. Лазуткин
Московский Энергетический Институт (ТУ), г. Москва
Введение
В докладе описаны языковые и инструментальные средства граф-схемного потокового программирования, разработанные в процессе вы­полнения проекта создания системы граф-схемного параллельного пото­кового программирования, осуществляемого на кафедре прикладной ма­тематики МЭИ [1, 2].
1. Язык граф-схемного потокового параллельного программирования
Язык граф-схемного параллельного программирования (ЯГСПП) ориентирован на крупноблочное (модульное) потоковое программиро­вание задач, он также может эффективно применяться для программно­го моделирования распределенных систем, систем массового обслужи­вания и др., информационные связи, между компонентами которых структурированы и управляются потоками данных, передаваемых по этим связям.
Язык позволяет эффективно и единообразно представлять в про­граммах следующие виды параллелизма:
параллелизм информационно-независимых фрагментов (про­странственный);
потоковый параллелизм, обязанный своим происхождением конвейерному принципу обработки данных;
параллелизм множества данных (SIMD), реализуемый в языке граф-схемных параллельных программ через механизм тегирования, ко­гда одна и та же программа или ее фрагмент применяются к различным данным;
«внутренний» параллелизм, описываемый в самих подпрограм­мах модулей, например, средствами порождения нитей в подпрограм­мах, задания векторного параллелизма идр. [1].
С другой стороны, важными с позиции программирования, осо­бенностями ЯГСПП являются:
возможность визуального графического и текстового способов разработки программ, возможность взаимнооднозначного перехода ме­жду ними;
возможность простого структурирования программы и отраже­ния декомпозиционной иерархии при ее построении путем использова­ния отношения «схема-подсхема»;
использование традиционных последовательных языков (Pascal, C/C++, Java и др.) при программировании модулей.
Граф-схемная параллельная программа (ГСПП) представляется в виде пары <ГСД>, где ГС - граф-схема, I - интерпретация.
Граф-схема или просто схема позволяет визуально представлять состоящую из модулей программу решения задачи; интерпретация со­поставляет модулям множество подпрограмм, а связям между модулями - типы данных, передаваемых между подпрограммами модулей в про­цессе выполнения ГСПП. Основным «строительным» блоком ГСПП яв­ляется модуль. Все входы и выходы модулей строго типизированы и раз­делены на группы (отдавая дань предыстории ЯГСПП, они называются конъюнктивными группами входов (КГВх) и конъюнктивными группами выходов (КГВых) соответственно) и отражают структуру потоков дан­ных, передаваемых между подпрограммами модулей. Каждой КГВх мо­дуля однозначно сопоставляется подпрограмма на одном из последова­тельных языков программирования (C/C++, Pascal, Java и др.), причем перечисленные формальные параметры и их типы в задании подпро­граммы должны совпадать с порядком изображения (слева направо) вхо­дов КГВх и их типами соответственно. ГС представляет блочную струк­туру, построенную из модулей, путем соединения выходов КГВых моду­ля с входами КГВх другого или этого же модуля, причем типы соединяе­мых входов и выходов должны совпадать. В интерпретации такое соеди­нение называется информационной связью (ИС), по которой данные со­ответствующего типа передаются от одного модуля к другому [1, 3].
Параллельное выполнение ГСПП представляется как последова­тельность смены состояний, каждое из которых характеризуется множе­ством процессов, индуцируемых при выполнении подпрограмм модулей ГСПП, сопоставляемых в интерпретации их КГВх.
Модуль ГСПП считается готовым для выполнения по любой из своих КГВх, если на всех входах этой КГВх (в соответствующих входам буферах) есть данные, помеченные одним и тем же тегом [1].
При выполнении процесса в его подпрограмме могут использоваться специальные системные команды, реализуемые посредством обычного обращения к специальным функциям: WRITE (запись), READ (чтение), OUT (выход), позволяющие осуществлять межмодульное взаимодействие, т.е. строить различные схемы взаимодействия по данным между подпро­граммами различных модулей путем чтения данных из буферов или запи­си данных в буферы, сопоставляемые входам КГВх модулей [1].
Для того чтобы ГСПП могла одновременно оперировать с различными, не связанными друг с другом экземплярами данных, последние снабжаются специальными метками, иначе тегами, позволяющими не смешивать данные из различных экземпляров. Тегирование позволяет одновременно применять подпрограммы модуля к экземплярам данных, обеспечивая при этом однозначность зависимости между входными данными и результатами параллельного потокового выполнения ГСПП. С каждым значением, которое передается по ИС, в процессе выполнения ГСПП, должен быть связан уникальный тег, идентифицирующий только этот набор данных, и наследуемый при передаче результата применения подпрограммы модуля к этим данным на вхо!д41С(ЕШвд^имцвр(ИМ?рг^ис.троения двух граф-схем по разному реали­зующих задачу вычисления двух сумм: произведений четных элементов

и частных (соответствующий элемент первого вектора делим на соот­ветствующий элемент второго вектора) нечетных элементов векторов a и b длины N, причем длина N и сами векторы заданы не статически, а генерируются случайным образом.
Разработка граф-схемы задачи, определение задач модулей:
а) Первое решение - c использованием механизма тегирования. С
помощью тега будем различать, какое именно (четное или нечетное)
значение поступило.
ГС данной задачи построим следующим образом (см. рис.1): мо­дуль GenN вырабатывает случайное целое число - количество компо­нент вектора и передает на вход модулей GenA и GenB, которые выра­батывают сами компоненты вектора. Четные компоненты вектора поме­чаем одним тегом, нечетные - другим и передаем их модулю EvalExpr, который в зависимости от значения тега либо перемножает компоненты векторов, либо делит их. А результат затем отправляет модулю Sum. На другой вход модуля Sum поступают два значения: количество четных и нечетных компонент вектора, с соответствующими тегами. Это необхо­димо для того, чтоб просуммировать четные (нечетные) компоненты вектора (будет одновременно запущено два экземпляра суммирующей функции). После суммирования результат передается модулю Print для вывода его на экран.
б) Второе решение - без использования механизма тегирования (см.
рис. 2). В данном случае задачу определения четности поступившего зна-
чения наложим на дополнительный модуль (CheckValue), который, в зави-
симости от четности значений, отсылает их либо на первую КГВых, либо
на вторую. Модуль EvalSum занимается вычислением суммы, если данные
поступили на первую КГВх модуля, то суммируются произведения посту-
пающих значений, если на вторую, то - частные. Модуль GetData читает
начальные данные из файла и передает модулю CheckValue, который, по-
токовым образом, отправляет полученные данные на различные КГВых в
зависимости от четности текущего индекса. КГВх модуля EvalSum также
обрабатывают данные потоковым образом, а именно суммируют произве-
дения (частные) компонент вектора. После вычисления обоих сумм ре-
зультат передаются модулю Print для вывода его на экран.

GenN
Генерация N
GenData
Генерация исходных данных



GenA
Генерация at
—fc=
GenB
Генерация bi
3—
О—6—6
CheskValue
Проверяем, какое значение (чет/нечет) поступило
-Q-Q

EvalExpr
Вычисление: аг*Ъ{, если i-четное, и a/bt, если i-нечетное
9-

Sum
Суммирование значений
—?
Print
Вывод результата


0-6
EvalSum Вычисление laab, и

Рис. 1. ГС программы а) Рис. 2. ГС программы б)
Для первого решения примера рассмотрим описание подпрограмм каждого модуля на языке С: Модуль GenN:
void startup() {
int N;
int place[1]={1},data[1];
N=rand();//reHepMpyeM случайное целое число N data[0]=N;
write(1,0,place,data);//nepecbmaeM количество генери­руемых элементов place[0]=2; data[0]=N - N/2;
write(1,1,place,data);//Kx^H4ecTBo четных элементов (тег = 1)
data[0]=N/2;
out(1,2,place,data);//Kx^H4ecTBo нечетных элементов (тег = 2)
}
Модули GenA и GenB:
void GenVector(int tag,int x1)
{
int place[1]={1},data[1];
for(int i=0;i<x1;i++)
{
data[0]=rand();//reHepMpyeM случайное целое число -элемент вектора
if(i%2==0)//e^M i-четное, то тег задаем равный 1
{
write(1,1,place,data);
}
elseZ/иначе тег устанавливаем в 2
{
write(1,2,place,data);
} }
}
Модуль EvalExpr:
void evalution(int tag,int x1,int x2)
{
int place[1]={1}; float data[1];
if(tag==1)//ecли четный индекс
{
data[0] = (float)(x1*x2);//Bbi4H^HeM произведение
}
else//ecли нечетный индекс
{
data[0]=(float)x1/(float)x2; //вычисляем частное
}
out(1,tag,place,data);
}
Модуль Sum:
void sum(int tag,float x1,int x2)
{
int place[1]={1}; float data[1];
float S=x1;//Haчaльнoe значение суммы
float value;
for(int i=0;i<x2-1;i++)
{
//Читаем новое значение и добавляем к сумме
read(1,tag,place,&value);
S+=value;
}
data[0]=S;
out(1,tag,place,data)
}
Модуль Print:
void outres(int tag,float x1)
{
if(tag==1) {
printf("Сумма произведений четных компонент вектора: %f",x1);
}
else
{
printf("Сумма частных нечетных компонент вектора: %f",x1);
}
}

Для второго решения примера ограничимся рассмотрением подпрограмм мо­дулей CheckValue и EvalSum:

Модуль CheckValue:
void checking(int tag,int x1,int x2,int x3)
{
int place1[2]={1,2},place2[1]={3},place3[2]={1,3}; int data1[2],data2[1];
data2[0]=x2-x2/2; data1[0]=x1; data1[1]=x2;
write(1,0,place1,data1);//Oтcылaeм модулю EvalSum1 первые четные значения векторов: a0 и b0
write(1,0,place2,data2);//Oтcылaeм модулю EvalSum1 ко­личество четных значений
data2[0]=x2/2;
write(2,0,place2,data2);//OTCbmaeM модулю EvalSum2 ко­личество нечетных значений
int CurrentVal=1;//nepeMeHHaH, которая будет отвечать за четность текущего значения (1-нечетное,0-четное)
for(int i=0;i<x2-1;i++)
{
read(1,0,place3,data1);//4MTaeM поступающие значения if(CurrentVal==0)//ecли текущий индекс четный
{
write(1,0,place1,data1);//nepeflaeM значения модулю EvalSum1
}
elseZ/если текущий индекс нечетный
{
write(2,0,place1,data1);//nepeflaeM значения модулю EvalSum2
}
CurrentVal=1-CurrentVal;//MeHHeM четность
}
}
Модуль EvalSum:
void EvalSum1(int tag,int x1,int x2,int x3)
{
int place1[2]={1,2},place2[1]={1};
float data[1];
float S=(float)(x1*x2);//Haчaльнoe значение суммы
int value[2];
for(int i=0;i<x3-1;i++)
{
//Читаем новые значение и их произведение добавляем к
сумме
read(1,0,place1,value); S+=(float)(value[0]*value[1]);
}
data[0]=S;
out(1,0,place2,data);
}
void EvalSum2(int tag,int x1,int x2,int x3)
{
int place1[2]={1,2},place2[1]={1}; float data[1];
float S=(float)x1/(float)x2;//Haчaльнoe значение суммы
int value[2];
for(int i=0;i<x3-1;i++)
{
//Читаем новые значение и их частное добавляем к сумме read(1,0,place1,value);
S+=(float)value[0]/(float)value[1];
}
data[0]=S;
out(1,0,place2,data);

2. Инструментальная среда разработки программ на ЯГСПП
Инструментальная среда предназначена для разработки граф-схемных параллельных программ и целиком согласована с ЯГСПП. В ин­струментальной среде поддерживается графическая разработка ГСПП и разработка ГСПП в текстовом виде, используя многооконную организа­цию. Между графическим и текстовым представлением ГСПП существует взаимнооднозначный переход. Инструментальная среда соединена с реля­ционной базой данных, которая играет роль единого хранилища ГСПП всех пользователей. При разработке программы пользователю предостав­ляется возможность сконцентрировать свое основное внимание на интере­сующем его элементе: подсхеме (ее содержимое открывается в новом ок­не), подпрограмме, сопоставленной некоторой КГВх (текст подпрограммы будет открыт в новом окне, где можно его отредактировать, настроить различные параметры подпрограммы, проверить корректность типов дан­ных) и др.
На рис. 3 приведены основные блоки инструментальной среды:



Блок графической разработки ГСПП
Блок текстовой разработки ГСПП




1
Блок взаимной трансляции

Блок координации
1


Блок взаимодействия с базой данных

ОС Windows

База данных
Рис. 3. Архитектура инструментальной среды Рассмотрим назначение каждого блока:
Блок графической разработки ГСПП предназначен для визуаль­ного проектирования ГС, позволяя добавлять, удалять, редактировать элементы ГСПП и др. Данный блок также осуществляет синтаксический контроль создаваемой ГС.
Блок текстовой разработки ГСПП управляет ходом построения текстового представления и по своему назначению представляет собой аналог блока разработки графического представления, но работает с текстом ГСПП. Текстовое представление ГСПП представляет собой на­бор XML - документов, DTD которых описано в [1].
Блоки графической и текстовой разработки ГСПП помимо редак­тирования, синтаксического анализа и выявления ошибок в ГС создавае­мых программ имеют средства для поддержки процессов разработки программ «сверху - вниз» и «снизу - вверх». Декомпозиция и структури­рование, присущие процессу разработки программ «сверху - вниз», легко реализуются в инструментальной среде, благодаря модульной организа­ции ГСПП и возможности выделения подсхем.
Механизм задания интерпретации ГС требует обращения к кон­кретному языку (или языкам) последовательного программирования. Как уже было сказано ранее, в ЯГСПП в качестве подпрограмм, сопос­тавляемых КГВх модулей, могут использоваться широко известные по­следовательные языки (C/C++, Pascal, Java и др.). Поскольку инстру­ментальная среда разработана под ОС Windows, в задании интерпрета­ции можно применять все стандартные средства этой ОС для написания подпрограмм, сопоставляемых КГВх модулей.
Все необходимые для задания интерпретации ГС подпрограммы образуют специальную библиотеку (или набор библиотек), а доступ к ним осуществляется, как это определено синтаксисом ЯГСПП.
Блок взаимной трансляции занимается переводом графического представления ГСПП в текстовое и наоборот. Промежуточным звеном на этапе трансляции является объектно-ориентированное внутреннее представление ГСПП.
В инструментальной среде используется реляционная база данных (MS SQL Server 2000) как средство для длительного хранения всей ин­формации о разрабатываемых пользователями ГСПП. Блок взаимодей­ствия с базой данных осуществляет перенос информации о ГСПП из внутреннего представления в базу данных и обратно.
Блок координации управляет работой других блоков.
Заключение
В настоящее время уже накоплен определенный опыт программи­рования на ЯГСПП различных задач [3], как вычислительного характера (матричных задач, задач решения систем линейных уравнений и др.), так и задач, которые непосредственно связаны с потоковой обработкой [4]. Как показывает этот опыт, визуальная схемная разработка парал­лельных потоковых программ на ЯГСПП с использованием созданных инструментальных средств существенно упрощает дело. К примеру, де­композиционное описание технологических процессов сборки автомо­билей, других автоматизированных производств позволяет быстро и просто строить прямые их аналоги в виде программ на ЯГСПП. В ста­дии завершения находится работа по объединению объектно-ориентированного и граф-схемного подходов, которые должны обеспе­чить более широкую технологическую базу для повышения эффектив­ности и унификации методов проектирования программ на ЯГСПП.
Литература
Кутепов В.П., Котляров Д. В., Лазуткин В.А., Осипов М.А. Граф-схемное модульное потоковое программирование и его реализация на кла­стерных системах // Программирование (в печати).
Кутепов В.П., Котляров Д. В., ЛазуткинВ.А., Осипов М.А. Разработка системы граф-схемного потокового параллельного программирования для кластеров // Доклад на четвертом Международном научно-практическом се­минаре «Высокопроизводительные параллельные вычисления на кластерных системах».
Лазуткин В.А. Реализация языка граф-схемного параллельного про­граммирования // Бакалаврская работа.
Грегори Р. Эндрюс Основы многопоточного, параллельного и распре­деленного программирования // Пер. с англ. - М.: Издательский дом «Виль­яме», 2003. - 512 с.
АНАЛИЗ СТРУКТУРНОЙ СЛОЖНОСТИ ФУНКЦИОНАЛЬНЫХ ПРОГРАММ И ЕГО ПРИМЕНЕНИЕ ДЛЯ ПЛАНИРОВАНИЯ ИХ ПАРАЛЛЕЛЬНОГО ВЫПОЛНЕНИЯ НА ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ
В.П. Кутепов, Д.А. Шестаков
Московский Энергетический Институт (ТУ), г. Москва
Введение
Задача определения характеристик программ, по которым можно судить об их организационной (структурной) и вычислительной слож­ности, представляют большой теоретический и практический интерес.
Ниже описывается решение этой задачи, которая возникла при реализации на кафедре прикладной математики проекта создания сис­темы функционального параллельного программирования для кластер­ных систем (научный руководитель - проф. В.П. Кутепов). В рамках этого проекта был разработан язык композиционного функционального параллельного программирования FPTL [1], программы на котором в математическом смысле представляются в виде специального вида функциональных уравнений:
(*)Xi = Ti(Xb..,Xk, i=1,2,..,k),
где Xi - определяемая функция, a ti - композиционные термы, постро­енные путем применения операций композиции функций к функцио­нальным переменным Xi, i=1,2,..,k, и базисным функциям, которые яв­ляются либо встроенными командами компьютера, либо функциями, определяемыми посредством конструкторов, либо импортируемыми из других языков (C, Pascal и т.д.).
Операции композиции функций в созданном языке таковы, что только операция последовательной композиции имеет последователь­ную вычислительную семантику; другие операции являются параллель­ными [2].
Это создает предпосылки для построения достаточно эффективных механизмов автоматического выявления параллелизма в программе и реа­лизации процессов параллельного выполнения функциональных программ на вычислительных системах (ВС). Однако на этом пути возникает пробле­ма определения фрагментов функциональной программы, которые целесо­образно перемещать между компьютерами ВС в процессе ее параллельного выполнения. Допуская возможность перемещения несложных фрагментов (например, базисных функций), обнаруживается известный эффект резкого увеличения интенсивности обменных взаимодействий между компьютера­ми ВС и следующей за этим ее деградацией [3]. Поэтому алгоритм плани­рования параллельных процессов должен обладать возможностью доста­точной тонкой дифференциации по сложности фрагментов выполняемой программы, которые могут выполняться одновременно [3].
Предлагаемое решение основано на анализе системы уравнений (*), представляющих функцию, а также на анализе отношений между транзитивными классами определяемых функций с целью выявления в ней различных по своей природе рекурсивных определений функций (простых циклов, взаимно рекурсивных определений и др.), независи­мых определений функций и др. [4]. Это позволяет достаточно точно упорядочивать одновременно выполняемые фрагменты параллельной программы по вычислительной сложности и сложности их взаимных связей по данным, эффективно решать задачу определения функций, которые планировщик перемещает между компьютерами с целью дос­тижения их равномерной загрузки и уменьшения обменных взаимодей­ствий.
Заметим, что анализ природы рекурсивных определений в про­грамме позволяет также достаточно строго судить о ее структурной сложности.
Описываемая ниже система оценок структурной сложности осно­вывается на понятиях «рекурсивность», «цикличность», «вложенность».
1. Характеристики структурной сложности функциональных программ
Будем исходить из того, что функция определена в виде системы уравнений (*), где ti - терм, в котором могут содержаться функцио­нальные переменныеX1v.,Xk и базисные функцииf1,.., fm.
Введем отношение непосредственной зависимости между функ­циональными переменными: если Xj используется в терме ti, то будем говорить, что Xi непосредственно зависит от Xj (обозначение Xi®Xj).
Обозначим через [Xi] транзитивное замыкание отношения непо­средственной зависимости для Xi.
Множество [Xi] будем транзитивным классом Xi. Очевидно, если [Xi] = 0, то в определении Xi не используется функциональных пере­менных.
Определение 1: Функциональная переменная Xi определена рекур­сивно, если Xie [Xi].
Определение 2: Определения Xi и Xj взаимно рекурсивны, если Xie[Xj] иXje[XJ.
Легко показать, что в этом случае [Xi]=[Xj]
Определение 3: Определение Xj- простое рекурсивное или простое циклическое определение, если
Xj e[Xj]AVXi(Xi e[Xj]/\Xi *Xj з Xj ? [Xi] /\Xi ? [Xi]).
Простое циклическое определение не содержит вложенных цик­лических определений.
Определение 4: Определение Xj назовем циклическим, если
Xj е [Xj] л VXi (Xi e [Xj] л Xi Ф Xj з XjЈ [Xi]).
Определение 5: Определение Xj - простое, если Xj не является ре­курсивным и [Xi] не содержит рекурсивных определений.
Определение 6: Назовем классом взаимной рекурсивности для Xi множество всех взаимно рекурсивных с Xi определений.
Будем обозначать класс взаимной рекурсивности для Xi через <Xi>. Очевидно, что для взаимно рекурсивных определений классы вза­имной рекурсивности будут эквивалентны. Легко показать, что неэкви­валентные классы взаимной рекурсивности не пересекаются. Очевидно, что если <Xi> вложено в Xj, то каждый элемент Xke<Xi> также вложен в
Xj.
Определение 7: Определение Xi вложено в определение Xj, если Xie [Xj], Xi строго вложено в определение Xj, если Xie[Xj] и XjЈ [Xi].
Очевидно, взаимно рекурсивные определения строго вложены друг в друга.
Если определение Xi - циклическое определение (простое цикли­ческое определение), то будем также говорить, что определение Xi -циклическое вложение в определение Xj (простое циклическое вложение в Xj).
Определение 8: Определения Xi и Xj независимы, если пересечение их транзитивных классов пусто.
Если Xi и Xj независимы, то ясно, что при параллельном вычисле­нии значений Xi(X) и Xj(X") на разных компьютерах ВС, между этим процессами не будут происходить обменные взаимодействия.
2. Применение к задаче планирования процессов параллельного вычисления функциональных программ на ВС
Описанные результаты структурного анализа функциональных программ используются в двух аспектах в рамках реализуемого проекта [1]. С одной стороны, в инструментальной среде разработки функцио­нальных программ создан программный блок, который позволяет про­граммисту проводить структурный анализ разрабатываемой им про­граммы и оценивать ее организационную и логическую сложность.
С другой стороны, в исполнительной части разработан планиров­щик, который использует результаты структурного анализа при опреде­лении фрагментов функциональной программы, которые назначаются для выполнения на различные компьютеры ВС.
При этом планировщик пытается решить две основные задачи: поддерживать равномерную загрузку компьютеров ВС, следуя эвристи­ческому правилу - не допускать простоев и перегрузок компьютеров, и минимизировать обменные взаимодействия между компьютерами ВС.
Используя результаты структурного анализа функциональной программы, планировщик при необходимости перемещения фрагментов программы с одного компьютера (например, перегруженного) на другой компьютер (простаивающий или недогруженный) выбирает наиболее сложный с вычислительной точки зрения фрагмент. При этом в качестве перемещаемых фрагментов рассматриваются только рекурсивно опре­деленные функциональные переменные, что позволяет существенно уменьшить обменные взаимодействия между компьютерами ВС и ис­ключить ее деградацию, которая возникает, если перемещать между компьютерами базисные функции.
Заключение
Были проведены предварительные эксперименты с целью провер­ки эффективности применения описанных алгоритмов для планирова­ния параллельного выполнения функциональных программ на ВС [5]. Эксперименты проводились на кластере из 6 машин (локальная сеть). Были заданы две функциональных программы - линейная и сильноре­курсивная. Для сравнения помимо эвристического алгоритма планиро­вания, основанного на описанных выше правилах, было использовано еще три алгоритма планирования:
случайный - назначение процессов на компьютеры для вычисления проводилось в случайном порядке,
с приоритетами - то же, что и случайный, но выбор функций для вы­числения производится в соответствии с их структурными характе­ристиками,
«равномерный» - на все узлы ЛВС назначалось одинаковое количе­ство процессов.
В результате произведенных экспериментов было выявлено, что время выполнения линейной программы для эвристического алгоритма планирования одинаково для 2, 4 и 6 машин. Это связано со стратегией назначения функциональных процессов. В результате вся программа выполнялась на одной машине, поэтому время вычислений не зависит от числа машин в кластере.
Наибольшая производительность достигается при использовании эвристического алгоритма планирования для вычисления рекурсивной программы. Фактически, на 6 машинах время выполнения при использо­вании этого алгоритма в 2-4 раза меньше времени выполнения с исполь­зованием случайного алгоритма.
Проведенные эксперименты, хотя и являются ограниченными (не­большое количество компьютеров в кластере, небольшое разнообразие моделируемых программ), тем не менее, показывают, что предложен­ный алгоритм упорядочивания может оказаться эффективным при орга­низации параллельного выполнения сложных рекурсивных программ на ВС и в настоящее время реализуется в создаваемой системе [1].
Литература
Бажанов С.Е., Кутепов В.П., Шестаков Д.А. Язык функционального параллельного программирования и его реализация на кластерных системах. Теория и системы управления (в печати).
Кутепов В.П., Фальк В.Н. Модель асинхронных вычислений значений функций в языке функциональных схем // Программирование, 1978, № 3. С.3-
15.
Кутепов В.П. Об интеллектуальных компьютерах и больших компью­терных системах нового поколения // Известия академии наук, Теория и сис-темыуправления, 1996. №5.
Шестаков Д.А. Разработка алгоритмов и инструментальных программ­ных средств для структурного анализа программ и оценки их сложности. Ди­пломная работы на соискания звания бакалавр математики, Москва, МЭИ,
2000.
5. ШестаковД.А. Структурныйисемантическийанализфункциональных
программ и создание на его основе эффективных алгоритмов планирования
процессов параллельных вычислений значений функций на вычислительных
системах // Диссертационная работы на соискание звания магистр математи-
ки, Москва, МЭИ, 2002.


ОСОБЕННОСТИ ФУНКЦИОНАЛЬНОГО ЯЗЫКА ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ «ПИФАГОР»

А.И. Легалов, Д.В. Привалихин
Государственный техническийуниверситет, г. Красноярск
Введение
Язык программирования Пифагор [1] предназначен для разработ­ки параллельных программ, управление вычислениями в которых осу­ществляется по готовности данных. Несмотря на то, что непосредствен­ная реализация подобных средств в настоящее время неэффективна, уже сейчас можно разрабатывать параллельные программы, выполняемые как на традиционных последовательных компьютерах, так и на кластер­ных системах. Существующие на данный момент версии языка и испол­нительной системы [2] поддерживают только динамическую типиза­цию. Формирование новых типов данных осуществляется неявно в ходе выполнения функций. Подобный механизм использовался в ранних языках функционального программирования, например, LISP [3]. Боль­шинство же современных языков данной группы поддерживают стро­гую типизацию.
Вместе с тем, механизмы динамической типизации могут разви­ваться по специфичным для них направлениям, что позволяет получать интересные эффекты, расширяющие возможности языка. В частности, сочетание механизма перегрузки функций и динамических типов, опре­деляемых пользователем, обеспечивает написание эволюционно расши­ряемых параллельных программ. Ниже эти возможности языка «Пифа­гор» рассматриваются более подробно.
Перегрузка функция с одинаковой сигнатурой
В языке отсутствует строгая типизация, поэтому все функции с оди­наковыми именами становятся неразличимы (имеют одинаковую сигнату­ру). Вместо выбора одной из перегруженных функций, осуществляется их одновременное выполнение. Результат возвращается в виде параллельного списка. В отличие от обычных функций, перегруженные функции задают­ся добавлением к обозначению имени квадратных скобок, в которых мо­жет стоять любое действительное число, задающее ранг.
Ранг используется для упорядочения функций в параллельном списке по возрастанию. При отсутствии числа ранг считается равным нулю. Функции с одинаковым рангом могут располагаться в списке в произвольном порядке. Обычно они размещаются в порядке их обра­ботки транслятором. Пример использования рангов:
OverFunc[2.5] << funcdef Param {// Тело функции}
OverFunc[] << funcdef Param { // Тело функции }
OverFunc[-10] << funcdef {// Тело функции}
Вызов параллельной функции синтаксически ничем не отличается от обычного вызова. В постфиксной записи он будет выглядеть следую­щим образом:
X:OverFunc;
Перегрузка функций позволяет гибко добавлять новые возможно­сти, обуславливаемые появлением дополнительной информацией о раз­рабатываемом алгоритме. В частности можно использовать методы, обеспечивающие децентрализованную разработку отдельных фрагмен­тов функций, связанных с вычислением при альтернативных условиях.
В качестве простейшего примера использования перегрузки функ­ций с одинаковой сигнатурой можно рассмотреть вычисление факториала. Пусть, факториал отдельно вычисляется для значений аргумента, равного
0, 1, диапазона от 2 до n (где n - константа, определяющая максимально допустимую величину аргумента). При значении аргумента, превышаю­щем n, выводится сообщение о переполнении. При отрицательном значе­нии аргумента выводится сообщение об ошибке. Константа n определена в программе следующим образом:
n<<const 10.
Функция, осуществляющая вычисление факториала, состоит из нескольких перегруженных функций, каждая из которых осуществляет необходимые вычисления для аргумента, расположенного в ее диапазо­не. Если значение аргумента не попадает в рассматриваемый диапазон, перегруженная функция выдает пустое значение.
Сообщение об ошибке, выдаваемое при отрицательном значении аргумента, порождается функцией:
overfact[]<< funcdef x {
«Ошибка! Отрицательный аргумент»:[(x,0):<] >>return;
}
В случае переполнения значащий результат выдает другая пере­груженная функция, сигнализирующая об ошибке переполнения:
overfact[]<< funcdef x {
«Ошибка! Слишком большой аргумент»:[(x,n):>] >>return;
}
При аргументе равном 0 или 1 вычисления осуществляются одной из следующих функций:
overfact[]<< funcdef x { 1:[(x,0):=] >>return;
}
overfact[]<< funcdef x { 1:[(x,1):=] >>return;
}
И, наконец, при попадании аргумента в диапазон от 2-х до макси­мально допустимого числа, получаемый результат возвращается сле­дующей функцией:
overfact[]<< funcdef x { ({(x, (x,1):-:overfact):*}) :[((x,1):>, (x,n):<=):*]:[]:. >> return
}
Одновременный вызов всех функций с одинаковой сигнатурой осуществляется внутри функции, осуществляющей окончательное фор­мирование и вывод факториала, синхронизацию альтернативных значе­ний в общем списке данных:
fact << funcdef x {
(x:overfact):[] >> return
}
Применение пользовательских типов данных
В языке реализована инструментальная поддержка механизма строгой динамической типизации на основе пользовательских типов. Для этого введен ряд дополнительных конструкций и расширена семан­тика уже существующих понятий. Возможны:
определение пользовательского типа;
сравнение пользовательских типов на равенство и неравенство;
- проверка на принадлежность некоторого значения величине, до­пустимой для заданного пользовательского типа;
преобразование в пользовательский тип;
разыменование пользовательского типа.
Определение пользовательского типа задается соответствую­щим предикатом, сопоставляющим проверяемый элемент с некоторым выражением. Если результат проверки является истиной, то элемент принадлежит проверяемому типу. Предикат оформляется в виде специ­альной функции typedef, возвращающей булевское значение. Ее обо­значение регистрируется в таблице пользовательских типов. В качестве примера можно рассмотреть, как задаются геометрические фигуры тре­угольник и круг:
Triangle << typedef X{
//Аргумент - список из трех целочисленных элементов [(((X:type,datalist):=,(X:\,3):=):*:int,1):+]A
(
false,
{([(X:1:type,int),
(X:2:type,int), (X:3:type,int)]:=):*} ):. >> return
};
Circle << typedef X{ //Аргумент - целочисленный атом (X:type,int):= >> return;
};
Сравнение пользовательских типов осуществляется точно так­же как и сравнение базовых типов языка: выделяется тип элемента функцией type, проверяется совпадение имен выделенного и проверяе­мого типа. Результат сравнения является истиной при совпадении имен типов. Ниже приводится пример использования сравнения пользова­тельских типов для описания обобщенной геометрической фигуры.
Figure << typedef X{
//Аргумент - треугольник или круг X:type >> t
([(t, Triangle), (t, Circle)]:=):+ >> return;
};
Проверка на принадлежность позволяет выяснить возможность соответствия между динамически формируемыми данными и typedef. Для этого используется функция in, которая возвращает значение, полу­ченное в результате выполнения предиката, заданного в описании поль­зовательского типа. Принадлежность позволяет в дальнейшем осущест­вить преобразование проверяемого аргумента в элемент пользователь­ского типа. Ниже представлены примеры использования функции при­надлежности:
((10,20,15),Triangle):in^>true
((10,20,15),Circle):in^>false
(10,Circle):in ^>true
Преобразование в пользовательский тип используется для формирования требуемых абстракций по принципу «обертки» преобра­зуемых данных. Является расширением операции преобразования базо­вых типов. Суть заключается в получении нового значения элемента, следующей структуры:
Элемент пользовательского типа = Пользовательский тип, преобразуемый элемент>
Само преобразование задается указанием пользовательского типа в качестве функции и осуществляется в зависимости от значения аргумента:
если тип аргумента совпадает с типов в операции преобразова­ния, то возвращается значение исходного аргумента;
преобразование осуществляется только в том случае, если провер­ка аргумента на принадлежность функцией in, осуществляемая неявно, да­ет «истину»;
во всех остальных случаях функция преобразования в пользова­тельский тип возвращает ошибку TYPEERROR.
Использование данной операции позволяет формировать необхо­димые абстракции при выполнении программы:
(10,20,15):Triangle Треугольник со сторонами (10,20,15) Описанная операция не обеспечивает автоматического преобразо­вания пользовательских типов друг в друга, даже если их значения при­надлежать единому подмножеству. Данное ограничение введено для более строгого контроля. Зачастую подобные преобразования бывают необходимы. В этом случае можно воспользоваться разыменованием пользовательского типа, заключающемся в выделении «обернутого» значение функцией value. Данная функция «отбрасывает» пользова­тельский тип, тем самым «обезличивая» преобразуемый элемент: (10,20,15):Triangle:value => (10,20,15) (10,20,15):Triangle:value:1:Circle => Круг радиусом 10 Следует отметить, что попытка применить операцию разыменова­ния к базовым типам ведет к генерации ошибки VALUEERROR: 10:value => VALUEERROR
Ниже приводится функция, вычисляющая периметры различных геометрических фигур, расположенных в некотором списке:
// Список из пяти фигур
Figures << const ((3,4,5): Triangle, 10:Circle,
7:Circle, 1:Circle, (13,14,15): Triangle);
//Нахождение периметра обобщенной фигуры
pi << 3.1415;
fig_perimeter << funcdeffigure { fig << figure:value; //выделение параметров фигуры // Формирование селектора по типу фигуры tag << ([(figure:type,Triangle), (figure:type,Circle)]: =):?;
//Использование признака для выбора формулы tagA(
// суммирование сторон треугольника
{((fig:1,fig:2):+,fig:3):+},
// формула для периметра круга
{((2,pi):*fg):*}
):.
>> return;
};
// Получение списка периметров по списку фигур all_perimeter << funcdeffigjist {
//Вычисление одновременно для всех элементов списка (fig_list:[]:fig_perimeter) >> return;
};
Заключение
Предлагаемые механизмы предоставляют инструментальную под­держку для гибкой разработки функциональных параллельных программ. Возможно не только добавление новых обработчиков специализаций, но и изменение свойств ранее разработанных типов. Это позволяет достаточно гибко наращивать функциональные возможности параллельной програм­мы. Работа выполнена при поддержке РФФИ № 02-07-90135.
Литература
Легалов А.И., Кузьмин Д.А., Казаков Ф.А., Привалихин Д.В. На пути к переносимым параллельным программам // Открытые системы, 2003. № 5 (май). С. 36-42.
Легалов А.И. Инструментальная поддержка процесса разработки эво-люционно расширяемых параллельных программ // Проблемы информатиза­ции региона. ПИР-2003/ Материалы 8-й Всероссийской научно-практической конференции. Красноярск, 2003. С. 132-136.
Маурер У. Введение в программирование на языке ЛИСП // М.: Мир, 1976. - 104 с.


РЕАЛИЗАЦИЯ ФУНКЦИЙ СТАНДАРТА MPI ДЛЯ ЭМУЛЯЦИИ ОБМЕНОВ СООБЩЕНИЯМИ МЕЖДУ УЗЛАМИ МНОГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ
А.В. Лепихов
Челябинский государственный университет, г. Челябинск
В настоящее время вычислительные комплексы с массовым па­раллелизмом широко применяются для решения большого класса задач. Однако при использовании данных систем возникает сложная проблема отладки параллельных программ, не решенная в полной мере до на­стоящего момента.
Как известно отладка программы отнимает порядка 50% времени создания программы, а зачастую оказывается очень продолжительной. Сложность параллельных программ как таковых и их недетерминирован­ное поведение превращают отладку параллельных программ в очень сложный для разработчика процесс.
Помимо приобретения коммерческого отладчика (например, To-talView [http://www.etnus.com] и PGDBG [http://www.pgroup.com]) суще­ствуют другие способы отслеживания событий программы при помощи вывода сообщений трассировки, распечатка значений переменных в за­данном процессе и т. д. - весьма трудоемкий процесс. Предложенное решение проблемы выбора средств отладки основано на эмуляции па­раллельных процессов и обменов данными между ними с помощью стандартных средств ОС Windows.
Разработанный эмулятор обменов сообщениями представляет со­бой динамически компонуемую библиотеку, интерфейс которой есть подмножество функций стандарта MPI, реализующих асинхронный об­мен сообщениями между процессами. Таким образом, эмулятор позво­ляет запускать параллельные программы непосредственно из среды
MS Visual C++ (без загрузчика) и использовать весь спектр средств встроенного отладчика.
Эмулятор обеспечивает представление процессов, запускаемых на процессорных узлах, в виде процессов ОС Windows, каждый из которых представляет собой совокупность следующих потоков (нитей): мастер, отправитель, получатель и терминатор. Поток-мастер выполняет соб­ственно код процесса. Поток-отправитель обрабатывает массив, эле­ментами которого являются очереди сообщений, передаваемых другим процессам программы. Поток-получатель обрабатывает очередь сооб­щений, поступающих от потоков-отправителей других процессов про­граммы. Поток-терминатор выполняет аварийное завершение всех процессов программы, если поток-мастер одного из процессов выпол­нил функцию MPIAbort.
Прием-передача сообщения от процесса S процессу R выглядит следующим образом (далее мы будем именовать потоки как Master, Sender и Receiver, а индексы имен будут указывать на принадлежность к процессу).
При выполнении функции посылки сообщения поток MasterS до­бавляет в соответствующую очередь потока SenderS запись о данном со­общении и открывает ему семафор для начала передачи сообщения.
Поток SenderS создает в оперативной памяти процесса S область, доступную для потока ReceiverR, записывает в нее передаваемое сооб­щение и генерирует для ReceiverR событие о необходимости начать при­ем. После этого поток SenderS переходит к ожиданию подтверждения от потока ReceiverR о завершении приема. При получении подтверждения SenderS уничтожает ранее созданную область и памяти и закрывает се­мафор передачи сообщения.
Поток ReceiverR выполняет перманентное ожидание события о не­обходимости начать прием. При наступлении такого события он обра­щается к области памяти, которую создал SenderS, и считывает передан­ное им сообщение. После этого ReceiverR высылает потоку SenderS под­тверждение о завершении приема сообщения.
Разработанный эмулятор может быть использован для отладки па­раллельных программ, выполняющих обмен сообщениями на основе стандарта MPI. Переход от отладки к тестированию и обратно требует внесения минимальных изменений в исходные тексты, не влияющие на её работу с использованием стандартных реализаций MPI и изменения параметров их компоновки.

АВТОМАТНАЯ МОДЕЛЬ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

B.C. Любченко
ООО Специальное конструкторское бюро «Локальные автоматизированные системы», г. Новочеркасск
Введение
Рассматривая вопросы проектирования сложных дискретных сис­тем, структурно представимых и/или разлагаемых на параллельно функционирующие подсистемы, можно обратить внимание, что в осно­ве методологии их проектирования в основном лежат сети Петри [1-3]. Модель конечного автомата, если и рассматривается, то на заключи­тельной стадии проектирования для реализации управления дискретны­ми процессами.
Мнение, различающее и разделяющее по своим возможностям се­ти Петри и автоматы, обосновано лишь в силу бытующих представле­ний об ограниченных возможностях конечных автоматов. Но, как мож­но убедиться, уже незначительное усовершенствование автоматной мо­дели придает свойства автоматам, которые могут поколебать главенст­вующее положение сетей Петри даже в такой традиционной для них об­ласти, как описание и реализация параллельных систем.
Проектирование
Формальная модель конечного автомата (КА) и сеть из множества КА - модель СМКА[4] предоставляют разработчику гибкие структур­ные средства для отображения параллельного взаимодействия, как на уровне отдельных компонентов, так и на уровне их множества. Другие технологии разработки программ «сверху вниз», «снизу вверх», струк­турный подход и т.п. таких возможностей, как правило, не имеют. В том же объектно-ориентированном программировании (ООП) вопросы па­раллельной работы объектов вынесены за рамки ООП.
Предлагаемая конечно-автоматная технология (КА-технология) ис­пользует модель со средствами описания параллелизма, которые по сво­им возможностям не уступают другим параллельным моделям. В то же время реализация базовой модели вычислений много проще. Кроме того, при необходимости, применяя стандартные приемы, несложно перейти от параллельного конечно-автоматного описания процессов к их триви­альному последовательному представлению в форме модели блок-схем.
Таким образом, в рамках КА-технологии можно легко и наглядно представлять структуру задач любой сложности в параллельном виде. Пример из [5] это демонстрирует на решении довольно простой задачи.
Более сложные примеры применения конечных автоматов можно найти в [6-8].
Кодирование
После описания структуры системы и алгоритмов работы ее час­тей в терминах формальной модели наступает момент ее реализации. Сейчас это сводится к программированию алгоритмов, представленных моделью блок-схем программ. В КА-технологии алгоритмы представ­лены формой КА-описания. И в ней для их (автоматов) реализации, во-первых, существуют формальные методы перехода от КА к эквивалент­ной блок-схеме (см. [9]), во-вторых, можно использовать давно извест­ные программные методы реализации автоматов.
В то же время современные программные средства позволяют реа­лизовать автоматы в форме, которая приближена к исходному описанию автоматов. В [5] показано, как это осуществимо в рамках КА-технологии. Там же имеется ссылка на DLL-библиотеку, реализующую автоматную модель и параллельную среду, в которою они «погружены».

<<

стр. 2
(всего 4)

СОДЕРЖАНИЕ

>>