Панков С.В. Лекции по системному анализу
Подождите немного. Документ загружается.
5.1. Обработка массивов
Одномерные массивы
Данные задачи встречаются довольно часто. Если значения элементов массива
определяются довольно сложным выражением, а вычислять их надо многократно, то
векторизация или распараллеливание цикла для вычисления элементов массива может
оказаться очень эффективным. В отдельный параграф мы вынесли решение систем
дифференциальных уравнений, что по своей сути также является обработкой массивов
функций, производных и т.д. Но на самом деле эффективными могут также быть
вычисления сверток, сумм, функций от каждого элемента массива и т.п.
Конечно, не имеет смысл векторизовать или распараллеливать действия над короткими
массивами кроме тех случаев, когда собственно вычисления каждого элемента занимают
большое время.
5.1.2. Двумерные массивы
При исполнении вложенных циклов эффективно распараллеливаются самые внешние
циклы, а векторизуются только внутренние. Однако практически все действия с
матрицами (сложение, умножение, умножение на вектор, прямое произведение) могут
быть выполнены быстро на супер-ЭВМ. Многие алгоритмы линейной алгебры (но не все)
могут быть эффективно векторизованы и распараллелены. Некоторые библиотеки
подпрограмм (например, LAPACK(?)) существуют для параллельных и векторных машин.
Совершенно неэффективно использовать векторные ЭВМ для работы с матрицами
размерности 3x3. Но можно переписать алгоритм для одновременной обработки
нескольких (к примеру 1000) матриц - обращение, поиск собственных чисел и т.д.
При увеличении размера матриц растет эффективность работы программы, но растет и
размер требуемой памяти для хранения матриц. При работе на векторной машине с
небольшим (128-512 Мбайт) объемом ОЗУ это может стать причиной общего снижения ее
быстродействия из-за частого обращения к дискам при записи/чтении данных.
5.2. Вычисления в узлах сеток и решеток
Инженерные и научные задачи
Во многих областях знания встречаются задачи, которые сводятся к вычислению
эволюции объектов, расположенных в дискретных точках и взаимодействующих с
ближайшими соседями. Простейшей и, наверно, наиболее широко известной такой
задачей является игра "жизнь".
Все игровое поле представляет двумерную сетку с квадратными ячейками. Каждая ячейка
может быть в одном из двух состояний - пустая или живая. Если на каком-то шаге игры
вокруг пустого поля существуют ровно три живых поля, то на следующем шаге игры в
этом поле рождается жизнь. Если число живых полей вокруг пустого поля не равно трем,
то в это поле остается пустым. Если вокруг живого поля существуют два или три других
живых поля, то жизнь в в этом поле продолжается. Если число живых соседей отлично от
двух или трех, то поле погибает (становится пустым). Начальная конфигурация
выбирается произвольным образом. Игровое поле может иметь края или может быть
свернуто в тор. Вот пример конфигурации:
o o o Обозначения:
o x o Oo - пустые
O X O Xx - живые
o x o O - родится, o - останется
o o o X - останется, x - погибнет
Пример игры реализован в качестве заставки на дисплее в системе OpenWindows на ЭВМ
фирмы SUN.
В игре "жизнь" реализуется простейшая модель "взаимодействия" пустых и живых ячеек с
соседями, определяющая эволюцию всей системы. Но вот пример из физики, который по
способу построения модели идентичен этой игре. Модель магнетиков Изинга
представляет собой набор спинов (элементарных магнитов), расположенных в узлах
решетки и взаимодействующих только с ближайшими соседями. Вычислительный
интерес представляют трех- и четырехмерные модели. Двумерные Изинговские магнетики
с анизотропными (зависящими от направления) дальними взаимодействиями (т.е. не
только с ближайшими, но и через один узел) также нельзя исследовать аналитически, а
только с помощью компьютерных экспериментов. Очевидно, что алгоритм построения
эволюции Изинговских магнетиков будет во многом идентичен алгоритму игры.
Многие молекулярные модели сплошных сред в статистической физике также строятся по
принципу узлов (или ячеек) в кубической решетке. Молекулы могут располагаться только
в ячейках. Взаимодействия молекул в соседних ячейках определя
Основная литература
1. Миренков Н.Н. Параллельное программирование для многомодульных вычислительных систем. - М.:
Радио и связь, 1989. - 320 с.
2. Воеводин В.В. Математические модели и методы в параллельных процессах./М.: Наука, 1986 г. – 296 с.
3. Ч. .Хоар Взаимодействующие последовательные процессы
4. М: Мир 1989г - 262с.
5. Непомнящий В. А. Проблемы сертификации и верификации параллельных систем. Новосибирск: Ис-т
систем информатики СО РАН, 1995. - 237 с.
6. Дополнительная литература (в сети Интернет):
7. Главная страница на русском языке, посвящённая параллельным вычислениям.
8. http://www.parallel.ru/
9. This page contains a link [Many materials for learning MPI are available], which goes to new page with
information on books http://www.mcs.anl.gov/mpi/ covering MPI.
10. MPI для начинающих. Учебное пособие + примеры. Автор: Илья Евсеев. Организация: ИВВиБД
( ЦСТ ).
http://www.csa.runnet.ru/~il/mpi_tutor/
11. Современные высокопроизводительные компьютеры В. Шнитман, информационно-аналитические
материалы Центра Информационных Технологий, 1996 год
http://www.citforum.ru/win/hardware/svk/contents.shtml