Диссертация (1149957), страница 15
Текст из файла (страница 15)
Этот алгоритм может использоваться для ускоренияалгоритмов линейной алгебры, которые сводятся к задаче умножения матриц(например, QR разложение матрицы).Описанный алгоритм является новым. Его новизна состоит в использованиинестандартного иерархического блочного размещения матриц. Такое размещениематриц позволяет уменьшить количество кеш-промахов и тем самым увеличитьобщую производительность алгоритма. Таким образом, в данной главераскрывается решение положения 1, выносимого на защиту.Вчетвертойглавеприводитсяалгоритмавтоматизацииблочныхразмещений данных, реализованный в с системе ОРС.
Такая автоматизацияреализована на уровне директив компилятора языка Си. Реализована такжеподдержка блочных размещений для программ, написанных на языке Фортран. Сцелью внедрения автоматического блочного размещения данных в программах,написанных на языке ФОРТРАН, автором был реализован парсер языкаФОРТРАН 77/90 в системе ОРС, который был апробирован на пакете ACELAN.114Этим самым, в данной главе раскрывается решение положения 2, выносимого назащиту.И так, все поставленные в диссертации задачи решены, и цель диссертациидостигнута.Результатыдиссертациивнедренывнаучныхисследованиях(приразработке Оптимизирующей распараллеливающей системы мехмата Южногофедерального университета) и в образовании (в магистерской программе«Высокопроизводительныевычисленияитехнологиипараллельногопрограммирования»).Можно выделить следующие рекомендации по применению полученныхрезультатов:1.
Предлагаемый алгоритм умножения матриц может использоваться дляускоренияработысуществующихпакетовприкладныхпрограмм,написанных для процессоров с поддержкой AVX, и использующихумножение матриц в качестве подзадачи. При этом программист долженучитывать, что подаваемые на вход матрицы должны храниться в памятиблочно.2. Директивы, реализованные в компиляторе языка Си системы ОРС,позволяющиеавтоматическиблочноразмещатьматрицы,могутиспользоваться для ускорения программ.3. Полученная модель времени выполнения может использоваться дляпрогнозирования времени работы некоторых работающих с матрицамипрограмм и может использоваться для построения подобных моделей длядругих случаев.Перспективы дальнейшей работы таковы: Адаптацияполученныхвдиссертацииметодовоптимизацииквычислительным архитектурам близкого будущего и исследование влиянияэтих методов на производительность оптимизируемых программ.115 Применение изложенных методов оптимизации программ к другим задачам,требующим большого объема вычислений.116Список сокращений и условных обозначенийOPS – Optimizing parallelization systemОРС – оптимизирующая распараллеливающая системаДВОР – диалоговый высокоуровневый оптимизирующий распараллеливательAVX – Advanced Vector Extensions – набор векторных команд, оперирующих с256-битными регистрамиLLVM – Low Level Virtual MachineDVM – Distributed Virtual MemoryICC – Intel C CompilerGCC – GNU C Compiler,MSVC – Microsoft Visual C++SUIF – Stanford University Intermediate FormatTLB – Translation Lookaside BufferLRU – Least Recently UsedMRU – Most Recently Used117Литература1.ACELAN.[electronic—resource].http://www.math.rsu.ru/mexmat/mathmodel/ac/index.php.URL:(online;accessed:2015-12-10).2.Charles, V.L.
A Block QR Factorization Scheme for Loosely Coupled Systems ofArray Processors [Text] / V.L. Charles, M. Schultz // Numerical Algorithms for ModernParallel Computer Architectures. — NY: Springer US, 1986. — Vol. 13, — P. 217-232.3.Charles, V.L. The WY representation for products of householder matrices [Text]/ Ch.
Bischof, V.L. Charles. // Computer science technical report, Cornell University, —1985.4.Denning, P.J. The Locality Principle [Text] / P.J. Denning // Communications ofthe ACM - Designing for the mobile device. — 2005. — Vol. 48, no 7, — P. 19–24.5.Gustavson, F.G. Cache Blocking for Linear Algebra Algorithms [Text] / F. G.Gustavson // PPAM 2011: Parallel Processing and Applied Mathematics: 9thInternational Conference, September 11-14, 2011. Revised Selected Papers, Part I —Torun, Poland: Springer Berlin Heidelberg.
— 2012. — P. 122–132.6.Lam, M.S. The cache performance and optimizations of blocked algorithms[Text] / Monica S. Lam, Edward E. Rothberg, Michael E. Wolf // Proceeding ASPLOSIV Proceedings of the fourth international conference on Architectural support forprogramming languages and operating systems. —1991. — P. 63-74.7.Prokop, H. Cache-oblivious algorithms [Text] / M. Frigo, C. E. Leiserson, H.Prokop, S.
Ramachandran // Proceedings of the 40th IEEE Symposium on Foundationsof Computer Science (FOCS’99). — 1999. — P. 285–297.8.Gustavson, F.G. Is Cache-Oblivious DGEMM Viable? [Text] / A. G. Joh, F. G.Gustavson, K. Pingali, K. Yotov // Proceedings of the 8th international conference onApplied parallel computing. Springer-Verlag — Berlin, Heidelberg 2007. ISBN:3-54075754-6 978-3-540-75754-2.
— 2007. — P. 919-928.1189.Larus, J. Improving Pointer-Based Codes Through Cache-Conscious DataPlacement [Text] / T. Chilimbi, J. Larus, M. D. Hill // Wisconsin University TechnicalReport CS-TR-98-1365. —1998.10.Chatterjee, S. Nonlinear Array Layouts for Hierarchical Memory Systems [Text] /S. Chatterjee, V.V. Jain, A.R.
Lebeck, S. Mundhra, and M. Thottethodi // Proc. 13thACM Int’l Conf. Supercomputing. — 1999. — P. 444-453.11.Prasanna, V. K. Cache Conscious Walsh-Hadamard Transform [Text] / N. Park,V. K. Prasanna // The 26th International Conference on Acoustics, Speech, and SignalProcessing. — 2001. — Vol. 2. — P.
1205-1208.12.Jeyarajan, T. Alternative Array Storage Layouts for Regular Scientific Programs[Text] / T. Jeyarajan // University of London Imperial College London Department ofComputing. — 2005.13.Manjikian, N. Array Data Layout for the Reduction of Cache Conflicts [Text] / N.Manjikian, T. Abdelrahman // department of Electrical and Computer Engineering. InProceedings of the 8th International Conference on Parallel and Distributed ComputingSystems — 1995.14.Karlsson, L.
Blocked In-Place Transposition with Application to Storage FormatConversion [Text] / Lars Karlsson // Technical Report UMINF 09.01, Dept. ofComputing Science, Umeе University, Sweden. — 2009.15.Prasanna, V. K. Efficient Matrix Multiplication Using Cache Conscious DataLayouts [Text] / N. Park, W. Liu, V.
K. Prasanna, C. Raghavendra // The DoD HPCMOUsers Group Conference — 2000.16.Prasanna, V. K. Tiling, Block Data Layout, and Memory Hierarchy Performance[Text] / N. Park, B. Hong, V. K. Prasanna // IEEE Transactions on Parallel andDistributed Systems — Vol. 14, no. 7 — 2003. — P. 640-654.17.Zuckerman, S. Fine Tuning Matrix Multiplications on Multicore [Text] / S.Zuckerman, M. Perache, W.
Jalby //High Performance Computing - HiPC 2008,Lecture Notes in Computer Science — Vol. 5374 — 2008. — P. 30-41.18.Herrero, J.R. Using Non-canonical Array Layouts in Dense Matrix Operations[Text] / J. R. Herrero, J. J. Navarro // Applied Parallel Computing. State of the Art in119Scientific Computing Lecture Notes in Computer Science. — Vol. 4699. — 2007. — P.580-588.19.Prasanna, V.K. Analysis of Memory Hierarchy Performance of Block DataLayout [Text] / N. Park, B. Hong, V.
K. Prasanna // International Conference onParallel Processing. — 2002. — P. 35 - 44.20.Frens, J. D. Auto-blocking matrix-multiplication or tracking BLAS3 performancewith source code [Text] / J. D. Frens and D. S. Wise. // Proceedings of the Sixth ACMSIGPLAN Symposium on Principles and Practice of Parallel Programming. — LasVegas, NV, June 1997. — P.
206–216.21.Goodchild, M. F. Optimizing raster storage: an examination of four alternatives[Text] / M. F. Goodchild, A. W. Grandfield // Proceedings Auto Carto 6 Ottawa, Oct.1983. — P. 400–407.22.Jagadish, H. V. Linear clustering of objects with multiple attributes [Text] / H. V.Jagadish. // Proceedings of the 1990 ACM SIGMOD international conference onManagement of data / ACM. — New York, NY, USA.
— 1990. — P. 332-342.23.Akin, B. FFTs with near-optimal memory access through block data layouts[Text] / B. Akin, F. Franchetti, J. C. Hoe // Proceedings of IEEE InternationalConference Acoustics Speech and Signal Processing. — 2014. — P. 3898-3902.24.Gustavson, F. G. Rectangular full packed format for LAPACK algorithmstimings on several computers [Text] / F. G. Gustavson, J. W. Sniewski // AppliedParallel Computing, State of the Art in Scientific Computing, PARA 2006. — Vol.LNCS 4699. —Springer-Verlag, Berlin Heidelberg, 2007.
— P. 570–579.25.Geijn, R. Parallel out-of-core computation and updating of the QR factorization[Text] / Robert A. Van De Geijn, B. C. Gunter, Robert A. Van De Geijn // JournalACM Transactions on Mathematical Software (TOMS). — Vol. 31, no. 1. —2005. —ACM New York, NY, USA. — P. 60-78.26.Goto, K. Anatomy of High-Performance Matrix Multiplication [Text] / K.
Goto,R. A. van de Geijn // ACM Transactions on Mathematical Software. — Vol. 34, no. 3.— 2008. P. 1-25.12027.Dongarra, J. Programming the LU Factorization for a Multicore System withAccelerators [Text] / J. Kurzak, P. Luszczek, M. Faverge, J. Dongarra // HighPerformance Computing for Computational Science (VECPAR 2012), Lecture Notes inComputer Science. — Vol. 7851. — 2013. — P.
28-35.28.PLASMA Users’ Guide, Parallel Linear Algebra Software for MulticoreArchitectures,UniversityofTennessee[Electronicresource].—URL:http://icl.cs.utk.edu/projectsfiles/plasma/pdf/users_guide.pdf (online;accessed:2015-1210).29.ATLAS (Automatically Tuned Linear Algebra Software). [Electronic resource].— URL: http://math-atlas.sourceforge.net/ (online;accessed:2015-12-10).30.OPENBLAS . [Electronic resource].
— URL:http://www.openblas.net/(online;accessed:2015-12-10).31.Kennedy, K. Optimizing compilers for modern architectures: a dependence-basedapproach / K. Kennedy, J. R. Allen // San Francisco, CA: Morgan Kaufmann PublishersInc. — 2001.32.Muchnik, S. Advanced compiler design and implementation / Muchnik S.
// San-Francisco, CA, USA: Morgan-Kaufmann. — 1997.33.Sharma, K. User-Specified and Automatic Data Layout Selection for PortablePerformance / K. Sharma, I. Karlin, J. Keasler, J. R McGraw, V. Sarkar. // RiceUniversity Technical Report (TR13-03), LLNL Technical Report TR-637873. — 2013.34.Keasler, J. TALC: A Simple C Language Extension For Improved Performanceand Code Maintainability [Text] / J. Keasler, T.
Jones, D. Quinlan // 9th LCIInternational Conference on High-Performance Clustered Computing - Urbana, IL, May— 2008.35.Liu, J. Data layout optimization for GPGPU architectures [Text] / J. Liu, W.Ding, O. Jang, M. Kandemir // PPoPP '13 Proceedings of the 18th ACM SIGPLANsymposium on Principles and practice of parallel programming. — ACM New York,NY, USA. — 2013. — P. 283-284. — ISBN: 978-1-4503-1922-5.36.Liu, J.
Compiler Framework for Extracting Superword Level Parallelism [Text]/J. Liu, Y. Zhang, O. Jang, W. Ding, M. Kandemir // A Proceeding PLDI '12121Proceedings of the 33rd ACM SIGPLAN conference on Programming LanguageDesign and Implementation / ACM. — New York, NY, USA. — 2012. — P. 347-358.37.ParaWise Automatic Parallelization Environment. [Electronic resource]. — URL:http://www.parallelsp.com/parawise.htm (online;accessed:2015-12-10).38.Intel C++ Composer XE 2013 SP1 for Linux, Update 3. [Electronic resource]. —URL: https://software.intel.com/en-us/articles/intel-c-composer-xe-2013-sp1-for-linuxupdate-3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
