Performance-constrained component selection

Apparatus and methodology solve a performance-constrained component selection problem. The method includes articulating a set of constraints comprising inter alia specifying particular processes to be performed in relation to an end-task, and comprising time, cost, and functional unit constraints, and, determining a minimal-cost implementation of the functional units which realize the processes and satisfies the constraints.

FIELD OF THE INVENTION 
This invention relates to apparatus and methodology for addressing a 
performance-constrained component selection problem. 
BACKGROUND OF THE INVENTION 
This invention deals with a problem of selecting a minimal cost set of 
components (e.g., arithmetic units, flip-flops, memory units, etc.) for 
implementing a system subject to given performance conditions. 
SUMMARY OF THE INVENTION 
Preliminarily, we note that while the methodology disclosed in this 
invention is applicable to a general class of component selection problems 
in a variety of system design applications, we address (for the sake of 
pedagogy) a specific problem comprising an implementation of registers in 
computers. A statement of this problem is articulated shortly below, and 
is referenced to the following (5) constraints: 
(1) A set of registers required for the computer under design. 
(2) For each of the registers, a list of possible hardware implementations. 
(3) For each of the implementations, cost, and performance measures 
(running or delay times of the components). 
(4) A set of processes, each one designated by a graph representing the 
register transfer flow of information. The nodes of the graph represent 
the names of the registers used by the process and the branches represent 
the flow path from register to register. Multiple branches implies 
simultaneous parallel routs of flow for the process. 
(Note that the graph can be replaced by a sequence of names of registers, 
and is so regarded in the formulation of the problem, infra. The rules for 
the transformation are as follows. If there are no multiple branches from 
a node, then the successor node (register) is listed separated by a comma 
from the preceding node. Multiple branches from a node are represented by 
enclosing by parentheses the alternate flow paths prior to their merging 
to a common node, and within the parentheses, separating by a semi-colon 
the subsequences of nodes in each alternative path. For example, see the 
illustrative graph in FIG. 1, numeral 10.) 
(5) For each process, an associated time bound for its completion. The 
running time, or delay, of the process is given by the sum of the delays 
of the nodes (registers) outside of the parentheses plus, within the 
parentheses, the maximum of the sum of the delays of each subsequence 
separated by semi-colon. More generally, other design applications call 
for different delay functions according to the process being modeled. For 
example, in communication systems, where the nodes represent message 
processing units, the minimum of the sum of the delays, rather than the 
maximum, would be an appropriate delay function for the subsequence inside 
the parentheses. The interpretation then is that the process is satisfied 
if a message is received via any branch rather than over all multiple 
(parallel) branches. See FIG. 1. 
Our problem, then, as referenced to the cited (5) constraints, is the 
following: 
Find the minimum cost register implementation subject to the condition that 
each process, according to its register usage, can be completed within its 
time bound. 
We believe our problem to be uniquely posed, with reference to the prior 
art, and to be solved, in a first aspect, by a digital computer dedicated 
to solving a performance-constrained component selection problem, the 
computer comprising: 
1) means for inputting to a central processing unit information comprising: 
(1) a matrix M=(M.sub.ij), where each row represents a functional unit, and 
the elements of each row designate a specific implementation of the 
functional unit; 
(2) a cost function C(M.sub.ij) defined on each element of M; 
(3) a performance time delay function E(M.sub.ij) defined on each element 
of M; 
(4) a set of processes P.sub.1, P.sub.2, . . . , P.sub.s, where each 
P.sub.k comprises a sequence of functional units, thereby defining a 
subsequence of row in M; 
(5) a set of time tolerances t.sub.1, t.sub.2, . . . , t.sub.s, associated 
with the s processes; 
2) means for selecting in the central processing unit exactly one element 
out of each row of M, such that .SIGMA. (C(M.sub.ij)) is minimal over 
selected elements of M, subject to .SIGMA. (E(M.sub.ij)).ltoreq..-+.tk, 
k=1, 2, . . . , s over selected elements in rows contained in Pk; and 
3) means for displaying the information corresponding to the one element. 
In a second aspect, the invention discloses a program storage device 
readable by a machine, tangibly embodying a program of instructions 
executable by the machine to perform method steps for 
performance-constrained component selection, said method steps comprising: 
1) specifying particular processes to be performed in in relation to an 
end-task; 
2) specifying a time constraint for each particular process given in step 
1); 
3) specifying a list of functional units to be used in the processes 
specified in step 1); 
4) specifying a list of candidate hardware implementations, for each of 
said functional units, to realize the step 1) processes; 
5) specifying an associated cost-measure with each candidate hardware 
implementation; 
6) specifying an associated performance-measure with each candidate 
hardware implementation; and 
7) determining a minimal-cost implementation of the set of functional units 
which realize the step 1) processes and which satisfy the step 2) through 
step 6) constraints. 
The advantages of the present invention, as defined, may be manifest by way 
of the following recital as to its applicability to important 
manufacturing tasks. For example, consideration of our problem and its 
solution are particularly important in special purpose computers dedicated 
to specific tasks, for example, the sequential processing of radar data. 
There, the "registers" actually might be computational units for 
coordinate transformations, shift registers for data packing and 
unpacking, and so on, as well as the usual arithmetic registers. The 
constraint on the sum of the delay times results from the real time 
demands of the application. Namely, each process must be performed before 
the acquisition of new data, thereby imposing time bounds upon the 
computer system. 
For a general purpose computer, the term register can be taken to mean the 
flip-flops comprising a set of registers. The flip-flop type must be 
specified as part of the design, and the ideal time to do so is 
immediately after the development of the implementing logic equations. The 
constraints on processing time, or sum of delays, are to be interpreted as 
constraints on the particular register operations and transfers 
(microsteps) comprising the definition of a computer instruction. For 
example, a multiplication instruction might have the requirement that it 
be completed within two microseconds. The totality of processes 
corresponds to the complete set of instructions in a general purpose 
computer.