Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Организация параллелизма на основе разделения данных

Читайте также:
  1. I. Исследование свойств форматов сжатия графических данных
  2. II. Организация выполнения контрольной работы
  3. II. Организация выполнения курсовой работы
  4. III. Медицинская психология; лечение психических расстройств; организация психиатрической помощи.
  5. IV. Организация выполнениявыпускной квалификационной работы
  6. IV. Организация питания
  7. V. Взаимоотношения отдела сбыта с другими подразделениями предприятия
  8. V2: Организация и методика ветеринарно-санитарного осмотра туш и внутренних органов
  9. А) организация деятельности студента по видам учебных занятий
  10. А) разделения властей

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

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

,

где каждый блок матрицы определяется в соответствии с выражением

.

Информационный граф алгоритма умножения при подобном представлении матриц показан на рис. 4.9 (на рисунке представлен фрагмент графа для вычисления только одного блока матрицы ). При анализе этого графа можно обратить внимание на взаимную независимость вычислений блоков матрицы . Как результат, возможный подход для параллельного выполнения вычислений может состоять в выделении для расчетов, связанных с получением отдельных блоков , разных процессоров. Применение подобного подхода позволяет получить многие эффективные параллельные методы умножения блочно-представленных матриц; один из алгоритмов данного класса рассматривается ниже.

Рис. 4.9. Информационный граф матричного умножения при блочном представлении матриц

Для организации параллельных вычислений предположим, что процессоры образуют логическую прямоугольную решетку размером (обозначим через процессор, располагаемый на пересечении строки и столбца решетки). Основные положения параллельного метода, известного как алгоритм Фокса (Fox) [15], состоят в следующем:

· каждый из процессоров решетки отвечает за вычисление одного блока матрицы ;

· в ходе вычислений на каждом из процессоров располагается четыре матричных блока:

o блок матрицы , вычисляемый процессором;

o блок матрицы , размещенный в процессоре перед началом вычислений;

o блоки , матриц и , получаемые процессором в ходе выполнения вычислений;

Выполнение параллельного метода включает:

· этап инициализации, на котором на каждый процессор передаются блоки , и обнуляются блоки на всех процессорах;

· этап вычислений, на каждой итерации , которого выполняется:

o для каждой строки , процессорной решетки блок процессора пересылается на все процессоры той же строки ; индекс , определяющий положение процессора в строке, вычисляется по соотношению

,

( есть операция получения остатка от целого деления);

o полученные в результаты пересылок блоки , каждого процессора перемножаются и прибавляются к блоку

;

o блоки каждого процессора пересылаются процессорам , являющимися соседями сверху в столбцах процессорной решетки (блоки процессоров из первой строки решетки пересылаются процессорам последней строки решетки).

Для пояснения приведенных правил параллельного метода на рис. 4.10 приведено состояние блоков на каждом процессоре в ходе выполнения итераций этапа вычислений (для процессорной решетки ).

Приведенный параллельный метод матричного умножения приводит к равномерному распределению вычислительной нагрузки между процессорами

, .

Вместе с тем, блочное представление матриц приводит к некоторому повышению объема пересылаемых между процессорами данных - на этапе инициализации и на каждой итерации этапа вычислений на каждый процессор передается 2 блока данных общим объемом . Учитывая выполняемое количество итераций метода, объем пересылаемых данных для каждого процессора составляет величину

Рис. 4.10. Состояние блоков на каждом процессоре в ходе выполнения итераций этапа вычислений

Объем пересылаемых данных может быть снижен, например, при использовании строкового (для ) и столбцового (для ) разбиения матриц, при котором справедлива оценка

.

Данные оценки показывают, что различие объемов пересылаемых данных

является не столь существенным и данное различие уменьшается при увеличении числа используемых процессоров.

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

 




Дата добавления: 2015-04-11; просмотров: 21 | Поможем написать вашу работу | Нарушение авторских прав

1 | 2 | 3 | 4 | 5 | 6 | <== 7 ==> |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.009 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав