Данному образовательному сайту пришлось несколько раз менять свое имя. С 2022 года доступ к нему обеспечивается по URL
emc.km.ru (2001-2007) ==> educomp.org.ru (2007-2011) ==> educomp.runnet.ru (2011-2021) ==> emc.orgfree.com (2022-...)
Более подробно об истории сайта можно прочитать здесь.
|
"Е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 достаточно проста.
Мы видим, что программа для центрального процессора состоит из трех мало зависящих друг от друга частей:
Конечно, на втором шаге CPU "тупо" (как сейчас любит говорить молодежь) тратит время. А мог бы вместо этого сосчитать сумму некоторых слагаемых. (Это сильно экономит время по двум причинам: во-первых, меньшее число слагаемых суммирует каждый PPU; а во-вторых, меньшее количество чисел передается из общей памяти PPU). Но это уже будет другой алгоритм. Подчеркнем, что программы для каждого PPU, суммируя по 15 чисел, проделывают строго одинаковое количество команд, а стартуют с разницей в одну команду. Это позволяет проверять завершение вычислений только для PPU1. Ниже в таблице приведена программа для PPU1. Она по очереди читает из первой четверти исходного массива (напомним, что массив лежит в общей памяти) числа, суммирует их и возвращает полученный ответ в ячейку общей памяти, отведенную под первую сумму. Позднее CPU просуммирует ее с результатами остальных PPU.
Далее располагаются аналогичные блоки 2-4 для PPU2-PPU4 соответственно. Они отличаются только начальными адресами для обработки массива (вместо T - T1/4 и т.д. - см. секцию констант в блоке 1) и адресом записи полученной суммы (вместо s1 - s2 и т.д.). Последний блок 5 содержит суммируемый массив. Он размещен начиная с адреса 100h.
Результаты. Для 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 раза. |