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

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

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

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

Приложение взято из примеров библиотеки Intel Threading Building Blocks (Intel TBB). Оно рисует фрактал Мандельброта и распараллелено по потокам с помощью Intel TBB. Т.е. преимущества многоядерного процессора оно использует — посмотрим, как обстоят дела с векторными инструкциями.

Многие из вас уже попробовали на вкус Stream API — потоки Java 8. Наверняка у некоторых возникло желание не только пользоваться готовыми потоками от коллекций, массивов, случайных чисел, но и создать какой-то принципиально новый поток. Для этого вам потребуется написать свой сплитератор. Spliterator — это начинка потока, публичная часть его внутренней логики. В этой статье я расскажу, как и зачем я писал сплитератор.

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

Меня зовут Дмитрий Сподарец. Сегодня я начинаю серию статей о сервисе FlyElephant, основателем которого являюсь. С чего все начиналось, функционал и нынешнее состояние проекта, программа бета-тестирования и наша конференция AI&BigData Lab, а также о многом другом Вы узнаете из ближайших публикаций.



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

В результате длительного использования даже самых хороших программных продуктов постепенно выявляются те или иные их недостатки. Не стала исключением, и библиотека Intel Performance Primitives (IPP). К моменту выхода версии 8.0 выяснились некоторые проблемы, часть из которых относится к функциям обработки двумерных изображений.
Для их решения в IPP 8.0 многие функции обработки изображений приведены к общему шаблону, позволяющему обрабатывать изображения по блокам ( tiles), и, следовательно, эффективно распараллеливать на уровне приложения код, содержащий вызовы IPP функций. Новый API соответствующих IPP функций поддерживает бордюры нескольких типов, не использует внутреннее выделение динамической памяти, позволяет делить изображения на фрагменты произвольного размера и обрабатывать эти фрагменты независимо; упрощает использование и повышает производительность ряда функций. В данной статье подробно рассмотрен новый API и приведены примеры использования.

Rust начинался как проект, решающий две трудные проблемы:

• Как обеспечить безопасность (работы с памятью) в системном программировании?
• Как сделать многопоточное программирование безболезненным?

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

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

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

С точки зрения многопоточности это означает, что вы можете пользоваться различными парадигмами (передача сообщений, разделяемое состояние, lock-free-структуры данных, чистое функциональное программирование), и Rust позволит избежать наиболее распространённых подводных камней.

Вот какие особенности у многопоточного программирования в Rust:

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

На днях появилась статья 5nw Два способа быстрого вычисления факториала, в которой приводится идея ускорения подсчёта факториала с помощью группировки перемножаемых чисел в дерево по принципу «разделяй и властвуй». Взглянув на это, я сразу понял, что тут параллельные потоки Java проявят себя во всей красе: ведь они делят задачу на подзадачи с помощью сплитераторов именно таким образом. Получается, что быстрая реализация будет ещё и красивой:

public static BigInteger streamedParallel(int n) {
    if(n < 2) return BigInteger.valueOf(1);
    return IntStream.rangeClosed(2, n).parallel().mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get();
}

Содержание

Часть 1: Введение.
Часть 2: Аппаратное обеспечение GPU и шаблоны параллельной коммуникации.
Часть 3: Фундаментальные алгоритмы GPU: свертка (reduce), сканирование (scan) и гистограмма (histogram).
Часть 4: Фундаментальные алгоритмы GPU: уплотнение (compact), сегментированное сканирование (segmented scan), сортировка. Практическое применение некоторых алгоритмов.
Часть 5: Оптимизация GPU программ.
Часть 6: Примеры параллелизации последовательных алгоритмов.
Часть 7: Дополнительные темы параллельного программирования, динамический параллелизм.

Большое обновление пакета Intel® Parallel Studio XE вышло на этой неделе. Версия 2016 включает три совершенно новых продукта:

1. Intel® Data Analytics Acceleration Library (Intel® DAAL) – C++ и Java решение для аналитики данных (статистика, машинное обучение и другое).
2. Новый Vectorization Advisor в составе Intel® Advisor XE 2016 Beta для оптимизации кода под SIMD инструкции, т.е. векторизации.
3. MPI Performance Snapshot для быстрой общей оценки производительности MPI программ.

Бета-версия доступна публично и бесплатно, программа длится до 23 июня, но лицензии будут работать вплоть до 25 сентября 2015 г. Для получения Бета-версии нужно зарегистрироваться здесь.
Эта статья посвящена обзору нового функционала, более детально отдельные продукты постараемся осветить в последующих блогах – пишите в комментариях, к чему есть интерес.

В комментариях к прошлому посту был поднят весьма важный вопрос – а будет ли вообще выигрыш в производительности от выгрузки вычислений на интегрированную графику, по сравнению с выполнением только на CPU? Конечно, он будет, но нужно соблюдать определенные правила программирования для эффективных вычислений на GFX+CPU.
В подтверждение моих слов, сразу представлю график ускорения, получаемого при выполнении вычислений на интегрированной графике, для различных алгоритмов и с разной долей вовлеченности CPU. На КДПВ мы видим, что выигрыш более чем весомый.

Это последняя, на сегодняшний день, статья из цикла про внутреннее устройство конкурентных ассоциативных контейнеров. В предыдущих статьях рассматривались hash map, был построен алгоритм lock-free ordered list и контейнеры на его основе. За бортом остался один важный тип структур данных — деревья. Пришло время немного рассказать и о них.

Исследования, посвященные алгоритмам конкурентных деревьев, не требующих внешней синхронизации доступа к ним, начались довольно давно — в 70-х годах прошлого века, — и были инициированы развитием СУБД, поэтому касались в основном оптимизации страничных деревьев (B-tree и его модификации).

Развитие lock-free подхода в начале 2000-х не прошло мимо алгоритмов деревьев, но лишь недавно, в 2010-х годах, появилось множество действительно интересных работ по конкурентным деревьям. Алгоритмы деревьев довольно сложны, поэтому исследователям потребовалось время — порядка 10 лет — на их lock-free/non-blocking адаптацию. В данной статье мы рассмотрим самый простой случай — обычное бинарное дерево, даже не самобалансирующееся.

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

Мы приведем краткое описание того, как организован обмен данными в параллельных приложениях на основе MPI, а также ссылки на внешние источники с более подробным описанием. В практической части вы найдете описание всех этапов разработки демонстрационного MPI-приложения «Hello World», начиная с настройки необходимого окружения и заканчивая запуском самой программы.

В предыдущих статьях (раз, два) мы рассматривали классический hash map с хеш-таблицей и списком коллизий. Был построен lock-free ordered list, который послужил нам основой для lock-free hash map.
К сожалению, списки характеризуются линейной сложностью поиска O(N), где N — число элементов в списке, так что наш алгоритм lock-free ordered list сам по себе представляет небольшой интерес при больших N.
Или все же представляет?..

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

Пройдем по следам C++ 2015 Russia далее.
В предыдущей статье мы рассмотрели алгоритм для lock-free ordered list и на его основе сделали простейший lock-free hash map. У этого hash map есть недостаток: размер хеш-таблицы постоянен и не может быть изменен в процессе роста числа элементов в контейнере. Это не представляет проблемы, если мы заранее примерно представляем требуемый объем контейнера. А если нет?

Мне оказали честь — пригласили выступить на первой конференции C++ 2015 Russia 27-28 февраля. Я был насколько наглым, что запросил 2 часа на выступление вместо положенного одного и заявил тему, наиболее меня интересующую — конкурентные ассоциативные контейнеры. Это hash set/map и деревья. Организатор sermp пошел навстречу, за что ему большое спасибо.
Как подготовиться ко столь ответственному испытанию выступлению? Первое — нарисовать презентацию, то есть кучу картинок, желательно близко к теме. Но надо ещё и два часа озвучивать картинки, — как все это запомнить? Как избежать глубокомысленных «ээээмммм», «здесь мы видим», «на этом слайде показано», несвязных прыжков повествования и прочих вещей, характеризующих выступающего c не очень хорошей стороны в части владения родным языком (это я про русский, с C++ я разобрался быстро — никакого кода в презентации, только картинки)?
Конечно, надо записать свои мысли, глядя на слайды. А если что-то написано, то не худо бы и опубликовать. А если публиковать, — то на хабре.
Итак, по следам C++ 2015 Russia! Авторское изложение, надеюсь, без авторского косноязычия, без купюр и с отступлениями по теме, написанное до наступления события, в нескольких частях.

Продолжаем начатый разговор о Intel® Graphics Technology, а именно о том, что у нас есть в распоряжении с точки зрения написания кода: прагмы offload и offload_attribute для оффлоадинга, атрибуты target(gfx) и target(gfx_kernel), макросы __GFX__ и __INTEL_OFFLOAD, интринсики и набор API функций для асинхронного оффлоада. Это всё, что нужно нам для счастья. Чуть было не забыл: конечно, нам нужен компилятор от Intel и магическая опция /Qoffload.

Но обо всё по порядку. Одна из основных идей – это относительно легкая модификация существующего кода, выполняемого на CPU для его выполнения на интегрированной в процессор графике.

Всем привет!

У нас большая удача! Нам удалось договориться с Дмитрием Леневым, уникальным специалистом, разработчиком MySQL Server с 11-летним стажем, о выступлении на CodeFreeze. Москвичи, обязательно приходите!

Итак, в четверг, 19 февраля, в 20:00 в московском офисе Mail.Ru состоится встреча CodeFreeze с Дмитрием Леневым, разработчиком MySQL Server в компании Oracle. Доклад будет посвящен обзору менеджеров блокировок данных в MySQL (включая блокировки метаданных, таблиц и блокировок InnoDB). Будут обсуждаться предназначение каждого из видов и архитектура этих менеджеров.

OpenMP* — довольно популярная модель параллельного программирования, особенно для высокопроизводительных вычислений. Но чтобы этой высокой производительности достичь, OpenMP конструкции частенько приходится «настраивать». И здесь не обойтись без хорошего профилировщика. Большинство профилировщиков выдают данные о производительности, ассоциированные с функциями или циклами, но не дают картины по конкретным OpenMP регионам. В результате программист теряет контекст. А без OpenMP-контекста диагностика дисбалансов или накладных расходов становится весьма затруднительной.
Intel VTune Amplifier XE умеет профилировать OpenMP регионы. Свежая версия 2015 Update 2 делает анализ гораздо более простым и понятным, благодаря представлению данных в «OpenMP терминах». Инструмент показывает время параллельных и последовательных регионов, разницу между фактическим и идеализированным временем исполнения региона, разбивку по параллельным циклам и загрузку ЦПУ по каждому региону в отдельности.
Пользователь может легче понять, куда вкладывать усилия в первую очередь, благодаря метрике «potential gain». Классификация накладных расходов помогает определить причину неэффективности – например, ожидание из-за дисбаланса нагрузки или на «замке» из-за синхронизации.
Статья описывает некоторые типы OpenMP проблем, определяемых VTune Amplifier, как их нужно понимать и устранять.