Алгоритм пушки - Cannons algorithm - Wikipedia

В Информатика, Алгоритм Кэннона это распределен алгоритм умножения матриц для двумерных сетки впервые описан в 1969 г. Линн Эллиот Кэннон.^[1][2]

Он особенно подходит для компьютеров, установленных в N × N сетка.^[3] Хотя алгоритм Кэннона хорошо работает в однородных 2D-сетках, его распространение на гетерогенные 2D-сетки оказалось трудным.^[4]

Основное преимущество алгоритма заключается в том, что его требования к памяти остаются постоянными и не зависят от количества процессоров.^[2]

Масштабируемый универсальный алгоритм умножения матриц (SUMMA)^[5]- это более практичный алгоритм, который требует меньше рабочего пространства и устраняет необходимость в квадратной 2D-сетке. Он используется ScaLAPACK, НАБОР, и Элементаль библиотеки.

Обзор алгоритма

При умножении двух п×п матрицы A и B, нам понадобится п×п узлы обработки p, расположенные в двумерной сетке. Первоначально p_{я, j} несет ответственность за_{я, j} и б_{я, j}.

// PE (i, j) k: = (i + j) mod N; a: = a [i] [k]; b: = b [k] [j]; c [i] [j]: = 0; для (l: = 0; l 
Нам нужно выбирать k на каждой итерации для каждого элемента процессора (PE), чтобы процессоры не имели доступа к одним и тем же данным для вычислений. ${\displaystyle a_{ik}*b_{kj}}$.
Поэтому процессоры в одной строке / столбце должны начинать суммирование с разных индексов. Если например PE (0,0)  вычисляет ${\displaystyle a_{00}*b_{00}}$ на первом этапе PE (0,1) выбирает ${\displaystyle a_{01}*b_{11}}$ первый. Выбор k: = (i + j) mod n за PE (i, j) удовлетворяет этому ограничению для первого шага.
На первом этапе мы распределяем входные матрицы между процессорами в соответствии с предыдущим правилом.
В следующих итерациях мы выбираем новый k ': = (k + 1) mod n для каждого процессора. Таким образом, каждый процессор будет продолжать получать доступ к различным значениям матриц. Тогда необходимые данные всегда находятся на соседних процессорах. A PE (i, j) тогда нужно ${\displaystyle a}$ из PE (i, (j + 1) mod n) и ${\displaystyle b}$ из PE ((i + 1) mod n, j) для следующего шага. Это означает, что ${\displaystyle a}$ должен проходить циклически влево, а также ${\displaystyle b}$ циклически вверх. Результаты умножения суммируются в обычном порядке. После n шагов каждый процессор рассчитал все ${\displaystyle a_{ik}*b_{kj}}$ один раз и его сумма, таким образом, искомая ${\displaystyle c_{ij}}$.
После первоначального распределения каждого процессора должны быть сохранены только данные для следующего шага. Это промежуточный результат предыдущей суммы, ${\displaystyle a_{ik}}$ и ${\displaystyle b_{kj}}$. Это означает, что все три матрицы необходимо сохранить в памяти только после того, как они будут равномерно распределены между процессорами.
Обобщение
На практике у нас гораздо меньше процессоров, чем матричных элементов. Мы можем заменить элементы матрицы на подматрицы, чтобы каждый процессор обрабатывал больше значений. Скалярное умножение и сложение превращаются в последовательное умножение и сложение матриц. Ширина и высота подматриц будут ${\displaystyle N=n/{\sqrt {p}}}$.
Время выполнения алгоритма ${\displaystyle T{\mathcal {(n,p)}}=T_{coll}(n/N,p)+N*T_{seq}(n/N)+2(N-1)(T_{start}+T_{byte}(n/N)^{2})}$ , куда ${\displaystyle T_{coll}}$ - время начального распределения матриц на первом шаге, ${\displaystyle T_{seq}}$ это расчет промежуточных результатов и ${\displaystyle T_{start}}$ и ${\displaystyle T_{byte}}$ обозначает время, необходимое для установления соединения и передачи байта соответственно.
Недостатком алгоритма является то, что существует множество настроек подключения с небольшими размерами сообщений. Было бы лучше иметь возможность передавать больше данных в каждом сообщении.
Смотрите также









Систолический массив
Рекомендации









 Линн Эллиот Кэннон, Сотовый компьютер для реализации алгоритма фильтра Калмана, Технический отчет, к.т.н. Диссертация, Государственный университет Монтаны, 14 июля 1969 г.
 Gupta, H .; Садаяппан, П .: Коммуникационное эффективное умножение матриц на гиперкубах, dbpubs.stanford.edu
 4.2 Умножение матриц на машине с распределенной памятью, www.phy.ornl.gov
 Жан-Франсуа Пино, Планирование с учетом коммуникации на гетерогенных платформах master-worker, Кандидатская диссертация, октябрь 2010 г.
 Роберт А. ван де Гейн и Джеррелл Уоттс, SUMMA: масштабируемый универсальный алгоритм умножения матриц, Параллелизм: практика и опыт. Том 9, выпуск 4, страницы 255–274, апрель 1997 г.
внешняя ссылка









Лекция в Беркли
mu.oz.au