Title :
Token space minimization by simulated annealing
Author :
Lohev, Rafi ; Gottlieb, Israel
Author_Institution :
Dept. of Math. & Comput. Sci., Bar-Ilan Univ., Ramat-Gan, Israel
Abstract :
We describe a heuristic solution for the minimum token space scheduling (MTSS) problem, based on simulated annealing. In MTSS, one schedules a set of tasks with precedence constraints, represented by a directed graph. The arcs in the graph represent data, or tokens, which the tasks must receive before they can be processed. MTSS seeks to minimize the maximum number of tokens extant at any time during execution, while minimizing completion time. We motivate MTSS with an application from computer architecture: maximizing the locality of data required for execution of a program by multiprocessors. Simulation results demonstrating the effectiveness of our method are presented
Keywords :
directed graphs; processor scheduling; simulated annealing; directed graph; minimum token space scheduling; simulated annealing; Application software; Computational modeling; Computer architecture; Computer science; Computer simulation; Mathematics; Processor scheduling; Simulated annealing; Terminology; Tree graphs;
Conference_Titel :
Frontiers of Massively Parallel Computation, 1999. Frontiers '99. The Seventh Symposium on the
Conference_Location :
Annapolis, MD
Print_ISBN :
0-7695-0087-0
DOI :
10.1109/FMPC.1999.750604
