Алгоритм избегания общения

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

Формальная теория

Двухуровневая модель памяти

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

Имеется один процессор и два уровня памяти.
Память уровня 1 бесконечно велика. Память уровня 0 («кэш») имеет размер . $М$
В начале входные данные находятся на уровне 1. В конце выходные данные находятся на уровне 1.
Процессор может работать только с данными в кэше.
Цель — минимизировать передачу данных между двумя уровнями памяти.

Умножение матриц

^[2] Следствие 6.2:

Теорема — Даны матрицы размеров , тогда имеет сложность связи . $А,Б,В$ $n\times m,m\times k,n\times k$ $AB+C$ $\Omega (\max(mkn/M^{1/2},mk+kn+mk))$

Эта нижняя граница достижима путем умножения матриц.

Более общие результаты для других числовых операций линейной алгебры можно найти в ^[3] . Следующее доказательство взято из ^{[4] .}

Доказательство

Мы можем нарисовать граф вычислений как куб точек решетки, каждая точка имеет форму . Поскольку , вычисления требуют, чтобы процессор имел доступ к каждой точке внутри куба по крайней мере один раз. Таким образом, проблема становится покрытием точек решетки с минимальным количеством коммуникаций. $D=AB+C$ $(i,j,k)$ $D[i,k]=\sum _{j}A[i,j]B[j,k]+C[i,k]$ $AB+C$ $mnk$

Если большой, то мы можем просто загрузить все записи, а затем записать записи. Это неинтересно. $М$ $mn+nk+mk$ $нк$

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

В течение каждого сегмента процессор имеет доступ максимум к разным точкам из . $2M$ $А,Б,В$

Пусть — множество точек решетки, охваченных в течение этого сегмента. Тогда по неравенству Лумиса–Уитни , $E$

$|E|\leq {\sqrt {|\pi _{1}(E)||\pi _{2}(E)||\pi _{3}(E)|}}$ с ограничением . $\sum _{i}|\pi _{i}(E)|\leq 2M$

По неравенству средних арифметических и геометрических имеем , причем экстремум достигается при . $|E|\leq \left({\frac {2}{3}}M\right)^{3/2}$ $\pi _{i}(E)={\frac {2}{3}}M$

Таким образом, арифметическая интенсивность ограничена сверху величиной , где , и поэтому коммуникация ограничена снизу величиной . $CM^{1/2}$ $С=(2/3)^{3/2}$ ${\frac {nmk}{CM^{1/2}}}$

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

Мотивация

Рассмотрим следующую модель времени выполнения: ^[5]

Мера вычисления = Время на FLOP = γ
Мера коммуникации = Количество переданных слов данных = β

⇒ Общее время выполнения = γ·(кол-во FLOP ) + β·(кол-во слов)

Из того факта, что β >> γ, измеряемого во времени и энергии, стоимость связи доминирует над стоимостью вычислений. Технологические тенденции ^[6] указывают на то, что относительная стоимость связи увеличивается на различных платформах, от облачных вычислений до суперкомпьютеров и мобильных устройств. В отчете также прогнозируется, что разрыв между временем доступа DRAM и FLOPs увеличится в 100 раз в течение ближайшего десятилетия, чтобы сбалансировать потребление энергии между процессорами и DRAM. ^[1]

Скорость FLOP (γ)	Пропускная способность DRAM (β)	Пропускная способность сети (β)
59% / год	23% / год	26% / год

Потребление энергии увеличивается на порядки по мере продвижения вверх по иерархии памяти. ^[7]

Президент США Барак Обама упомянул алгоритмы избегания общения в бюджетном запросе Министерства энергетики на 2012 финансовый год в Конгресс: ^[1]

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

Цели

Алгоритмы избегания общения разрабатываются с целью достижения следующих целей:

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

Следующий простой пример ^[1] демонстрирует, как это достигается.

Пример умножения матриц

Пусть A, B и C — квадратные матрицы порядка n × n . Следующий наивный алгоритм реализует C = C + A * B:

для i = 1 до n для j = 1 до n для k = 1 до n С(i,j) = С(i,j) + А(i,k) * В(k,j)

Арифметическая стоимость (временная сложность): n ² (2 n − 1) для достаточно большого n или O( n ³ ).

Переписываем этот алгоритм с указанием стоимости связи на каждом шаге

для i = 1 до n {считывание строки i из A в быструю память} - n ² считываний для j = 1 до n {считывание C(i,j) в быструю память} - n ² считываний {считываем столбец j из B в быструю память} - n ³ считываний для k = 1 до n С(i,j) = С(i,j) + А(i,k) * В(k,j) {записать C(i,j) обратно в медленную память} - n ² записей

Быструю память можно определить как локальную память процессора ( кэш ЦП ) размером M, а медленную память можно определить как DRAM.

Стоимость связи (чтение/запись): n ³ + 3 n ² или O( n ³ )

Поскольку общее время выполнения = γ ·O( n ³ ) + β ·O( n ³ ) и β >> γ , стоимость связи является доминирующей. Блокированный (плиточный) алгоритм умножения матриц ^[1] уменьшает этот доминирующий член:

Блочное (плиточное) умножение матриц

Рассмотрим A, B и C как матрицы размером n / b на n / b, состоящие из подблоков размером b на b , где b называется размером блока; предположим, что три блока размером b на b помещаются в быстрой памяти.

для i = 1 до n/b для j = 1 до n/b {считываем блок C(i,j) в быструю память} - b ² × (n/b) ² = n ² считываний для k = 1 до n/b {считываем блок A(i,k) в быструю память} - b ² × (n/b) ³ = n ³ /b считываний {считываем блок B(k,j) в быструю память} - b ² × (n/b) ³ = n ³ /b считываний C(i,j) = C(i,j) + A(i,k) * B(k,j) - {выполнить матричное умножение на блоки} {записать блок C(i,j) обратно в медленную память} - b ² × (n/b) ² = n ² записей

Стоимость связи: 2 n ³ / b + 2 n ² чтения/записи << 2 n ³ арифметическая стоимость

Делаем b максимально возможным:

3 б ² ≤ М

мы достигаем следующей нижней границы связи:

3 ^1/2n ³ / M ^1/2 + 2 n ² или Ω (кол-во FLOP / M ^1/2 )

Предыдущие подходы к сокращению коммуникации

Большинство подходов, исследованных в прошлом для решения этой проблемы, основаны на методах планирования или настройки, которые направлены на перекрытие коммуникации с вычислениями. Однако этот подход может привести к улучшению максимум в два раза. Ghosting — это другой метод для сокращения коммуникации, при котором процессор сохраняет и вычисляет избыточные данные из соседних процессоров для будущих вычислений. Алгоритмы, игнорирующие кэш, представляют собой другой подход, введенный в 1999 году для быстрых преобразований Фурье ^[8], а затем распространенный на графовые алгоритмы, динамическое программирование и т. д. Они также применялись к нескольким операциям в линейной алгебре ^[9]^[10]^[11] как плотные LU и QR-факторизации. Разработка архитектурно-специфических алгоритмов — это еще один подход, который можно использовать для сокращения коммуникации в параллельных алгоритмах, и в литературе есть много примеров алгоритмов, которые адаптированы к заданной топологии коммуникации. ^[12]

Смотрите также

Локальность данных

Ссылки

^ abcde Деммель, Джим. «Алгоритмы избегания связи». 2012 SC Companion: Высокопроизводительные вычисления, сетевое хранение и анализ. IEEE, 2012.
^ Цзя-Вэй, Хонг; Кунг, ХТ (1981). «Сложность ввода-вывода». Труды тринадцатого ежегодного симпозиума ACM по теории вычислений - STOC '81 . Нью-Йорк, Нью-Йорк, США: ACM Press. С. 326–333 . doi :10.1145/800076.802486. S2CID 8410593.
^ Баллард, Г.; Карсон, Э.; Деммель, Дж.; Хёммен, М.; Найт, Н.; Шварц, О. (май 2014 г.). «Нижние границы связи и оптимальные алгоритмы для числовой линейной алгебры». Acta Numerica . 23 : 1– 155. doi :10.1017/s0962492914000038. ISSN 0962-4929. S2CID 122513943.
^ Деммель, Джеймс; Дин, Грейс (2018-04-24). «Коммуникационные оптимальные сверточные нейронные сети». arXiv : 1802.06905 [cs.DS].
^ Деммел, Джеймс и Кэти Йелик. «Избегание коммуникации (CA) и другие инновационные алгоритмы». Berkeley Par Lab: Прогресс в области параллельных вычислений: 243–250.
^ Бергман, Керен и др. «Исследование вычислений на уровне экзафлопсных технологий: технологические проблемы в вычислительных системах на уровне экзафлопсных технологий». Управление технологий обработки информации Агентства перспективных исследовательских проектов Министерства обороны США (DARPA IPTO), Технический отчет 15 (2008).
^ Шалф, Джон, Судип Досандж и Джон Моррисон. «Проблемы технологий эксафлопсных вычислений». Высокопроизводительные вычисления для вычислительной науки–VECPAR 2010. Springer Berlin Heidelberg, 2011. 1–25.
^ М. Фриго, CE Лейзерсон, Х. Прокоп и С. Рамачандран, «Кэш-обливионные алгоритмы», в FOCS '99: Труды 40-го ежегодного симпозиума по основам компьютерной науки, 1999. IEEE Computer Society.
^ С. Толедо, «Локальность ссылки в LU-разложении с частичным поворотом», SIAM J. Matrix Anal. Appl., т. 18, № 4, 1997.
^ Ф. Густавсон, «Рекурсия приводит к автоматической блокировке переменных для плотных алгоритмов линейной алгебры», IBM Journal of Research and Development, т. 41, № 6, стр. 737–755, 1997.
^ Э. Элмрот, Ф. Густавсон, И. Йонссон и Б. Кагстром, «Рекурсивные блочные алгоритмы и гибридные структуры данных для программного обеспечения библиотеки плотных матриц», SIAM Review, т. 46, № 1, стр. 3–45, 2004.
^ Григорий, Лора . «Введение в коммуникацию, избегающую алгоритмов линейной алгебры в высокопроизводительных вычислениях».

[Demmel_2012-1] Деммель, Джим. «Алгоритмы избегания связи». 2012 SC Companion: Высокопроизводительные вычисления, сетевое хранение и анализ. IEEE, 2012.

[2] Цзя-Вэй, Хонг; Кунг, ХТ (1981). «Сложность ввода-вывода». Труды тринадцатого ежегодного симпозиума ACM по теории вычислений - STOC '81 . Нью-Йорк, Нью-Йорк, США: ACM Press. С. 326–333 . doi :10.1145/800076.802486. S2CID 8410593.

[3] Баллард, Г.; Карсон, Э.; Деммель, Дж.; Хёммен, М.; Найт, Н.; Шварц, О. (май 2014 г.). «Нижние границы связи и оптимальные алгоритмы для числовой линейной алгебры». Acta Numerica . 23 : 1– 155. doi :10.1017/s0962492914000038. ISSN 0962-4929. S2CID 122513943.

[4] Деммель, Джеймс; Дин, Грейс (2018-04-24). «Коммуникационные оптимальные сверточные нейронные сети». arXiv : 1802.06905 [cs.DS].

[Demmel_2-5] Деммел, Джеймс и Кэти Йелик. «Избегание коммуникации (CA) и другие инновационные алгоритмы». Berkeley Par Lab: Прогресс в области параллельных вычислений: 243–250.

[DARPA_2008-6] Бергман, Керен и др. «Исследование вычислений на уровне экзафлопсных технологий: технологические проблемы в вычислительных системах на уровне экзафлопсных технологий». Управление технологий обработки информации Агентства перспективных исследовательских проектов Министерства обороны США (DARPA IPTO), Технический отчет 15 (2008).

[Shalf_2010-7] Шалф, Джон, Судип Досандж и Джон Моррисон. «Проблемы технологий эксафлопсных вычислений». Высокопроизводительные вычисления для вычислительной науки–VECPAR 2010. Springer Berlin Heidelberg, 2011. 1–25.

[Frigo_1999-8] М. Фриго, CE Лейзерсон, Х. Прокоп и С. Рамачандран, «Кэш-обливионные алгоритмы», в FOCS '99: Труды 40-го ежегодного симпозиума по основам компьютерной науки, 1999. IEEE Computer Society.

[Toledo_1997-9] С. Толедо, «Локальность ссылки в LU-разложении с частичным поворотом», SIAM J. Matrix Anal. Appl., т. 18, № 4, 1997.

[Gustavson_1997-10] Ф. Густавсон, «Рекурсия приводит к автоматической блокировке переменных для плотных алгоритмов линейной алгебры», IBM Journal of Research and Development, т. 41, № 6, стр. 737–755, 1997.

[Elmroth_2004-11] Э. Элмрот, Ф. Густавсон, И. Йонссон и Б. Кагстром, «Рекурсивные блочные алгоритмы и гибридные структуры данных для программного обеспечения библиотеки плотных матриц», SIAM Review, т. 46, № 1, стр. 3–45, 2004.

[Grigori_2014-12] Григорий, Лора . «Введение в коммуникацию, избегающую алгоритмов линейной алгебры в высокопроизводительных вычислениях».