Теория и практика параллельных вычислений
Краткий обзор лекции
В данной лекции на примере задачи умножения матрицы на вектор рассматриваются возможные схемы разделения матриц между процессорами многопроцессорной вычислительной системы, которые могут быть использованы для организации параллельных вычислений при выполнении матричных операций. В числе излагаемых схем способы разбиения матриц на полосы (по вертикали или горизонтали) или на прямоугольные наборы элементов (блоки).
Далее в лекции с использованием рассмотренных способов разделения матриц подробно излагаются три возможных варианта параллельного выполнения операции умножения матрицы на вектор. Первый алгоритм основан на разделении матрицы между процессорами по строкам, второй – на разделении матрицы по столбцам, а третий – на блочном разделении данных. Каждый алгоритм представлен в соответствии с общей схемой, описанной в лекции 4, — вначале определяются базовые подзадачи, затем выделяются информационные зависимости подзадач, далее обсуждается масштабирование и распределение подзадач между процессорами. В завершение для каждого алгоритма проводится анализ эффективности получаемых параллельных вычислений и приводятся результаты вычислительных экспериментов. Для алгоритма умножения матрицы на вектор при ленточном разделении данных по строкам приводится возможный вариант программной реализации.
Полученные показатели эффективности показывают, что все используемые способы разделения данных приводят к равномерной балансировке вычислительной нагрузки, и отличия имеются только в трудоемкости выполняемых информационных взаимодействий между процессорами. В этом отношении представляется интересным проследить, как выбор способа разделения данных влияет на характер необходимых операций передачи данных, и выделить основные различия в коммуникационных действиях разных алгоритмов. Кроме того, важным является определение целесообразной структуры линий связи между процессорами для эффективного выполнения соответствующего параллельного алгоритма. Так, например, алгоритмы, основанные на ленточном разделении данных, ориентированы на топологию сети в виде гиперкуба или полного графа. Для реализации алгоритма, основанного на блочном разделении данных, необходимо наличие топологии решетки.
На рис. 6.11 на общем графике представлены показатели ускорения, полученные в результате выполнения вычислительных экспериментов для всех рассмотренных алгоритмов. Следует отметить, что дополнительные расчеты показывают , что при большем количестве процессоров и при большом размере матриц более эффективным становится блочный алгоритм умножения.
Рис. 6.11. Показатели ускорения рассмотренных параллельных алгоритмов умножения по результатам вычислительных экспериментов с матрицами размера 2000x2000 и векторами из 2000 элементов
