Закон Амдала в реальном мире

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

Логично думать, что если один процессор выполнит работу за час, то два, работающих сообща, сделают ту же работу за полчаса. Для больших и сложных задач такое бывает часто. Тогда можно предположить, что три процессора сосчитают нашу задачу за 20 минут, а десять процессоров — за шесть минут. А 3600 процессоров — за секунду? Да, но только в том случае, если нашу задачу можно разделить на 3600 независимых друг от друга частей.

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



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

Если мы раскидали вычисления на процессорные нити (threads), и они обмениваются между собой (или даже только с одним «главным» процессом) информацией, тогда мгновенно наши графики получают максимумы:

• Было (закон Амдала):
  
  S — во сколько раз можно ускорить вычисления, N — количество вычислителей, p — доля последовательно вычисляемого кода. Графики для разных значений p см. выше.
  
• Стало:
  теперь процессы обмениваются пакетами данных — считаем, что число пересылаемых пакетов пропорционально числу процессов, поэтому ко времени расчётов надо прибавить число, пропорциональное N.
  
  где A — какая-то маленькая положительная константа, пропорциональная скорости передачи данных между процессами. Какой бы маленькой она ни была, всё равно на большом количестве вычислителей быстродействие будет меньше, чем на некотором максимальном значении. А в пределе вообще ноль:
  
  

На графике показаны две кривые ускорения, соответствующие p = 0.9: идеальный случай (красная кривая) и реальный (синяя) с A = 0.001. Видно, что считать такую задачу более чем на тридцати процессорах бессмысленно.


Суперкомпьютер отличается от «обычного» компьютера, не тем, что у него много ядер, а тем, что эти ядра у него соединены в быструю сеть, т.е. коэффициент A из (2) у него очень маленький.

Умные люди говорят³, что зависимость может быть не такая страшная, а всего лишь

где функция f мала для больших N, а B — другая маленькая константа. (Я несколько упрощаю, но принципиально всё так.)

Вывод: если кто-то просит у вас денег на суперкомпьютер, спросите у него, как он собирается обойти закон Амдала. Десять поваров не сварят стакан риса за минуту.
_________________________
¹ Тактовая частота процессора 3 ГГц = 3×10⁹ 1/c соответствует тому, что сигнал за один такт пройдёт не далее, чем на 10 см. Конечно, 10 см — это очень большое расстояние в масштабах процессора. Но ведь частота интерфейса, связывающего отдельные ядра, меньше в разы, а частота, шины, связывающей процессор со внешней памятью, меньше на несколько порядков.
² Кроме задач типа «сосчитаем что-нибудь по методу Монте-Карло» я больше и не придумаю.
³ http://www.clgrid.cl/images/2/26/Cluster-scalability.pdf