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

Пять из четырех разработчиков признают, что многопоточное программирование понять непросто.

Большую часть времени, что я провел в Ruby-сообществе, печально известная GIL оставалась для меня темной лошадкой. В этой статье я расскажу о том, как наконец познакомился с GIL поближе.

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

Я хотел знать, как работает GIL с технической точки зрения. На GIL нет ни спецификации, ни документации. По сути, это особенность MRI (Matz's Ruby Implementation). Команда разработчиков MRI ничего не говорит по поводу того, как GIL работает и что гарантирует.

Впрочем, я забегаю вперед.

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

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

Было:

class Service {
  public void longJob(Object arg) {...}
}
...
Service s=new Service();
...

s.longJob(arg);

Стало:

class Service {
  public void longJob(Object arg) {...}
}
class ServiceWrapper extends Service {
...
}
...
Service s=new ServiceWrapper() ;
...

s.longJob(arg);

JRE позволяет абстрагироваться от конкретной платформы, делая написание кросс-платформенного кода намного проще. Конечно до идеала Write once, run anywhere не дотягивает, но жизнь облегчает существенно.

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

Подавляющее большинство современных процессоров имеют кэш-память для хранения часто используемых данных. Кэш-память делится на блоки (Сache line). Механизмы реализующие Cache coherence обеспечивают синхронизацию кэш-памяти между ядрами процессора(ов) в компьютерной системе.

Термин false sharing означает доступ к разным объектам в программе, разделяющим один и тот же блок кэш-памяти. False sharing в многопотоковом приложении, когда в одном блоке оказываются переменные модифицируемые из разных потоков, ведет к снижению производительности и увеличению нагрузки на Cache coherence механизмы. Подробно о том как это происходит, можно прочесть в статье на эту тему.

Во второй части статьи рассказывалось о механизмах обнаружения ошибок в процессе обработки.

Обработка завершилась с ошибкой, что делать дальше? Вполне возможно, что потеряна связь с одним из узлов кластера или временно недоступна база данных. В этом случае, нельзя с уверенностью сказать, какие операции выполнились успешно, а какие — нет. Если все операции в цепочке повторно применимы (идемпотентны), например установка флага, то можно просто перезапустить обработку. Если нет, то на помощь приходят механизмы транзакций Storm.

В первой части рассматривались базовые понятия Storm.

Разные классы задач предъявляют различные требования к надежности. Одно дело пропустить пару записей при подсчете статистики посещений, где счет идет на сотни тысяч и особая точность не нужна. И совсем другое — потерять, например, информацию о платеже клиента.

Далее рассмотрим о механизмы защиты от потери данных, которые реализованы в Storm.

ИМХО (Имею Мнение Хрен Оспоришь)

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

В 2011 году Twitter открыл, под лицензией Eclipse Public License, проект распределенных вычислений Storm. Storm был создан в компании BackType и перешел к Twitter после покупки.

Storm это система ориентированная на распределенную обработку больших потоков данных, аналогичная Apache Hadoop, но в реальном времени.

Ключевые особенности Storm:

• Масштабируемость. Задачи обработки распределяются по узлам кластера и потокам на каждом узле.
• Гарантированная защита от потери данных.
• Простота развертывания и спровождения.
• Восстановление после сбоев. Если какой либо из обработчиков отказывает, задачи переадресуются на другие обработчики.
• Возможность написания компонентов не только на Java. Простой Multilang protocol с использованием JSON объектов. Есть готовые адаптеры для языков Python, Ruby и Fancy.

В первой части рассматриваются базовые понятия и основы создания приложения c использованием Storm версии 0.8.2.

Обычно в таких статьях делают заголовок вида «аналог 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.

Представьте себе фреймворк общего назначения для распределенного исполнения приложений со следующими статистическими показателями*:


* Статистические данные за 2011 год.

А теперь представьте, что это не Hadoop.

О том, что это за фреймворк, о идеях и концепциях, заложенных в его основу и о том, почему этот фреймворк даже более инновационный (субъективно), чем Hadoop, речь пойдет ниже.

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

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

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

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

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

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

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

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

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

Эта статья описывает, как построить простое приложение для магазина Windows используя Intel Threading Building Blocks (Intel TBB).

Мой предыдущий пост Windows 8: Написание многопоточных приложений для магазина Windows с помощью Intel Threading Building Blocks описывает экспериментальную поддержку для приложений для магазина Windows. Обновление 3 для Intel TBB 4.1, так же как стабильный релиз tbb41_20130314oss содержит динамические библиотеки для таких приложений.

Недавно в нашем блоге появилась статья о NUMA-системах, и я хотел бы продолжить тему, поделившись своим опытом работы в Linux. Сегодня я расскажу о том, что бывает, если неправильно использовать память в NUMA и как диагностировать такую проблему с помощью счётчиков производительности.

Зондирование обстановки на Реддите показало, что едва ли хоть кто-то всерьез занимается обработкой изображений на Хаскеле, несмотря на то, что достаточно популярная библиотека Repa предполагает работу с изображениями как одно из основных приложений. Надеюсь, ситуацию сможет изменить библиотека Yarr (документация, гитхаб).

Я называю библиотеку dataflow-фреймворком, потому что она обобщена для обработки массивов (от одномерных до трехмерных) элементов любых типов, в том числе векторов чисел, например координат, комплексных чисел. Но основное предполагаемое применение — обработка двумерных массивов из векторов цветовых компонент, т. е. изображений. Фреймворк непосредственно не содержит алгоритмов обработки изображений, а предоставляет мощную инфраструктуру для их написания.

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

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

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