An approach to the parallel algorithms synthesis.pdf Для решения ряда задач в различных областях науки и тех-ники всё шире используются параллельные компьютерные ком-плексы различной архитектуры. Это и параллельные суперком-пьютеры, которые включают сотни и тысячи процессоров, ирабочие станции, которые объединены компьютерными сетями,и многопроцессорные рабочие станции. Как следствие этогорастет число пользователей-непрограммистов, не обладающихнадлежащей профессиональной подготовкой для реализации па-раллельных приложений. В связи с этим повышается актуаль-ность создания инструментальных систем, снабженных возмож-ностями «интеллектуальной» деятельности и позволяющих ав-томатически генерировать параллельные программы на основа-нии так называемых непроцедурных спецификаций.Хорошо известна теория вычислительных моделей (ВМ),впервые предложенная Э.Х.Тыугу [1]. Указанный формализми его модификации успешно применяются при создании раз-личных прикладных систем, в силу того, что структура вы-числительных моделей хорошо согласуется с содержаниемсведений, используемых при решении широкого круга вы-числительных задач. В то же время синтез параллельныхпрограмм в рамках теории ВМ исследован достаточно слабо,хотя теория вычислительных моделей обладает хорошо раз-работанным формальным аппаратом и предоставляет возмож-ности для создания весьма эффективных машин вывода.Представляется заманчивым расширить теорию планирова-ния решений задач на вычислительных моделях для синтезапараллельных программ.За основу исследования взят вариант теории ВМ, предло-женный в [2], откуда и заимствован, практически полностью,язык теории.МОДЕЛИ ДЛЯ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВВ данном разделе рассматриваются некоторые прин-ципы и этапы проектирования параллельных структур,которых придерживаются при разработке и реализациипараллельных программ, а также модели, используе-мые при их проектировании.Параллельные комплексы интересны тем, что они по-тенциально могут предоставить сосредоточенные ресурсы(процессоры, память с высокой пропускной способностьюсредств ввода - вывода) для решения важных вычислите-льных проблем. Параллельные вычисления в течение дол-гого времени рассматривались как редкая и экзотическаяподобласть вычислений, мало интересная среднему про-граммисту, но тенденции в приложениях, архитектуре вы-числительных систем и использовании сетей показывают,что на данный момент это не так. Параллелизм становитсяповсеместным, а параллельное программирование стано-вится неотъемлемой частью в разработке программногообеспечения в корпоративных масштабах.В [3] выделяется четыре основных желательных свой-ства параллельных алгоритмов: параллелизм, масштаби-руемость, локальность и модульность. Параллелизм выра-жается в способности выполнять несколько действий од-новременно. Это определяющее свойство, если программавыполняется на нескольких процессорах. Масштабируе-мость означает устойчивость к увеличению числа процес-соров. Локальность означает высокий коэффициент отно-шения числа обращений к локальной памяти к числу об-ращений к удаленной памяти, что является ключом к высо-кой производительности на мультикомпьютерной архитек-туре. И, наконец, модульность - это декомпозиция слож-ных сущностей на отдельные компоненты, что являетсяважным аспектом разработки и проектирования программ-ного обеспечения в параллельных вычислениях, также каки в последовательных.Для теоретических исследований проектирования па-раллельных алгоритмов и программ предложена модельвычислительной машины, называемая мультикомпьюте-ром. Эта модель весьма проста (что облегчает понимание ипрограммирование) и, в то же время, реалистична (этослужит гарантий того, что программа, разработанная дляэтой модели, будет выполняться с соответствующей эф-фективностью на реальных компьютерных комплексах).Мультикомпьютер - это идеализированная модель парал-лельного компьютера, содержащая в себе несколько машинфон Неймана или узлы, соединенные сетью. Сообщенияиспользуются для взаимодействия с другими компьютера-ми или для чтения или записи в удаленную память. Стои-мость посылки или приема сообщения в мультикомпьюте-ре зависит только от длины сообщения.Из множества существующих на практике парал-лельных компьютеров можно выделить три основныхархитектуры.Одна из них - это компьютеры с распределеннойпамятью, множеством потоков данных и множествомпотоков команд (distributed-memory MIMD) - их ещеназывают компьютерами с векторно-конвейерной об-работкой данных. Распределенная память (distributedmemoryMIMD) означает, что компьютер может вы-полнять отдельный поток инструкций над своими дан-ными, и каждый процессор имеет собственную локаль-ную память. Эта архитектура наиболее похожа на муль-тикомпьютер, различие в том, что стоимость посылкисообщений между процессорами в мультикомпьютерене зависит от расположения узлов в сети и других осо-бенностей сетевого трафика. Примерами таких системявляются IBM SP, Intel Paragon, Thinking Machines CM5,Cray T3D, Meiko CS-2 and nCUBE.Другую разновидность архитектуры параллельныхкомпьютеров называют многопроцессорным компьюте-ром или компьютером с общей памятью (shared-memoryMIMD). В многопроцессорных компьютерах все про-цессоры обладают доступом к одному общему адрес-ному пространству памяти обычно через шину или ие-рархию шин. Примерами таких систем являются SiliconGraphics Challenge, Sequent Symmetry и множество дру-гих многопроцессорных станций.Наиболее специализированный, третий класс парал-лельных компьютеров называют классом с одним потокомкоманд и множеством потоков данных (SIMD). В SIMDкомпьютерах, все процессоры выполняют один поток ко-манд над различными частями данных. MasPar MP являет-ся примером такого класса компьютерных комплексов.Следует оговориться, что еще два сорта компьютер-ных систем можно отнести к мультикомпьютерам, хотяна них накладываются дополнительные требования к безо-пасности и достоверности данных, и они имеют вы-сокую стоимость передачи сообщений между рабочимистанциями. Одни из них − это компьютеры, соединен-ные локальной сетью (LAN), а к другому сорту отно-сятся компьютерные системы, состоящие из компьюте-ров, которые географически значительно удалены исоединены глобальной сетью (WAN).Рис. 1. Методология проектированиядля параллельных программДля структуризации описания и для того, чтобы вмашинно-независимой форме оценить свойства про-ектируемых параллельных алгоритмов, предлагаются раз-личные модели (programming models - [3]). Они разли-чаются гибкостью, механизмами взаимодействия меж-ду задачами, степенью детализации задач, поддержкойлокальности, масштабируемостью и модульностью. Рас-смотрим некоторые из них.1. Модель программирования, основанная на задачахи каналах (task/channel programming model). Мы гово-рим о модели программирования, основанной на зада-чах и каналах, когда вычисления представлены множе-ством каналов и множеством задач. Задача инкапсули-рует программу и локальную память и определяет на-бор портов, которые формируют интерфейс этой зада-чи в модели. Канал представляет собой очередь сооб-щений, в которую задача-отправитель может помещатьсообщение и из которого задача-получатель может из-влекать сообщение или блокировать его, если сообще-ние недоступно. Модель программирования, основан-ная на задачах и каналах, упрощает программированиедля мультикомпьютеров за счет предоставлением абст-ракций, которые позволяют говорить о параллелизме,локальности и взаимосвязях в машинно-независимой фор-ме. Последнее обеспечивает основу для модульного кон-струирования параллельных программ.2. Другая модель программирования носит названиемодели передачи сообщений (message-passing programmingmodel). Она основана на передаче сообщений и,возможно, является наиболее широко используемой мо-делью параллельного программирования на сегодня.Программы, основанные на передаче сообщений, соз-дают множество задач, в каждой из которых инкапсу-лируются локальные данные. Каждая задача иденти-фицируется своим уникальным именем, и эти задачивзаимодействуют между собой посредством посылки иполучения сообщений. Обсуждаемая модель являетсянезначительной вариацией модели задач и каналов,отличаясь только механизмами передачи данных. На-пример, при посылке сообщения на «канал № 1», мыможем послать сообщение «задаче № 1».3. Информационный параллелизм (data parallelism programmingmodel) − еще одна модель программирования,отличительной особенностью которой является возмож-ность применения одной и той же операции к множествуэлементов структуры данных. Например, увеличить наединицу все элементы массива. Спроектированная про-грамма состоит из последовательности таких операций.4. Модели программирования с общей памятью (shared-memory programming model). В них задачи делят об-щее адресное пространство, из которого они читают и вкоторое они пишут данные асинхронно. Различные ме-ханизмы как, например, шлюзы и семафоры, могутбыть использованы для организации доступа к общейпамяти. Выгода этой модели заключается в том, чтоданные не имеют конкретных владельцев и, следова-тельно, нет необходимости определять механизмы пе-редачи данных между задачами. Эта модель может уп-ростить разработку программ. Однако понимание и уп-равление локальностью становиться более сложным.Большинство задач в программировании имеет не-сколько параллельных решений. Наилучшее решение мо-жет отличаться от предложенного используемыми после-довательными алгоритмами. Существует методология про-ектирования, предназначенная для разработки параллель-ных приложений. Эта методология разбивает процесс про-ектирования на четыре отдельных стадии: декомпозиция,коммуникация, агломерация и отображение [3].1. Декомпозиция. Вычисления, которые могут бытьвыполнены, и данные, которыми оперируют эти вы-числения, разделяются на меньшие (локальные) задачи.Внимание сосредотачивается на оценки возможностейдля параллельного исполнения.2. Коммуникация. Определяется координирование вы-полнения задачи и подходящие коммуникационныеструктуры и алгоритмы.3. Агломерация. Структуры задач и коммуникаций, оп-ределенные на первых двух стадиях проектирования, оце-ниваются в плане стоимости реализации и требований крабочим характеристикам. При необходимости локальныезадачи объединяются в большие, чтобы улучшить рабочиехарактеристики или уменьшить стоимость разработки.4. Отображение. Каждая задача назначается процессо-ру таким способом, чтобы удовлетворить конкурентнымтребованиям: максимизации загрузки процессоров и ми-нимизации стоимости коммуникаций. Отображение мо-жет быть определено статически или во время выполне-ния при помощи алгоритмов балансирования нагрузки.Очевидно, что рассмотренная методология проек-тирования параллельных программ и алгоритмов привсех ее выгодах, тем не менее, не вводит четко сфор-мулированного алгоритма действий для создания па-раллельных программ. При проектировании, основан-ном на этой методологии, чрезвычайно важное значе-ние приобретает квалификация разработчика. В сле-дующих разделах будет рассмотрены подходы к авто-матизации процесса проектирования параллельныхпрограмм.ПОДХОДЫ К АВТОМАТИЧЕСКОМУ СИНТЕЗУ ПРОГРАММНаправление автоматического синтеза программ на-чало формироваться достаточно давно в области искус-ственного интеллекта. Уже в середине 1960-х гг. поя-вились первые системы синтеза, основанные на прин-ципе резолюции.К проблеме автоматического синтеза программ су-ществует три основных подхода: дедуктивный, индук-тивный и трансформационный. При дедуктивном под-ходе задача синтеза трактуется следующим образом: позаданному значению x, удовлетворяющему условиюP(x), вычислить значение y, удовлетворяющему усло-вию Q(x,y). Здесь x и y - конечные множества, соответ-ственно, входных и выходных величин. Считается, чтоспецификация R=(P(x), Q(x, y)) содержит достаточноинформации для построения программы, которая реа-лизует вычисление значений выходных величин позначениям входных. Задача однозначно представляетсятройкой (x, y, R). Теорема существования решения за-дачи имеет вид: ∀x(P(x) ⊃ ∃yQ (x, y)). Построение ин-туиционистского доказательства теоремы существова-ния решения обеспечивает получение требуемой про-граммы. При таком подходе автоматическое построе-ние программ осуществимо для формализуемых пред-метных областей в тех случаях, когда разработка спе-цификации программы по тем или иным соображе-ниям проще разработки самой программы.Индуктивный подход к автоматическому синтезупрограмм характеризуется поиском общих закономер-ностей на основании анализа свойств некоторого рядаобъектов и, в определённом смысле, является моделиро-ванием метода обобщений, применяемого человеком.В противоположность индуктивному подходу, гдепроизводится переход от частного к общему, трансфор-мационный подход предполагает конкретизацию некойисходной спецификации общего вида. При этом, какправило, преследуется цель упрощения и/или повыше-ния эффективности работы результирующей програм-мы. Осуществляется это как за счёт знаний о предмет-ной области, для которой строится программа, так и наосновании традиционной техники оптимизации.Достаточно хорошо известны вычислительные моде-ли, предложенные Э.Х. Тыугу [1]. Они находят широкоеприменение при создании систем управления базами дан-ных, в пакетах прикладных программ с автоматическимсинтезом программ и в других аналогичных разработках.В этой работе под вычислительной моделью понимаютсясовокупность переменных и отношений над этими пере-менными. Отношения используются для вычисления зна-чений. Под отношениями понимаются связи функцио-нального вида, уравнения, зависимости и т.д. В таких мо-делях специальные машины вывода (без участия пользо-вателя) строят вычислительные структуры над перемен-ными для реализации поставленной задачи. Однако дан-ная задача без введения дополнительных условий являет-ся NP-полной и, следовательно, требует огромных вычис-лительных ресурсов. Поэтому работа [1] не могла бытьэффективно использована для практической реализациисистем синтеза программ на вычислительных моделях.Для снижения затрат на генерацию на вычислительныемодели накладываются дополнительные условия. Например,переменным и отношениям приписываются дополнитель-ные свойства [2], которые позволяют избежать избыточно-сти вывода. Некоторые свойства позволяют обеспечиватьсинтез ветвящихся и рекурсивных программ. Конкретизациявида связей также способствует повышению эффективностисинтеза (естественно, при этом несколько сужается и классрешаемых задач). Тем не менее, остается возможным созда-вать достаточно эффективные и практически полезные сис-темы автоматического синтеза линейных, ветвящихся и ре-курсивных программ. Синтезу параллельных программ врамках теории вычислительных моделей уделено мало вни-мания, хотя, повторяем, теория вычислительных моделейобладает хорошо разработанным и исследованным фор-мальным аппаратом и предоставляет возможности для реа-лизации весьма эффективных машин вывода.В последующих рассуждениях мы будем использо-вать аппарат теории, приведенный в [2]. Здесь на вычис-лительную модель накладываются следующие условия.Строго определен вид отношений, которые представля-ются в виде разрешенных уравнений f:a1,…, an→a0.Вычислительная модель в [2] называется структурнойС-моделью и представляет собой конечную совокуп-ность элементарных и неэлементарных структур, назы-ваемых схемами. Элементарная схема - это, на самомделе, конечное или счетное множество элементов (зна-чений элементов). Неэлементарная схема представляетсобой структуру следующего вида:T = (a00 : T00,…, a0N0 : T0N0,if p1→a10 : T10,…, a1N1

Скачать электронную версию публикации