Данному образовательному сайту пришлось несколько раз менять свое имя. С 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". Сумма массива: модель с общей памятью, схема A1S2

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

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

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

Но прежде чем начинать вычисления, надо в память каждого PPU скопировать "его" четверть массива. В данном алгоритме это делается с помощью блочного копирования данных из PPU в CPU. Копирование в PPU1-PPU4 запускается друг за другом с минимально возможным промежутком времени. При этом главная особенность состоит в том, что у копируемых блоков отличается только начальный адрес в CPU (согласно принятому алгоритму обмена, он читается первым). Посему, запустив обмен с PPU1, CPU ждет ровно столько, сколько требуется PPU1 для чтения этого адреса. После чего адрес устанавливается на вторую 1/4 массива и активируется PPU2. Аналогично запускаются и остальные процессоры. Благодаря описанной процедуре запуска копирование данных идет практически параллельно.

Заметим, что ожидание организуется с помощью 3 операций nop при записи в ОЗУ PPU и 2 - при чтении.

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

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

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

адрескод ассемблер действиякомментарии
меткикоманды
  ;memory=COMM
;BLOCK 0
;PPU=4321
;CPUaddr=0380
;PPUaddr=0000
  память общая
блок 0
для всех PPU 1-4
адрес буфера чтения в ОЗУ CPU - 380
начальный адрес загрузки в PPU - 0
N/4=15 ;n=60
dA=1Eh ;dA=2*(N/4)
sum=18h
Tp=1Ah
  1/4 от количества слагаемых
изменение адреса при переходе на N/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-3D).
  • Ожидание завершения копирования данных и запуск программ суммирования в каждом PPU (3E-5D).
  • Ожидание, пока PPU1 закончит вычисления и активизация чтения сумм PPU в ОЗУ CPU (5E-93).
  • Ожидание завершения копирования результатов суммирования и вычисление итоговой суммы (94-B1).

адрескод ассемблер действиякомментарии
меткикоманды
  ;BLOCK 1
;CPUaddr=0
  блок 1 (для CPU)
начальный адрес - 0
N/4=15 ;N=60
T=100h
dA=1Eh ;dA=2*(N/4)
sum=18h
Tp=1Ah
@s4=F6h
@s3=F8h
@s2=FAh
@s1=FCh
@s=FEh
@xchgCPUAddr=3FAh
@xchgPPUAddr=3FCh
@xchgN=3FEh
  1/4 от количества слагаемых
адрес начала массива в ОЗУ CPU
смещение по массиву на N/4=15 чисел
адрес ячейки суммы в ОЗУ PPU
адрес 1/4 массива в ОЗУ PPU
адрес ячейки суммы от PPU1 в ОЗУ CPU
адрес ячейки суммы от PPU2 в ОЗУ CPU
адрес ячейки суммы от PPU3 в ОЗУ CPU
адрес ячейки суммы от PPU4 в ОЗУ CPU
адрес ячейки общей суммы в ОЗУ CPU
адрес CPU при обмене данными
адрес PPU при обмене данными
размер передаваемого блока
0000
0002
0004
01DE
0100
03FA
 mov #T,@xchgCPUAddr100 ==> (3FA) адрес начала массива в CPU для обмена
0006
0008
000A
01DE
001A
03FC
 mov #Tp,@xchgPPUAddr1A ==> (3FC) адрес начала 1/4 массива в PPU для обмена
000C
000E
0010
01DE
000F
03FE
 mov #N/4,@xchgNF ==> (3FE) размер блока для обмена (60/4=15)
00122B29  out #2,p92 ==> порт 9 PPU1 в режим IN (чтение блока из CPU)
0014
0016
0018
0000
0000
0000
  nop
nop
nop
3 раза
нет операции
ждем, пока PPU прочитает адрес CPU
001A
001C
001E
02DE
001E
03FA
  add #dA,@xchgCPUAddr(3FA)+1E ==> (3FA) адрес элемента во второй 1/4 массива
00202B2A  out #2,pAh2 ==> порт A PPU2 в режим IN (чтение блока)
0022
0024
0026
0000
0000
0000
  nop
nop
nop
3 раза
нет операции
ждем, пока PPU прочитает адрес CPU
0028
002A
002C
02DE
001E
03FA
  add #dA,@xchgCPUAddr(3FA)+1E ==> (3FA) адрес элемента в третьей 1/4 массива
002E2B2B  out #2,pBh2 ==> порт B PPU3 в режим IN (чтение блока)
0030
0032
0034
0000
0000
0000
  nop
nop
nop
3 раза
нет операции
ждем, пока PPU прочитает адрес CPU
0036
0038
003A
02DE
001E
03FA
  add #dA,@xchgCPUAddr(3FA)+1E ==> (3FA) адрес элемента в четвертой 1/4 массива
003C2B2C  out #2,pCh2 ==> порт C PPU4 в режим IN (чтение блока)
003E0A90 w1: in p9,r0порт 9 ==> R0 прочитать состояние PPU1
00402410  cmp #1,r0 сравнить R0 с 1сравнить с 1 - состояние СТОП (обмен окончен)
00424DFA   bne w1 переход по <>0если <>0, то повторить цикл ожидания
00442B09  out #0,p9 0 ==> порт 9запуск программы в PPU1
00460AA0 w2: in pAh,r0порт A ==> R0 прочитать состояние PPU2
00482410  cmp #1,r0 сравнить R0 с 1сравнить с 1 - состояние СТОП (обмен окончен)
004A4DFA   bne w2 переход по <>0если <>0, то повторить цикл ожидания
004C2B0A  out #0,pAh 0 ==> порт Aзапуск программы в PPU2
004E0AB0 w3: in pBh,r0порт B ==> R0 прочитать состояние PPU3
00502410  cmp #1,r0 сравнить R0 с 1сравнить с 1 - состояние СТОП (обмен окончен)
00524DFA   bne w3 переход по <>0если <>0, то повторить цикл ожидания
00542B0B  out #0,pBh 0 ==> порт Bзапуск программы в PPU3
00560AC0 w4: in pCh,r0порт C ==> R0 прочитать состояние PPU4
00582410  cmp #1,r0 сравнить R0 с 1сравнить с 1 - состояние СТОП (обмен окончен)
005A4DFA   bne w4 переход по <>0если <>0, то повторить цикл ожидания
005C2B0C  out #0,pCh 0 ==> порт Cзапуск программы в PPU4
005E
0060
0062
01DE
00FC
03FA
 mov #@s1,@xchgCPUAddrFC ==> (3FA) (читаем результаты в CPU)
адрес @s1 в CPU для обмена
0064
0066
0068
01DE
0018
03FC
 mov #sum,@xchgPPUAddr18 ==> (3FC) адрес sum в PPU для обмена
006A
006C
211E
03FE
 mov #1,@xchgN1 ==> (3FE) размер блока = 1 (одно число)
006E0A90 w5: in p9,r0 порт 9 ==> R0 прочитать состояние PPU1
00702410  cmp #1,r0 сравнить R0 с 1сравнить с 1 - состояние СТОП (счет окончен)
00724DFA   bne w5 переход по <>0если <>0, то повторить цикл ожидания
00742B39  out #3,p93 ==> порт 9 PPU1 в режим OUT (вывод блока в CPU)
0076
0078
0000
0000
  nop
nop
2 раза
нет операции
ждем, пока PPU прочитает адрес CPU
007A
007C
232E
03FA
  sub #2,@xchgCPUAddr(3FA)-2 ==> (3FA) адрес @s2 в CPU для обмена
007E2B3A  out #3,pAh3 ==> порт A PPU2 в режим OUT (вывод блока в CPU)
0080
0082
0000
0000
  nop
nop
2 раза
нет операции
ждем, пока PPU прочитает адрес CPU
0084
0086
232E
03FA
  sub #2,@xchgCPUAddr(3FA)-2 ==> (3FA) адрес @s3 в CPU для обмена
00882B3B  out #3,pBh3 ==> порт B PPU3 в режим OUT (вывод блока в CPU)
008A
008C
0000
0000
  nop
nop
2 раза
нет операции
ждем, пока PPU прочитает адрес CPU
008E
0090
232E
03FA
  sub #2,@xchgCPUAddr(3FA)-2 ==> (3FA) адрес @s4 в CPU для обмена
00922B3C  out #3,pCh3 ==> порт C PPU4 в режим OUT (вывод блока в CPU)
0094
0096
0098
01EE
00FC
00FE
  mov @s1,@s (@s1) ==> (@s)(начинаем считать итоговую сумму!)
сумма в PPU1 уже готова!!!
скопировать сумму от PPU1 в ячейку @s
009A0AA0 w6: in pAh,r0 порт A ==> R0 прочитать состояние PPU2
009C2410  cmp #1,r0 сравнить R0 с 1сравнить с 1 - состояние СТОП (счет окончен)
009E4DFA   bne w6 переход по <>0если <>0, то повторить цикл ожидания
00A0
00A2
00A4
02EE
00FA
00FE
  add @s2,@s (@s) + (@s2) ==> (@s)добавить сумму от PPU2
00A6
00A8
00AA
02EE
00F8
00FE
  add @s3,@s (@s) + (@s3) ==> (@s)добавить сумму от PPU3
00AC
00AE
00B0
02EE
00F6
00FE
  add @s4,@s (@s) + (@s4) ==> (@s)добавить сумму от PPU4
00B2AF18  hlt стопзавершить программу

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

Последний блок 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) приведенные выше программы выполняются за время 236 команд. Это чуть меньше, чем у однопроцессорной программы, где время эквивалентно времени выполнения 245 команд. Ускорение S = 245/236, т.е. незначительно превышает 1.

С данным алгоритмом проводилась серия экспериментов для нескольких разных N. С ростом N, когда объем вычислений в PPU тоже возрастает, величина S немного увеличивается. Например, при N = 240 получилось значение S = 965/776, т.е. примерно 1,2.

Тем не менее, в целом для данной задачи вся экономия времени благодаря разделению вычислений "съедается" процессом копирования массива.


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