Browse Prior Art Database

Interactive Software System for Partitioning of Computer Logic

IP.com Disclosure Number: IPCOM000085953D
Original Publication Date: 1976-Jun-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 3 page(s) / 41K

Publishing Venue

IBM

Related People

Hanan, M: AUTHOR [+3]

Abstract

The mapping or partitioning of a set of circuits onto large-scale integration (LSI) chips is one of the key problems in taking advantage of the potential low cost of LSI logic. An interactive capability containing computational power and manually-initiated tactical decision making is presented here as one solution to this key problem.

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 52% of the total text.

Page 1 of 3

Interactive Software System for Partitioning of Computer Logic

The mapping or partitioning of a set of circuits onto large-scale integration (LSI) chips is one of the key problems in taking advantage of the potential low cost of LSI logic. An interactive capability containing computational power and manually-initiated tactical decision making is presented here as one solution to this key problem.

The system operates under a time sharing system (TSS) after receiving an initial partitioning from a batch operated CPU, as shown schematically in Fig. 1. An alphanumeric graphic display provides the designer with updated information concerning the progress of his work, while instructions re entered on a keyboard terminal and short instantaneous print output is obtained at the typewriter.

ALMS/360 is a batch oriented partitioning capability which comprises the 360/91 batch partitioning part of this system. See "A Heuristic Procedure for Partitioning and Mapping of Computer Logic Graphs", R. L. Russo, P. H. Oden,
P. K. Wolff, Sr., IEEE Transactions on Computers, Vol. C-20, Number 12, December 1971, pp. 1455-1462 for a detailed description. "The Iterative- Improvement Algorithm for Partitioning and Mapping of Computer Logic," M. Hanan, P. K. Wolff, Sr., defensive publication No. T944,001 of March 2, 1976 Official Gazette, comprises part of the iterative portion of the system on the TSS. Several other key capabilities are added to this basic set of algorithms, to take advantage of the alphanumeric display capability available under the TSS.

This interactive system relies strongly on the characteristics of the vertex allocation program-VAP-used in ALMS/360 (as well as on the latter's vertex generation program, which groups circuits into vertices according to topological criteria). The input parameters to VAP are: the number of chips, the maximum number of pins per chip to be used (P(max)), the maximum number of circuits per chip to be allowed (C(max)), the maximum number of vertices per chip to be allowed (V(max)), and the number of trials to be made. The output of VAP is an allocation of vertices to modules, which attempts to satisfy these global constraints.

Given an initial ALMS/360 partitioning as input, the approach here is to improve the existing partition by small perturbations rather than recomputation. Removal of one or...