Yoğun İşlem Yüküne Sahip Matris Çarpımı Hesaplama Sürelerinin Önbellek Kullanım Optimizasyonu ve Paralel Programlama Teknikleri Kullanılarak İyileştirilmesi

Abstract

Başta görüntü işleme/iyileştirme ve robotik olmak üzere, ekonometri, inşaat mühendisliği, kuantum fiziği gibi birçok alanda hesaplama işlemlerinde yaygın olarak kullanılan matris işlemleri üzerine cache bellek kullanım optimizasyonu yapılarak hesaplama sürelerinin değişimi incelenmiştir. Çalışmada, bilinen matris çarpma işlemi yerine kullanılan farklı algoritmalarla zamanda ve mekanda yerellik prensiplerinden yararlanılarak hesaplama performansı 14 kat daha hızlı hale getirilmiştir. Bilgisayar performansında çok önemli yeri olan ön belleğin etkisinin önemi saptanmaya çalışılmıştır. Ön bellek kullanım optimizasyon yöntemleri ile önemli ölçüde işlem süreleri kısaltılmış ayrıca ön bellek ve diğer işlem birimlerinin daha fazla kullanılmasının önüne geçilerek sistemin ömrünün uzatılması hedeflenmiştir. Cache optimizasyonunun ardından paralel programlama teknikleri kullanılarak yoğun matris işlemlerinin hesaplama sürelerinin kısaltılması amaçlanmıştır. Böylece hem ön bellek daha etkin kullanıldı hem de uygun veri paralelliği kullanılarak mümkün olabilecek en verimli hesaplama işlemlerinin gerçekleştirilmesi sağlanmaya çalışıldı. Cache optimizasyonu ardından yapılan 5 bilgisayarlı paralel programlama tekniği sayesinde hesaplama işlemi genel olarak kullanılan tekniğe göre yaklaşık 59 kat daha hızlı hale getirildi. Paralel programlama ile yapılan hesaplama işlemlerinde farklı sayıda bilgisayarlara göre Speedup değerleri hesaplandı. Ayrıca matris işlemleri için bilgisayarla yapılan hızlı hesaplama yöntemlerinin yanında hesaplama işlemlerine negatif etki gösteren algoritmalar üzerinde de durulmuştur.

Keywords

• Matris çarpımı,MPI,Optimizasyon,Önbellek optimizasyonu,Paralel programlama

Acceleration of High Dimensional Matrix Multiplication Processes With Cache Usage Optimization and Parallel Programming Techniques

Abstract

Optimization of cache on the matrix operations according to calculation times, which are commonly used in many field such as image processing, robotics, econometrics, civil engineering and quantum physics were investigated. The calculation performance is made 14 times faster than using the different algorithms instead of the known matrix multiplication, by using the temporal and spatial locality principles in the study. Effect of the cache which is very important for computer performance, has been tried to detect. Processing times have significantly shortened thanks to cache utilization optimization methods, also it has been aimed that extending the lifetime of the system by preventing use the cache and other processing units more. After cache optimization, it has been aimed to shorten the computation times of intensive matrix operations using parallel programming techniques. Thus, both the cache was used more efficiently and the most effective computations were tried to be performed using the appropriate data parallelism. Thanks to parallel programming techniques applied with 5 computers after cache optimization, the calculation process is made 59 times faster than the commonly used technique. Speedup values are calculated according to the different number of computers in the calculations made by parallel programming. In addition to computer-based fast computation methods for matrix operations, also we have focused on algorithms that have a negative effect on computation.

Keywords

• Cache optimization,Matrix multiplication,MPI,Optimization,Parallel programming

References

1. [1] C. Young, Precalculus, Laurie Rosatone.
2. [2] K.B.T. Leise, The linear algebra behind Google, SIAM Review, 48(3) (2006) 569-581.
3. [3] D.T. Fudenberg, Jean, Game Theory, MIT Press, 1983.
4. [4] M. Healy, Matrices for Statistics, Oxford University Press, 1986.
5. [5] C.R. Godsil, Gordon, Algebraic Graph Theory, Springer-Verlag, 2004.
6. [6] S.D. B, Models for practical parallel computation, International Journal of Parallel Programming, 20.2 (1991) 133-158.
7. [7] G.C. Hillar, Professional Parallel Programming with C#: Master Parallel Extensions with .NET 4, wrox, 2010.
8. [8] G. Moore, Cramming more components onto integrated circuits, Electronics, 8 (1965).

9. [9] işlemci-bellek başarımı farkı, in, acm.org, 19 May 2010.
10. [10] H. Gümüşkaya, Mikroişlemciler ve Bilgisayarlar, Alfa Yayınları, 2011.
11. [11] SystemML Documents, in, systemml.apache.org/, 2016.
12. [12] R. Gu, Y. Tang, C. Tian, H. Zhou, G. Li, X. Zheng, Y. Huang, Improving Execution Concurrency of Large-Scale Matrix Multiplication on Distributed Data-Parallel Platforms, IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 28 (2017) 2539-2552.
13. [13] C. Kart, Matris Metodları ve Lineer Dönüşümler, Fen Fakültesi Yayınevi, Ankara, 1985.
14. [14] K. Chan, K.T. Lam, C.L. Wang, Cache Affinity Optimization Techniques for Scaling Software Transactional Memory Systems on Multi-CMP Architectures, in: D. Grosu, H. Jin, G. Papadopoulos (Eds.) 2015 14th International Symposium on Parallel and Distributed Computing, Ieee, New York, 2015, pp. 56-65.
15. [15] J.R. Goodman, CACHE MEMORY OPTIMIZATION TO REDUCE PROCESSOR MEMORY TRAFFIC, Journal of Vlsi and Computer Systems, 2 (1987) 61-86.
16. [16] S.J. Frank, Tightly coupled multiprocessor system speeds memory-access times, Electronics, 57 (Jan 1984) 164-169.
17. [17] J. Isaak, Squeezing the Most Out of the 68000, Mini-Micro Systems, (October 1982) 193-202.
18. [18] J. Goodman, Computer Sciences Technical Report On Cache Memory Optimization to Reduce Processor/Memory Traffic, ACM Transactions on Computer Systems, (Feb 1985) 1-19.
19. [19] M.M. Mano, Bilgisayar Sistemleri Mimarisi, Literatür Yayıncılık, 2015.
20. [20] P.J. Hatcher, M.J. Quinn, DataParallel Programming on MIMD Computers, MIT Press, (1993).
21. [21] J. Rose, G. Steele, C*: an Extended C Language for Data Parallel Programming, Technical Report PL Thinking Machines Inc. Cambridge MA, (1987).
22. [22] T. Rauber, G. Rünger, Tlib a library to support programming with hierarchical multi-processor tasks, J. Parallel and Distrib. Comput, 65 (March 2005) 347-360.
23. [23] C. Kessler, J. Keller, Models for Parallel Computing Review and Perspectives, PARS-Mitteilungen, 24 (Dec 2007) 13-29.
24. [24] G.M. Amdahl, Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities, in: In Proceedings of AFIPS spring joint computer conference, Atlantic City, NJ, USA, 1967, pp. 483-485.
25. [25] W. Zuo, A. McNeil, M. Wetter, E.S. Lee, Acceleration of the matrix multiplication of Radiance three phase daylighting simulations with parallel computing on heterogeneous hardware of personal computer, Journal of Building Performance Simulation, 7 (2013) 152-163.
26. [26] W.C. Brown, Matrices and vector spaces, New York, 1991.
27. [27] J.D. Alvarez, J.L. Risco-Martin, J.M. Colmenar, Multi-objective optimization of energy consumption and execution time in a single level cache memory for embedded systems, Journal of Systems and Software, 111 (2016) 200-212.
28. [28] C. Y., S. M., E. A., A.-H. B., R. S., Cache size selection for performance, energy and reliability of time-constrained systems, in: Proceedings of the Asia and South Pacific Conference on Design Automation, 2006, pp. 6.
29. [29] M. H., P. M., M. E., Cache aging reduction with improved performance using dynamically re-sizable cache, in: European Design and Automation Association, Proceedings of the Conference on Design, Automation & Test in Europe 3001 Leuven, Belgium, 2014.