Browse Prior Art Database

Implementing Large Scale Functions

IP.com Disclosure Number: IPCOM000082072D
Original Publication Date: 1974-Sep-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Lewis, BA: AUTHOR [+2]

Abstract

A large-scale function can be implemented in hardware only by the interconnection or composition of smaller, more primitive functions. Thus, a classical problem of hardware design, whether the implementation is by relay contacts, hydraulic logic, or large-scale integration (LSI) is: given an assemblage of primitives determined by a chosen technology, how to compose these primitives so as to realize some large-scale function generally having memory in its operation. The composing is, of course, to be performed in an efficient manner both with regard to cost and speed. If such composing operation is to be performed automatically, i.e., by computer, then a formal symbolic definition of the function to be realized is necessary.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Implementing Large Scale Functions

A large-scale function can be implemented in hardware only by the interconnection or composition of smaller, more primitive functions. Thus, a classical problem of hardware design, whether the implementation is by relay contacts, hydraulic logic, or large-scale integration (LSI) is: given an assemblage of primitives determined by a chosen technology, how to compose these primitives so as to realize some large-scale function generally having memory in its operation. The composing is, of course, to be performed in an efficient manner both with regard to cost and speed. If such composing operation is to be performed automatically, i.e., by computer, then a formal symbolic definition of the function to be realized is necessary.

In this latter connection, a "high-level" notation, the R-notation as disclosed in "R-Notation and its Usage in Computer Design", J. P. Roth and L. S. Levy, RC 4658, December 20, 1973, published by the IBM Corporation, has been developed and which provides an effective and natural mechanism for precisely defining functions, algorithms, programs, etc. Concomitantly, a compiler, the "R- compiler", has been constructed which transforms an "R-algorithm" into a completely detailed, efficient hardware implementation.

A salient problem which arises in the automatic generation of large-scale functions in hardware and, particularly, in the LSI technology is that engineering changes are made at the low-level logic design level. The problem is to reflect this change back up to the high-level definition in, for example, the R-notation mentioned hereinabove.

One technique for effecting such change reflecting, i.e., such inverse operation, is the Pi *-algorithm as disclosed in "Computer Design/I", J. P. Roth, RA 45, December 22, 1972, pp. 143-178, published by the IBM Corporation, which is operative to transform a multiple-level design, in general, with feedback into a 2-level design (also generally with feedback) which is equivalent to the original design. The disadvantage presented by the use of the aforementioned pi*-algorithm is that, for sizable functions, the resulting 2-level design is or can be excessively large, even if its size is optimized.

In the technique described herein, an algorithm is employed which begins with a 2-level design, or a design composed of portions defined individually in two levels. The operation of the algorith...