Закон Амдала и его применение при создании компьютерных систем

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

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

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

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

Рисунок 2.3 – Схемы параллельных алгоритмов

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

реализуется только на одном вычислители коллектива, а информационные

связи между их операторами их ветвей (формула),выполняется с помощью специальных операторов обмена информации.

Зависит коэффициент ускорения от числа процессоров и степени параллелизма алгоритма называется законом Амдала. Если построить график

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

Наличие последующих частей кода. Закон Амдала и его последствия.

Пусть f- это часть последовательных вычислений, 0<f<1.