В связи с тем, что разработка параллельного программного обеспечения на сегодняшний день представляется достаточно сложной задачей, крайнюю актуальность приобретают вопросы теоретической подготовки специалистов и изучение методологии проектирования таких систем. В рамках статьи приведена историческая и техническая информация, подготавливающая программиста к усвоению знаний в области разработки параллельных вычислительных систем.
Данный документ является частью серии статей, посвященных вопросам создания качественных и эффективных программных решений для современных 64-битных многоядерных систем. Ознакомиться с другими статьями вы можете на сайте http://www.viva64.com.
Программистам, начинающим использовать многопроцессорные ЭВМ, очень трудно сориентироваться во всех тонкостях их использования при разработке программ по прикладным задачам. Как показывает практика, трудности начинаются, когда к разрабатываемому параллельному программному обеспечению предъявляется требование его эффективности и мобильности. Это связано с тем, что универсальные средства, облегчающие труд программиста и обеспечивающие полноценный доступ к отладочной информации, находятся в стадии разработки. Проблема заключается в отсутствии стандартов в области создания и отладки программ для параллельных систем, по причине молодости компьютерной отрасли. Соответственно на настоящий момент отсутствуют логически завершенные учебные курсы по параллельному программированию для начинающих.
Развитие многопроцессорной вычислительной техники неразрывно связано с разработкой технологий параллельного программирования - как универсальных, так и под конкретную архитектуру ЭВМ. Под технологией программирования, то есть под организацией работы с памятью, подразумевается использование средств управления конкретной вычислительной техникой.
Необходимо отметить, что при составлении программных средств под суперЭВМ (как средств управления, так и средств для решения прикладных задач) особое внимание следует уделять технике программирования, то есть построению логической архитектуры программы. Здесь подразумевается развитие и дополнение алгоритмов распараллеливания, повышающих эффективность их выполнения на многопроцессорных ЭВМ.
Прошло немногим более 50 лет с момента появления первых электронных вычислительных машин - компьютеров. За это время сфера их применения охватила практически все области человеческой деятельности. Сегодня невозможно представить себе эффективную организацию работы без применения компьютеров в таких областях, как планирование и управление производством, проектирование и разработка сложных технических устройств, издательская деятельность, образование - словом, во всех областях, где необходима обработка больших объемов информации. Такие задачи возникли в середине прошлого века в связи с развитием атомной энергетики, авиастроения, ракетно-космических технологий и ряда других областей науки и техники [1].
В наше время круг задач, требующих для своего решения применения мощных вычислительных ресурсов, еще более расширился. Это связано с тем, что произошли фундаментальные изменения в самой организации научных исследований. Вследствие широкого внедрения вычислительной техники, значительно усилилось направление численного моделирования и численного эксперимента [2]. Численное моделирование, заполняя промежуток между физическими экспериментами и аналитическими подходами, позволило изучать явления, которые являются либо слишком сложными для исследования аналитическими методами, либо слишком дорогостоящими или опасными для экспериментального изучения. При этом численный эксперимент позволил значительно удешевить процесс научного и технологического поиска. Стало возможным моделировать в реальном времени процессы интенсивных физико-химических и ядерных реакций, глобальные атмосферные процессы, процессы экономического и промышленного развития регионов и т.д. Очевидно, что решение таких масштабных задач требует значительных вычислительных ресурсов.
Вычислительное направление применения компьютеров всегда оставалось основным двигателем прогресса в компьютерных технологиях. Не удивительно поэтому, что в качестве основной характеристики компьютеров используется такой показатель, как производительность - величина, показывающая, какое количество арифметических операций он может выполнить за единицу времени. Именно этот показатель с наибольшей очевидностью демонстрирует масштабы прогресса, достигнутого в компьютерных технологиях. Так, например, производительность одного из самых первых компьютеров EDSAC составляла всего около 100 операций в секунду, тогда как пиковая производительность Earth Simulator, одного из самых мощных на сегодняшний день суперкомпьютеров, оценивается в 40 триллионов операций в секунду. Т.е. произошло увеличение быстродействия в 400 миллиардов раз! Невозможно назвать другую сферу человеческой деятельности, где прогресс был бы столь очевиден и так велик. Естественно, что у любого человека сразу же возникает вопрос: за счет чего это оказалось возможным? Как ни странно, ответ довольно прост: примерно 1000-кратное увеличение скорости работы электронных схем и максимально широкое распараллеливание обработки данных.
Идея параллельной обработки данных как мощного резерва увеличения производительности вычислительных аппаратов была высказана Чарльзом Бэббиджем примерно за сто лет до появления первого электронного компьютера. Однако уровень развития технологий середины 19-го века не позволил ему реализовать эту идею. С появлением первых электронных компьютеров эти идеи неоднократно становились отправной точкой при разработке самых передовых и производительных вычислительных систем [3]. Без преувеличения можно сказать, что вся история развития высокопроизводительных вычислительных систем - это история реализации идей параллельной обработки на том или ином этапе развития компьютерных технологий, естественно, в сочетании с увеличением скорости и надежности работы электронных схем.
Принципиально важными решениями в повышении производительности вычислительных систем были: введение конвейерной организации выполнения команд; включение в систему команд векторных операций, позволяющих одной командой обрабатывать целые массивы данных; распределение вычислений на множество процессоров. Сочетание этих 3-х механизмов в архитектуре суперкомпьютера Earth Simulator, состоящего из 5120 векторно-конвейерных процессоров, и позволило ему достичь рекордной производительности, которая в 20000 раз превышает производительность современных персональных компьютеров.
Очевидно, что такие системы чрезвычайно дороги и изготавливаются в единичных экземплярах [4]. Ну, а что же производится сегодня в промышленных масштабах? Широкое разнообразие производимых в мире компьютеров с большой степенью условности можно разделить на четыре класса: персональные компьютеры (Personal Computer - PC); рабочие станции (WorkStation - WS); суперкомпьютеры (Supercomputer - SC); кластерные системы [5].
Условность разделения связана в первую очередь с быстрым прогрессом в развитии микроэлектронных технологий. Производительность компьютеров в каждом из классов удваивается в последние годы примерно за 18 месяцев (в соответствии с так называемым законом Мура). В связи с этим, суперкомпьютеры начала 90-х годов зачастую уступают в производительности современным рабочим станциям, а персональные компьютеры начинают успешно конкурировать по производительности с рабочими станциями. Тем не менее, попытаемся каким-то образом классифицировать их.
Персональные компьютеры. Как правило, в этом случае подразумеваются однопроцессорные системы на платформе Intel или AMD, работающие под управлением однопользовательских операционных систем (Microsoft Windows и др.). Используются в основном как персональные рабочие места.
Рабочие станции. Это чаще всего компьютеры с RISC процессорами с многопользовательскими операционными системами, относящимися к семейству ОС UNIX. Содержат от одного до четырех процессоров. Поддерживают удаленный доступ [6]. Могут обслуживать вычислительные потребности небольшой группы пользователей.
Суперкомпьютеры. Отличительной особенностью суперкомпьютеров является то, что это, как правило, большие и, соответственно, чрезвычайно дорогие многопроцессорные системы. В большинстве случаев в суперкомпьютерах используются те же серийно выпускаемые процессоры, что и в рабочих станциях. Поэтому зачастую различие между ними не столько качественное, сколько количественное. Например, можно говорить о 4-х процессорной рабочей станции фирмы SUN и о 64-х процессорном суперкомпьютере фирмы SUN. Скорее всего, в том и другом случае будут использоваться одни и те же микропроцессоры.
Кластерные системы. В последние годы широко используются во всем мире как дешевая альтернатива суперкомпьютерам. Система требуемой производительности собирается из готовых серийно выпускаемых компьютеров, объединенных опять же с помощью некоторого серийно выпускаемого коммуникационного оборудования. Таким образом, многопроцессорные системы, которые ранее ассоциировались в основном с суперкомпьютерами, в настоящее время прочно утвердились во всем диапазоне производимых вычислительных систем, начиная от персональных компьютеров и заканчивая суперкомпьютерами на базе векторно-конвейерных процессоров. Это обстоятельство, с одной стороны, увеличивает доступность суперкомпьютерных технологий, а с другой, повышает актуальность их освоения, поскольку для всех типов многопроцессорных систем требуется использование специальных технологий программирования для того, чтобы программа могла в полной мере использовать ресурсы высокопроизводительной вычислительной системы [7, 8]. Обычно это достигается разделением программы с помощью того или иного механизма на параллельные ветви, каждая из которых выполняется на отдельном процессоре.
Суперкомпьютеры разрабатываются в первую очередь для того, чтобы с их помощью решать сложные задачи, требующие огромных объемов вычислений. При этом подразумевается, что может быть создана единая программа, для выполнения которой будут задействованы все ресурсы суперкомпьютера. Однако не всегда такая единая программа может быть создана или ее создание целесообразно. В самом деле, при разработке параллельной программы для многопроцессорной системы мало разбить программу на параллельные ветви. Для эффективного использования ресурсов необходимо обеспечить равномерную загрузку всех процессоров, что в свою очередь означает, что все ветви программы должны выполнить примерно одинаковый объем вычислительной работы. Однако не всегда этого можно достичь. Например, при решении некоторой параметрической задачи для разных значений параметров, время поиска решения может значительно различаться. В таких случаях, видимо, разумнее независимо выполнять расчеты для каждого параметра с помощью обычной однопроцессорной программы [9]. Но даже в таком простом случае могут потребоваться суперкомпьютерные ресурсы, поскольку выполнение полного расчета на однопроцессорной системе может потребовать слишком длительного времени. Параллельное выполнение множества программ для различных значений параметров позволяет существенно ускорить решение задачи. Наконец, следует отметить, что использование суперкомпьютеров всегда более эффективно для обслуживания вычислительных потребностей большой группы пользователей, чем использование эквивалентного количества однопроцессорных рабочих станций, так как в этом случае с помощью некоторой системы управления заданиями легче обеспечить равномерную и более эффективную загрузку вычислительных ресурсов.
В отличие от обычных многопользовательских систем, для достижения максимальной скорости выполнения программ операционные системы суперкомпьютеров, как правило, не позволяют разделять ресурсы одного процессора между разными, одновременно выполняющимися программами. Поэтому, как два противоположных варианта, возможны следующие режимы использования n-процессорной системы:
При решении широкого круга задач математической физики на многопроцессорных системах с помощью сеточных методов [10], широко используются два подхода для построения параллельных программ. Первый получил название метода геометрического параллелизма, второй - метод коллективного решения [11]. Идеи, положенные в основу этих методов, отличает простота и элегантность. Не будет преувеличением утверждение, что подавляющее большинство решаемых в настоящее время с помощью методов конечных разностей или конечных элементов задач газовой динамики, микроэлектроники, экологии, и многих других эффективно решаются именно методом геометрического параллелизма. Методом коллективного решения целесообразно пользоваться при построении параллельных алгоритмов решения задач методами Монте-Карло, при проведении серий однотипных расчетов и в ряде других случаев.
Отметим, что метод геометрического параллелизма является методом статической балансировки загрузки, заранее определяя обрабатываемую каждым процессором часть сетки. Статическая балансировка эффективна при условии, что априорной информации достаточно для предварительного распределения общей вычислительной нагрузки поровну между процессорными узлами. Метод коллективного решения является методом динамической балансировки загрузки. В его рамках перед началом вычислений не известно, какие именно узлы сетки будут обработаны тем или иным процессором. Процессоры получают задания динамически, по мере выполнения уже поступивших, что обеспечивает равномерную загрузку процессорных узлов при наличии большого набора независимых заданий.
Параллелизм типа "коллективного решения" удобен при проведении вычислений, распадающихся на большое количество однотипных задач, каждая из которых решается независимо от остальных. Передачи данных между такими задачами нет, а значит, полностью отсутствует необходимость их взаимной синхронизации.
Рассмотрим в качестве примера разностную сетку как набор независимых узлов, в каждом из которых следует определять ряд параметров на каждом временном слое с помощью решения системы ОДУ с соответствующими начальными данными [12]. Решение системы в каждом узле зависит только от локальных значений переменных в этом узле. При этом вычислительная нагрузка в различных узлах значительно отличается. При построении параллельной программы с помощью классического метода "коллективного решения" используется следующая стратегия распределения вычислительной нагрузки.
Выделяется один управляющий процессор, все остальные используются в качестве обрабатывающих узлов, то есть счетных. Каждый обрабатывающий процессор выполняет элементарные задания - решение системы ОДУ для очередного узла сетки с соответствующими локальными параметрами. На управляющий процессор возлагаются функции распределения элементарных заданий по обрабатывающим процессорам и сбора полученных результатов.
В начале очередного шага каждый из процессоров ожидает новую порцию данных, обрабатывает ее, возвращает результат и снова переходит к ожиданию очередного задания, пока не получит в ответ вместо задания сообщение, что все узлы сетки уже обработаны.
Отсутствие необходимости выполнения синхронизации между элементарными задачами позволяет передавать разным процессорам разное количество расчетных узлов по мере окончания обработки данных. Тем самым решается проблема равномерной загрузки процессоров, даже если время решения системы уравнений для разных узлов сетки или производительность процессоров сильно отличается.
В случае неоднородной вычислительной нагрузки при расчете разных узлов пространственной сетки использование принципа "коллективного решения" потенциально позволяет значительно снизить время простоя и повысить эффективность распараллеливания по сравнению с рассмотренным далее методом геометрического параллелизма. Преимущества этого метода в полной мере могут быть реализованы, если данные для обработки изначально сосредоточены на одном из процессоров, который в этом случае может выполнять управляющие функции. При исходных данных, изначально распределенных между процессорами случайным образом, использование метода требует предварительного сбора данных, соответствующих всем расчетным точкам, на одном из процессоров. Необходимость предварительного копирования данных со всех процессоров на один и последующего возврата результатов с этого одного процессора процессорам-"владельцам" точек в значительной мере снижают эффективность данного метода, что делает его мало пригодным для практического применения при решении многих задач численного моделирования.
Исходную задачу мы можем разбить на группу областей, независимых друг от друга на каждом расчетном шаге и пересекающихся только по границе разбиения. Т.е. мы рассчитываем (n+1)-м временной слой в каждой области, затем согласуем границы и переходим к расчету следующего слоя.
Однако, при таком подходе, когда мы делим расчетную область на непересекающиеся подобласти, у нас возникают проблемы с пересчетом значений на границах между данными областями, поэтому предлагается следующий достаточно логичный шаг, - делить исходную область на взаимно перекрывающиеся подобласти.
Появятся по две "фиктивные" точки слева для первой области и справа для последней области. Таким образом, мы получаем четыре независимых на каждом шаге по времени процесса. Для перехода к следующей итерации необходимо согласование границ, так как первая область должна передать второй ее левую границу для следующего шага по времени, в свою очередь, вторая область должна предать первой ее правую границу, и т.д.
Данная методика может быть обобщена на большинство численных методов, основанных на уравнениях для моделирования физических процессов.
Применение суперЭВМ налагает особые требования на вновь создаваемые программные средства, обеспечивающие надежную и экономичную реализацию алгоритма при решении прикладных задач. Эффективность использования суперЭВМ проявляется при создании сложных исследовательских комплексов и экспертных систем.
Написать эффективную параллельную программу намного труднее, чем последовательную. Создание программного обеспечения для параллельных компьютеров - это центральная проблема суперкомпьютерных вычислений [13].
Частично проблема выбора оптимального числа параллельных ветвей в соответствии с критерием минимума суммарных затрат времени может быть решена в автоматах генерации параллельной программы. Частный случай разрешения этой проблемы для вычислительных систем с MIMD архитектурой рассмотрен в статье Костенко В.А. "К вопросу об оценке оптимальной степени параллелизма" [14].
Эффективность использования многопроцессорных вычислительных систем в значительной мере определяется качеством прикладных параллельных программ. Программа считается эффективной, когда во время ее выполнения загружены все процессоры, выделенные под процессы. Но практически это не реализуемо.
Отметим, что идеальная параллельная программа обладает следующими свойствами:
Увеличение степени эффективности параллелизма (уменьшение временных затрат на накладные расходы) достигается следующими способами:
Основные этапы самого процесса адаптации программ к архитектуре параллельных компьютеров, а также описание задач, возникающих на каждом из этих этапов, представлены в статье Антонова А.С. "Эффективная адаптация последовательных программ для современных векторно-конвеерных и массивно- параллельных супер-ЭВМ" [15]. На некоторые из задач, с которыми столкнулись авторы проведенного исследования, хотелось бы обратить особое внимание. Среди них:
Отметим, что решение этих задач позволяет осуществить эффективный перенос последовательной программы на параллельную архитектуру.
Процесс разработки параллельной программы очень длителен и трудоемок, не смотря на то, что, как правило, на момент ее создания уже имеется реализация ее "последовательного" аналога. Обычно программа разрабатывается на машине с одной архитектурой, а ее практическое применение производится на другой, с отличной от первой топологией, но при этом более мощной. Такой подход позволяет экономить машинное время на более мощных суперЭВМ, число которых на порядок меньше, по сравнению с более дешевыми моделями суперкомпьютеров.
При переносе параллельной программы на машины с различной архитектурой перед программистом встает проблема неработоспособности однажды разработанных параллельных процедур.
На сегодняшний день не существует универсальных средств адаптации программ к конкретной архитектуре суперЭВМ, поэтому большую часть этой проблемы приходится решать вручную, что делает процесс очень трудоемким [15]. Для облегчения труда программиста в математических институтах РАН разрабатываются библиотеки эффективных процедур и алгоритмов под конкретные архитектуры суперЭВМ (УРО РАН, НИВЦ МГУ им. М.В.Ломоносова). Обращение к этим библиотекам может частично облегчить труд программиста-прикладника не только на этапе модификации программы под более мощные суперЭВМ, но и на этапе первичной разработки параллельной программы.
Проблема отладки и мониторинга очень актуальна, ввиду отсутствия менеджеров, которые предоставляли бы разработчику прикладного ПО промежуточную информацию, особенно актуальную на начальном этапе проектирования [16]. Ситуация становится еще сложнее, если речь идет об управлении распределенными разнородными системами. В общем случае задача отладки и мониторинга таких систем ставится следующим образом [17, 18]. Имеется сеть разнородных по аппаратным и/или программным платформам узлов, на каждом из которых параллельно выполняется множество процессов (нитей) [19]. Имеется также совокупность пользователей, каждый из которых желает отслеживать и/или воздействовать на свое подмножество программных и/или аппаратных компонентов.
Трактовка отладки/мониторинга как контролируемого выполнения меняет место отладки в жизненном цикле систем, позволяет применить архитектурные и протокольные решения, характерные для средств управления. Это делает средства отладки масштабируемыми, способными обслуживать распределенные разнородные системы.
Для дальнейшего развития средств отладки/мониторинга важно формирование набора спецификаций, определяющих функциональность разрабатываемых программ-менеджеров [20].
Программы представляют собой сложные динамические системы. Особенно это относится к параллельным и интерактивным программам (работающим в диалоговом режиме), которые включают в себя сложные взаимодействия между процессами программы и взаимодействие с внешним миром. Исследование таких программ нельзя проводить в терминах отношений между входными и выходными значениями программы, как это обычно делается для последовательных программ. Это показывает, что проверка и доказательство правильности работы таких программ требует разработки адекватных средств формальной спецификации. В частности, необходимо иметь возможность формально выражать отношения между состояниями системы в моменты времени, когда происходят те или иные события при работе программной системы. В статье Валиева М.К. "Применение временной логики к спецификации программ" [21] обсуждается подход к анализу параллельной программы, основанный на применении методов математической логики.
Функция управления процессами является одной из важнейших задач операционной системы. Для выполнения этой задачи на суперЭВМ может использоваться технология семафоров [22], которая заключается в блокировке и разблокировке процессов.
Семафоры традиционно использовались для синхронизации процессов, обращающихся к разделяемым данным. Каждый процесс должен исключать для всех других процессов возможность одновременного обращения к своим данным.
При решении прикладных задач, в большинстве случаев, объем получаемой информации настолько велик, что исключается возможность верификации - детального анализа данных, получаемых непосредственно вычислительной программой. Поскольку для таких ситуаций не существует универсальных графических пакетов с визуализацией различных изометрических проекций и цветовых гамм, разработчикам прикладного программного обеспечения рекомендуется их дополнительная разработка.
Разрабатываемые подходы использования компьютеров основаны на тезисе: компьютер - это инструмент познания, при помощи которого добывают новую информацию об исследуемом объекте или явлении [23]. Следовательно, квалифицированный пользователь должен владеть современной методологией познания - моделированием. Моделирование - это не только конструирование объекта познания, но и метод познания. Моделирование есть методология работы, эффективность которой раскрывается лишь при высокой квалификации специалистов и при их свободном владении современными средствами формализации - логикой и математикой.
Сформулировав задачу и обозначив конечную цель, исследователь включается в поиск решения. Одним из путей его нахождения является моделирование. Пройденный путь становится методом.
Процесс моделирования предполагает как движение "от предмета к модели" (отражение действительности в системе понятий), так и движение "от модели к предмету" (испытание истинности модели на ее возможностях). Компьютер является естественным средством проведения такого рода "исследовательских" циклов.
Специалисты по теории разработки программного обеспечения при описании процесса его создания весьма редко уделяют внимание моделированию. С другой стороны специалисты по моделированию обосновывают настоятельную необходимость широкого использования своих методов при проектировании любых сложных систем [24]. Так как программный комплекс является сложной системой с большим количеством уровней и компонентов, а также со сложной структурой связей между ними, то при разработке таких систем необходимо применять моделирование.
Принимая во внимание, что разработка параллельного программного обеспечения (объекта распараллеливания) на сегодняшний день представляется достаточно сложной, проблема создания теоретических основ его проектирования стоит еще более остро. Кроме анализа структуры и свойств разрабатываемых программ на всех этапах проектирования моделирование может позволить описать все особенности взаимодействия параллельных процессов на уровне имитационной модели. В работе Маркова Н.Г. "Моделирование параллельного программного обеспечения с использованием PS-сетей" [25], на основании требований, предъявляемых к параллельному программному обеспечению, предлагается использование графоаналитического подхода к имитационному моделированию проекта программы. Целью упомянутой работы явилась выработка требований к аппарату имитационного моделирования параллельного программного обеспечения, а также создание аппарата, сохраняющего баланс между математической простотой и строгостью - с одной стороны, и практической применимостью - с другой.
Таким образом, можно констатировать, что наиболее удобным средством анализа вычислительных алгоритмов параллельных вычислений являются графы [26].
Проблема создания современных пакетов прикладных программ, ориентированных на широкий класс задач механики, выходит далеко за рамки синтеза этих задач из отдельных программных модулей. Она связана с глобальной оптимизацией всей вычислительной последовательности задач [27]. Поэтому пакет программ, как продукт, используемый в научно-прикладных целях не только самими создателями, но и конечными пользователями, должен производиться на качественно новом уровне программирования. При разработке современного программного обеспечения необходимо не только учитывать нелинейные (с обратным влиянием) связи между всеми звеньями вычислительной цепочки, но и реализовывать возможность сегментации программы на высоком, среднем и низшем уровнях параллелизации вычислительного процесса. Сегментация необходима для более эффективного использования многопроцессорных систем. Кроме этого, при разработке численного алгоритма следует увязывать между собой вопросы точности и надежности конечного программного обеспечения, а также вопросы его эффективности и переносимости под конкретную архитектуру суперЭВМ. Такое параллельное программирование существенно отличается от традиционного - последовательного программирования.
Для предоставления пользователям суперЭВМ возможности одновременного выполнения большого числа научных вычислений или многопоточной обработки запросов в базе данных на многопроцессорных ЭВМ должно быть проинсталлировано соответствующее серверное обеспечение. В данном случае, функции распараллеливания лежат не только на прикладном программном обеспечении, но и на операционной системе.
В общем случае, при создании операционных систем параллельной обработки данных центральными являются две взаимосвязанные проблемы: первая - минимизация времени выполнения заданных объемов вычислений; вторая - синхронизация большего числа одновременно взаимодействующих параллельных процессов [28]. Для решения каждой из них разрабатываются свои подходы. В упомянутой работе предлагается учитывать тот факт, что при реализации сложных механизмов синхронизации происходит рост накладных расходов, что самым негативным образом сказывается на оперативности решения задач. Выявленная проблема в многопроцессорных системах с ограниченным параллелизмом по числу процессоров разрешается методом минимизации общего времени выполнения для заданных объемов вычислений.
Результаты реализации такого подхода относятся, прежде всего, к "операционному параллелизму". В таких системах может оказаться полезным метод, основанный на построении расписания моментов запуска и окончания каждого из конкурирующих процессов. Это дает возможность не только наиболее эффективно решить проблему синхронизации процессов, но и существенно минимизировать системные затраты и непроизводительные простои процессоров. Метод по управлению взаимодействием между параллельными процессами осуществляется с помощью технологии "семафоров" [29].
При создании исследователями прикладного программного обеспечения практическая ценность разрабатываемых ими численных методик определяется не только результатами, полученными с их помощью при исследовании сложных явлений, но и их применимостью на конкретных суперЭВМ. Обнаружено, что с ростом производительности персональных компьютеров, стимулирующим развитие вычислительных методов, происходят также качественные изменения в архитектуре суперкомпьютеров, ориентированные на углубление параллелизма и специализации процессоров. А это, в свою очередь, стимулирует поиск новых представлений физических явлений, допускающих более прямое отображение на архитектуру вычислительной техники. Так, например, появился клеточно-автоматный подход в газо- и гидродинамике [30]. В статье представлена новая модель параллельных вычислений - клеточно-нейронная сеть (КНС). В ней описывается суть клеточно-автоматной модели, а также показаны широкие возможности КНС для представления пространственно-временной динамики активных сред. Эта модель может служить основой для создания параллельных программ, предназначенных для решения дифференциальных уравнений в частных производных, а также для имитации явлений нелинейной динамики. Отмечается, что применение КНС-методов вычисления с использованием параллельных процессоров позволит резко повысить решение задач такого класса.
Целью любой работы, связанной с параллельным программированием, является рассмотрение взаимосвязей между структурой математического алгоритма и архитектурой многопроцессорной вычислительной системы. В зависимости от сложности поставленной задачи возможна реализация различных видов взаимосвязей. Последние называются уровнями декомпозиции исходной задачи. Они могут быть определены следующим образом [31]:
Первый уровень - разбивка задачи на подзадачи.
Второй уровень - разбиение каждой отдельно взятой подзадачи на множество одновременно выполняемых при различных исходных данных квазиоднотипных процедур. В математической физике такой тип параллелизма называют геометрическим параллелизмом или параллелизмом данных, так как распараллеливание здесь производится путем распределения вычислений в разных точках расчетной области в разные процессоры.
Третий уровень - распараллеливание отдельных процедур.
Наиболее глубокий уровень распараллеливания, четвертый - разбиение арифметических процессов на число процессоров.
Последний не рекомендуется к использованию на суперЭВМ с распределенной памятью, у которых на каждый процессор выделена локальная память. Исследователями большинства прикладных задач рекомендуется останавливать процесс их декомпозиции на втором уровне.
Далее рассмотрим, какие объекты в алгоритмах решений задач поддаются распараллеливанию.
Основные численные методы (метод конечных элементов, метод конечных разностей и другие) сводят исходную задачу к формированию системы линейных алгебраических уравнений (СЛАУ) и последующему ее решению [32, 33]. В последовательной программе, например, реализующей метод конечных элементов, основная часть времени приходится на формирование самой СЛАУ (расчет коэффициентов), а не на ее решение. Важно также отметить, что элементы матрицы СЛАУ зависят только от своего положения в ней и не зависят друг от друга. В этом случае складывается благоприятная ситуация для применения параллельных алгоритмов формирования СЛАУ. При этом необходимо выполнить следующие операции:
В статье [34] приводится пример описания параллельного алгоритма формирования СЛАУ, а также особенности применения технологии MPI.
В статье [35] рассматривается реализация метода Гауса для решения разреженных систем линейных алгебраических уравнений на ЭВМ с параллельными процессами и общей памятью. Отмечается, что разбиение на несколько потоков команд возможно либо по функциональному признаку, либо непосредственно по данным. В предложенной постановке задачи возможна только реализация разбиения по данным. При этом обращается внимание на допустимость выделения из задачи несвязных областей.
В той же статье указывается на привязку предлагаемого параллельного алгоритма к конкретной архитектуре ЭВМ, но при этом отмечается, что эффективность алгоритма распараллеливания зависит от соотношения числа процессов и числа процессоров, а также от объема обрабатываемой информации за один цикл.
Можно выдвинуть тезис о том, что циклы - это одни из наиболее важных программных конструкций с доступным параллелизмом. Проблема извлечения мелкозернистого параллелизма (параллелизма внутри циклов) из этих конструкций имеет важное значение в свете возрастающей популярности суперскалярных ЭВМ [36].
В статье [37] представлены алгоритмы вычислительных процедур, а также полученные с их помощью результаты, основанные на методологии сверхточной параллельной арифметики. Эту методологию предлагается применять для решения прикладных задач линейной алгебры и математической физики. Упомянутая работа посвящена созданию алгоритмических и программных средств поддержки точных матричных вычислений, основанных на комплексном использовании параллелизма MIMD-систем [38] и многоразрядной арифметики с динамической длиной операндов. Особое внимание уделяется влиянию округлений в базовых матричных операциях на точность вычисления матричных задач. В работу включены библиотека программ, а также тестовые примеры, демонстрирующие эффективность разработанного подхода. Представленные результаты демонстрируют возможность выполнения на параллельных ЭВМ точных матричных вычислений с одновременной передачей сообщений. Разработанный пакет прикладных программ может быть легко адаптирован к выполнению на параллельных компьютерах различных типов.
Очевидно, что использование многоразрядной арифметики не является типичным для суперкомпьютеров. Ее применение неизбежно ведет к замедлению выполнения приложения. Однако потери времени в этом случае могут быть компенсированы не только проведением расчетов с максимальным использованием стандартных типов данных, но также и адаптацией высокоэффективных параллельных алгоритмов, изначально приспособленных к исполнению на однопроцессорной ЭВМ, к средствам высокоточной обработки. Многоразрядная арифметика должна применяться только в самых "тяжелых" участках алгоритма. Но даже в этом случае динамическая длина операндов помогает обрабатывать только ограниченное количество разрядов. Именно таким образом предлагается достигать баланс между скоростью и точностью вычислений.
В статье [39] подробно анализируется векторно-конвейерная архитектура суперЭВМ семейства CRAY. В результате проведенных исследований обнаружены факторы программирования, снижающие производительность суперЭВМ. К ним относятся:
Здесь также приводятся примеры (в программных кодах), демонстрирующие выход из неблагоприятных ситуаций.
В ряде вышеупомянутых исследовательских работ особо выделяется разработка, в которой структура алгоритма не приспосабливается к структуре ЭВМ, а сама определяет структуру последней [40]. Работа ориентирована на создание новых современных вычислительных технологий и методов параллельного программирования, направленных на повышение эффективности решения фундаментальных научных и прикладных проблем в области численного моделирования задач аэродинамики и газовой динамики. Особое внимание в ней уделено теоретическим вопросам распараллеливания. В работе рассматриваются различные методы декомпозиции полной задачи на ряд одновременно выполняемых подзадач. Весьма важным, имеющим стратегическое значение, является теоретический этап исследования проблемы распараллеливания программного комплекса, то есть разработка принципов (а на их основе - конкретных методов и способов) оптимальной декомпозиции всей совокупности алгоритмов, составляющих процессорную систему и ее операционную среду.
В статье предлагаются три основных вида декомпозиции (сегментации) для планируемого к разработке программного комплекса "Поток-3" в процессе подготовки к параллелизации составляющих его алгоритмов:
Одним из глобальных видов структурирования высокого уровня для решаемой проблемы является декомпозиция исследуемого физического процесса по составляющим его подпроцессам и, соответственно, сегментация общего алгоритма решения полной задачи на ряд алгоритмов решения составляющих подзадач.
Предлагается сегментный алгоритм параллельного проведения вычислений по физическим процессам, при этом работа всех модулей-сегментов вычислительного ядра программы инициируется одновременно. Кроме того, в каждом сегменте может одновременно стартовать работа подсегментов.
Исключительно важное значение при распараллеливании вычислительных процедур приобретает синхронизация вычислений и маршрутизация данных, неудачная организация которых приводит либо к неверному счету, либо к большим накладным расходам компьютерного и астрономического времени из-за всякого рода задержек счета на ожидание данных и, соответственно, бездействия процессоров в некоторых сегментах. Предполагается, что последнее приводит к неоптимальности, или даже невозможности использования реконфигурируемого процессорного пространства.
Геометрическая декомпозиция (сегментация) полной задачи и последующая параллелизация вычислений позволяет существенно снизить величину астрономического времени, требуемого на вычисления. Геометрическая декомпозиция заключается в разделении всей области интегрирования на карту подобластей (сегментов), а также в одномоментном расчете состояния физического процесса в каждой из подобластей с последующей сшивкой решений. В статье приводятся требования к математической постановке задачи, допускающие геометрическую декомпозицию.
Технологическая декомпозиция подразумевает под собой сегментирование математически независимых задач. Возможно несколько уровней технологической декомпозиции. Самый наглядный пример декомпозиции - это распараллеливание программы на определенные физико-математические задачи, каждая из которых аналогично может состоять из алгоритмически независимых задач. Процесс технологической декомпозиции сильно зависит от структуры программы и от используемых в ней численных методов.
Применение последнего вида декомпозиции предполагает повышенное внимание к эффективности параллельной программы.
Несмотря на несомненные успехи в применении мультипроцессорных систем, имеют место рассуждения об их низкой эффективности. Рост производительности мультипроцессорной системы в целом обусловлен сбалансированностью вычислительной работы и обменов на ее фоне. Невыполнение этого условия - одна из причин деградации по производительности при распараллеливании с увеличением числа вычислительных модулей программы.
Оценка эффективности программ ведется еще со времен первых мультипроцессорных систем - транспьютеров. Уже тогда предпринимались попытки для успешного разрешения проблемы максимального использования времени под вычисления. При решении конкретной задачи, в первую очередь, необходим поиск вариантов параллелизма на основе разбивки отдельно взятой задачи на несколько подзадач. Во вторую очередь, допускается параллелизм данных (или геометрический параллелизм) - разбиение вычислительной области. Этот вид параллелизма означает, что вычислительная область разбивается на подобласти, каждая из которых сопоставляется с отдельно взятым процессором системы.
При разработке реальных параллельных программ, как правило, достижение высокой эффективности требует многократных изменений программы для поиска наилучшей схемы ее распараллеливания. Успешность такого поиска определяется простотой модификации программы.
Карпов Андрей Николаевич, http://www.viva64.com
Занимается вопросами создания программных решений в области повышения качества и быстродействия ресурсоемких приложений. Является одним из разработчиков статического анализатора Viva64 для верификации 64-битного программного обеспечения. Участвует в разработке открытой библиотеки VivaCore для работы с Си/Си++ кодом.