WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 |
М.В. Якобовский Е.Ю. Кулькова РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ Москва 2004 - 2 УДК 681.324.012:519.6 Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.:

Станкин, 2004.- 30 с.

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

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

Объем – 2 а.л.

© Станкин, 2004 - 3 Введение На примере задачи вычисления определенного интеграла от аналитически заданной функции рассматриваются алгоритмы, минимизирующие время решения задачи на многопроцессорной вычислительной системе. Их использование обеспечивает снижение времени решения задачи относительно «наилучшего» доступного последовательного алгоритма. Определение эффективности параллельного алгоритма относительно собственной же последовательной версии, как правило, не корректно. Обладающий высокой эффективностью параллельный алгоритм может по времени выполнения проигрывать лучшему из доступных последовательных алгоритмов решения той же задачи. Далее рассматриваются алгоритмы, минимизирующие именно время решения задачи, оперирующей относительно небольшим объемом данных. Применяемые подходы могут быть полезны при решении широкого круга проблем.

Интегрирование одномерной функции на многопроцессорной системе с общей памятью В качестве модельной задачи рассматривается проблема вычисления с точностью значение определенного интеграла (1):

B J(A, B) = f (x)dx,(1) A Пусть на отрезке [A,B] задана равномерная сетка, содержащая n+1 узел:

B - A xi = A + i, i = 0,,n n (2) Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции f (x) на отрезке [A,B]:

n-B - A f (x0 ) f (xn ) Jn(A, B)= + f (xi )+ (3) i=n 2 Будем полагать значение J найденным с точностью, если выполнено условие (4):

Jn1 - Jn2 Jn2, n1 > n2,(4) - 4 где n1 и n2 - количество узлов, образующих две разные сетки.

Последовательные алгоритмы Метод трапеций Рассмотрим алгоритм, реализующий метод трапеций:

IntTrap01(A,B) { n=J2n=(f(A)+f(B))(B-A)/do { Jn= J2n n=2n s=f(A)+f(B) for(i=1;i

J2n=s(B-A)/n;

} while(|J2n- Jn| J2n) return J2n } Алг. 1. Последовательный алгоритм "метод трапеций" Алгоритм 1 неэффективен в силу ряда причин, среди которых выделим две:

1. в некоторых точках значение подынтегральной функции вычисляется более одного раза. Например, в точке A функция будет вычислена k раз, где k - число выполнений цикла do - while;

2. на всем интервале интегрирования используется равномерная сетка, тогда как число узлов сетки на единицу длины на разных участках интервала интегрирования, необходимое для достижения заданной точности, зависит от вида функции f (x). Например, число точек, необходимых для достижения заданной точности при определении интеграла (6) возрастает при A 0, несмотря на уменьшения длины отрезка интегрирования (рис. 1, таб. 1).

Модифицируем алгоритм, с тем что бы избежать указанных недостатков.

- 5 Метод рекурсивного деления В дальнейшем будем рассматривать интегрирование функции (5), вид которой приведен на Рис. 1:

1 f (x)= sin2, 0 < A << 1 (5) x2 x Точное значение интеграла (1) от функции (5) дается выражением (6):

B B 1 1 1 1 J(A, B) = sin2 dx = - + sin x2 x 2x 4 x A A 1 B - A 2 J(A, B) = 2 + sin - sin (6) 4 AB B A 0.02 0.03 0.04 0.Рис. 1. График f(x) Таблица Результаты вычисления интеграла на разных отрезках A B Npoints eps real time, c 0.00001 0.0001 1 553 568 289 -2.77E-11 434.0.0001 0.001 1 726 123 903 1.90E-10 470.0.001 0.01 360 075 831 2.05E-11 74.0.01 0.1 79 973 845 -2.22E-12 16.0.1 1 105 108 653 8.67E-11 21.1 10 396 149 -6.00E-11 0.10 100 412 331 -6.30E-11 0.Как уже было указано, использование для вычислений непосредственно метода трапеций неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции. Построим алго - 6 ритм, свободный от указанного недостатка, для чего воспользуемся простым соотношением (7):

A + B J(A, B)= J(A,C)+ J(C, B), C = (7) Разобьем интервал интегрирования на две части и независимо проинтегрируем функцию f(x) на каждой из них, выбрав соответствующие шаги интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения (Алг. 2) достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования.

main() { J= IntTrap03(A,B,(f(A)+f(B))*(B-A)/2) } IntTrap03(A,B,fA,fB) { J=C=(A+B)/fC=f(C) sAB=(fA+fB)*(B-A)/sAC=(fA+fC)*(C-A)/sCB=(fC+fB)*(B-C)/sACB=sAC+sCB if(|sAB-sACB||sACB|) J= IntTrap03(A,C,fA,fC)+ IntTrap03(C,B,fC,fB) else J= sACB return J } Алг. 2. Последовательный алгоритм "рекурсивного деления" При наличии достаточного количества процессоров и нулевого времени порождения параллельных процессов можно было бы непосредственно запускать пары подпрограмм IntTrap03 для обработки половинок разбиваемого интервала. Но, поскольку в реальной системе число процессоров ограничено и время, необходимое для порож - 7 дения параллельных процессов существенно не равно нулю, такой подход неэффективен. Запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Следует разработать метод, позволяющий распределить вычислительную работу между ограниченным числом процессов. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса (они попадают туда в момент вызова процедуры IntTrap03) и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы.



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

Стек выбран исключительно из соображений простоты реализации.

Следует отметить, что в процедурах Алг. 4 для сокращения текста программ опущен код, обеспечивающий контроль переполнения и исчерпания стека.

Метод локального стека IntTrap04(A,B) { J=fA=f(A) fB=f(B) sAB=(fA+fB)*(B-A)/while(1) { C=(A+B)/fC=fun(C) sAC=(fA+fC)*(C-A)/sCB=(fC+fB)*(B-C)/sACB=sAC+sCB if(|sAB-sACB||sACB|) { PUT_INTO_STACK( A, C, fA, fC, sAC) A=C fA=fC sAB=sCB - 8 } else { J+=sACB if(STACK_IS_NOT_FREE) break GET_FROM_STACK( A, B, fA, fB, sAB) } } return J } Алг. 3. Метод локального стека // данные, описывающие стек sp=0 // указатель вершины стека struct { A,B,fA,fB,s } stk[1000] // массив структур в которых // хранятся отложенные задания // макроопределения доступа к данным стека #define STACK_IS_NOT_FREE (sp>0) #define PUT_INTO_STACK(A,B,fA,fB,s) { stk[sp].A=A stk[sp].B=B stk[sp].fA=fA stk[sp].fB=fB stk[sp].s=s sp++ } #define GET_FROM_STACK(A,B,fA,fB,s) { sp-A=stk[sp].A B=stk[sp].B fA=stk[sp].fA fB=stk[sp].fB s=stk[sp].s } Алг. 4. Процедуры доступа к локальному стеку Времена выполнения алгоритмов 2 и 3 отличаются примерно на 5% в пользу последнего, таким образом, алгоритм "локального стека" будет в дальнейшем использоваться в качестве наилучшего из имеющихся в нашем распоряжении последовательных методов. Именно относительно алгоритма 3 будет оцениваться эффективность создаваемых параллельных алгоритмов.

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

Метод геометрического параллелизма Согласно методу геометрического параллелизма отрезок интегрирования разбивается на p частей, где p - число используемых процессоров. Далее, каждому из процессоров предоставляется обработка одного из интервалов, причем разные процессоры вычисляют значения интеграла на разных интервалах. Рассмотрим соответствующий параллельный алгоритм 5.

main() { … for(i=0;i

Алгоритм 5 эффективен при условии равномерного распределения всего объема вычислений по отрезку интегрирования. Однако существует множество функций при интегрировании которых указанное условие не соблюдается. В их числе рассматриваемая нами на отрезке [10-5,1] функция 5. При разбиении интервала [10-5,1] на p равных частей практически весь объем вычислений, необходимых для опре - 10 деления интеграла с точностью =10-5, сосредоточен в первой части:

1-10--.

10, 10-5 + p Таблица Параметры расчета интеграла на разных отрезках p интервал 1 интервал2 время1, с время2, с 10 [1e-5, 0.10000900000] [0.10000900000, 1] 37.679 0.100 [1e-5, 0.01000990000] [0.01000990000, 1] 37.274 0.1 000 [1e-5, 0.00100999000] [0.00100999000, 1] 36.989 0.10 000 [1e-5, 0.00010999900] [0.00010999900, 1] 34.064 3.100 000 [1e-5, 0.00001999990] [0.00001999990, 1] 18.869 18.Из таблицы 2 следует полная непригодность метода геометрического параллелизма для решения поставленной задачи даже на системе из двух процессоров. При разбиении на две равные части, на первую из них приходится практически вся вычислительная нагрузка.

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





Метод коллективного решения Из таблицы 2 так же следует неприменимость и метода коллективного решения (Алг. 6).

main() { // управляющий процесс // Предполагается, что число интервалов n не меньше числа процессоров p:

// np // Порождение p параллельных процессов, каждый из которых // выполняет процедуру slave for(k=0;k

n T1 = i,(8) i=где i - время интегрирования отрезка i.

Время выполнения параллельного алгоритма:

n Tp = + 2ts),(9) (i p i=где ts - время передачи координат [a,b] или время возврата результата вычислений s. Поскольку объем передаваемых данных и в первом и во втором случае мал, правомерно считать времена их передачи одинаковыми и равными латентности.

Соотношение (9) предполагает, что время интегрирования на каждом из n интервалов одинаково: i = 0. В этом случае эффективность составит:

- 12 n 0 Ep = = = (10) 1 2ts + 2ts 1+ p n( + 2ts ) p Согласно (10) эффективность близка к 100% при соблюдении условия 0 >> 2ts и при равенстве времен обработки разных фрагментов интервала интегрирования. Данные таблицы 2 свидетельствует об обратном: при равной длине фрагментов отрезка интегрирования, требуется разное время для обработки каждого из них. В связи с этим соотношение (9) преобразуется следующем образом:

' Tp = max (i + 2ts ), p iI p где Ip - множество номеров отрезков, обработанных процессом p.

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

- параллельный алгоритм выполнит в целом больше операций, чем последовательный;

- соотношение i >> 2ts не выполняется для большинства из этих отрезков, поскольку среди отрезков есть такие, на которых интеграл можно с достаточной точностью найти без измельчения сетки, что требует времени значительно меньше, чем необходимо для синхронизации (передачи данных).

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

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

Метод глобального стека не требует наличия управляющего процесса. Процесс, выполняющий запуск расчета, никаким образом не участвует ни в самой процедуре расчета, ни в принятии решения об окончании вычислений. В этом принципиальное отличие метода глобального стека от метода коллективного решения: порожденные процессы совершенно равноправны в своих возможностях и каждый из них в равной степени выполняет вычислительные и управляющие функции. Укрупненная блок-схема алгоритма приведена на Рис. 2.

- 13 Инициализация данных Вычисления Порождение p параллельных процессов Процесс 1 Процесс 2 Процесс 3 Процесс p Ожидание завершения выполнения запущенных процессов Завершение работы Рис. 2. График f(x) Основные вычисления выполняются параллельными процессами Процесс1 … Процессp, каждый из которых выполняет один и тот же алгоритм.

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

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

Пока в глобальном стеке есть отрезки:

- взять один отрезок из глобального стека - выполнить алгоритм локального стека (Алг. 3), выполняя при записи в локальный стек следующие действия:

- 14 - если в локальном стеке есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то - переместить часть отрезков из локального стека в глобальный стек.

- по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

Pages:     || 2 | 3 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.