Параллельное программирование *

Введение

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

1. Повысить скорость работы программы.
2. Работать с сетками такого размера, который не помещается в оперативной памяти одного процессора.

При таком подходе сетка, покрывающая расчетную область, разбивается на множество доменов, каждый из которых обрабатывается отдельным процессором. Основная проблема здесь заключается в «честности» разбиения: нужно выбрать такую декомпозицию, при которой вычислительная нагрузка распределена равномерно между процессорами, а накладные расходы, вызванные дублированием вычислений и необходимостью передачи данных между процессорами, малы.

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

Попытка заглянуть вглубь hashCode() привела к спелеологическому путешествию по исходному коду JVM, с рассмотрением структуры объектов и привязанной блокировки (biased locking), а также удивительных последствий для производительности, связанных с использованием hashCode() по умолчанию.

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

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

Ситуация несколько усложняется, когда понятия имеют природу множеств (рисунок ниже). Тогда возможны формулировки типа: «понятие C содержит понятия A и B», «понятия A и B различны», «понятия A и B имеют нечто общее». Если положить, что близость определяется в интервале от 0 до 1, то про рисунок слева можно сказать: «близость A и C равна 1, близость B и C равна 1, близость A и B равна 0).

Мы всё-таки смогли дойти до третьей части и добрались до самого интересного — организации асинхронных вычислений.

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

Теперь посмотрим, как можно управлять потоком исполнения (control flow) в случае обработки асинхронных задач.

• Параллелизм (часть 1)
  
  
  • Потоки: scheduling, сон
  • Синхронизация: Spinlock, семафоры, барьеры памяти
  • Атомарность: TAS, CAS
  
  
• Кооперативность (часть 2)
  
  
  • Корутины (coroutines)
  • Акторы
  
  
• Асинхронность (часть 3, текущая)
  
  
  • Event loop
    • select
  • Callbacks
  • Async Monad
  • Промисы (promises, обещания)
  • async/await — промисы + корутины
  
  

Intel Xeon Phi — уникальный процессор, как никто другой раскрывающий все преимущества параллельного исполнения задач. Созданный по технологии Intel Many Integrated Core (MIC), он предоставляет вам несколько десятков мощных вычислительных ядер и порядочный кусок интегрированной высокоскоростной памяти. Думаю, что многие программисты, как начинающие, так и опытные, хотели бы «погонять» свой код на таком процессоре, чтобы найти его узкие места, оценить влияние параллелизма на производительность и так далее. Останавливает одно: стоимость самой младшей модели Xeon Phi составляет $2500, и это только сам процессор. Навряд ли многие рискнут приобрести такую систему для личных нужд, а нужда такая, как уже говорилось, бывает.

Теперь жизнь энтузиастов становится немного проще. Образовательный центр Colfax Research при финансовой поддержке Intel запустил программу удаленного доступа до кластера серверов на базе Intel Xeon Phi. Детали программы — под катом, но сначала коротко о самом Intel Xeon Phi — давненько мы на эту тему не писали.

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

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

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

Моделирование сложных физических процессов в наши дни рассматривается как важная технологическая возможность многими современными компаниями. Широко используемым сейчас подходом для создания вычислителей, способных рассчитывать сложные модели, является создание кластерных систем, где вычислительный узел представляет собой сервер общего назначения, подключенный к сети малой латентности и управляемый своей собственной ОС (как правило, из семейства GNU/Linux).

Введение виртуализационного слоя в системное ПО вычислительных кластеров, позволяет в течение нескольких минут создавать “виртуальный кластер”. Такие виртуальные кластера в рамках одной OpenStack инфраструктуры являются абсолютно независимыми. Пользовательские программы внутри них могут изменяться так, как нужно пользователю без каких-либо согласований с кем-либо, а логические устройства, на которых находятся пользовательские данные, недоступны другим виртуальным кластерам.

Поддержка сети малой латентности виртуализационными решениями представляет собой отдельную сложную проблему. Для прикладных программ в большинстве случаев современная виртуализация на основе KVM приводит к минимальным потерям вычислительной мощности (<1%). Однако специализированные тесты сетей малой латентности показывают накладные расходы от виртуализации не более 20% на операциях синхронизации.

Хочу рассказать сообществу о проведённом мной эксперименте.

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

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

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

Или ещё замечательный пример — Kerbal Space Program. Там физика уже является непосредственым источником геймплея.

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

Я давно мечтал сделать именно такой, до предела физически реалистичный римейк Scorched Earth. Но все мои эксперименты с моделированием физических систем упирались в неумолимо медленные процессоры. Тысяча-две частиц были пределом для real-time симуляции.

Но недавнее моё «открытие» изменило ситуацию.

Лаборатория DISLab (ОАО «НИЦЭВТ») совместно с НИВЦ МГУ проводят четвертую ежегодную научно-практическую конференцию по проблемам параллельной обработки больших графов с использованием суперкомпьютерных комплексов и кластерных систем.

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

Совсем скоро, в рамках данной научно-технической конференции GraphHPC-2017, стартует конкурс GraphHPC, посвященный проблемам параллельной обработки больших графов с использованием суперкомпьютеров. В этот раз участникам предстоит получить самую быструю реализацию задачи Betweenness Centrality (Центральность по посредничеству) в неориентированном графе.

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

n! = n * (n — 1) * (n – 2) * … * 3 * 2 * 1

Факториал – достаточно быстро растущая функция, об этом говорит ее асимптотика (формула Стирлинга), хотя достаточно посмотреть на факториалы нескольких первых членов натурального ряда:

1! 1
2! 2
3! 6
4! 24
5! 120
6! 720
7! 5 040
8! 40 320
9! 362 880
10! 3 628 800
11! 39 916 800
12! 479 001 600
13! 6 227 020 800
14! 87 178 291 200
15! 1 307 674 368 000

Как видно, факториал 13-ти уже не умещается в тип данных long.

Если задаться целью найти однозначное соответствие между номером перестановки — числом в диапазоне от 1 до n! – и ее реализацией, можно натолкнуться на один очень интересный математический факт.

Думаю, что практически каждый реальный проект использует ту или иную форму реализации очереди поставщик-потребитель (producer-consumer queue). Идея проблемы довольно проста. Приложению нужно развязать производство некоторых данных от их обработки. Возьмем, к примеру, пул потоков в CLR: мы добавляем элемент на обработку путем вызова ThreadPool.QueueUserWorkItem, а пул потоков сам разбирается, какое число рабочих потоков наиболее оптимально и вызывает методы для обработки элементов с нужной степенью параллелизма.

Но использование стандартного пула потоков не всегда возможно и/или разумно. Несмотря на возможность указания минимального и максимального числа потоков, эта конфигурация глобальная и повлияет на приложение целиком, а не на нужные его части. Существует множество других способов решить задачу поставщика потребителя. Это может быть решение «в лоб», когда логика приложения смешивается с аспектами многопоточности, очередями и синхронизацией. Это может быть обертка над BlockingCollection с ручным управлением числа рабочих потоков или задач. Или же это может быть решение на основе полностью готового решения, такого как ActionBlock<T> из TPL DataFlow.

Сегодня мы рассмотрим внутреннее устройство класса ActionBlock, обсудим дизайн-решения, которые были приняты его авторами и узнаем, почему нам все это нужно знать, чтобы обойти некоторые проблемы при его использовании. Готовы? Ну тогда поехали!

Много ядер не бывает

Атомарные операции (atomics), например, Compare-and-Swap (CAS) или Fetch-and-Add (FAA) широко распространены в параллельном программировании.

Мульти- или многоядерные архитектуры установлены одинаково как в продуктах настольных и серверных компьютеров, так и в крупных центрах обработки данных и суперкомпьютерах. Примеры конструкций включают Intel Xeon Phi с 61 ядрами на чипе, который установлен в Tianhe-2, или AMD Bulldozer с 32 ядрами на узле, развернутых в Cray XE6. Кроме того, количество ядер на кристалле неуклонно растет и процессоры с сотнями ядер, по прогнозам, будут изготовлены в обозримом будущем. Общей чертой всех этих архитектур является растущая сложность подсистем памяти, характеризующаяся несколькими уровнями кэш-памяти с разными политиками включения, различными протоколами когерентности кэш-памяти, а также различными сетевыми топологиями на чипе, соединяющими ядра и кэш-память.

Практически все такие архитектуры обеспечивают атомарные операции, которые имеют многочисленные применения в параллельном коде. Многие из них (например, Test-and-Set) могут быть использованы для реализации блокировок и других механизмов синхронизации. Другие, например, Fetch-and-Add и Compare-and-Swap позволяют строить разные lock-free и wait-free алгоритмы и структуры данных, которые имеют более прочные гарантии прогресса, чем блокировки на основе кода. Несмотря на их важность и повсеместное употребление, выполнение атомарных операций полностью не проанализировано до сих пор. Например, по общему мнению, Compare-and-Swap идет медленнее, чем Fetch-and-Add. Тем не менее, это всего лишь показывает, что семантика Compare-and-Swap вводит понятие «wasted work», в результате – более низкая производительность некоторого кода.

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

Вот первичный анонс о внедрении нового сборщика, датированный августом 2015-го:

В Go создаётся сборщик мусора (GC) не только для 2015 года, но и для 2025-го, и ещё дальше… Сборщик в Go 1.5 возвещает о наступлении будущего, в котором паузы на сборку больше не являются барьером для перехода на безопасный язык. Это будущее, в котором приложения без труда масштабируются вместе с оборудованием, и по мере роста мощности оборудования сборщик мусора больше не является сдерживающим фактором при создании более качественного, масштабируемого ПО. Go — хороший язык для использования как минимум в ближайший десяток лет.

Создатели утверждают, что они не просто решили проблему пауз на сборку мусора, а пошли куда дальше:

Одним из высокоуровневых способов решения проблем с производительностью является добавление GC-настроек (knobs), по одной на каждую проблему. Программист может менять их, подбирая наилучшую комбинацию для своего приложения. Недостатком этого подхода является то, что при внедрении каждый год одной-двух новых настроек через десять лет придётся законодательно регулировать труд людей, которые будут менять эти настройки. Go не пошёл по этому пути. Вместо кучи настроек мы оставили одну и назвали её GOGC.

Более того, освободившись от бремени поддержки десятков настроек, разработчики могут сосредоточиться на улучшении runtime’а приложения.

Не сомневаюсь, что многие пользователи Go были просто счастливы получить новый подход к runtime’у в Go. Но у меня есть претензии к этим заявлениям: они выглядят как недостоверный маркетинговый булшит. А поскольку они раз за разом воспроизводятся в Сети, пришло время подробно с ними разобраться.

Я продолжаю свой небольшой цикл статей относительно средств организации и реализации конкурентных вычислений.

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

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

• Параллелизм (часть 1)
  
  • Потоки: scheduling, сон
  • Синхронизация: Spinlock, семафоры, барьеры памяти
  • Атомарность: TAS, CAS
  
  
• Кооперативность (часть 2, текущая)
  
  • Корутины (coroutines)
  • Акторы
  
  
• Асинхронность (часть 3)
  
  • Event loop
    • select
  • Callbacks
  • Async Monad
  • Промисы (promises, обещания)
  • async/await — промисы + корутины
  
  

В статье описывается подход к программированию многоядерных сигнальных процессоров на основе OpenMP. Рассматриваются директивы OpenMP, разбирается их смысл и варианты использования. Делается акцент на цифровых сигнальных процессорах. Примеры применения директив OpenMP выбраны приближенными к задачам цифровой обработки сигналов. Реализация проводится на процессоре TMS320C6678 фирмы Texas Instruments, включающем 8 DSP-ядер. В части I статьи рассматриваются основные директивы OpenMP. Во II части статьи планируется дополнить список директив, а также рассмотреть вопросы внутренней организации работы OpenMP и вопросы оптимизации программного обеспечения.

Данная статья отражает лекционно-практический материал, предлагаемый слушателям в рамках курсов повышения квалификации по программе «Многоядерные процессоры цифровой обработки сигналов C66x фирмы Texas Instruments», проводимых ежегодно в Рязанском радиотехническом университете. Статья планировалась к публикации в одном из научно-технических журналов, но в силу специфики рассматриваемых вопросов было принято решение о накоплении материала для учебного пособия по многоядерным DSP-процессорам. А пока данный материал будет копиться, он вполне может полежать на страницах Интернета в свободном доступе. Отзывы и пожелания приветствуются.

Эта статья объясняет почему при разработке Win32-приложений механизм Slim Reader/Writer Lock (SRWL) часто более предпочтителен, чем классические критические секции.

Легковесность

SRWL-объект занимает в памяти всего 8 байт на x64-архитектуре, в то время как критическая секция — 40 байт. Критическая секция требует инициализации и деинициализации через вызовы функций ядра ОС, в то время как SRWL инициализируется простым присваиванием ему константы SRWLOCK_INIT, а затрат на удаление нет вообще никаких. Использование SRWL генерирует более компактный код и использует меньше оперативной памяти при работе.

Если у вас будет 100 000 объектов, требующих некоторой внутренней синхронизации, экономия памяти будет уже существенной. Прирост производительности от избегания лишних промахов кэша будет ещё более ощутимым. В современных процессорах (начиная с Intel Nehalem, вышедшего в 2008-ом) одна кэш-линия занимает 64 байта. Если вы используете на объект синхронизации 40 из них — это существенно ударит по производительности доступа к небольшим объектам в вашем ПО.

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

И, надеюсь, кому-нибудь это может оказаться полезно, ибо кто-нибудь может чего-нибудь не знать, или, наоборот, окажется полезно мне, если кто-нибудь покажет что-нибудь ещё/укажет на изъяны в моих знаниях.

• Параллелизм (часть 1, текущая)
  
  
  • Потоки: scheduling, сон
  • Синхронизация: Spinlock, семафоры, барьеры памяти
  • Атомарность: TAS, CAS
  
  
• Кооперативность (часть 2)
  
  
  • Корутины (coroutines)
  • Акторы
  
  
• Асинхронность (часть 3)
  
  • Event loop
    • select
  • Callbacks
  • Async Monad
  • Промисы (promises, обещания)
  • async/await — промисы + корутины
  
  

В публикации «Сказка о потерянном времени» пользователь crea7or рассказал, как он опровергал Гипотезу Эйлера на современном CPU.

Мне же было интересно узнать как покажет себя GPU, и я сравнил однопоточный код с многопоточным для CPU и совсем многопоточным для GPU, с помощью архитектуры параллельных вычислений CUDA.

Lock-free list является основой многих интересных структур данных, — простейшего hash map, где lock-free list используется как список коллизий, split-ordered list, построенный целиком на списке с оригинальным алгоритмом расщепления bucket'а, многоуровневого skip list, являющегося по сути иерархическим списком списков. В предыдущей статье мы убедились, что можно придать такую внутреннюю структуру конкурентному контейнеру, чтобы он поддерживал thread-safe итераторы в динамичном мире lock-free контейнеров. Как мы выяснили, основным условием для того, чтобы lock-free контейнер стал итерабельным, является стабильность внутренней структуры: ноды не должны физически удаляться (delete). В этом случае итератор суть просто (быть может, составной) указатель на ноду с возможностью перехода к следующей (оператор инкремента).

Можно ли такой подход распространить на lock-free list?.. Посмотрим…

Это перевод обзора статьи «MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing» Fan et al. в Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI’13), pdf тут

Чуваки (бывший гугловец, чувак из университета Карнеги Меллон и еще один из Интел лабс) сделали улучшенный Memcached-совместимый кеш (по факту просто допилили мемкеш), и у них классные результаты производительности. Мне очень понравился обзор этой статьи в блоге "The morning paper" — описание алгоритмов и прочее.