Данному образовательному сайту пришлось несколько раз менять свое имя. С 2022 года доступ к нему обеспечивается по URL
emc.orgfree.com

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


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



Модели (software):

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

Модели (hardware):






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

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

Задача. Имеется одномерный массив, состоящий из 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адрес начала массива
00082102  mov #0,r2 0 ==> R2обнуление суммы
000A0252 c: add (r1),r2 R2+(R1) ==> R2добавить очередное слагаемое
000C2221  add #2,r1 R1+2 ==> R1адрес следующего слагаемого
000E2310  sub #1,r0 R0-1 ==> R0уменьшить счетчик
00104DF8   bne c переход по <>0если <>0, то повторить цикл
0012
0014
012E
0018
 mov r2,sum R2 ==> (sum)сохранить сумму
0016AF18  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,r0100 ==> R0 адрес начала массива в CPU
0004
0006
01D1
001A
 mov #Tp,r11A ==> R1 адрес начала 1/4 массива в PPU
0008
000A
01D2
000F
 mov #N/4,r2F ==> R2 счетчик слагаемых (60/4=15)
000C0B16 c: out r1,p6 R1 ==> порт 6 адрес ОЗУ в PPU на шину адреса
000E0B47  out (r0),p7 (R0) ==> порт 7очередной элемент массива на шину данных
00102B29  out #2,p92 ==> порт 9 PPU1 в режим IN (чтение данных с шины)
0012
0014
02D0
001E
 add #sh+,r0 R0+1E ==> R0адрес элемента во второй 1/4 массива
00160B47  out (r0),p7 (R0) ==> порт 7очередной элемент массива на шину данных
00182B2A  out #2,pAh2 ==> порт A PPU2 в режим IN (чтение данных с шины)
001A
001C
02D0
001E
 add #sh+,r0 R0+1E ==> R0адрес элемента в третьей 1/4 массива
001E0B47  out (r0),p7 (R0) ==> порт 7очередной элемент массива на шину данных
00202B2B  out #2,pBh2 ==> порт B PPU3 в режим IN (чтение данных с шины)
0022
0024
02D0
001E
 add #sh+,r0 R0+1E ==> R0адрес элемента в четвертой 1/4 массива
00260B47  out (r0),p7 (R0) ==> порт 7очередной элемент массива на шину данных
00282B2C  out #2,pCh2 ==> порт C PPU4 в режим IN (чтение данных с шины)
002A
002C
03D0
0058
 sub #sh3-,r0 R0-58 ==> R0обратно в первую 1/4 массива
и там переход к следующему элементу
002E2221  add #2,r1 R1+2 ==> R1следующий адрес для ОЗУ PPU
00302312  sub #1,r2 R2-1 ==> R2уменьшить счетчик
00327DD8   bg с переход по >0если >0, то повторить цикл
00342B09  out #0,p9 0 ==> порт 9запуск программы в PPU1
00362B0A  out #0,pAh 0 ==> порт Aзапуск программы в PPU2
00382B0B  out #0,pBh 0 ==> порт Bзапуск программы в PPU3
003A2B0C  out #0,pCh 0 ==> порт Cзапуск программы в PPU4
003C0A90 w: in p9,r0 порт 9 ==> R0 прочитать состояние PPU1
003E2410  cmp #1,r0 сравнить R0 с 1сравнить с 1 - состояние СТОП (счет окончен)
00404DFA   bne w переход по <>0если <>0, то повторить цикл ожидания
0042
0044
0BD6
0018
  out #sum,p618 ==> порт 6 (читаем результаты!)
адрес суммы в ОЗУ PPU на шину адреса
00462B39 out #3,p93 ==> порт 9 PPU1 в режим OUT (запись данных на шину)
00480000 nop нет операцииждем готовности данных на шине
004A0000 nop нет операцииждем готовности данных на шине
004C
004E
0A7E
00FC
  in p7,@s1порт 7 ==> (@s1) чтение суммы из ОЗУ PPU1
00502B3A out #3,pAh3 ==> порт A PPU2 в режим OUT (запись данных на шину)
00520000 nop нет операцииждем готовности данных на шине
00540000 nop нет операцииждем готовности данных на шине
0056
0058
0A7E
00FA
  in p7,@s2порт 7 ==> (@s2) чтение суммы из ОЗУ PPU2
005A2B3B out #3,pBh3 ==> порт B PPU3 в режим OUT (запись данных на шину)
005C0000 nop нет операцииждем готовности данных на шине
005E0000 nop нет операцииждем готовности данных на шине
0060
0062
0A7E
00F8
  in p7,@s3порт 7 ==> (@s3) чтение суммы из ОЗУ PPU3
00642B3C out #3,pCh3 ==> порт C PPU4 в режим OUT (запись данных на шину)
00660000 nop нет операцииждем готовности данных на шине
00680000 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
0086AF18  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" (разные!) модели архитектуры получились такими. Их не стоит количественно сравнивать между собой.


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


Free Web Hosting