36. Законы Амдала. Классификация параллельных систем по Флинну.

Законы Амдала.

Первый закон Амдала.

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

Второй закон Амдала.

Пусть вычислительная система состоит из p процессоров. Предположим, что k из N операций алгоритма могут выполняться только последовательно. Пусть β = k/N – доля последовательных операций в алгоритме, 0 ≤ β ≤ 1. Тогда максимально возможное ускорение системы R = 1 / (β + (1- β)/p). Очевидно, что предел выражения для ускорения R при неограниченном увеличении количества процессоров, то есть при p, стремящемся к бесконечности равен 1/ β. Пусть, например, доля операций, которые могут быть выполнены последовательно, равна β = 0,1, тогда реальное ускорение R не может быть больше 10 при любом количестве процессоров. Практический вывод из этих соображений состоит в том, что для общего повышения эффективности нужно не только наращивать количество процессоров в системе, но и улучшать свойства программы, в частности, уменьшать долю операций, выполняемых только последовательно.

Классификация параллельных систем по Флинну

Она основана на понятиях потока команд и потока данных.

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

Если в вычислительной системе на одной и той же стадии обработки находится более одного набора операндов, которые поступают в различные процессорные элементы, то поток данных называется множественным. Поток команд соответствует счетчику команд. Система с n процессорами имеет n счетчиков команд и, следовательно, n потоков команд. Поток данных состоит из набора операндов.
Потоки команд и данных в какой-то степени независимы, поэтому существует 4 комбинации: