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

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

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

• Параллелизм (часть 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" — описание алгоритмов и прочее.

В предыдущих частях опуса (1, 2, 3) мы рассмотрели внутреннее строение lock-free map и убедились, что все основные операции — поиск, добавление и удаление ключа — могут быть выполнены без глобальных блокировок и даже в lock-free манере. Но стандартный std::map поддерживает ещё одну очень полезную абстракцию — итераторы. Возможно ли реализовать итерабельный lock-free map?
Ответ на этот вопрос — под катом.

Прим. перев.: Это перевод истории о том, как нелегко оказалось написать параллельную быструю сортировку (quicksort) на Хаскеле. Оригинал статьи написан в 2010 году, но, мне кажется, он до сих пор поучительный и во многом актуальный.

Есть много примеров того, как Хаскель делает простые проблемы сложными. Вероятно, самый известный из них—это решето Эратосфена, которое легко написать на любом императивном языке, но настолько сложно написать на Хаскеле, что почти все решения, которые преподавались в университетах и использовались в исследованиях последние 18 лет, оказались неправильными. На их несостоятельность обратила внимание Мелисса О'Нил [Melissa O'Neill] в своей важной научной работе "Настоящее решето Эратосфена". В ней приводится прекрасное описание того, что не так в старых подходах, и как их надо исправить. Решением Мелиссы было использовать очередь с приоритетом [priority queue] для реализации решета. Правильное решение оказалось в 10 раз длиннее, чем намного более простое решение на F# и в целых 100 раз длиннее, чем оригинальный изуродованный алгоритм на Хаскеле.

Всё течет, всё меняется, и OpenMP продолжает активно развиваться. Почти три года назад стандарт стал поддерживать не только параллелизм по задачам, но и по данным (векторизацию), про что я подробно писал. Самое время посмотреть, что появилось в последней версии, выпущенной в ноябре 2015, и что уже поддерживается на данный момент в компиляторах от Intel. Ну что, приступим!

Все готово, чтобы рассказать Хабр аудитории о применении FPGA в сфере научных высокопроизводительных вычислений. И о том, как на данной задаче надо удалось значительно обскакать GPU (Nvidia K40) не только в метрике производительность на ватт, но и просто с точки зрения скорости вычисления. В качестве FPGA платформы использовался кристалл Xilinx Virtex-7 2000t, подключенный по PCIe к хост компьютеру. Для создания аппаратного вычислительного ядра использовался язык C++ (Vivado HLS).

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

Unified Parallel C (UPC) — это расширение языка C, разработанное для высокопроизводительных вычислений на крупномасштабных параллельных машинах. Язык представляет единую программную модель для систем с общей и разделенной памятью. Количество параллелизма фиксируется на старте программы, обычно с одним потоком на ядро процессора.

» Официальный сайт UPC
» Официальный сайт Berkeley UPC

В своё время возникли определенные трудности с разворачиванием UPC и отсутствием каких-либо подсказок по первым шагам ни в русскоязычном, ни в англоязычном сегменте интернета, кроме официальной инструкции INSTALL.TXT, которую пришлось переваривать.

Чтобы сей опыт не пропал даром, я решил написать статью по установке UPC в различных средах.

Традиционно московская конференция CEE-SECR (Central & Eastern European Software Engineering Conference in Russia) была про софтвер, но в этом году ее организаторы решили поэкспериментировать и впустить темных демонов хардвера. Причем не из чего-то народного типа Ардуино, а из уровней посуровее: микроархитектуры микропроцессоров, прототипирования систем на кристалле с помощью микросхем ПЛИС/FPGA, и автоматической генерации тестов для процессоров во время их разработки. Чтобы привязать данный материал к чему-то знакомому для программистов, в хардверной теме возникли приложения встроенных процессоров для интернета вещей, связь лицензируемых микропроцессорных ядер с российскими микропроцессорными проектами, обучение хардверу в российских университетах, а также российские встроенные операционные системы реального времени для тех применений, куда нельзя впускать длинный нос американского Госдепа.

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

Привет друзья! Будучи студентами одного небезызвестного образовательного проекта, мы с bo_0m, после вводной лекции по курсу Углубленное программирование на Java, получили свое первое домашнее задание. Необходимо было реализовать программу, которая бы перемножала матрицы. И всё бы ничего, да так совпало, что на следующей неделе должна была состояться конференция Joker, и наш преподаватель решил отменить по такому случаю занятие, подарив нам несколько часов свободного пятничного вечера. Не пропадать же времени зря! Раз никто не торопит, то можно подойти к делу творчески.

Welcome, under the hood ↓

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

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

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

Большинство ПО кластерных систем предполагает наличие файловой системы доступной со всех узлов кластера. Эта файловая система используется для хранения ПО, данных, для организации работы некоторых кластерных подсистем и т.д. Требования на производительность такой FS могут сильно отличаться для разных задач, однако, чем она выше, тем считается, что кластер более устойчив и универсален. NFS сервер на мастер-узле является минимальным вариантом такой FS. Для больших кластеров NFS дополняется развертыванием LustreFS — высокопроизводительной специализированной распределенной файловой системы, использующей несколько серверов в качестве хранилища файлов и несколько метаинформационных серверов. Однако такая конфигурация обладает рядом свойств, которые сильно затрудняют работу с ней в случае, когда клиенты используют независимые виртуализированные кластера. В системе HPC HUB vSC для создания разделяемой FS используется широко известное решение CEPH и файловая система GFS2.

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

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

Лучшие спикеры из России, США и Европы приедут, чтобы поделиться с вами своими мыслями и идеями.

На конференции 14 октября издательство «Питер» представит книги по IT, которые можно будет приобрести по издательской цене.

Это будет уже четвертый Joker в Питере. Спикеров и докладов, спонсоров и стендов, участников и экспертов будет больше, чем в прошлые разы, поэтому каждому пришедшему будет чем заняться!

На первой неделе сентября этого года вышла в свет новая версия продукта Intel Parallel Studio XE 2017. Давайте разбираться, что интересного появилось в ней.

Стремитесь узнать про все этапы проектирования и производства микросхем от идеи до фабрики? Хотите построить прототип своей собственной системы на кристалле используя микросхемы ПЛИС? Интересуетесь программированием микроконтроллеров и операционными системами реального времени? Тогда приходите на семинары, которые совместно организовали американские, российские и украинские компании и университеты. Эти семинары будут проходить в Москве, Зеленограде, Санкт-Петербурге, Киеве и Алма-Ате во второй половине октября и первой половине ноября:

• Nanometer ASIC — двухдневный семинар, описывающий все этапы проектирования и производства микросхем: создание спецификации, описание цифровой логики на языках описания аппаратуры Verilog и VHDL на уровне регистровых передач, логический синтез, размещение и трассировка, создание фотошаблонов и производство микросхем на фабрике. Для проведения этих семинаров из Калифорнии приезжает Чарльз Данчек, преподаватель такого курса в University of California Santa Cruz Extension in Silicon Valley. В Москве семинары проходят под эгидой Фонда инфраструктурных и образовательных программ (ФИОП) РОСНАНО и его дочерней компании eNANO.
  
  
• MIPSfpga — устройство систем на кристалле, протоколы внутри чипа и вне чипа, интеграция процессорного ядра с памятью и устройствами ввода-вывода, наблюдение работы кэша и конвейера промышленного процессора на плате с ПЛИС. Семинары проводятся под эгидой британской компании Imagination Technologies, известной как разработчик графического процессора PowerVR внутри Apple iPhone.
  
  
• Connected MCU — введение в использование микроконтроллеров, организация параллельности на одном процессоре, использование прерываний, таймеров, конечных автоматов реализованных в софтвере, и наконец — введение в RTOS и лабораторное занятие с использованием операционной системы FreeRTOS. Материалы семинаров подготовлены профессором Александром Дин из университета Северной Каролины в сотрудничестве с Imagination и Microchip Technology.
  

Андрей Саломатин ( filipovskii_off )

Сегодня каждый день появляются новые языки программирования — Go, Rust, CoffeeScript — все, что угодно. Я решил, что я тоже горазд придумать свой язык программирования, что миру не хватает какого-то нового языка…

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

Что в нем не очень обычно, что может даже оттолкнуть, на первый взгляд, — это то, что в Schlecht!Script функции имеют цвет.

Виртуальный суперкомпьютер (vSC) — это современная альтернатива использованию собственных суперкомпьютерных мощностей для наукоемкого бизнеса и научных групп при решении ресурсоемких задач. В процессе бурного развития облачных технологий клаудизация начала проникать в наиболее сложные IT-сферы — суперкомпьютинг и распределенные вычисления. Один из возможных подходов к задаче клаудизации HPC реализован компанией HPC HUB.

Блокировки в общем и мьютексы, как их частная реализация, имеют давнюю историю неправильной оценки скорости их работы. Ещё в 1986-ом году в одной из Usenet-конференций Matthew Dillon написал: «Большинство людей ошибочно уяснили себе, что блокировки работают медленно». Сегодня, спустя многие годы, можно констатировать, что ничего не изменилось.

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

Одна из причин заблуждений о скорости работы блокировок состоит в том, что многие программисты не отличают понятия «легковесный мьютекс» и «мьютекс, как объект ядра ОС». Всегда используйте легковесные мьютексы. К примеру, если вы программируете на С++ под Windows, то ваш выбор это критические секции.

Второй причиной заблуждений могут служить, как это ни парадоксально, бенчмарки. К примеру, далее в этой статье мы будем измерять производительность блокировок под высокой нагрузкой: каждый поток будет требовать блокировку для выполнения любого действия, а сами блокировки будут очень короткими (и, в результате, очень частыми). Это нормально для эксперимента, но такой способ написания кода — это не то, что вам нужно в реальном приложении.