کاشی‌بندی حلقه‌های تودرتو با در نظر گرفتن محلیت داده‌ها به‌منظور اجرای موازی بر روی پردازنده‌های چندهسته‌ای

نویسندگان

1 دانشیار دانشکده مهندسی کامپیوتر - دانشگاه علم و صنعت ایران

2 دانشجوی دکترای دانشکده مهندسی کامپیوتر - دانشگاه علم و صنعت ایران

چکیده

چکیده: در سال­های اخیر صنعت ریزپردازنده به سمت طراحی و ساخت پردازنده­های چندهسته­ای حرکت کرده است. این بستر محاسباتی با کارایی بالا دارای دو جنبه اصلی است: تعدادی هسته محاسباتی و سلسله مراتب حافظه نهان به­منظور استفاده از این بستر در جهت افزایش کارایی برنامه‌ها نیاز به تکنیک­های کامپایلری مناسب با در نظر گرفتن این دو جنبه در کنار هم است. کاشی­بندی حلقه­های تکرار یکی از اصلی­ترین تبدیلات حلقه­ای است که هم به­منظور موازی­سازی دانه­درشت در جهت استفاده از چندپردازنده­ها و هم به­منظور بهبود محلیت داده­ها در جهت استفاده از سلسله مراتب حافظه نهان به­کار رفته است. مشکل، کاربرد همزمان موازی­سازی حلقه­ها و بهبود محلیت داده­ها در حلقه­های تکرار است. در این مقاله، روشی نوین برایزمان­بندی کاشی­ها در جهت اجرای موازی کاشی­ها بر اساس میزان استفاده مجدد داده­ها بین آن­ها ارائه شده است. در این روش بهبود محلیت داده­ها با درظر گرفتن سلسله مراتب حافظه نهان همگام با موازی­سازیدانه­درشت حاصل می­شود.

کلیدواژه‌ها


[1]G. Ottoni, Global Instruction Scheduling for Multi-Threaded Architectures, PhD Thesis, Princeton University, 2008.
[2]O. Ozturk, “Data locality and parallelism optimization using a constraint-based approach,” Journal of Parallel and Distributed Computing, vol. 71, no. 2 , pp. 280-287, 2011.
[3]U. Bondhugula, A. Hartono, J. Ramanujam and P. Sadayappan, “A practical automatic polyhedral parallelizer and locality optimizer,” ACM SIGPLAN Notices, vol. 43, no. 6, pp. 101-113, 2008.
[4]S. Lotfi and S. Parsa, “Parallel loop generation and scheduling,” The Journal of Supercomputing, vol. 50, no. 3, pp. 289-306, 2009.
[5]M. E. Wolf and M. S. Lam, “A loop transformation theory and an algorithm to maximize parallelism,” IEEE Transactions on Parallel and Distributed Systems, vol. 2, no. 4, pp. 452-471, 1991.
[6]J. Xue and C-H. Huang, “Reuse-driven tiling for improving data locality,” International Journal of Parallel Programming, vol. 26, no. 6, pp. 671-696, 1998.
[7] Y. Song and Z. Li, “New tiling techniques to improve cache temporal locality,” ACM SIGPLAN Notices, vol. 34, no. 5, pp. 215-228, 1999.
[8]M. E. Wolf and M. S. Lam, “A data locality optimizing algorithm”, ACM SIGPLAN Notices, vol. 26, no. 6, pp. 30-44, 1991.
[9]S. Parsa and M. Hamzei, “Locality conscious nested-loops parallelization,” ETRI Journal, vol. 36, no. 1, pp. 124-133, 2014.
[10]J. Liu, Y. Zhang, W. Ding and M. Kandemir, “On-chip cache hierarchy-aware tile scheduling for multicore machines,” In 9th Annual IEEE/ACM International Symposium on Code Generation and Optimization (CGO), pp. 161-170. 2011.
[11]L. Pouchet, Iterative Optimization in the Polyhedral Model, PhD Thesis, France University of Paris-Sud XI, 2010.
[12]A. Cohen, S. Girbal and O. Temam, “A polyhedral approach to ease the composition of program transformations,” In Euro-Par 2004 Parallel Processing, pp. 292-303, 2004.
[13]L. Pouchet, C. Bastoul, A. Cohen and J. Cavazos, “Iterative optimization in the polyhedral model: part II, multidimensional time”, ACM SIGPLAN Notices, vol. 43, no. 6, pp. 90-100, 2008.
[14]P. Feautrier, “Some efficient solutions to the affine scheduling problem. part II. multidimensional time,” International Journal of Parallel Programming, vol. 21, no. 6, pp. 389-420, 1992.
[15]J. Ramanujam and P. Sadayappan, “Tiling multidimensional iteration spaces for multicomputers,” Journal of Parallel and Distributed Computing, vol. 16, no. 2, pp. 108-120, 1992.
[16]C. Bastoul, “Efficient code generation for automatic parallelization and optimization,” In ISPDC’2 IEEE International Symposium on Parallel and Distributed Computing, pp. 23-30, 2003.
[17]C. Bastoul, “Extracting polyhedral representation from high level languages,” Technical Report at Paris-Sud University, 2008.