DocumentCode
2626206
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
fYear
1999
fDate
21-25 Feb 1999
Firstpage
226
Lastpage
233
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;
fLanguage
English
Publisher
ieee
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
Type
conf
DOI
10.1109/FMPC.1999.750604
Filename
750604
Link To Document