© 2000 by British Computer Society
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
TLS: A Tabu Search Based Scheduling Algorithm for Behavioral Synthesis of Functional Pipelines
1 Department of Electrical and Computer Engineering, Kuwait University, PO Box 5969, Safat 13060, Kuwait, Kuwait Email: imtiaz@eng.kuniv.edu.kw
This paper presents a resource-constrained scheduling algorithm based on tabu search for high-level behavioral synthesis of functional pipelines. The proposed algorithm, designated as TLS, integrates list scheduling with tabu search. List scheduling algorithms have been widely used in high-level synthesis systems, because they are very fast, easy to implement and the low computational complexity of these algorithms make them applicable to large data flow graphs. In list scheduling, the quality of the solution is very sensitive to the priority assigned to the operations. The distinct feature of our technique is that we use tabu search to find suitable priorities. Tabu search is a metaheuristic that can be superimposed on existing procedures to guide these procedures towards searching in more desirable neighborhoods and to prevent them from becoming trapped at locally optimal solutions. The proposed algorithm is conceptually very simple, easy to implement and is very effective in conquering the intractable nature of the resource-constrained scheduling problem. The proposed technique can handle multicycle operations, structural pipelined operations, chained operations and functional pipelining. We demonstrate the effectiveness of our technique by comparing against the existing scheduling techniques for functional pipelining on a number of benchmark examples reported in the literature.
Received 21 July, 1999. Revised 2 December, 1999.