Стронгин Р.Г (ред.) Высокопроизводительные параллельные вычисления на кластерных системах

Подождите немного. Документ загружается.

271

перегиба. Все описанные действия повторяются до тех пор, пока новая

точка перегиба не будет отстоять от предыдущей точки более чем на

единицу (одно вычислительное устройство). Таким образом, будет

определено количество процессорных элементов, при котором время

решения задачи наименьшее, с погрешностью в один процессорный

элемент.

Эффективность использования предложенной методики

Для проверки эффективности использования предложенной

методики была выбрана задача решения систем уравнений методом

Гаусса-Жордана.

Результаты экспериментов на четырёхпроцессорном кластере

Регионального центра суперкомпьютерных вычислений Пензенского

государственного университета (ПГУ) и сетевом многомашинном

комплексе Института информатики и вычислительной техники ПГУ

[3] подтверждают эффективность использования систем кластерного

типа для задачи решения систем уравнений, реализованных

вложенными циклическими конструкциями. Результаты

экспериментов на высокопроизводительном 24-процессорном кластере

научно-исследовательского вычислительного центра Московского

государственного университета [3] подтверждают существование

такого количества процессорных элементов, при котором время

решения систем уравнений минимальное.

С использованием предложенной методики по результатам ряда

экспериментов было определено количество вычислительных

устройств, необходимых для решения задачи определённой

трудоёмкости (количество операций, необходимых

для решения

системы уравнений некоторой размерности) за минимальное время.

Для нескольких задач решения систем уравнений оптимальное

количество устройств было найдено последовательным приближением

за 4-5 шагов. Оно совпало с экспериментальными данными [3]. Для

задачи решения системы уравнений, состоящей из 1024 уравнений,

методом Гаусса-Жордана за минимально возможное время

необходимо пятнадцать вычислительных устройств, при этом

время

решения системы сокращается в 10 раз.

Использование предложенной методики при проектировании и

построении кластерных систем для решения конкретных прикладных

задач позволяет определить необходимый объём вычислительных

ресурсов с целью максимально эффективного их использования.

272

Литература

1. Андреев А., Воеводин Вл., Жуматий С. Кластеры и

суперкомпьютеры – близнецы или братья? // Открытые

системы. – 2000. – № 5–6. – С. 9–14.

Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. –

СПб.: БХВ-Петербург, 2004. – 608 с.: ил.

Мялицин В.В., Шашков Б.Д. Эффективность параллельной

реализации алгоритмов помехоустойчивого кодирования

Рида-Соломона // Прикладная информатика. – 2006. – № 3. –

С. 120–129.

ИНТЕГРИРОВАННАЯ СРЕДА СОЗДАНИЯ ПАРАЛЛЕЛЬНЫХ

ПРОГРАММ НА ЯЗЫКЕ СВЕРХВЫСОКОГО УРОВНЯ НОРМА

Д.В. Осипов

МГУПИ, Москва

На данный момент предложено множество способов разработки

параллельных программ (ПП), но все они требуют в той или иной

степени достаточно сложной и трудоемкой работы опытного

программиста. Также не оправдываются надежды на эффективное

распараллеливание последовательных программ, несмотря на

постоянно проводимые исследования в области нахождения скрытого

параллелизма в алгоритмах.

Давно муссируется

мысль, что при создании новых ПП не только

нецелесообразно, но и, пожалуй, даже вредно сначала создавать

последовательную версию программы. Такой подход может быть

реализован использованием функциональных языков

программирования (напр., известный язык Haskell). В ИПМ

им.М.В.Келдыша РАН с 60-х гг. ведется работа над языком НОРМА,

предназначенным для решений задач

моделирования сеточными

методами [1].

Язык НОРМА называют декларативным (описательным)

вследствие упора именно на описание правил вычисления значений,

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

НОРМА-исходного текста синтезируется исходный текст программы в

традиционной системе параллельного программирования (напр., MPI с

использованием Fortran’а или C/C++), далее компиляция и

редактирование связей [2].

273

Однако для создания НОРМА-программы классическим методом

все же требуется программист, знакомый с правилами языка и

формально “набивающий” текст программы. Вышеуказанные

особенности языка НОРМА наводят на мысль о еще большем

упрощении последовательности создания параллельных программ.

Логично будет максимально далеко уйти от текстового представления

программы и снабдить язык НОРМА интерактивной оболочкой,

которая будет являться как удобным интерфейсом для написания

параллельных программ, значительно уменьшающим временные

затраты прикладного специалиста на описание своей задачи в

терминах НОРМА, и в то же время автоматической проверкой на

синтаксические ошибки программирования [3].

Разрабатываемая система получила название «Интерактивная

НОРМА» (далее ИН) и выполнена в виде web-сайта на технологии

PHP (в

целях достижения платформенной независимости); одно из

интерфейсных окон ИН см. на рис.1. Работа с интерактивной средой

создания НОРМА-программ, конечно, требует от разработчика

определенных навыков работы с ЭВМ, однако нет необходимости

усвоения полного синтаксиса этого языка программирования, наличие

шаблонов программного кода еще более упрощает работу.

ИН поможет пользователям сгенерировать их первые

параллельные программы и не отнимет много времени на изучение

различных языков программирования. Все, что требуется от

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

программа на языке НОРМА. Плюсом является то, что в

«Интерактивной НОРМЕ» присутствуют автоматизированные

стандартные методы создания программ, которые являются заранее

отлаженными методами программирования. За счет

чего,

пользователь, даже начинающий, не допустит ошибок в тексте

программы (а вместе с тем не потратит время на поиски этих ошибок)

и в то же время сможет получить априори работоспособный код

программы.

При создании параллельной программы с помощью интерактивной

среды необходимо советовать пользователю наилучший выбор

распределения его данных и вычислений

по процессорам. Это связано

прежде всего с тем, что при работе с матрицами в языках

программирования

C и Fortran, в которые компилируется НОРМА

программа, данные в оперативной памяти сохраняются по-разному. В

языке

Fortran они располагаются последовательно в оперативной

274

памяти по столбцам, а в

C по строкам. При нерациональном

распределении данных по процессорам параллельная программа будет

выполняться дольше, чем при правильном распределении (эффект

кэширования). И соответственно, что для пользователя (особенно для

начинающего) эти советы будут очень полезны. Также важно знать,

что в языке НОРМА каждый раздел программы можно

распараллеливать единожды и что в каждом разделе

может

присутствовать несколько областей вычисления. ИН должна

проанализировать, по каким областям будет выгоднее распределить

данные и вычисления. Выполнив вышеприведенные действия, мы

практически можем гарантировать наилучшее (в смысле достижения

максимальной скорости) выполнение нашей будущей параллельной

программы. Конечно, пользователь может выбрать и другое

распределение данных в этом разделе, но предлагаемый метод

значительно упрощает

операцию распределения данных по

процессорам и освобождает пользователя от излишних временных

затрат для расчета нагрузки распределяемых данных.

Согласно синтаксису НОРМА распределение данных и

вычислений по процессорам определяется инструкцией описания

индексов распределения вида

DISTRIBUTION INDEX (формально

постулируется использование двумерной решетки процессоров). Это

описание приводит к распределению между процессорными

элементами, как данных, так и управления и автоматической

генерации операторов обмена данными между ними. Распределению

подлежат величины, участвующие в расчетах и имеющие индексы,

совпадающие с указанными в описании. Например, если задано

описание

DISTRIBUTION INDEX i=1..12, j=1. , то все переменные,

определенные на областях с индексами

i и j, будут распределены по

процессорным элементам

(i,j) с виртуальными номерами строк i=1..12

в столбце с номером

j=1 матрицы процессорных элементов. Заметим,

что в современной реализации языка НОРМА допускается фактически

только одномерная топология сетевого объединения процессоров

(один из индексов двумерной матрицы процессоров должен быть

равен 1).

Приведем пример использования ИН на задаче создания ПП по

умножению матриц. Матрица A размером (i

k) умножается на

матрицу B размером (k

j), результатом становится матрица C

размерностью (i

j).

275

Формула для вычисления произведения матриц выглядит

следующим образом (умножение матриц по классической схеме):

∑

ikij

В этом простом примере наиболее загруженное направление

соответствует направлению индекса (k), и, следовательно, по данному

направлению целесообразно распределить данные и вычисления.

Наиболее загруженным направлением можно назвать направление,

соответствующее индексу цикла максимальной вложенности в

рассматриваемом гнезде циклов. При использовании языка С/C++

направление (k) должно соответствовать строкам в оперативной

памяти.

В ИН распределение данных

и вычислений по процессорам

происходит в пункте меню «Разделы программы», в данном разделе

выбирается «Задать решетку процессоров» и в появившемся окне

задаются индексные направления, по которым следует распределять

данные и вычисления, а уже в следующем окне непосредственно

задается количество процессоров по каждому индексному

направлению:

Рис. 1. Пример задания распределения данных по процессорам в

«Интерактивной Норме»

В результате наших действий в ИН сформированная программа на

языке НОРМА будет выглядеть так:

MAIN PART Listing.

BEGIN

Oi: (i=1..300).

Oj: (j=1..200).

Ok: (k=1..100).

OA: (Oi;Ok).

OB: (Ok; Oj).

OC: (Oi; Oj).

276

VARIABLE a DEFINED ON OA DOUBLE.

VARIABLE b DEFINED ON OB DOUBLE.

VARIABLE c DEFINED ON OC DOUBLE.

FOR OA ASSUME a = ( i – 1 ) + ( k – 1 ).

FOR OB ASSUME b = ( k – 1) + ( j – 1).

COMPUTE Matrix(a ON OA, b ON OB RESULT c ON OC).

OUTPUT c(FILE='pmatrix.out') ON OC.

END PART.

PART Matrix.

a, b RESULT c

BEGIN

Oi: (i=1..300).

Oj: (j=1..200).

Ok: (k=1..100).

OA: (Oi;Ok).

OB: (Ok; Oj).

OC: (Oi; Oj).

VARIABLE a DEFINED ON OA DOUBLE.

VARIABLE b DEFINED ON OB DOUBLE.

VARIABLE c DEFINED ON OC DOUBLE.

FOR OC ASSUME c = SUM((Ok) a[i,k] * b[k,j]).

DISTRIBUTION INDEX k=1..4, j=1.

END PART.

В этом случае при вычислении произведения матриц НОРМА-

инструкцией c=SUM((Ok) a[i,k]*b[k,j]). Данные и вычисления будут

распределены по процессорным элементам

(k,j) с виртуальными

номерами строк

k=1..4 в столбце с номером j=1 матрицы

процессорных элементов.

Правильность выбора данного распределения доказывают

проведенные опыты, в которых при распределении данных на 4

процессора (линейная топологии связей) матриц размером 1000

1000

по направлению (k), для языка C с MPI-вызовами, было зафиксировано

наименьшее время выполнения программы. При распределении

данных по другим индексным направлениям, время выполнения

программы увеличивалось более чем в 2 раза, что доказывает

правильность выбора лучшего варианта распределения данных. Как

уже было показано выше, этот эффект связан с распределением

данных в оперативной памяти для

различных языков

программирования, рационального использования эффекта

кэширования и с распараллеливанием наиболее нагруженного

направления рассчитываемого раздела программы.

277

Данный пример примитивно прост и нагляден, и при

распределении данных можно было бы не задействовать компьютер,

чтобы определить рациональное индексное направление. В более

сложных случаях сама система ИН самостоятельно (на основе анализа

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

быстродействия) индексное направление.

Система «Интерактивная НОРМА» в настоящее время

применяется при проведении

лабораторного практикума по

дисциплине “Параллельное программирование” на кафедре ИТ-4

“Персональные компьютеры и сети” Московского государственного

университета приборостроения и информатики (МГУПИ).

Литература

1. Задыхайло И.Б. Организация циклического процесса счета по

параметрической записи специального вида. // ЖВМ и МФ,

т.3. № 2. —M.: 1963, c.337

Андрианов А.Н., Бугеря А.Б., Ефимкин К.Н., Задыхайло И.Б.

Норма. Описание языка. Рабочий стандарт. // Препринт ИПМ

им. М.В.Келдыша РАН, № 120, —M.: 1995, -50 с.

Лацис А.О. Как построить и использовать суперкомпьютер. —

M.: Бестселлер. 2003, -240 c.

ПОДХОДЫ К РАСПАРАЛЛЕЛИВАНИЮ АЛГОРИТМА

ВОЗВЕДЕНИЯ ДЛИННЫХ ЧИСЕЛ В СТЕПЕНЬ ПО МОДУЛЮ

ДЛЯ КРИПТОГРАФИЧЕСКИХ СИСТЕМ

П.Н. Полежаев, М.Ю. Нестеренко

Оренбургский государственный университет

Введение

В современном мире большое значение имеет защита информации,

передаваемой по открытым каналам связи. В этом случае применяют

различные криптографические схемы шифрования.

В связи с широким распространением многоядерных процессоров

и необходимостью использования затратных по времени, но

криптостойких криптографических систем для защиты информации,

возникает необходимость распараллеливания последних для систем с

общей памятью.

278

Перечислим основные подходы к распараллеливанию

асимметричных криптосистем:

Распараллеливание на уровне реализации длинной

арифметики (распараллеливание арифметических операций

для CRT-представления длинных чисел).

Распараллеливание на уровне реализации методов

шифрования, дешифрования и генерации ключей

(распараллеливание трудоемкого алгоритма возведения в

степень по модулю, алгоритма генерации псевдослучайных

чисел).

Распараллеливание на уровне блоков шифртекста

(распараллеливание по независимым блокам).

Операция возведения длинных чисел в степень по модулю

является фундаментальной, т.к. используется во многих

криптографических системах (RSA, Эль-Гамаля, Диффи-Хеллмана) и

других областях криптологии (алгоритмы проверки чисел на простоту,

алгоритмы факторизации и дискретного логарифмирования), алгебры

и теории чисел.

Данная операция

является очень трудоемкой по времени, и

поэтому именно ее имеет смысл распараллелить, что и было сделано в

данной работе.

Бинарный метод возведения в степень по модулю и варианты

его распараллеливания

В источниках [1, 2] приводится обзор последовательных

алгоритмов возведения в степень по модулю, а также выполняется

анализ возможности разработки их параллельных версий. Наиболее

подходящими для распараллеливания являются – бинарный и

арный (как его обобщение) алгоритмы.

Пусть необходимо вычислить

mbr

mod=

, (1)

для чисел

длины k бит.

Пусть

0011

2...22...

−

−−

+++==

ppppppp

- представление

показателя степени в двоичной системе счисления (

}1,0{

∈

), тогда

формула (1) примет вид:

279

mmmb

mmmbmmbmb

mod))mod)mod...((

)...mod))mod)mod)((mod)mod(...((((mod

−

(2)

Бинарный метод заключается в последовательном возведении в

квадрат основания для вычисления

mmb

mod)mod(

и умножения

результата на полученное значение при всех

Данный метод может быть распараллелен несколькими способами.

Первый способ распараллеливания заключается в

последовательном вычислении всех значений

mmb

mod)mod(

(

1...,,1,0 −= kj

), а затем – параллельное умножение по модулю m

всех полученных значений, для которых

, с помощью

каскадной схемы умножения. Очевидно, что основным недостатком

данного алгоритма является большая доля последовательных

вычислений (оценку времени см. в таблице 1).

Второй вариант распараллеливания предлагает на каждой

итерации цикла, проходящего по всем битам показателя степени

(

1...,,1,0 −= kj

), вычисление очередного

mmmbmmb

mod)mod)mod((mod)mod(

222

выполнять

параллельно с умножением по модулю результата на

mmb

mod)mod(

при

. Основной недостаток – дисбаланс

загрузки ядер процессоров. Так как в среднем число единичных бит

показателя степени составляет половину его длины, то в половине

случаев у потока, выполняющего умножение результата на очередную

степень основания, не будет работы, и он будет ожидать другой поток

для перехода к следующей итерации цикла. Также данный вариант

распараллеливания не масштабируется.

Рассмотрим

третий вариант распараллеливания.

Пусть необходимо вычислить (1), причем

, где

простые числа. Последнее условие всегда выполняется, например, для

алгоритмов шифрования и дешифрования криптосистемы RSA. Также

возможно обобщение, если модуль удается представить в виде

произведения двух и более попарно взаимно простых чисел.

Любое число

]1,0[

−

∈

может быть однозначно представлено

своими остатками от деления на

/2/:

),( wqx =

, где

)(mod rxq

≡

)(mod txw

≡

. (3)

280

Представление (3) называется (

q,w)-представлением числа x,

представлением в остатках или CRT-представлением.

Операции сложения, вычитания и умножения чисел,

представленных в остатках, могут выполняться покомпонентно.

Таким образом, если требуется производить большое количество

умножений по модулю, как в алгоритме возведения в степень, то

можно использовать умножение в остатках. Во-первых, оно в силу

независимости компонент позволяет выполнять операцию

параллельно.

Во-вторых, т.к. нахождение представления в остатках

можно выполнить в самом начале и восстановить результат в конце, то

можно получить приблизительно хорошее ускорение работы

алгоритма без учета распараллеливания.

Основным недостатком данного алгоритма является отсутствие

масштабируемости.

Анализ параллельных алгоритмов возведения в степень по

модулю

По таблице 1 видно, что лучшую временную сложность имеет

бинарный метод с параллельными вычислениями для (

q,w)-

представления чисел.

Для оценки ускорения и эффективности параллельных

алгоритмов возведения в степень по модулю были созданы их

программные реализации, распараллеливание осуществлялось с

помощью OpenMP 2.0. Замеры времени работы производились с

помощью Intel VTune Performance Analyzer.

На рисунке 1 приведен график зависимости ускорений

параллельных алгоритмов от длины в битах. По графикам видно, что

наилучшее ускорение имеет бинарный метод

с параллельными

вычислениями для (

q,w)-представления чисел, которое асимптотически

приближается к теоретическому пределу 2.