AGAR: A single-layer router for gate array cell generation

Abstract

AGAR is a single-layer router which does internal wiring of gate array cells for a variety of technologies and background cell images. It starts by using image-specific heuristics to do a partial routing. The heuristics can be supplied by the circuit designer and may be coded using a rule-based shell or a standard programming language. The routing is completed using an image-independent algorithm which systematically generates legal routings on a virtual grid, in increasing order of cost, until a complete legal routing is found or the search fails. AGAR was used to generate the majority of the cells in a CMOS gate array cell library and to complete partial routings of bipolar gate array cells.