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

Здравствуйте, уважаемые читатели.

Предлагаю всем, кто заинтересуется, обсудить некоторые основные идеи классического и параллельного программирования в расширении C++, основанном на процедурах/функциях с планированием повторного входа (ПППВ/ФППВ). В минимальном варианте — это процедура или функция, у которой есть статический или динамический план исполнения.

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

У нас праздник! В начале июля в Санкт-Петербурге пройдет SPTCC 2017, летняя школа по параллельному программированию. Одним из лекторов школы станет Морис Херлихи (Maurice Herlihy), легенда параллельного программирования, один из авторов знаменитого учебника «The Art of Multiprocessor Programming».

В четверг, 6 июля, в 19:00 в Университете ИТМО Морис выступит на встрече JUG.ru. На этот раз мы будем говорить не про Java. Тема встречи — транзакционная память.

О чем же нам расскажет Морис?

Транзакционная память

Новое поколение процессорных архитектур предоставляет нам аппаратную транзакционную память (Hardware Transactional Memory — HTM), механизм синхронизации для быстрых транзакций в оперативной памяти. В данном докладе будет показано, что HTM это не просто более быстрый путь для релизации старых-добрых monitor-ов и latch-ей. На самом деле, HTM обеспечивает фундаментальные позитивные изменения в том, как мы программируем многоядерные машины (и возможно даже базы данных), позволяя нам переосмыслить базовые примитивы синхронизации, такие, как lock-и, управление памятью, и многообразие многопоточных структур данных.

В конце мая в Петербурге в ПОМИ РАН прошла международная студенческая школа «Recent Advances in Algorithms». Идея школы заключалась в том, чтобы ведущие учёные рассказали о последних достижениях в области алгоритмов. В результате у нас получился следующий список курсов.

Цель публикации показать начинающим 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, — умение писать правильный многопоточный код, используя мьютексы или другие высокоуровневые объекты синхронизации, например, семафоры или события.