Q13VLSI Design

Euler Path in VLSI Layout Design

An Euler path (or Euler trail) in graph theory is a path through a graph that traverses every edge of the graph exactly once (visiting vertices possibly more than once, but never repeating an edge) - a graph possesses an Euler path if and only if it has exactly zero or exactly two vertices of odd degree (number of edges incident to that vertex), a classical result in graph theory.

In VLSI layout design specifically, the Euler path concept is applied to the design of series-connected transistor networks (such as the pull-up or pull-down network of a complex CMOS gate implementing an AOI/OAI Boolean function) to determine an ordering of the input signals along the polysilicon gate lines that allows the diffusion (source/drain) regions of adjacent transistors in the layout to be physically merged (shared) rather than requiring a separate diffusion break and metal contact between every pair of adjacent transistors.

To construct such an Euler path for a given series-parallel transistor network, the network's graph is formed by representing each transistor as an edge and each node (junction between transistors, plus the output node and the supply/ground rail) as a vertex; finding an Euler path through this graph that traverses every transistor (edge) exactly once, in an order such that each edge shares a vertex (a diffusion node) with the immediately preceding edge in the path, directly gives a valid ordering of gate inputs along a single, uninterrupted polysilicon strip with continuous, shared source/drain diffusion regions between consecutive transistors - crucially, if the SAME Euler path ordering (same sequence of input labels) works for BOTH the pull-up (PMOS) network and the pull-down (NMOS) network of a CMOS gate simultaneously, an extremely compact, minimum-diffusion-break layout can be achieved with all PMOS and all NMOS transistors sharing a common set of vertically-aligned polysilicon gate lines.

As a suitable example, consider a CMOS gate implementing a series-connected NMOS pull-down network for the function corresponding to three cascaded series transistors A, B, C between the output node and ground - the graph has vertices output, n1 (between A and B), n2 (between B and C), and ground, with edges A (output-n1), B (n1-n2), C (n2-ground); this simple linear chain already forms a trivial Euler path (output-A-n1-B-n2-C-ground) traversing each edge exactly once, giving the layout designer the direct gate-ordering A, B, C along a single continuous diffusion strip. For more complex series-parallel networks (such as those implementing a full AOI221-type Boolean function with both series and parallel transistor groupings), finding a valid common Euler path ordering that works for both the PMOS and NMOS networks simultaneously (since the two networks are logically dual to each other, having the same graph topology) is a standard, systematic technique taught in VLSI physical design courses specifically to minimize layout area by maximizing diffusion sharing and minimizing the number of separate diffusion islands and metal contacts required, directly reducing both silicon area and parasitic diffusion capacitance (which would otherwise slow down circuit switching speed) in the final chip layout.