Задача. Имеется одномерный массив, состоящий из N=60 целых чисел. Найти их сумму.

Как можно построить параллельный алгоритм суммирования массива, если вы работаете с многопроцессорной машиной, у которой распределенная память (архитектура A2 в обозначениях "Е14")?

Схема может быть, например, такой. Пусть у нас P процессоров. Тогда делим массив на P равных частей (по N/P чисел), каждую из которых сумирует отдельный процессор.

Но прежде чем начинать вычисления, надо в память каждого PPU скопировать "его" четверть массива. В данном алгоритме для повышения скорости это делается так. Масссивы с суммируемыми числами во всех PPU начинаются с одного и того же адреса; выставим этот адрес на шину адреса. Затем поместим на шину данных первое число (из первой 1/4 массива) и переведем PPU1 в режим IN - чтение данных с шины. PPU1 прочитает число и сохранит его в свою память. А CPU в это время рассчитает адрес первого элемента во второй 1/4 массива: нетрудно сообразить, что имеющийся адрес надо увеличить на 15 чисел * 2 байта (каждое) = 30 = 1Eh байт. Прочитаем теперь содержимое этого адреса на шину данных и запустим на чтение PPU2. Далее аналогичным образом передадим в PPU3 первый элемент третьей 1/4, а в PPU4 - последней 1/4. При этом адрес будет увеличен на 30*3 = 90. А теперь уменьшим его на 88 = 58h. Тем самым мы получим адрес второго элемента в первой 1/4. Увеличим адрес на шине адреса для ОЗУ PPU на 2 и заново повторим описанный выше цикл. На место попадут вторые числа всех четвертей и т.д.

Следующим шагом CPU запускает в каждом PPU программу суммирования.После вычисления суммы каждый PPU помещает ее в ячейку своей памяти ("перед массивом"). Дождавшись завершения вычислений, CPU читает каждую из сумм к себе в память и затем находит "сумму всех сумм".

Назовем предложенную схему вычислений схемой A2S2. В приводимых ниже листингах принято P=4 (в суммировании принимают участие все четыре PPU). Будем также сейчас предполагать, что CPU не участвует в непосредственном суммировании элементов массива, хотя это возможно.

Программа для всех PPU одинакова и практически совпадает (за исключением количества суммируемых чисел) с программой "однопроцессорного" суммирования.

адрес	код	ассемблер		действия	комментарии
		метки	команды
		;memory=DIST ;BLOCK 0 ;PPU=4321 ;CPUaddr=0380 ;PPUaddr=0000			память распределенная блок 0 для всех PPU 1-4 адрес буфера чтения в ОЗУ CPU - 380 начальный адрес загрузки в PPU - 0
		N/4=15 ;n=60 sum=18h Tp=1Ah			1/4 от количества слагаемых адрес ячейки для суммы в ОЗУ PPU адрес начала массива в ОЗУ PPU
0000 0002	01D0 000F		mov #N/4,r0	3C ==> R0	счетчик слагаемых (60/4=15)
0004 0006	01D1 001A		mov #Tp,r1	#Tp ==> R1	адрес начала массива
0008	2102		mov #0,r2	0 ==> R2	обнуление суммы
000A	0252	c:	add (r1),r2	R2+(R1) ==> R2	добавить очередное слагаемое
000C	2221		add #2,r1	R1+2 ==> R1	адрес следующего слагаемого
000E	2310		sub #1,r0	R0-1 ==> R0	уменьшить счетчик
0010	4DF8		bne c	переход по <>0	если <>0, то повторить цикл
0012 0014	012E 0018		mov r2,sum	R2 ==> (sum)	сохранить сумму
0016	AF18		hlt	стоп	завершить программу
0018		sum:			ячейка для хранения суммы
001A ...		Tp:			начало 1/4 массива в PPU

Главная программа для CPU, как уже описывалось выше, состоит из нескольких частей.

• "Раздача" чисел в PPU (адреса 0-33).
• Запуск программ суммирования в каждом PPU (34-3B).
• Ожидание, пока PPU1 закончит вычисления (3C-41).
• Чтение сумм из PPU в CPU и сохранение их в "своем" ОЗУ (42-6D).
• Вычисление итоговой суммы (6E-87).

адрес	код	ассемблер		действия	комментарии
		метки	команды
		;BLOCK 1 ;CPUaddr=0			блок 1 (для CPU) начальный адрес - 0
		N/4=15 ;N=60 T=100h sh+=1Eh sh3-=58h sum=18h Tp=1Ah @s4=F6h @s3=F8h @s2=FAh @s1=FCh @s=FEh			1/4 от количества слагаемых адрес начала массива в ОЗУ CPU смещение по массиву на 15 чисел вперед смещение по массиву на 44 числа назад адрес ячейки суммы в ОЗУ PPU адрес 1/4 массива в ОЗУ PPU адрес ячейки суммы от PPU1 в ОЗУ CPU адрес ячейки суммы от PPU2 в ОЗУ CPU адрес ячейки суммы от PPU3 в ОЗУ CPU адрес ячейки суммы от PPU4 в ОЗУ CPU адрес ячейки общей суммы в ОЗУ CPU
0000 0002	01D0 0100		mov #T,r0	100 ==> R0	адрес начала массива в CPU
0004 0006	01D1 001A		mov #Tp,r1	1A ==> R1	адрес начала 1/4 массива в PPU
0008 000A	01D2 000F		mov #N/4,r2	F ==> R2	счетчик слагаемых (60/4=15)
000C	0B16	c:	out r1,p6	R1 ==> порт 6	адрес ОЗУ в PPU на шину адреса
000E	0B47		out (r0),p7	(R0) ==> порт 7	очередной элемент массива на шину данных
0010	2B29		out #2,p9	2 ==> порт 9	PPU1 в режим IN (чтение данных с шины)
0012 0014	02D0 001E		add #sh+,r0	R0+1E ==> R0	адрес элемента во второй 1/4 массива
0016	0B47		out (r0),p7	(R0) ==> порт 7	очередной элемент массива на шину данных
0018	2B2A		out #2,pAh	2 ==> порт A	PPU2 в режим IN (чтение данных с шины)
001A 001C	02D0 001E		add #sh+,r0	R0+1E ==> R0	адрес элемента в третьей 1/4 массива
001E	0B47		out (r0),p7	(R0) ==> порт 7	очередной элемент массива на шину данных
0020	2B2B		out #2,pBh	2 ==> порт B	PPU3 в режим IN (чтение данных с шины)
0022 0024	02D0 001E		add #sh+,r0	R0+1E ==> R0	адрес элемента в четвертой 1/4 массива
0026	0B47		out (r0),p7	(R0) ==> порт 7	очередной элемент массива на шину данных
0028	2B2C		out #2,pCh	2 ==> порт C	PPU4 в режим IN (чтение данных с шины)
002A 002C	03D0 0058		sub #sh3-,r0	R0-58 ==> R0	обратно в первую 1/4 массива и там переход к следующему элементу
002E	2221		add #2,r1	R1+2 ==> R1	следующий адрес для ОЗУ PPU
0030	2312		sub #1,r2	R2-1 ==> R2	уменьшить счетчик
0032	7DD8		bg с	переход по >0	если >0, то повторить цикл
0034	2B09		out #0,p9	0 ==> порт 9	запуск программы в PPU1
0036	2B0A		out #0,pAh	0 ==> порт A	запуск программы в PPU2
0038	2B0B		out #0,pBh	0 ==> порт B	запуск программы в PPU3
003A	2B0C		out #0,pCh	0 ==> порт C	запуск программы в PPU4
003C	0A90	w:	in p9,r0	порт 9 ==> R0	прочитать состояние PPU1
003E	2410		cmp #1,r0	сравнить R0 с 1	сравнить с 1 - состояние СТОП (счет окончен)
0040	4DFA		bne w	переход по <>0	если <>0, то повторить цикл ожидания
0042 0044	0BD6 0018		out #sum,p6	18 ==> порт 6	(читаем результаты!) адрес суммы в ОЗУ PPU на шину адреса
0046	2B39		out #3,p9	3 ==> порт 9	PPU1 в режим OUT (запись данных на шину)
0048	0000		nop	нет операции	ждем готовности данных на шине
004A	0000		nop	нет операции	ждем готовности данных на шине
004C 004E	0A7E 00FC		in p7,@s1	порт 7 ==> (@s1)	чтение суммы из ОЗУ PPU1
0050	2B3A		out #3,pAh	3 ==> порт A	PPU2 в режим OUT (запись данных на шину)
0052	0000		nop	нет операции	ждем готовности данных на шине
0054	0000		nop	нет операции	ждем готовности данных на шине
0056 0058	0A7E 00FA		in p7,@s2	порт 7 ==> (@s2)	чтение суммы из ОЗУ PPU2
005A	2B3B		out #3,pBh	3 ==> порт B	PPU3 в режим OUT (запись данных на шину)
005C	0000		nop	нет операции	ждем готовности данных на шине
005E	0000		nop	нет операции	ждем готовности данных на шине
0060 0062	0A7E 00F8		in p7,@s3	порт 7 ==> (@s3)	чтение суммы из ОЗУ PPU3
0064	2B3C		out #3,pCh	3 ==> порт C	PPU4 в режим OUT (запись данных на шину)
0066	0000		nop	нет операции	ждем готовности данных на шине
0068	0000		nop	нет операции	ждем готовности данных на шине
006A 006C	0A7E 00F6		in p7,@s4	порт 7 ==> (@s4)	чтение суммы из ОЗУ PPU4
006E 0070 0072	01EE 00FC 00FE		mov @s1,@s	(@s1) ==> (@s)	(начинаем считать итоговую сумму!) скопировать сумму от PPU1 в ячейку @s
0074 0076 0078	02EE 00FA 00FE		add @s2,@s	(@s) + (@s2) ==> (@s)	добавить сумму от PPU2
007A 007C 007E	02EE 00F8 00FE		add @s3,@s	(@s) + (@s3) ==> (@s)	добавить сумму от PPU3
0080 0082 0084	02EE 00F6 00FE		add @s4,@s	(@s) + (@s4) ==> (@s)	добавить сумму от PPU4
0086	AF18		hlt	стоп	завершить программу

Заметим, что в данном алгоритме CPU не производит суммирования элементов массива.

Программы для каждого PPU, суммируя по 15 чисел, проделывают строго одинаковое количество команд, а стартуют с разницей в одну команду. Это позволяет проверять завершение вычислений только для PPU1.

Последний блок 2 содержит суммируемый массив. Он размещен начиная с адреса 100h.

адрес	код	ассемблер		действия	комментарии
		метки	команды
		;BLOCK 2 ;CPUaddr=0100			блок 2 начальный адрес массива в CPU - 100
0100 0102 ...	0001 0002 0003 0004 0005 0006 0007 0008 0009 000A 000B 000C 000D 000E 000F	a:	dw 1 dw 2 dw 3 dw 4 dw 5 dw 6 dw 7 dw 8 dw 9 dw Ah dw Bh dw Ch dw Dh dw Eh dw Fh		массив (значения 1, 2, ... 60) Первая четверть (60/4=15 чисел) - для PPU1.
011E 0120 ...	0010 0011 0012 0013 0014 0015 0016 0017 0018 0019 001A 001B 001C 001D 001E	a1/4:	dw 10h dw 11h dw 12h dw 13h dw 14h dw 15h dw 16h dw 17h dw 18h dw 19h dw 1Ah dw 1Bh dw 1Ch dw 1Dh dw 1Eh		Вторая четверть - для PPU2.
013C 013E ...	001F 0020 0021 0022 0023 0024 0025 0026 0027 0028 0029 002A 002B 002C 002D	a2/4:	dw 1Fh dw 20h dw 21h dw 22h dw 23h dw 24h dw 25h dw 26h dw 27h dw 28h dw 29h dw 2Ah dw 2Bh dw 2Ch dw 2Dh		Третья четверть - для PPU3.
015A 015C ...	002E 002F 0030 0031 0032 0033 0034 0035 0036 0037 0038 0039 003A 003B 003C	a3/4:	dw 2Eh dw 2Fh dw 30h dw 31h dw 32h dw 33h dw 34h dw 35h dw 36h dw 37h dw 38h dw 39h dw 3Ah dw 3Bh dw 3Ch		Четвертая четверть - для PPU4.

Результаты. Для N=60 и P=4 (CPU не суммирует, алгоритм P4) приведенные выше программы выполняются за время 335 команд. Это больше(!), чем у однопроцессорной программы, где время эквивалентно времени выполнения 245 команд.

Эксперименты с алгоритмом позволили уменьшить его время до 240 команд. Главная идея состояла в том, что в PPU каждое принятое число не записывалось в ОЗУ ради последующего цикла суммирования, а сразу добавлялось к сумме (A2S1).

Значат ли эти цифры, что архитектура с распределенной памятью хуже, чем с общей? Видимо, нет. Просто заложенные в "Е14" (разные!) модели архитектуры получились такими. Их не стоит количественно сравнивать между собой.