TLS: A tabu search based scheduling algorithm for behavioral synthesis of functional pipelines

This paper presents a resource-constrained scheduling algorithm based on ta bu 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 syn thesis systems, because they are very fast, easy to implement and the low c omputational complexity of these algorithms make them applicable to large d ata flow graphs. In list scheduling, the quality of the solution is very se nsitive 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. Th e proposed algorithm is conceptually very simple, easy to implement and is very effective in conquering the intractable nature of the resource-constra ined scheduling problem. The proposed technique can handle multicycle opera tions, structural pipelined operations, chained operations and functional p ipelining. We demonstrate the effectiveness of our technique by comparing a gainst the existing scheduling techniques for functional pipelining on a nu mber of benchmark examples reported in the literature.