Аннотация

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

Введение

Применение параллельных вычислительных систем является стратегическим направлением развития вычислительной техники. Это обстоятельство вызвано не только принципиальным ограничением максимально возможного быстродействия обычных последовательных ЭВМ, но и практически постоянным наличием вычислительных задач, для решения которых возможностей существующих средств вычислительной техники всегда оказывается недостаточно. К таким задачам можно отнести проблемы моделирование климата, генной инженерии, проектирования интегральных схем, анализа загрязнения окружающей среды, создание лекарственных препаратов и др., которые требуют для своего анализа ЭВМ с производительностью более 10¹² операций с плавающей запятой в секунду (1 TFlops) [1].

Не всякая вычислительно трудоемкая задача может быть решена с помощью параллельных вычислительных систем в силу наличия в ней разнородных зависимостей. А для задач, подлежащих распараллеливанию, проведение удачной декомпозиции – весьма серьезная проблема, требующая основательного осмысления и поиска ответов на следующие вопросы: как определить масштаб компьютерной системы, обеспечивающий достижение требуемого времени выполнения программы, как найти наилучший метод решения задачи, каким языком необходимо воспользоваться, чтобы он был адекватен задаче и позволял отразить возникший параллелизм в методе ее решения, как определить максимальную зернистость в параллельной программе, наконец, как организовать выполнение программы (синхронизировать процессы и распределить ресурсы), чтобы достичь желаемого эффекта [2].

Преимущество параллелизма в возможности одновременного выполнения независимых подзадач, но на практике, как правило, не удается создать алгоритм, полностью разделяющийся на параллельные фрагменты. Последовательные участки непременно присутствуют во всяком приложении, использующем средства параллелизма. Поэтому, строго говоря, в настоящей работе речь пойдет о последовательно-параллельных вычислениях. Классическая оценка их ускорения сформулирована в законе Амдаля [1, 4]. Джин Амдал в 1967 году сформулировал ограничение на величину ускорения при распараллеливании вычислений:

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

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

К задачам, обладающим хорошей масштабируемостью, в большинстве своем, относят широкий круг матричных задач: решение систем линейных алгебраических уравнений (СЛАУ), вычисление определителей, определение собственных значений и собственных векторов, матричное умножение, нахождение обратной матрицы и др. Основная вычислительная нагрузка в таких задачах ложится на участки, которые можно разбить на независимые фрагменты. Это означает, что доля последовательных вычислений невелика, следовательно, можно составить параллельный алгоритм, дающий некоторое ускорение, ограниченное сверху значением .

Сами матричные задачи сравнительно редко представляют самостоятельный интерес для приложений, но от их эффективного решения часто зависит сама возможность математического моделирования самых разнообразных процессов с применением ЭВМ [3].

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

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

Работа состоит из введения, трех глав, заключения, библиографического списка и пяти приложений. Общий объем работы 40 страниц.

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

Во второй главе представлен обзор существующих методов решения СЛАУ, предлагается последовательно-параллельная модификация итерационного метода Якоби для класса разреженных систем, обладающих свойством диагонального преобладания. В качестве примера рассматривается задача математического моделирования распределения температуры в тонком стержне, сводящаяся к системе уравнений, решаемой с помощью разработанного метода. Получена зависимость ускорения последовательно-параллельного решения в зависимости от количества используемых для решения СЛАУ процессоров и сделаны выводы по ней.

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

В приложения вынесены фрагменты наиболее важных участков составленных программ.