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

Лаборатория 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, обсудим дизайн-решения, которые были приняты его авторами и узнаем, почему нам все это нужно знать, чтобы обойти некоторые проблемы при его использовании. Готовы? Ну тогда поехали!

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

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

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

• Параллелизм (часть 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 ↓

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

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

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

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

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

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

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

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