енных градиентов (CG),
• обобщенный метод минимальных невязок (GMRES),
• квадратичный метод сопряженных градиентов (CGS),
• метод квазиминимальных невязок (TFQMR),
• метод бисопряженного градиента (BiCGSTAB) со стабилизацией
При решении СЛАУ используются как прямой метод LU, так и неполное
LU-разложение в подобластях. Матрица системы может быть как общего ви- да, так и специального, возникающего при конечно-разностной аппроксима- ции дифференциальных уравнений в частных производных (PDE - Partial
Differential Equations). Руководство по использованию AZTEC может быть получено с адреса http://rsusu1.rnd.runnet.ru/ncube/aztec/index.html.
Библиотека ScaLAPACK (Scalable LAPACK, http://www.netlib.org/ scalapack/index.html
) ориентирована на решение задач линейной алгебры c матрицами общего вида. ScaLAPAC является расширением известной биб- лиотеки LAPACK (как считается, наиболее полно отвечающей архитектуре современных процессоров – напр., библиотечные подпрограммы оптимизи- рованы для эффективного использования кэш-памяти и т.п.) на многопроцес- сорную архитектуру.
Пакет ScaLAPACK фактически является стандартом в программном обес- печении многопроцессорных систем. В нем почти полностью сохранены со- став и структура пакета LAPACK и практически не изменились обращения к
- 113 - подпрограммам верхнего уровня. В основе успеха реализации этого проекта лежали два принципиально важных решения: • В пакете LAPACK все элементарные векторные и м атричные операции выполняются с помощью высокооптимизированных подпрограмм биб- лиотеки BLAS ( Basic Linear Algebra Subprograms). По аналогии с этим при реализации ScaLAPACK была разработана параллельная версия этой библиотеки (названная PBLAS), что избавило от необходимости ради- кальным образом переписывать подпрограммы верхнего уровня. • Все коммуникационные операции выполняются с использованием под- программ из специально разработанной библиотеки BLACS ( Basic Linear Algebra Communication Subprograms), поэтому перенос пакета на различ- ные многопроцессорные платформы требует настройки только этой биб- лиотеки. Обозначенные как ‘глобальные’ компоненты пакета выполняются парал- лельно на заданном наборе процессоров и в качестве аргументов используют векторы и матрицы, распределенные по этим процессорам, подпрограммы из озн аченных как ‘локальные’ компонентов пакета вызы- ваются на одном процессоре и работают с локальными данными (рис.27). Имеется возможность работы с веще- ственными и комплексными данными одинарной или двойной точности, матрица- ми различного вида, выпол- нение факторизации, вычис- ление собственных значений и собственных векторов, оп- ределение сингулярных зна- чений и др.; руководство пользователя дост упно на адресе http://rsusu1.rnd.runnet.ru/ncube/scalapack/scalapack_home.html Из иных библиотечных пакетов следует указать Block Solve (решение СЛАУ с редкозаполненной матрицей системы, Argonne National Laboratory, http://www.mcs.anl.gov, http://www- unix.mcs.anl.gov/sumaa3d/BlockSolver ), разрабо- танную в математическом отделении университета Бата (Англия) библиоте- ку DOUG ( Domain On Unstructured Grids), позиционируемую как ‘параллель- ный решатель для систем, возникающих при решении методом конечных элементов’ ( http://www.math.bath.ac.uk/mjh/doug ) и некоторые другие. Рисунок 27 — Структура пакета ScaLAPACK - 114 - Практически все предметно-ориентированные библиотеки для решения за- дач матфизики бесплатны и дост упны в исходных кодах. 4.5 Параллелизм в системах управления базами данных Управление большими базами данных – естественное применение много- процессорных вычислительных систем. В списке Top500 25-й редакции (июнь 2005) приведены данные 16 инсталляций МВС для применений в об- ласти финансов, максимальной LINPACK-производительностью в 4713 GFlops обладает находящаяся на 62 месте система eServer BlueGene Solution (2048 процессоров фирмы IBM, поставленна для NIWS Co. Ltd, Япония в 2005 г.). В СберБанке РФ с 2003 г. эксплуатируется 256-процессорная SMP- система HP SuperDome с процессорами PA-RISK 750 MHz производительно- стью 440 Gflops. Параллельная система баз данных - это система управления базами данных (СУБД), реализованная на многопроцессорной системе с высокой степенью св язности. Под многопроцессорной системой с высокой степенью связности понимается система, включающую в себя много процессоров и много дисков, в которой процессоры объединены между собой с помощью некоторой соединительной сети, причем время обмена данными по сети сравнимо со временем обмена данными с диском. Приведенное опреде- ление исключает из рассмотрения распределенные СУБД, реализуемые на нескольких независимых компьютерах, объединенных локальной и/или глобальной сетями ( * ). Основная нагрузка в параллельной системе баз данных приходится на выполнение запросов к БД. Обычно рассматривают несколько путей рас- параллеливания запросов: ( ** ) • Горизонтальный параллелизм возникает при распределении хранящей- ся в БД информации по нескольким физическим устройствам (жестким дискам). При этом информация из одного соотношения разбивается на части по горизонтали (достигается сегментация данных), распараллели- вание заключается в выполнении одинаковых операций над разными физически хранимыми данными. Эти операции независимы и могут вы- полняться различными процессорами, конечный результат складывается из результатов выполнения отдельных операций (рис.28а). * Л.Б.Соколинский. Обзор архитектур параллельных систем баз данных. / ПРОГРАММИРОВАНИЕ, 2004, № 6, с. 49 ÷ 63. ** Т.С.Крюкова. Базы данных: модели, разработка, реализация. –CПб.: Питер, 2001. –304 c.
- 115 -
• Вертикальный параллелизм реализуется конвейерным способом вы- полнения cоставляющих запрос пользователя операций. При этом ядро
СУБД должно произвести декомпозицию запроса с целью выявления параллельно выполняющихся шагов запроса (рис.28б).
• Гибридный параллелизм предполагает совместное использование двух первых подходов (рис.28в).
Рисунок 28 — Укрупненная схема выполнение запроса при а) – горизонтальном, б) - вертикальном и в) - гибридном параллелизме.
- 116 - Классификация архитектур параллельных машин баз данных разрабо- тана в основном Стоунбрейкером ( M. Stonebraker, 1986). Далее классифика- ция была расширена Ерхардом Рамом ( E. Rahm, 1992) в сторо- ну гибридных архитектур и Копеландом ( Copeland, 1989) и Келлером ( Keller) в направ- ление иерархических архитек-тур. Автор работы ( * ) развив ает подход Копеланда и Келлера, ввод я и используя малоизу- ченную до сих пор альтерна- тивную трехуровневую иерар- хическую архитектуру, в осно- ве которой лежит понятие Омега-кластера. Эта архитек- тура (рис.29, ср. с рис.8в) предполагает наличие небольшого количества процессорных модулей PM и обслуживающего их модуля д исковой подсистемы DSM (последняя включает сопряженный с SCSI-шиной коммуникационный процессор, что дает воз- можность подключения до 7 дисковых накопителей) и является определен- ным продолжением и развитием идей проекта SDC ( Super Database Computer, суперкомпьютер баз данных) токийского университета ( ** ). Несколько Омега-кластеров могут объединяться в систему верхнего уров- ня через свободные л инки L процессорных модулей, топология межкластер- ных соединений может варьироваться от простой линейной до гиперкуба. Иерархическая архитектура системы Омега предполагает два уровня фраг- ментации. Каждое отношение может разделяться на фрагменты, размещае- мые в различных Омега-кластерах ( межкластерная фрагментация). В свою очередь, каждый такой фрагмент разделяется на более мелкие фрагменты, распределяемые по различным узлам Омега-кластера ( внутрикластерная фрагментация). Этот подход делает процесс балансировки загрузки более гибким, поскольку он может выполняться на двух уровнях - локальном, сре- ди процессорных модулей внутри Омега-кластера, и глобальном, среди Оме- га-кластеров. Описанная архитектура была реализована в прототипе парал- лельной СУБД Омега на базе МВС-100 в 8-процессорной конфигурации. *Л.Б.Соколинский. Проектирование и анализ архитектур параллельных машин баз дан- ных с высокой отказоустойчивостью. / Челябинский государственный университет. ** Hirano M.S. et al. Architecture of SDC, the super database computer. // In Proceedings of JSPP'90. 1990. Рисунок 29 — Схема Омега-кластера. - 117 - Предложенная в работе ( * ) классификация форм параллелизма обработки запросов в параллельных БД приведена на рис.30, несколько подробнее о возможных реализациях транзакций в распредел енных БД реляционного типа см. в работе [7]. Контрольные вопро-сы 1. В чем заключается проблема перенос имости параллельных программ? 2. В чем суть функционального программирования и отличие его от опера- торного? В чем заключаются недостатки первого и второго? 3. Что такое ‘ процесс, управляемый данными’? В чем отличие его от тради- ционного подхода к управлению вычислениями? Есть ли недостатки у процесса управления данными? 4. В чем выражается преимущество подхода ‘data flow’ и какими средствами оно может быть достигнуто? 5. Каковы основные принципы построения языков (систем) программирова- ния параллельных вычислений? 6. Какие принципы синхронизации независимо выполняющихся процессов известны? Для чего вообще необходима синхронизация? 7. Каким образом параллельная обработка данных применяется в технологии баз данных? Какие формы параллелизма при обработке транзакций извест- ны? * Соколинский Л.Б. Методы организации параллельных систем баз данных на вычисли- тельных системах с массовым параллелизмом. Диссертация на соискание ученой сте- пени доктора физико-математических наук: 05.13.18 // Челябинский государственный университет, -Челябинск: 2003, -247 c. Рисунок 30 — Классификация форм параллелизма при обработке транзакций в параллельных базах данных.
- 118 -
Заключение
Параллельные вычисления представляют собой целый куст смежных во- просов, включающих аппаратную поддержку, анализ структуры алгоритмов с цель выявления параллелизма и алгоритмические языки для программирова- ния параллельных задач. Технологии параллельных вычислений в настоящее время бурно развиваются в связи с требованиями мировой науки и техноло- гий.
Сегодняшняя проблема – явный недостаток аппаратных средств для парал- лельных вычислений в учебных и научных учреждениях, что не дает воз- можности всестороннего освоения соответствующих технологий; часто прак- тикуемое чисто теоретическое изучение предмета приводит скорее к нега- тивным (отчуждение от предмета из-за схоластичности подхода), чем к пози- тивным следствиям. Только сейчас появляются технологии, позволяющие ввести практику параллельных вычислений в большинство учебных и произ- водственных лабораторий.
Создание эффективных параллельных программ требует намного более серьезного и углубленного анализа структуры алгоритмов, нежели при тра- диционно-последовательном программировании, причем некоторые подходы невозможно реализовать без серьезного изменения мышления программи- стов. Наряду с теоретическим анализом для получения практически значи- мых результатов необходима постоянная практика в создании параллельных программ.
- 119 -
Список использованной литературы
1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. –СПб.: БХВ-
Петербург, 2004.
-
608 c.
2. Гарви М.Дейтел. Введение в операционные системы (пер. с англ.
Л.А.Теплицкого, А.Б.Ходулева, Вс.С.Штаркмана под редакцией Вс.С.
Штаркмана). –М.: Мир, 1987 (электронная версия http://www.deepweb.ru
,
2004)
3. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для много- процессорных вычислительных систем (учебное пособие, изд. 2, допол- ненное). -Н.Новгород.: изд. ННГУ им. Н.И.Лобачевского, –2003 (электрон- ная версия http://pilger.mgapi.edu/metods/1441/basic_pr.zip
).
4. Корнеев В.В. Вычислительные системы. -М.: Гелиос АРВ, –2004, -512 c.
5. Лацис А.О. Как построить и использовать суперкомпьютер. –M.: Бестсел- лер, 2003. –240 c.
6. Крюков В.А.. Разработка параллельных программ для вычислительных кластеров и сетей. // Информационные технологии и вычислительные сис- темы. –M.: № 1
÷
2, 2003, с.42
÷
61.
7. Шпаковский Г.И. Организация параллельных ЭВМ и суперскалярных процессоров. // Учеб. пособие. -Минск.: Белгосуниверситет, 1996. -296 с.
(электронная версия http://pilger.mgapi.edu/metods/1441/spakovsk.zip
)
8. Шпаковский Г.И., Серикова Н.В. Программирование для многопроцессор- ных систем в стандарте MPI. -Минск:, БГУ, 2002. -325 с.
(электронная версия http://www.cluster.bsu.by/download/book_PDF.pdf,
http://pilger.mgapi.edu/metods/1441/pos_mpi.pdf
)
9. Андрианов А.Н., Бугеря А.Б., Ефимкин К.Н., Задыхайло И.Б. Норма. Опи- сание языка. Рабочий стандарт. // Препринт ИПМ им.М.В.Келдыша РАН,
№ 120, 1995, -50 с.8.
10. Информационно-аналитические материалы по параллельным вычислени- ям (электронная версия http://parallel.ru
)
- 120 -
Приложение 1.
Примеры последовательной и параллельных реализаций алгоритма
Якоби решения сеточных уравнений (по материалам работы [6])
a) последовательная программа на языке Fortran’77
PROGRAM JAC_F77
PARAMETER (L=8, ITMAX=20)
REAL A(L,L), B(L,L)
PRINT *, '********** TEST_JACOBI **********'
DO IT = 1, ITMAX
DO J = 2, L-1
DO I = 2, L-1
A(I, J) = B(I, J)
ENDDO
ENDDO
DO J = 2, L-1
DO I = 2, L-1
B(I, J) = 0, 25
×
(A(I-1, J) + A(I, J-1) + A(I+1, J) + A(I, J+1))
ENDDO
ENDDO
ENDDO
END б) параллельная программа на языке HPF, цветом (насыщенностью) выделены HPF-предписания
PROGRAM JAC_HPF
PARAMETER (L=8, ITMAX=20)
REAL A(L,L), B(L,L)
!HPF$ PROCESSORS P(3,3)
!HPF$ DISTRIBUTE ( BLOCK, BLOCK) :: A
!HPF$ ALIGN B(I,J) WITH A(I,J)
C arrays A and B with block distribution
PRINT *, '********** TEST_JACOBI **********'
DO IT = 1, ITMAX
!HPF$ INDEPENDENT
DO J = 2, L-1
!HPF$ INDEPENDENT
DO I = 2, L-1
A(I, J) = B(I, J)
ENDDO
ENDDO
!HPF$ INDEPENDENT
DO J = 2, L-1
!HPF$ INDEPENDENT
DO I = 2, L-1
B(I, J) = (A(I-1, J) + A(I, J-1) + A(I+1, J) + A(I, J+1)) / 4
ENDDO
ENDDO
ENDDO
END в) параллельная программа на языке Fortran’DVM, цветом (насыщенностью) выделены DVM-директивы
PROGRAM JAC_DVM
PARAMETER (L=8, ITMAX=20)
REAL A(L,L), B(L,L)
- 121 -
СDVM$ DISTRIBUTE ( BLOCK, BLOCK) :: A
СDVM$ ALIGN B(I,J) WITH A(I,J)
С arrays A and B with block distribution
PRINT *, '********** TEST_JACOBI **********'
DO IT = 1, ITMAX
СDVM$ PARALLEL (J, I) ON A(I, J)
DO J = 2, L-1
DO I = 2, L-1
A(I, J) = B(I, J)
ENDDO
ENDDO
СDVM$ PARALLEL (J, I) ON B(I, J), SHADOW_RENEW (A)
С copying shadow elements of A-array from
С neighboring processors before loop execution
DO J = 2, L-1
DO I = 2, L-1
B(I, J) = (A( I-1, J ) + A( I, J-1 ) + A( I+1, J ) + A( I, J+1 )) / 4
ENDDO
ENDDO
ENDDO
END г) параллельная программа на языке Fortran с использованием MPI, цветом (насыщенностью) выделены относящиеся к MPI структуры
PROGRAM JAC_MPI include 'mpif.h' integer me, nprocs
PARAMETER (L=8, ITMAX=20, LC=2, LR=2)
REAL A(0:L/LR+1, 0:L/LC+1), B(L/LR,L/LC)
C arrays A and B with block distribution integer dim(2), coords(2) logical isper(2) integer status(
MPI_STATUS_SIZE
, 4), req(8),newcomm integer srow,lrow,nrow,scol,lcol,ncol integer pup,pdown,pleft,pright dim(1) = LR dim(2) = LC isper(1) = .false. isper(2) = .false. reor = .true. call MPI_Init(ierr) call MPI_Comm_rank(mpi_comm_world, me, ierr) call MPI_Comm_size(mpi_comm_world, nprocs, ierr) call MPI_Cart_create(mpi_comm_world,2,dim,isper, .true., newcomm, ierr) call MPI_Cart_shift(newcomm,0,1,pup,pdown, ierr) call MPI_Cart_shift(newcomm,1,1,pleft,pright, ierr) call MPI_Comm_rank (newcomm, me, ierr) call MPI_Cart_coords(newcomm,me,2,coords, ierr)
C rows of matrix I have to process srow = (coords(1) * L) / dim(1) lrow = (((coords(1) + 1) * L) / dim(1))-1 nrow = lrow - srow + 1
C colomns of matrix I have to process scol = (coords(2) * L) / dim(2) lcol = (((coords(2) + 1) * L) / dim(2))-1 ncol = lcol - scol + 1 call MPI_Type_vector(ncol,1,nrow+2,MPI_DOUBLE_PRECISION, vectype, ierr) call MPI_Type_commit(vectype, ierr)
IF (me. eq. 0) PRINT *, '***** TEST_JACOBI *******'
- 122 -
DO IT = 1, ITMAX
DO J = 1, ncol
DO I = 1, nrow
A(I, J) = B(I, J)
ENDDO
ENDDO
C Copying shadow elements of array A from
C neighboring processors before loop execution call MPI_Irecv(A(1,0),nrow,MPI_DOUBLE_PRECISION,pleft,1235,MPI_COMM_WORLD,req(1),ierr) call MPI_Isend(A(1,ncol),nrow,MPI_DOUBLE_PRECISION,pright,1235,MPI_COMM_WORLD,
+ req(2),ierr) call MPI_Irecv(A(1,ncol+1),nrow,MPI_DOUBLE_PRECISION,pright,1236,MPI_COMM_WORLD,
+ req(3),ierr) call MPI_Isend(A(1,1),nrow,MPI_DOUBLE_PRECISION,pleft,1236,MPI_COMM_WORLD,req(4),ierr) call MPI_Irecv(A(0,1),1,vectype,pup,1237,MPI_COMM_WORLD,req(5),ierr) call MPI_Isend(A(nrow,1),1,vectype,pdown,1237,MPI_COMM_WORLD,req(6),ierr) call MPI_Irecv(A(nrow+1,1),1,vectype,pdown,1238,MPI_COMM_WORLD,req(7),ierr) call MPI_Isend(A(1,1),1,vectype,pup,1238,MPI_COMM_WORLD,req(8),ierr) call MPI_Waitall(8,req,status,ierr)
DO J = 2, ncol-1
DO I = 2, nrow-1
B(I, J) = (A( I-1, J ) + A( I, J-1 ) + A( I+1, J) + A( I, J+1 )) / 4
ENDDO
ENDDO
ENDDO call MPI_Finalize(ierr)
END
Приложение 2.
Параллельная Fortran-программа c использованием
OpenMP (вычисление числа
π
, по материалам [9])
Цветом (насыщенностью) выделены относящиеся к OpenMP структуры
PROGRAM COMPUTE_PI parameter (n = 1000) integer i double precision w,x,sum,pi,f,a f(a) = 4.D0/(1.D0+a*a) w = 1.0D0/n sum = 0.0D0;
!$OMP PARALLEL DO PRIVATE(x), SHARED(w)
!$OMP& REDUCTION(+:sum)
do i=1,n x = w*(i - 0.5D0) sum = sum + f(x) enddo pi = w * sum print *, 'pi = ',pi stop end
Приложение 3.
Программа рекурсивного обхода дерева
(язык T++, основная часть кода).
// Специальный заголовочный файл
txx
переопределяет (с помощью макроопределений)
// все ключевые слова, добавленные в язык C++ для обеспечения функциональности Т++
- 123 -
#include
#include
#include struct tree { struct tree tptr left; struct tree tptr right; int value;
}; struct tree tptr create_tree(int deep) { struct tree tptr res = new tval tree; res->value = 1; if (deep <= 1) { res->left = NULL; res->right = NULL;
} else { res->left = create_tree(deep-1); res->right = create_tree(deep-1);
} return res;
} tfun int tsum(struct tree tptr tree) { tval int leftSum, rightSum; if (tree->left != NULL) { leftSum = tsum(tree->left);
} else { leftSum = tree->value;
} if (tree->right != NULL) { rightSum = tsum(tree->right);
} else { rightSum = tree->value;
} return leftSum + rightSum;
} tfun int main (int argc, char* argv[])
{ struct tree tptr tree = create_tree(12); printf("sum = %d\n", (int) tsum(tree)); return 0;
}
Приложение 4.
НОРМА- программа умножения матриц
[c]=[a]
×[b]
размерностью a[iMAX][kMAX], b[kMAX][jMAX], c[iMAX][jMAX]
на линейке процессоров размерности 12
MAIN PART MMmatrix.
! Программа умножения матриц (основной раздел)
BEGIN
Oi: (i=1..iMAX). ! определение одномерных областей
Oj: (j=1..jMAX).
- 124 - Ok: (k=1..kMAX). 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. OUTPUT c(FILE='MMmatrix.out') ON OC. ! операция вывода результирующей матрицы [C] DOMAIN PARAMETERS iMAX=500. ! определение констант DOMAIN PARAMETERS jMAX=1000. DOMAIN PARAMETERS kMAX=1000. FOR OA ASSUME a=(i-1)+(k-1). ! коллективная операция для задания FOR OB ASSUME b=(k-1) × (j-1). ! начальных значений элементам a[i][k] и b[k][j] матриц COMPUTE Pmatrix(a ON OA, b ON OB RESULT c ON OC). ! вызов процедуры Pmatrix END PART. ! конец основного раздела PART Pmatrix. ! начало раздела Pmatrix a,b RESULT c ! a,b - входные параметры, с - выходной ! тело процедуры Pmatrix BEGIN DOMAIN PARAMETERS iMAX=500. DOMAIN PARAMETERS jMAX=1000. DOMAIN PARAMETERS kMAX= 1000. Oi: (i=1..iMAX). Oj: (j=1..jMAX). Ok: (k=1..kMAX). 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. DISTRIBUTION INDEX i=1..12, k=1. ! описание топологии многопроцессорной системы FOR OC ASSUME c=SUM((Ok)a[i,k] × b[k,j]). ! коллективная операция baсkjkMAXk1kikij× = ∑ = = END PART. ! конец раздела Pmatpix
- 125 -
Учебное издание.
Баканов Валерий Михайлович
Параллельные вычисления
Учебное пособие
ЛР № 020418 от 08 октября 1997 г.
Подписано в печать 02.02.2006 г.
Формат 60
×
84. 1/16.
Объем 7,5 п.л. Тираж 100 экз. Заказ 16.
Московский государственный университет приборостроения и информатики.
107996, Москва, ул.Стромынка, 20.
|
Скачать 1.75 Mb.