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

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

От создания нового проекта в Юнити до публикации бета-версии в Стиме прошло 10 месяцев. 90% времени ушло на создание, оптимизацию и вылизывание физической модели, остальное — на геймплей.

Цель была в том, чтобы создать полностью физический мир. Но подход, реализованный в Red Faction показался слишком громоздким и не слишком реалистичным. В той игре меши при взрыве разбивались на куски, на которые натягивались физические коллайдеры. Я решил не мучаться с сопроматом и множеством частных случаев разрушений, а сделать простую систему, работающую во всех случаях.

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

Получившаяся из частиц материя сначала выглядела странно, и напоминала то ли жидкость, то ли газ:



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

Начну свою первую статью с небольшой предыстории. К моменту когда все началось, я уже на протяжении 7 лет участвовал в научном проекте, целью которого была разработка семантической технологии проектирования интеллектуальных систем. А началось все с прочтения одной замечетельной статьи (спасибо vovochkin) во второй половине 2015 года. Именно тогда я понял, что разрабатываемая нами технология хорошо подходит под решение задач в области интернета вещей. Это был первый фактор который привел меня к текущему проекту. Вторым фактором было то, что мне сильно нравился фильм «Железный человек» и я сильно хотел иметь своего «Джарвиса» у себя дома.

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

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

Забегая вперед сразу скажу, что в конце статьи будет ссылка на github, куда я выложил готовое решение, позволяющее тестировать параллельные консольные процессы легко и просто.

SDAccel это система программирования на OpenCL для ПЛИС фирмы Xilinx. В настоящее время всё более обостряется проблема разработки проектов для ПЛИС на традиционных языках описания аппаратуры, таких как VHDL/Verilog. Одним из методов решения проблемы является применение языка C++. OpenCL это один из вариантов применения языка С++ для разработки прошивок ПЛИС.

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

Владимир Маяковский

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

Сделаем еще один шаг в сторону универсального обобщения. Опишем идею комбинаторного пространства и то, как это пространство помогает искать закономерности и тем самым решать задачу обучения с учителем.

В одном из прежних постов я рассказывал, как реализовать «простейшую в мире lock-free хеш-таблицу» на C++. Она была настолько проста, что было невозможно удалять из нее записи или менять ее размерность. С тех пор прошло несколько лет, и не так давно я написал несколько многопоточных ассоциативных массивов без таких ограничений. Их можно найти в моем проекте Junction на GitHub.

Junction содержит несколько многопоточных реализаций интерфейса map – даже «самая простая в мире» среди них, под названием ConcurrentMap_Crude. Для краткости будем называть ее Crude map. В этом посте я объясню разницу между Crude map и Linear map из библиотеки Junction. Linear — самый простой map в Junction, поддерживающий и изменение размера, и удаление.

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

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

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

Введение

Расчетные сетки широко применяются при решении численных задач с помощью методов конечных разностей. Качество построения такой сетки в значительной степени определяет успех в решении, поэтому иногда сетки достигают огромных размеров. В этом случае на помощь приходят многопроцессорные системы, ведь они позволяют решить сразу 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», в результате – более низкая производительность некоторого кода.