Алгоритм предотвращения общения
Алгоритмы предотвращения связи сводят к минимуму перемещение данных в иерархии памяти для улучшения времени ее работы и энергопотребления. Они сводят к минимуму две затраты (с точки зрения времени и энергии): арифметические и коммуникационные. Коммуникация в этом контексте относится к перемещению данных либо между уровнями памяти, либо между несколькими процессорами по сети. Это намного дороже, чем арифметика. [1]
Из-за того, что β >> γ , измеренное во времени и энергии, стоимость связи преобладает над стоимостью вычислений. Технологические тенденции [3] указывают на то, что относительная стоимость связи увеличивается на различных платформах, от облачных вычислений до суперкомпьютеров и мобильных устройств. В отчете также прогнозируется, что разрыв между временем доступа к DRAM и количеством FLOP увеличится в 100 раз в ближайшее десятилетие, чтобы сбалансировать энергопотребление между процессорами и DRAM. [1]
Потребление энергии увеличивается на порядки по мере того, как мы поднимаемся выше в иерархии памяти. [4] Президент США Барак Обама процитировал алгоритмы предотвращения общения в бюджетном запросе Министерства энергетики на 2012 финансовый год Конгрессу: [1]
Новый алгоритм повышает производительность и точность вычислительных систем экстремального масштаба. В современных компьютерных архитектурах связь между процессорами занимает больше времени, чем выполнение арифметической операции с плавающей запятой данным процессором. Исследователи ASCR разработали новый метод, основанный на широко используемых методах линейной алгебры, для минимизации связи между процессорами и иерархией памяти путем переформулирования шаблонов связи, указанных в алгоритме. Этот метод был реализован в среде TRILINOS, высоко оцененном пакете программного обеспечения, которое предоставляет исследователям по всему миру функциональные возможности для решения крупномасштабных сложных мультифизических задач.
Пусть A, B и C — квадратные матрицы порядка n × n . Следующий наивный алгоритм реализует C = C + A * B:
Быстрая память может быть определена как локальная память процессора ( кэш ЦП ) размера M, а медленная память может быть определена как DRAM.
