Concurrency Reduction of Untimed Latch Protocols - Theory and Practice

A systematic investigation into concurrency reduction of untimed asynchronous 4-phase latch controllers is reported. Starting with a state graph that exhibits maximal concurrency, rules are provided for systematically reducing its states and thereby curtailing its behaviors. The rules predict liveness and occupancy, as well as the regularity and behavior of their pipelines. The rules also reveal the precise extent of the design space and thus provide a secure platform on which to study the implications of concurrency reduction on power, performance and area by implementing and evaluating the complete set of abstracted controllers. This complete characterization enhances the understanding and usage of concurrency and its reduction in handshake protocols. Trade-offs have been observed and reported which will aid designers in trying to find the best protocols for a required specification. Finally, the best synthesized protocols in this class have been identified.