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

Добрый день.
15 мая была проведен первый вебинар (из 16) курса «Multicore programming in Java». Тут я бы хотел опубликовать материалы, упоминавшиеся на лекции: ссылки на источники, термины, картинки, задание. Возможно кто-то сочтет их полезными для себя.

Также я веду курс «Scala for Java Developers» на платформе для онлайн-образования udemy.com (аналог Coursera/EdX).

Введение

• Закон Мура, Moore’s law
• Herb Satter, “The Free Lunch Is Over”
• Закон Амдала, Amdahl’s law

“Железо”

Стоит «посмотреть картинки» в следующих источниках

• «What Every Programmer Should Know About Memory»
• «The Architecture of the Nehalem Processor and Nehalem-EP SMP Platforms»
• «A Primer on Memory Consistency and Cache Coherence»

В последнее время в научных публикациях всё чаще упоминается алгоритм достижения консенсуса в распределенных системах под названием Paxos. Среди таких публикаций ряд работ сотрудников Google (Chubby, Megastore, Spanner) ранее уже частично освещенных на хабре, архитектуры систем WANdisco, Ceph и пр. В то же время, сам алгоритм Paxos считается сложным для понимания, хоть и основывается он на элементарных принципах.

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

Доброго времени суток, хотел бы поделиться с сообществом своей небольшой библиотектой.
Я программирую на С/C++, и, к сожалению, в рабочих проектах не могу использовать стандарт C++11. Но вот пришли майские праздники, появилось свободное время и я решил поэкспериментировать и по-изучать этот запретный плод. Самое лучшее для изучения чего либо — это практика. Чтение статей о языке программирования научит максимум лучше читать, поэтому я решил написать маленькую библиотеку для асинхронного выполнения функций.
Сразу оговорюсь, что я знаю, что существует std::future, std::async и тп. Мне было интересно реализовать самому нечто подобное и окунуться в мир лямбда-функций, потоков и мьютексов с головой. Праздники — отличное время для велопрогулок.

Определение

Параллельное программирование сложно. При использовании систем с общей памятью не обойтись без синхронизации доступа параллельных процессов/потоков к общему ресурсу (памяти). Для этого используются:

• блокировки (mutex);
• алгоритмы без блокировки (lockless, lock-free);
• транзакционная память.

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

Введение

Прочитав статьи TimeCoder — «Путешествия во времени и программирование» [1, 2] я вспомнил свои скромные практические исследования в программировании, связанные с реализацией разветвляющихся миров. Однажды товарищ по работе подкинул мне интересную задачу, но решить я ее до сих пор не смог. Задача о том, как нагрузить станки на производстве. Даже не программисту было понятно, что нужен простой перебор, но я так и не смог придумать подходящую структуру данных для обеспечения вычисляющего алгоритма. Задача из реального мира, поэтому я решил попробовать реализовать в программе реальный мир в той части, который требуется для вычисления задачи. Каждый раз, когда в дальнейших вычислениях стоял выбор между двумя действиями — происходило «создание двух новых миров» с разным решением в каждом. Дальше каждый мир развивался своим путем.

Под катом я расскажу, как развивалась идея, и чем мне помог ерланг. Практика — критерий истины!

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

Сразу раскрою мысль, вынесенную в заголовок. Использование потоков (также именуемых нити, треды, англ. threads) и средств прямой манипуляции ими (создание, уничтожение, синхронизация) для написания параллельных приложений оказывает столь же пагубное влияние на сложность алгоритмов, качество кода и скорость его отладки, какое вносило использование оператора Goto в последовательных программах.
Как когда-то программисты отказались от неструктурированных переходов, нам необходимо отказаться от прямого использования потоков сейчас и в будущем. И так же, как каждый из нас использует структурные блоки вместо Goto, вместо потоков должны использоваться структуры, построенные поверх них. Благо, все инструменты для этого появились во вполне традиционных языках.
^{Автор фото: Rainer Zenz}

От переводчика

Лично я просто невероятно обрадовался новой возможности. Как раз не так давно одолел Pro .Net Perfomance, в которой одна из глав была посвящена параллельности, и векторизации в частности. Вывод, сделанный авторами: «К сожалению, использование векторизации возможно исключительно на С++, выполнение кода на видеокарте — возможно и средствами .Net, однако C++ AMP оставляет любые управляемые библиотеки GPGPU далеко позади, поэтому, к сожалению, в данных задачах рекомендуем использовать подключаемые C++ сборки.» Поэтому рад сообщить, что по крайней мере одна проблема решена. Что ж, приступим!

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

Безусловно, памяти ваших серверов можно найти лучшее применение, чем хранение мусора. Поэтому не повторяйте мою ошибку. А именно: не стоит пытаться хранить в ThreadLocal ссылки на этот самый ThreadLocal, или на какой-то граф объектов, в конечном итоге ссылающийся на этот самый ThreadLocal.

Имитационное моделирование с использованием методов Монте-Карло в наше время используется практически во всех областях операционной деятельности, где требуется многократное принятие решений по итогам анализа поступающих из внешнего мира данных. При этом важную роль начинает играть качество, производительность и доступность генераторов случайных чисел, использующихся для придания абстрактному методу черт реальной задачи, решаемой специалистом. Как я недавно выяснил, этот вопрос начинает играть решающее значение при переходе к параллельному программированию… Вы тоже столкнулись с этой проблемой, и хотите знать, как в Windows можно быстро получить массивы случайных чисел с нужным распределением?

Аннотация

В данной статье хочу рассказать как можно эффективно распараллелить алгоритм BFS — поиск в ширину в графе с использованием графических ускорителей. В статье будет приведен подробный анализ полученного алгоритма. Вычисления выполнялись на одном GPU GTX Titan архитектуры Kepler.

Введение

В последнее время все большую роль играют графические ускорители (GPU) в не графических вычислениях. Потребность их использования обусловлена их относительно высокой производительностью и более низкой стоимостью. Как известно, на GPU хорошо решаются задачи на структурных сетках, где параллелизм так или иначе легко выделяется. Но есть задачи, которые требуют больших мощностей и используют неструктурные сетки. Примером такой задачи является Single Shortest Source Path problem (SSSP) – задача поиска кратчайших путей от заданной вершины до всех остальных во взвешенном графе. Решение данной задачи рассмотрено мной в этой статье. Вторым примером задачи на неструктурных сетках является задача Breadth First Search (BFS) — поиска в ширину в неориентированном графе. Данная задача является основной в ряде алгоритмов на графах. Также она немного проще, чем поиск кратчайшего пути. На данный момент алгоритм BFS используется как основной тест для рейтинга Graph500. Далее рассмотрим, как можно использовать идеи решения задачи SSSP в задаче BFS. Про архитектуру GPU компании Nvidia и об упомянутых алгоритмах уже много написано, поэтому в этой статье я не стану дополнительно писать про это. Так же, надеюсь, что понятия warp, cuda блок, SMX, и прочие базовые вещи, связанные с CUDA читателю знакомы.

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

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

Введение

Я описываю результаты применения способов оптимизации вычислений на CUDA при моделировании плазмы. Вычисления производятся с использованием Java-привязки к CUDA (JCUDA) [1] на GT630 (Kepler). Моделирование происходит как решение задачи Коши — задание значений параметров в начальный момент времени, затем приращение времени и перерасчет всех уравнений, и т.д. многократно. Вычисления происходят в двойной точности (double). Правильность полученных результатов подтверждена вычислениями на CPU без JCUDA.

Многие из новейших суперкомпьютеров основаны на аппаратных ускорителях вычислений (accelerator). включая две самые быстрые системы согласно TOP500 от 11/2013. Ускорители распространяются так же и на обычных PC и даже появляются в портативных устройствах, что ещё больше способствовует росту интереса к программированию ускорителей.

Такое широкое применение ускорителей является результатом их высокой производительности, энергоэффективности и низкой стоимости. Например, если сравнить Xeon E5-2687W и GTX 680, выпущенные в марте 2012, мы увидим, что GTX 680 в четыре раза дешевле, имеет в 8 раз большую производительность операций одинарной точности и в 4 раза большую пропускную способность памяти, а так же обеспечивает более 30 раз большую производительность в пересчёте на доллар и в 6 раз большую производительность на ватт. Исходя из таких сравнительных результатов, ускорители должны бы использоваться везде и всегда. Почему же этого не происходит?

Mozilla выпустила новую версию компилятора Rust 0.9 и соответствующих инструментов.

Rust — это компилируемый и мультипарадигмальный язык для системного программирования, который позиционируется как альтернатива С/С++. Визуально он похож на C, но отличается в деталях синтаксиса и семантики. Идеально подходит для параллельных вычислений.

Разработчики говорят о существенном улучшении рантайма и подсистемы ввода-вывода. Так, в компиляторе появились статические ссылки и поддерживается оптимизация во время линковки (link-time). В языке уменьшено количество разных видов замыканий, чтобы упростить и сделать более логичным синтаксис.

   Эта статья посвящена языку R. Он не так широко распространен на территории ex-USSR, как Matlab и тем более Python, но, безусловно, заслуживает внимания. Нельзя не отметить, что R — фактически стандарт для Data Science (хотя тут хорошо написано, что не R единым живут data scientists). Богатый синтаксис, совместимость с legacy кодом (что весьма важно в научных приложениях), удобная среда разработки RStudio и наличие огромного числа библиотек в CRAN делают R таковым.

Я очень часто по работе слышу вопрос, задаваемый из, большей частью, академической среды, ввиду огромного количества выполняемых вычислений именно там: «Почему наши результаты разные от запуска к запуску одного и того же приложения? Мы же ничего не меняем в нем». Стоит отметить, разговор про это уже был, но лишь частично отвечающий на вопрос. Попробую рассказать про эту проблему ещё чуть-чуть.

Высоконагруженные системы, построенные по модели акторов – это тренд сегодняшнего времени. Вот далеко неполный перечень статей на хабре, в которых, в той или иной степени, упоминается данная модель или одна из ее реализаций, например,1, 2, 3, 3, 4, 5, 6, 7. Есть хорошая статья в википедии, рассказывающая про акторы. К сожалению, после ее прочтения, у меня осталось много вопросов, ответы на которые я смог найти только в первоисточниках. Результаты этого обзора я и хочу представить Вашему вниманию.

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

Мой недавний пост про OpenMP 4.0 натолкнул меня на мысль, что было бы неплохо написать и про Intel Cilk Plus, потому что модель программирования весьма интересная и уж точно заслуживает отдельного внимания. Ну и раз её часть стала фактически новым стандартом OpenMP, то, вероятно, были на то веские причины.