2.Закон Гроша. Гипотеза Минского.

Это попытка провести оценку эффективности параллельных вычислений в сравнении с вычислениями в однопроцессорных системах с фоннеймановской архитектурой. Оценки производительности, которые были получены в соответствии с законом Гроша и гипотезой Минского были пессимистичны и долгое время сдерживали развитие теории параллельного вычисления.

Закон Гроша.

В соответствии с законом производительность процессора увеличивается пропорционально квадрату его стоимости. Т.о. отпадает необходимость построения параллельных выч-ых систем для обеспечения эффективности вычисления. Достаточно вложить побольше денег в производство одного процессора, и требуемая эффективность будет достигнута. Однако со временем выяснилось, что в пределе закон Гроша не является справедливым, т.к. рост производительности физически ограничивается скоростью распределения электронов в проводнике.

Гипотеза Минского.

Допустим, в системе имеется n обрабатывающих устройств или процессоров. Производительность каждого из них равна 1. В этом случае производительность системы, состоящей из n процессоров, может оцениваться как log₂ n. Подобный результат основан на необходимости процессоров обмениваться результатами вычислений в ходе решения задачи.

В 80-е годы за счет совершенствования механизмов управления удалось доказать, что производительность системы с ростом числа процессоров увеличивается быстрее, чем log₂ n.

3. Законы Амдала и следствия из них.

Позволяют более реалистично, хотя и асимптотически оценить отрасль параллельных программ.

1 Закон.

Производительность выч-ой системы, состоящей из связанных между собой устройств, в общем случае определяется самым непроизводительным ее устройством.

Следствие: пусть система состоит из простых устройств и граф системы сильно связанный. Если все устройства системы имеют одинаковые пиковые производительности, то асимптотическая производительность системы будет max-ой.

Пояснение к закону: потери производительности определяются простоями в очереди к самому непроизводительному устройству. Если же все устройства имеют одинаковые пиковые производительности, то очередей и простоев можно избежать.

2 Закон.

Пусть доля операций в программе, которые нужно выполнить последовательно, составляет

0 ≤ f ≤ 1: если f = 0, то программа полностью параллельна;

если f = 1, то программа полностью последовательна.

П ри заданном значении f и известном количестве процессов p ускорение выполнения программы оценивается по формуле:

,

где s – ускорение выполнения программы

Закон означает, что количество процессов не всегда явным образом позволяет достичь требуемого ускорения программы. Для достижения требуемого ускорения необходимо учитывать свойства самой программы. Кроме того, свойства программы накладывают ограничения на величину достижимого ускорения. Например, если f = 0,1, то невозможно достичь ускорения работы программы более, чем в 10 раз при любом, даже неограниченно

Следствие: позволяет решить обратную задачу, т.е. определить, какую часть, когда необходимо ускорить, чтобы получить требуемое значение s.

Формулировка следствия: чтобы ускорить выполнение программы в q раз, необходимо ускорять не менее, чем в q раз не менее, чем (1-1/q) часть программы.

Для рассматриваемого примера это значит, что для достижения десятикратного ускорения, необходимо ускорить не менее, чем в 10 раз не менее, чем 0,9 программы.

Пиковая производительность – max-ая производительность, которой может достичь выч-ая система, если все ее устройства работают с max-ой нагрузкой.