TASK TREE SCHEDULING ONTO LINEAR ARRAYS USING TABU SEARCH

Authors
Citation
Mk. Dhodhi et I. Ahmad, TASK TREE SCHEDULING ONTO LINEAR ARRAYS USING TABU SEARCH, IEE proceedings. Computers and digital techniques, 144(5), 1997, pp. 317-323
Citations number
22
ISSN journal
13502387
Volume
144
Issue
5
Year of publication
1997
Pages
317 - 323
Database
ISI
SICI code
1350-2387(1997)144:5<317:TTSOLA>2.0.ZU;2-S
Abstract
Tabu search is a promising optimisation heuristic that has been succes sfully applied to the solution of many combinatorial optimisation prob lems, yielding optimal or near optimal results. An efficient algorithm based on tabu search is presented, designated as TASS, for the proble m of scheduling a tree-like task graph (task tree) onto linear arrays of processors, with the aim of minimising the system response time. Th e linear processor arrays implemented in VLSI/ULSI technology provide an affordable and cost-effective solution for special applications tha t can be represented by task trees. The performance of the proposed ta bu search-based algorithm is evaluated for a set of test problems sele cted from the literature. Comparison of results obtained by the propos ed algorithm with results reported by previous techniques, shows a con siderable improvement in the system response time.