Продолжение

Начало

4.2 Матричные операции.

Самыми распространенными формами хранения матриц являются стандартная построчечная форма хранения всех коэффициентов матрицы (DM), которая применяется для хранения плотных матриц, а также построчечная форма хранения ненулевых коэффициентов матрицы и их индексов (SM), которая применяется для хранения разреженных матриц.

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

Таким естественным форматом может служить формат кватернарного дерева (QT). Дерево строится следующим образом. Если порядок матрицы 2ⁿ, то она может быть разбита на четыре квадратных блока порядка 2^n-1, которые также могут быть разбиты на четыре равных блока, и так – вплоть до элементов. Если блокам поставить в соответствие вершины, а ребрами соединить вершины, соответствующие блокам, с вершинами, соответствующими его подблокам, то в результате получим кватернарное дерево. Если некоторый блок нулевой, то соответствующее ему ребро в дереве отсутствует. Это обеспечивает эффективный способ хранения разреженных матриц (см. также [10 и [11]). Отметим, что при необходимости всякая матрица может быть дополнена до матрицы размера 2ⁿ, введением дополнительных нулевых или единичных элементов. Заметим, что обозначения QT, DM и SM происходят от названий: quaternary tree, density matrix и sparse matrix.

Если время вычисления суммы и произведения элементов матриц примерно одинаковые, то применение схемы умножения Штрассена не приводит к ускорению вычислений, если порядок матрицы менее 1287 (см. оценки в [12]). Поэтому в первую очередь были разработаны параллельные программы для стандартного алгоритма умножения матриц. При этом использовались две схемы – простая параллельная схема умножения и рекурсивная блочная схема умножения.

4.3 Простая параллельная схема умножения матриц.

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

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

Эксперименты с этой программой показали, что при умножении матриц порядка 1024 в конечном поле коэффициент ускорения равен 77% при использовании 12 процессоров. На рис. 4 показана зависимость скорости вычислений этой параллельной программы от количества процессоров, участвующих в вычислении.

Рис. 4. Вычисление произведения матриц в конечном поле с помощью простой параллельной схемы умножения.
Коэффициент ускорения равен 77%.

4.4 Рекурсивная блочная схема умножения матриц.

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

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

Эксперименты для матриц 512 порядка с небольшими целыми коэффициентами (~2²⁸) показали, что при умножении в кольце целых чисел коэффициент ускорения равен 85%, а при умножении в конечном поле коэффициент ускорения равный 86.4%. Использовались 2 и 14 процессоров.

На рис. 5 и 6 показаны результаты двух экспериментов, проведенных для динамических параллельных программ умножения матриц. В этих программах использовался QT-формат хранения коэффициентов. В каждом эксперименте выполнялось умножение матриц 512 порядка. В первом случае коэффициенты матриц – это целые числа в пределах 2²⁸. Коэффициент ускорения при переходе с двух на 14 процессоров был равен 85%. Во втором случае коэффициенты матриц берутся из конечного поля, характеристика которого не превосходит 2·10⁸. Коэффициент ускорения при переходе с двух на 14 процессоров составляет 85%.

Рис. 5. Вычисление произведения целочисленных матриц в QT формате с помощью рекурсивной схемы умножения.
Коэффициент ускорения равен 85%.

Рис. 6. Вычисление произведения матриц в конечном поле в QT формате с помощью рекурсивной схемы умножения.
Коэффициент ускорения равен 86%.

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

Для QT-формата был реализован рекурсивный алгоритм вычисления присоединенной и обратной матриц, а также решения систем линейных уравнений (см. [13] и [14]).

Вычисления производились с плотной случайной целочисленной матрицей 128 порядка, с 28-битовыми целыми коэффициентами. Была составлена программа с помощью рекурсивного алгоритма [14] для QT-формата.

Этот алгоритм вычисления присоединенной матрицы в коммутативной области имеет такую же сложность, что и алгоритма матричного умножения, который в нем используется. Для построения параллельного алгоритма был применен последовательный алгоритм вычисления присоединенной матрицы, в котором все процедуры умножения выполнялись параллельно. Результаты экспериментов приведены на рис 7. Коэффициент ускорения при переходе с двух на 14 процессоров равен 60%.

Рис. 7. Вычисление присоединенной (обратной) матрицы в случае целых коэффициентов в QT формате с помощью рекурсивного алгоритма. Коэффициент ускорения равен 60%.

5. Заключение.

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

ЛИТЕРАТУРА

1. G. M. Amdahl. Validity of the single processor approach to achieving large scale computing capabilities. // Proc. AFIPS Conference, Reston, VA, vol. 30, pp. 483-485, April 1967.

2. E. Walker. Extracting data flow information for parallelizing FORTRAN nested loop kernels. / Submission for the degree of Doctor of Philosophy. Department of Computer Science, Heslington, the University of York, England. 1994.

3. J. L. Gustafson. Reevaluating Amdahl’s law. // Communications of the ACM, vol. 31, no. 5, pp. 532-533, May 1988.

4. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan and Hennadiy Leontyev. Dynamic Analysis and Trace Simulation for Data Parallel Programs in the ParJava Environment. M. Estrada, A. Gelbukh (Eds.) // Avances en la Ciencia de la Computacion, ENC’04, Colima, Mexico, pp. 481-488.

5. M. Elnozahy and L. Alvisi and Y.~M. Wang and D.~B. Johnson. A survey of rollback-recovery protocols in message passing systems. / Technical report, Carnegie Mellon University, CMU-CS-96-181. October 1996.

6. W. E. Nagel, A. Arnold, M. Weber, H.-C. Hoppe, and K. Solchenbach. VAMPIR: Visualization and analysis of MPI resources. // Supercomputer, 12(1): 69--80, January 1996.

7. B. Carpenter, G. Zhang, G. Fox, Xiaoming Li, Xinying Li, and Y. Wen. Towards a Java environment for SPMD programming. // D. Pritchard and J. Reeve, (eds.), 4th Intern. Europar Conf., LNCS vol. 1470, 1998.

8. Виктор Иванников, Сергей Гайсарян, Арутюн Аветисян, Вартан Падарян. Применение среды ParJava для разработки параллельных программ. // Труды Института СистемногоПрограммирования. 2004. с. 41-62.

9. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Improving properties of a parallel program in ParJava Environment // The 10th EuroPVM/MPI conference, Venice, Sept. 2003, LNCS v. 2840, pp 491-494.

10. Г.И.Малашонок, А.В.Красиков. Пакет процедур для работы с би-матрицами. Вестник ТГУ, Т.7, вып.1 VII Деpжавинские чтения. 2002, с.76.

11. М.С.Зуев. Параллельные матричные алгоритмы в коммутативных областях. Дипломная работа. ИМФИ ТГУим.Г.Р.Державина, 2004. 12. Malaschonok G.I. Complexity Considerations in Computer Algebra. / Computer Algebra in Scientific Computing, CASC 2004/ Techn. Univ. Munchen, Garching, Germany, 2004. с. 325—332.

13. Malaschonok G.I. Recursive Method for the Solution of systems of Linear Equations.
/ Computational Mathematics. A. Sydow Ed. Proc. 15th IMACS World Congress. V.I. Berlin, August 1997. Wissenschaft and Technik Verlag, Berlin, 1997. pp. 475-480.

14. Malaschonok G.I. Effective Matrix Methods in Commutative Domains. Formal Power Series and Algebraic Combinatorics. Springer, 2000. pp. 506-517.

Начало