In this article, we have thoroughly explored several critical aspects of partitioning in CMOS circuits. We began with a brief overview of partitioning, emphasizing its importance in the design flow. Next, we delved deeper into various levels and types of partitioning, highlighting why it is a crucial process. We also covered the fundamental rules of partitioning, drawing on graph theory to explain its principles. Additionally, we examined both pin and net-oriented netlists and concluded with detailed discussions on two different partitioning algorithms.
Design Flow and Partitioning:
VLSI design cycle is broadly categorized into Front End and Back End. Front end starts with system specification. FE defines the logical behavior according the functional specifications. At the end of FE we get technology mapped gate level netlist. BE starts from there and main focus of BE is to translate the circuit we have got in FE into Silicon wafer with proper placement of blocks , essential power lines routing and etc. After all these the process lead to tape out.
Partitioning is the initial step in the PD process. Partitioning is dividing a chip into smaller blocks. Different functional blocks are separated and routing and placement is simplified. The designer breaks the larger design into various smaller functional modules/blocks and then proceeds with implementation of these smaller modules during RTL design phase. These smaller functional blocks are structurally instantiated or linked in the main module. Main module is called TOP LEVEL module. This type of partitioning is called as Logical Partitioning.
What is Partitioning ?
To simplify complex integrated circuit designs, they are divided into smaller parts called modules. These modules can be as simple as a few electrical components or as complex as fully functional integrated circuits (ICs). A tool called a partitioner splits the circuit into smaller subcircuits/ partitions/blocks. It aims to reduce the number of connections between these partitions while adhering to design rules like maximum size and delay limits.
If each block is designed without considering the others, it can lead to problems. More connections between partitions can increase circuit delay and decrease reliability. Too many connections can create dependencies that slow down the design process. The main objective is to minimize connections between sub-circuits to improve performance and meet design constraints. Constraints may include limits on the logic size in a partition or the number of external connections (e.g., limited by the number of I/O pins on a chip). By following these points, designers aim to create efficient, reliable, and easily manageable integrated circuits.
Level of Partitioning :
Circuit Partitioning (CP) is an important task in VLSI design applications. Partitioning algorithms are used to achieve various objectives such as Circuit Layout, Circuit Packaging and Circuit Simulation.
Level Of Partitioning is as follows-
1. System Level Partitioning :
A system is partitioned into group of PCBs. Each sub-
system can be designed as single PCB.
2. Board level partitioning :
A PCB is partitioned into sub- circuits. Each subcircuit
fabricated as VLSI Chips.
3. Chip Level Partitioning : Circuit assigned to the chip is
divided into manageable sub circuits.
Why Partitioning is Important?
1. Physical packaging : Partitioning decomposes the system in order to satisfy the physical packaging constraints. The partitioning conforms to a physical hierarchy ranging from cabinets, cases, boards, chips, to modular blocks.
2. Divide and conquer strategy : Partitioning helps manage complex designs by breaking them into smaller parts. Thisapproach allows team members to work on different sections, creates a logical order for design, converts the netlist into a physical layout for planning, assigns cells to specific areas for placement and RLC extraction, and coordinates between logic and layout for simulation.
3. System emulation & Rapid Prototyping : One way to emulate and prototype a system is by using FPGAs to build the hardware. Since FPGAs usually have less capacity than modern VLSI designs, these prototype systems use a hierarchical setup of multiple FPGAs. A partitioning tool is necessary to map the netlist onto the hardware.
4. Hardware & Software Codesign : For hardware and software codesign, partitioning is used to decompose the designs into hardware and software.
5. Management of Design Reuse : For huge designs especially system-on-a-chip, we have to manage design reuse. Partitioning can identify clusters of the netlist and construct functional modules out of the clusters.
Rules of Partitioning :
3. Number of Terminals: The number of nets needed to connect a sub-circuit to other sub-circuits does not exceed the sub-circuit's terminal count.
4. Number of Partitions : A large number of partitions can simplify the design of individual sections, but it may also increase fabrication costs and the number of interconnections between partitions.
5. Are of each partition
After Circuit Partitioning :
- Area occupied by each partition is estimated
- Possible shapes of blocks can be ascertained
- Number of terminals required by each block is known
- Netlist specifying connections between block is available
Graph Theory & Partitioning :
Graphs are used in physical design algorithms to describe and represent layout topologies.
A graph G(V,E) is made up of two sets :
(1) Elements : Set of nodes or vertices denoted as V
(2) Edges : relations between the elements, denoted as E
Order of Hypergraph = Size of vertex set,
Size of Hypergraph = Size of the edges set
Pin & Net Oriented Netlist:
(i) Pin-oriented: each design component has a list of associated nets
Netlists are created during logic synthesis and are a key input to physical design. A connectivity graph is a representation of the netlist as a graph. Cells, blocks and pads correspond to nodes, while their connections correspond to edges.
Partitioning Algorithm:
A cell is any logical or functional unit built from component. A partition or block is a grouped collection of components and cells. The k-way partitioning problem seeks to divide a circuit into k partitions. The most common partitioning objective is to minimize the number or total weight of cut edges while balancing the sizes of the partitions. Often, partition area is limited due to packing considerations and other boundary conditions implied by system hierarchy, chip size, or floorplan restrictions. Circuit partitioning, is very hard to solve. As the problem gets bigger, the time needed to find the best solution grows very quickly. There is no known fast and perfect method to solve balance- constrained partitioning.
There are two types of partitioning methods:
1. Constructive or Iterative Method : A constructive algorithm creates a partitioning from the graph that represents the circuit or system. Iterative methods work to improve the quality of an already existing partitioning solution.
2. Deterministic or Probabilistic Method : Deterministic programs always produce the same solution each time they run. Probabilistic methods give different solutions each time because they use random numbers.
Methods, like the Kernighan-Lin (KL) algorithm and the Fiduccia-Mattheyses (FM) algorithm, can find good solutions and run relatively quickly. Optimization using simulated annealing can address particularly challenging partitioning problems. KL algorithm is sensitive to the number of nodes and edges. The KL algorithm performs partitioning through iterative improvement steps.The KL algorithm is based on exchanging (swapping) pairs of nodes, each node from a different partition.
FM algorithm is sensitive to the number of nodes and nets (hyperedges). The FM algorithm is typically applied to large circuit netlists. This algorithm is more naturally applicable to partitions of unequal size or the presence of initially fixed cells. FM algorith offers best tradeoff between solution quality and runtime.
Partition area is limited by packing considerations and other boundary conditions such as chip size, or floorplan restrictions. Commercial Tool uses command line options or a GUI to create and manage partitions. Changes the net-list tree structure to create hierarchy nodes at the top level that can be physically divided. This ensures that the nodes are evenly sized and reduces the number of top-level connections needed for the hierarchy blocks. Finds the best way to divide a design into blocks that can be worked on separately. Makes sure the partitions are balanced by size or number of instances. Reduces the number of top-level connections between block I/O ports. Ensures the netlist is partitioned without changing how it works.
Watch the video lecture here:
Courtesy: Image by www.pngegg.com
