×

zbMATH — the first resource for mathematics

Scheduling loops onto arbitrary target machines using simulated annealing. (English) Zbl 0861.90072
Summary: The problem of scheduling program tasks onto multiprocessor computers has received considerable attention in recent years. It is known to be a computationally intensive problem. The complexity of the problem rises even more when loops are considered especially when the loop upper bound is not known before execution time. In this paper, we introduce a loop unrolling technique that allows several iterations of a set of loops as well as tasks within the same iteration to overlap in execution in such a way that minimizes the loop execution time. We use simulated annealing technique to achieve near-optimal mapping of the tasks included in a set of nested loops on an arbitrary parallel computer. Our goal is to find the best unrolling vector and the Gantt chart that indicates the allocation and the order of the tasks in the post-unrolled loop on the available processors.

MSC:
90B35 Deterministic scheduling theory in operations research
65Y05 Parallel numerical computation
PDF BibTeX XML Cite