Задача

В последовательных ячейках памяти лежат N целых чисел (одномерный массив).
Реализовать циклическую программу суммирования всех этих чисел.

Решение для однопроцессорной машины

Пусть в нашем распоряжении имеется традиционная однопроцессорная машина. Напишем для нее программу, приняв N=60. Для системы команд, принятой в "Е14", решение будет иметь приведенный ниже вид.

адрес	код	ассемблер		действия	комментарии
		метки	команды
		;memory=COMM ;BLOCK 0 ;CPUaddr=0000			память общая блок 0 начальный адрес 0
		N=60			количество слагаемых
0000 0002	01D0 003C		mov #N,r0	3C ==> R0	счетчик слагаемых
0004 0006	01D1 001A		mov #T,r1	1A ==> 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,s	R2 ==> (18)	сохранить сумму
0016	AF18		hlt	стоп	завершить программу
0018	AE97	s:	rw 1		ячейка для хранения суммы
001A 001C ...	0001 0002 0003 0004 0005 0006 0007 0008 0009 000A 000B 000C 000D 000E 000F 0010 0011 0012 0013 0014 0015 0016 0017 0018 0019 001A 001B 001C 001D 001E 001F 0020 0021 0022 0023 0024 0025 0026 0027 0028 0029 002A 002B 002C 002D 002E 002F 0030 0031 0032 0033 0034 0035 0036 0037 0038 0039 003A 003B 003C	T:	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 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 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 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		массив (значения 1, 2, ... 60)

Данная программа является "классикой жанра" и в особых комментариях не нуждается.

Результаты

В "Е14" принято допущение, что все имеющиеся команды выполняются за одинаковое время. В таком случае время выполнения программы пропорционально количеству выполненных команд. Для нашей задачи это количество легко подсчитать: 3 команды перед циклом, 2 - после и, наконец, цикл из 4 команд, повторяемый N раз. Получаем 5+4N, так что при N=60 это составит 245 команд. С этим числом мы в дальнейшем будем сравнивать результаты параллельных программ.

Решения для многопроцессорных машин

Теперь перейдем к моделированию на "Е14" многопроцессорной машины разных архитектур.

Более простой является архитектура с общей памятью, когда все процессоры - CPU и 4 PPU могут читать и записывать данные на нулевую страницу ОЗУ, которая является базовой для CPU. Возможны два варианта обмена с общей памятью:

1. каждый PPU сам обращается к общей памяти по мере необходимости;
2. CPU организует перенос блока данных из своей памяти в память PPU (или в обратном направлении).

Рассмотрим сначала первый случай. Программу для него можно изучить на отдельной странице. Там же обсуждаются результаты. Показано, что применение 5-процессорной вычислительной системы "Е14" с общей памятью ценой определенных усилий позволяет на данной задаче повысить быстродействие в 2 раза. Это лучшее, чего удалось достичь в экспериментах с данной задачей.

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

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

Программу для рассматриваемой архитектуры можно изучить на отдельной странице. Там же обсуждаются результаты. Показано, что применение многопроцессорной вычислительной системы "Е14" с распределенной памятью на задаче о сумме массива практически не дает выигрыша в быстродействии.

С последним алгоритмом был проведен любопытный эксперимент: из программы было удалено копирование четвертей массива, зато они сразу стали загружаться в нужные ОЗУ PPU вместе с программами. В итоге время выполнения такого "урезанного" алгоритма по сравнению с предыдущим уменьшилось в 3,6 раза! А его ускорение S по сравнению с одномашинным алгоритмом достигло 2,7 раза, что заметно лучше любого из алгоритмов, "честно" копирующих данные в ОЗУ PPU.

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

• насколько возможно уменьшать количество передаваемых между процессорами данных;
• увеличивать время "автономного счета" (применительно к нашей задаче - увеличивать размерность массива, тогда каждому процессору достанется больше слагаемых для суммирования).