29 мая 2009 г.

Шлакоблоки параллельного программирования

Существует несколько способов, как добиться от программистов большой скорости решения поставленных задач с минимальным количеством ошибок. Первый способ — использование языков высокого уровня, например, С++. Объектно-ориентированное программирование позволяет создать в коде сущности различной природы, а также определять операции над ними. В результате мы получаем в распоряжение набор каких-либо объектов, которые соответствуют объектам из предметной области решаемой задачи, с высокоуровневыми свойствами и методами. Детали реализации скрываются за этими высокоуровневыми методами, что позволяет программисту сосредоточиться на решении задачи. Второй способ — использование современных инструментальных средств: компиляторов, генераторов тестов, формальных верификаторов, профайлеров. Компиляторы используют внутренние оптимизации для получения лучших временных характеристик и минимальных затрат памяти. Примером таких оптимизаций может служить автоматическая конвейеризация, развертки (свёртки) или распараллеливание циклов, при котором получается более быстрая реализация программы. В этом случае решением рутинных задач программирования занимается компилятор, который, как известно, работает намного быстрее и ошибается реже, чем программист. Третий способ — использование методического обеспечения. Разработано множество методов проектирования и т. н. паттернов — подходов к решению той или иной задачи в определенном контексте. Издано множество книг и пособий, посвященных как программированию самому по себе, решению абстрактных задач, а также по применению в конкретных задачах народного хозяйства. Четвертый способ — использование библиотек, которые содержат готовые протестированные решения: алгоритмы и структуры данных. Используя библиотечные компоненты, во-первых, сокращается время на разработку, а, во-вторых, сокращается время на тестирование проекта, потому что библиотечные компоненты протестированы заранее и неоднократно были внедрены в промышленные проектах. Таким образом, объем библиотечного кода может существенно превышать объем кода, написанного программистом. Сделаем краткий обзор технологий, которые повышают производительность программистов, разрабатывающих параллельные приложения. Многие годы самым доступным способом многопоточного программирования было использование библиотеки Windows API или POSIX Threads. Программисту приходилось решать поставленные задачи на очень низком уровне. Например, программисту необходимо:
  • самостоятельно создавать и удалять потоки;
  • определять те функции, которые должны выполняться в потоке;
  • передавать в поток нужные параметры;
  • использовать различные функции для синхронизации потоков;
  • обеспечить равномерную загрузку потоков вычислениями;
  • позаботиться о масштабируемости полученного решения.
Очевидно, что недостаток такого подхода заключается в том, что преобразование последовательной программы в параллельную может занять много времени. Также полученное решение будет подвержено множеству ошибок. Часть этих проблем была успешно решена в библиотеке OpenMP. Эта библиотека реализована в виде набора функций и директив — специальных расширений к компилятору. Программист в требуемом месте применяет ту или иную директиву, а компилятор в указанном месте подставляет вызовы системных функций. Например, распараллеливание цикла осуществляется единственной директивой компилятору. При этом компилятор позаботится о создании и синхронизации потоков, разделении итераций между потоками, а также хорошим балансом загрузки. Такой подход позволяет решить ограниченный класс задач практически без ошибок и в краткий срок. Но библиотека OpenMP имеет ряд ограничений и недостатков. Укажем лишь некоторые из них.
  1. Циклы с неизвестным количеством итераций не могут быть распараллелены.
  2. Существенные ограничения на параметры цикла.
  3. Ограниченные возможности по распределению работы между потоками.
  4. Операция reduction ограничена восемью элементарными операциями.
  5. Отсутствие более сложных шаблонов, чем параллельный цикл или параллельная секция.
Intel Threading Building Blocks (далее ТББ) — новая библиотека для многопоточного программирования, разработанная фирмой Интел. Библиотека имеет ряд функций и классов для решения распространенных задач параллельного программирования:
  • функция parallel_for для организации параллельного цикла;
  • функция parallel_reduce для параллельного цикла с последующей комбинацией частичных результатов;
  • класс parallel_while для создания параллельного цикла с неизвестным количеством итераций;
  • класс pipeline для организации конвейерных вычислений;
  • контейнеры с возможностью параллельного доступа: concurrent_vector, concurrent_queue, concurrent_hash_map.
В ТББ введена концепция объекта-задачи — класс С++, в котором определен оператор (), который выполняет поставленную задачу (см. листинг ниже). В зависимости от алгоритма, в котором используется объект-задача, этот оператор, например, может принимать в качестве параметра диапазон итераций (parallel_for, parallel_reduce) или очередной элемент для обработки (parallel_while, pipeline).
// Класс-задача
class Body
{
public:
    // Оператор-обработчик
    void operator() ()
    {
        // Здесь расположены вычисления
    }
};


* This source code was highlighted with Source Code Highlighter.
Здесь видно отличие от программирования обычных потоков: программист создает задачи, а не потоки. Библиотека ТББ при инициализации создает необходимое количество потоков, а встроенный планировщик назначает задачи на эти потоки во время работы программы. Функции-шаблоны parallel_for и parallel_reduce работают с диапазонами (пространствами итераций). Библиотека ТББ предоставляет для этого два класса: blocked_range и bloced_range2d, одномерное и многомерное пространство соответственно. ТББ рекурсивно делит исходный диапазон на множество блоков, которые передаются в качестве параметров для оператора-обработчика. Таким образом, каждый объект-задача делает вычисления над собственной порцией итераций. Приведем пример использования одномерного диапазона.
blocked_range<int>(begin, end, grainsize)
Здесь параметр шаблона — это тип элементов диапазона, begin — начальная точка, end — конечная точка. Пара begin и end описывает полуоткрытый интервал [begin, end), например, цикл for (int i = 2; i < 5; i++) соответствует интервалу [2; 5) и включает в себя итерации 2, 3, 4. Параметр grainsize определяет размер неделимого блока итераций. В том случае, если на очередном этапе разделения исходного диапазона встретится блок, меньший, чем grainsize, то он будет считаться неделимым. На рисунке ниже показан пример рекурсивного разделения диапазона blocked_range(0, 10, 3).
В завершении статьи приведем пример распараллеливания цикла for.
#include "tbb/blocked_range.h"
#include "tbb/parallel_for.h"
#include "tbb/task_scheduler_init.h"

using namespace tbb;

///////////////////////////////////////////////////////////////////////////////

// Класс-задача
class MyTask
{
public:
    // Метод-обработчик выполняет функцию Calculate для каждого элемента
    // блока итераций.
    void operator() (const blocked_range<int>& r) const
    {
        for (int i = r.begin(); i != r.end(); i++)
            Calculate(i);
    }
};

///////////////////////////////////////////////////////////////////////////////

int main()
{
    // Инициализация библиотеки ТББ
    task_scheduler_init init;

    // Запуск шаблона parallel_for, который принимает два параметра:
    // * объект диапазона итераций [0, 1000000)
    // * объект-задачу
    parallel_for(blocked_range<int>(0, 1000000, 10000), MyTask);

    return 0;
}

///////////////////////////////////////////////////////////////////////////////


* This source code was highlighted with Source Code Highlighter.

Комментариев нет:

Отправить комментарий

Темы

2012 (2) амазон (1) анпакинг (1) артемий лебедев (4) атн (1) аудио (1) аэропорт (1) безопасность (3) бизнес (1) билайн (1) блог (2) будущее (2) видео (11) википедия (5) вымысел (16) гагарин (1) герман (1) гитхаб (1) гугл (3) дед мороз (1) декабрь (1) демотиватор (2) дети (2) дизайн (13) диссертация (2) документация (1) друзья (5) евпатория (1) евро-2012 (1) жадность (1) заяц (1) идея (1) имейл (1) инстаграм (1) интервью (5) интересное (20) интерфейс (13) история (7) как_выжить (4) календарь (1) капитализм (1) картина (1) кмб (6) книга (6) коллекция (4) компилятор (2) конкурс (5) космос (1) лаборатория (1) либералы (1) лингво (1) лузер (6) макаренко (2) макдональдс (2) математика (1) медиапорт (1) ментор (1) металлика (1) металлист (2) метро (7) микрософт (6) миргород (1) москва (2) музыка (3) наркомания (1) новости (17) образование (3) оптимизация (5) основы (14) открытки (3) ошибка (11) памятник (1) патриотизм (3) плагиат (1) плата (1) погода (3) поиск (1) политика (2) полтава (2) праздник (1) программирование (15) прошлое (2) путешествия (8) рейтинг (1) рендер (1) рисунок (2) русские (1) русский язык (1) сайт (4) санкт-петербург (1) сапр (7) сеть (1) си++ (1) синтез (1) системси (1) скриншот (40) социализм (1) соцопрос (3) спектрум (2) спорт (2) срач (2) статистика (1) такси (1) тбб (3) твитер (9) тимошенко (1) украина (5) униан (1) фан (30) фокус (1) фото (39) фотошоп (1) фурсенко (1) футбол (2) хабр (1) харьков (21) хнурэ (19) хобби (4) цитата (2) чехия (1) школа (1) эпл (1) эхостар (1) юмор (1) яндекс (1) clang (2) doxygen (1) english (3) ios (1) llvm (1) msdn (1) outlook (1) PHP (1) stackoverflow (1)

Поиск

Архив

Читатели