### Abstract

In this paper, we consider a board-level routing problem which is applicable to FPGA-based logic emulation systems such as the Realizer system [3] and the Enterprise Emulation System [5] manufactured by Quickturn Systems. For the case where all nets are two-terminal nets, we present an O(n^{2})-time optimal algorithm where n is the number of nets. Our algorithm guarantees 100% routing completion if the number of inter-chip signal pins on each FPGA chip in the logic emulation system is less than or equal to the number of I/O pins on the chip. Our algorithm is based on iteratively finding Euler circuits in graphs. We also prove that the routing problem with multi-terminal nets is NP-complete.

Original language | English (US) |
---|---|

Pages (from-to) | 552-556 |

Number of pages | 5 |

Journal | Proceedings - Design Automation Conference |

State | Published - Jan 1 1995 |

Externally published | Yes |

Event | Proceedings of the 32nd Design Automation Conference - San Francisco, CA, USA Duration: Jun 12 1995 → Jun 16 1995 |

### Fingerprint

### ASJC Scopus subject areas

- Hardware and Architecture
- Control and Systems Engineering

### Cite this

*Proceedings - Design Automation Conference*, 552-556.