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

В комментариях к прошлому посту был поднят весьма важный вопрос – а будет ли вообще выигрыш в производительности от выгрузки вычислений на интегрированную графику, по сравнению с выполнением только на CPU? Конечно, он будет, но нужно соблюдать определенные правила программирования для эффективных вычислений на GFX+CPU.
В подтверждение моих слов, сразу представлю график ускорения, получаемого при выполнении вычислений на интегрированной графике, для различных алгоритмов и с разной долей вовлеченности CPU. На КДПВ мы видим, что выигрыш более чем весомый.

Это последняя, на сегодняшний день, статья из цикла про внутреннее устройство конкурентных ассоциативных контейнеров. В предыдущих статьях рассматривались hash map, был построен алгоритм lock-free ordered list и контейнеры на его основе. За бортом остался один важный тип структур данных — деревья. Пришло время немного рассказать и о них.

Исследования, посвященные алгоритмам конкурентных деревьев, не требующих внешней синхронизации доступа к ним, начались довольно давно — в 70-х годах прошлого века, — и были инициированы развитием СУБД, поэтому касались в основном оптимизации страничных деревьев (B-tree и его модификации).

Развитие lock-free подхода в начале 2000-х не прошло мимо алгоритмов деревьев, но лишь недавно, в 2010-х годах, появилось множество действительно интересных работ по конкурентным деревьям. Алгоритмы деревьев довольно сложны, поэтому исследователям потребовалось время — порядка 10 лет — на их lock-free/non-blocking адаптацию. В данной статье мы рассмотрим самый простой случай — обычное бинарное дерево, даже не самобалансирующееся.

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

Мы приведем краткое описание того, как организован обмен данными в параллельных приложениях на основе MPI, а также ссылки на внешние источники с более подробным описанием. В практической части вы найдете описание всех этапов разработки демонстрационного MPI-приложения «Hello World», начиная с настройки необходимого окружения и заканчивая запуском самой программы.

В предыдущих статьях (раз, два) мы рассматривали классический hash map с хеш-таблицей и списком коллизий. Был построен lock-free ordered list, который послужил нам основой для lock-free hash map.
К сожалению, списки характеризуются линейной сложностью поиска O(N), где N — число элементов в списке, так что наш алгоритм lock-free ordered list сам по себе представляет небольшой интерес при больших N.
Или все же представляет?..

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

Пройдем по следам C++ 2015 Russia далее.
В предыдущей статье мы рассмотрели алгоритм для lock-free ordered list и на его основе сделали простейший lock-free hash map. У этого hash map есть недостаток: размер хеш-таблицы постоянен и не может быть изменен в процессе роста числа элементов в контейнере. Это не представляет проблемы, если мы заранее примерно представляем требуемый объем контейнера. А если нет?

Мне оказали честь — пригласили выступить на первой конференции C++ 2015 Russia 27-28 февраля. Я был насколько наглым, что запросил 2 часа на выступление вместо положенного одного и заявил тему, наиболее меня интересующую — конкурентные ассоциативные контейнеры. Это hash set/map и деревья. Организатор sermp пошел навстречу, за что ему большое спасибо.
Как подготовиться ко столь ответственному испытанию выступлению? Первое — нарисовать презентацию, то есть кучу картинок, желательно близко к теме. Но надо ещё и два часа озвучивать картинки, — как все это запомнить? Как избежать глубокомысленных «ээээмммм», «здесь мы видим», «на этом слайде показано», несвязных прыжков повествования и прочих вещей, характеризующих выступающего c не очень хорошей стороны в части владения родным языком (это я про русский, с C++ я разобрался быстро — никакого кода в презентации, только картинки)?
Конечно, надо записать свои мысли, глядя на слайды. А если что-то написано, то не худо бы и опубликовать. А если публиковать, — то на хабре.
Итак, по следам C++ 2015 Russia! Авторское изложение, надеюсь, без авторского косноязычия, без купюр и с отступлениями по теме, написанное до наступления события, в нескольких частях.

Продолжаем начатый разговор о Intel® Graphics Technology, а именно о том, что у нас есть в распоряжении с точки зрения написания кода: прагмы offload и offload_attribute для оффлоадинга, атрибуты target(gfx) и target(gfx_kernel), макросы __GFX__ и __INTEL_OFFLOAD, интринсики и набор API функций для асинхронного оффлоада. Это всё, что нужно нам для счастья. Чуть было не забыл: конечно, нам нужен компилятор от Intel и магическая опция /Qoffload.

Но обо всё по порядку. Одна из основных идей – это относительно легкая модификация существующего кода, выполняемого на CPU для его выполнения на интегрированной в процессор графике.

Всем привет!

У нас большая удача! Нам удалось договориться с Дмитрием Леневым, уникальным специалистом, разработчиком MySQL Server с 11-летним стажем, о выступлении на CodeFreeze. Москвичи, обязательно приходите!

Итак, в четверг, 19 февраля, в 20:00 в московском офисе Mail.Ru состоится встреча CodeFreeze с Дмитрием Леневым, разработчиком MySQL Server в компании Oracle. Доклад будет посвящен обзору менеджеров блокировок данных в MySQL (включая блокировки метаданных, таблиц и блокировок InnoDB). Будут обсуждаться предназначение каждого из видов и архитектура этих менеджеров.

OpenMP* — довольно популярная модель параллельного программирования, особенно для высокопроизводительных вычислений. Но чтобы этой высокой производительности достичь, OpenMP конструкции частенько приходится «настраивать». И здесь не обойтись без хорошего профилировщика. Большинство профилировщиков выдают данные о производительности, ассоциированные с функциями или циклами, но не дают картины по конкретным OpenMP регионам. В результате программист теряет контекст. А без OpenMP-контекста диагностика дисбалансов или накладных расходов становится весьма затруднительной.
Intel VTune Amplifier XE умеет профилировать OpenMP регионы. Свежая версия 2015 Update 2 делает анализ гораздо более простым и понятным, благодаря представлению данных в «OpenMP терминах». Инструмент показывает время параллельных и последовательных регионов, разницу между фактическим и идеализированным временем исполнения региона, разбивку по параллельным циклам и загрузку ЦПУ по каждому региону в отдельности.
Пользователь может легче понять, куда вкладывать усилия в первую очередь, благодаря метрике «potential gain». Классификация накладных расходов помогает определить причину неэффективности – например, ожидание из-за дисбаланса нагрузки или на «замке» из-за синхронизации.
Статья описывает некоторые типы OpenMP проблем, определяемых VTune Amplifier, как их нужно понимать и устранять.

Здравствуйте. В этой статье я расскажу про свой хобби-проект не-фон неймановского компьютера. Архитектура соответствует функциональной парадигме: программа есть дерево применений элементарных функций друг к другу. Железо — однородная статическая сеть примитивных узлов, на которую динамическое дерево программы спроецировано, и по которой программа «ползает» вычисляясь.


Примерно так работает дерево, только здесь для наглядности вычисляются арифметическое выражение, а не комбинаторное; шаг на рисунке — один такт машины.

Сейчас готов ранний прототип, существующий как в виде потактового программного симулятора, так и в виде реализации на ПЛИС.

В посте речь пойдет о написании утилиты для нагрузочного тестирования HTTP сервисов на Node.js, а также описание самого инструмента и области его использования.

Статей про double-checked locking на Хабре было столько, что казалось бы ещё одна — и Хабр лопнет. Вот только по Java неплохие публикации: Реализация Singleton в JAVA, Правильный Singleton в Java, А как же всё-таки работает многопоточность? Часть II: memory ordering или вот замечательный пост от TheShade (слава web-archive!). В наши дни, наверно, каждый Java-разработчик слышал, что если используешь DCL, будь добр объявить переменную volatile. Найти сегодня в коде известных опенсорсных проектов DCL без volatile довольно трудно, но оказалось, что проблемы ещё не полностью решены. Поэтому я добавлю небольшую заметку по теме с примерами из реальных проектов.

Иногда складывается ощущение, что программисты не включают мозги и не пытаются понять, как что работает, а просто следуют простым и понятным правилам вроде «объяви переменную volatile, используй DCL, и всё будет хорошо». К сожалению, такой подход в программировании не всегда работает.

Введение

Сравнивая две различные технологии параллельного программирования: потоки POSIX и потоки C++11, можно заметить, что в последних отсутствует аналог типа barrier_t из библиотеки pthread.

Довольно странно, что такой важный примитив синхронизации отсутствует в стандартной библиотеке. В этой статье пойдёт речь о том, как сделать барьер с использованием только библиотек, входящих в набор стандарта C++11.

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

Начнём создавать свой барьер, с блэкджеком и ...

Привет, Хабр!

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

В текущем модуле на примере построения гистограммы будут показаны две оптимизационные техники для улучшения автоматической векторизации кода компилятором и приведены результаты производительности для Intel Xeon CPU и Intel Xeon Phi копроцессора.

Содержание

Часть 1: Введение.
Часть 2: Аппаратное обеспечение GPU и шаблоны параллельной коммуникации.
Часть 3: Фундаментальные алгоритмы GPU: свертка (reduce), сканирование (scan) и гистограмма (histogram).
Часть 4: Фундаментальные алгоритмы GPU: уплотнение (compact), сегментированное сканирование (segmented scan), сортировка. Практическое применение некоторых алгоритмов.
Часть 5: Оптимизация GPU программ.
Часть 6: Примеры параллелизации последовательных алгоритмов.
Часть 7: Дополнительные темы параллельного программирования, динамический параллелизм.

Еще одна статья о CUDA — зачем?

На Хабре было уже немало хороших статей по CUDA — раз, два и другие. Однако, поиск комбинации «CUDA scan» выдал всего 2 статьи никак не связанные с, собственно, алгоритмом scan на GPU — а это один из самых базовых алгоритмов. Поэтому, вдохновившись только что просмотренным курсом на Udacity — Intro to Parallel Programming, я и решился написать более полную серию статей о CUDA. Сразу скажу, что серия будет основываться именно на этом курсе, и если у вас есть время — намного полезнее будет пройти его.

Со времени предыдущего поста из жизни lock-free контейнеров прошло немало времени. Я рассчитывал быстро написать продолжение трактата об очередях, но вышла заминка: о чем писать, я знал, но реализации на C++ этих подходов у меня не было. «Не годится писать о том, что сам не попробовал», — подумал я, и в результате я попытался реализовать в libcds новые алгоритмы очередей.
Сейчас настал момент, когда я могу аргументированно продолжить свой цикл. В данной статье закончим с очередями.

Кратко напомню, на чем я остановился. Были рассмотрены несколько интересных алгоритмов lock-free очередей, а под занавес приведены результаты их работы на некоторых синтетических тестах. Главный вывод — всё плохо! Надежды на то, что lock-free подход на магическом compare-and-swap (CAS) даст нам пусть не линейный, но хотя бы какой-то рост производительности с увеличением числа потоков, не оправдались. Очереди не масштабируются. В чем причина?..

Перевод статьи Джефа Прешинга Atomic vs. Non-Atomic Operations. Оригинальная статья: http://preshing.com/20130618/atomic-vs-non-atomic-operations/

В Сети уже очень много написано об атомарных операциях, но в основном авторы рассматривают операции чтения-модификации-записи. Однако, существуют и другие атомарные операции, например, атомарные операции загрузки (load) и сохранения (store), которые не менее важны. В этой статье я сравню атомарные загрузки и сохранения с их неатомарными аналогами на уровне процессора и компилятора C/C++. По ходу статьи мы также разберемся с концепцией «состояния гонок» с точки зрения стандарта C++11.

В этой статье я попытаюсь описать терминологию, используемую для описания систем, способных исполнять несколько программ параллельно, то есть многоядерных, многопроцессорных, многопоточных. Разные виды параллелизма в ЦПУ IA-32 появлялись в разное время и в несколько непоследовательном порядке. Во всём этом довольно легко запутаться, особенно учитывая, что операционные системы заботливо прячут детали от не слишком искушённых прикладных программ.



Используемая далее терминология используется в документации процессорам Intel. Другие архитектуры могут иметь другие названия для похожих понятий. Там, где они мне известны, я буду их упоминать.

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