Software & Systems

В последние годы для решения множества трудновычислимых задач стали применяться методы и средства параллельного программирования. Широко известны модели программирования в общей и распределенной памяти [1], позднее к ним добавились гибридные модели [2]. Однако упомянутые средства чаще всего реализуются при достаточно низкоуровневом программировании, что требует значительной переделки исходного последовательного кода. Следует отметить, что немало математических расчетов выполняется не на алгоритмических языках (C/C++, Fortran), а в специализированных математических пакетах MATLAB [3], Maple [4], Mathematica [5], MathCad [6]. Производители пакетов тоже задумались о реализации возможностей параллелизма в своих продуктах.

К 2016 году сложилась следующая картина.

Изначально возможности параллельного программирования в пакете Mathematica появились в 2001 г. [7]. Для их обеспечения было выпущено дополнительное средство – Parallel Computing Toolkit (требовалась отдельная лицензия, но после выхода версии 7.0 в 2008 г. для работы на локальном компьютере лицензия уже не требуется). В пакете MATLAB возможности параллельного программирования появились в 2005 г. В 2009 г. о реализации средств параллельного программирования было заявлено в Maple. В среде Maple 13 было реализовано программирование в модели общей памяти. Однако средства именно параллельного программирования появились только в выпуске Maple 15 в 2011 г. Следует отметить, что независимые решения предлагались и ранее (см., например, Distributed Maple [8]).

Пакет MathCad чрезвычайно долгое время никак не развивался в этом направлении. Только в версии MathCad Prime 2.0 (2012 г.) появились некоторые изменения: параллелизм на основе средств многоядерных процессоров обеспечивается за счет использования библиотеки Intel MKL [9, 10]. В данной работе рассмотрены средства параллельного программирования в пакетах MATLAB, Maple и Mathematica.

Средства параллельного программирования в MATLAB

До момента реализации функционала па- раллельного программирования производителем (компанией MathWorks) существовали различные подходы к решению [11]. После обеспечения возможностей параллельного программирования появились два вида параллелизма: distributed compu­ting – распределенные вычисления, когда фактически обеспечивается параллелизм по данным [1], и собственно parallel computing, когда взаимодействие между параллельными процессами осуществляется с помощью вызовов специальных команд MATLAB. Для обеспечения возможностей параллелизма в пакете был разработан тулбокс Parallel Computing Toolbox, лицензируемый отдельно.

Параллельное программирование в MATLAB основано на парадигме модели передачи сообщений. Последний (на январь 2016 г.) выпуск R2015b использует на низком уровне библиотеку MPICH2 v.1.4.1p1 [12]. Кроме того, допускается работа с собственной реализацией MPI, удовлетворяющей определенным условиям [13]. Для конечного пользователя есть два режима работы: интерактивный режим pmode [11] и непосредственно параллельное программирование в модели передачи сообщений (модели распределенной памяти).

В таблице 1 приведены основные примитивы параллельного программирования в MATLAB.

Таблица 1

Команды (переменные) MATLAB и их соответствие в MPI

Table 1

MATLAB commands (variable) and their matching in MPI

Как видим, пакет реализует базовый набор директив для параллельного программирования. Опишем реализацию параллельного алгоритма умножения матрицы на вектор z=y+Ax, AÎRn´n, x, y, zÎRn [11]. На начальной стадии перед вычислениями в каждой сессии (в каждом рабочем пространстве процесса) доступен соответствующий блок матрицы A, вектора x и вектора y. Вычисления начинаются с того, что каждый рабочий процесс отправляет доступный ему блок вектора x сосед- нему (по номеру ID) процессу. Следующий шаг – получение с помощью функции labReceive блока вектора x от соседнего рабочего процесса, который к этому моменту уже отправил его.

После получения блока x происходит непосредственное вычисление вектора yk = yk + Ap,txt , где t – номер доступного блока вектора x (на каждом шаге, у каждого рабочего процесса определена своя переменная t).

Приведем реализацию алгоритма на языке MATLAB:

function z=par_multiplication(A, x, y)

% A – матрица

% x,y,z вектор-столбцы

% z=Ax+y;

q=mod(n,numlabs);% остаток от деления

if q==0

r=n/numlabs;

x=x((labindex-1)*r+1:labindex*r);

y=y((labindex-1)*r+1:labindex*r);

A=A((labindex-1)*r+1:labindex*r,:);

else % делится с остатком

r=(n-q)/numlabs;

if labindex==1

x=x(1:r+q);

y=y(1:r+q);

A=A(1:r+q,:);

else

x=x((labindex-1)*r+1+q:labindex*r+q);

y=y((labindex-1)*r+1+q:labindex*r+q);

A=A((labindex-1)*r+1+q:labindex*r+q,:);

end

end

for t=1:numlabs

if labindex==numlabs

labSend(x,1); % последний сразу отправил первому

else

labSend(x,labindex+1);

% остальные отправляют своим соседям (справа)

end

if labindex==1

x=labReceive(numlabs);

% первый получил от последнего

else

x=labReceive(labindex-1);

% остальные получают от своих соседей (слева)

end

tau=labindex-t;

if tau<=0

tau=tau+numlabs;

end

y=y+A(:,1+(tau-1)*r:tau*r)*x;

end

z=y;

Достаточно часто встречаются типовые ситуации, имеющие понятный способ решения. Для некоторых таких случаев предусмотрены штатные средства. Рассмотрим два из них: векторизацию циклов (директива parfor) и частный случай MIMD (в классификации Флинна [1]) типа Single Program Multiple Data (директива spmd).

Цикл parfor – параллельная модификация стандартного цикла for. Оператор parfor полезен в случаях, когда нужно провести много однотипных расчетов, например, при моделировании методом Монте-Карло. Итерации цикла считаются независимо в произвольном порядке рабочими процессами. Понятно, что оператор parfor нельзя применять тогда, когда имеется зависимость по данным между итерациями. Также существуют дополнительные ограничения, о которых можно узнать в документации на продукт.

Операторы внутри блока spmd выполняются одновременно во всех рабочих процессах. Синтаксис команды выглядит следующим образом:

spmd [(m, n)]

end spmd,

где опциональные параметры m и n – минимальное и максимальное число рабочих процессов соответственно.

Помимо описанных способов, начиная с MATLAB R2007b предусмотрено автоматическое распараллеливание функций различных тулбоксов (ядро, Image Processing, Statistics, Optimization Toolbox и т.д.). Система производит автоматическое распределение расчетов на все доступные мощности (например, на все 8 ядер процессора). Кроме того, MATLAB с выпуска R2010b поддерживает параллельные вычисления на графических процессорах (GPU) NVIDIA – программирование в модели CUDA. Соответственно, есть директивы для копирования данных из основной памяти в GPU и, наоборот, директивы для выполнения операций на GPU. Вычисления на GPU происходят как с одинарной, так и с двойной точностью. MATLAB также поддерживает выполнение параллельных задач на кластерных системах с использованием функционала MATLAB Distributed Computing Server (лицензируется отдельно). В его рамках возможен запуск параллельных задач в системе управления пакетными заданиями (СУПЗ) Micro­soft, PBS, Torque, LSF, Condor [14].

Средства параллельного программирования в Maple

Еще в старых версиях Maple были реализованы средства работы с нитями (threads). В качестве примера можно привести реализацию классической задачи «производитель–потребитель» [15, 16]. В этой задаче один процесс (Producer) выдает информацию, а другой (Consumer) ее получает и обрабатывает. При решении задачи могут возникать проблемы потери данных и повторного использования данных.

В версии Maple 13 появилось средство Task Programming Model [17], позволяющее работать в модели общей памяти на высоком уровне абстракции. На более низком уровне Task Programming Model реализуется как работа с нитями (threads). Разра- ботчик не рекомендует конечным пользователям работать на этом уровне [15]. При выполнении программы Maple создаются подзадачи (Tasks), которые средой распределяются на все доступные ресурсы процессоров. Каждая подзадача – это вызов функции, который выполняется отдельной нитью.

В качестве примера приведем реализацию алгоритма сложения большого количества чисел:

Команда Start создает начальную задачу и ожидает, пока она не завершится.

В развитии данного подхода в версии Maple 15 появились средства именно параллельного программирования, которые реализованы в дополнительном пакете Grid Package (Toolbox). Как и в MATLAB, пакет позволяет работать с различными реализациями MPI. По умолчанию в среде Windows используется реализация Microsoft MPI, включенная в Windows HPC Server, а в среде Linux – MPICH2. В таблице 2 приведены основные примитивы параллельного программирования в Maple. Более подробно с ними можно ознакомиться в документации на продукт.

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

После выхода Maple 2015 расширились функции Maple в тулбоксе grid. Были добавлены директивы ожидания выполнения (Wait, WaitForFirst) и запуска на выполнение (Run). Для указания на то, что вычисления необходимо производить параллельно, служит директива Launch. На всех узлах выполняется одинаковая команда. Все вычисления прекращаются, как только закончит работу главный процесс (номер 0). С целью предотвращения взаимоблокировок вычисления прекращаются автоматически по тайм-ауту, если все узлы ожидают сообщений и нет ни одного узла, который их отправляет. Пакет Maple позволяет производить ограниченные параллельные вычисления на GPU. Однако в отличие от MATLAB нет возможности вычислять произвольные функции на GPU. Доступен только ограниченный набор действий. Maple поддерживает выполнение параллельных задач на кластерных системах с использованием функционала тулбокса Grid. В его рамках возможен запуск параллельных задач в СУПЗ Microsoft, PBS, Torque. В этом случае уже требуется дополнительная лицензия на удаленных клиентах-узлах.

Таблица 2

Функции Maple и их соответствие в MPI

Table 2

Maple functions and their matching in MPI

Средства параллельного программирования в Mathematica

Начиная с версии 7.0 (2008 г.) в пакете Mathematica средства параллельного программирования были интегрированы прямо в пакет, не требуя дополнительных программных продуктов (Parallel Computing Toolkit). В версии 8.0 (2010 г.) были произведены некоторые изменения (добавлены sub-kernels), реализована поддержка Windows HPC Server, Microsoft Compute Cluster Server и Sun Grid. В отличие от остальных математических пакетов в Mathematica нет привязки к какой-либо системной библиотеке передачи сообщений. Все действия производятся исключительно средствами среды Wolfram Mathematica. На низком уровне взаимодействие организуется средствами протокола Wolfram Symbolic Transfer Protocol (WSTP) [18]. Он позволяет работать с гетерогенной средой (Windows, Unix, Mac). Поскольку все параллельные возможности «привязаны» к языку, нельзя установить прямые аналогии с функциями MPI, как в случае работы с другими пакетами. В таблице 3 приведены основные примитивы параллельного программирования в Mathematica.

Таблица 3

Команды Mathematica для параллельных вычислений

Table 3

Mathematica commands for parallel computations

Для иллюстрации приведем реализацию решения задачи нахождения списка чисел n, для которых значение n!+1 простое [19]:

In(1):=    n = 1; primes= {}; SetSharedVariable[n, primes];

In(2):=    PrintTemporary[Dynamic[{n, primes}]];

    CheckAbort[

       ParallelEvaluate[While[True,

        With[{n = n++}, If[PrimeQ[n! + 1], AppendTo[primes, n]]]]],

      {n, primes}]

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

Начиная с версии 8.0 среда может работать с графическими процессорами NVIDIA и поддерживает технологии CUDA и OpenCL (что позволяет работать и с графическими процессорами AMD). Для этого реализованы свободно доступные модули CudaLink [20] и OpenCLLink [21].

Как и все предыдущие пакеты, Mathematica позволяет производить распределенные параллельные вычисления на кластерных системах, для чего используется тулбокс GridMathematica [22]. Тулбокс разработан еще в 2002 г. Он также лицензируется отдельно. В настоящее время он позволяет запускать задания на СУПЗ Wolfram Lightweight Grid Manager, PBS, Microsoft, Platform LSF и Sun Grid Engine. В качестве вычислительных мощностей выступают как процессоры, так и графические ускорители.

В заключение отметим, что средства параллельного программирования в пакетах MATLAB и Mathematica достаточно хорошо описаны в литературе (например [23, 24]). Для работы со средствами параллельного программирования в пакете Maple нет литературных источников, однако документация на продукт достаточно высокого качества, что позволяет использовать ее для полноценного решения задач. Отметим, что средства параллельного программирования в математических пакетах регулярно развиваются. В зависимости от того, в каком пакете происходит работа, доступны несколько отличающиеся возможности, однако любая задача может быть решена в каждом из рассмотренных пакетов, за исключением MathCad.

Литература

1.     Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб: BHV-Петербург, 2002. 608 с.

2.     Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования; [пер. с англ.]. М.: Вильямс, 2003. 512 с.

3.     MathWorks. URL: http://www.mathworks.com (дата обращения: 01.01.2016).

4.     Maplesoft. URL: http://www.maplesoft.com (дата обращения: 01.01.2016).

5.     Wolfram. URL: http://www.wolfram.com (дата обращения: 01.01.2016).

6.     PTC Mathcad. URL: http://www.ptc.com/mathcad (дата обращения: 01.01.2016).

7.     Mäder R. Parallel Computing with Mathematica. Proc. 4th Intern. Workshop on Computer Algebra in Scientific Computing, Konstanz, Sept. 22–26, 2001, p. 399.

8.     Schreiner W., Mittermaier C., Bosa K. Distributed Maple: parallel computer algebra in networked environ-ments. Journ. of Symbolic Computation, 2003. vol. 35, iss. 3, pp. 305–347.

9.     Kucan J. Multi-threading, multi-core and parallel calcu­lation in Mathcad. URL: http://blogs.ptc.com/2012/05/16/multi-threading-multi-core-and-parallel-calculation-in-mathcad/ (дата обращения: 01.01.2016).

10.  Intel® Math Kernel Library (Intel® MKL). URL: https:// software.intel.com/en-us/intel-mkl (дата обращения: 01.01.2016).

11.  Оленев Н.Н., Печенкин Р.В., Чернецов А.М. Параллельное программирование в MATLAB и его приложения. М.: Изд-во ВЦ РАН, 2007. 120 с.

12.  Чернецов А.М. Использование сторонних библиотек MPI для параллельного программирования в MATLAB // Радиоэлектроника, электротехника и энергетика: тр. 14 Междунар. науч.-технич. конф. студентов и аспирантов в 3-х т. М.: Изд-во МЭИ, 2008. Т. 1. C. 309–310.

13.  MPICH. URL: http://www.mpich.org (дата обращения: 01.01.2016).

14.  Чернецов А.М. Использование средств MATLAB для организации распределенной обработки // Информатизация инженерного образования: тр. междунар. конф. М.: Изд-во МЭИ, 2012. С. 127–130.

15.  Multithreaded Programming. URL: http://www.maplesoft. com/support/help/Maple/view.aspx?path=multithreaded (дата обращения: 01.01.2016).

16.  Таненбаум Э. Современные операционные системы; [пер. с англ.]. СПб: Питер, 2013. 1120 с.

17.  Task Programming Model URL: http://www.maplesoft. com/support/help/Maple/view.aspx?path= TaskProgrammingModel (дата обращения: 01.01.2016).

18.  WSTP API. URL: http://reference.wolfram.com/language/ guide/WSTPAPI.html (дата обращения: 01.01.2016).

19.  Parallel Computing. URL: https://reference.wolfram.com/ language/guide/ParallelComputing.html (дата обращения: 01.01.2016).

20.  CUDALink Overview. URL: http://reference.wolfram. com/language/CUDALink/tutorial/Overview.html (дата обращения: 01.01.2016).

21.  OpenCLLink Overview URL: http://reference.wolfram. com/language/OpenCLLink/tutorial/Overview.html (дата обращения: 01.01.2016).

22.  Wolfram gridMathematica. URL: http://www.wolfram. com/gridmathematica/ (дата обращения: 01.01.2016).

23.  Кепнер Дж. Параллельное программирование в среде MATLAB для многоядерных и многоуровневых вычислительных машин; [пер. с англ.]. М.: Изд-во МГУ, 2013. 296 с.

24.  Аладьев В., Гринь Д., Ваганов В. Избранные системные задачи в программной среде Mathematica. М.: Олди-плюс, 2013. 555 с.