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

Оригинальный pdf (на английском)
Переведённый pdf (на русском)

Обычно в таких статьях делают заголовок вида «аналог await/async для C++», а их содержимое сводится к описанию ещё одной библиотеки, выложенной где-то в интернете. Но в данном случае нам не требуется ничего подобного и заголовок точно отражает суть статьи. Почему так смотрите ниже.

Постановка задачи

Один из алгоритмов, который я реализовывал, имел интересные особенности при работе с памятью:

• Могло выделяться огромное количество, до десятков и сотен миллионов небольших объектов одного типа.
• Объекты представляли собой POD- типы.
  
  POD

  A Plain Old Data Structure in C++ is an aggregate class that contains only PODS as members, has no user-defined destructor, no user-defined copy assignment operator, and no nonstatic members of pointer-to-member type.
• Заранее было неизвестно какое количество объектов понадобится, могло так случится, что потребуется сотня, а может и сто миллионов.
• Объекты никогда не удаляются по одному, в какой-то момент они становятся не нужны все сразу.
• Алгоритм хорошо распараллеливается, по этому выделением объектов занимается одновременно несколько потоков, по количеству ядер процессора(ов).

Использование в таких условиях стандартного new – delete приводит к очень большим потерям времени на удаление объектов. Если без отладчика удаление происходило хотя бы за несколько секунд, то в присутствии отладчика освобождение памяти замедляется примерно в 100(!) раз, и отладка проекта становится просто невозможной. Кроме того из-за большого количества выделенных объектов достаточно ощутимым становился перерасход памяти на внутренние данные распределителя памяти.
Для решения задачи выделения огромного количества объектов одного типа, и их пакетного удаления, был сделан lock-free контейнер MassAllocator. Код компилируется Visual Studio 2012. Полный код проекта выложен на github.

Каждый день тысячи спутников, самолетов, камер наблюдения делают миллионы снимков высокого разрешения. Чтобы добыть оттуда полезную информацию, их надо обработать – и эта задача даже на первый взгляд не кажется легкой. Именно благодаря своей сложности (а также большому простору для распараллеливания) она и стала содержанием летнего тура конкурса Intel «Accelerate Your Code», который проходит с 1 мая по 31 августа. В этот раз в условиях конкурса произошли некоторые изменения, а вот главный приз остался прежним – победитель получит ультрабук стоимостью 1000 евро.

В рамках своей научной активности реализовал так называемый Федеративный Фильтр Калмана (Federated Kalman Filter). В этой статье рассказывается о том, что такое «Федеративный ФК», чем он отличается от обобщенного, а также описывается консольное приложение, реализующее данный фильтр и генетические алгоритмы для подбора параметров его математической модели. Приложение было реализовано с использованием TPL (Task Parallel Library), поэтому пост будет интересен не только специалистам по цифровой обработке сигналов.

UPD1: после прочтения двух недавних статей решил тоже присоединиться к эксперименту/исследованию/авантюре (называйте как хотите). В конце статьи добавил еще один опрос — "Стали бы Вы поощрать рублем такие узко специализированные статьи на Хабрахабре?".

Продолжаю вести блог о разработке игрушечной ОС.

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

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

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

Здравствуйте, уважаемые Хабраюзеры!

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

Если вы помните, в октябре был пост о сборе средств на Kickstarter для проекта Parallella — нового типа многоядерного процессора с высоким соотношением производительности к потреблению энергии. Компания удалась и принесла 900 тысяч долларов. Первые платы будут отправлены бэкерам в мае.

Разработчики завершают дизайн и разводку платы в ближайшие недели.

В этой статье я расскажу о том, как загруженность шины данных влияет на масштабируемость (scalability) приложений. Под масштабируемостью мы будем понимать не только способность многопоточного приложения сокращать свое время выполнения по мере увеличения числа потоков. Мы также добавим сюда и способность однопоточного приложения, запущенного одновременно в несколько копий (instances), выполняться за тот же самый промежуток времени, что и одна копия. Хотя последний пример было бы правильнее охарактеризовать таким свойством как пропускная способность (throughput), так как он относится к «серверному» режиму запуска приложений. Т.е. это такой режим, при котором на сервере запускается однопоточное приложение, каждый раз когда к нему подключается новый клиент. Главная задача при разработке таких приложений — это снижение их зависимости от общих ресурсов, одним из которых может являться шина данных.

Я поделюсь 30 практиками для достижения максимальной производительности приложений, которые этого требуют. Затем, я расскажу, как применил их для коммерческого продукта и добился небывалых результатов!
Приложение было написано на C# для платформы Windows, работающее с Microsoft SQL Server. Никаких профайлеров – содержание основывается на понимании работы различных технологий, поэтому многие топики пригодятся для других платформ и языков программирования.

Здравствуйте! В этой статье я вкратце расскажу вам о процессах, потоках, и об основах многопоточного программирования на языке Java.
Наиболее очевидная область применения многопоточности – это программирование интерфейсов. Многопоточность незаменима тогда, когда необходимо, чтобы графический интерфейс продолжал отзываться на действия пользователя во время выполнения некоторой обработки информации. Например, поток, отвечающий за интерфейс, может ждать завершения другого потока, загружающего файл из интернета, и в это время выводить некоторую анимацию или обновлять прогресс-бар. Кроме того он может остановить поток загружающий файл, если была нажата кнопка «отмена».

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

Давайте начнем. Сначала о процессах.

Если ты ИТшник, то нельзя просто так взять и выйти на работу 2-го января: пересмотреть 3-ий сезон битвы экстрасенсов или запись программы «Гордон» на НТВ (дело умственных способностей вкуса).
Нельзя потому, что у других сотрудников обязательно будут для тебя подарки: у секретарши закончился кофе, у МП — закончились дедлайны, а у администратора баз данных — амнезия память.
Оказалось, что инженеры из команды Hadoop тоже любят побаловать друг друга новогодними сюрпризами.

2008

2 января. Упуская подробное описание эмоционально-психологического состояния лиц, участвующих в описанных ниже событиях, сразу перейду к факту: поставлен таск MAPREDUCE-279 «Map-Reduce 2.0». Оставив шутки про число, обращу внимание, что до 1-ой стабильной версии Hadoop остается чуть менее 4 лет.

За это время проект Hadoop пройдет эволюцию из маленького инновационного снежка, запущенного в 2005, в большой снежный com ком, надвигающийся на ИТ, в 2012.
Ниже мы предпримем попытку разобраться, какое же значение январский таск MAPREDUCE-279 играл (и, уверен, еще сыграет в 2013) в эволюции платформы Hadoop.

Есть приложения, которые хорошо реализуются как системы передачи сообщений. Сообщениями в широком смысле может быть что угодно – блоки данных, управляющие «сигналы» и т.д. Логика же состоит из узлов, обрабатывающих сообщения, и связей между ними. Такая структура естественно представляется графом, по рёбрам которого «текут» сообщения, обрабатываемые в узлах. Наиболее устоявшееся название такой модели – вычислительный граф.

С помощью вычислительного графа можно установить зависимости между задачами и в какой-то мере программно реализовать «dataflow архитектуру».

В этом посте я опишу, как реализовать такую модель на С++, используя библиотеку Intel Threading Building Blocks (Intel TBB), а именно класс tbb::flow::graph.

Использование возможностей параллелизма в настоящее время стало уже обычной практикой в программировании. Однако все языки можно разделить на два типа: те, в которых параллельность применяется вовсю и активно (например, С), и те, которые не вкусили еще в полной мере радостей многопоточности. К последним, в частности, относится JavaScript. Чтобы восполнить этот досадный пробел и пополнить копилку прогрессивного опыта, предлагаем вашему вниманию перевод сообщения из блога Ника Матсакиса, программиста Mozilla Foundation, в котором он делится первыми личными впечатлениями от использования Rivertrail — инструмента параллелизации в JavaScript, созданным Intel.

Джефф Прешинг (Jeff Preshing) опубликовал отличную демонстрацию, как нормальный код C++ возвращает непредсказуемый результат на многоядерных процессорах со слабо упорядоченной обработкой очереди запросов (Weakly-Ordered CPU), то есть на ARM-процессорах. Например, на iPhone или каком-нибудь современном Android-устройстве.

Простая программа C++ с двумя потоками 20.000.000 раз прибавляет единичку к значению, защищённому мьютексом, — и каждый раз на выходе получается разный результат, который меньше 20.000.000!



Как говорится, наш враг — CPU.

За последнюю неделю Хабр пополнился сразу несколькими статьями об игре «Жизнь». Что ж, тогда и я поделюсь своими наработками по этой теме.

Предисловие

Минувшим летом мне довелось побывать на летней школе по параллельному программированию, проводимой НГУ. В рамках школы каждый студент должен был подготовить какой-либо проект по одной из тематик, озвученных на лекциях. Меня заинтересовали клеточные автоматы. У меня первая ассоциация при фразе «клеточный автомат» это именно «Жизнь».
Я понимал, что никому не будет интересно наблюдать за черными клеточками, живущими на экране. Да и слишком просто это для такого проекта. Нужно было придумать что-то принципиально новое. Я решил расширить диапазон своих мыслей и выйти за пределы двухмерного пространства. В прямом смысле. Я подумал, а почему бы не сделать эту игру трехмерной? Ведь это гораздо интереснее!

Компания Adapteva (про которую вы скорее всего слышите в первый раз) планирует сделать суперкомпьютер который будет доступен каждому. С 2008 года они занимаются разработками энергоэффективных RISC-процессоров по заказам производителей смартфонов и других мобильных устройств.

«Мы идем вниз по пищевой цепочке», говорит CEO и основатель Andreas Olofsson. Но Adapteva хочет дать свои технологии напрямую людям через проект на Кикстартере, если они соберут как минимум $750K с конечной целью в $3M.

В этой серии постов мы попробуем решить одну простую задачу с помощью более-менее актуальных технологий параллельного программирования (Нативные потоки, OpenMP, TBB, MPI, CUDA, OpenCL, OpenACC, Chapel может быть еще что-нить экзотическое. Как бы сравнительно и в hands-on ключе.