PLACEMENT AND ROUTING ALGORITHMS FOR ASYNCHRONOUS LOGIC CIRCUITS

Abstract

Nowadays, asynchronous design is more and more predominate over synchronous design due to its advantages such as no clock skew, lower power, etc. A design methodology and CAD tools for asynchronous circuits are needed to diffuse largely asynchronous circuits in industry. Placement and routing is one of important processes to visualize the resultant circuit so user can modify if the result of synthesizing and optimizing phases is not really optimal. Many algorithms are developed for placement and routing, but most of them are for physical layout. Logical layout and asynchronous circuits have their own constraints. Algorithms for physical layout; therefore, are not able to be applied directly. This paper proposes algorithms for the placement and routing of logical layout which take into account constraints of an asynchronous circuit. The algorithm of placement is a combination of Kernighan-Lin and Breuer algorithms. A new algorithm for logical routing is introduced based on wave propagating strategy. Although the proposed solution is for logical layout placement and routing of asynchronous circuits, they can be also expanded to cover synchronous circuits. Experiments are done to show that these algorithms give a good result in an acceptable time. These algorithms are implemented and integrated in a design framework for asynchronous circuits (PAID).