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






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

Одновременные расчеты по нескольким программам

Рассмотрим сначала ситуацию, когда у нас есть несколько расчетных программ для исполнителя Удвоитель, и мы хотим запустить их параллельно, каждую в отдельном ПУ. В теории параллельных вычислений такая ситуация называется параллелизм по задачам, когда каждое вычислительное устройство считает отдельную задачу. Под описанную постановку попадает, в частности, запуск задач в операционной системе на многопроцессорном (многоядерном) компьютере.

Достаточно очевидно, что реализовать рассматриваемую форму параллелизма несложно, зато трудно добиться равномерной загрузки вычислительных устройств в случае, когда задачи требуют очень разного объема вычислений. В связи с этим рассмотрим наиболее благоприятную ситуацию, когда запускается несколько экземпляров одинаковой программы. В этом случае равный объем вычислительной работы гарантирован. Заметим, что предлагаемая модельная ситуация может иметь и некоторую практическую реализацию. Например, когда у нас есть длительно считающая программа и надо «прогнать» ее много раз для различных значений входных параметров. Будет ли выигрыш времени, если вместо запуска задач друг за другом по очереди в обычной однопроцессорной системе выполнить их все сразу каждую в своем процессоре более сложной (и дорогой) параллельной системы?

В качестве задачи для ПУ выберем программу для умножения некоторого фиксированного числа (параметра задачи) на 10m, где m есть постоянное для конкретной серии расчетов значение. Иначе говоря, при фиксированном mодновременно запускается несколько программ, каждая из которых считается для своего значения входного параметра. Результат вычислений каждой задачи выводится на экран. Программа умножения числа на 10 для S9PU имеет вид
2 MW 2 2 M+ MR
(Расчетная формула: 10z = 2z + 8z.)

Повторив текст базовой программы m раз, получим требуемую степень. Например, для m = 2 полная программа для ПУ0 (с учетом ввода-вывода) примет вид:
R (2 MW 2 2 M+ MR) (2 MW 2 2 M+ MR) W
Ради наглядности каждая серия команд умножения на 10 заключена в скобки (вводить их в S9PU категорически не рекомендуется).

Итак, обычная программа у нас уже есть, остается написать параллельную. Для случая трех параллельных задач получим следующее:
>p0 R o1 R o2 R o3 i1 W i2 W i3 W
>p13 i (2 MW 2 2 M+ MR) (2 MW 2 2 M+ MR) o

Программа для управляющего ПУ0 трижды читает параметры с помощью команды R, а командами o1-o3 по очереди пересылает прочитанные значения в ПУ1-ПУ3. После этого ПУ0 принимает результаты командами i1-i3 и с помощью W выводит ответы на экран.

Вы легко можете убедиться, что программа, предназначенная для ПУ1-ПУ3 (напомним, что об этом говорит стоящая в самом начале запись >p13), отличается от «непараллельной» программы только заменой команд ввода-вывода на инструкции обмена i и o. Скобки в программе по-прежнему исключительно средство наглядности.

Программы готовы, можно запускать их в нашем учебном ПО S9PU. Эксперимент показывает, что программа для ПУ0 выполнится за 16 тактов, а параллельная программа на ПУ1-ПУ3 – за 32. Дальше рассуждаем следующим образом. Троекратные последовательные вычисления для трех разных параметров на ПУ0 завершаются за 16*3 = 48 тактов. При параллельных вычислениях эта же работа потребовала 32 такта. Следовательно, полученное ускорение вычислений S = 48/32 = 1,5 (а вовсе не 3, как хотелось бы!)

Временная диаграмма для последовательного ...

такт 12345 678910 1112131415 161718...3132 3334...4748
ПУ0 R 2MW22M+MR 2MW22M+MR W R...W R...W

... и параллельного выполнения трех задач умножения числа на 100.

такт 12345 678910 1112131415 1617181920 2122232425 2627282930 3132
ПУ0 Ro1 Ro2 Ro3 ждетi1W ждет i2W ждет i3W
ПУ1 ждет i 2MW22M+MR 2MW22M+MR o               
ПУ2 ждет i 2MW22M+MR 2MW22M+MR o         
ПУ3 ждет i 2MW22M+MR 2MW22M+MR o   

В теории параллельных вычислений также часто используют параметр эффективности E = S/p, где p – это количество устройств (т.е. ускорение в пересчете на одно устройство). В нашем случае E = 1,5/3 = 0,5.

Аналогичным образом можно провести расчеты и для другого количества задач (или ПУ, что в данной ситуации то же самое). Готовые файлы с программами для рассматриваемых параметров можно найти в комплекте ПО в каталоге s9_soft\mul\100. Результаты для умножения на 100 отмечены на рисунке квадратиками белого цвета. Верхний пунктир соединяет значения для S, а нижний – для E.

графики S(p) и E(p)

Зависимость для S оказывается весьма удивительной: начиная примерно с 5 ПУ, величина ускорения от параллельности вычислений перестает расти и становится константой. Почему так происходит? Проведем следующие рассуждения. С ростом числа ПУ быстро растет объем работ, связанных с обменом данными. В самом деле, посмотрим на верхнюю строку программы для ПУ0 в листинге, которая написана для трех ПУ. Что добавится в нее, если перейти к четырем Удвоителям? В середину программы – команды R и o4, а в конец – i4 и W. Согласно таблице, их суммарное выполнение занимает 9 тактов, значит, каждый новый ПУ добавляет к программе по 9 тактов. В то же время вычисления в каждом ПУ занимают всего 12 тактов (по 6 на каждую скобку в нижней строке программы). Очевидно, что с ростом p достаточно быстро время обмена превысит время счета, и мы попадем в область «легких» приложений. А дальше все понятно. Время выполнения в этой области определяется исключительно длиной управляющей программы в ПУ0, а она, как мы только что видели, строго пропорциональна количеству ПУ. Но и при последовательном запуске время тоже пропорционально числу запусков! В итоге ускорение S, равное отношению этих величин, будет оставаться постоянным.

Что означает постоянство S для практики? Ни много, ни мало, бесполезность большого количества вычислителей. В частности, в рассмотренном выше случае двукратное выполнение 5 программ на 5 ПУ требует ровно столько же тактов, сколько параллельное выполнение всех этих 10 задач на 10 ПУ. Спрашивается, зачем тогда дополнительные вычислительные элементы?

Как улучшить ситуацию и уйти из этой неблагоприятной области? Уменьшить программу для ПУ0 не получается, так что единственным выходом является увеличить объем вычислений. Для этого перейдем от умножения на 100 к умножению на 108 = 100 000 000. Программа для ПУ0, разумеется, не изменится, зато программы для остальных ПУ существенно удлинятся (вместо 2 скобок станет 8, т.е. расчет займет 6*8 = 48 тактов). В этом случае, как показывают оценки (и подтверждает S9PU), за время обмена даже со всеми девятью Удвоителями, ПУ1 уже не успевает закончить вычисления. Если же взять меньше ПУ, то приложение станет еще более «тяжелым».

Результаты для параллельного умножения на 100 миллионов на уже обсуждавшемся рисунке приведены в виде черных круглых точек. Ускорение S все время растет и для девяти ПУ почти достигнет 5 раз. Существенно возрастет и значение эффективности, так что для «тяжелых» приложений параллельная работа действительно выгодна.

Конечно, переносить описанные результаты на реальное программное обеспечение надо с осторожностью, тем не менее, рискнем это сделать. Мы видим, что для «легких» приложений эффект от параллельности слаб. Зато на «тяжелых» можно получить существенное ускорение. Представим себе, что речь идет о многоядерной операционной системе. Порадует ли нас такая картина? Думаю, едва ли. Трудно представить себе «юзера», запускающего множество «тяжелых» приложений одновременно. В самом деле, как часто вам приходится параллельно с 3D-рендерингом и расчетами полей скорости и температуры жидкости смотреть на этом же компьютере кино?


© Е.А.Еремин, 2017


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