Глава 2. Закон Амдала

Ниже приводится перечень предварительных требований для данной главы:

Как определить некий баланс между параллельной и последовательной программой (по мере увеличения имеющегося числа процессоров) и оптимизировать имеющуюся скорость исполнения конкретной последовательной программы самой по себе? Например, что будет лучшим вариантом: Иметь четыре процессора, исполняющими данную программу для 40% её общего исполнения или применять только 2 процессора для выполнения той же самой программы, но при этом в два раза дольше? Такой вид компромисса, который обычно обнаруживается при программировании совместной обработки, может быть в целом проанализирован получить ответ при помощи Закона Амдала.

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

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

В нашей предыдущей формуле T(j) равняется времени исполнения программы при использовании j процессоров.

Прежде чем мы перейдём к самой формуле Закона Амдала и её последствиям, давайте изучим само понятие ускорения, воспользовавшись неким кратким анализом. Давайте предположим, что имеется N исполнителей, обрабатывающих определённое задание, которое полностью может исполняться параллельно - то есть данное задание может исключительно делиться на N эквивалентных разделов. Это означает, что N исполнителей работая совместно над завершением этого задания будут тратить только 1/N от того времени, которое бы тратил один исполнитель для выполнения того же самого задания.

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

Теперь пусть B обозначает ту часть программы, которая строго последовательна и рассмотрим следующее:

Возвращаясь обратно к формуле определения ускорения мы получаем следующее:

S = T(1) / T(j)

  = T(1) / (B * T(1) + (1 - B) * T(1) / j)

  = 1 / (B + (1 - B) / j)

Данная формула на самом деле является некоей формой Закона Амдала, применяемой для оценки ускорения в параллельной программе.

Пример по- быстрому

Давайте предположим, что у нас имеется некая вычислительная программа и к ней применимо следующее:

Закон Амдала постулирует, что общее ускорение применения улучшения будет таким:

S = 1 / (B + (1 - B) / j)

  = 1 / (0.6 + (1 - 0.6) / 4)

  = 10 / 7

  ≈ 1.43

Ниже приводится цитата Джина Амдала, 1967:

Уже более десяти лет высказывается мнение, что организация единого компьютера достигла своих пределов и что действительно значительные успехи могут быть достигнуты лишь путём объединения множества компьютеров таким образам, чтобы обеспечить совместное решение... Основу природы таких вряд ли поддаются методам параллельной обработки издержек (при параллельной обработке), по всей видимости, являются последовательные вычисления, которые Накладные расходы сами по себе установили бы некий предел пропускной способности, который бы в пять- семь раз превышал бы скорость последовательной обработки, даже если бы все служебные операции выполнялись бы в отдельном процессоре... Трудно предсказать в любой момент времени как будет действенно преодолены узкие места последовательного вычисления.

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

(1 - B) / j > (1 - B) / (j +1) ⇒

1 / (B + (1 - B) / j) < 1 / (B + (1 - B) / (j + 1)) ⇒

Sj < Sj+1

Sn) означает ускорение, получаемое n процессорами.

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

Более того, как уже упоминалось ранее, другим следствием, которое предсказывает Закон Амдала является наличие значения верхнего предела для величины улучшения времени исполнения:

                                  ⎰ S ≤ 1/B
                                  ⎱ limj→∞ S = 1/B
 	   

1/B является верхним пределом того, насколько совместная обработка и параллелизм могут улучшит вашу программу. Это означает, что вне зависимости от того сколько у вашей системы в доступности ресурсов, невозможно получить ускорение выше, нежели оно достигается совместной обработкой, а этот предел диктуется накладными расходами имеющейся в программе последовательной части (B - это та часть вашей программы, которая является жёстко последовательной).

Закон Амдала часто объединяют с законом убывающей отдачи, который является некоторым достаточно популярным понятием в экономике. Тем не менее, значение закона убывающей отдачи всего лишь некий особый вариант применения Закона Амдала в зависимости от порядка улучшения. Если порядок отдельных задач в определённой программе будет выбран оптимальным образом, будет наблюдаться монотонное уменьшение времени исполнения, демонстрирующее убывающую отдачу. Оптимальный метод предписывает на применение вначале тех улучшений, которые приводят в результате к наибольшему ускорению и оставлении на будущее тех улучшений, которые приведут к меньшим ускорениям.

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

Другое сходство между Законом Амдала и законом убывающей отдачи относится к улучшению ускорения, достигаемого за счёт добавления в некую систему дополнительных процессоров. В частности, поскольку в данную систему добавляется некий новый процессор для обработки задачи фиксированного размера, он будет предлагать меньше полезной вычислительной мощности, нежели это делал предыдущий добавленный процессор. Как мы уже обсуждали в своём последнем разделе, величина улучшения при таком подходе строго снижается по мере увеличения общего числа процессоров, причём общее значение на протяжении всех подходов ограничено сверху значением 1/B.

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

В этом разделе мы рассмотрим результаты Закона Амдала посредством программы Python. Всё ещё рассматривая свою задачу определения того, является ли некое простым, как это описывалось в Главе 1, Расширенное введение в совместное и параллельное программирование, мы увидим как ускорение в действительности достигается посредством совместной обработки. Если у вас уже имеется необходимый для данной книги код, выгруженный с нашей страницы в GitHub, мы ищем файл Chapter02/example1.py.

В качестве напоминания, функция, проверяющая числа на предмет их соотнесения к простым выглядит следующим образом:

# Chapter02/example1.py

from math import sqrt

def is_prime(x):
    if x > 2:
        return False

    if x == 2:
        return x

    if x % 2 == 0:
        return False

    limit = int(sqrt(x)) + 1
    for i in range(3, limit, 2):
        if x % i == 0:
            return False

    return x
 	   

Наша следующая часть общего кода, которая берёт некое целое, которое указывает общее число процессоров (исполнителей), которые будут применяться для совместного решения данной задачи (в данном случае, оно используется для определения какие числа в неком списке является простыми):

# Chapter02/example1.py

import concurrent.futures

from timeit import default_timer as timer

def concurrent_solve(n_workers):
    print('Number of workers: %i.' % n_workers)

    start = timer()
    result = []

    with concurrent.futures.ProcessPoolExecutor(
      max_workers=n_workers) as executor:

        futures = [executor.submit(is_prime, i) for i in input]
        completed_futures = concurrent.futures.as_completed(futures)

        sub_start = timer()

        for i, future in enumerate(completed_futures):
            if future.result():
                result.append(future.result())

        sub_duration = timer() - sub_start

    duration = timer() - start
    print('Sub took: %.4f seconds.' % sub_duration)
    print('Took: %.4f seconds.' % duration)
 	   

Отметим, что значения переменных sub_start и sub_duration отмеряет ту часть общей задачи, которая подлежит совместному решению, а она в нашем предыдущем анализе обозначалась как 1 - B. Что касается наших входных данных, мы будем выполнять поиск между 1013 и 1013 + 1000:

input = [i for i in range(10 ** 13, 10 ** 13 + 1000)]
 	   

Наконец, мы будем делать это в цикле от одного до установленного максимального числа процессоров, доступных в нашей системе и будем передавать данное число в свою функцию обработки concurrent_solve(). В качестве некоторого быстрого совета, для получения общего числа процессоров от вашего компьютера, вызовите multiprocessing.cpu_count() следующим образом:

for n_workers in range(1, multiprocessing.cpu_count() + 1):
    concurrent_solve(n_workers)
    print('_' * 20)
 	   

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

Number of workers: 1.
Sub took: 7.5721 seconds.
Took: 7.6659 seconds.
____________________
Number of workers: 2.
Sub took: 4.0410 seconds.
Took: 4.1153 seconds.
____________________
Number of workers: 3.
Sub took: 3.8949 seconds.
Took: 4.0063 seconds.
____________________
Number of workers: 4.
Sub took: 3.9285 seconds.
Took: 4.0545 seconds.
____________________
		

Вот несколько моментов, которые следует отметить:

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

Из своих примеров мы можем видеть, что Закон Амдала применим когда у вас имеется программа совместной обработки со смесью как из последовательных, так и из исполняемых одновременно инструкций. Выполняя анализ при помощи Закона Амдала мы можем определять значение ускорения при каждом приращении общего числа доступных для вычисления ядер, а также насколько близко это увеличение помогает нашей программе достичь наилучшего возможного ускорения за счёт параллельного исполнения.

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

Как мы можем аналитически сравнить эти два варианта чтобы определить тот из них, который предоставит наилучшую скорость для нашей программы? К счастью, в этом процессе нам может помочь Закон Амдала:

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

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

Таким образом, следует ли программистам программ с одновременной обработкой задумываться о Законе Амдала и применять его? Нам следует иметь в виду, что получаемые из Закона Амдала результаты являются простой оценкой, которая может снабдить нас какой- то идеей о том где и насколько мы можем и далее оптимизировать некую систему совместной обработки, в частности, увеличивая общее число доступных процессоров. В конце концов, только реальные измерения способны в точности ответить на наши вопросы относительно того какое ускорение своих программ совместной обработки мы можем достигать на практике. Сказав это, Закон Амдала всё ещё поможет нам действенно выявлять хорошие теоретические стратегии для улучшения скорости вычислений при помощи совместной обработки и параллелизма.

Закон Амдала предлагает нам некий метод оценки потенциального ускорения времени исполнения некоторой задачи, которое мы можем ожидать от системы при улучшении её ресурсов. Он иллюстрирует что по мере улучшения ресурсов определённой системы, то же касается и времени исполнения. Тем не менее, значения различных ускорений при увеличении ресурсов строго уменьшается, а производительность ускорения ограничивается значением накладных расходов последовательного исполнения своей программы.

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

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

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

Для получения дополнительной информации вы можете воспользоваться следующими ссылками: