ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

2
Publication date:
16 June 2024

Parallel programming in mathematical suites

Date of submission article: 21.02.2016
UDC: 007:004.451.2:004.434
The article was published in issue no. № 2, 2016 [ pp. 5-10 ]
Abstract:Recently tools and features of parallel programming have been used for calculating difficult tasks. Programming models in shared and distributed memory are well-known. Later hybrid models have appeared. However, all these tools suppose fairly low-level programming when a source code is modified significantly. A significant number of mathematical calculations is performed not in algorithmic languages (C/C++, Fortran), but in special mathematical suites such as MATLAB, Maple, Mathematica, MathCad. The paper discusses parallel programming tools in modern mathematical suites. There is a short review of parallel programming tools development in well-known suites, such as MATLAB, Maple, Mathematica and Mathcad. The paper briefly describes the main primitives of parallel programming and their analogs in MPI for MATLAB. It also mentions other operators of parallel programming. It describes different features of parallelism in Maple (threads programming, high-level Task Programming Model, parallel programming). There are some basic constructions of parallel programming in Mathematica Wolfram language. The paper describes different examples. Different possibilities are available depending on an operation suite. However, any problem can be solved in each of these suites (except MathCad).
Аннотация:За последние годы при решении множества трудновычислимых задач стали применяться средства и возможности параллельного программирования. Широко известны модели программирования в общей и распределенной памяти, позднее к ним прибавились гибридные модели. Однако все упомянутые средства относятся к достаточно низкоуровневому программированию, когда производится значительная переделка исходного кода. Немалое число математических расчетов выполняется не на алгоритмических языках (C/C++, Fortran), а в специализированных математических пакетах MATLAB, Maple, Mathematica, MathCad. В работе рассмотрены средства параллельного программирования в современных математических пакетах. Приведен краткий обзор развития средств параллельного программирования в широко распространенных пакетах MATLAB, Maple, Mathematica и MathCad. Для MATLAB кратко описываются основные примитивы параллельного программирования и их соответствия в среде MPI, а также приводятся другие операторы параллельного программирования. Рассматриваются различные средства обеспечения параллелизма в пакете Maple (работа с нитями, высокоуровневыми абстракциями Task Programming Model, параллельное программирование). Для Mathematica приводятся некоторые базовые конструкции параллельного программирования, имеющиеся в языке Mathematica Wolfram Language. Рассматриваются различные примеры. В зависимости от того, в каком пакете происходит работа, доступны несколько отличающиеся возможности, однако любая задача может быть решена в каждом из рассматриваемых пакетов (за исключением MathCad).
Authors: Chernetsov A.M. (an@ccas.ru) - Dorodnicyn Computing Centre FRC CSC RAS, National Research University “MPEI” (Research Associate, Associate Professor), Moscow, Russia, Ph.D
Keywords: wstp, MPI, mathematical suites, parallel programming
Page views: 11867
Print version
Full issue in PDF (7.11Mb)
Download the cover in PDF (0.37Мб)

Font size:       Font:

В последние годы для решения множества трудновычислимых задач стали применяться методы и средства параллельного программирования. Широко известны модели программирования в общей и распределенной памяти [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

Команда MATLAB

Функция MPI

Numlabs

MPI_Comm_size(size)

Labindex

MPI_Comm_rank(rank, MPI_COMM_WORLD)

LabBarrier()

MPI_Barrier(MPI_COMM_WORLD)

Shared_data=LabBroadcast(root, buffer)

MPI_Bcast(void *buffer, int count, MPI_Datatype datatype, int root, MPI_COMM_WORLD)

LabSend(buf,dest) LabSend(data,dest,tag)

MPI_Send(void *buf, int count, int tag, MPI_COMM_WORLD)

data=LabReceive(source,tag),

data=LabReceive('any',tag)

MPI_Recv(void *buf, int count, int source, int tag, MPI_COMM_WORLD, MPI_Status *status)

is_data_available= =LabProbe(source,tag)

MPI_Probe(int source, int tag, MPI_COMM_WORLD, MPI_Status *status)

Как видим, пакет реализует базовый набор директив для параллельного программирования. Опишем реализацию параллельного алгоритма умножения матрицы на вектор 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), которые средой распределяются на все доступные ресурсы процессоров. Каждая подзадача – это вызов функции, который выполняется отдельной нитью.

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

cont := proc(a, b)    return a + b; end proc; task := proc(i, j)    local k;    if (j-i < 1000) then        return add(k, k=i..j);    else        k := floor( (j-i)/2 )+i;        Threads:-Task:-Continue( cont, Task=[task, i, k], Task=[task, k+1, j]);    end if; end proc; Threads:-Task:-Start(task, 1, 10^8);

Команда 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

Функция Maple

Функция MPI

NumNodes()

MPI_Comm_size(size)

MyNode()

MPI_Comm_rank(rank, MPI_COMM_WORLD)

Barrier()

MPI_Barrier(MPI_COMM_WORLD)

Set(node,v1, v2, ...)

int MPI_Scatter(void *sendbuf, int sendcount, MPI_Datatype sendtype, void *recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_COMM_WORLD)

int root, MPI_COMM_WORLD)

Send( node, msg)

MPI_Send(void *buf, int count, int tag, MPI_COMM_WORLD)

Receive()

Receive(node) – получить от конкретного узла

MPI_Recv(void *buf, int count, MPI_COMM_WORLD, MPI_Status *status)

Средства параллельного программирования в 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

Функция Mathematica

Смысл

$KernelCount

Число ядер для параллельного вычисления

$KernelId

Уникальный номер (ID) параллельного вычисления

SetSharedVariable [s1, s2, …]

Установить символы si как общие переменные, чьи значения синхронизированы во всех ядрах

WaitAll[{pid1, pid2, …}]

Дождаться, пока все параллельные вычисления не будут завершены

ParallelSubmit[{var1, var2, …}, expr]

Посылает expr на вычисление следующим доступным параллельным ядром

ParallelTable[expr, {i, imax}]

Создает параллельно список значений expr, когда i в диапазоне от 1 до imax

ParallelEva- luate[expr, kernel]

Вычислить expr на заданном параллельном kernel

Parallelize[expr]

Вычислить expr, используя автоматическое распараллеливание

ParallelDo [expr, {i, imin, imax}] 

Вычислить expr параллельно, начиная с i=imin и до i=imax

DistributeDefinitions[s1, s2, …]

Распространить определения символов si на все параллельные ядра

CUDAFunctionLoad

Загрузить CUDA-функцию в пакет и сделать доступной для языка Wolfram

OpenCLFunctionLoad

Загрузить функцию OpenCL в пакет

Для иллюстрации приведем реализацию решения задачи нахождения списка чисел 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 с.


Permanent link:
http://swsys.ru/index.php?page=article&id=4140&lang=en
Print version
Full issue in PDF (7.11Mb)
Download the cover in PDF (0.37Мб)
The article was published in issue no. № 2, 2016 [ pp. 5-10 ]

Perhaps, you might be interested in the following articles of similar topics: