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

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

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

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

Дополнительно укажем, что для чтения из общей памяти в ПЗУ каждого PPU имеется процедура READ. Она временно подключает общую страницу ОЗУ, считывает содержимое адреса, который задается в регистре R1, и помещает прочитанное число в R0. Аналогичная процедура WRITE служит для записи значения из R0 по адресу из R1. Описанные процедуры состоят из нескольких машинных команд, так что обмен с общей памятью требует в разы больше времени, чем с обмен с "собственной". (Но, тем не менее, в модели "Е14" это более быстрый механизм, чем обмен через шину при распределенной памяти и блочный обмен при общей).

Главная программа для CPU достаточно проста.

адрес	код	ассемблер		действия	комментарии
		метки	команды
		;memory=COMM ;BLOCK 0 ;CPUaddr=0			память общая блок 0 (для CPU) начальный адрес - 0
		s4=F6h s3=F8h s2=FAh s1=FCh s=FEh			адрес ячейки суммы от PPU1 адрес ячейки суммы от PPU2 адрес ячейки суммы от PPU3 адрес ячейки суммы от PPU4 адрес ячейки общей суммы
0000	2B09		out #0,p9	0 ==> порт 9	запуск программы в PPU1
0002	2B0A		out #0,pAh	0 ==> порт A	запуск программы в PPU2
0004	2B0B		out #0,pBh	0 ==> порт B	запуск программы в PPU3
0006	2B0C		out #0,pCh	0 ==> порт C	запуск программы в PPU4
0008	0A90	w:	in p9,r0	порт 9 ==> R0	прочитать состояние PPU1
000A	2410		cmp #1,r0	сравнить R0 с 1	сравнить с 1 - состояние СТОП (счет окончен)
000C	4DFA		bne w	переход по <>0	если <>0, то повторить цикл ожидания
000E 0010 0012	01EE 00FC 00FE		mov s1,s	(s1) ==> (s)	(начинаем считать итоговую сумму!) скопировать сумму от PPU1 в ячейку s
0014 0016 0018	02EE 00FA 00FE		add s2,s	(s) + (s2) ==> (s)	добавить сумму от PPU2
001A 001C 001E	02EE 00F8 00FE		add s3,s	(s) + (s3) ==> (s)	добавить сумму от PPU3
0020 0022 0024	02EE 00F6 00FE		add s4,s	(s) + (s4) ==> (s)	добавить сумму от PPU4
0026	AF18		hlt	стоп	завершить программу

Мы видим, что программа для центрального процессора состоит из трех мало зависящих друг от друга частей:

• запуск программ в каждом PPU;
• ожидание, пока PPU1 сосчитает результат;
• суммирование четырех полученных в PPU сумм.

Конечно, на втором шаге CPU "тупо" (как сейчас любит говорить молодежь) тратит время. А мог бы вместо этого сосчитать сумму некоторых слагаемых. (Это сильно экономит время по двум причинам: во-первых, меньшее число слагаемых суммирует каждый PPU; а во-вторых, меньшее количество чисел передается из общей памяти PPU). Но это уже будет другой алгоритм.

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

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

адрес	код	ассемблер		действия	комментарии
		метки	команды
		;BLOCK 1 ;PPU=0001 ;CPUaddr=0300 ;PPUaddr=0000			блок 1 для PPU1 адрес буфера чтения в ОЗУ CPU - 300 начальный адрес загрузки в PPU1 - 0
		N/4=15 ;n=60 s1=FCh ;(s2=FAh, s3=F8h, s4=F6h) T=100h ;(T1/4=11Eh, T2/4=13Ch, ;T3/4=15Ah) SP0=3F0h read=2048h write=2050h			1/4 от количества слагаемых адрес ячейки 1-й суммы в общем ОЗУ (адреса для PPU2-4 будут другие!) адрес начала 1-й четверти массива       в общем ОЗУ (адреса для PPU2-4 будут другие!) адрес для указателя стека SP адрес подпрограммы READ в ROM адрес подпрограммы WRITE в ROM
0000 0002	0E6D 03F0		toSP #SP0	3F0 ==> SP	задать SP для применения подпрограмм
0004 0006	01D3 000F		mov #N/4,r3	F ==> R3	счетчик слагаемых (60/4=15)
0008 000A	01D1 0100		mov #T,r1	100 ==> R1	адрес начала массива в общем ОЗУ
000C	2102		mov #0,r2	0 ==> R2	обнуление суммы
000E 0010	9C0D 2048	c:	call #read	вызов п/п ROM с адресом 2048	прочитать из общего ОЗУ (адрес из R1) очередное слагаемое (в R0)
0012	0202		add r0,r2	R2+R0 ==> R2	добавить очередное слагаемое
0014	2221		add #2,r1	R1+2 ==> R1	адрес следующего слагаемого
0016	2313		sub #1,r3	R3-1 ==> R3	уменьшить счетчик
0018	4DF8		bne c	переход по <>0	если <>0, то повторить цикл
001A	0120		mov r2,r0	R2 ==> R0	скопировать сумму в R0 (для WRITE)
001C 001E	01D1 00FC		mov #s1,r1	FC ==> R1	адрес ячейки в общем ОЗУ для суммы s1 (в PPU2 - для s2 и т.д.)
0020 0022	9C0D 2050		call #write	вызов п/п ROM с адресом 2050	записать из R0 в общее ОЗУ (адрес из R1) полученную сумму
0024	AF18		hlt	стоп	завершить программу

Далее располагаются аналогичные блоки 2-4 для PPU2-PPU4 соответственно. Они отличаются только начальными адресами для обработки массива (вместо T - T1/4 и т.д. - см. секцию констант в блоке 1) и адресом записи полученной суммы (вместо s1 - s2 и т.д.).

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

адрес	код	ассемблер		действия	комментарии
		метки	команды
		;BLOCK 5 ;CPUaddr=0100			блок 5 начальный адрес массива в 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) приведенные выше программы выполняются за время 156 команд. Следовательно, по сравнению с однопроцессорной машиной выигрыш здесь составляет S = 245/156, т.е. примерно в 1,6 раза.

Если в программу CPU добавить цикл суммирования части массива, т.е. использовать центральный процессор как дополнительный вычислитель, время счета уменьшится. Так при обсуждаемых значениях N и P при равномерном распределении чисел (по 60/5=12, алгоритм P4+) оно будет эквивалентно 130 командам. Если же распределить нагрузку так, что CPU обработает 20 чисел, а PPU - по 10 (схема A1S1m), то время удается сократить до 111 команд. Это лучшее, что удалось получить! Эффект связан с тем, что CPU непосредственно работает с общей страницей памяти, а значит, получает данные из нее быстрее, чем PPU. Но даже в этом случае ускорение S = 245/111, что составит примерно 2,2 раза.