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

Вашему вниманию простой C++ template аллокатора с потокобезопасным циклическим буфером.

Вся реализация в одном заголовочном .h файле: [fast_mem_pool.h]

Фишки, чем этот аллокатор лучше сотни подобных — под катом.

1. Введение

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

Мы — программисты. Может, в разной степени, но некоторые — уж точно. Это я к тому, что мы разные и мыслить можем тоже по-разному. Утверждение, что программист мыслит только последовательно, столь же однобоко, вредно и даже кощунственно, как и то, что человек только бегает. Он иногда — и летает. Кто-то, как летчики, делает это довольно регулярно, а некоторые, как космонавты, даже месяцами и непрерывно. Идея последовательного мышления принижает способности человека. В какой-то момент и на какое-то время в это можно даже поверить, но " все-таки она вертится" — это про то, что рано или поздно жизнь возьмет свое.

Вы хотите узнать, как получить работу по проектированию электроники космического корабля? Мне надавно пришло предложение поинтервьироваться на позицию FPGA designer для Blue Origin (см. выше). Лично мне такая позиция не нужна (у меня уже есть позиция ASIC designer-а в другой компании), но я отметил, что технические требования к претендентам в Blue Origin точно совпадают с содержанием семинара для школьников и младших студентов, который пройдет 15-17 сентября на выставке ChipEXPO в Сколково, с поддержкой от РОСНАНО. Хотя разумеется на семинаре мы коснемся технологий Verilog и FPGA только на самом начальном уровне: базовые концепции и простые, но уже интересные, примеры. Чтобы устроится после этого в Blue Origin, вам все-же потребуется несколько лет учебы и работы.

Из-за короновируса семинар будет удаленный, поэтому принять участие смогут не только школьники и студенты Москвы, но и всей России, Украины, Казахстана, Калифорнии и других стран и регионов. Физически проводить лекции и удаленно помогать участникам будут преподаватели и инженеры МИЭТ, ВШЭ МИЭМ, МФТИ, Черниговского Политеха, Самарского университета, IVA Technologies и fpga-systems.ru.

Для участия сначала, еще до семинара, нужно пройти три части теоретического курса от РОСНАНО, под общим названием «Как работают создатели умных наночипов»: «От транзистора до микросхемы», «Логическая сторона цифровой схемотехники», «Физическая сторона цифровой схемотехники». Этот курс необходим, чтобы вы понимали, что вы делаете, по время практического семинара. По получению сертификата окончания теоретического онлайн-курса, вы можете зайти в офис РОСНАНО в Москве и получить бесплатную плату для практического семинара (если они останутся, преимущество имеют школьники). С этой платой вы можете работать дома, до, во время и после семинара в Сколково.

Как получить плату, подготовится к семинару и что на нем будет:

1. Введение

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

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

Спасибо вам за внимание, проявленное к нашей предыдущей переводной публикации о REST. Сегодня мы предлагаем взглянуть на тему проектирования систем несколько с другой стороны и публикуем перевод статьи Стивена Бреннана, корифея Linux, который рассказывает о собственной реализации многозадачности в userspace и о том, какая может быть от этого польза.

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

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

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