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

В предыдущей статье мы обсудили основу метода молекулярной динамики, в том числе вычисление энергии и сил взаимодействия между частицами с заданными парными потенциалами. А что, если частицы обладают некоторым электрическим зарядом? Например, в том случае, если мы моделируем кристалл поваренной соли, состоящий из ионов Na⁺ и Cl^-. Или водный раствор, содержащий те или иные ионы. В этом случае, кроме парных потенциалов типа Леннарда-Джонса между ионами действуют силы электростатического взаимодействия, т.е. закон Кулона. Энергия такого взаимодействия для пары частиц i-j равна:

$$

где q – заряд частицы, r_ij – расстояние между частицами, С – некоторая постоянная, зависящая от выбора единиц измерения. В системе СИ это — $$, в СГС — 1, в моей программе (где энергия выражена в электронвольтах, расстояние в ангстремах, а заряд в элементарных зарядах) C примерно равно 14.3996.



Ну и что, скажете вы? Просто добавим соответствующее слагаемое в парный потенциал и готово. Однако, чаще всего в МД моделировании используют периодические граничные условия, т.е. моделируемая система со всех сторон окружена бесконечным количеством её виртуальных копий. В этом случае каждый виртуальный образ нашей системы будет взаимодействовать со всеми заряженными частицами внутри системы по закону Кулона. А поскольку Кулоновское взаимодействие убывает с расстоянием очень слабо (как 1/r), то отмахнуться от него так просто нельзя, сказав, что с такого-то расстояния мы его не вычисляем. Ряд вида 1/x расходится, т.е. его сумма, в принципе, может расти до бесконечности. И что же теперь, миску супа не солить? Убьёт электричеством?

И снова здравствуй. Какое-то время назад я писал о другом малоизвестном инструменте для любителей высокой производительности — System.IO.Pipelines. По своей сути, рассматриваемый System.Threading.Channels (в дальнейшем «каналы») построен по похожим принципам, что и Пайплайны, решает ту же задачу — Производитель-Потребитель. Однако имеет в разы более простое апи, которое изящно вольется в любого рода enterprise-код. При этом использует асинхронность без аллокаций и без stack-dive даже в асинхронном случае! (Не всегда, но часто).

Цель данной статьи – поднять вопросы распараллеливания кода программы для численного моделирования методом молекулярной динамики (МД) с помощью технологии CUDA. Зачем это вообще нужно, ведь уже существуют программные пакеты по МД, работающие в том числе и на CUDA? Дело в том, что я развиваю свою собственную концепцию «непостоянного поля сил» (non-constant force field), которая не реализована в существующих МД-программах.

Переделывать чужой код под эти нужды – довольно неблагодарное занятие, поэтому я взялся перенести уже написанный свой последовательный код и заодно поделится некоторыми размышлениями. Кроме того, это ответ на часто мелькающий здесь комментарий к статьям по CUDA, вроде этого .

Итак, что же такое молекулярная динамика? На Хабре уже есть несколько постов на эту тему, например здесь или вот здесь. Кратко, МД – это метод, позволяющий моделировать движение множества частиц (в том числе атомов, ионов, молекул) и рассчитывать коллективные свойства системы, зависящие от этого движения. Как это работает? Допустим для множества из N частиц заданы некоторые начальные координаты, скорости, массы и (главное!) законы взаимодействия между ними. Изменяем координаты согласно скоростям. На основе законов взаимодействия вычисляем силы, действующие между частицами. Раз знаем силу и массу – знаем ускорение. Поправляем скорость с учетом ускорения. И снова переходим к изменению координат. И так повторяем тысячи раз, пока не надоест не наберем достаточную статистику.

Здравствуйте, уважаемые посетители Хабра!

В этой статье речь пойдёт о связном списке, многопоточности и С++. Сразу отмечу, что были все шансы положить эту работу «на полочку» и использовать в небольшом количестве личных проектов. Вместо этого я всё-таки решил выложить её на суд общественности – вдруг это действительно покажется кому-нибудь полезным или интересным. Более того, если окажется, что кто-нибудь когда-нибудь уже успел сделать что-нибудь подобное, укажите мне эти материалы, пожалуйста. Однако сколько я ни пытался гуглить на эту тему, все попытки были безуспешны.

Также отмечу, что речь пойдёт не о классическом связном списке, а о моём творческом переосмыслении использования этой структуры данных в многопоточном окружении. Я рассматривал сценарий неупорядоченного интенсивного многопоточного обращения к списку. Это означает, что любой поток в любой момент независимо от других может получить доступ к списку и произвести требуемые операции. Если он только добавляет или изменяет элементы, это ещё полбеды. Если же он ещё и удаляет элементы, могут возникнуть различные интересные особенности.

Этот проект, которым я занимался на правах хобби и саморазвития, по ряду причин растянулся на весьма длительный срок. Кроме того, по мере работы над ним я интенсивно учился: проект начинался без знания и понимания STL и проектировался соответственно, используя только внутренние средства собственно языка С++. Однако потом я весьма серьёзно его модифицировал с учётом STL и даже под STL. Что у меня из этого получилось, судить вам, уважаемые читатели.

Признаюсь, но я не знаю Python. Просто потому, что не использую. Тем не менее, взявшись за его освоение, а также в попытках расшифровать загадочную аббревиатуру GIL, вышел на статью с описанием «необъяснимых магических явлений» параллельного варианта CPU-зависимой функции на Python. Возникло желание перепроверить данный тест и сравнить с эквивалентной реализацией в форме модели конечного автомата (Finite-state machine или сокращенно FSM) в среде Визуального Компонентного Программирования (автоматного) — ВКП(а).

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

В то же время есть ситуации, когда зависимости от CPU может почти не быть (в этом мы убедимся). Речь идет о языках, вычислительная модель которых отлична от типовой архитектуры процессоров. Вычислительная модель Python, ей соответствует, а автоматная модель вычислений, о которой далее пойдет речь, имеет другую архитектуру и это будет определять специфику ее тестирования. Какая будет скорость и будет ли иметь место мистика выяснится в процессе тестирования «автоматного кода».

^{Фото: James P. Blair/National Geographic Creative}

Вы когда-нибудь сталкивались со следующей проблемой в rust, когда использовали std::sync::Mutex в асинхронном коде?

 7  |     tokio::spawn(/* some future here */);
    |     ^^^^^^^^^^^^ future returned by `fut` is not `Send`
    |
127 |         T: Future + Send + 'static,
    |                     ---- required by this bound in `tokio::task::spawn::spawn`
    |

Привет, Хабр! Я хочу рассказать, как я решал проблему эффективного конкурентного исполнения asyncio задач в Celery.

Новый лабник «Цифровой синтез» продолжает традиции учебника Дэвида Харриса и Сары Харрис «Цифровая схемотехника и архитектура компьютера», скачивания которого завалили британский сайт. Лабник позволяет потрогать руками всю теорию из Харрис & Харрис на плате FPGA, от мигания лампочек до процессора. В лабнике также разобрана концепция конвейерной обработки, без которой вы не пройдете интервью на работу проектировщиком ни в одну микроэлектронную компанию. В конце показан путь от FPGA до ASIC, массовых микросхем, которые стоят в айфонах, теслах и ИИ-акселераторах.

В книжке есть интервью команды из Питера, которую Intel привез в свою штаб-квартиру в Silicon Valley за их победу на конкурсе Innovate FPGA. Книжку «Цифровой синтез: практический курс» поддержала ведущая компания в автоматизации пректирования микросхем Cadence Design Systems (на фото выше сибирячка Наташа стоит с FPGA платой перед штаб-квартирой Cadence в Silicon Valley — в посте будет ее видео).

Лабник делался под эгидой Высшей Школы Экономики / МИЭМ (Александр Романов, Вероника Прохорова и Игорь Агамирзян), при этом разные главы в нем писали преподаватели Московского, Киевского и Самарского университетов, Питерского ИТМО, Черниговского политеха и Университета Калифорнии Санта-Круз (Чарльз Данчек, вечернее отделение в Silicon Valley). В создании учебника приняли участие инженеры российских компании IVA Technologies (Станислав Жельнио, аппаратный ускоритель ИИ + образовательный проект schoolMIPS) и ФГУП НПЦАП
(отделение Роскосмоса), американских компаний MIPS, Juniper Networks и AMD. Издало учебник ДМК-Пресс.

Я недавно проводил исследование, в рамках которого было необходимо обработать несколько сотен тысяч наборов входных данных. Для каждого набора — провести некоторые расчеты, результаты всех расчетов собрать вместе и выбрать "лучший" по некоторым критериям. По сути это bruteforce перебор. Тоже самое происходит при подборе параметров ML моделей с помощью GridSearch.

Однако, с некоторого момента размер вычислений может стать для одного компьютера великоват, даже если запускать ее в несколько процессов с помощью joblib. Или, если сказать точнее, он становится слишком долгим для нетерпеливого экспериментатора.

И поскольку в современной квартире сейчас можно найти больше одного "недогруженного" компьютера, а задача явно подходит для массового параллелизма — пора собрать свой домашний кластер и запускать такие задачи на нем.

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

Хотя есть и другой вариант. Не надо ничего пока менять и/или на что-то влиять. Пусть будет многопоточность и корутины, пусть будет… и параллельное автоматное программирование (АП). Пусть соревнуются и, когда это необходимо и возможно, дополняют друг друга. В этом смысле у современного параллелизма есть, как минимум, один плюс — он позволяет это делать.

Ну, так что, посоревнуемся!?

В данном посте будет рассказано, как реализовать сортировку на Java c использованием ExecutorService. Общая суть сортировки в следующем:

1. Массив разбивается на части
2. Каждая часть массива сортируется
3. Идем по упорядоченным массивам, сливаем их в один

Здесь применяются идеи сортировки слиянием, но массив разбивается только на две части (рекурсия не используется).

Для слияния можно использовать следующую функцию:

1. Введение

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

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

Наша цель — получить из лапши коллбэков:

    abActor.getA(ABActor::GetACallback([this](int a) {
        abActor.getB(ABActor::GetBCallback([a, this](int b) {
            abActor.saveAB(a - b, a + b, ABActor::SaveABCallback([this](){
                abActor.getA(ABActor::GetACallback([this](int a) {
                    abActor.getB(ABActor::GetBCallback([a, this](int b) {
                        std::cout << "Result " << a << " " << b << std::endl;
                    }));
                }));
            }));
        }));
    }));

Что-то вроде:

const int a = co_await actor.abActor.getAAsync();
const int b = co_await actor.abActor.getBAsync();
co_await actor.abActor.saveABAsync(a - b, a + b);
const int newA = co_await actor.abActor.getAAsync();
const int newB = co_await actor.abActor.getBAsync();
std::cout << "Result " << newA << " " << newB << std::endl;

Итак, приступим.

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

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

В этой статье я расскажу:

• Что за задача такая, о которой идет речь;
• Подробнее об интегральных изображениях;
• Как использовать интегральные изображения для приближенного решения гравитационной задачи N тел применительно к дискретному полю импульсов (масс-скоростей);
• Какой недостаток имеет это решение и как его исправить;
• И, наконец, как за константное время вычислить центр масс для произвольного региона.

1. Введение

Влияние подпрограмм (англ. subroutine) на программирование без преувеличения огромно. Введенные на заре программирования они не теряют своей актуальности и поныне. Без них практическое программирование представить просто невозможно. Хотя с формальной точки зрения они не так уж и нужны, т.к. чистую теорию интересуют больше свойства алгоритма, чем его размеры.

В теории автоматов понятие вложенных автоматов, на базе которых строилась бы практика автоматных подпрограмм (АПП), обсуждается редко. Подобная (вложенная) иерархическая организация автоматов, если и рассматривается, то весьма поверхностно. Одной из причин подобного отношения может служить сложность реализации вложенной иерархии на аппаратном уровне [1, 2].

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

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

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

Ни экономика, ни социальные коммуникации уже невозможны без использования развитых ИТ. Вот и рассмотрим, почему используемые сейчас технологии далее непригодны и на что их следует заменить. Автор будет признателен за конструктивное квалифицированное обсуждение и надеется узнать полезную информацию о современных решениях затронутых «проблем».

^{Theory is when you know everything but nothing works.
Practice is when everything works but no one knows why.
In distributed systems, theory and practice are combined:
nothing works and no one knows why.}

Чтобы доказать, что шутка в эпиграфе — абсолютная глупость, мы уже в третий раз проводим SPTDC (school on practice and theory of distributed computing). Об истории школы, её сооснователях Петре Кузнецове и Виталии Аксёнове, а также об участии JUG Ru Group в организации SPTDC мы уже рассказывали на Хабре. Поэтому сегодня — о школе в 2020 году, о лекциях и лекторах, а также об отличиях школы от конференции.

Школа SPTDC пройдёт с 6 по 9 июля 2020 года онлайн.

Все лекции будут на английском языке. Основные темы лекций: persistent concurrent computing, cryptographic tools for distributed systems, formal methods for verifying consensus protocols, consistency in large-scale systems, distributed machine learning.


Сразу догадались, в каком воинском звании персонажи на картинке? Я вас обожаю.

Здравствуйте, коллеги.

В рамках проработки темы С++20 нам в свое время попалась уже довольно старенькая (сентябрь 2018) статья из хаброблога «Яндекса», которая называется "Готовимся к С++20. Coroutines TS на реальном примере". Заканчивается она следующей весьма выразительной голосовалкой:



«Почему бы и нет», — решили мы и перевели статью Давида Пиларски (Dawid Pilarski) под названием «Coroutines introduction». Статья вышла чуть более года назад, но, надеемся, все равно покажется вам очень интересной.

18 апреля 2020 в Санкт-Петербурге и 16 мая в Москве пройдёт седьмая мини-конференция по платформе .NET CLRium #7. В этот раз мы будем и говорить и заниматься практикой многопоточного кода. Как и в прошлый раз, все доклады будут придерживаться единой линии повествования. В шестом CLRium мы поднаторели в теории и узнали много нового относительно планировщика потоков, блокировок и неблокирующих алгоритмов. В платформе .NET изучили контексты синхронизации, планировщики задач, как работают сами задачи, async/await и типичные ошибки при его использовании… Мы изучили вообще всё, чтобы уверенно начать заниматься практическими задачами.

В CLRium #7 мы перейдём к практике. Наша программа, наконец, окончательно готова: мы разработали матрицу докладов, которые построены так, что последующие доклады логически вытекают из предыдущих. А кроме самих докладов по желанию будет дана практическая работа на дом, в рамках которой вы приобретете опыт работы над задачами совместно: группами по несколько человек (контролируемых координатором).

В прошлом году в Санкт-Петербурге прошла первая конференция Hydra, посвящённая параллельным и распределённым системам. С докладами выступали лауреаты премии Дейкстры и премии Тьюринга (Лесли Лэмпорт, Морис Херлихи и Майкл Скотт), создатели компиляторов и языков программирования (C++, Go, Java, Kotlin), разработчики распределённых баз данных (Cassandra, CosmosDB, Yandex Database), а также создатели и исследователи алгоритмов и структур данных (CRDT, Paxos, wait-free data structures). В общем, на этом месте уже можно брать отпуск, сворачивать окно IDE, открывать плейлист на YouTube с лучшими докладами Hydra 2019 — и пусть task scheduler немного подождёт.

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

На новой Гидре — более замысловатая программа, новые спикеры вместе с героями прошлого года, а также уже знакомое ощущение распределённого между участниками восторга от параллельного хардкора в трёх залах.