Параллельная обработка данных


Легко ли достичь пиковой производительности компьютера CRAY C90? - часть 2


Do i=1,n CALL SUBR(A,B) End Do

Анализ узких мест в архитектуре компьютера CRAY C90 (один процессор)

Анализ факторов, снижающих реальную производительность компьютеров, начнем с обсуждения известного закона Амдала. Смысл его сводится к тому, что время работы программы определяется ее самой медленной частью. В самом деле, предположим, что одна половина некоторой программы - это сугубо последовательные вычисления. Тогда вне всякой зависимости от свойств другой половины, которая может идеально векторизоваться либо вообще выполняться мгновенно, ускорения работы всей программы более чем в два раза мы не получим.

Влияние данного фактора надо оценивать с двух сторон. Во-первых, по природе самого алгоритма все множество операций программы Г разбивается на последовательные операции Г1 и операции Г2, исполняемые в векторном режиме. Если доля последовательных операций велика, то программист сразу должен быть готов к тому, что большого ускорения он никакими средствами не получит и, быть может, следует уже на этом этапе подумать об изменении алгоритма.

Во-вторых, не следует сбрасывать со счетов и качество компилятора, который может не распознать векторизуемость отдельных конструкций и, тем самым, часть "потенциально хороших" операций из Г2 перенести в Г1.

Прекрасной иллюстрацией к действию закона Амдала могут служить наши эксперименты, которые мы проводили с алгоритмом компактного размещения данных. Задача ставилась следующим образом: l разрядов из каждого элемента массива A(i) надо плотно упаковать по элементам массива B. Если очередная секция из l разрядов целиком не помещается в очередном элементе B(j), то оставшаяся часть должна быть перенесена в следующий элемент B(j+1) (примерная схема данного преобразования показана на рис.1). Общее число элементов массива A было порядка одного миллиона.

Рис.1 Примерная схема сжатия данных

Первоначально был реализован самый простой алгоритм, который перебирает по очереди все элементы массива A, для каждого выделяет битовую секцию из l разрядов, записывает в соответствующий элемент B(j) и, если необходимо, увеличивает j на единицу, записывая остаток из текущей секции в следующий элемент массива B.


Начало  Назад  Вперед



Книжный магазин