Channel router

Last updated
Figure 1: A channel routing problem. The numbered pins on the top and bottom of the channel must be connected. The nets specified on the left and right of the channel must be brought to that end of the channel ChannelRouteProblem.svg
Figure 1: A channel routing problem. The numbered pins on the top and bottom of the channel must be connected. The nets specified on the left and right of the channel must be brought to that end of the channel

A channel router is a specific variety of router for integrated circuits. Normally using two layers of interconnect, it must connect the specified pins on the top and bottom of the channel. Specified nets must also be brought out to the left and right of the channel, but may be brought out in any order. The height of the channel is not specified - the router computes what height is needed.

Figure 2: A solution to the channel routing problem shown above. Solutions are not unique, and this is just one of the many possible. ChannelRouteSolution.svg
Figure 2: A solution to the channel routing problem shown above. Solutions are not unique, and this is just one of the many possible.

The density of a channel, defined for every x within the channel, is the number of nets that appear on both the left and right of a vertical line at that x. The maximum density is a lower bound on the height of the channel. A "cyclic constraint" occurs when two pins occur in the same column (but with different orders) in at least two columns. In the example shown, nets 1 and 3 suffer from cyclic constraints. This can only be solved by "doglegs" as shown on net 1 of the example.

Channel routers were one of the first forms of routers for integrated circuits, [1] and were heavily used for many years, with YACR [2] perhaps the best known program. However, modern chips have many more than 2 interconnect layers. Although the effort was made to extend channel routers to more layers, [3] [4] this approach was never very popular, since it did not work well with over-the-cell routing where pins are not movable. In recent years, area routers have in general taken over.

Related Research Articles

Rent's rule pertains to the organization of computing logic, specifically the relationship between the number of external signal connections to a logic block with the number of logic gates in the logic block, and has been applied to circuits ranging from small digital circuits to mainframe computers. Put simply, it states that there is a simple power law relationship between these two values.

In electronic design, wire routing, commonly called simply routing, is a step in the design of printed circuit boards (PCBs) and integrated circuits (ICs). It builds on a preceding step, called placement, which determines the location of each active element of an IC or component on a PCB. After placement, the routing step adds wires needed to properly connect the placed components while obeying all design rules for the IC. Together, the placement and routing steps of IC design are known as place and route.

Placement is an essential step in electronic design automation — the portion of the physical design flow that assigns exact locations for various circuit components within the chip's core area. An inferior placement assignment will not only affect the chip's performance but might also make it non-manufacturable by producing excessive wire-length, which is beyond available routing resources. Consequently, a placer must perform the assignment while optimizing a number of objectives to ensure that a circuit meets its performance demands. Together, the placement and routing steps of IC design are known as place and route.

Design flows are the explicit combination of electronic design automation tools to accomplish the design of an integrated circuit. Moore's law has driven the entire IC implementation RTL to GDSII design flows from one which uses primarily stand-alone synthesis, placement, and routing algorithms to an integrated construction and analysis flows for design closure. The challenges of rising interconnect delay led to a new way of thinking about and integrating design closure tools.

Delay calculation is the term used in integrated circuit design for the calculation of the gate delay of a single logic gate and the wires attached to it. By contrast, static timing analysis computes the delays of entire paths, using delay calculation to determine the delay of each gate and wire.

The primary focus of this article is asynchronous control in digital electronic systems. In a synchronous system, operations are coordinated by one, or more, centralized clock signals. An asynchronous system, in contrast, has no global clock. Asynchronous systems do not depend on strict arrival times of signals or messages for reliable operation. Coordination is achieved using event-driven architecture triggered by network packet arrival, changes (transitions) of signals, handshake protocols, and other methods.

<span class="mw-page-title-main">Network on a chip</span> Electronic communication subsystem on an integrated circuit

A network on a chip or network-on-chip is a network-based communications subsystem on an integrated circuit ("microchip"), most typically between modules in a system on a chip (SoC). The modules on the IC are typically semiconductor IP cores schematizing various functions of the computer system, and are designed to be modular in the sense of network science. The network on chip is a router-based packet switching network between SoC modules.

Jingsheng Jason Cong is a Chinese-born American computer scientist, educator, and serial entrepreneur. He received his B.S. degree in computer science from Peking University in 1985, his M.S. and Ph. D. degrees in computer science from the University of Illinois at Urbana-Champaign in 1987 and 1990, respectively. He has been on the faculty in the Computer Science Department at the University of California, Los Angeles (UCLA) since 1990. Currently, he is a Distinguished Chancellor’s Professor and the director of Center for Domain-Specific Computing (CDSC).

Giovanni De Micheli is Professor and Director of the Institute of Electrical Engineering and of the Integrated Systems Centre at École Polytechnique Fédérale de Lausanne (EPFL), Switzerland. He is program leader of the Nano-Tera.ch program. Previously, he was Professor of Electrical Engineering at Stanford University. He holds a Nuclear Engineer degree, a M.S. and a Ph.D. degree in Electrical Engineering and Computer Science under Alberto Sangiovanni-Vincentelli.

<span class="mw-page-title-main">Physical design (electronics)</span>

In integrated circuit design, physical design is a step in the standard design cycle which follows after the circuit design. At this step, circuit representations of the components of the design are converted into geometric representations of shapes which, when manufactured in the corresponding layers of materials, will ensure the required functioning of the components. This geometric representation is called integrated circuit layout. This step is usually split into several sub-steps, which include both design and verification and validation of the layout.

<span class="mw-page-title-main">Floorplan (microelectronics)</span> Layout of major electronic circuit blocks

In electronic design automation, a floorplan of an integrated circuit is a schematic representation of tentative placement of its major functional blocks.

<span class="mw-page-title-main">Jacob K. White</span> American electronics engineer and professor

Jacob K. White is the Cecil H. Green Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. He researches fast numerical algorithms for simulation, particularly the simulation of circuits. His work on the FASTCAP program for three-dimensional capacitance calculation and FASTHENRY, a program for three-dimensional inductance calculations, is highly cited. He has also done extensive work on steady-state simulation of analog and microwave circuits. White was a significant early contributor to the development of Spectre and SpectreRF.

The Alpha 21464 is an unfinished microprocessor that implements the Alpha instruction set architecture (ISA) developed by Digital Equipment Corporation and later by Compaq after it acquired Digital. The microprocessor was also known as EV8. Slated for a 2004 release, it was canceled on 25 June 2001 when Compaq announced that Alpha would be phased out in favor of Itanium by 2004. When it was canceled, the Alpha 21464 was at a late stage of development but had not been taped out.

<span class="mw-page-title-main">Ken Kundert</span> Creator of Spectre, SpectreRF, and Verilog-A; pioneer of analog verification

Kenneth S. Kundert is an engineer that is notable for his work in the area of Electronic Design Automation (EDA). He studied electrical engineering at the University of California, Berkeley under professors Alberto Sangiovanni-Vincentelli and Robert G. Meyer and received his doctorate in 1989. During this time, he created the circuit simulator that eventually became the Advanced Design System from what is now PathWave Design and the Spectre circuit simulator from Cadence Design Systems.

<span class="mw-page-title-main">Farinaz Koushanfar</span> Computer scientist

Farinaz Koushanfar is an Iranian-American computer scientist whose research concerns embedded systems, ad-hoc networks, and computer security. She is a professor and Henry Booker Faculty Scholar of Electrical and Computer Engineering at the University of California, San Diego.

Lawrence Pileggi is the Coraluppi Head and Tanoto Professor of Electrical and Computer Engineering at Carnegie Mellon University. He is a specialist in the automation of integrated circuits, and developing software tools for the optimization of power grids. Pileggi's research has been cited thousands of times in engineering papers.

Signal Transition Graphs (STGs) are typically used in electronic engineering and computer engineering to describe dynamic behaviour of asynchronous circuits, for the purposes of their analysis or synthesis.

Luca P. Carloni is a professor and chair of the Department of Computer Science at Columbia University in the City of New York.. He has been on the faculty at Columbia since 2004. He is an international expert on electronic computer-aided design.

<span class="mw-page-title-main">Igor L. Markov</span> American computer scientist and engineer

Igor Leonidovich Markov is an American professor, computer scientist and engineer. Markov is known for mathematical and algorithmic results in quantum computation, work on limits of computation, research on algorithms for optimizing integrated circuits and on electronic design automation, as well as artificial intelligence. Additionally, Markov is a California non-profit executive responsible for aid to Ukraine worth tens of millions dollars.

References

  1. Feller, A. 1976. Automatic layout of low-cost quick-turnaround random-logic custom LSI devices. In Proceedings of the 13th Conference on Design Automation (San Francisco, California, United States, June 28–30, 1976). DAC '76. ACM Press, New York, NY, 79-85.
  2. Reed, J., Sangiovanni-Vincentelli, A., Santomauro, M.; A New Symbolic Channel Router: YACR2, Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, Vol.4, Iss.3, July 1985 Pages: 208- 219
  3. Braun, D., Burns, J., Davadas, S., Ma, H. K., Mayaram, K., Romeo, F., and Sangiovanni-Vincentelli, A. 1986. Chameleon: a new multi-layer channel router. In Proceedings of the 23rd ACM/IEEE Conference on Design Automation (Las Vegas, Nevada, United States). Annual ACM IEEE Design Automation Conference. IEEE Press, Piscataway, NJ, 495-502.
  4. Fang, S., Feng, W., and Lee, S. 1992. A new efficient approach to multilayer channel routing problem. In Proceedings of the 29th ACM/IEEE Conference on Design Automation (Anaheim, California, United States, June 08–12, 1992). Annual ACM IEEE Design Automation Conference. IEEE Computer Society Press, Los Alamitos, CA, 579-584