Placement and Routing Algorithms for Asynchronous Logic Circuits

Cuong Pham-Quoc
Faculty of Computer Science and Engineering, Ho Chi Minh City University of Technology

Thien-Nga Nguyen-Vu
Faculty of Computer Science and Engineering, Ho Chi Minh City University of Technology

Anh Pham-Hoang
Faculty of Computer Science and Engineering, Ho Chi Minh City University of Technology

Anh-Vu Dinh-Duc
Faculty of Computer Science and Engineering, Ho Chi Minh City University of Technology

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 in the design flow. 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).