The purpose of this correspondence is to provide an example computer logic graph and data concerning various partitions and mappings of this graph. This information should be of particular interest to those workers who are developing partitioning and mapping algorithms, since it provides a means to test and compare alternative methods. It should also be of use to those interested in other algorithms (e.g., placement, diagramming, grouping, etc.) for logic graphs.

A key problem in the effective use of large-scale integration is the design and partitioning of computer logic to achieve sufficiently high circuit-to-pin ratios. In this paper a power-law relationship between pins and partitioned circuits is discussed and empirical evidence is presented that implies that the pin requirement is a sensitive function of the performance level of the logic. Two techniques for increasing the circuit-to-pin ratio are discussed. The first is to serialize the interchip transfer of information that results in a degradation in performance of the logic. The second is to encode the information to be transferred so that fewer pins are required but without reducing the performance. The results of experiments using the encoding principle to map a small logic graph onto chips are presented to obtain an indication of the effectiveness of this technique. It is shown that the relationship between circuits and pins when using encoding remains a power law.

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.

A heuristic procedure for partitioning or mapping a set of interconnected blocks into subsets called modules is presented. Each module may be constrained in terms of the number of blocks and/or the number of intermodule connections that it can accommodate. The procedure allows given blocks to be mapped to more than one module in order to reduce the number of modules required if such reduction is desirable. Results obtained from applying the procedure, by means of a computer program, to the partitioning and mapping of computer logic gates into chips and cards are presented.

It is shown that by using minimum distance three state assignments and considering error states when deriving the input equations, counters tolerant of a single error can be synthesized. Although one flip-flop in the counter might be in error, the other flip-flops will continue to sequence correctly. Thus acceptable sequencing continues with a malfunctioning unit present in the circuit. Because of the error correcting properties of the state assignment, the correct state of the counter can be recovered. A one-bit error introduced by noise or an intermittent malfunction will be automatically corrected. Failure occurs if more than one flip-flop is in error. Redundancy is incorporated as an inherent result of the initial design procedure rather than being included after a nonredundant working design is obtained. Instead of using any of the known methods of simplification of Boolean functions, the synthesis procedure involves the selection of a minimum number of terms which satisfy a concise set of distance and intersection properties. The selection procedure is intrinsically suitable for machine computation. Although specific logic units are discussed, it is believed that the concepts are general in nature and can be applied to any type of logic hardware.