Browse Prior Art Database

Module Allocation Technique

IP.com Disclosure Number: IPCOM000074195D
Original Publication Date: 1971-Mar-01
Included in the Prior Art Database: 2005-Feb-23
Document File: 3 page(s) / 39K

Publishing Venue

IBM

Related People

Gurski, CS: AUTHOR [+2]

Abstract

A module allocation technique is described which implements logic using the general purpose modules of Fig. 1, which consist of circuits with input interconnection. The general purpose modules consist of AND-Invert circuits with input interconnections.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Module Allocation Technique

A module allocation technique is described which implements logic using the general purpose modules of Fig. 1, which consist of circuits with input interconnection. The general purpose modules consist of AND-Invert circuits with input interconnections.

The basic input can be described in the injective word format as in Fig. 2.

The algorithms used are heuristic, and therefore, do not always yield an optimum answer.

The order of implementation is from blocks with the greatest number of inputs to blocks with the smallest number of inputs. In this way, if any allocated modules have not been fully utilized, the residual circuits of these modules may be used when blocks with fewer inputs are considered.

For the purpose of discussion, assume the program is at a point where it is implementing blocks with n-inputs. There will only be a subset of module types with which the implementation is possible, since only those module types which consist of circuits with n or more inputs may be used. The most efficient implementation is obtained when an n-input block is implemented with an n-input circuit. Therefore, to obtain the most efficient implementation, the program must group n-input blocks with other blocks (not necessarily with n-inputs) in such a way that the circuits forming these groups share an appropriate number of inputs. From all such feasible groups a selection is made that attempts to implement as many n-input blocks as possible. A selection of groups achieving implementation of the greatest number possible of n-input blocks is called a maximum covering set. If after generating the first covering set there are any n-input blocks left, then groups are made which are now the best possible implementation, and a covering set for these groups is again determined. This procedure is continued until no input interconnection between remaining n-input blocks and other blocks is possible. Any remaining n-input blocks after the procedure is completed are implemented as best possible.

Assume we are implementing four-input blocks. This implies that all blocks with more than four inputs have been implemented. The modules that can be used are F, G, H. The least wasteful implementation is to assign pairs of four- input blocks and three-input blocks with one common input to F modules. The second best implementation is to assign pairs of four- and two-input blocks with one common input also to F modules, or to assign groups of three four-input blocks with one common input to G modules. In either of these two...