کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
523952 | 868534 | 2013 | 12 صفحه PDF | دانلود رایگان |
• We solve the hyperplane model at run time by scheduling tasks in parallel.
• We improve the solution to be self adaptive and able to load balance.
• We show that our method accurately computes the optimal tile size.
• We get comparable execution times with compile-time methods.
In this paper we suggest a new approach for solving the hyperplane problem, also known as “wavefront” computation. In direct contrast to most approaches that reduce the problem to an integer programming one or use several heuristic approaches, we gather information at compile time and delegate the solution to run time. We present an adaptive technique which intuitively calculates which new threads will be able to be executed in the next computation cycle based on which threads are executed in the current one. Moving the solution to the run time environment provides us with higher versatility alongside a perfect solution of the underlying hyperplane pattern being discovered without the need to perform any prior calculations. The main contribution of this paper is the presentation of the self adaptive algorithm, an algorithm which does not need to know the tile size (which controls the granularity of parallelism) beforehand. Instead, the algorithm itself adapts the tile size while the program is running in order to achieve optimal efficiency. Experimental results show that if we have a sufficient number of parallel processing elements to diffuse the scheduler’s workload, its overhead becomes low enough that it is overshadowed by the net gain in parallelism. For the implementation of the algorithm we suggest, and for our experimentations our parallelizing compiler C2μTC/SL is used, a C parallelizing compiler which maps sequential programs on the SVP processor and model.
Journal: Parallel Computing - Volume 39, Issue 10, October 2013, Pages 603–614