Real time pipelined system design through simulated annealing

This paper is concerned with automatic pipeline implementation of a program subject to some real time (RT) constraints; the program is described through a Control Data Flow Graph (CDFG). We have developed a mapping methodology which assigns to each instruction of CDFG a time step and a HW resource for its execution. We have defined the space Omega of all the possible feasible mappings, as well as an adjacency criterion on it and a cost function evaluating the quality of the mappings, We have minimized the cost function through a Simulated Annealing algorithm. The minimization process returns a mapping which satisfies all RT constraints, has minimal schedule length and minimal HW resource requirement. In order to show the capabilities of the proposed mapping methodology, we apply it to a graph with 50 nodes and several RT constraints: the obtained mapping gives a pipelined execution modality of the graph which satisfies all the given RT constraints.