A divide-and-conquer approach for asynchronous interface synthesis

Asynchronous circuits are crucial in designing low power, high performance digital systems. They are widely used in many real time applications such as digital communication and computer systems. The design of complex asynchronous interface circuits is a difficult and error-prone task. We present an area and time efficient synthesis algorithm for general signal transition graph (STG) specifications. It utilizes a divide-and-conquer approach to significantly reduce the number of design constraints. Thus, large size specifications can be synthesized in a very short execution time. We further developed a BDD based constraint satisfaction algorithm that exploits the don´t cares for area efficient synthesis. Experimental results with a large number of practical signal transition graph benchmarks are presented. These results show that compared to the existing techniques, the divide-and-conquer technique is capable of achieving an average of 20% reduction in implementation area for all the benchmarks and it offers a practical solution for the complex asynchronous interface design problems