Массивный и аппаратный параллелизм — горячие темы 21 века. Для этого есть несколько приятных причин и одна довольно печальная.

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

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

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

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

Мы также видим, что входные данные для наиболее успешных параллельных алгоритмов (сортировка, сопоставление строк, быстрое преобразование Фурье, матричные операции, обратное квантование изображений и т. д.) выглядят довольно похоже. Как правило, у них метрическая структура и подразумевается различие между «ближними» и «дальними» данными, что позволяет разрезать их на части, поскольку связь между дальними элементами незначительна.

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

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

В итоге можем сформулировать простую эвристику: Шансы на применение параллельных вычислений обратно пропорциональны степени неприводимой семантической нелокальности во входных данных.

Другим ограничением параллельных вычислений является то, что некоторые важные алгоритмы вообще не поддаются распараллеливанию — даже теоретически. Когда я впервые рассуждал на эту тему в блоге, то придумал термин «больной алгоритм», где SICK расшифровывается как «Serial, Intrinscally – Cope, Kiddo!». Среди значительных примеров: алгоритм Дейкстры нахождения кратчайшего пути; обнаружение циклов в ориентированных графах (с применением в солверах 3-SAT); поиск в глубину; вычисление n-го члена в криптографической цепочке хэшей; оптимизация сетевого потока… и это далеко не полный список.

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

И тут вступает блокировка: вы ничего не можете распараллелить, пока работает SICK-алгоритм.

Мы не закончили. Есть ещё как минимум два класса препятствий, причём весьма распространённые.

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

Если повезёт, вы получите более сговорчивый набор примитивов, такие как каналы Go (aka Communicating Sequential Processes) или систему владения/отправки/синхронизации в Rust. Но на самом деле мы не знаем, какой «правильный» язык примитивов для реализации параллелизма на фон-неймановской архитектуре. Возможно, даже нет одного правильного набора примитивов. Возможно, два или три различных набора подходят для разных проблемных областей, но они несоизмеримы как единица и квадратный корень из двух. На сегодняшний день в 2018 году никто толком не знает.

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

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

Думаю, что понимание этих ограничений становится более важным после краха закона масштабирования Деннарда. Из-за всех этих узких мест в программировании на части многоядерных систем всегда будет работать софт, не способный загрузить оборудование на 100% вычислительной мощности. Если посмотреть с другой стороны, у нас избыточное железо для текущих заданий. Сколько денег и усилий мы тратим впустую?

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

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

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

Вот основания для таких подозрений:

  1. Серьёзные параллельные вычисления на настольных/портативных компьютерах происходят только на GPU.
  2. Больше чем два ядра в процессоре обычно бесполезны. Операционные системы могут распределять потоки приложений, но типичный софт не способен использовать параллелизм, а большинству пользователей редко удаётся одновременно запускать большое количество разных приложений, потребляющих много ресурсов CPU, чтобы полностью загрузить своё оборудование.
  3. Следовательно, большинство четырёхъядерных систем основную часть времени не делают ничего, кроме выработки тепла.

Среди моих читателей много людей, которые наверняка смогут разумно прокомментировать эту гипотезу. Интересно посмотреть, что они скажут.

UPDATE. Комментатор на G+ указал одну интересную пользу от многоядерных процессоров: они очень быстро компилируют код. Исходный код языков вроде C имеет хорошую локальность: здесь хорошо разделённые единицы (исходные файлы) компилируются в объектные файлы, которые потом соединяет компоновщик.

Комментарии (36)


  1. andreili
    28.12.2018 16:02

    Я уже давно понял, что всякие там I7 с 6-10 ядрами — это просто «пальцы веером». Куда эффективнее купить простой I5 с 4-6 ядрами, при этом максимальная частота на 1 ядро хоть чуть, но выше. Всё равно в повседневном использовании редко используется даже 3 ядра. Сборка крупных программ (тот же GCC в Gentoo) производится очень редко, отсюда и выигрыша от количества ядер не видно особо.
    Лучше поставить SSD на NVME — вот где будет прирост скорости…


    1. Sdima1357
      28.12.2018 16:13

      Это не пальцы веером. Многопоточные — для обработки видео, трассировки лучей, физические симуляции и тп. Кому -то надо, а кому-то и нет. Каждый подбирает по себе в зависимости от задач и бюджета.


      1. andreili
        28.12.2018 16:17

        Я имел в виду домашнее применение. Да и для повседневной разработки выигрыш в пару минут при времени сборки проекта около 2 минут на 4 ядрах — сомнительно, потому что всё равно 99% времени сидим «тупо пялясь в код» ;)


        1. Sdima1357
          28.12.2018 16:59
          +2

          У вас Вас все равно стоит весьма многопоточный GPU и он Вам нужен, если Вы только не сторонник интерфейса командной строки:) Поговорим о пользе многопоточности?


          1. andreili
            28.12.2018 17:05
            -1

            Многопоточность полезна, я говорил о избыточности ядер в домашних ПК, куда «ради понтов» ставят i7, которые не будут утилизироваться в принципе. Или вы хотите сказать, что рядовой пользователь способен часами нагружать на 100% 8 ядер полезной нагрузкой? Игра (1-2 потока, редко 3 потока) + браузер (много потоков, но нагрузка мизерная) — рядовой случай дома.


            1. Sdima1357
              28.12.2018 17:20
              -1

              Вопрос с понтами не такой простой как кажется. Мне без разницы по какой причине рядовые пользователи покупают i7-i9. Но благодаря именно им эти процессоры массовые и доступные. И мне не надо брать ссуду, когда мне нужен именно многоядерный процессор для работы дома. Тоже касается и GPU разработка которого оплачена геймерами.


            1. nidheg666
              28.12.2018 18:40
              +1

              вы малость застряли во времени.

              начиная с года 2015 все игры, которые я ставил грузили все ядра моего 8 -ядерного процессора. я досихпор помню жаркие холивары на форумах варгейминга когда они под «многопоточностью» релизнули клиент, который юзал всего 2 ядра из возможных. это первый момент.

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


              1. andreili
                28.12.2018 18:47

                Ок. Запустил танки, открыл ProcessExplorer:

                Скрин
                image


                1. nidheg666
                  28.12.2018 18:51

                  у меня максимум было 4 потока. но это уже явно не 2, как у автора)


      1. SokolovJuri
        28.12.2018 20:42

        А я в качестве хобби массивы картинок обрабатываю. Там несколько программ: фотошоп — для выравниваяния/склеивания панорам, фотоматикс — для шдр-инга. Поскольку получить то, что нравится получается не сразу (нужно несколько итераций), то весь массив картинок приходится обрабатывать по нескольку раз и по-разному. В среднем фотоматикс грузит оба ядра ноутбука на 100% на несколько минут для одного прогона. Поэтому я подумываю о многоядерном монстре от АМД, чтобы получать результат не через полчаса, а сразу


        1. andreili
          28.12.2018 21:14

          Это частный случай, который относительно редок :)


          1. Sdima1357
            28.12.2018 23:45

            Тут я с Вами соглашусь, на ноутбуке обрабатывать картинки довольно странно, для этого есть десктопы :)


            1. andreili
              28.12.2018 23:57

              Мсье знает толк в извращениях.
              Да и ноутбучные процессоры сильно кастрированы — заметна разница в производительности на тяжёлом софте. По работе использую Siemens TIA Portal — декстоп с HDD уделывает ноут с SSD даже по скорости открытия проекта и объектов в нём :)


    1. Milein
      28.12.2018 16:38

      Лучше поставить SSD на NVME — вот где будет прирост скорости…

      Да тоже не так много.
      NVMe относительно SATA даёт значительный для линейного копирования килотонны информации.
      Если нагрузка не состоит из такого, то NVMe смысла практически не имеет.


      1. andreili
        28.12.2018 16:46

        Разница в 2 раза даже на нелинейных задачах. Вот мои результаты синтетики (Samsung 970 EVO M.2 vs OCZ-ARC100 SATA3):

        Crystal Disk Mark
        970 Evo OCZ


        1. SergeyMax
          28.12.2018 23:33

          В синтетике всё прекрасно. Но винда как грузилась пять секунд, так и грузится(


          1. andreili
            28.12.2018 23:38

            Ну, у меня сейчас большую часть загрузки занимает POST, даже в FastBoot'е. Совсем от этого уйти нельзя. А сама винда грузится очень быстро. Тут уже упирается в процессор, как понимаю в загрузке Win.


    1. 0xd34df00d
      28.12.2018 21:19
      +1

      В моём хобби-проекте достаточно файлов, чтобы шестиядерный 12-поточный i7 3930k был хорошо загружен (полная сборка — где-то 8 минут), и при этом я задумывался бы о всяких тредрипперах. Да и всякое там индексирование файлов в IDE многопоточное.


      Кроме того, есть ряд вычислительных задач, для которых дешевле купить многоядерный процессор, чем переносить их на GPU.


      А вот NVMe ставить совсем не вижу необходимости. /usr/include очень быстро закешируется в памяти.


      1. Sdima1357
        28.12.2018 23:48

        Долгая компиляция — признак избыточности связей в коде :)


        1. MikailBag
          29.12.2018 08:57

          Или упарывания с шаблонами.


        1. 0xd34df00d
          30.12.2018 17:35

          Долгая компиляция с нуля — признак большого количества файлов:


          % find ./ -name "*.cpp" | wc -l 
          1832

          И упарывания темплейтами, да.


  1. Duduka
    28.12.2018 16:08
    -2

    Счастье — дело техники! (с) КО
    Вы верно заметили, что проблема в мозгах программистов, все программисты страдают тяжелой формой си головного мозга, как последствие засилия си подобных языков, опыта (в основном) однозадачного мышления/управления, и мышления состояниями. В соседних темах про Rust (даже в нем), программисты советовали строить дерево, как мелкие объекты (на куче!), еще раз, в языке для разработки многозадачных приложений (никто не обеспечил инкапсуляцию, элементы дерева, по дизайну, разделяются, блокируются...), местные программисты предложили симулировать си указатель через RC и разделяемое владение… это — финиш.
    И в топике Вы поднимаете проблемы, остающиеся как последствие си мышления, какие мьютексы, какие инструкции?!.. откройте же для себя Rust, Erlang и прочая, и прочая.
    Инструменты требуют развития, освоения, и реально: (уже) от фон-Неймоновской архитектуры остались только устаревшие встраиваемые soc-системы, которые, опять-же могут оснащаться модемом и создавать не фон-Неймонавские архитектуры. Почитайте работы eao197, он (и не только он) уже эти проблемы решал.


    1. AlexTheLost
      28.12.2018 16:41

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


  1. AlexTheLost
    28.12.2018 16:34

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


    1. nomoreload
      29.12.2018 02:00
      +1

      Не правильный у вас какой-то сервер-сайд. В правильном сервер-сайде асинхронность > многопоточности. А ещё лучше, если сервер-сайд умеет и в одно, и в другое.


      1. AlexTheLost
        29.12.2018 14:43

        Не правильный у вас какой-то сервер-сайд.

        Что простите неправильно?)


        В правильном сервер-сайде асинхронность > многопоточности.

        Термин асинхронность описывает отсутствие порядка выполнения а не параллельность. Когда говорится об участках алгоритма которые могут быть выполнены параллельно используется термин — concurrency. Асинхронность не гарантирует параллельности, например когда у вас есть разделяемый ресурс который несколько задач хотят изменить незавимо, они могут быть выполнены в любом порядке но не одовремнно. Скажем обновление строки в БД. Так что вы, насколько я вижу, как и автор пишите о том что не знаете.
        Если этот момент прояснили и по сути вы имели ввиду concurrency >= parallelism. То мною сказанное это не нарушает. Чем больше реальная параллельность(parallelism) за счет ядер, тем больше задач из очереди(concurrency), будет принято на выполенения параллельно. Для конкретного пользователя системы это приведет к уменьшению времени ответа.


  1. edo1h
    28.12.2018 16:43
    +2

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


  1. RomanArzumanyan
    28.12.2018 16:51
    +4

    Больше чем два ядра в процессоре обычно бесполезны.

    Жмём Ctrl + Shift + Esc, видим (цифры у всех разные, но порядки схожие) 137 процессов и 2460 потоков. Про параллелизм на уровне задач автор не слышал.


    1. a-tk
      29.12.2018 14:32

      … из которых почти все I/O bound.


      1. arheops
        29.12.2018 22:33

        … именно потому, что у вас мощный многоядерный процессор. Иначе были бы cpu-wait


  1. epishman
    28.12.2018 22:19

    Откуда мнение, что многопоточное программирование сложно? Бывает сложно задачу разделить на блоки, это да, а программировать потоки — чего сложного то? Если человек вообще не писал параллельное, его ошибки могут быть трудно-обнаруживаемые (для него). Но если вошел в тему — вообще нет никаких проблем с гонкой, дедлоками и прочими ужасами. Особенно, если язык дает возможность не общие данные дергать, а посылать сообщения (Go, Javascript).


  1. Insane11
    28.12.2018 22:45
    +1

    Не понял о чём статья. Кому сейчас больше двух ядер не нужно? Калькулятору и блокноту? Нужен десктопный юзкейс? Ок, GTA5 уписывает 4 ядра за обе щёки. StarCitizen рекомендует 8. На рабочей машине один только касперский пару ядер греет, а ведь нужно ещё что-то полезное крутить. Под *nix использование zfs прдъявляет суровые требования к CPU. А общем мне пожалуйста в десктоп ядер побольше и подешевле. А в сервера ЕЩЁ больше, 28 на сокет это уже несерьёзно, при наличии возможности запихать в сервер пару-тройку терабай оперативы.


  1. StriganovSergey
    28.12.2018 23:08

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


    1. claygod
      29.12.2018 10:59

      Добавлю, что и CAS в определённых задачах вполне покрывает потребности, а если появится двойной CAS (или одинарный но на 128 бит), то это будет вообще отличная новость.


  1. Shinso
    29.12.2018 01:27

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


  1. Daddy_Cool
    29.12.2018 01:43

    Ну господа… Компутер девайс весьма универсален.
    Вот сейчас что-то качается, висят фоновые скайпы и прочие аськи, завтра я посчитаю что-то в расчетной программе типа Open Foam, потом запишу песенку под гитару в Cubase, скину несколько гигов фоток с отдыха, посортирую и слегка поредактирую их, потом порежу видео с концерта, сконвертирую и перешлю друзьям. И да — еще я мог бы поиграть в игрушку (но увы — не играю ни во что по причине лени).
    И наконец! Я опять запущу браузер, почитаю хабр и напишу коммент. В общем нам надо больше, больше ядер…