Масштабируемая местность
компьютерное программное обеспечение Говорят, что демонстрирует масштабируемую локальность. [1] если он сможет продолжать использовать процессоры , опережающие их системы памяти , для решения еще более серьезных проблем. Этот термин представляет собой высокопроизводительный однопроцессорный аналог использования масштабируемого параллелизма для обозначения программного обеспечения , в котором для решения более крупных задач можно использовать все большее количество процессоров.
Обзор
[ редактировать ]Рассмотрим шаблоны использования памяти в следующем гнезде циклов (итеративное двумерное вычисление трафарета ):
for t := 0 to T do
for i := 1 to N-1 do
for j := 1 to N-1 do
new(i,j) := (A(i-1,j) + A(i,j-1) + A(i,j) + A(i,j+1) + A(i+1,j)) * .2
end
end
for i := 1 to N-1 do
for j := 1 to N-1 do
A(i,j) := new(i,j)
end
end
end
Все гнездо циклов касается примерно 2*N**2 элементов массива и выполняет около 5*T*N**2 операций с плавающей запятой. Таким образом, общий вычислительный баланс (отношение вычислений с плавающей запятой к используемым ячейкам памяти с плавающей запятой) всего этого гнезда циклов составляет около 5T/2. Когда баланс вычислений является функцией размера задачи, как здесь, говорят, что код имеет масштабируемый баланс вычислений . Здесь мы могли бы достичь любого желаемого баланса вычислений, просто выбрав достаточно большое T .
Однако, когда N велико, этот код все равно не будет демонстрировать хорошее повторное использование кэша из-за плохой локальности ссылки : к тому времени, когда new(1,1) понадобится во втором присваивании, или к тому моменту, когда на втором временном шаге будет выполнено первое задание, строка кэша, содержащая new(1,1), будет перезаписана какой-либо другой частью одного из массивов.
Мозаичное размещение первого гнезда циклов i/j может повысить производительность кэша. но только с ограниченным коэффициентом, поскольку вычислительный баланс этого гнезда составляет около 5/2. Чтобы обеспечить очень высокую степень локальности, например 500 (чтобы эффективно запустить этот код с массивом, который не помещается в ОЗУ и передается в виртуальную память), мы должны повторно использовать значения через временные шаги.
Оптимизация по временным шагам изучалась в ряде составителей исследований; см. работу Воннакотта, [1] [2] Сун и Ли, [3] или Садаяппан и др. [4] для получения подробной информации о некоторых подходах к таймингу . Воннакотт [1] продемонстрировал, что тайлинг времени можно использовать для оптимизации наборов внешних данных; в принципе, любой из этих подходов [2] [3] [4] должен иметь возможность достичь произвольно высокой локальности памяти, не требуя, чтобы весь массив помещался в кэш (однако требования к кэшу растут с увеличением требуемой локальности). Многопроцессорные методы, упомянутые выше [2] [4] в принципе должен одновременно обеспечивать масштабируемую локальность и масштабируемый параллелизм .
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с Дэвид Воннакотт. Достижение масштабируемой локальности с искажением времени. Международный журнал параллельного программирования 30.3 (2002 г.)
- ^ Перейти обратно: а б с Дэвид Воннакотт. Использование Time Skewing для устранения простоя из-за пропускной способности памяти и ограничений сети. Международный симпозиум по параллельной и распределенной обработке, 2000 г.
- ^ Перейти обратно: а б Юнхун Сун и Чжиюань Ли. Новые методы тайлирования для улучшения временной локальности кэша. ПЛДИ '99
- ^ Перейти обратно: а б с Шрирам Кришнамурти, Мутху Баскаран, Удай Бондхугула, Дж. Рамануджам, Атанас Рунтев и П. Садаяппан. Эффективное автоматическое распараллеливание трафаретных вычислений. ПЛДИ '07