Вычислительная математика Учебно-практическая задача Пути достижения параллелизма Моделирование и анализ параллельных вычислений Каскадная схема суммирования

Процессы и ресурсы Учебно-практическая задача

Учебно-практическая задача: Решение дифференциальных уравнений в частных производных

Порождаемый на основе такого подхода метод вычислений в самом общем виде может быть описан следующим образом (блоки образуют в области расчётов прямоугольную решётку размера NBxNB):

 // Алгоритм 6.6 // NB количество блоков do { // нарастание 
волны (размер волны равен nx+1) for ( nx =0; nx<NB; nx++ ) { 
#pragma omp parallel for shared(nx) private(i,j) for ( i=0; i<nx+1; 
i++ ) { j = nx – i; // <обработка блока с координатами (i,j)> 
} // конец параллельной области } // затухание волны for ( nx=NB-2; nx>-1; 
nx-- ) { #pragma omp parallel for shared(nx) private(i,j) for ( 
i=0; i<nx+1; i++ ) { j = 2*(NB-1) - nx – i; // <обработка 
блока с координатами (i,j)> } // конец параллельной области } // <определение 
погрешности вычислений> } while ( dmax > eps ); 

Вычисления в предлагаемом алгоритме происходят в соответствии с волновой схемой обработки данных – вначале вычисления выполняются только в левом верхнем блоке с координатами (0,0), далее для обработки становятся доступными блоки с координатами (0,1) и (1,0) и т.д. – см. результаты экспериментов в табл. 6.3.

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

Наилучшие показатели использования кэша будут достигаться, если в кэше будет достаточно места для размещения не менее трех строк блока (при обработке строки блоки блока используются данные трех строк блока одновременно). Тем самым, исходя из размера кэша, можно определить рекомендуемый максимально-возможный размер блока. Так, например, при кэше 8 Кб и 8-байтовых значениях данных этот размер составит приближенно 300 (8Кб/3/8). Можно определить и минимально-допустимый размер блока из условия совпадения размеров строк кэша и блока. Так, при размере строки кэша 256 байт и 8-байтовых значениях данных размер блока должен быть кратен 32.

Последнее замечание следует сделать о взаимодействии граничных узлов блоков. Учитывая граничное взаимодействие, соседние блоки целесообразно обрабатывать на одних и тех же процессорах. В противном случае, можно попытаться так определить размеры блоков, чтобы объем пересылаемых между процессорами граничных данных был минимален. Так, при размере строки кэша в 256 байт, 8-байтовых значениях данных и размере блока 64х64 объем пересылаемых данных 132 строки кэша, при размере блока 128х32 – всего 72 строки. Такая оптимизация имеет наиболее принципиальное значение при медленных операциях пересылки данных между кэшами процессоров, т.е. для систем с неоднородным доступом к памяти, (nonuniform memory access - NUMA).

Существуют два способа оценки пиковой производительности компьютера. Один из них опирается на число команд, выполняемых компьютером в единицу времени. Единицей измерения, как правило, является MIPS (Million Instructions Per Second). Производительность, выраженная в MIPS, говорит о скорости выполнения компьютером своих же инструкций. Но, во-первых, заранее не ясно, в какое количество инструкций отобразится конкретная программа, а, во-вторых, каждая программа обладает своей спецификой, и число команд от программы к программе может меняться очень сильно

Информатика, черчение, математика