PARALLEL.RU - Информационно-аналитический центр по параллельным вычислениям

Большинство методов создания параллельных программ ориентируется на распараллеливание последовательных алгоритмов. В этом случае затруднительно создать прикладные программы для многопроцессорных суперЭВМ, эффективно функционирующие для различных вариантов распараллеливания. Для структурно-процедурной организации параллельных вычислений исходным является информационный граф алгоритма решения задачи. Если оборудования суперЭВМ достаточно для покрытия информационного графа задачи, то задача будет решена структурно, в противном случае необходимо произвести разрезку информационного графа на кортежи подграфов (кадры), каждый из которых будет выполняться аппаратно, а процесс смены кадров будет происходить по единой, а следовательно, детерминированной управляющей программе.

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

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

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

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

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

Пользователям будет предоставлена возможность использовать одни и те же загрузочные модули при различных конфигурациях многопроцессорной системы. При увеличении числа модулей системы реальная производительность выполнения загрузочных модулей параллельных программ, созданных по технологии индуктивных параллельных заданий, будет увеличена пропорционально увеличившемуся количеству процессоров суперЭВМ. Для индуктивных параллельных программ, использующих принцип виртуального процессорного пространства, будет иметь место линейный рост производительности при увеличении числа процессоров в системе.

Разработаны принципы построения многопроцессорных суперЭВМ с массовым параллелизмом и программируемой архитектурой, основные компоненты системного математического обеспечения.

Разработан и изготовлен базовый модуль многопроцессорной суперЭВМ с массовым параллелизмом и программируемой архитектурой на основе макропроцессорного комплекта СБИС(1995-1996 гг.). Базовый модуль многопроцессорной системы с программируемой архитектурой и его программное обеспечение демонстрировались на международных выставках CEBIT-97, CEBIT-98, Ганновер (Германия), SIMO- 98, Мадрид (Испания).

Разработано системное и прикладное математическое обеспечение для различных многопроцессорных вычислительных систем. Разработаны эффективные структурно-процедурные алгоритмы решения на суперЭВМ с массовым параллелизмом и программируемой архитектурой различных научно-технических задач.

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

Разработаны примеры индуктивных параллельных программ для решения задач математической физики, цифровой обработки сигналов, САПР СБИС. Исследованы вопросы ресурсонезависимого программирования и функционирования суперЭВМ с массовым параллелизмом в многозадачном режиме.

Разработан алгоритм планировщика заданий индуктивных параллельных программ для полнодоступной коммутационной системы межпроцессорного обмена.

Для базового модуля многопроцессорной суперЭВМ с программируемой архитектурой разработан параллельный ассемблер, распараллеливающий ФОРТРАН-компилятор, основные элементы операционной системы, разработаны параллельные алгоритмы и программы для решения на суперЭВМ задач из различных проблемных областей.

347922, Таганрог, НИИ МВС, к.339
Илья Израилевич Левин, тел. (86344) 617-21
e-mail: levin@mvs.tsure.ru