Данному образовательному сайту пришлось несколько раз менять свое имя. С 2011 года доступ к нему обеспечивается по URL
http://educomp.runnet.ru

emc.km.ru (2001-2007) ==> educomp.org.ru (2007-2011) ==> educomp.runnet.ru (2011-...)
Более подробно об истории сайта можно прочитать здесь.


Учебные модели компьютера



Модели (software):

"Е14" (parallel !!!)
"S9PU" (parallel)

Модели (hardware):






Награды сайта
Награды сайта

"Е14". Сумма массива: модель с общей памятью, схема A1S1

Задача. Имеется одномерный массив, состоящий из 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
адрес ячейки общей суммы
00002B09  out #0,p9 0 ==> порт 9запуск программы в PPU1
00022B0A  out #0,pAh 0 ==> порт Aзапуск программы в PPU2
00042B0B  out #0,pBh 0 ==> порт Bзапуск программы в PPU3
00062B0C  out #0,pCh 0 ==> порт Cзапуск программы в PPU4
00080A90 w: in p9,r0 порт 9 ==> R0 прочитать состояние PPU1
000A2410  cmp #1,r0 сравнить R0 с 1сравнить с 1 - состояние СТОП (счет окончен)
000C4DFA   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
0026AF18  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адрес начала массива в общем ОЗУ
000C2102  mov #0,r2 0 ==> R2обнуление суммы
000E
0010
9C0D
2048
c: call #read вызов п/п ROM
с адресом 2048
прочитать из общего ОЗУ (адрес из R1)
очередное слагаемое (в R0)
00120202   add r0,r2 R2+R0 ==> R2добавить очередное слагаемое
00142221  add #2,r1 R1+2 ==> R1адрес следующего слагаемого
00162313  sub #1,r3 R3-1 ==> R3уменьшить счетчик
00184DF8   bne c переход по <>0если <>0, то повторить цикл
001A0120  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) полученную сумму
0024AF18  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 раза.


Автор сайта - Евгений Александрович Еремин (Пермский государственный педагогический университет). e_eremin@yahoo.com