Возможно, вы в курсе, что существует такая штука, как Закон Мура (https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%BA%D0%BE%D0%BD_%D0%9C%D1%83%D1%80%D0%B0).
Возможно, вы даже в курсе, что он уже перестаёт работать из-за физических ограничений вселенной, и даже параллелизация (наращивание ядер) уже не особо спасает.
Маловероятно, но, возможно, вы даже слышали о Законе Амдала (https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%BA%D0%BE%D0%BD_%D0%90%D0%BC%D0%B4%D0%B0%D0%BB%D0%B0), который показывает почему же именно наращивание ядер перестаёт помогать.
И согласно нему, мы практически в заднице: даже у программы, содержащей всего 1% последовательных вычислений (т.е. операций, зависящих от результата других операций) предел ускорения - 100 раз. Сколько бы ядер мы ни добавляли в систему. Быстрее, чем в 100 раз программа работать не станет.
В реальности же, программ с 1% последовательных вычислений не существует. И даже программ с 10% (для которых предел - 10-кратное укорение) исчезающе мало.
А для программ в которых последовательных вычислений половина - предел ускорения - 2 раза.
Как вы догадываетесь, в тех же игрушках, например, последовательных вычислений даже больше половины.
Вот и думайте теперь...
Однако, не всё так печально: в нашем мире существует так же и Закон Густавсона-Барриса (https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%BA%D0%BE%D0%BD_%D0%93%D1%83%D1%81%D1%82%D0%B0%D0%B2%D1%81%D0%BE%D0%BD%D0%B0_%E2%80%94_%D0%91%D0%B0%D1%80%D1%81%D0%B8%D1%81%D0%B0), у которого шанс, что вы о нём слышали стремится к нулю, но который, тем не менее, переосмысливает закон Амдала, смотря на "производительность" под другим углом и вселяет надежду.
Закон Амдала предполагает что фиксированным является объём задачи (грубо говоря - количество действий).
И это вполне справедливо применительно к текущим компьютерам, программам и ОС.
Однако же закон Г-Б рассматривает ситуацию с точки зрения ОС реального времени (типа тех, которые используются на космических аппаратах):
у каждой задачи есть лимит времени, в течение которого она может выполняться, вне зависимости от того, успела ли она, или нет.
Иначе аппарату может настать капут (особенно актуально для солнечных зондов, которые тусуются намного ближе к солнцу, чем даже Меркурий).
Так вот, в случае закона Г-Б (и ОС РВ) ситуация с распараллеливанием НАМНОГО более благоприятная.
Посмотрим рассчёты (на консльном калькуляторе bc, если что. Надеюсь, ни для кого не будет проблемой разобрать синтаксис):
```
$ bc -l <<< 'n=10; s=0.01; print "Amdall: ",1/(s+((1-s)/n)),"\n","Gust-Bars: ",n+(1-n)*s,"\n"'
Amdall: 9.17431192660550458715
Gust-Bars: 9.91
$ bc -l <<< 'n=100; s=0.01; print "Amdall: ",1/(s+((1-s)/n)),"\n","Gust-Bars: ",n+(1-n)*s,"\n"'
Amdall: 50.25125628140703517587
Gust-Bars: 99.01
$ bc -l <<< 'n=1000; s=0.01; print "Amdall: ",1/(s+((1-s)/n)),"\n","Gust-Bars: ",n+(1-n)*s,"\n"'
Amdall: 90.99181073703366696997
Gust-Bars: 990.01
$ bc -l <<< 'n=100000; s=0.01; print "Amdall: ",1/(s+((1-s)/n)),"\n","Gust-Bars: ",n+(1-n)*s,"\n"'
Amdall: 99.90109791306606459604
Gust-Bars: 99000.01
```
где:
n = к-во вычислительных ядер (процессоров),
s = коэффициент (% от 1) последовательных вычислений,
а остальное вам и не нужно (там формулы и print) 😊
Как мы видим, для текущего софта, который пишут всякие макаки, мнящие себя программистами, даже при 1% последовательных вычислений, только при количестве процессоров порядка 100 тысяч ускорение оказывается максимально близко к своему 100-кратному пределу.
В то же время, программы реального времени на том же количестве ядер имеют 99000-кратное ускорение.
Мораль, думаю, понятна 😃
@mva Есть ещё одна вещь, которая мешает многопоточности — синхронизация. Она будет отъедать время, и даже не постоянное его количество, как в в законе Амдала, а возрастающее с числом потоков. Так что распараллеливание задачи на миллион потоков может занять даже больше времени, чем на десять (в законе Амдала этого не увидишь, там время в любом случае уменьшится при большем распарралеливании).
В идеальном случае время на синхронизацию будет расти логарифмически, в худшем — может линейно или даже ещё хуже, не знаю. Это даже не так влияет на закон Амдала, как на закон Густавсона-Барриса. Если его дополнить расходами на синхронизацию, то ситуация может стать печальной. Итак…
Пусть \(n\) — число процессоров, \(s\) — доля последовательно выполняемых операций, \(t\) — доля времени на синхронизацию \(e = 2,7...\) процессоров (это абстракция, число легко привести к времени на синхронизацию каждых 2, 3, 4 и т. п. процессоров), тогда доля времени на синхронизацию между \(n\) процессорами будет:
\[t_s = t\log n;\]
время на параллельные вычисления:
\[p = 1 - s - t\log n.\]
Как результат, итоговый объём вычислений:
\[S_n = n\left(1-s-t\log n\right) + s\].
Допустим что условные затраты на синхронизацию составляют 0,1, доля последовательных вычислений тоже 0,1. Тогда, например
n = 10 — Sn = 8,3
n = 100 — Sn = 72
n = 1000 — Sn = 605
n = 10 000 — Sn = 4895 (уже не так радужно, потеряли половину производительности)
n = 100 000 — Sn = 37 425
n = 1 000 000 — Sn = 259 225 (уже потеряли три четверти)
n = 10 000 000 — Sn = 1 440 952
n = 100 000 000 — Sn = 2 896 590 (всего 2,8% времени процессоры заняты делом!)
и ещё маленький шажочек…
n = 150 000 000 — Sn = 1 303 906 (производительность вообще упала!)
Не надо думать, что синхронизация это надуманная проблема — она включает в себя много всего: создание процесса, пересылку данных между процессорами, синхронный запуск, ожидание процессами других процессов, и в массивно-параллельных системах — те самые суперкомпьютеры, представляет отдельную проблему, решаемую кучей разных способов.
@iron_bug @mva Если мы говорим о результате, который зависит от всех данных, а не просто несколько независимых расчётов, синхронизировать всё равно придётся, просто в некоторых случаях это тривиально.
Хардварные баги в ПК-подобных системах от того, что проблему пытаются «замести под ковёр» железом, делая вид, что память между ядрами полностью синхронна. Попытка переложить синхронизацию на программистов вызовет их закономерный вой. Ведь общая память это так удобно! (sarcasm)
@iron_bug @mva Lockless это тоже вид синхронизации (т. е. синхронизация есть, ожиданий нет). Но опять же Lockless базируется на атомарных операциях, которые просто реализованы в железе (необходимый минимум — неделимый read-write общей памяти). Это то же самое заметание под ковёр — пользуемся общей памятью, надеемся, что это быстро и безглючно (на самом деле нет).
понятно, что на уровне харда фенсы всё равно есть. но и ими можно управлять и иногда более эффективно написать какой-нибудь лок на ассемблере, нежели полагаться на то, что подсунет компилятор. но это уже тонкости конкретных реализаций.
@iron_bug @mva Синхронизация памяти есть, если есть разделяемая память. Если разделяемой памяти нет, то синхронизации памяти нет. В своё время топовых DSP такое практиковалось, каждый проц имеет собственную память, а весь обмен через шустрые каналы связи точка-точка. Это предполагалось соединять в большую прямоугольную сетку.
сейчас мейнстрим CPU примерно одинаков. всякие другие архитектуры - это редкие частные случаи.
да и дело не в архитектуре, а в расплодившемся говнософте. разруха не в процессорах, а в головах.
к тому же, выяснилось, что процессоры делать толком не умеют, и попытки оптимизировать эту самую синхронизацию внутри архитектуры процессоров породили столько хардварных багов, что просто капец. и ккривые попытки их залатать или обойти с помощью нелепых софтовых изворотов сделали всё ещё намного хуже, чем оно было.