автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Анализ и разработка параллельных алгоритмов для вычислительного комплекса МВС-100

/

ад у / р*/*

«/ ^ ™ / / о р&о - а

российская академия наук

дальневосточное отделение институт автоматики и процессов управления

Л

С хМ1-^0 На правах рукописи

СМИРНОВ Сергей Викторович

АНАЛИЗ И РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ДЛЯ ВЫЧИСЛИТЕЛЬНОГО КОМПЛЕКСА МВС-100, НА ПРИМЕРЕ МОДЕЛИ ДИНАМИКИ ОКЕАНА

05.13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (техника)

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата физико-математических наук

Научный руководитель:

чл.-корр. РАН д.ф.-м.н. В.А.Левин

СОДЕРЖАНИЕ

ВВЕДЕНИЕ ..........................................................................................4

Глава 1. АНАЛИЗ ВЫЧИСЛИТЕЛЬНЫХ ВОЗМОЖНОСТЕЙ

МВС-100 И РАЗРАБОТКА ПРОГРАММНЫХ СРЕДСТВ

ДЛЯ КОНВЕЙЕРНЫХ ВЫЧИСЛЕНИЙ.................................11

§ 1.1. Вычислительные возможности комплекса МВС-100.............15

§ 1.2. Концепция построения параллельных структур

вычислительного алгоритма..................................................21

§ 1.3. Программная реализация векторных команд на языке

нижнего уровня микропроцессора ШТЕЬ860......................23

§ 1.4. Выводы по главе .......................................................................35

Глава 2. АНАЛИЗ И РАЗРАБОТКА ВАРИАНТОВ

ЭКОНОМИЧНОГО АЛГОРИТМА МПТМ.............................36

§ 2.1. Попеременно-треугольный итерационный метод..................37

§ 2.2. Построение вариантов экономичного алгоритма...................38

§ 2.3. Основные черты программной реализации............................43

§ 2.4. Выводы по главе ......................................................................44

Глава 3. АНАЛИЗ И ПОСТРОЕНИЕ ЧИСЛЕННОЙ СХЕМЫ

МОДЕЛИ ДИНАМИКИ ОКЕАНА..........................................46

§ 3.1. Математическая модель динамики океана..............................48

§ 3.2. Дискретные аналоги уравнений модели.................................49

§ 3.3. Выводы по главе ......................................................................59

Глава 4. ПОСТРОЕНИЕ ПАРАЛЛЕЛЬНОГО

ВЫЧИСЛИТЕЛЬНОГО АЛГОРИТМА МОДЕЛИ..................60

§ 4.1. Общая организация счета в модели........................................60

§ 4.2. Организация межпроцессорного обмена................................66

§ 4.3. Векторизация и организация вычислений в программных

модулях...................................................................................70

§ 4.4. Выводы по главе......................................................................87

Глава 5. ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ..............................89

§ 5.1. Тестовый вычислительный эксперимент................................90

§ 5.2. Вычислительный эксперимент с реальной топографией

дна...........................................................................................97

§ 5.3. Организация вычислений в эксперименте с реальной

топографией дна...................................................................108

Выводы по главе...............................................................................109

ЗАКЛЮЧЕНИЕ.....................................................................................111

ЛИТЕРАТУРА.......................................................................................113

Приложение 1. ПОДПРОГРАММЫ ВЕКТОРНОЙ ОБРАБОТКИ......126

Приложение 2. УРАВНЕНИЯ МОДЕЛИ ДИНАМИКИ ОКЕАНА И

ВЫЧИСЛИТЕЛЬНАЯ СЕТКА...............................................132

§ П2.1. Математическая модель динамики океана.........................132

§ П2.2. Вычислительная сетка.........................................................137

Приложение 3. ДОКУМЕНТЫ.............................................................143

ВВЕДЕНИЕ

Актуальность темы и предмет исследования

Увеличение производительности ЭВМ расширяет возможности применения вычислительной техники для крупномасштабных задач численного моделирования и проведения вычислительного эксперимента в фундаментальных и прикладных научных исследованиях. Рост вычислительных возможностей современных высокопроизводительных вычислительных систем во многом определяется интенсивным развитием средств параллельной работы в аппаратуре ЭВМ. Параллельный подход приводит к самым разнообразным вариантам архитектуры. Наиболее распространены системы с массовым параллелизмом, в которых процессоры содержат конвейерные функциональные устройства и непосредственно обмениваются только со своей локальной памятью. Такие конструктивные особенности реализованы, например, в ЭВМ МВС-100/1000, PARAGON, CRAY ТЗЕ. При этом возникает проблема, как наилучшим способом могут быть использованы имеющиеся аппаратные средства для эффективного решения конкретных вычислительных задач.

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

ной схемы, включая численные методы и алгоритмы расчета моделей, на параллельно-конвейерную архитектуру ЭВМ.

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

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

Решение задач, поставленных в диссертации, проводилось в соответствии с научно-исследовательскими планами ИАПУ ДВО РАН в рамках выполнения разделов следующих программ:

1.Проект N0201.01.018 Миннауки РФ "Разработка для систем массового параллелизма новых методов прогнозирования и программного обеспечения динамики океана и окраинных морей, а также обработки спутниковой информации";

2. Проект N0201.01.244 Миннауки РФ "Создание системного программного обеспечения мультипроцессорных суперкомпьютеров и режимов удаленного доступа к вычислительным ресурсам на основе

использования стандартизованных средств программирования высокого уровня";

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

Цель работы

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

В соответствии с данной целью были поставлены и решены следующие задачи.

¡.Проведен совместный анализ архитектуры ЭВМ МВС-100 и численного метода модели динамики океана. На основе крупноблочно-иерархического подхода разработана концепция построения параллельного алгоритма модели. На верхнем уровне выполнено геометрическое распараллеливание вычислительного процесса, нижний уровень параллельного алгоритма базируется на векторных командах.

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

3. Решена задача отображения экономичного алгоритма модифицированного попеременно-треугольного итерационного метода

А.А.Самарского (МПТМ) на архитектуру процессорного элемента (ПЭ) системы МВС-100.

4. С использованием разработанных программно-алгоритмических средств проведен крупномасштабный вычислительный эксперимент по изучению динамики Японского моря.

Основные методы исследований

Задачи, поставленные в работе решались с привлечением разностных методов, попеременно-треугольного итерационного метода, методов параллельного программирования.

Научная новизна работы и положения, выносимые на защиту

Научная новизна выполненной работы и положения, выносимые на защиту, состоят в следующем:

1. Построен и программно реализован параллельный алгоритм численной модели динамики океана для мультипроцессорной ЭВМ МВС-100.

1. Разработано эффективное алгоритмическое и программное обеспечение векторных операций на процессорном элементе МВС-100.

2. Разработан новый вариант экономичного алгоритма МПТМ.

4. Проведен крупномасштабный вычислительный эксперимент по изучению динамики Японского моря с реальной топографией дна на сетке с 280000 расчетными узлами.

Практическая ценность работы

Практическая ценность работы состоит в том, что

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

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

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

Апробация работы

Основные результаты, полученные в диссертационной работе, докладывались на семинарах в ИАПУ ДВО РАН, на Океанологическом семинаре и семинаре лаборатории Математического моделирования ТОЙ ДВО РАН. Сделаны доклады: "Численное моделирование циркуляции Японского моря" на научно-технической конференции "Проблемы механики сплошной среды и прогрессивные технологии в машиностроении и металлургии", г. Комсомольск-на-Амуре, 1997г., "Вычислительные алгоритмы математической модели океанской циркуляции для ЭВМ с массовым параллелизмом", г. Пермь, 12-я Зимняя школа по механике сплошных сред, 1999 г.

Публикации

По материалам диссертации опубликовано 5 печатных работ.

Структура диссертации.

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

В первой главе кратко описаны основные черты архитектуры комплекса МВС-100 и микропроцессора ГЫТЕЬ860, проанализированы основные ограничивающие факторы вычислительного процесса, изложена выработанная общая концепция решения задачи отображения численного алгоритма на вычислительную систему МВС-100 и описаны базовые подпрограммы нижнего уровня, с помощью которых на процессорном элементе системы имитируется векторный вычислитель.

Во второй главе описывается процесс построения варианта экономичного алгоритма МПТМ для решения разностного эллиптического уравнения на одном вычислительном модуле с микропроцессором ШТЕЬ860.

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

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

Пятая глава посвящена описанию организации и проведения с помощью реализованной модели численного эксперимента по моделированию циркуляции Японского моря.

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

В Приложение 1 вынесено описание реализованного набора команд конвейерной обработки.

В Приложение 2 вынесены формулировка математической модели циркуляции океана и описание используемой вычислительной сетки.

В Приложение 3 вынесены документы, подтверждающие внедрение разработок автора.

Глава 1. АНАЛИЗ ВЫЧИСЛИТЕЛЬНЫХ ВОЗМОЖНОСТЕЙ МВС-100 И РАЗРАБОТКА ПРОГРАММНЫХ СРЕДСТВ ДЛЯ КОНВЕЙЕРНЫХ

ВЫЧИСЛЕНИЙ

В начале 80-х годов произошло утверждение суперЭВМ в качестве самостоятельного класса машин. Этому способствовали возрастание потребностей в вычислительных ресурсах в стратегических областях науки и техники и резкое увеличение производительности за счет векторной обработки. С увеличением производительности вычислительных средств расширился круг решаемых задач, еще более он возрастает со снижением стоимости вычислений. Например, математическое моделирование циркуляции океана в середине 80-х годов вступило в новую эру [5], что стало возможным благодаря двум техническим достижениям. Одним из них является создание спутникового альтиметра, вторым - удешевление вычислительных работ с появлением конвейерных суперЭВМ СЯАУ-1 и СуЬег-205, что дало возможность для проведения расчетов с гораздо более высоким разрешением, чем в предшествующих работах.

Параллельные вычислительные системы

Рост вычислительных возможностей современных высокопроизводительных вычислительных систем связан не только с переходом на высокочастотные элементы, но и во многом определяется интенсивным развитием средств параллельной работы в аппаратуре ЭВМ [50,60]. Увеличение производительности может достигаться с помощью может самых разнообразных форм параллелизма:

1) сокращение временных затрат при обращении к памяти за счет усложнения ее структуры: а)разбиение памяти на модули, обращение к которым производится одновременно, б) применение дополнительной быстродействующей кэш-памяти, в) увеличение числа внутренних регистров в процессоре;

2) сокращенние длительности исполнения команд за счет временного перекрытия различных ее фаз;

3) выполнение системой одновременно нескольких команд.

Параллельный подход приводит к самым различным вариантам архитектуры в зависимости от способа, по которому осуществляется задание очередности следования команд и управления их исполнением. Например, наиболее мощные современные суперкомпьютеры состоят из нескольких параллельно работающих векторных процессоров [105]. Из всего разнообразия выделим системы с массовым параллелизмом (МРР - Massively Parallel Processing), как наиболее распространенные. В таких системах каждый процессор имеет только свою локальную память и обменивается информацией с соседями по сети. По классификации Флинна [71] такие системы относятся к типу MIMD или МКМД (много потоков команд - много потоков данных). Среди типов процессоров особо выделим конвейерные, в которых различные фазы одной команды выполняются последовательно на различных блоках функциональных устройств. Если команды не зависят по данным, они могут частично перекрываться во времени, что повышает производительность процессора и удешевляет вычисления.

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

по процессорам и векторизаторы трансляторов [4,12,16, 21,61]. Например, в работах [80,82,96] основной акцент делается на векторизации вычислений для Сгау-1 и СуЬег-205, описывается сведение структур программ к такому виду, который распознают автоматические векторизаторы трансляторов этих ЭВМ.

Параллельные вычислительные алгоритмы

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

С введением параллельного выполнения команд изменилась сама структура алгоритма, по которому работает система. Эффективность использования систем тесно связана со структурами вычислительных алгоритмов [6,9,60]. Перечислим условия эффективной реализации, например, разностных схем на параллельном вычислителе [15]:

- локальность и квазирегулярность расчетных сеточных шаблонов;

- квазирегулярность структуры обмена данными;

- квазиоднородность групп расчетных формул;

- членение сложной структуры задачи на отдельные фрагменты (счетные области) с последующим их комплексированием в ходе расчета;

- доминирование по времени объема вычислений над объемом обмениваемой информации.

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