The Core Problem: Why Partition at All?

Modern ICs can contain billions of transistors. Designing such a system all at once is practically
impossible — it would be like trying to build an entire city without ever dividing the work among
architects, engineers, and contractors.

Partitioning solves this by cutting the big circuit into smaller, manageable pieces called blocks or
subcircuits, so that each piece can be designed, verified, and optimized independently.

The partitioner is a software tool (an EDA — Electronic Design Automation tool), not a human.

Here is why this makes sense. A modern IC can contain anywhere from millions to billions of logic
cells. The number of possible ways to divide those cells into blocks is astronomically large — no
human could evaluate even a tiny fraction of those combinations manually, let alone find a near-
optimal solution in a reasonable time. So algorithms are used to do this automatically.

The partitioning software takes as input a netlist (a description of all the logic cells and how they are
connected), along with the design constraints (maximum block size, maximum pin count, etc.), and
then runs optimization algorithms — such as Kernighan-Lin, Fiduccia-Mattheyses, spectral methods,
or multilevel partitioning — to find a good division of the circuit that minimizes inter-block
connections while satisfying all constraints.

The human's role in this process is limited to:

 Setting up the constraints and objectives (e.g., "each block must fit in this FPGA, with no
more than 512 I/O pins")

 Choosing which partitioning algorithm or tool to use

 Reviewing and approving the result

 Manually tweaking the partition boundaries in exceptional cases if the tool's output is
unsatisfactory

So in short — the heavy computational work of partitioning is entirely done by the software tool. The
human provides guidance at the beginning and reviews the outcome at the end.

What Does a Partitioner Actually Do?

Think of the circuit as a network of cities connected by roads. The partitioner draws boundaries on
this map, grouping cities into regions (blocks). The key goal is:

Minimize the number of roads that cross the boundary between regions, while keeping each region
a reasonable size.

In circuit terms, the "roads" are wires/connections between logic cells, and the "boundaries" are the
block interfaces. Connections that cross block boundaries are called inter-block connections, and
they are expensive — they add delay, consume I/O pins, and create dependencies between blocks
that slow down the design team.
Why Are Inter-Block Connections Bad?
Three concrete reasons:

Circuit Delay. A signal traveling between two blocks must cross a physical boundary, often over a
longer wire, through a buffer, or via a package pin. Each of these adds propagation delay. If a timing-
critical path crosses many block boundaries, the overall circuit becomes slow.

Reliability. Long inter-block wires are more susceptible to noise, crosstalk, and signal integrity issues
compared to short, local wires within a block.

Design Productivity. When block A's output feeds block B, the teams working on A and B become
interdependent. One team cannot finalize their design until the other's interface is frozen.
Minimizing such connections keeps teams working in parallel without blocking each other.

Design Constraints the Partitioner Must Respect

Minimizing connections alone is not enough. The partitioner must also satisfy hard constraints:

Maximum partition size. For example, if each block is going to be implemented on a separate FPGA
chip, the number of logic gates in a partition cannot exceed what the FPGA can hold. You cannot
pack an unlimited amount of logic into one block just because it reduces connections.

Maximum number of external pins. Every signal crossing a block boundary needs a physical I/O pin
on the chip package. Chip packages have a finite number of pins (e.g., 256, 512, 1024). If a block has
too many inter-block connections, it runs out of pins. This is a hard physical limit.

So the partitioner is solving an optimization problem — minimize inter-block connections, subject to

size and pin-count constraints per block.

Rent's Rule — The Empirical Pattern Behind Partitioning

Once engineers started partitioning real designs, they noticed a consistent pattern across many well-
designed ICs. IBM engineer E.F. Rent observed:
r
n P=t ⋅nGWhere:

Symbol Meaning

nP Number of external connections (pins) of a block

nG Number of logic cells (gates) inside that block

t Average number of pins per cell (a technology constant) pins means both Inputs and Output

r Rent's exponent (a constant, always less than 1)

Numerical Intuition
Take r =0.6, t=2.
0.6
Gates nG Pins n P=2 × nG

10 ~8

100 ~32

1000 ~126

10000 ~502

Gates grew 1000× (from 10 to 10,000), but pins only grew about 63×. This is the power of r <1— pins
grow far slower than gates.

What r Value Tells You

Rent's Exponent
Meaning
r

Close to 0 Very local design — gates mostly talk to neighbors, very few external pins needed

0.5 – 0.8 Typical well-designed hierarchical IC

Communication-intensive — gates talk widely across the chip, hard to partition

Close to 1
cleanly

At every level of hierarchy, most signals stay inside that level. The full adder cells talk mostly to each
other inside the adder. The adder talks mostly within the ALU. Only a small number of signals need to
go outside the processor block entirely. This is why the number of external pins is always much
smaller than you would expect if communication were random.

A random circuit with no hierarchy would have r ≈ 1— every gate talks to every other gate with
equal probability, so pins would grow linearly with gates. Real well-designed circuits have r between
0.5 and 0.8.

Graph Theory Terminology

Directed vs Undirected Graphs — Quick Recap

Before the new terms, note that graphs can be:

 Undirected — edges have no direction, just a connection between two nodes

 Directed — edges have arrows, meaning signal/data flows in one specific direction (like a
wire driving a gate input — current flows one way)

Cyclic and Acyclic Graphs

Cyclic graph — a directed graph that contains at least one directed cycle, meaning you can start at a
node, follow the arrows, and return to the same node.