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

Задача

В последовательных ячейках памяти лежат 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адрес начала массива
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,s R2 ==> (18)сохранить сумму
0016AF18  hlt стопзавершить программу
0018AE97 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.

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

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


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