|
"Е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 | адрес начала массива | |
| 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,sum | R2 ==> (sum) | сохранить сумму | |
| 0016 | AF18 | 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,@xchgCPUAddr | 100 ==> (3FA) | адрес начала массива в CPU для обмена | |
| 0006 0008 000A | 01DE 001A 03FC |
mov #Tp,@xchgPPUAddr | 1A ==> (3FC) | адрес начала 1/4 массива в PPU для обмена | |
| 000C 000E 0010 | 01DE 000F 03FE |
mov #N/4,@xchgN | F ==> (3FE) | размер блока для обмена (60/4=15) | |
| 0012 | 2B29 | out #2,p9 | 2 ==> порт 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 массива | |
| 0020 | 2B2A | out #2,pAh | 2 ==> порт 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 массива | |
| 002E | 2B2B | out #2,pBh | 2 ==> порт 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 массива | |
| 003C | 2B2C | out #2,pCh | 2 ==> порт C | PPU4 в режим IN (чтение блока) | |
| 003E | 0A90 | w1: | in p9,r0 | порт 9 ==> R0 | прочитать состояние PPU1 |
| 0040 | 2410 | cmp #1,r0 | сравнить R0 с 1 | сравнить с 1 - состояние СТОП (обмен окончен) | |
| 0042 | 4DFA | bne w1 | переход по <>0 | если <>0, то повторить цикл ожидания | |
| 0044 | 2B09 | out #0,p9 | 0 ==> порт 9 | запуск программы в PPU1 | |
| 0046 | 0AA0 | w2: | in pAh,r0 | порт A ==> R0 | прочитать состояние PPU2 |
| 0048 | 2410 | cmp #1,r0 | сравнить R0 с 1 | сравнить с 1 - состояние СТОП (обмен окончен) | |
| 004A | 4DFA | bne w2 | переход по <>0 | если <>0, то повторить цикл ожидания | |
| 004C | 2B0A | out #0,pAh | 0 ==> порт A | запуск программы в PPU2 | |
| 004E | 0AB0 | w3: | in pBh,r0 | порт B ==> R0 | прочитать состояние PPU3 |
| 0050 | 2410 | cmp #1,r0 | сравнить R0 с 1 | сравнить с 1 - состояние СТОП (обмен окончен) | |
| 0052 | 4DFA | bne w3 | переход по <>0 | если <>0, то повторить цикл ожидания | |
| 0054 | 2B0B | out #0,pBh | 0 ==> порт B | запуск программы в PPU3 | |
| 0056 | 0AC0 | w4: | in pCh,r0 | порт C ==> R0 | прочитать состояние PPU4 |
| 0058 | 2410 | cmp #1,r0 | сравнить R0 с 1 | сравнить с 1 - состояние СТОП (обмен окончен) | |
| 005A | 4DFA | bne w4 | переход по <>0 | если <>0, то повторить цикл ожидания | |
| 005C | 2B0C | out #0,pCh | 0 ==> порт C | запуск программы в PPU4 | |
| 005E 0060 0062 | 01DE 00FC 03FA |
mov #@s1,@xchgCPUAddr | FC ==> (3FA) | (читаем результаты в CPU) адрес @s1 в CPU для обмена |
|
| 0064 0066 0068 | 01DE 0018 03FC |
mov #sum,@xchgPPUAddr | 18 ==> (3FC) | адрес sum в PPU для обмена | |
| 006A 006C | 211E 03FE |
mov #1,@xchgN | 1 ==> (3FE) | размер блока = 1 (одно число) | |
| 006E | 0A90 | w5: | in p9,r0 | порт 9 ==> R0 | прочитать состояние PPU1 |
| 0070 | 2410 | cmp #1,r0 | сравнить R0 с 1 | сравнить с 1 - состояние СТОП (счет окончен) | |
| 0072 | 4DFA | bne w5 | переход по <>0 | если <>0, то повторить цикл ожидания | |
| 0074 | 2B39 | out #3,p9 | 3 ==> порт 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 для обмена | |
| 007E | 2B3A | out #3,pAh | 3 ==> порт 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 для обмена | |
| 0088 | 2B3B | out #3,pBh | 3 ==> порт 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 для обмена | |
| 0092 | 2B3C | out #3,pCh | 3 ==> порт C | PPU4 в режим OUT (вывод блока в CPU) | |
| 0094 0096 0098 | 01EE 00FC 00FE | mov @s1,@s | (@s1) ==> (@s) | (начинаем считать итоговую сумму!) сумма в PPU1 уже готова!!! скопировать сумму от PPU1 в ячейку @s |
|
| 009A | 0AA0 | w6: | in pAh,r0 | порт A ==> R0 | прочитать состояние PPU2 |
| 009C | 2410 | cmp #1,r0 | сравнить R0 с 1 | сравнить с 1 - состояние СТОП (счет окончен) | |
| 009E | 4DFA | 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 | |
| 00B2 | AF18 | 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.
Тем не менее, в целом для данной задачи вся экономия времени благодаря разделению вычислений "съедается" процессом копирования массива.
