Optimal functional assignment and communication selection under timing constraint for self-Timed pipelines

In high-level synthesis for application-specific embedded systems, it is critical to employ a proper model to measure the performance of a system containing both computation and communication. The self-Timed system model, which describes the process of computation and communication as timed transitions, is able to accurately model the distributed embedded systems. In the design of a self-Timed system, there are two realistic problems: how to assign heterogeneous functional units to task nodes and how to select communication protocols for pairs of task nodes. This paper focuses on the application with pipeline structure where task nodes are organized in a linear topology. Given a serial of task nodes, our objective is find the optimal functional assignment and communication selection, such that the resultant self-Timed pipeline can satisfy the timing constraint with the minimum total cost. In this paper, we present efficient dynamic programming algorithm to find the optimal solution. Experiments show that other heuristics may not find a feasible assignment for the required time performance while our algorithms can. Even for feasible assignments, our algorithms can achieve 42.47% reduction in total cost.