Self-Scheduling Algorithm for Loop with Cross-Iteration Dependences Under Threads Programming Model

摘要

This paper presents several self-scheduling schemes operating within a thread programming model for scheduling loops with cross-iteration dependences in a shared memorv system. Four of the schemes are already well known: self-scheduling (SS), chunked self-scheduling (CSS), guided self-scheduling (GSS). and factoring. However, since all these schemes were originally developed for loops without any cross-iteration dependence, modifications were investigated to enable the scheduling of loops with cross-iteration dependences. The fifth scheme is a new proposal: carried-dependence self-scheduling (CDSS). Experiments conducted with varving parameters clearly demonstrated that CDSS outperformed the other modified self-scheduling approaches in a number of simulations.