Пессимизм насчёт многопоточности +13



Массивный и аппаратный параллелизм — горячие темы 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
    /#19562436

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

    • Sdima1357
      /#19562490

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

      • andreili
        /#19562508

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

        • Sdima1357
          /#19562706 / +2

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

          • andreili
            /#19562732 / -1

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

            • Sdima1357
              /#19562800 / -1

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

            • nidheg666
              /#19563140 / +1

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

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

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

              • andreili
                /#19563160

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

                Скрин
                image

                • nidheg666
                  /#19563172

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

      • SokolovJuri
        /#19563470

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

        • andreili
          /#19563564

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

          • Sdima1357
            /#19563942

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

            • andreili
              /#19563984

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

    • Milein
      /#19562612

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

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

      • andreili
        /#19562648

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

        Crystal Disk Mark
        970 Evo OCZ

        • SergeyMax
          /#19563918

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

          • andreili
            /#19563928

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

    • 0xd34df00d
      /#19563582 / +1

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


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


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

      • Sdima1357
        /#19563956

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

        • 0xd34df00d
          /#19566688

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


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

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

  2. Duduka
    /#19562466 / -2

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

    • AlexTheLost
      /#19562628

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

  3. AlexTheLost
    /#19562600

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

    • nomoreload
      /#19564214 / +1

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

      • AlexTheLost
        /#19566130

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

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


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

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

  4. edo1h
    /#19562632 / +2

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

  5. RomanArzumanyan
    /#19562670 / +4

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

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

    • a-tk
      /#19566084

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

      • arheops
        /#19567402

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

  6. epishman
    /#19563724

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

  7. Insane11
    /#19563794 / +1

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

  8. StriganovSergey
    /#19563862

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

    • claygod
      /#19565100

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

  9. Shinso
    /#19564166

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

  10. Daddy_Cool
    /#19564190

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