Сборочная технология реализации метода частиц для MIMD мультикомпьютеров

• Автор: Краева, Марина Анатольевна
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Новосибирск
• Количество страниц: 141 с.

ВВЕДЕНИЕ
ГЛАВА 1 .МЕТОД ЧАСТИЦ В ЯЧЕЙКАХ И ОСОБЕННОСТИ ЕГО ПАРАЛЛЕЛЬНОЙ РЕАЛИЗАЦИИ
Введение
1.1 Применение Р1С в физике плазмы
1.2 Математическая модель и ее дискретизация
1.3 Проблемы создания параллельной программы
Заключение
ГЛАВА 2.ОБЗОР ПАРАЛЛЕЛЬНЫХ РЕАЛИЗАЦИЙ МЕТОДА ЧАСТИЦ В ЯЧЕЙКАХ
Введение
2.1 Две основных стратегии распределения данных между ПЭ
2.2 Иерархическая декомпозиция
2.3 Две реализации Р1С на архитектуре гиперкуб
2.4 Реализация Р1С алгоритма на МВК "Сибирь"
2.5 Реализация на мультитранспьютерной системе
Заключение

ГЛАВА 3.ЗАДАЧА КОНСТРУИРОВАНИЯ ПРОГРАММЫ, РЕАЛИЗУЮЩЕЙ Р1С
Введение
3.1 Линеаризация массовых алгоритмов и сборочная технология программирования
3.1.1 Линеаризация массовых алгоритмов
3.1.2 Отображение алгоритма на ресурсы мулътикомпъютера
3.1.3 Сборочная технология
3.2 ЛинеаризацияР1С алгоритма
3.3 Выполнение линеаризованного Р1С алгоритма на двумерной решетке процессоров
3.4 Выполнение линеаризованного Р1С алгоритма на гиперкубе
3.5 Определение атомарного фрагмента вычислений
Заключение
ГЛАВА 4.ДИНАМИЧЕСКАЯ БАЛАНСИРОВКА ЗАГРУЗКИ ПРОЦЕССОРНЫХ ЭЛЕМЕНТОВ
Введение
4.1 Алгоритм начальной балансировки загрузки ПЭ при реализации
МЕТОДА ЧАСТИЦ В ЯЧЕЙКАХ НА ЛИНЕЙКЕ ПЭ
4.2 ЦЕНТРАЛИЗОВАННЫЙ АЛГОРИТМ ДИНАМИЧЕСКОЙ БАЛАНСИРОВКИ ЗАГРУЗКИ ПРОЦЕССОРНЫХ ЭЛЕМЕНТОВ ПРИ РЕАЛИЗАЦИИ МЕТОДА ЧАСТИЦ В ЯЧЕЙКАХ НА ЛИНЕЙКЕ ПЭ
4.3 Определение порога разрешенного дисбаланса ВР

4.4 Балансировка загрузки ПЭ при реажзации метода частиц в ячейках
НА РЕШЕТКЕ ПЭ
4.5 Использование виртуальных слоев ПМ
4.6 Децентрализованный алгоритм динамической балансировки
ЗАГРУЗКИ ПЭ ДЛЯ ЗАДАЧ С НЕИЗМЕНЯЕМЫМ КОЛИЧЕСТВОМ ЧАСТИЦ
4.7 Специализированный децентрализованный алгоритм
4.8 Диффузионные алгоритмы балансировки загрузки
4.8.1 Основной диффузионный алгоритм балансировки загрузки
4.8.2 Диффузионный алгоритм балансировки загрузки при реализации РІС метода на линейке процессоров
4.9 Сравнение работы различных алгоритмов динамической балансировки загрузки ПЭ
Заключение
ГЛАВА 5.СРЕДСТВА АВТОМАТИЧЕСКОГО КОНСТРУИРОВАНИЯ ПАРАЛЛЕЛЬНОЙ ПРОГРАММЫ, РЕАЛИЗУЮЩЕЙ РІС МЕТОД
Введение
5.1 Решение двух задач физики плазмы
5.1.1 Расширение облака плотной плазмы в замагниченном фоне
5.1.2 Задача о взаимодействии лазерного импульса с плазмой
5.2 Реализации РІС на ряде мультикомпьютеров в сборочном стиле
5.2.1 Реализация РІС для мулътикомпьютера Parsyt.ec РомгегХрІогег
5.2.2 Реализация на мультикомпьютере МВС
5.2.3 Реализация РІС на гиперкубе Іпіеі іРБС/860

передавать М-частицы из одного ПЭ в другой в ходе моделирования, следовательно, не возникает проблемы динамической балансировки загрузки. Однако, помимо того, что при этом существенно ограничивается максимальный размер решаемой задачи, также требуется передавать большой объем данных между ПЭ. Так как в каждом ПЭ находятся различные частицы, при этом частицы из одной или соседних ячеек могут храниться в разных процессорных элементах, то на каждом временном шаге необходимо суммировать значения средней плотности заряда и тока во всех узлах сетки, вычисленные в каждом ПЭ. Рассмотренный способ распределения данных между ПЭ называется декомпозицией Лагранжа.
Возможны следующая модификация декомпозиции Лагранжа. Множество М-частиц по-прежнему распределяется между ПЭ вне зависимости от их расположения в М-пространстве. Однако сеточные переменные не дублируются целиком в памяти каждого ПЭ. Массивы сеточных переменных также разрезаются на части по числу ПЭ, так чтобы каждая часть содержала равное количество узлов сетки, и распределяются между ПЭ. В этом случае перевычисление электромагнитных полей (четвертая фаза на Рис. 1.2) также распараллеливается. Таким образом снимается ограничение на размер решаемой задачи - нет необходимости хранить в каждом ПЭ массивы сеточных переменных целиком (все М-пространство). Недостаток модифицированной декомпозиции Лагранжа - необходимость пересылок во время выполнения первой и третей фазы Р1С алгоритма, так как М-частицы и соответствующие им и М-ячейки в общем случае находятся в разных ПЭ
Противоположный подход к распределению данных между ПЭ называется декомпозицией Эшера. Как и в случае модифицированной декомпозиции Лагранжа, массивы сеточных переменных также разрезаются на части по числу ПЭ. Однако М-ячейки и находящиеся в них М-частицы на протяжении всего процесса моделирования хранятся в памяти одного ПЭ. При «перелете» Ф-