Self-Timed Pipelines:
Pipelining has been a fundamental technique to achieve parallelism for different computer systems, ranging from micro-architecture level to system level optimizations. When pipelining technique is applied to more complicated systems with multiple heterogeneous processing elements operating at different frequencies, e.g. a heterogeneous pipelined MPSoC for multimedia applications, it is not realistic to employ a global clock for the synchronization between processing elements. It is even true when the whole system consists of multiple distributed computation nodes. For these systems, synchronization is commonly conducted in a self-timed (or asynchronous) fashion.
Different from synchronous pipelines, self-timed pipelines utilize the handshaking protocol to coordinate the behaviors of different pipeline stages, which open up new challenges in the design phase. First, the careless configurations on self-timed pipelines may lead to the inconsistenct behavior with the application; in particular, it may result in deadlocks in some cases. Hence, the first problem is how to configure a self-timed pipeline, such that the resultant systems have the consistent behavior with the target application. Second, without a global clock, it is hard to capture the start and finish time for different stages. The problem is to find a suitable model to capture the behavior of a self-timed system. Third, Third, controlled by handshaking, the rate of generating output data may not be stable, making the throughput and performance analysis complicated. The problem is how to calculate the timing performance, and how to detect the performance bottleneck for a self-timed pipeline with the initial configuration. Fourth, with a global clock, only one buffer is required between two stages; on the contrary, controlled by handshaking, more buffers (memories) may be required to alleviate performance degradation caused by waiting for data/requests. In the consideration of limited memory capacities in processing elements (e.g., FPGAs) and the real-time requirements, a critical problem arises: how to minimize the number of buffers under the timing constraints.
This project tackles the above challenges by modeling the self-timed pipeline using marked graph, and devise efficient algorihtms to obtain optimal or near-optimal solutions.
Weiwen Jiang
