Научный журнал
ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ.
СЕВЕРО-КАВКАЗСКИЙ РЕГИОН.

ТЕХНИЧЕСКИЕ НАУКИ


ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ СЕВЕРО-КАВКАЗСКИЙ РЕГИОН. 2017; 3: 81-88

 

http://dx.doi.org/10.17213/0321-2653-2017-3-81-88

 

ПЕРЕРАЗМЕЩЕНИЕ МАТРИЦ К БЛОЧНОМУ ВИДУ С МИНИМИЗАЦИЕЙ ИСПОЛЬЗОВАНИЯ ДОПОЛНИТЕЛЬНОЙ ПАМЯТИ

М.В. Юрушкин, С.Г. Семионов

Юрушкин Михаил Викторович – канд. физ.-мат. наук, инженер-программист, Южный федеральный университет, г. Ростов-на-Дону, Россия. E-mail: m.yurushkin@gmail.com

Семионов Станислав Георгиевич – студент, Южный федеральный университет, г. Ростов-на-Дону, Россия. E-mail: stassemionov@mail.ru

 

 

Аннотация

Представлен метод преобразования размещения матриц между строчным и блочным представлениями. Строчное размещение используется в языке программирования Си в качестве стандартного. Блочное размещение подразумевает хранение элементов матрицы в памяти таким образом, что элементы блока располагаются в памяти последовательно. Такая модель размещения обеспечивает высокую эффективность работы кеш-памяти процессора для алгоритмов, выполняющих значительное число операций над каждым элементом матрицы. Особенностью представленного метода является то, что он требует небольшой объем дополнительной памяти для переразмещения матрицы, который равен длине строки переразмещаемого блока. Кроме того, результаты численных экспериментов показали, что такой подход позволяет в 4–10 раз быстрее переразмещать матрицу, чем наивный алгоритм переразмещения матрицы. Предлагаемый алгоритм можно использовать в блочных алгоритмах, использующих блочное размещение матриц. Программная реализация данного алгоритма была реализована в рамках проекта системы ОРС.

 

Ключевые слова: каноническое размещение матриц; блочное размещение матриц; двойное блочное размещение матриц; высокопроизводительные вычисления; цикл перестановки; кеш-память.

 

Полный текст: [in elibrary.ru]

 

Ссылки на литературу

  1. Herrero J.R., Navarro J.J. Using Non-canonical Array Layouts in Dense Matrix Operations // Applied Parallel Computing. State of the Art in Scientific Computing: 8th International Workshop, PARA 2006, Umea, Sweden, June 18 – 21, 2006, Revised Selected Papers / Ed. by B. Kagstrom [et al.]. Berlin; Heidelberg: Springer Berlin; Heidelberg, 2007. Р. 580 – 588.
  2. Efficient Matrix Multiplication Using Cache Conscious Data Layouts / N. Park [et al.]. 2001.
  3. Park N., Hong B., Prasanna V.K. Tiling, block data layout, and memory hierarchy performance // IEEE Transactions on Parallel and Distributed Systems. 2003. July. Vol. 14, № 7. P. 640 – 654.
  4. Park N., Hong B., Prasanna V.K. Analysis of memory hierarchy performance of block data layout // Proceedings International Conference on Parallel Processing. 2002. P. 35 – 44.
  5. Автоматизация распараллеливания программ с блочным размещением данных / Б. Штейнберг [и др.] // СибЖВМ. 2015. Т. 18, № 1.
    С. 41 – 53.
  6. Frens J.D., Wise D.S. Auto-blocking Matrix-multiplication or Tracking BLAS3 Performance from Source Code // SIGPLAN Not. New York, NY, USA, 1997. July. Vol. 32, № 7. P. 206 – 216.
  7. Yurushkin M.V. Double Block Data Layout in High Performance Matrix Multiplication Algorithm // Software Engineering. 2016. Vol. 7, № 3.
    P. 132 – 139.
  8. Fred G. Gustavson T.S. In-Place Transposition of Rectangular Matrices // Applied Parallel Computing. State of the Art in Scientific Computing. 2007. June. P. 560 – 569.
  9. Kirschenhofer P.H., Prodinger R.T. A contribution to the analysis of in situ permutation // Glas. Mat. Ser. III. 1987. Vol. 22, № 2. С. 269 – 278.
  10. ОРС. Оптимизирующая распараллеливающая система. URL: www.ops.rsu.ru (дата обращения 25.01.2017).
  11. Bischof C., Loan C.V. The WY Representation for Products of Householder Matrices // SIAM Journal on Scientific and Statistical Computing. 1987. Vol. 8, № 1. Р. 2 – 13.