Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.parallel.ru/sites/default/files/ftp/chg99/Voevodin.doc Дата изменения: Wed Nov 2 11:53:58 2011 Дата индексирования: Tue Oct 2 03:00:17 2012 Кодировка: koi8-r

В.В.Воеводин

Супервычисления и структура алгоритмов

Есть одна глобальная, трудно решаемая проблема, которая связывает пути
развития вычислительной техники и интересы пользователей такой техники. Это
- разработка принципов создания языков программирования, компиляторов и
всего того системного программного обеспечения, которое реально оказывает
влияние на эффективность решения пользовательских задач.
Какой бы сложной ни была вычислительная техника, она является всего лишь
инструментом решения прикладных задач. С момента зарождения ЭВМ и по
настоящее время основным посредником между вычислительной техникой и
пользователями являются языки программирования. Первоначальной целью их
создания было освобождение разработчиков алгоритмов от необходимости знать
особенности конкретных ЭВМ. Все функции по адаптации программ к конкретным
ЭВМ должны были взять на себя компиляторы и операционные системы.
Первоначальная цель не достигнута и трудно ожидать, что она будет
достигнута в ближайшем будущем. Анализ истории развития прикладного
программного обеспечения убедительно показывает: как только появляются
компьютеры нового поколения, прикладное программное обеспечение приходится
полностью или частично переделывать. Конечно, можно упрекнуть создателей
языков, компиляторов и операционных систем в недостаточном внимании к
интересам разработчиков алгоритмов. В таком упреке есть доля истины, так
как действительно интересы разработчиков алгоритмов постепенно затерялись
среди многих других интересов и перестали быть доминирующими. Однако надо
также признать, что проблемы разработчиков алгоритмов оказались совсем не
простыми.
Широкое внедрение идей параллелизма и конвейерности в вычислительную
технику привело к полному пересмотру всей концепции прикладного
программирования. В большом количестве стали возникать новые языки
"параллельного" программирования, "параллельные" компиляторы,
"параллельные" операционные системы и многое другое, в той или иной мере
"параллельное". Во всем этом обилии "параллельных" средств, якобы
предназначенных для помощи прикладным программистам, прослеживается четкая
тенденция: указание тех свойств алгоритмов и программ, которые в наибольшей
степени влияют на эффективность "параллельной" реализации и которые, в свою
очередь, обнаруживаются наиболее трудно, возлагается именно на прикладных
программистов.
Пока нет никаких оснований предполагать, что в обозримое время появятся
такие языки программирования, для которых будут даны гарантии, что
написанные на них программы будут реализовываться на будущих машинах
эффективно. Это верно даже для современных параллельных машин, архитектура
которых в целом вполне понятна. А ведь, возможно, не так далеко до
появления квантовых и других компьютеров нового типа, для которых совсем не
ясно, какими будут принципы программирования.
По-видимому, надо принять за истину, что еще очень долго забота об
эффективности реализации прикладных программ будет лежать на прикладных
программистах. И не следует ожидать, что системные программисты сами по
себе предложат для повышения эффективности пользовательских программ
достаточно разумные средства. Для их разработки у них нет ни стимулов, ни
соответствующих знаний.
Полезно более внимательно посмотреть на причины возникновения трудностей
переделки программ при переходе от последовательных машин к параллельным.
Несмотря на длительный период развития вычислительной математики вообще и
численных методов и алгоритмов в частности, математики очень мало знают о
том, как в действительности устроены разрабатываемые и используемые ими
методы и алгоритмы. Господствовавшая в течение нескольких десятилетий
концепция однопроцессорных ЭВМ обращала внимание разработчиков на две
характеристики, связанные с вычислительной техникой, - это общее число
операций о объем требуемой памяти. Что же касается структурных свойств
алгоритмов, например, таких как модульность, то их изучение так и не вышло
из зачаточного состояния. Все это в конечном счете привело к тому, что к
моменту широкого внедрения параллельных вычислительных систем в практику
решения больших задач вычислительная математика оказалась без нужного
багажа знаний, касающихся структуры алгоритмов. Без нужного багажа знаний
оказались и смежные науки, в частности, связанные с разработкой
алгоритмических языков, компиляторов и архитектуры вычислительных систем.
В связи со сказанным, интересно отметить следующее обстоятельство. Когда
стало ясно, что машины параллельной архитектуры входят в широкую практику,
появилось большое число новых численных методов. Эти методы касались разных
областей и позволяли теоретически решать задачи за лучшее "параллельное"
время. Но очень скоро выяснилось, что новые методы на практике далеко не
всегда эффективны. Как правило, по сравнению с традиционными методами они
либо обладали численной неустойчивостью, либо имели очень сложную
структуру, приводящую к громоздким программам и, как следствие, к потере
реальной эффективности. В результате на параллельных машинах используется,
главным образом, старые, хорошо исследованные и многократно апробированные
методы, но реструктурированные специальным образом.
Реструктуризация алгоритмов на уровне отдельных операций - это основная
идея, которая эксплуатируется самым активным образом в настоящее время при
согласовании свойств программ и компьютеров с целью добиться максимальной
реальной производительности. Другой аналогичной по эффективности идеи, на
наш взгляд, пока нет и не предвидится.
Чтобы описать структуру алгоритмов на уровне отдельных операций,
необходимо каждой операции приписать какие-то координаты и указать в этих
координатах зависимость операций между собой. Тем самым строится некоторый
ориентированный граф, обобщенно называемый графом зависимостей. В
зависимости от того, как выбираются координаты операций, как
устанавливаются зависимости и как по графу зависимостей решаются нужные
задачи, зависит успех или неуспех использования сведений о структуре
алгоритма.
Общепризнанно приписывать координаты операциям через введение так
называемого пространства итераций [1]. Общепризнанно также для установления
зависимостей использовать понятие зависимых операций [1]. Напомним, что две
операции называются зависимыми, если при их выполнении происходит обращение
к одной и той же переменной. В зависимости от того, происходит при
выполнении отдельной операции использование значения переменной или ее
пересчет, различают четыре типа зависимостей. Традиционно используют графы
зависимостей, в которых связаны дугой любые две зависимые операции.
Традиционные графы зависимостей устроены очень сложно. В каждую вершину
входит очень большое число дуг, зависящее, к тому же, от значений внешних
переменных программы. Поэтому для таких графов трудно получить приемлемое
аналитическое представление и, следовательно, с ними трудно решать сложные
содержательные задачи. Несмотря на длительный период использования
традиционных графов зависимостей, их применение не вышло, в основном, за
рамки разработки различных достаточных критериев независимости операций.
Достаточные критерии грубы и не дают возможность решать нужные задачи.
Более 10 лет назад мы ввели и до сих пор успешно используем для изучения
структуры алгоритмов на уровне отдельных операций другие графы. Это так
называемые минимальные графы зависимостей [1]. Они являются подграфами
традиционных графов зависимостей, но отличаются от них принципиально.
Именно, в каждую вершину любого из таких графов входит лишь конечное число
дуг и это число не зависит от значений внешних переменных программы. Для
минимальных графов зависимостей получено их представление в виде конечного
набора простейших функций. В свою очередь, это представление позволило
решить широкий спектр задач, связанный со знанием структуры алгоритмов.
Перечислим некоторые из задач, которые удалось решить с помощью
минимальных графов зависимостей, и задач, которые, как оказалось, имеют с
минимальными графами очень тесную связь:
. определение параллельной структуры алгоритмов и программ на уровне
отдельных операций;
. расчленение алгоритмов на крупные, параллельно исполняемые фрагменты;
. восстановление по программе исходных математических формул;
. оптимизация использования внешней памяти;
. оценивание параллельной сложности алгоритмов и программ;
. быстрое вычисление градиента сложных функций;
. исследование влияния ошибок округления;
. построение математических моделей систолических массивов;
. разработка портабельных библиотек программ;
. и многое другое

Конечно, многие вопросы структуры алгоритмов и программ еще ждут своего
решения. Но мы хотим настоятельно обратить внимание на то, что
сопровождение каждой программы детальным описанием структуры реализуемого
ею алгоритма на уровне отдельных операций и разработка общих методов
использования таких описаний, возможно, является самым надежным гарантом от
огромных малопроизводительных затрат по переделке программного обеспечения
под требования новых компьютеров.
Для широкого класса алгоритмов и программ получение описания структуры и
ее использование можно автоматизировать. Успешный опыт в этом направлении
демонстрирует использование V-Ray system, разработанной в Научно-
исследовательском вычислительном центре МГУ (http://parallel.srcc.msu.su/v-
ray/). Но данный опыт говорит и о том, что необходима жесткая дисциплина
программирования. Альтернативы наведению порядка в написании программ нет.

1. В.В.Воеводин. Информационная структура алгоритмов. М., Изд-во МГУ,
1997 г.