TILING AND SCHEDULING OF THREE-LEVEL PERFECTLY NESTED LOOPS WITH DEPENDENCIES ON HETEROGENEOUS SYSTEMS.

Saved in:

Bibliographic Details
Title:	TILING AND SCHEDULING OF THREE-LEVEL PERFECTLY NESTED LOOPS WITH DEPENDENCIES ON HETEROGENEOUS SYSTEMS.
Authors:	ZEFREH, EBRAHIM ZAREI¹, LOTFI, SHAHRIAR, KARIMPOUR, JABER, KHANLI, LEYLI MOHAMMAD²
Source:	Scalable Computing: Practice & Experience. Dec2016, Vol. 17 Issue 4, p331-349. 19p. 8 Charts, 6 Graphs.
Subjects:	Loop tiling (Computer science), Heterogeneous computing
Abstract:	Nested loops are one of the most time-consuming parts and the largest sources of parallelism in many scientific applications. In this paper, we address the problem of 3-dimensional tiling and scheduling of three-level perfectly nested loops with dependencies on heterogeneous systems. To exploit the parallelism, we tile and schedule nested loops with dependencies by awareness of computational power of the processing nodes and execute them in pipeline mode. The tile size plays an important role to improve the parallel execution time of nested loops. We develop and evaluate a theoretical model to estimate the parallel execution time of tilled nested loops. Also, we propose a tiling genetic algorithm that used the proposed model to find the near- optimal tile size, minimizing the parallel execution time of dependence nested loops. We demonstrate the accuracy of theoretical model and effectiveness of the proposed tiling genetic algorithm by several experiments on heterogeneous systems. The 3D tiling reduces the parallel execution time by a factor of 1.2× to 2× over the 2D tiling, while parallelizing 3D heat equation as a benchmark. [ABSTRACT FROM AUTHOR]
	Copyright of Scalable Computing: Practice & Experience is the property of Scalable Computing: Practice & Experience and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
Abstract:	Nested loops are one of the most time-consuming parts and the largest sources of parallelism in many scientific applications. In this paper, we address the problem of 3-dimensional tiling and scheduling of three-level perfectly nested loops with dependencies on heterogeneous systems. To exploit the parallelism, we tile and schedule nested loops with dependencies by awareness of computational power of the processing nodes and execute them in pipeline mode. The tile size plays an important role to improve the parallel execution time of nested loops. We develop and evaluate a theoretical model to estimate the parallel execution time of tilled nested loops. Also, we propose a tiling genetic algorithm that used the proposed model to find the near- optimal tile size, minimizing the parallel execution time of dependence nested loops. We demonstrate the accuracy of theoretical model and effectiveness of the proposed tiling genetic algorithm by several experiments on heterogeneous systems. The 3D tiling reduces the parallel execution time by a factor of 1.2× to 2× over the 2D tiling, while parallelizing 3D heat equation as a benchmark. [ABSTRACT FROM AUTHOR]
ISSN:	18951767
DOI:	10.12694/scpe.v17i4.1205