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

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

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

У каждой российской микроэлектронной компании есть рассказ, почему она самая хорошая и передовая. По английски это называется «claim to fame» — «заявка на славу». Одни российские компании славятся оригинальной архитектурой и/или микроархитектурой CPU, другие — спроектированной в России системой на кристалле, третьи — спроектированными в России блоками, которые были лицензированы западным компаниям.

У российской компании ЭЛВИС (ELVEES), которая исторически специализировалась на космической электронике, DSP и хардверно-поддерживаемом распознавании образов, текущая «заявка на славу» выражена в совместном российско-британско-американско-тайваньском чипе для «умных камер» под названием ELISE. Инженеры в подмосковном Зеленограде спроектировали внутри этого чипа важные блоки для видео-обработки и GNSS, которые потом кросс-лицензировала британско-американская Imagination Technologies.

Блоки от элвисовцев интегрированы с тремя разнородными процессорными ядрами: двухядерным кластером суперскалярных ядер MIPS P5607 (Apache) с частотой 1.2 GHz, на котором работает Linux, процессором с аппаратно-поддерживаемой многопоточностью MIPS interAptiv (1 GHz) и небольшим вспомогательным процессором с аппаратно-поддерживаемой виртуализацией MIPS M5150 (Virtuoso).

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

На фотографиях ниже некоторые из инженеров-участников проекта. Девушка слева спроектировала часть load-store unit в MIPS P5607, юноша в зеленой майке написал модели интерфейсов шин, а товарищ в клетчатой рубашке — архитектор софтверной экосистемы:

В первой части я описал на примере cmoda7 как портировать MIPSfpga (Портирование MIPSfpga на другие платы и интеграция периферии в систему. Часть 1) на FPGA платы отличные от уже портированых среди которых такие популярные как: basys3, nexys4, nexys4_ddr фирмы Xilinx, а так же de0, de0_cv, de0_nano, de1, DE1, de10_lite, de2_115, DE2-115 фирмы Altera(Intel), во второй части как интегрировать клавиатуру Pmod KYPD (Портирование MIPSfpga на другие платы и интеграция периферии в систему. Часть 2).

В этой части добавим к MIPSfpga-plus встроенный АЦП, и популярный LCD от Nokia 5100.
С предыдущих частей можно сделать вывод, что интеграция периферии в MIPSFPGA состоит из пять основных этапов:

• Добавление модуля интерфейса общения с периферией (i2c, spi, и т.д.).
• Соединение входных/выходных портов модуля с шиной AHB-Lite.
• Присваивание адресов сигналов подключаемого устройства.
• Добавление констрейнов на физические контакты платы.
• Написание программы для MIPS процессора.

Подключение встроенного в cmoda7 АЦП

Как я уже говорил плата cmodA7 имеет встроенный АЦП, pin 15 и 16 используются в качестве аналоговых входов модуля FPGA. Диапазон работы встроенного АЦП от 0-1V, поэтому используется внешняя схема для увеличения входного напряжения до 3.3V.


Эта схема позволяет модулю XACD точно измерить любое напряжение от 0 В и 3,3 В (по отношению к GND). Чтобы работать с АЦП в Vivado существует блок IP (интеллектуальной собственности) Xilinx, с помощью которого можно будет просто его интегрировать в нашу систему MIPSfpga.

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

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

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

PHP очень далёк от других технологий. Например, в Java очень активно используются потоки выполнения, ещё они могут встречаться в пользовательских программах. В PHP такого нет. И тому есть причины.

Примеры использования и тестирование потоко-безопасного указателя и contention-free shared-mutex

В этой статье мы покажем: дополнительные оптимизации, примеры использования и тестирование разработанного нами потоко-безопасного указателя с оптимизированным разделяемым мьютексом contfree_safe_ptr<T> – это эквивалентно safe_ptr<T, contention_free_shared_mutex<>>
В конце покажем сравнительные графики тестов нашего thread-safe указателя и одних из лучших lock-free алгоритмов из libCDS на процессорах Intel Core i5/i7, Xeon, 2 x Xeon.

В этой статье мы детально разберем атомарные операции и барьеры памяти C++11 и генерируемые ими ассемблерные инструкции на процессорах x86_64.

Далее мы покажем как ускорить работу contfree_safe_ptr<std::map> до уровня сложных и оптимизированных lock-free структур данных аналогичных по функциональности std::map<>, например: SkipListMap и BronsonAVLTreeMap из библиотеки libCDS (Concurrent Data Structures library): github.com/khizmax/libcds

И такую многопоточную производительность мы сможем получить для любого вашего изначально потоко-небезопасного класса T используемого как contfree_safe_ptr<T>. Нас интересуют оптимизации повышающие производительность на ~1000%, поэтому мы не будем уделять внимание слабым и сомнительным оптимизациям.

В этих 3-ех статьях я детально расскажу об атомарных операциях, барьерах памяти и о быстром обмене данными между потоками, а так же о «sequence-points» на примере «execute-around-idiom», а заодно постараемся вместе сделать что-нибудь полезное — умный указатель, который делает любой объект потоко-безопасным для любых операций с его членами переменными или функциями. А затем покажем как используя его достичь производительности высоко-оптимизированных lock-free алгоритмов на 8 — 64 ядрах.

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

От создания нового проекта в Юнити до публикации бета-версии в Стиме прошло 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 — промисы + корутины