Minimizing back pressure for latency insensitive system synthesis

Most scheduling based latency insensitive designs in the literature focus on systems whose graphical representation is a single strongly connected component (SCC), where a hand-shake based protocol can be replaced by periodic clock gating through ASAP scheduling. However, for systems that are represented as interconnected SCCs, `back pressure´, always implemented as the `stall´ signal in the backward directions between SCCs, is required to prevent overflow. In this paper, we formulate the problem of finding a minimum set of back pressure edges. We show that this problem can be reduced to the Minimum Cost Arborescence (MCA) problem for directed graphs. This allows us to obtain a polynomial time algorithm for synthesizing a minimum cost latency insensitive implementation starting from a synchronous model of the original system. We also show that implementing back pressure edges for every inter-SCC connection, as done in a regular hand-shake based protocol, is inferior for the overall system´s throughput. Our approach provides a formal framework for converting a synchronous model into a latency insensitive implementation with a minimum number of inter-SCC back pressure edges and for leveraging periodic clock based scheduling of intra-SCC latency insensitivity.