Параллелизм супер-ЭВМ – магистральный путь развития вычислительной техники. Господствующим способом распараллеливания задач до сих пор является крупноблочное. При этом задача разбивается на большие подзадачи (блоки), предназначенные для параллельного решения на небольшом числе процессоров. Соответственно ориентированы и параллельные алгоритмы численного решения задач.
Очевидно, что с ростом числа процессоров блоки измельчаются, и вычисления в подавляющем большинстве случаев будут идти медленнее: параллелизм вырождается. Избежать вырождения можно только при условии, что обмены происходят и одновременно, и локально, т.е. физическое расстояние между взаимодействующими процессорами мало и не зависит от размера задачи.
В работах профессора В.А. Воробьева рассмотрены три обязательных условия, при которых не происходит снижения производительности МЛПП [2, c. 12]:
- Локальность взаимодействий, когда обмен данными происходит только в пределах ограниченного физического и структурного радиуса, независимо от размеров задачи и системы.
- Параллелизм взаимодействий, когда все возможные в данный момент обмены совершаются параллельно и одновременно с процессом счета.
- Количество глобальных операций не должно влиять на оценку временной сложности задачи.
При описании алгоритма параллельных вычислений на ЭВМ класса MIMD предполагается, что MIMD –машина состоит из p одинаковых процессоров, каждый из которых обладает определенным объемом своей локальной памяти (одинаковым для всех параллельных процессоров) и способен осуществлять численную обработку информации в автономном и управляемом режимах.
Отметим существенные особенности архитектуры MIMD – машины, при которых стиль МЛП – программирования был наиболее эффективен.
- Попарное соединение процессоров осуществляется за очень короткий промежуток времени и поэтому оно не учитывается.
- Все возможные в данный момент обмены машинными словами совершаются параллельно и одновременно с процессом счёта за время, сравнимое со временем выполнения одной арифметической операции (из-за близости связанных процессоров в физическом пространстве).
- Имеется возможность программировать структуру межпроцессорных связей.
Опишем клеточную машину, предназначенную для МЛП-программирования в клеточном стиле.
Клеточная машина (К-машина) представляет собой клеточное множество – массив поименованных клеток, в каждой из которых находится универсальный вычислитель, известный в теории вычислений, как РАМ-машина. Клетка может обмениваться информацией с соседями согласно шаблону соседства, задающему доступную для клетки окрестность. В частности, если в клетках будут размещены более простые устройства – автоматы, то клеточная машина моделирует клеточный автомат. Клетка К-машины содержит процессор, память и коммутационное устройство для связи с соседями и управляющей машиной. Данные, расположенные в клетке – называются локальными, в управляющей машине – глобальными. Состояние клетки – набор значений всех её локальных переменных, состояние окрестности – набор значений локальных переменных в её окрестности. Состояние К-машины – набор значений всех её локальных и глобальных переменных. Все клетки функционируют одновременно, но вычисления происходят только там, где состояние клетки и её окрестности удовлетворяет заданным условиям активности. Такие клетки называются активными.
Шаблон соседства для данной клетки – это список приращений её координат для получения координат соседей. Взаимодействовать должны только ближайшие соседи. Условие локальности означает, что радиус шаблона соседства -это константа, на много меньшая размера всего клеточного множества и не зависящая от этого размера.
Топология К-машины задаётся шаблоном соседства. Поскольку К-машина в простейшем случае – прямоугольный массив, то появляется несколько вариантов определения соседей на границах прямоугольника. Одна из них — тор, которая получается, если мы склеим попарно и вертикальные, и горизонтальные границы прямоугольника.
Из всего вышесказанного следует, что MIMD – машина и К-машина изоморфны по своей структуре и свойствам, а понятие «процессор» соответствует понятию «клетка».
Разработка и исследование МЛПП для задач математической физики – одно из актуальных направлений современного параллельного программирования. В [1, c.50] для этих целей применяются модели клеточных автоматов на планарных бесконечномерных решетках.
Целью настоящей работы является вложение данных МЛПП –алгоритма решения сеточной задачи для разностной схемы расщепления трехмерного уравнения теплопроводности в клеточную машину с топологией тороидально связанного куба с иллюстрацией межпроцессорных обменов.
Кратко изложим физическую интерпретацию задачи.
В заключение отметим, что существуют другие алгоритмы распараллеливания методов решения разностных схем гиперболических уравнений. Однако эти алгоритмы крупноблочные и к ним трудно применима технология мелкозернистого локально-параллельного программирования, и, как правило, они реализуются либо на кластерах, либо на планарных неразрезных процессорных матрицах. Предложенную идею можно использовать для распараллеливания других методов решения разностных схем гиперболических уравнений.
Список литературы
- Бандман О.Л. Мелкозернистый параллелизм в математической физике // Программирование.- 2001.- №4. С.12-25.
- Воробьев В.А. Об эффективности параллельных вычислений // Автометрия.- 2000. — № 1. С. 50-58.[schema type=»book» name=»РЕАЛИЗАЦИЯ РЕШЕНИЯ ТРЕХМЕРНОЙ РАЗНОСТНОЙ СХЕМЫ РАСЩЕПЛЕНИЯ УРАВНЕНИЯ ТЕПЛОПРОВОДНОСТИ В КЛЕТОЧНОЙ МАШИНЕ В МЕЛКОЗЕРНИСТОМ ЛОКАЛЬНО–ПАРАЛЛЕЛЬНОМ СТИЛЕ ПРОГРАММИРОВАНИЯ» description=»В статье содержится описание клеточной машины и основные положения мелкозернистого локально-параллельного (МЛП) программирования, предназначенного для применения в К-машине. Представлен новый МЛП-алгоритм в клеточном стиле для сеточных задач математической физики. » author=»Заручевская Галина Васильевна» publisher=»Басаранович Екатерина» pubdate=»2017-03-13″ edition=»ЕВРАЗИЙСКИЙ СОЮЗ УЧЕНЫХ_30.05.2015_05(14)» ebook=»yes» ]