Данному образовательному сайту пришлось несколько раз менять свое имя. С 2022 года доступ к нему обеспечивается по URL
emc.orgfree.com

emc.km.ru (2001-2007) ==> educomp.org.ru (2007-2011) ==> educomp.runnet.ru (2011-2021) ==> emc.orgfree.com (2022-...)
Более подробно об истории сайта можно прочитать здесь.


Учебные модели компьютера



Модели (software):

"Е14" (parallel !!!)
"S9PU" (parallel)

Модели (hardware):






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

Вычисления по демо-формуле

Используя систему S9PU, вычислим выражение
[(2+X)*1000]+[(19+Y)*256+7]+[(23+Z)*8]
Честно признаюсь, что формула специально подобрана так, чтобы обеспечить как можно больший эффект от параллельности вычислений.

Сначала напишем программу для одного Удвоителя - для ПУ0. Она не очень сложная, но достаточно длинная. Поэтому чтобы легче было ориентироваться, она разбита на 3 строки, каждая из которых соответствует слагаемому, заключенному в исходном выражении в квадратные скобки.
0 1 2 R+ 2 MW 2 2 M+ MR 2 MW 2 2 M+ MR 2 MW 2 2 M+ ; (2+X)*1000
0 1 2 2 2 1 2 1 R+ 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 M+ ; (19+Y)*256+7
0 1 2 2 1 2 1 2 1 R+ 2 2 2 M+ MR W ; (23+Z)*8
Команды строго соответствуют указанному в формуле порядку действий. При этом неприлично много операций тратится на получение констант 19 и 23. (Вероятно, можно было бы ввести в систему команд исполнителя занесение произвольной константы в сумматор, но это бы похоронило столь любимые задачи для Удвоителя, как из одного заданного числа получить другое, да еще за наименьшее число шагов.)

Умножение на 1000 в первой строке организовано как троекратное повторение фрагмента умножения на 10.

Выполнение написанной выше программы на S9PU требует 66 тактов.

такт 12345 678910 1112131415 1617181920 2122232425 2627282930 3132333435 3637383940 4142434445 4647484950 5152535455 5657585960 616263646566
ПУ0 012 R+ 2MW22M+MR 2MW22M+MR 2MW22M+ 0 1222121 R+ 22222222 1111111M+ 0 12212121 R+ 222M+MR W

Для удобства анализа такт, соответствующий началу каждой строки приведенного листинга, выделен светло-серым цветом.

Перейдем теперь к разработке параллельной программы. Для ее оптимизации обратим внимание на следующие важные обстоятельства.

  • Как показывают уже рассмотренные примеры, эффект сокращения времени при параллельных вычислениях лучше проявляется на длинных программах (тогда не так сказывается время обмена). Поэтому программа, увы, не должна быть слишком короткой.
  • Выполнение предыдущего положения приводит к тому, что ПУ0 приходится ждать результатов вычислений от остальных ПУ. Хорошая мысль состоит в том, чтобы он в это время тоже что-нибудь считал. В предлагаемой ниже программе ПУ0 "в свободное время" вычисляет последнее слагаемое.
  • Много тактов обычно теряется при старте, когда периферийные ПУ ожидают от ПУ0 значения параметров. В данном случае для исключения указанных потерь ПУ1 и ПУ2 в начале программы считают значения констант. Так удается недостаток модели - долгое вычисление констант, использовать "во благо", заполняя время ожидания.
  • После того, как периферийный ПУ передал результат, он останавливается и простаивает до конца задачи. Во время вывода окончательного результата на экран простаивают все ПУ, кроме главного. Это вынужденный простой, ибо что можно делать, когда ответ уже сосчитан? Поэтому полезно стараться распределять работу между ПУ равномерно, тогда они "дружно" закончат и обсуждаемый простой будет минимальным.

Все указанные выше пути оптимизации были тщательно учтены в приведенной ниже параллельной программе для ПУ0-ПУ2.
ПУ0: R o1 R o2 0 1 2 2 1 2 1 2 1 R+ 2 2 2 A1 A2 W ;организация вычислений и (23+Z)*8
ПУ1: 0 1 2 A 2 MW 2 2 M+ MR 2 MW 2 2 M+ MR 2 MW 2 2 M+ MR o ; (2+X)*1000
ПУ2: 0 1 2 2 2 1 2 1 A 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 o ; (19+Y)*256+7

Временная диаграмма для нее выглядит так.

такт 12345 678910 1112131415 1617181920 2122232425 2627282930
ПУ0 Ro1 Ro2 012212121 R+ 222 A1 A2 W
ПУ1 012 A 2MW22M+MR 2MW22M+MR 2MW22M+MR o     
ПУ2 01222121 A 22222222 1111111 o   

Видно, что, исключая неизбежные 6 тактов в конце программы, нет больше ни одного(!) такта простоя ПУ. А во время тактов 11-19 и 22-23 все(!) ПУ занимаются вычислениями.

Такая оптимизация вычислений не может не сказаться положительно. Вместо 66 тактов при расчетах на одном ПУ0, для рассматриваемой параллельной программы требуется всего 30. Таким образом, ускорение S = 66/30 = 2,2, что для трех вычислителей очень даже неплохо. Эффективность (ускорение на один вычислитель) E = 2,2/3 = 0,73.

Оценим также, какую часть времени каждый из ПУ занимался непосредственно вычислениями (исключая обмен и простои). Здесь также показатели неплохие. Больше всех считал ПУ2: он выполнил 23 вычислительных операции за 23 такта, так что его к.п.д. равен 23/30 = 77%. ПУ1 чуть отстает - 21/30 = 70%. Наконец, ПУ0, много времени потративший на организацию вычислений, и то посвятил счету 12/30 = 40% своего времени.

Заметим, что не для каждой формулы результаты будут такими оптимистичными. Но для каждой можно попытаться использовать описанные здесь приемы для повышения эффективности параллельных вычислений на S9PU.


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


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


Free Web Hosting