ЗАДАЧИ РАСПАРАЛЛЕЛИВАНИЯ И ИХ АКТУАЛЬНОСТЬ

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

Мультиобработка информации, архитектура мультипроцес­сорных систем, место и масштабы «ручного» и автоматическо­го распараллеливания, языковые средства и методы распаралле­ливания и другие вопросы все больше и больше интересуют раз­работчиков и пользователей [2]. С одной стороны, естествен­ный параллелизм реальных процессов является предпосылкой для разработки параллельных алгоритмов и языков их описа­ния, то есть ручного распараллеливания. С другой стороны, пос­ледовательный характер мышления человека, многолетний опыт последовательной алгоритмизации и программирования дела­ют предпочтительным автоматическое распараллеливание. Мас­штабы использования вычислительной техники, сложность про­изводственных, технических, народнохозяйственных, природных и других объектов, моделирование которых требует наличия мощных многопроцессорных вычислительных систем и сетей ЭВМ, являются еще одним важным доводом в пользу автомати­ческого распараллеливания и реализации управления мульти­обработкой на уровне операционных систем.

Следует отметить, что в связи с повышением мощности и надежности элементной базы возросли возможности параллель­ного выполнения (а, следовательно, и потребности распаралле­ливания) на различных операционных уровнях. Важное место в этой проблематике занимают теоретические вопросы, включа­ющие выбор модели распараллеливания, определение эквива­лентности программ, определение степени параллелизма и син­хронизация параллельных процессов, анализ потенциального параллелизма алгоритмов и программ, определение максималь­ного параллелизма и др.

Нередко практические потребности могут быть удовлет­ворены системами распараллеливания, которые хотя и не обес­печивают максимального параллелизма, но позволяют в рамках приемлемой модели и соответствующего определения эквива­лентности получать практически достаточно приемлемые па­раллельные программы. Такие системы, основываясь, как пра­вило, на крупноблочном распараллеливании, значительно уп­рощают функции системы, освобождая ее от микрораспаралле­ливания, частой синхронизации, обмена и тех функций, кото­рые связаны с анализом входной и синтезом выходной программ при мелкоблочном распараллеливании. Кроме того, имеются алгоритмы микрораспараллеливания, схемная (либо программ­но-схемная) реализация которых предпочтительна.

Создание ПВС вызвало необходимость решения возника­ющей при этом проблемы параллельного программирования, одной из важнейших составных частей которой является задача десеквенции - т.е. распараллеливания алгоритмов, программ или непосредственно вычислений. Первоначально под распаралле­ливанием понималось преобразование последовательной про­граммы в эквивалентную параллельную, обрабатываемую од­новременно на нескольких процессорах. В настоящее время этот термин определяет комплексную процедуру «подгонки» алго­ритма, программы или даже вычислительного метода к архи­тектуре конкретного или гипотетического вычислительного ком­плекса.

Общая проблема «подгонки» структуры программы под архитектуру ЭВМ не является новой. Известны различные ме­тоды структуризации программ в целях оптимального исполь­зования памяти, быстродействующих регистров, каналов связи, устройств ввода-вывода и т.д. Специфика обработки, связанная с многопроцессорностью, также оказала влияние эту проблему. Разные типы архитектур обусловили разные грани постановки задачи распараллеливания. Так, для конвейерных ЭВМ актуаль­ной стала задача векторизации, поскольку на настройку и раз­гон конвейера, реализующего данную операцию, тратится до­вольно большое время. Поэтому наиболее эффективно на кон­вейерных ЭВМ реализуются программы, состоящие из длин­ных серий однотипных операций и как можно меньшего числа одиночных операций и коротких серий. Векторизацией называ­ется преобразование программы в эквивалентную ей, произво­дящую обработку максимально длинными сериями однотипных операций, т. е. требующую минимального числа запусков кон­вейера. Задача векторизации может быть решена либо сборкой частей программы в новом порядке, либо распараллеливанием ее повторяющихся участков. Это приводит к образованию «вер­тикальных» серий однотипных операций, которые, в частности, могут быть выполнены и «горизонтально» в конвейере. Это лишьодин пример преобразования программ, который можно трак­товать как частный случай распараллеливания.

Характерными особенностями современных методов рас­параллеливания являются следующие:

■ распараллеливание может производиться в динамичес­ком режиме, т.е. независимые вычислительные акты могут вы­являться в процессе вычисления и назначаться на обработку по мере освобождения требуемого оборудования;

■ допускается наличие не только последовательных, но и параллельных входных программ, и может оказаться, что про­цедура распараллеливания производит не распараллеливание, а, наоборот, свертку излишне коротких параллельных ветвей;

■ результирующая программа должна обладать наилучши­ми в каком-то определенном смысле характеристиками.

Преобразование распараллеливания, как правило, произво­дится в два этапа. На первом этапе «вскрывается» и фиксируется в каком-либо машинно-независимом виде параллелизм алгорит­ма или задачи, а на втором выполняется генерация программы с параллельной структурой, адекватной архитектуре реализующей ЭВМ. На любом из этих этапов можно использовать два подхода: универсальный и специальный. При специальном подходе имеют дело с известным классом задач, фиксированными языками про­граммирования, характерными для них структурами программ и конкретным вычислительным комплексом. При универсальном подходе предполагается, что исходная программа может быть из любой предметной области и может иметь произвольную струк­туру. Задача распараллеливания ставится как задача разработки распараллеливателя или десеквентора - специальной программы (алгоритма), выполняющей автоматическое преобразование пос­ледовательной программы в эквивалентную параллельную. При этом в процессе выявления параллелизма и распараллеливания почти не используются интерпретация и семантика операций. Вычислительные средства классифицируют также довольно гру­бо, выделяя лишь их типы или схемы архитектуры ЭВМ. Таким образом, при универсальном подходе обнаруживаются наиболее устойчивые закономерности и разрабатываются наиболее общие методы распараллеливания.

Анализ проблематики универсального распараллелив-аниявыявил несколько обобщающих особенностей этого направле­ния исследований:

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

2. При рассмотрении всего многообразия методов оказалось возможным выделить своего рода двойственные постановки за­дачи распараллеливания. Особенно отчетливо прослеживается двойственность императивного и регламентирующего контро­ля над вычислением. Первый тип контроля исходит из того, что первоначально запрещается выполнение всех вычислительных актов и для инициации какого-либо действия нужно дать указа­ние об его выполнении. Второй тип контроля применяется к сре­де вычислителей, осуществляющих свободное хаотическое фун­кционирование, и заключается в запрещении выполнения каких-либо актов. Оказалось, что первый и второй механизмы контроля внутренне весьма схожи и могут быть построены и обоснованы с помощью одного и того же математического аппарата. Конкрет­ным проявлением этого типа двойственности можно считать вза­имную зависимость и независимость операторов при распарал­леливании массовых вычислений. Помимо того, что трактовка формализмов как двойственных друг другу помогает лучше по­нять природу вещей, это дает еще и определенную техническую выгоду: конструкции и доказательства утверждений о них пере­носятся из одной области в другую почти автоматически.

3. Обнаружилось, что в наиболее «чистых» постановках задача распараллеливания оказалась во многих случаях принци­пиально разрешимой. Речь идет о задаче максимального распа­раллеливания, в которой требуется построить программу, до­пускающую все возможные вычисления, не нарушающие экви­валентность исходной схеме. Так, один из результатов можно интерпретировать как возможность организации «абсолютно бы­стрых вычислений», т.е. без учета особенностей интерпретации быстрее осуществлять все необходимые вычисления в принци­пе нельзя.

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