On a Pin Versus Block Relationship For Partitions of Logic Graphs

TLDR

Partitions of logic graph blocks into modules reveal a two‑region relationship between the average pins per module (P) and the average blocks per module (B). The authors performed controlled partitioning experiments on four logic graphs (500–13,000 circuits) from three computers, varying block sizes from single NOR gates to 30‑circuit chips, using a computer program to generate the partitions. They found that in the first region P = KBr (with 0.57 ≤ r ≤ 0.75), while in the second region (1–5 modules) P falls below this prediction and follows a more complex relationship.

Abstract

Partitions of the set of blocks of a computer logic graph, also called a block graph, into subsets called modules demonstrate that a two-region relationship exists between P, the average number of pins per module, and B, the average number of blocks per module. In the first region, P = KBr, where K is the average number of pins per block and 0.57 ≤ r ≤ 0.75. In the second region, that is, where the number of modules is small (i.e., 1-5), P is less than predicted by the above formula and is given by a more complex relationship. These conclusions resulted from controlled partitioning experiments performed using a computer program to partition four logic graphs varying in size from 500 to 13 000 circuits representing three different computers. The size of a block varied from one NOR circuit in one of the block graphs to a 30-circuit chip in one of the other block graphs.