сравнение метода гаусса и lu разложения

2,11 Mb. страница4/6Дата конвертации29.09.2011Размер2,11 Mb.Тип ... Смотрите также:       4     ^ 1 X (I, J) = X (I-1, J) + Y (I, J 1) + C Рассмотрим две любые смежные по значениям индексов итерации, например:X(2,2) = X(1,2) + X(2,1) X(2,3) = X(1,3) + X(2,2)Рисунок показывает, что между итерациями существует прямая зависимость. Использовать для сложения смежные строки нельзя, так как нижняя строка зависит от верхней. Нельзя складывать и смежные столбцы, так как правый столбец зависит от левого. Тем не менее параллелизм в задаче есть, например, все операции в диагонали 41, 42, 43, 44 можно выполнять парал лельно. Если повернуть оси I, J на 45 градусов и переименовать операции внутри каждой диагонали,как на следующем рисунке, то можно использовать этот параллелизм. Соответствующая программа для верхних диагоналей (включая главную) и нижних диагоналей приведена ниже:DO 1 I = 1,N Пусть I =3, тогда x(3,1)=x(2,1)+x(3,0) DO PAR J = 1, I x(3,2)=x(2,2)+x(2,1) X (I, J) = X(I-1, J) + X(I-1, J-1) x(3,3)=x(2,3)+x(2,2) 1 CONTINUE Эти итерации действительно независимы --------------------------------------- K + 2 DO 2 I = N +1, 2N 1 DO PAR J + K, N R = K + 1 X(I, J) = x(I-1, J) + X(I-1, J-1) + C 2 CONTINUEЗдесь К = 1,2 обозначает левый - верхний или правый - нижний треугольник пространства итерацийАлгоритм метода гиперплоскостей состоит в следующем: Производится анализ индексов и построение зависимостей в пространстве итераций Определяется угол наклона осей и переименование переменных Строится параллельная программ Недостаток метода гиперплоскостей состоит в том, что ширина параллелизма в каждой итерации параллельной программы неодинакова. Это исключено в методе параллелепипедов и ряде других методов. Достаточно полное описание методов практической разработки параллельных алгоритмов для начального изучения представлено в известной книге Ортеги [3 ]. Для параллельного программирования существует ряд языков. Основные из них: OpenMP для многопроцессорных систем с общей памятью MPI - для многопроцессорных систем с индивидуальной памятью Существует часто некоторая путаница между OpenMP и MPI. Эта путаница вполне понятно, поскольку есть еще версия MPI называется "Open MPI". С точки зрения программиста, MPI является библиотекой, которая содержит процедуры передачи сообщений. OpenMP, с другой стороны, представляет собой набор директив компилятора, которые сообщают OpenMP, если включен компилятор, какие части программы может быть запущены как нити. Таким образом, разница «нити» против «сообщений». Давайте взглянем на обоих методов.^ 4.2. Стандарт MPIНаиболее распространенной библиотекой параллельного программирования в модели передачи сообщений является MPI (Message Passing Interface). Рекомендуемой бесплатной реализацией MPI является пакет MPICH, разработанный в Аргоннской национальной лаборатории. MPI [8] является библиотекой функций межпроцессорного обмена сообщениями и содержит около 300 функций, которые делятся на следующие классы: операции точка-точка, операции коллективного обмена, топологические операции, системные и вспомогательные операции. Поскольку MPI является стандартизованной библиотекой функций, то написанная с применением MPI программа без переделок выполняется на различных параллельных ЭВМ. Принципиально для написания подавляющего большинства программ достаточно нескольких функций, которые приведены ниже. Функция MPI_Send является операцией точка-точка и используется для посылки данных в конкретный процесс. Функция MPI_Recv также является точечной операцией и используется для приема данных от конкретного процесса. Для рассылки одинаковых данных всем другим процессам используется коллективная операция MPI_BCAST, которую выполняют все процессы, как посылающий, так и принимающие. Функция коллективного обмена MPI_REDUCE объединяет элементы входного буфера каждого процесса в группе, используя операцию op, и возвращает объединенное значение в выходной буфер процесса с номером root. ^ MPI_Send(address, сount, datatype, destination, tag, comm), аddress адрес посылаемых данных в буфере отправителя сount длина сообщения datatype тип посылаемых данных destination имя процесса-получателя tag для вспомогательной информации comm имя коммуникатораMPI_Recv(address, count, datatype, source, tag, comm, status) address адрес получаемых данных в буфере получателя count длина сообщения datatype тип получаемых данных source имя посылающего процесса процесса tag - для вспомогательной информации comm имя коммуникатора status - для вспомогательной информацииMPI_BCAST (address, сount, datatype, root, comm) root номер рассылающего (корневого)процесса^ MPI_REDUCE(sendbuf, recvbuf, count, datatype, op, root, comm) sendbuf - адрес посылающего буфера recvbuf - адрес принимающего буфера count - количество элементов в посылающем буфере datatype тип данных op - операция редукци

«Архитектура» 1 чел. помогло.

1 X (I, J) = X (I-1, J) + Y (I, J 1) + C - «Архитектура»