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

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

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

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

1. Введение

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

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

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

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

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

^{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 июля, потому что спикеры успевают исследовать и преподавать, например, в университетах Кембриджа, Рочестера и Санкт-Петербурга, и другое время года не для них.

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

Ниже представлена не простая расшифровка доклада с семинара CLRium, а переработанная версия для книги .NET Platform Architecture. Той её части, что относится к потокам.

Потоки и планирование потоков

Что такое поток? Давайте дадим краткое определение. По своей сути поток это:

• Средство параллельного относительно других потоков исполнения кода;
• Имеющего общий доступ ко всем ресурсам процесса.

Очень часто часто слышишь такое мнение, что потоки в .NET — они какие-то абсолютно свои. И наши .NET потоки являются чем-то более облегчённым чем есть в Windows. Но на самом деле потоки в .NET являются самыми обычными потоками Windows (хоть Windows thread id и скрыто так, что сложно достать). И если Вас удивляет, почему я буду рассказывать не-.NET вещи в хабе .NET, скажу вам так: если нет понимания этого уровня, можно забыть о хорошем понимании того, как и почему именно так работает код. Почему мы должны ставить volatile, использовать Interlocked и SpinWait. Дальше обычного lock дело не уйдёт. И очень даже зря.

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

Задача процессора — просто исполнять код. Поэтому с точки зрения процессора есть только один поток: последовательное исполнение команд. А задача операционной системы каким-либо образом менять поток т.о. чтобы эмулировать несколько потоков.

Прим. перев.: Содержимое этой статьи не совсем типично для нашего блога. Однако, как многим известно, etcd находится в самом сердце Kubernetes, из-за чего данное исследование, проведённое независимым консультантом в области надёжности, оказалось интересным и в среде инженеров, эксплуатирующих данную систему. Кроме того, оно интересно в разрезе того, как Open Source-проекты, уже зарекомендовавшие себя в production, совершенствуются даже на таком, весьма «низком», уровне.



Хранилище пар «ключ-значение» (KV) etcd представляет собой распределённую базу данных, основанную на алгоритме консенсуса Raft. В ходе анализа, проведенного в 2014 году, мы обнаружили, что etcd 0.4.1 по умолчанию была подвержена так называемым stale reads (операциям чтения, возвращающим старое, неактуальное значение из-за запаздывания синхронизации — прим. перев.). Мы решили вернуться к etcd (в этот раз — к версии 3.4.3), чтобы снова детально оценить ее потенциал в области надежности и безопасности.

В мире JVM про корутины знают в большей степени благодаря языку Kotlin и Project Loom. Хорошего описания принципа работы котлиновских корутин я не видел, а код библиотеки kotlin-coroutines совершенно не понятен неподготовленному человеку. По моему опыту, большинство людей знает о корутинах только то, что это "облегченные потоки", и что в котлине они работают через умную генерацию байткода. Таким был и я до недавнего времени. И мне пришла в голову идея, что раз корутины могут быть реализованы в байткоде, то почему бы не реализовать их в java. Из этой идеи, впоследствии, появилась небольшая и достаточно простая библиотека, в устройстве которой, я надеюсь, может разобраться практически любой разработчик. Подробности под катом.

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


— Меня зовут Сева Миньков. Я работаю в отделе облачной инфраструктуры поискового департамента. Занимаюсь в основном бэкендом. Пишу на разных языках, но чаще всего это Java и языки, запускаемые на Java Virtual Machine (JVM).

"Цветорасширитель для ZX-Spectrum" — так называлась статья, опубликованная в эхе fido7.zx.spectrum 3 августа 1997 года. Статья описывала идею решения одной из главных проблем платформы ZX-Spectrum — конфликта атрибутов (attribute clash). Публикация вызвала в то время определенный интерес, про технические детали и историю вопроса я и хотел бы рассказать.

Не буду залезать глубоко в технические подробности и просто структурно опишу идею и решение.

Совсем скоро, 29-30 ноября в Санкт-Петербурге и 06-07 декабря — в Москве мы запустим шестой семинар по .NET. На этот раз — по теме многопоточки и конкурентности. Мы уже писали об этом пару раз на Хабре, но сегодня есть отдельный повод для этого: на семинаре настоящий эксклюзив. Будет описана работа гибридного примитива синхронизации: Monitor. Да, всем привычная вещица достойна отдельного доклада. Ведь он в своей работе учитывает и частоту процессора и количество ядер, учитывает lock convoy/starvation и вообще, очень сложен.

А в конце статьи развлечения ради предложу пройти парочку QUIZов по многопоточке.

Qt — чрезвычайно мощный и удобный фреймворк для C++. Но у этого удобства есть и обратная сторона: довольно много вещей в Qt происходят скрыто от пользователя. В большинстве случаев соответствующая функциональность в Qt «магически» работает и это приучает пользователя просто принимать эту магию как данность. Однако когда магия все же ломается то распознать и решить неожиданно возникшую на ровном казалось бы месте проблему оказывается чрезвычайно сложно.

Эта статья — попытка систематизации того как в Qt «под капотом» реализована работа с потоками и о некотором количестве неочевидных подводных камней связанных с ограничениями этой модели.

Основы
Thread affinity, инициализация и их ограничения
Главный поток, QCoreApplication и GUI
Rendering thread
Заключение

Доброго времени суток. В этот раз поговорим на тему, в которой начинал разбираться каждый уважающий себя адепт языка C# — асинхронное программирование с использованием Task или, в простонародье, async/await. Microsoft проделали хорошую работу — ведь для того, чтобы использовать асинхронность в большинстве случаев нужно лишь знание синтаксиса и никаких других подробностей. Но если лезть вглубь, тема довольно объемная и сложная. Ее излагали многие, каждый в своем стиле. Есть очень много классных статей по этой теме, но все равно существует масса заблуждений вокруг нее. Постараемся исправить положение и разжевать материал настолько, насколько это возможно, не жертвуя ни глубиной, ни пониманием.

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

Мы берём Go, начинаем писать конкурентный код. Конечно, ожидаем, что легко сможем обуздать мощь каждого ядра нашего процессора. Так ли это?

Меня зовут Артемий. Этот пост — вольная расшифровка моего доклада с GopherCon Russia. Он появился как попытка дать толчок людям, которые хотят разобраться, как писать хороший, конкурентный код.

Видео с конференции GopherCon Russia

Введение

Несколько лет назад, мы решили, что настало время поддержать SIMD код в .NET. Мы представили пространство имен System.Numerics с типами Vector2, Vector3,Vector4 и Vector<T>. Эти типы представляют API общего назначения для создания, доступа и оперирования векторными инструкциями, когда это возможно. Они, так же, обеспечивают программную совместимость для тех случаев, где аппаратное обеспечение не поддерживает подходящих инструкций. Это позволило, с минимальным рефакторингом, векторизовать ряд алгоритмов. Как бы там ни было, общность такого подхода делает его сложным в применении с целью получения полного преимущество от всех доступных, на современном аппаратном обеспечении, векторных инструкций. В дополнении, современное аппаратное обеспечение предоставляет ряд специализированных, не векторных, инструкций, которые могут значительно улучшать производительность. В этой статье я расскажу, как мы обошли эти ограничения в .NET Core 3.0.

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

День Программиста традиционно отмечается в 256-й день года. Число 256 выбрано потому, что это количество чисел, которые можно выразить с помощью одного байта (от 0 до 255).

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

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

Совсем скоро, 29-30 ноября в Санкт-Петербурге и 06-07 декабря — в Москве мы запустим шестой семинар по .NET. На этот раз — по теме многопоточки и конкурентности. Мы уже писали об этом пару раз на Хабре, но сегодня — День Программиста и есть отличный повод дать вам всем комплимент: скидку на его посещение.

У меня для вас есть новость: мы с Андреем Гончаровым, моим хорошим другом и соратником решили сделать для вас доклады по lock-free, выступая вместе. Мне показалось, это должно сильно оживить атмосферу выступления. Андрей сейчас закапывается в эту тему так, что иногда его приходится даже останавливать: доклады будут очень интересными и полезными.

Юрий Власов, мой второй коллега нашёл библиотеку Microsoft.VisualStudio.Threading, которую с удовольствием использует в проектах. Он решил поведать вам о её богатых возможностях и применимости в различных задачах. Этот доклад отлично завершит тему lock-free, закрыв вопросы теории, оценки сложностей, анализа существующих алгоритмов и построения собственных вопросом хорошей реализации в виде промышленной библиотеки.

В честь Дня Программиста мы ввели промокод: CLRiumDevDay. Он действует всего-лишь два дня, когда можно забронировать билеты. Далее — вы имеете 5 дней на оплату билетов.
Первый день — скидка = 25%, второй = 15%

Сколько процессорных ядер Intel в вашем компьютере? Если вы пользуетесь системой на базе Intel, то в абсолютном большинстве случаев к вашему ответу надо будет прибавить единицу. В состав почти всех процессоров Intel — от Atom и до Xeon E3, естественно, не пропуская Core, уже много лет входит интегрированное графическое ядро Intel Graphics, являющееся по сути полноценным процессором, и соответственно, способное не только показывать на экране картинки и ускорять видео, но и выполнять «обычные» вычисления общего назначения. Как это можно эффективно использовать? Смотрите под катом.