Технология параллельного программирования

Когда-то параллельное программирование было уделом только тех одиночек, которых интересовали задачи для огромных суперкомпьютеров. Но теперь, когда на многоядерных процессорах начали работать обычные приложения, параллельное программирование быстро становится технологией, которую должен освоить и уметь применять любой профессиональный разработчик ПО.

Параллельное программирование может быть сложным, но его легче понять, если считать не "трудным", а просто "немного иным". Оно включает в себя все черты более традиционного, последовательного программирования, но в параллельном программировании имеются три дополнительных, четко определенных этапа.

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

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

• OpenMP: директивы компилятора для простого параллельного программирования
• MPI: библиотечные подпрограммы для реализации высокоэффективной переносимости
• Java: параллельность в языке программирования на основе ведущих объектов

Чтобы сделать обсуждение максимально конкретным, для каждого варианта приводится параллельная версия известной программы. Это обычное численное интегрирование с помощью формулы трапеций, причем подынтегральная функция и пределы интегрирования выбираются так, чтобы математически верным результатом являлось число π. Эта задача считается аналогом программы "hello world" в параллельном программировании. В конце статьи дается краткое объяснение, как выбрать систему обозначений параллельного программирования для работы и изучения.

Программа π: параллельное интегрирование по формуле трапеций

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

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

Можно выбрать подынтегральную функцию и пределы интегрирования так, чтобы значение интеграла было равно π. Таким образом, проверка правильности работы программы становится простой задачей. Простая программа на языке C, реализующая этот алгоритм, выглядит следующим образом:

static long num_steps = 100000;

double step;

void main ()

{int i; double x, pi, sum = 0.0;

step = 1.0/(double) num_steps;

for (i=0;i<= num_steps; i++){

x = (i+0.5)*step;

sum = sum + 4.0/(1.0+x*x);

}

pi = step * sum;

}

OpenMP

OpenMP [omp] — это API-интерфейс, который является отраслевым стандартом для создания параллельных приложений для компьютеров с совместным использованием памяти. Главная задача OpenMP — облегчить написание программ, ориентированных на циклы. Такие программы часто создаются для высокопроизводительных вычислений. Кроме того, в OpenMP были включены компоненты для поддержки таких параллельных алгоритмов как SPMD, "главный и рабочий процесс", конвейерный и т.д.

OpenMP стал очень успешным языком параллельного программирования. Он имеется на каждом компьютере с совместным использованием памяти, выходящем на рынок. Кроме того, недавно в Intel© был создан вариант OpenMP для поддержки кластеров. OpenMP поддерживает такой стиль программирования, при котором параллелизм добавляется постепенно, пока имеющаяся последовательная программа не превратится в параллельную. Впрочем, это преимущество является и самым слабым местом OpenMP. Если параллелизм добавляется постепенно, программист может не выполнить широкомасштабную перестройку программы, которая часто необходима для достижения максимальной производительности.

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

OpenMP: обзор

OpenMP основывается на модели программирования "разветвление-объединение" (fork-join). Работа программы OpenMP начинается с одного потока. Когда программисту требуется добавить в программу параллелизм, выполняется разветвление на несколько потоков, чтобы создать группу потоков. Эти потоки выполняются параллельно в рамках фрагмента кода, который называется параллельным участком. В конце параллельного участка все потоки заканчивают свою работу и снова объединяются вместе. После этого исходный (или "главный") поток продолжает выполняться до тех пор, пока не начнется следующий параллельный участок (или не наступит конец программы).

Языковые конструкции в OpenMP определены как директивы компилятора, которые сообщают компилятору, что он должен делать, чтобы реализовать требуемый параллелизм. В C и C++ такие директивы называются "прагмы".

Прагма OpenMP всегда имеет один и тот же вид:

#pragma omp имя_конструкции один_или_несколько_операторов

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

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

Для создания потока в OpenMP используется конструкция "parallel".

#pragma omp parallel

{

…. A block of statements

}

Если такая конструкция используется без уточняющих операторов, то число потоков, которые создает программа, определяется средой выполнения (обычно это число равно числу процессоров или ядер). Каждый поток будет выполнять блок инструкций, который следует за прагмой parallel. Это может быть почти любой набор разрешенных инструкций в C; единственным ограничением является запрет на переходы внутрь этого блока инструкций или из него. Если вдуматься, это не лишено смысла. Если потоки выполняют весь набор инструкций, а результат работы программы должен быть осмысленным, то потоки не должны беспорядочно перемещаться внутрь конструкции в рамках параллельного участка или из нее. В OpenMP это - общее ограничение. Такой блок инструкций без переходов называется "структурированным блоком".

Значительная часть параллельного программирования состоит именно в том, чтобы поручить всем потокам выполнение одних и тех же инструкций. Но чтобы использовать OpenMP в полной мере, потребуется что-то большее. Необходимо разделить между потоками работу по выполнению набора инструкций. Такой тип поведения называется "совместное выполнение работы". Самая типичная конструкция для совместной работы — это конструкция цикла (в C это цикл for).

#pragma omp for

Это работает только для простых циклов стандартного вида:

for(i=lower_limit; i<upper_limit; inc_exp)

Конструкция for распределяет итерации цикла между потоками группы, созданными ранее с помощью конструкции parallel. Начальное и конечное значения счетчика цикла, а также выражение для шага счетчика (inc_exp) должны быть полностью определены во время компиляции, а все константы, которые используются в этих выражениях, должны быть одинаковы для всех потоков группы. Если вдуматься, это не лишено смысла. Система должна вычислить, сколько итераций цикла должно быть выполнено, чтобы разделить их на наборы, которые будут обрабатывать группы потоков. Это можно сделать только согласованно и точно, если все потоки используют одни и те же наборы счетчиков.

Необходимо отметить, что сама по себе конструкция for потоки не создает. Это можно сделать только с помощью конструкции parallel. Для простоты можно поместить конструкции parallel и for в одну и ту же прагму.

#pragma omp parallel for

При этом будет создана группа потоков для выполнения итераций цикла, который следует непосредственно за прагмой.

Итерации цикла должны быть независимыми, чтобы результат выполнения цикла оставался неизменным независимо от того, в каком порядке и какими потоками выполняются эти итерации. Если один поток записывает переменную, которую затем считывает другой поток, то наблюдается кольцевая зависимость, и результат работы программы будет неверным. Программист должен тщательно проанализировать тело цикла, чтобы убедиться в отсутствии кольцевых зависимостей. В большинстве случаев такая зависимость возникает, если в переменную записываются промежуточные результаты, которые используются в данной итерации цикла. В этом случае приобретенной зависимости можно избежать, объявив, что каждый поток должен иметь собственное значение для этой переменной. Это можно сделать с помощью оператора private. Например, если в цикле используется переменная "tmp", в которой хранится временное значение, к конструкции OpenMP можно добавить следующий оператор, после чего переменную можно будет использовать в теле цикла, не создавая приобретенных зависимостей.

private(tmp)

Кроме того, часто встречается ситуация, когда переменная внутри цикла используется для сложения значений, полученных в каждой итерации. Например, это происходит в цикле, который суммирует результаты вычислений, чтобы получить одно итоговое значение. Такая ситуация часто возникает в параллельном программировании. Она называется "редукция". В OpenMP имеется оператор reduction:

reduction(+:sum)

Как и оператор private, он добавляется в конструкцию OpenMP, чтобы сообщить компилятору, что следует ожидать редукции. После этого создается временная закрытая переменная, которая используется для получения промежуточного результата операции суммирования для каждого потока. В конце выполнения конструкции значения этой переменной для каждого потока суммируются, чтобы получить конечный результат. Операция, которая используется при редукции, также указывается в операторе. В данном случае это операция "+". OpenMP определяет значение для закрытой переменной, которая используется в редукции, на основе соответствующей математической операции. Например, для "+" это значение равно нулю.

В OpenMP еще много интересных моментов, но и этих двух конструкций и операторов достаточно, чтобы объяснить, как распараллелить программу π.

OpenMP: программа π

Чтобы не усложнять задачу, будем использовать фиксированное число шагов. Кроме того, будет использоваться только число потоков по умолчанию. В последовательной программе π имеется единственный цикл, который требуется распараллелить. Итерации цикла полностью независимы, если не считать значения зависимой переменной "x" и накопительной переменной "sum". Необходимо отметить, что "x" используется как временное хранилище для вычислений в итерации цикла. Соответственно, эту переменную необходимо сделать локальной для каждого потока с помощью оператора private:

private(x)

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

Накопительная переменная, "sum", используется для суммирования. Это классический пример редукции, поэтому можно применить оператор reduction:

reduction(+:sum)

После добавления этих операторов к конструкции "parallel for", получим программу п, распараллеленную с помощью OpenMP.

#include <omp.h>

static long num_steps = 100000; double step;

void main ()

{ int i; double x, pi, sum = 0.0;

step = 1.0/(double) num_steps;

#pragma omp parallel for private(x) reduction(+:sum)

for (i=0;i<= num_steps; i++){

x = (i+0.5)*step;

sum = sum + 4.0/(1.0+x*x);

}

pi = step * sum;

}

Необходимо отметить, что с помощью директивы include был также включен стандартный файл для OpenMP:

#include <omp.h>

Это позволяет определить типы и библиотечные подпрограммы времени выполнения, которые иногда требуются программисту OpenMP. Заметим, что в данной программе эти компоненты языка не использовались, но хороший стиль программирования предполагает добавление подключаемого файла OpenMP, хотя бы на тот случай, если он потребуется для будущего изменения программы.

MPI

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

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

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

В большинстве MPI-программ используется шаблон "Одна программа, разные данные" (Single Program Multiple Data, или SPMD) [mattson05]. В его основе лежит простой принцип: каждый элемент обработки (processing element, PE) выполняет одну и ту же программу. Каждому элементу обработки присваивается уникальный целочисленный идентификатор, который определяет его ранг в наборе элементов обработки. Программа использует этот ранг, чтобы распределить работу и определить, какой элемент PE какую работу выполняет. Иными словами, программа всего одна, но благодаря выбору, сделанному в соответствии с идентификатором, данные для каждого элемента обработки могут быть разными. Это и есть шаблон "Одна программа, разные данные".

MPI Overview

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

Ключевое понятие MPI — коммуникатор. При создании набора процессов они образуют группу, которая может совместно использовать среду для связи.

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

При запуске MPI-программы создается коммуникатор по умолчанию, MPI_COMM_WORLD, который передается каждой MPI-подпрограмме в качестве первого аргумента. Остальные аргументы определяют источник сообщения и буферы для хранения сообщений. MPI-подпрограммы возвращают целочисленное значение как параметр ошибки, что позволяет узнать о любых проблемах, имевших место при выполнении подпрограммы.

Обычно где-нибудь в начале MPI-программы выполняется вызов трех подпрограмм для настройки применения MPI.

int my_id, numprocs;
MPI_Init(&argc, &argv);
MPI_Comm_Rank(MPI_COMM_WORLD, &my_id);
MPI_Comm_Size(MPI_COMM_WORLD, &numprocs);

Первая подпрограмма (MPI_Init) принимает в качестве входных параметров аргументы командной строки, знакомые каждому программисту C, и инициализирует среду MPI. Две следующие подпрограммы принимают как входной параметр имя MPI-коммуникатора (в данном случае это коммуникатор по умолчанию) и возвращают ранг вызывающего процесса и общее число процессов. Ранг используется как уникальный идентификатор процесса. Его значение может лежать в пределах от нуля до числа процессов минус один.

Информация о том, сколько процессов создано и на каких процессорах они работают, является внешней по отношению к API-интерфейсу MPI. В зависимости от того, какая платформа поддерживает MPI, используются разные методы. В большинстве случаев это файл главной машины, в котором все процессоры перечислены по именам. Он передается стандартному сценарию оболочки под названием mpirun, который имеется на большинстве MPI-платформ, для запуска MPI-программы. Детали этой простой процедуры меняются от одной платформы к другой и поэтому здесь обсуждаться не будут.

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

int MPI_Finalize();

Между этими подпрограммами и располагается рабочая часть MPI-программы. Большая часть программы представляет собой обычный последовательный код, язык которого программист выбирает сам. Как упоминалось выше, хотя все процессы выполняют одинаковый код, поведение программы различается в зависимости от ранга процесса. В тех точках, где требуется связь или иное взаимодействие между процессами, вставляются MPI-подпрограммы. В первую версию MPI входило более 120 подпрограмм, а в последней версии (MPI 2.0) их количество еще возросло. Впрочем, в большинстве программ используется очень небольшой набор MPI-функций. Здесь будет обсуждаться только одна подпрограмма для выполнения редукции и возврата конечного результата одному из процессов в группе.

int MPI_Reduce(void* sendbuf, void* recvbuf,
int count, MPI_Datatype datatype, MPI_OP op,
int root, MPI_COMM comm.)

Эта функция принимает "count" значений типа "datatype" в буфере "sendbuf", собирает результаты от каждого процесса с помощью операции "op", а затем помещает результат в буфер "recvbuf" процессов ранга "root". MPI_Datatype и MPI_OP принимают интуитивно понятные значения, такие как "MPI_DOUBLE" или "MPI_SUM".

Другие часто используемые в MPI подпрограммы служат для широковещательной передачи сообщения (MPI_Bcast), определения барьерных точек синхронизации (MPI_Barrier), отправки (MPI_Send) или получения (MPI_Recv) сообщения. Дополнительные сведения об MPI можно найти в Интернете либо в источниках [mpi] и [mattson05].

MPI: программа π

MPI-программа π является непосредственной модификацией исходного последовательного кода. Чтобы избежать излишнего усложнения, число шагов по-прежнему будет задаваться в программе, а не вводиться и передаваться другим процессам.

В начале программы подключается файл MPI, чтобы определить типы данных, константы и подпрограммы MPI. Затем следует стандартная тройка подпрограмм, чтобы инициализировать среду MPI и сделать основные параметры (число процессов и ранг) доступными для программы.

#include <mpi.h>

static long num_steps = 100000;

void main (int argc, char *argv[])

{

int i, my_id, numprocs;

double x, pi, step, sum = 0.0;

step = 1.0/(double) num_steps;

MPI_Init(&argc, &argv);

MPI_Comm_Rank(MPI_COMM_WORLD, &my_id);

MPI_Comm_Size(MPI_COMM_WORLD, &numprocs);

my_steps = num_steps/numprocs;

for (i=my_id; i<num_steps; i+numprocs)

{

x = (i+0.5)*step;

sum += 4.0/(1.0+x*x);

}

sum *= step;

MPI_Reduce(&sum, &pi, 1, MPI_DOUBLE, MPI_SUM, 0,

MPI_COMM_WORLD);

MPI_Finalize(ierr);

}

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

После завершения работы каждого процесса он вносит свой вклад в сложение, помещая готовую промежуточную сумму в переменную "sum", а затем выполняется редукция с помощью следующего вызова:

MPI_Reduce(&sum, &pi, 1, MPI_DOUBLE, MPI_SUM, 0,
MPI_COMM_WORLD);

Смысл каждого аргумента должен быть ясен при сравнении с определением MPI_Reduce, которое обсуждалось в предыдущем разделе. Промежуточная сумма, "sum", используется как буфер отправки, а переменная "pi" — как буфер приема. Это значение будет доставлено процессу ранга "0", который указан в качестве шестого аргумента подпрограммы MPI_Reduce. Буфер отправки содержит одно значение типа MPI_DOUBLE с операцией накопления суммирования (MPI_SUM). И, наконец, процессы, участвующие в этой редукции, используют коммуникатор MPI_COMM_WORLD.

Потоки Java: обзор

Язык Java разрабатывался с встроенной поддержкой многопотоковости. Потоки — один из ключевых элементов технологии Java; они поддерживаются как на языковом (синтаксическом) уровне, так и на уровне виртуальной машины Java и библиотек классов. Во многих случаях потоки Java очень похожи на потоки POSIX (pthreads). Библиотеки классов Java предоставляют класс thread, который поддерживает широкий набор методов для запуска, выполнения и остановки потока, а также проверки его состояния.

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

Потоки Java: программа π

Этот простой пример показывает, как создать распараллеленный вариант программы π с помощью "чистых" потоков Java.

public class PI1 {

static long num_steps = 100000;

static double step;

static double sum = 0.0;

static int part_step;

static class PITask extends Thread {

int part_number;

double x = 0.0;

double sum = 0.0;

public PITask(int part_number) {

this.part_number = part_number;

}

public void run()

{

for (int i = part_number; i < num_steps; i += part_step) {

x = (i + 0.5) * step;

sum += 4.0 / (1.0 + x * x);

}

}

}

public static void main(String[] args) {

int i;

double pi;

step = 1.0 / (double) num_steps;

part_step = Runtime.getRuntime().availableProcessors();

PITask[] part_sums = new PITask[part_step];

for (i = 0; i < part_step; i++) {

(part_sums[i] = new PITask(i)).start();

}

for (i = 0; i < part_step; i++) {

try {

part_sums[i].join();

} catch (InterruptedException e) {

}

sum += part_sums[i].sum;

}

pi = step * sum;

System.out.println(pi);

}

}

Чтобы запустить новый поток в Java, обычно нужно создать подкласс класса Thread и определить пользовательский метод run(), выполняющий основную работу, которая должна быть распараллелена. В нашем примере эта задача реализована с помощью метода run() класса PITask. Из соображений производительности весь участок интегрирования был разбит на part_step фрагментов, так чтобы число этих фрагментов было равно числу имеющихся процессоров. Объекты PITask принимают параметр part_number, который помечает данный фрагмент участка интегрирования. Таким образом, в теле run() вычисляется промежуточная сумма по данному фрагменту участка интегрирования. Реальный поток запускается и выполняется параллельно после вызова метода start(). Это делается в цикле для всех фрагментов. Затем начинает работать второй цикл, где с помощью метода join() каждого параллельного потока ожидается завершение выполнения последнего, после чего результаты, полученные от каждого потока, суммируются. В данном примере каждый фрагмент участка интегрирования явно назначается отдельному потоку Java.

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

Параллельная среда Java FJTask

В то время как "чистые" потоки Java, описанные в предыдущем разделе, представляют собой самый нижний уровень поддержки многопотоковости в Java, существует еще множество высокоуровневых библиотек распараллеливания, которые предназначены как для расширения базовых возможностей многопотоковости в Java, так и для добавления решений для некоторых часто встречающихся задач. Ярким примером является пакет java.util.concurrent, который входит в стандарт Java начиная с версии 1.5. Этот пакет включает в себя множество усовершенствований базового распараллеливания Java, таких как поддержка пулов потоков, элементарные переменные и сложные примитивы синхронизации. Однако некоторые компоненты пакета util.concurrent не вошли в стандарт J2SE и в настоящее время доступны в виде отдельной библиотеки под названием EDU.oswego.cs.dl.util.concurrent.

Одним из наиболее важных таких компонентов является среда FJTask, которая реализует концепцию параллелизма "разветвление-объединение" для Java. Эта среда предназначена, в первую очередь, для распараллеливания сложных вычислений, таких как численное интегрирование или перемножение матриц. Задачи FJTask — это облегченные аналоги потоков Thread. Эту технологию часто называют "параллелизмом на основе задач", в отличие от "параллелизма на основе потоков". Задачи FJTask обычно выполняются с помощью того же пула потоков Java. Задачи FJTask поддерживают вариации самых общих методов класса Thread, включая start(), yield() и join(),
и не поддерживают некоторые методы потоков Java, например управление приоритетами. Основной выигрыш при использовании задач FJTask получается за счет того факта, что они не поддерживают блокировку операций любого рода. Ничто не мешает выполнить блокировку внутри FJTask, и очень короткие ожидания и блокировки вполне приемлемы. Задачи FJTask не предназначены для поддержки произвольной синхронизации, поскольку не существует способа приостановить, а затем продолжить выполнение отдельных задач после того, как они были запущены. Кроме того, время выполнения задач FJTask должно быть ограничено, и они не должны содержать бесконечных циклов. Задачи FJTask просто должны выполняться до конца, безо всяких ожиданий и блокировок ввода-вывода. Между задачами FJTask и потоками Thread имеются существенные различия. FJTask могут выполняться на два или три порядка быстрее, чем Thread, по крайней мере если они работают на виртуальных машинах Java с высокопроизводительным сбором мусора (каждая задача FJTask производит очень много мусора) и хорошей встроенной поддержкой потоков.

Параллельная среда Java FJTask: программа π

Приведенный ниже пример показывает, как написать программу π с помощью среды FJTask.

import EDU.oswego.cs.dl.util.concurrent.FJTask;
import EDU.oswego.cs.dl.util.concurrent.FJTaskRunnerGroup;

public class PI2 {

static int num_steps = 100000;

static double step;

static double sum = 0.0;

static int part_step;

static class PITask extends FJTask {

int i = 0;

double sum = 0.0;

public PITask(int i) {

this.i = i;

}

public void run() {

double x = (i + 0.5) * step;

sum += 4.0 / (1.0 + x * x);

}

}

public static void main(String[] args) {

int i;

double pi;

step = 1.0 / (double) num_steps;

try {

FJTaskRunnerGroup g = new FJTaskRunnerGroup(Runtime.getRuntime()

.availableProcessors());

PITask[] tasks = new PITask[num_steps];

for (i = 0; i < num_steps; i++) {

tasks[i] = new PITask(i);

}

g.invoke(new FJTask.Par(tasks));

for (i = 0; i < num_steps; i++) {

sum += tasks[i].sum;

}

pi = step * sum;

System.out.println(pi);

System.out.println(Math.PI);

} catch (InterruptedException ie) {

}

}

}

Сначала объявляется метод run() для класса PITask, как и в предыдущем примере. Однако теперь вместо того чтобы вычислять промежуточную сумму для каждого фрагмента участка интегрирования, в PITask рассчитывается только одно значение x, которое соответствует i-му шагу. Затем создается массив объектов PITask, который помещается в объект FJTask.Par. Далее массив передается на выполнение с помощью вызова invoke() объекта FJTaskRunnerGroup. Помещение массива в объект FJtask.Par показывает среде, что этот массив задач должен выполняться параллельно в пуле потоков. Число потоков в этом пуле было задано равным числу процессоров. Метод invoke() в данном примере выполняет блокировку до тех пор, пока все задачи в массиве не будут выполнены. Это позволяет вычислить общую сумму сразу после этого, получив промежуточное значение суммы от каждой конкретной задачи.

Следует отметить, что эта слегка измененная версия Java-программы π не создает никаких потоков явным образом и не выполняет никакого разделения работы между потоками и задачами. Однако, как можно видеть, эта программа работает достаточно хорошо, даже по сравнению с предыдущим примером, в котором разделение работы между потоками выполнялось явным образом. Это происходит потому, что создание и асинхронное выполнение каждой новой задачи FJtask происходит почти со скоростью вызова метода. Впрочем, чтобы добиться максимальной производительности, все же рекомендуется назначать каждому объекту FJTask разумный объем работы, чтобы числом этих объектов можно было управлять. Это позволит уменьшить нагрузку на сборщик мусора в виртуальной машине Java.

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

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

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

Поиск по сайту: