Система функциональных устройств. Закон амдала.

Любая вычислительная система, есть работающая во времени совокупность функциональных устройств. Для оценки качества ее работы вводятся различные характеристики. Рассмотрим их в рамках некоторой модели процесса работы устройств, вполне достаточной для практического применения. Нас не будет интересовать, содержательная часть операций, выполняемая функциональными устройствами. Они могут означать арифметические или логические функции, ввод/вывод данных, пересылку данных в память и извлечение данных из нее или что-либо другое. Более того, допускается , что при разных обращениях операции могут означать разные функции. Для нас важно лишь времена выполнения операций и то, устройствах, какого типа они реализуются.

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

Назовем функциональные устройства простыми, если никакая последующая операция не может начать выполнение раньше, чем закончится предыдущая. Простое ФУ может выполнять операции одного типа или разные операции.

Разные ФУ, могут выполнять операции, в том числе одинаковые, за разное время. Примером простого ФУ может служить не конвейерные сумматоры или умножители. Эти ФУ реализуют только один тип операций. Простым устройством можно считать многофункциональный процессор, если он способен выполнять различные операции одновременно, и мы не принимаем во внимание различия во временах реализации операций, предполагая что они одинаковые. Основная черта простого ФУ: оно монопольно использует свое оборудование для выполнения каждой отдельной операции.

В отличии от простого ФУ, конвейерное ФУ распределяет свое оборудование для одновременной реализации нескольких операций. Очень часто оно конструируется как линейная цепочка простых элементарных ФУ , имеющие одинаковые времена срабатывания. На этих элементарных ФУ последовательно реализуются отдельные этапы операций. В случаи конвейерного ФУ выполняющий операцию сложения с плавающей запятой, соответствующие элементарные устройства последовательно реализует такие операции: сравнение порядков, сдвиг мантиссы, сложение мантисс и т.д.

Принцип функционирование конвейерного ФУ остается тем же. Сначала на первом элементарном ФУ первый этап первой операции. Затем на втором элементарном ФУ реализуется второй этап первой операции. Одновременно на освободившимся первом ФУ реализуется первый этап второй операции. После этого результат срабатывания второго ФУ , передается третьему ФУ , результат срабатывания первого ФУ , передается второму ФУ. Освободившиеся первое ФУ готово для выполнения первого этапа третий операции и т.д.

После прохождение всех элементарных ФУ в конвейере операция оказывается выполненной.

Элементраные ФУ называются ступенями конвейера, число ступеней – длина конвейера. Простое ФУ можно считать конвейерным, с длиной конвейера равной 1 .

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

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

Второй закон Амдала и его следствие:

Предположим что в вашей программе доля операций , которых нужно выполнить последовательно равна f, где 0≤f≤1 ( при этом доля понимается не по статическому числу строк в коде, а по числу операций в процессе выполнения).

Крайние случаи в значения f соответствуют полностью параллельным (f=0) и полностью последовательным (f=1) программам.

Для того чтобы оценить какое ускорение S может быть получено на компьютере из «р» процессоров при данном значении f , можно воспользоваться законом Амдала.

Если 9/10 программы исполняется параллельно, а 1/10 по-прежнему последовательно, то ускорение более , чем в 10 раз получить в принципе невозможно вне зависимости от качества реализации параллельной части кода и числа используемых процессоров(ясно, что 10 получается только в том случае, когда время исполнение параллельной части равна 0 ).

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

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

Пример изменения последовательного алгоритма на параллельный:

S:=0;

For i:=1 to n do

S:=S+a[i];

По своей природе алгоритм строго последовательный, так как на i-ой итерации требуется результат с (i-1) и все итерации выполняются одна за одной. Имеем 100% последовательных операций , а значит и никакого эффекта от использования параллельных компьютеров.

Переделаем алгоритм. Нет существенной разницы от порядка складывание числа. Выбираем иную схему сложения . Сначала найдем сумму пар соседних элементов: а(1)+а(2); а(3)+а(4); а(5)+а(6) и т.д.

При такой схеме все пары складываются одновременно. На следующих шагах будем действовать аналогично, получив вариант параллельного алгоритма.

Если ФУ разнородны по своей природе, то возникает проблема: одно ФУ закончило свою работу, а остальные еще работают. В таких случаях первое ФУ простаивает в ожидании. Если разброс производительности большой, то и эффективность системы при равномерной загрузке ФУ будет низкой.

Еще одна проблема – это передача данных между ФУ.

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

Третий закон Амдала:

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