US 5,201,057 AGrant
System for Extracting Low Level Concurrency From Serial Instruction Streams
Issue Date:1993-04-06
•33 Claims
•9 Drawing Sheets
Abstract
An architecture for a central processing unit (cpu) provides for the extraction of low-level concurrency from sequential instruction streams. The cpu includes an instruction queue, a plurality of processing elements, a sink storage matrix for temporary storage of data elements, and relational matrixes storing dependencies between instructions in the queue. An execution matrix stores the dynamic execution state of the instructions in the queue. An executable independence calculator determines which instructions are eligible for execution and the location of source data elements. New techniques are disclosed for determining data independence of instructions, for branch prediction without state restoration or backtracking, and for the decoupling of instruction execution from memory updating.
Metadata
Inventor
- Augustus K. Uht
Application Information
Application Number:US 4742478
Filing Date:1990-02-05
Priority Date:1987-01-22
Art Unit:232
Classifications
IPC:
G06F 704
Field of Search:
395800;560;375
Patent Drawings (9 sheets)
Description
BACKGROUND OF THE INVENTION
This invention relates to an improved architecture for a central processing unit in a general purpose computer, and, specifically, it relates to a method and apparatus for extracting low-level concurrency from sequential instruction streams.
A timeless problem in computer science and engineering is how to increase processor performance while keeping costs within reasonable bounds. There are three fundamental techniques known in the art for improving processor performance. First, the algorithms may be re-formulated; this approach is limited because faster algorithms may not be apparent or achievable. Second, the basic signal propagation delay of the logic gates may be reduced, thereby reducing cycle time and consequent execution time. This approach is subject not only to physical limits (e.g., the speed of light), but also to developmental limits, in that a significant improvement in propagation delay can take years to realize. Third, the architecture and/or the implementation of a computer can be reorganized to more efficiently utilize the hardware, such as by exploiting the opportunities for concurrent execution of program instructions at one or more levels.
High-level concurrency is exploited by systems using two or more processors operating in parallel and executing relatively large subsections of the overall program. Low-level (or semantic) concurrency extraction exploits the parallelism between two or more individual instructions by simultaneously executing independent instructions, i.e., those instructions whose execution will not interfere with each other. Low-level concurrency extraction uses a single central processor, with multiple functional units or processing elements operating in parallel; it can also be applied to the individual processors in a multiprocessor architecture.
Extraction of low-level concurrency starts with dependency detection. Two instructions are dependent if their execution must be ordered, due to either semantic dependencies or resource dependencies. A semantic dependency exists between two instructions if their execution must be serialized to ensure correct operation of the code. This type of dependency arises due to ordering relationships occurring in the code itself.
There are two forms of semantic dependencies, data and procedural. Procedural dependencies arise from branches in the input code. Data dependencies arise due to instructions sharing sources (input) and sinks (results) in certain combinations. Three types of data dependencies are possible, as illustrated in Table I. In the first type, a data dependency exists between instructions 1 and 2 because instruction 1 modifies A, a source of instruction 2. Therefore instruction 2 cannot execute in a given iteration until instruction 1 has executed in that iteration. In the second type, instruction 1 uses as a source variable A, which is also a sink for instruction 2. If instruction 2 executes before instruction 1 in a given iteration, then it may modify A and instruction 1 may use the wrong input value when it executes. In the third type, both instructions write variable A (a common sink). If instruction 1 executes last, an unintended value may be written to variable A and used by subsequent instructions.
In the prior art, all three types of data dependencies have generally been enforced. Although the effects of the first type of data dependency can never be avoided, the effects of the second and third types can be reduced if multiple copies of a variable exist. However, prior art efforts to reduce or eliminate the effects of type 2 and type 3 data dependencies suffer from undesirable implementation features. The algorithms for instruction execution are essentially sequential, requiring many steps per cycle, thereby negating any performance gain from concurrency extraction. The prior techniques also only allow one iteration of an instruction to execute per cycle and are potentially very costly.
Further, in the prior art, branch prediction techniques have been used to reduce the effects of procedural dependencies by conditionally executing code beyond branches before the conditions of the branch have been evaluated. Since such execution is conditional, some code-backtracking or state restoration has heretofore been necessary if the branch prediction turns out to be wrong. This complicates the hardware of machines using such techniques, and can reduce performance in branch-intensive situations. Also, such techniques have usually been limited to conditionally executing one branch at a time.
SUMMARY OF THE INVENTION
The present invention provides a system for concurrency extraction, and particularly for reduction of data dependencies, which exploits a nearly maximal amount of concurrency at high speed and reasonable cost. The concurrency extraction calculations can be performed in parallel, so as not to negate the effects of increased concurrency. The system can be implemented at reasonable cost in hardware with low critical path gate delays.
Accordingly, the invention provides a central processing unit for executing a series of instructions in a computer. The central processing unit includes an instruction queue for storing a series of instructions, a plurality of processing elements for executing instructions, a loader for loading instructions into the instruction queue, a sink storage matrix for storing the results of the execution of multiple iterations of instructions, and an interconnect switch for transmitting data elements to and from the processing elements. As instructions are loaded into the instruction queue, a set of relational matrices are updated to indicate data and domain relationships between pairs of instructions in the queue. As instructions are executed, execution matrices are updated to indicate the dynamic execution state of the instructions in the queue. The execution matrices distinguish between real (actual) execution of instruction iterations and virtual execution (the disabling of instruction iterations as a result of branch execution). The relational matrices include data dependency matrices indicating source-sink (type 1) data dependencies separately for each source element in each instruction in the queue.
According to the invention, an executable independence calculator uses the information in the relational matrices and the execution matrices to select a set of instructions for execution and to determine the location of source data elements to be supplied to the processing elements for executing the executably independent instructions. Data executable independence exists when all source elements needed for execution of an instruction iteration are present in either sink storage or memory. The central processing unit thus achieves data-flow execution of sequential code. The code executed by the invention consists of assignment statements and branches, as those terms are understood in the art.
The invention provides for the decoupling of instruction execution from memory updates, by temporarily storing results in the sink storage matrix and copying data elements from sink storage to memory as a separate process. This decoupling improves performance in two ways: a) by itself, in that it has been established in the prior art that decoupled memory accesses and instruction executions may be performed concurrently; and b) by allowing branch prediction, in which it is possible to conditionally execute multiple branches, and instructions past the branches, with no state restoration or backtracking required if the branch prediction turns out to be wrong.
BRIEF DESCRIPTION OF THE FIGURES
FIG. 1 is a block diagram of a computer system for practicing the invention.
FIG. 2 is a block diagram of the central processing unit of FIG. 1.
FIG. 3 is a diagram of the instruction queue of FIG. 2.
FIG. 4 is a diagram of the branch format in memory.
FIG. 5 is a diagram of the assignment instruction format in memory.
FIG. 6 is a diagram of the instruction format in the IQ.
FIG. 7 is a diagram of the relational matrices of FIG. 2.
FIG. 8 is a diagram of the basic machine cycle.
FIG. 9 is a diagram of two instructions and their data dependency relationships.
FIGS. 9A-9C illustrate the conceptual arrangement of dependency matrices.
FIG. 10 is a model of the nominal instruction execution order of the instructions in the instruction queue.
FIG. 11 illustrates the method for determining an instruction's source data, according to the invention.
FIG. 12 is a diagram of an Advanced Execution Matrix illustrating the branch prediction technique.
FIG. 13 is an illustration of PD1 and PD2.
FIG. 14 is an illustration of PD3.
FIG. 15 is an illustration of PD4.
FIG. 16 is an illustration of PD5.
FIG. 17 is an illustration of PD6.
FIG. 18 is a diagram of nested forward branches.
FIG. 19 is a diagram of statically later FB.
FIG. 20 is a diagram of a statically later BB, SD disjoint.
FIG. 21 is a diagram of a statically later BB, enclosing.
FIG. 22 is a diagram of a universal structural code example.
FIG. 23 is a diagram of nested BBs.
FIG. 24 is a diagram of overlapped FBs.
FIG. 25 is a diagram of FB domain overlapped with previous BB domain.
FIG. 26 is a diagram of BB domain overlapped with previous FB domain.
FIG. 27 is a diagram of overlapped BBs.
FIG. 28 is a diagram of chained branches.
FIG. 29 is a diagram of multiply overlapped branches.
FIG. 30 is an illustration of OOBFB.
FIG. 31 is a diagram of the multiple OOBFB execution truth-table.
DESCRIPTION OF THE PREFERRED EMBODIMENT
FIG. 1 is a block diagram of a computer system 10 for practicing the invention. At a high level, as seen by the user and the user's application programs, computer system 10 comprises a main memory 12 for temporarily storing data and instructions, a central processing unit (cpu) 14 for fetching instructions and data from memory 12, for executing the instructions, and for storing the results in memory 12, and an I/O subsystem 16, for permanent storage of data and instructions and for communicating with external devices and users. I/O subsystem 16 is connected to memory 12 and/or directly to CPU 14. Memory 12 may include data and instruction caches in addition to main storage.
FIG. 2 is a block diagram illustrating central processing unit 14 at a more detailed level (transparent to user applications). CPU 14 includes an instruction queue (IQ) 18 for storing a sequential stream of instructions, a loader 20 for decoding instructions from memory 12 and loading them into IQ 18, and a plurality of processing elements (PEs) 22. The CPU of the present invention executes all code consisting of assignment statements and/or branches. One or more instructions in IQ 18 are issued and executed (concurrently, when possible) by processing elements 22. Each processing element has the functionality of an Arithmetic Logic Unit (ALU) in that it may perform some instruction interpretation and executes any non-branch instruction. Processing elements 22 receive instruction operation codes directly from IQ 18.
CPU 14 further comprises an interconnect switch 24 (typically a crossbar) and an internal data buffer (shadow sink matrix) 26. Interconnect switch 24 receives operand addresses and immediate operands from IQ 18 and couples data from the appropriate location to a processing element. Instruction operand (source) data may come from instruction contents (immediate operands), from memory 12, or from a buffer storage location in internal cpu buffer 26. Instruction output (sink) data is written into buffer 26 via interconnect 24.
CPU 14 further comprises an executable independence calculator (EIC) 28, a resource dependency filter 30, a branch execution unit 32, relational matrices 34, and memory update logic 36. Branch execution unit 32 includes execution matrices 38 for storing the dynamic execution state of the instructions in IQ 18. Relational matrices 34 are updated by the loader 20 whenever new instructions are loaded, to indicate data dependencies, procedural dependencies, and procedural (domain) relationships between instructions in IQ 18. Each execution cycle, executable independence calculator (EIC) 28 determines which instructions in IQ 18 are semantically executably independent (and thus eligible for execution), using the information contained in the relational matrices 34 and execution matrices 38. EIC 28 also determines the location of source data (memory 12 or internal cpu storage 26) for eligible instructions. The vector of semantically independent instructions eligible for execution is passed to the resource dependency filter 30, which reduces the vector according to the resources available to produce a vector of executably independent instructions. The vector of executably independent instructions is sent to IQ 18, gating the instructions to the processing elements, and to branch execution unit 32. Resource dependency filter 30 updates execution matrices 38 to reflect the execution of the executably independent instructions. The execution of branch instructions by branch execution unit 32 also updates execution matrices 38. Memory update logic 36 controls the updating of memory 12 from internal CPU buffer 26, based on information from relational matrices 34 and execution matrices 38.
An instruction is semantically executably independent if all of the instructions on which it is semantically dependent have executed, so as to allow the instruction to execute and produce correct results. Semantic dependence includes data dependence and procedural dependence. Data dependencies arise due to instructions sharing source (input) and sink (result) names (addresses) in certain combinations. Procedural dependencies arise as a result of branch instructions in the code. Data dependencies are the principal concern of the present invention.
A system for determining procedural independence is described in applicant's co-pending commonly assigned U.S. patent application "Improved Concurrent Computer," Ser. No. 807,941 filed Dec. 11, 1985, now abandoned, the disclosure of which is hereby incorporated by reference. That system is modified as described below for use in the preferred embodiment of the present invention.
The equation determining semantically executable independence is the same as in the original system except, as modified, independence is calculated for each iteration of every instruction. The component executable independence equations are somewhat different, however. The procedurally executable independence calculations require new but similar hardware to that used before; however, the IE (iteration enabled) logic array is no longer used. Note that if IQ.sub.j is procedurally dependent on IQ.sub.j, IQ.sub.j is a BB, and iteration i of IQ.sub.i is being considered for execution, then AE.sub.j,i through AE.sub.j,k must equal one (be virtually or really executed) before IQ.sub.i may execute in iteration k. In other words, all iterations of the BB prior to and including that of IQ.sub.i eligible for execution, must have executed. This is to ensure that the BB has fully executed before dependent instructions execute; otherwise, the dependent instructions may execute while iterations of the BB are pending, leading to erroneous results.
If IQ.sub.j is a FB, with the other conditions the same, then only AE.sub.j,k must equal one before IQ.sub.i may execute in iteration k. The latter requires that the overlapped FB procedural dependencies be separated from PBDE for maximal concurrency. Therefore assume that an OFBDE (overlapped forward branch dependency) matrix (like the other dependency matrices) holds the overlapped FB procedural dependencies, in the same elements as they were held in in PBDE. The matrix PBDE holds the remaining dependencies originally kept in PBDE; these procedural dependencies are only on backward branches.
For the BBEI calculation, take:
indicating if all instruction i iterations to the left of and including column j have been executed.
The, for i=row(u):
For all u.vertline.1.ltoreq.u.ltoreq.nm,
In words, an instruction is backward branch executably independent when: if it is BB, all previous iterations have been executed; and regardless when: all BB procedural dependencies have been resolved; any BB on which the instruction is dependent must have executed in all iterations up to and including that of u. An instruction is forward branch executably independent when the FB procedural dependencies indicated by both the forward branch domain matrix and the overlapped forward branch dependency matrix are resolved; any FB on which the instruction is dependent must only have executed in the iteration of u(col(u)).
Execution of instructions in the preferred embodiment of the present invention is complicated by the presence of array accesses. Referring to Table II, not that I.sub.3 is data dependent on I.sub.2, and thus will not execute until I.sub.2 executes serially previously. But what if A(H) and A(B) refer to the same location (or similarly A(F) is the same as A(B)))? As presently formulated, the hardware will not necessarily cause I.sub.3 to source from I.sub.2, since only array base addresses and array indices are compared; the actual locations (the sum of the contents of an array base address and an index) are not compared (this is primarily a hardware cost constraint, although timing is also important).
TABLE II
1. D.rarw.A(F)
2. A(B).rarw.C
3. G.rarw.A(H)
Therefore logic to maintain the proper dependencies and allow the writing of shadow sink contents to memory at the right time is now developed. First, array accesses (and in particular array writes) are considered; at the end of the derivation the logic is generalized to include all sink writes. All array reads are made from memory. This can be avoided if 0(n.sup.2 m.sup.2) address comparators are provided to match array sources with array sinks, the addresses of which are not known until execute time; in this case the dependencies with previous array read instructions need not be made. The technique uses much less hardware and is more practical; no comparators are used (for a similar execute-time function).
The logic for write array sink enable (WASE) is now derived. There is one WASE element for each AE element. During each cycle, if WASE.sub.u =1, then SSI.sub.u is to be written into memory. The WASE logic checks for the appropriate data dependencies (real or potential, as described above) amongst array accesses. Note that for a given WASE.sub.u, the serially previous array reads that must be checked for resolved data dependencies are those for which serially later data dependencies hold. Therefore the following data dependency matrix is needed:
The "T" superscript indicates the normal matrix transpose operation. Its purpose here is to convert the normally serially data dependencies to serially later data dependencies.
Now, for 1.ltoreq.u.ltoreq.nm,
WASE.sub.u =1 iff [instruction u has been really executed and has not yet been stored ] [for all previous ARWI.sub.s instructions that are dependent on instruction u, WASE.sub.s =1 (their sinks are being written in the current cycle) or AST.sub.s =1 (their sinks have effectively been written)] [for all previous ARRI.sub.s instructions that are data dependent on instruction u, AE.sub.s =1 (they have effectively been executed)].
Take A, B, and C to be defined as follows (in the above definition of WASE, A corresponds to the first two terms, B corresponds to most of the second term, and C corresponds to the last term):
Then: ##EQU1##
It is desired to make WASE.sub.u independent of serially previous values, i.e., WASE.sub.s. Therefore various WASE values are not computed to derive WASE.sub.u logic independent of WASE.sub.s (s<u). Briefly, a form of WASE.sub.u independent of WASE.sub.s is inductively proven to be valid.
The induction is anchored as follows: ##EQU2## The inductive premise is now asserted:
Using the original logic for WASE.sub.u, it is not shown that the premise implies a similar relation for u>s. ##EQU3## Expanding the product series terms gives: ##EQU4## The B.sub.u-1 term and the terms in [ ] and { } are now combined. Calling B.sub.u-1 "d", the terms in [ ] "a", the term in { } "c", gives an equation of the form:
which reduces to:
Substituting, this is: ##EQU5##
Combining the remaining terms similarly gives logic of the form:
but the last product series is covered by the first series; therefore:
and the induction is proven.
Substituting for A, B, and C and simplifying gives:
For all u.vertline.1.ltoreq.u.ltoreq.nm,
A slight digression is now made to introduce a new vector, BV, derived from the b-element, determined as follows:
This may be implemented easily with a shift register, shifting right or left as the b-element is incremented or decremented (respectively).
The WASE logic is now generalized to accommodate all sink writes, not only array writes. The new logic is called write sink enable (WSE), and is given by:
For all u/1.ltoreq.u.ltoreq.nm,
The BV term in the above equation allows only valid sinks to be written, not those to the right of the column indicated by the b-element.
Array accesses are restrictive in the modified system, but not to the same degree as in the original system. In the implementation of the modified system, data dependency relation 3 (common sink) type array accesses may be executed concurrently, due to the presence of multiple sink copies (shadow sinks). However, since all array reads must be of necessity be made from memory, relation 1 and 2 type array accesses may not execute concurrently. In other words, any array accesses involving one or more array reads must be sequentialized; otherwise (with only array writes taking place) the accesses may proceed concurrently.
Referring to FIG. 3, a diagram of instruction queue (IQ) 18 is shown. IQ 18 comprises a plurality of shift registers. Instructions enter at the bottom and are shifted up, into lower numbered rows, as new instructions are shifted in and the upper instructions are shifted out. The order of instructions in the queue (from lower numbered rows to higher numbered rows) corresponds to the statically-ordered program sequence, e.g., the order of the code as exists in memory. The static order is independent of the control-flow of the code, i.e., it does not change when a branch is taken. Any necessary decoding of instructions is performed relatively statically, one instruction at a time, as an instruction is loaded. Each row i of IQ 18 holds the code data corresponding to instruction i, including the operation code(opcode) and operand identifiers, and the jump destination address if the instruction is a branch. IQ 18 holds n instructions; it may be large enough to hold an entire program, or it may hold a portion of a program. The instructions in IQ 18 are accessed in parallel via lines 19.
The formats of branch and assignment instructions are shown in FIG. 4 and FIG. 5. The fields are: OP (opcode); TA (target address); A (sink name); B (variable name which describes the condition for branches or source 1 for assignment instructions); and C (source 2 name). The addresses need only be partially specified in the memory, e.g., the TA field may actually contain a relative offset to the actual target address.
An actual instruction set may contain more information in a given machine instruction format, such as more sources or sinks. This is feasible as long as the extra hardware needed to perform the more complex data dependency checks is included in the semantic dependency calculator. The above formats are proposed as an example of a typical encoding only.
The format of all instructions in the IQ is shown in FIG. 6. The fields are: IA (instruction address); OP (opcode, possibly decoded); AA (sink address); BA (source 1 address); CA (source 2 address); flags (AF, valid sink address flag; BF, valid source 1 address flag; CF, valid source 2 address flag); and TA (target address). All addresses are assumed to be absolute addresses. The flags need only be one bit indicators, when equal to 1 implying a valid address. Their primary use is to allow either addresses or immediate operands to be held in the same storage; they are also set when an address field is not used, e.g., in branch instructions. One or more fields may not be relevant to a particular instruction; in this case they contain 0.
Returning to FIG. 2, loader 20 includes logic circuitry capable of constructing the relational matrices 34 concurrently with the loading of instructions into IQ 18. As an instruction is loaded into IQ 18, the instruction is compared (concurrently) with each instruction ahead of it in IQ 18, and the results are signalled to the relational matrices.
Each relational matrix is an array of storage elements containing binary values indicating the existence or non-existence of a data dependency, a procedural dependency or a domain relation between each of the n instructions in IQ 18. Each relational matrix can be triangular in shape, because the relationships are either unidirectional or reflexive. A seen in FIG. 7, each relational matrix preferably comprises n diagonal shift registers. This implementation aids loading of the matrices in that every time a new instruction is loaded into IQ 18, the new column of relationships is shifted in from the right and the existing columns shift one column to the left and one row upward, into proper position for future accesses. The top row, corresponding to the top instruction in IQ, is retired.
After the initial loading of the IQ and the relational matrices, loads can occur simultaneous with execution cycles. (The basic machine cycle of the preferred embodiment is described in detail in Table III.
TABLE III
1. loading the IQ
a. determination of absolute addresses
b. calculation of semantic dependencies and branch domains
c. partial or full decoding of machine instructions
2. Concurrency determination
a. determination of a set of instructions eligible for issuing (execution) in the current cycle, assuming infinite resources (e.g., processing element); this is the semantically executable independent instructions' calculation
b. if necessary, reducing the said set of instructions to a subset to match the resources available; this is the executably independent instrutions' calculation
3. parallel execution of said subset of instructions
4. AE, b update
5. GOTO 1.
Note that actions 2 and 4 may be overlapped with action 3. Action 1 may be pipelined, and in many cases will not need to be performed every cycle, e.g., when entire loop(s) are held in the IQ. Actions 2 and 4 must be performed sequentially to keep the hardware cost down. Hence their delays contribute to a probable critical path, and should therefore be minimized. See FIG. 8 for typical timing diagrams of the basic cycle, both with and without IQ loads.
In FIG. 8, each LOAD time corresponds to loading one instruction into the IQ, accomplishing the operations in action 1 (see Table III). Each EXECUTION CYCLE consists of the following sequential actions: 2a, 2b, 4. The assignment instructions found to be executably independent after action 2b are sent to processing elements at time A. The assignment instructions' executions are overlapped both with action 4 of the current execution cycle, and either actions 2a and 2b of the next execution cycle or, alternatively, following load cycles, if they occur. At time B either another execution cycle begins (see the top time-line in FIG. 8), or new instructions are loaded into the IQ (see the bottom time-line). The basic cycle repeats indefinitely.
Relational matrices 34 include domain matrices and procedural dependency matrices, such as those described in co-pending application Ser. No. 807,941, and data dependency matrices. The data dependency matrices of this embodiment will now be described. Referring to FIG. 9, the operand portions of two instructions 48 and 50 and the five possible data dependencies 51-55 are shown. (Instructions are shown with two sources and one sink.) Instruction 48 is previous to instruction 50 in IQ 18. For each pair of instructions in IQ 18, the five possible data dependencies are evaluated by comparing pairs of addresses. Each comparison determines an element in a binary upper triangular half matrix wherein each column indicates all of an instruction's data dependencies of a specific type (51-55) with respect to preceding instructions in the IQ. These matrices are, conveniently arranged as shown in FIG. 9A-9C, where DD1 combines source 1-sink dependencies (types 52 and 54 in FIG. 9), and DD2 combines source 2-sink dependencies (types 53 and 55 in FIG. 9), and DD3 includes type 51 sink-sink dependencies. All lower triangular matrices have been rotated about their diagonals from their original positions.
The data dependencies illustrated in FIG. 9 are the full set of data interrelationships between instructions which can affect concurrency extraction, corresponding to the three types shown and described with reference to Table I. If an instruction's source is a previous instruction's sink (dependencies 54 and 55, corresponding to type 1 in Table I), then the later instruction cannot execute until the previous instruction has executed. If an instruction's sink is a previous instruction's source (dependencies 52 and 53, corresponding to type 2 in Table I),then the later instruction can execute first if (and only if) such execution does not prevent the earlier instruction from having access to its source operand value as it exists before execution of the later instruction. As will be shown, the present invention provides for such access by providing multiple copies of sink variables in the internal cpu buffer (the SSI matrix, described in detail below). However, when multiple iterations are considered, each instruction is both serially prior to and serially later than the instructions preceding it in the static IQ; it is therefore necessary to take type 2 data dependencies into consideration. For example, if there is a type 2 relationship (e.g., dependency 52) between instructions 48 and 50, then iteration x+ 1 of instruction 48 cannot execute before iteration x of instruction 50, because iteration x of instruction 50 calculates a source for iteration x+1 of instruction 48. However, the type 2 relationship does not itself preclude iteration x of instruction 50 from executing before iteration x of instruction 48, because the SSI matrix contains multiple copies of instruction 2's sink variable (one per iteration). Thus, in the combined (dependency 52 and 54) matrix of FIG. 9A, column j indicates both types of relations for instruction j--type 1 for instructions preceding instruction j in the IQ and type 2 for instructions succeeding instruction j in the IQ. Further, the diagonal indicates that an instruction in a given iteration can be data dependent on the same instruction in a previous iteration (e.g., instruction z=z+1). As will also be shown below, the type 3 sink-sink dependencies of DD3 are only needed for array accesses.
Although this embodiment comprises data dependency matrices DD1, DD2, and DD3 for instructions having two sources and one sink, it will be understood that the invention can accommodate instructions with more sources and sinks. According to the invention, the data dependencies for each source in each instruction are separately accessible.
Internal cpu buffer 14 (FIG. 2) is referred to as the shadow sink (SSI) matrix. The shadow sink matrix is an n.times.m matrix, where n is an implementation-dependent variable indicating the number of instructions in the IQ and m is an implementation-dependent variable indicating the total number of iterations being considered for execution. Each element of the SSI matrix is typically the size of an architectural machine register, i.e., large enough to hold a variable's value. SSI(i,j) is loaded with the sink (result) value of an assignment instruction i (the ith instruction in IQ) having executed in iteration j.
Variables' values are held in SSI at least until they have been copied to memory. Values in SSI may be used as source variables for data dependent instructions. Since there are multiple copies of variables in SSI, "shadow effects" can be avoided; that is, if an instruction's sink variable is a source variable for a previous instruction in the IQ (e.g., Type 2 dependency in Table I), iteration x of the later instruction can execute before, or concurrently with, iteration x of the earlier instruction. The earlier instruction is given access to its source variable (in SSI) as it exists before execution of the later instruction, e.g., in iteration x-1. Similarly, two instructions can write the same sink variable to SSI (e.g., Type 3 dependency in Table I), allowing instructions with common sinks to execute concurrently.
Referring to FIG. 10, a model of the nominal execution order of instructions in the IQ is shown. Each row represents an instruction in the IQ and each column represents an iteration. The directed line L shows the nominal, or serial, order of execution of the sequentially biased code in the IQ. Instructions execute in this order when dependencies force instructions to be executed one at a time. Instruction R in iteration C uses as its source a sink generated previously and residing in either main memory or in SSI. The instruction iteration generating the previous sink is somewhere serially previous to instruction iteration R,C along line P. The particular SSI word to be used is determined by both the data dependencies and the execution state of the relevant instructions. The execution state is contained in the execution matrices.
The execution matrices (FIG. 2, 38) will now be described. There are two execution matrices: the real execution (RE) matrix and the virtual execution (VE) matrix. Each matrix is an n.times.m binary matrix, where n is the number of instructions in the IQ and m is the number of iterations under consideration. The RE matrix indicates whether a particular iteration j of instruction i has been really executed. An iteration really executes if ,for an assignment statement, an assignment has really occurred, or for a branch statement, a conditional has been really evaluated and a branch decision made. In this embodiment, RE(i,j) equals 1 if IQ(i) has been executed in iteration j, else RE(i,j)=0. The VE matrix indicates whether an iteration of an instruction has been "virtually" executed; an instruction is virtually executed when it is disabled (branched around) as a result of the true execution of a branch instruction. In this embodiment, VE(i,j) equals 1 if IQ(i) has been virtually executed in iteration j, else VE(i,j)=0. The execution matrices are updated by the resource dependency filter after it determines which semantically executably independent instructions are to be executed, or by the branch execution unit when branch instructions are executed. When new instructions are loaded into the IQ, the execution matrices are updated by shifting each row up and initializing a new bottom row.
Associated with the execution matrices is a register called the b-element register. The b-element is an integer indicating the total number of iterations that each instruction in the instruction queue is to execute (really or virtually). The b-element is incremented when a backward branch executes true (enabling a new iteration for execution). When all of the instructions in an iteration have been executed, the column is retired from the execution matrices (by shifting higher number columns to the left and initializing a new column of zeroes on the right) and the b-element is decremented. The b-vector (BV) is an ordered set of m (where m is the width of the execution matrices) binary elements derived from the b-element; the first n elements of the b-vector equal 1, and all other elements are zeroes. The b-vector is implemented with a shift register and is used in certain calculations described below.
The data independence calculations can now be described. In the following description, the execution matrices, the data dependency matrices, and the other two-dimensional matrices will be considered as one dimensional vectors of length n * m, with the elements ordered in column-major fashion, as shown by line L in FIG. 10. The formal mappings for deriving a serial index for an n.times.m matrix M are:
For all s.vertline.1.ltoreq.s.ltoreq.n.multidot.m, M.sub.s =M.sub.i,j ; s=i+(j-1)n
For all (i,j).vertline.(1.ltoreq.i.ltoreq.n, 1.ltoreq.j.ltoreq.m), M.sub.i,j =M.sub.s ; i=row(s), j=col(s)
where:
this is the row index of x
this is the column index of x.
The executable independence calculator (28, FIG. 2) uses execution matrices RE and VE, and data dependency matrices DD1, DD2, and DD3 to determine, for each instruction in IQ, which iterations of that instruction are data executably independent in this execution cycle. This determination is made concurrently, in logic circuitry, for each instruction iteration, i.e., for each iteration (1 thru m) of each instruction (1 thru n) in IQ. More than one iteration of an instruction may execute in a cycle, and one instruction may execute in one iteration while another instruction is executing in another iteration.
Data independence is established when all inputs (sources) are available for an instruction. If all sources are available, then the sources are linked to a processing element for execution of the instruction. A source for an instruction iteration may be available either in SSI or in memory.
Referring to FIG. 7, if instruction iteration u (iteration j of instruction IQ(i)) is under consideration for execution, then one or none of the instruction iterations serially previous to u (indicated by the larger circles) may supply a sink to be used as a source by u. Looking back along line S, the SSI element needed for execution of instruction iteration u is the first element SSI(t) (corresponding to iteration 1 of instruction IQ(k)) which is data dependent (source(i)=sink(k)) with IQ(i), where instruction iteration (k,l) has really executed, and all intervening data dependent instructions have been virtually executed.
If a source for an instruction iteration is available in SSI (as the sink of a previously executed instruction iteration) one sink enable line (SEN) is enabled by the executable independence calculator. There are nm sets of less than nm output SEN lines (29, FIG. 2) each, one set per source per IQ instruction iteration, each line of which potentially enables (connects) a serially previous sink to the instruction iteration's source input. These lines are implemented using the following equation:
For all(u,t,z,).vertline.t<u,
where
where u is the serial index to the IQ instruction iteration (i,j) under consideration for execution;
t indicates the serial SSI element under consideration for linking to an input of u;
z is the source element index for instruction i; and
This equation indicates that SSI(t) may be used by instruction IQ(i) in iteration j if: (1) SSI(t) has been generated (RE(t)=1) and (2) it is required as a source to instruction IQ(i) in iteration j (indicated by the presence of the data dependency (DD) matrix term) and (3) instruction iteration u has not been executed (indicated by the AE(u) term); and (4) there is no serially later sink SSI(s) that should be used as the z source for instruction IQ(i) in iteration j (indicated by the product term). The product term ensures that for each u,z combination at most one SEN is enabled (equal to 1). For a sink t to be used as a source to instruction iteration u, all SSI elements between t and u must correspond to instruction iterations which are either data independent of u or virtually executed (disabled). If an SSI element between t and u corresponds to an instruction that is data dependent on u and really executed, then that SSI element is potentially the one to use as a source for instruction iteration u; if it is data dependent and not executed at all (either virtually or really) than it is too early to use SSI(t).
If no SEN line is enabled, then either the source is not in SSI, i.e., it is in memory, or the source has not yet been produced. A source is taken from storage if for all serially previous iterations, no valid sink exists in SSI. This is determined according to the following equation:
For all u.vertline.(u is the serial index of IQ.sub.i),
This equation is the same basic product series term as the SEN equation, but performed once over all iterations serially prior to u. SFS equals 1 if all instructions prior to u are either data independent of u or virtually executed (VE=1). In this case, the source is obtained from memory, using the address in IQ.
EIC 28 therefore implements the following equation for determining data executable independence (DDEI)
This means that instruction iteration u is data executably independent if either its source(s) is in memory or one SSI element is set (i.e., a valid sink exists in SSI).
The reduction of data dependencies through the implementation of the sink storage matrix and the calculation of DDEI, SEN, and SFS, are thus rendered feasible by the implementation of the particular execution matrices (VE and RE) and data dependency matrices (DDz, where z is a source variable) described hereinabove. These matrices and the logic circuitry for the calculations can be implemented at reasonable cost by those of ordinary skill in the art, whereby the data independence determination and the enabling of SEN lines can be performed with a high degree of concurrency.
EIC 28 determines procedural independence concurrently with the determination of data independence. In this embodiment, the procedural independence calculations and hardware implementation are similar to the embodiment described in copending commonly assigned patent application Ser. No. 807,941, with certain modifications to accommodate the new data independence calculations described herein.
Besides the modification described previously, modification must be made to the out-of-bounds branches and executable independence calculations.
The OOBBBEI (out-of-bounds backward branch executably independent indicator) and OOBBBEN (out-of-bounds backward branch enable: indicates if an instruction is below an unexecuted OOBB and thus should be kept from fully executing) hardware remains the same. IFE (instruction fully executed) and IAFE (instruction almost fully executed) are calculated by the following logic:
BVLS.tbd.BV left shifted by one bit, i=row(u), j=col(u)
For all i.vertline.1.ltoreq.i.ltoreq.n,
IFE.sub.i =EQ(AE.sub.i,*, BVLS.sub.*), each vector is taken as an integer for the equal calculation
IAFE.sub.i =.about.GT(AE.sub.1,*, BVLS.sub.*), each vector is taken as an integer for the greater than calculation; GT(x,y)=1 iff x>y, GT(x,y)=0 otherwise.
BBI.sub.i are the backward branch indicators, and are defined as follows:
BBI.sub.1 =a iff IQ.sub.i is a backward branch.
EXSTAT.sup.u is the execution status indicator for instruction IQ.sub.i, and for the purposes of this implementation is given by:
For all u.vertline.1.ltoreq.u.ltoreq.nm,
The EXSTAT logic keeps instructions from executing more iterations than they should, i.e., normally less than or equal to about b iterations, except when an instruction is super-advanced executing. Not included in the equation is logic to prevent instructions from executing in iteration m when b<m; this logic is straightforward, and may be derived from the BV vector and a similar m-based vector. The PDSAEVE indicator ensures that only instruction interactions for which PDSAEVE=0 are allowed to execute. The PDSAEVE.sub.u term may also be OR'd with the entire EXSTAT equation.
SEI (semantically executable independence) is now for all nm serial iterations:
For all u.vertline.1.ltoreq.u.ltoreq.nm,
SEI.sub.u =1 iff serial instruction iteration u will execute in the current execution cycle, ignoring resource dependencies.
The TAEN (target address enable) logic becomes: given:
BEXS.sub.k is the branch execution sign (=0 for False, =1 for True) of instruction iteration k.
FBD.sub.k,n is 1 iff IQ.sub.k is an OOBFB (out-of-bounds forward branch). then:
For all i.vertline.1.ltoreq.i.ltoreq.n,
The logic causes a target address to be enabled to be used from instruction IQ.sub.I if the instruction is an out-of-bounds forward branch executing true in the current cycle, and all statically previous out-of-bounds forward branches either are not executing, or are executing false, in the current cycle.
The UPIN (AE update inhibit) logic becomes:
For all u.vertline.1.ltoreq.u.ltoreq.nm,
This logic inhibits an out-of-bounds forward branch from executing if any serially previous instruction either is not executing in the current cycle (indicated by the EI term), or has not really or virtually executed in a previous cycle (indicated by the AE term), or a statically previous out-of-bounds forward branch is executing true in the current cycle (as indicated by the term in {.tbd.). The logic allows multiple out-of-bounds forward branches to execute in the same cycle, as long as only one executes true.
FIG. 28 realizes minimal semantic dependencies for code containing addresses known at Instruction Queue load time, with the minor exceptions give in the section or theory. When this embodiment is used with fully dynamic data dependency calculators, it achieves minimal semantic dependencies overall, with the minor exceptions given in the theory section. It will be understood, however, that other methods and systems for determining procedural independence may be used with the data independence calculations described herein and the teachings of the present invention. It will be further understood that the separation of the data independence calculation from the procedural independence calculation is an advantageous feature of this invention.
The logic for writing SSI variables to memory will now be described. The memory updates are advantageously decoupled from the execution of instructions. This decoupling improves performance and also allows for zero-time-penalty branch prediction, as will be described below. Memory update logic (36, FIG. 2), includes the Instruction Sink Address matrix (ISA), the Advanced Storage Matrix (AST) and the Write Sink Enable (WSE) logic.
The instruction sink address matrix (ISA) is of the same dimensions as the SSI matrix and stores the memory address of each SSI element. ISA(i,j) holds the memory address of SSI(i,j). For scalars (non-array writes), ISA(i,*)=AA(i), where AA is the address of operand A (held in IQ). For array write instructions, ISA is determined for each iteration at run time.
The AST matrix is a binary matrix with the same dimensions as the SSI matrix. AST(i,j) is set to one if either VE(i,j) is 1 or SSI(i,j) has been written to memory. Thus AST(i,j) equals one if SSI(i,j) has been really or virtually stored.
Every cycle, each eligible SSI value is written to memory at the location pointed to by the contents of the corresponding ISA element. Eligibility is determined by the WSE logic. The WSE logic implements the following equation:
For all .vertline.u1.ltoreq.u.ltoreq.nm,
SSI(u) is written to memory (WSE=1) if the following conditions are met:
1) Instruction iteration u has really executed (RE(u)=1), and SSI(u) has not been written to storage (AST(u) not=1), and this iteration has been enabled (b-element greater than or equal to col(u)); and
2) For all instruction iterations serially prior to u, all instructions that are data dependent on instruction u have executed (AE=1). The data dependency referred to here is DD4, where DD4=(DD1+DD2).sup.T, i.e the transpose of the combined DD1 and DD2 matrices. Thus, all serially previous instructions having a source which is the sink variable under consideration for writing must have executed (really or virtually); and
3) For all instruction iterations serially prior to u, all instructions that write the same sink variable as instruction u (type 3 data dependencies, stored in DD3) have either executed (AE=1) or have already been written to memory (AST=1).
An instruction iteration is said to execute absolutely if it is executed only once, i.e., it is not re-evaluated, regardless of the final control-flow of the code.
The inclusion of the B-vector in the WSE logic allows only valid sinks to be written (those sinks whose iterations have been enabled), not those to the right of the column indicated by the b-element. This means that branch prediction techniques can be used to absolutely execute code beyond branches, ahead of time as described below; sinks generated by such execution will be written to SSI, but will not be written to memory unless and until the predicted branch is actually executed. In other words, iterations may be executed before it is known that they will be needed. A unique feature of this invention is that no time penalty is incurred if a branch prediction turns out to be wrong.
In this embodiment, the following form of branch prediction is used: Instructions within an innermost loop assume that the backward branch comprising the loop will always execute true. Thus, such backward branches are, in effect, conditionally executed. The instructions within the inner loops are therefore allowed to execute absolutely up to m iterations ahead of time, where m is the width of the execution matrices. Thus, forward branches within the inner loop may also execute absolutely ahead of time in future (unenabled) iterations. Therefore, both forward and backward branches may be executed ahead of time. A novel feature of the present invention is that both forward branch and other instructions within an inner loop may be executed absolutely ahead of time (in future iterations), while eliminating state restoration and backtracking, thereby improving performance.
Referring to FIG. 12, b=3, and therefore normally only those instruction's iterations in columns 1-3 (indicated by Xs and Ts) are allowed to execute absolutely. (Indeed, they must execute for correct results.) The instruction iterations (indicated by Ss) to the right of column 3 (to the right of the b pointer) and within the inner loop are now also allowed to execute. This is possible by considering the instruction iterations indicated by Vs to be virtually executed. An SAEVE matrix indicates those instruction iterations considered to be virtually executed for this limited purpose. The instructions in the T region are also considered to be virtually executed by instruction iterations in the S region. This is so that T sinks are not used as inputs to S instruction iterations. Otherwise, T instruction iterations are allowed to execute as normal X instruction iterations. Instruction iterations in the S region thus execute ahead of time, absolutely (with the minor exception given in the SAE section), writing to the SSI matrix. However, the sink is not copied to memory at least until the instruction iteration becomes an X instruction iteration. This can occur only upon the inner loop' s backward branch executing true.
This branch prediction technique is a direct result of the decoupling of instruction execution and memory updating taught by the present invention. Very little additional cost (in hardware or performance penalty) is incurred by implementing this branch prediction technique because: a) the WSE logic and the SSI, ISA, and AST matrices are already in place; and b) no state restoration or backtracking is needed in the event that the branch does not execute tue.
A later section discusses implementation details of this branch prediction technique (called "Super Advanced Execution" (SAE)).
It will be understood that the embodiment described hereinabove assumes that all source and sink addresses are known at the time instructions are loaded into IQ and the data dependency matrices are calculated. The logic can be expanded to handle array accesses or indirect accesses, where addresses are calculated at execution time, e.g., from an array base address and an index value. One possible approach is to compare calculated array read (source) addresses to sink addresses stored in ISA, to match array sources with array sinks stored in SSI. This requires a large number of comparators, and it is therefore preferred to force all array reads to be done from memory (not from SSI).
Including array accesses, the logic for SEN becomes:
For all(u,t,z).vertline.(t<u, 1.ltoreq.z.ltoreq.2),
where ARWI(i)=1 if instruction i is an array write instruction.
The inclusion of the ARWI terms has the following effects: 1) ARWI(t) ensures that no array write instruction is used as a sink to a serially later source (all array reads are from memory); and 2) ARWI(s) ensures that array writes do not inhibit other assignments from being used as inputs.
With array accesses, there are effectively three sources to an instruction, the normal two (B,C) appearing on the right hand side of the assignment relation, and that for A, when A specifies the name of an array base address for array write instructions. A must be read to obtain the base address of the array before the array element can be written; therefore A is also a source and a sink enable (SEN) computation must be made to ensure that it is linked to the proper sink. When a third source is implied (array write instructions) the SEN logic for z=3 is:
For all(u,t,z).vertline.(t<u,z=3),
The inclusion of ARWI(u) ensures that A (the first operand specifier, normally a sink) is only used as a source if the instruction is an array write instruction.
The modified (SFS) source from storage logic is:
For all(u,z).vertline.(u is the serial index of IQ.sub.i,1.ltoreq.z.ltoreq.2),
For the sink, the logic is:
For all(u,z).vertline.(u is the serial index of IQ.sub.i,z=3),
The modified Data Dependency Executable Independence (DDEI) indicators are:
For all u.vertline.1.ltoreq.u.ltoreq.nm,
DDEI is now checked for all sources, including z=3, and the largest bracketed term ensures that if instruction u is an array read instruction, all previous array writes to the specified array have been stored in memory. ARRI(i)=1 if instruction i is an array read instruction.
Since all array reads are from memory, and not SSI, array accesses involving both an array read and an array write to the same array must be sequentialized; otherwise, with only array reads or only array writes taking place, the accesses may proceed concurrently.
With this exception, and those in the theory section, this embodiment achieves minimal semantic dependencies of all code consisting of assignment statements and branches.
In summary, the preferred embodiment of the present invention provides an improved method and apparatus for extracting low level concurrency from sequential instruction streams to achieve greatly reduced semantic dependencies, as well as allowing absolute execution of instructions dynamically past conditionally executed backward branches. All or part of the invention can be implemented in software, but the preferred embodiment is in hardware to maximize the overall concurrency of the machine. The design of logic circuitry for implementing all of the equations presented herein is well within the capability of those of ordinary skill in the art of digital logic design. Theoretical background (including derivations of the equations presented herein) is provided along with execution examples and additional implementation details.
A computer program source code listing in the "C" language for simulating the system described in the foregoing description of the preferred embodiment is provided herewith as Appendix 1. A brief description of the simulator program of Appendix 1 is given below.
Although the invention has been described in terms of a preferred embodiment, it will be understood that many modifications may be made to this embodiment by those skilled in the art without departing from the true spirit and scope of the invention. The scope of the invention may be determined by the appended claims.
THEORY
The following items enumerate the procedural dependencies (PD) of instruction i on instruction j for non-trivial sequentially-biased code. Note that statements 1-6 (labelled PD 1-6) are only concerned with the present iteration of instruction i. Statement 7 (labeled PD 7) is only concerned with future iterations of instruction i. The notation IQ.sub.k (k is either i or j) indicates instruction k in the Instruction Queue. For the general case, take the Instruction queue length to be infinite. These procedural dependencies hold for any section of static code.
1. IQ.sub.i is an As in the domain of FB IQ.sub.j ; see FIG. 13.
2. IQ.sub.i is a BB in the domain of FB IQ.sub.j ; see FIG. 13.
3. IQ.sub.i is an FB in the domain of FB IQ.sub.j and the two FBs are overlapped; see FIG. 14; this procedural dependency is only essential for unstructured code; note that non-overlapped FBs are completely procedurally independent.
4. IQ.sub.i is a BB statically later in the code than BB IQ.sub.j and the two BBs are either overlapped or nested; see FIG. 15.
5. IQ.sub.i is any type of instruction statically later in the code than BB IQ.sub.j and IQ.sub.i is data dependent on one or more instructions in IQ.sub.j 's domain; see FIG. 16.
6. IQ.sub.i is any type of instruction statically later in the code than BB IQ.sub.j and IQ.sub.i is in the domain of an FB which is overlapped with IQ.sub.j ; see FIG. 17; this procedural dependency is only relevant for unstructured code.
7. IQ.sub.i is any type of instruction in BB IQ.sub.j 's super domain; i.e., future iterations of IQ.sub.i are not enabled until one or more BBs whose domains contain IQ.sub.i execute true.
The enumerated procedural dependencies are direct dependencies, one instruction being immediately dependent on another. Indirect dependencies (for example, instruction 1 is dependent on instruction 2 which is dependent on instruction 3, implies instruction 1 is indirectly dependent on instruction 3) do not imply direct dependencies and are not considered further; enforcing just the direct dependencies guarantees that the indirect ones will be enforced, and code will be executed correctly.
Nested forward branches are procedurally independent. The proof consists of examining all consequences of the relative execution order of I.sub.1 and I.sub.2 as shown in FIG. 18. This order is only relevant insofar as it affects the state of memory, i.e., the actual user's program state. The execution of I.sub.1 preceding the execution of I.sub.2 is the normal (sequential) case and is not examined further. I.sub.2 executing at the same time as or before I.sub.1 executes is the case now examined.
The program's memory state will only be valid if an instruction executes ahead of time, ignoring some dependency. The data dependencies amongst the instructions in FIG. 18 are independent of the procedural dependencies and, more to the point, are independent of the relative execution of I.sub.1 and I.sub.2. I.sub.x will not execute until both I.sub.1 and I.sub.2 have executed true, since I.sub.x is in both I.sub.1 's and I.sub.2 's domains, and by definition can instruction in a forward branch domain must wait for the branch to execute true before the instruction may execute. Therefore any instruction procedurally or data dependent on I.sub.x will not execute until both I.sub.1 and I.sub.2 have executed true, maintaining correct program execution results. The order of execution of I.sub.1 and I.sub.2 is thus irrelevant: I.sub.2 executing before I.sub.1 only partially enables I.sub.x ; I.sub.x cannot execute until I.sub.1, and all forward branches in PDS.sub.x, have executed true.
Also note that neither I.sub.1 nor I.sub.2 executing true or false affects the contents of memory, hence I.sub.2 can execute prior to I.sub.1, then I.sub.1 may execute without any change in program memory state taking place. Therefore, I.sub.1 and I.sub.2 are procedurally independent.
Two utility lemmas are stated and proven. Then the procedural dependencies necessary and sufficient for structured code (SC) are derived. The structured code restriction is then relaxed and the additional procedural dependencies are derived and, when taken together with those procedural dependencies arising from structured code, are shown to be necessary and sufficient for all non-trivial code.
The first utility lemma is that an instruction I is only procedurally dependent on a statically later branch B iff B is a BB and I.epsilon.SD.sub.8. (This is just a re-statement of PD 7). this is true since, by definition, only a statically later BB executing true can create new (future) iterations of I. In cases other than that considered in the above lemma, I.sub.i can only be procedurally dependent in its present iteration on statically previous branches I.sub.j (lemma 2). To prove this assume I.sub.j is a statically later branch. The three possible cases of statically later branches are examined and shown not to create present iteration procedural dependencies with I.sub.i. First, in any given iteration, I.sub.i 's execution is independent of I.sub.j 's; I.sub.i may execute, regardless of I.sub.j 's execution (FIG. 19). Second, in any given iteration, I.sub.i 's execution is independent of I.sub.j 's; I.sub.i may execute regardless of I.sub.j 's execution (FIG. 20). Third, in any given present iteration I.sub.i must execute, virtually or really, independently of I.sub.j. I.sub.j can only partially enable future iterations of I.sub.i (FIG. 21).
For structured code, PDs 1, 2, 4 and 5 are necessary and sufficient for describing codes' present iteration procedural dependencies (lemma 3). With the structured code and present iteration constraints, the procedural dependencies are determined by an exhaustive examination of possible codes. FIG. 22 is an all-encompassing example of structured code used in the proof.
In the first case, I.sub.i is an AS. By definition, I.sub.i is procedurally dependent on all FBs in whose super-domain it is, therefore PD 1 is sufficient. In the example, I.sub.i is procedurally dependent on I.sub.0 and I.sub.4. I.sub.i is not procedurally dependent on I.sub.1, I.sub.2, and I.sub.5 (by definition), or I.sub.7 and I.sub.8 (by Lemma 2). If I.sub.i is data dependent on one or more I.sub.d in I.sub.3 's super-domain, then I.sub.i may not execute until I.sub.d has fully executed in the present iteration. Since I.sub.d cannot be fully executed until I.sub.3 is fully executed (I.sub.3 may generate more iterations of I.sub.d, and I.sub.d may appear to be fully executed before I.sub.3 has finished executing), I.sub.i is procedurally dependent on I.sub.3. An equivalent argument can be made for all previous BBs. Therefore PD 5 is sufficient for I.sub.i being an AS.
In the second case, I.sub.i is an FB. Based on the earlier proof in this section, I.sub.i is procedurally independent of I.sub.0, I.sub.1, I.sub.2, I.sub.4 and I.sub.5 (in the example), and in fact all other FBs, since the code is structured (no overlapped branches). For the same reasons as in the first case, PD 5 is sufficient for I.sub.i being an FB.
In the third case, I.sub.i is a BB. As in the first case, I.sub.i is procedurally independent of those previous FBs that I.sub.i is not in the super-domain of (e.g., I.sub.1, I.sub.2, and I.sub.5 in the example). If I.sub.i branched back to section h in the example, then the relevant enclosing FB would be I.sub.4. Given the definition of FBs, I.sub.4 only partially enables the present iterations of the instructions in I.sub.i 's super-domain, therefore allowing I.sub.i to generate new iterations of the instructions in its upper-domain before I.sub.4 executes is incorrect, and I.sub.i must be procedurally dependent on I.sub.4. Therefore PD 2 is sufficient. Note that if the definition of FBs were changed to also partially enable future iterations of the instructions in their domains, then I.sub.i could generate new iterations and infinitum, since none would be executed until the enclosing FBs execute true. Allowing this execution of backward branches ahead of time is only possible when the BB forms an endless loop, i.e., is trivial code. (If the loop is not endless, then it contains loop termination instructions which by definition are procedurally dependent on the FB.)
As in the first case, I.sub.i is procedurally dependent on those statically previous BBs (containing I.sub.d in their super-domains), in which I.sub.i is data dependent on an I.sub.d. If I.sub.i branches to section h, then I.sub.6 is nested in I.sub.i. The relevant instructions are shown in FIG. 23.
Consider the following scenario:
1. I.sub.B is data dependent on I.sub.C
2. I.sub.i executes true, enabling a new iteration each of I.sub.B , I.sub.C and I.sub.D
3. I.sub.6 executes true, enabling a new iteration of I.sub.C
If is now possible for I.sub.B to use a variable as a source which is sunk by I.sub.C and does not yet contain the proper value, as I.sub.6 (and hence I.sub.C) may not have executed in all I.sub.6 loop iterations for the first iteration of the I.sub.i loop. A similar argument exists for code I.sub.D with respect to I.sub.C. Therefore I.sub.i is procedurally dependent on I.sub.6 if either I.sub.B or I.sub.D is data dependent on I.sub.C. Since the cases when there are no such dependencies consist of only trivial code (the inner loop would be executed only for the first iteration of the outer loop, and could be moved outside of the outer loop), I.sub.i is procedurally dependent on I.sub.6. Therefore PD 4 is sufficient for non-trivial code.
In summary, an exhaustive search for all the procedural dependencies has been made, resulting in PDs 1, 2, 4 and 5 being found to be sufficient. Having found no other present iteration procedural dependencies in structured code, PDs 1, 2, 4 and 5 are also necessary. Furthermore, PDs 1, 2, 4, 5 and 7 are necessary and sufficient to describe all possible procedural dependencies in structured code. Since an iteration may only be present in future, all such code is covered by lemmas 1 and 3; in the proofs of the lemmas the specific dependencies were either derived, or determined via an exhaustive search; they were all that were found.
To determine unstructured code procedural dependencies the structured code constraint is removed. The sole difference between structured code and unstructured code is that unstructured code allows overlapped branches, while structured code does not.
The fourth lemma states that the procedural dependencies additionally sufficient for unstructured code (due to overlapped branches) are PD 2 (overlapped), PD 3, PD 4 (overlapped) and PD 6. The overlapped cases of PDs 2 and 4 are meant to distinguish the new dependencies from those also found in structured code, i.e., nested cases. The four new possible control flow scenarios created by overlapped branches are now exhaustively examined for new procedural dependencies. Unless noted otherwise, the present iteration is assumed. (In the figures, assume code sections A, B, and C each contain unstructured code with no branch targets outside of the section). For each of the scenarios, each code section is examined, along with the statically later branch.
The first case, shown in FIG. 24, is for overlapped FBs. Code A is only procedurally dependent on I.sub.j, by definition. Code B is procedurally dependent on both I.sub.i and I.sub.j, be definition. Code C is only procedurally dependent on I.sub.i, by definition.
I.sub.i is procedurally dependent on I.sub.j ; otherwise, I.sub.i could execute before I.sub.j and thus code C could be disabled before the execution of I.sub.j, which can indirectly determine if code C is to execute. (I.sub.j executing true causes I.sub.i not to be executed, thus indirectly enabling code C; otherwise I.sub.i might execute true, incorrectly disabling code C.) Therefore PD 3 is sufficient.
In the second case the FB domain is overlapped with the previous BB domain (FIG. 25). Code A is only procedurally dependent (in future iterations) on I.sub.j, by definition and lemmas 1 and 2. Code B is procedurally dependent in future iterations on I.sub.j, by definition. Code B is procedurally dependent in the present iteration on I.sub.i, by definition. Code C is procedurally dependent in the present iteration on I.sub.i, by definition. Also, since multiple iterations of I.sub.i may be pending (due to looping by I.sub.j), it cannot be assumed that code C will execute, until the last iteration of I.sub.i executes true; this is indicated by I.sub.j executing false and I.sub.j executing false in its last present iteration. Therefore code C is procedurally dependent on I.sub.j, i.e., PD 6 is sufficient. I.sub.j is procedurally dependent on I.sub.i, since otherwise it is possible for unwanted iterations of codes A and B to be partially enabled by I.sub.j. Therefore PD 2 is sufficient for the overlapped case.
In the third case, shown in FIG. 26, the BB domain overlaps with the previous FB domain. Code A is procedurally dependent on I.sub.j, by definition. Code B is procedurally dependent on I.sub.j, by definition. Code B is also procedurally dependent in future iterations on I.sub.i, by definition. Code C is procedurally dependent in future iterations on I.sub.i, by definition. For I.sub.i only its present iteration is in question. In the worst case, I.sub.i is data dependent on I.sub.B which is procedurally dependent on I.sub.j. But any necessary serialization of code execution is guaranteed by these already present dependencies. Therefore there are not new procedural dependencies resulting from this situation.
The fourth case, shown in FIG. 27, is for overlapped BBs. Code A is procedurally dependent in future iterations on I.sub.j, by definition. Code B is procedurally dependent in future iterations on I.sub.j and I.sub.i, by definition. Code C is procedurally dependant in future iterations on I.sub.i, by definition. Also, PD 5 applies, as usual. For I.sub.j, PD 5 applies, as usual. Assume I.sub.i is present iteration independent of I.sub.j. Then new iterations of I.sub.B can be enabled by I.sub.i before code A has executed in all iterations, and erroneous execution may result. Therefore the assumption is false and I.sub.i is procedurally dependent on I.sub.j, i.e., PD 4 (overlapped) is sufficient.
Having shown that the unstructured code procedural dependencies are sufficient, the necessity of all of the procedural dependencies (PDs) for unstructured code is demonstrated via a sequence of two lemmas and a theorem. The following lemma effectively anchors an induction.
Lemma 5 states that present iteration procedural dependencies due to multiple chained branches (FIG. 28) are described by PDs 1-6. Chained branches are overlapped branches such that an overlapped area is in the domains of at most two branches. In FIG. 28, the extent of each branch's super domain (SD) is represented by a solid lien (in the shape of a "C"); the branches may be either forward or backward, so no arrows are shown. Two cases must be reviewed in order to prove the lemma. In the first case the branches (within overlapped areas) are nested or disjoint. This is just structured code, in which case structured code procedural dependencies apply.
In the second case, in which the branches are overlapped, only code A can be procedurally dependent on at most branches 1, 2 and 3, and then only if B.sub.1 is a BB and B.sub.2 and B.sub.3 are FBs. All three procedural dependencies arise from either an unstructured code procedural dependency (B.sub.1) or from definitions (B.sub.2 and B.sub.3). Other combinations of FBs and BBs are covered by the cases in lemma 4. By inspection and lemma 2, chained branches above B.sub.1 or below B.sub.3 cannot add any new procedural dependencies to code A.
Lemma 6 states that present iteration procedural dependencies due to multiply overlapped (not nested) branches are covered (contained) by PDs 1-6 (FIG. 29). In order to prove this lemma, first the particular three branch case of FIG. 29 is exhaustively examined for procedural dependencies other than PD 1-7. This case is then generalized to k-tuple overlap, k.epsilon. positive integers.
In FIG. 29, the extent of each branch's (B's) super domain is represented by a solid line (in the shape of a "C"); the branches may be either forward or backward, so no arrows at the ends of the lines are shown. Only code in sections F, E and D can possible have additional procedural dependencies arising from the overlap of all branches 1-3 (indicated by the large arrow in the figure), since lemma 2 eliminates codes sections A-C.
Code F is only unstructured code procedurally dependent on B.sub.1 and B.sub.2 iff B.sub.1 and B.sub.2 are BBs and B.sub.3 is a FB. All of the possible procedural dependencies resulting from these branches and that resulting from F.epsilon.SD.sub.3 imply code F is procedurally dependent on B.sub.3, in turn implying that code F is maximally procedurally dependent, i.e., it is procedurally dependent on all B.sub.1 -B.sub.3. If B.sub.3 is a BB, then there are no unstructured code procedural dependencies, since B.sub.3 is after code F (no present iteration procedural dependencies). If B.sub.1 is a FB, F is not procedurally dependent on B.sub.1 since it is not in B.sub.1 's super-domain. The same is true for B.sub.2.
For code E: B.sub.1 is a BB, B.sub.2 and B.sub.3 are FBs, implying code E is procedurally dependent on B.sub.1 -B.sub.3 in turn implying that code E is maximally procedurally dependent, i.e., is dependent on all of the branches.
For code D: is procedurally dependent on B.sub.1 -B.sub.3 iff B.sub.1 -B.sub.3 are FBs, i.e., code D is maximally procedurally dependent.
In other branch combinations, the code cases are covered by overlaps of less than three, since both: enclosing BBs affect only the future iterations of an instruction, reducing the possible present iterations procedural dependencies; and non-enclosing FBs also reduce the present iteration procedural dependencies, since an instruction must be in the domain of a FB for the FB to cause any procedural dependencies between the instruction and previous branches. The latter effectively keeps such branches from generating additional procedural dependencies.
In general, code K in the k-tuple intersection (e.g., code D in FIG. 29) can have a new procedural dependency only if all enclosing branches are FBs, but then it is maximally procedurally dependent, and the case is covered by structured code and unstructured code procedural dependency conditions. Code K+q (q is a positive integer between 0 and k-1, inclusive, this code is statically later than code K) requires combinations of .gtoreq.k-q FBs for maximal procedural dependence, since .gtoreq.q BBs overlap with the FBs; this implies that code K+q is procedurally dependent on the BBs. Or all statically later branches are BBs implies that only the codes' future iterations are affected.
Intermediate cases (less than maximal procedural dependence), as well as the procedural dependencies for code above code K, are covered by the proofs for other k-tuple overlaps, k'<k, applied recursively. This is possible since for the non-maximally procedurally dependent cases of code K+q (q>0), the non-enclosing branches are FBs, and thus there are no procedural dependencies between them and code K+q. In this way the situation is the same as if only k' overlap is occurring. For example, in FIG. 29 k=3. Code D is the k case. For code E k'=2, and for F use k'=1 for the non-maximally procedurally dependent cases.
Based on the above proofs, PDs 1-7 are both necessary and sufficient to describe all procedural dependencies in all non-trivial unstructured code, i.e., all non-trivial code. All code may be considered to be formed of sections of structured code optionally interspersed with overlapped branches, forming unstructured code. The dependencies arising form the unstructured branches (where overlap occurs) are found to be sufficient in lemma 4. The baseline for demonstrating their necessity is given in lemma 5. Lemma 6 demonstrates their complete necessity.
The previous theory assumed an unlimited IQ (or instruction window). A finite IQ is now considered as far as forward branches are concerned. The primary new concern is with out-of-bounds forward branches (OOBFBs). OOBFBs jump to locations statically later than all instructions in the IQ. The study of OOBFBs is essentially the study of the interface between the static and dynamic instruction streams. The interface arises from the inherent finiteness of the Instruction Queue.
Allowing the execution of multiple OOBFBs simultaneously is useful for the speedy execution of both large SWITCH statement constructs, and mixtures of branches and procedure calls, as calls may be considered to be OOBFBs. Without the capability of multiple OOBFB execution, some code would be forced to execute sequentially, one OOBFB per cycle.
All non-forward branch instructions statically before an OOBFB must fully execute before the OOBFB can execute, since the OOBFB's execution may cause new code to be loaded into the IQ. If full execution is not required, then when now code is loaded into the IQ the partially executed instructions will be overwritten, implying that one or more of their iterations will not execute, leading to erroneous results. Conversely, all non-forward branch instructions statically later than OOBFB cannot execute until the OOBFB has executed. Forward branches (e.g., I.sub.3 and I.sub.4 in FIG. 30) nested in OOBFBs (I.sub.1 and I.sub.2 in FIG. 30), are procedurally independent of the enclosing OOBFBs. (In FIG. 30, I.sub.2 and I.sub.3 may be considered to be nested in I.sub.1 since ASD.sub.2 ASD.sub.1 and ASD.sub.3 ASD.sub.1. ASD.sub.i is the apparent super domain of instruction i.) Therefore if there are not instructions between OOBFBs (as is the case with I.sub.1 and I.sub.2 in FIG. 30), the OOBFBs are procedurally independent, assuming that statically lower numbered OOBFBs executing true have priority over following branches. For example, I.sub.1 executing true inhibits the activation of I.sub.2, as far as jumping to I.sub.2 's target address is concerned.
All of the possible outcomes of the two OOBFSs' (I.sub.1 and I.sub.2 in FIG. 30) execution are shown in FIG. 3; in this truth table the branch conditions C.sub.k have one of four possible states:
1. T--the branch executes in the current cycle and its condition evaluates "true", i.e., the branch is to be taken;
2. F--the branch executes in the current cycle and its condition evaluates "false", i.e., the branch is not to be taken;
3. ale (already executed)--the branch fully executed in a previous cycle;
4. nye (not yet executed)--the branch is not yet fully executed, nor is it executing in the current cycle.
The output TA (target address) indicates one of three possible actions:
1. 1--jump is to be taken to the TA of OOBFB 1, IQ loading starts at that address;
2. 2--a jump is to be taken to the TA of OOBFB 2, IQ loading starts at that address;
3. F--no jumps are to be taken, execution of the code currently in the IQ continues.
In the noted case in FIG. 31, branch 2 is statically previous to branch 1, and branch 1 is "not yet executed"(nye); therefore branch 2 cannot be allowed to execute true, as this would cause instruction 1 to be unexecuted (its condition untested), leading to erroneous results. In such a case, the execution state of branch 2 is reset so that it is evaluated again in another later cycle, and branch 2 is inhibited from being taken; therefore it is not completely executed.
The truth table can be expanded to include more than two OOBFBs; in such cases the statically previous OOBFBs have priority, as mentioned earlier. Logic an be realized from the truth table allowing all OOBFBs to conditionally execute in the same cycle. Only the statically most previous OOBFB executing true, and statically later OOBFBs executing false, are allowed to completely execute, however. Therefore, multiple OOBFBs may be executed concurrently.
Since structured code by definition consists of non-overlapped branches, FDs 2, 3, and 6 do not exist for structured code. In other words, the procedural dependencies extent for structured code are a proper subset of those existing in unstructured code. Thus it appears that more concurrent exists in structured code than in unstructured code. This does not mean that the algorithmic conversion from unstructured to structured code [61] results in faster code execution. It does mean that if HLL code (primarily of a structured nature) is converted to the model's machine code, constraining the machine code to be structured, more concurrent execution of the HLL code will likely result. Structured code may be used to advantage in realizing HLL statements.
SUPER ADVANCED EXECUTION DETAILS
The logic basically stays the same when SAE is used. Wherever a virtual execution (VE) terms occurs in the original logic, another term is OR'd with it indicating the pseudovirtual execution of certain instructions' iterations.
The regions of the AE matrix shown in FIG. 12 are calculated as follows. The BV and BVLS vectors indicate the horizontal boundaries of the regions delineated in the figure. The vertical region boundaries are given by the bit vector in inner loop (IIL) of length n. IIL is determined in a relatively static fashion using the contents of the backward branch domain (BBDO) matrix to set those elements of IIL that are within an inner loop's backward branch's domain. Taking the BV vector to be horizontal, with its elements' values extending vertically, and the IIL vector to be vertical, with its elements' values extending horizontally, then the various regions of FIG. 12 are calculated by various logical combinations of the intersections of the BV, BVLS, and IIL values.
Forward branches within inner loops (overlapped with the loop-forming backward branch) are allowed to conditionally execute in super advanced iterations, such that they are only allowed to completely execute false (branch not taken). If their conditions evaluate true, then they are not executed, nor is the AE matrix updated to show an execution. This keeps loops from prematurely terminating.
The following logic is used to compute the IIL elements:
ILI (Inner Loop backward branch indicator) is computed at each load cycle:
wherein:
new=n+1
BBDO.sub.i,new= 1 if IQ.sub.i is in new instruction's BB domain;
BBDO.sub.i,i =1 if IQ.sub.i is a BB;
BBDO.sub.new,new =1 if IQ.sub.new is a BB; and
ILI=1 iff the new instruction being loaded is an inner loop forming backward branch.
IIL.sub.i (Inner Loop indicators) are initialized to zero and computed at each load cycle for all i, where 2.ltoreq.i.ltoreq.n+1:
The following logic computes (at each load cycle) indicators showing those instructions which are forward branches with targets out of an inner loop, also known as Out of Inner Loop Forward Branches:
for all i, where 2.ltoreq.i<n+1:
The BIL.sub.i (Below Inner Loop) indicators are also computed at each load cycle:
for all i where 2.ltoreq.i.ltoreq.n+1:
(All of the above indicators are nominally computed after the new (n+1) columns of the BBDO and FBD matrices have been computed.
Now, referring to FIG. 12, the matrix SAEVE indicates those instruction iterations (V and T) which would be considered to be virtually executed for Super Advanced Execution of instruction iterations marked "S" in the figure. Using row and column indexing:
for all i,j:
Similar logic, indicating just the V's is:
for all i,j:
The PDSAEVE indicators are OR'd with the AE and VE terms in the procedural independence calculating logic. The SAEVE and PDSAEVE indicators are computed by arrays of logic; their values only (potentially) change upon load cycles. For example, PDSAEVE is computed using a logic array with an AND gate at each intersection; each element of the column vector IIL is AND'd with each element of the row vector BV to generate the PDSAEVE matrix. The ones in this matrix are the "V" terms in FIG. 12. Note that PDSAEVE indicates those instructions allowed to execute, either normally or SAE.
The SAEVE indicators are used to modify the SEN and SFS logic for SAE, as follows:
for all i,j:
Where VETYP.sub.i,j =1, this indicates the "S" instruction iterations of FIG. 12. This VETYP matrix can also be computed using a logic array.
One technique then OR's the original VE.sub.s term in the SEN and SFS logic with:
where u and s are serial indices.
Alternatively, and in a preferred fashion, the original VE.sub.s terms in the SEN and SFS logic is OR'd with:
These modifications ensure that only "S" instruction iterations consider the "T" iterations to be virtually executed in SAE operation.
BRIEF DESCRIPTION OF THE "SIMCD"
Simulator Program and Documentation
The simcd program is a simulator of the hardware embodiment described in the specification. With appropriate input switch settings (described below), and a suitably encoded test program, the execution of the simulator causes the internal actions of the hardware to be mimicked, and the test program to be executed. The simulator program is written "C", the test programs are written in machine language.
The file simcd.doc contains descriptions of the switch settings and input parameters of the simulator. For the hardware embodiment described in the specification, dct=1, bct=4, n=32 (typically), m=8 (typically), parameters 5-8=32 or greater, IQ load type=1. The specification of the input code has not been included.
The basic operation of the simulator program is now described. Page numbers will refer to those numbers on the pages of the simcd54.c program listing. The first few pages contain descriptions of the data structures, in particular the dynamic concurrency structures of the hardware are declared on page 2 right; the name is dcs. Much of the `main` () routine, starting on page 4 left, is concerned with initialization of the simulated memory and other data structures.
The major execution loop of the simulator starts on page 5 right, 12th line down (the while loop). Each iteration of the loop corresponds to one hardware machine cycle. The first function executed in the loop is the `load` () function which loads instructions into the Instruction Queue, and also sets corresponding entries of the static concurrency structures. In many, if not most, cases, no instructions will be loaded, and the `load` () function will take 0 time (otherwise, the current cycle may have to be effectively lengthened). Continuing to refer to page 5 right, the next relevant code is in the section in case 1: of the `switch` (ddct) construct. The next five function calls are the heart of the machine cycle simulation; the rest of the `while` loop consists of output specification statements, which are not relevant to the application claims. In hardware, the actions of these functions would be overlapped in time, keeping the cycle time reasonable.
The first function, `eidetr` (), is one of the most relevant sections of code; it starts on page 22 right. Its primary functions are to determine those instruction instances (iterations) eligible for execution in the current cycle, and for assignment instructions, to determine the inputs to each instruction instance. The first code in the function, page 22 right to page 23 right top, determines whether procedural dependencies have been resolved or not. The next small piece of code on page 23 right determines `saeve` terms for use in the SEN (sink enable) calculations, allowing the super advanced execution by the hardware. The `for` loop at the bottom of page 23 right, continuing on to page 24 left, computes the SEN pointers in an incremental fashion, to reduce simulation time. Next is the DD EI calculation, which determines the final data dependency executable independence of the instructions instances. There are some further relatively minor calculations on pages 24 right through 25 right, including the final determination of semantic executable independence, and the function ends.
The next function in the main loop is `asex` (). In this function, those assignment instruction instances found to be ready for execution in eidetr () are actually executed, with their results being written into the shadow sink matrix. The advanced execution matrix is also updated, indicating those instances which have executed.
The next major function is `memupd` (), which is contained on page 29 right. First, a determination is made of which shadow sink registers are eligible for writing to main memory, i.e., the WSE calculations are made using the advanced storage matrix. Next, memory is updated with the eligible shadow sink values, using the addresses in instructions in address; and the advanced storage matrix is updated.
The next function is brex () beginning on page 27 left. In this code, the appropriate branch tests are made (very possibly more than one per cycle), and branches out of the Instruction Queue are handled.
The last major function is the `dcsupd` () function, which starts on page 29 right bottom. The dynamic concurrency structures are updated as indicated by branch executions. Also, fully executed iterations, in which the advanced execution and advanced storage matrix columns corresponding to that iteration and all those earlier that have all ones in them, are retired, making room for new iterations to be executed.
All the major functions in the primary loop of the simcd54.c simulator program have been described. The loop continues until a special "end-of-simulation" instruction is encountered in the test program. ##SPC1##
APPENDIX 4
Brief Description of the "simcd" Simulator Program and Documentation
The simcd program is a simulator of the hardware embodiment described in the specification. With appropriate input switch settings (described below), and a suitably encoded test program, the execution of the simulator causes the internal actions of the hardware to be mimicked, and the test program to be executed. The simulator program is written in "C", the test programs are written in a machine language.
The file simcd.doc contains descriptions of the switch settings and input parameters of the simulator. For the hardware embodiment described in the specification, dct=1, bct=4, n=32 (typically), parameters 5-8=32 or greater, IQ load type=1. The specification of the input code has not been included.
The basic operation of the simulator program is now described. Page numbers will refer to those numbers on the pages of the simcd54.c program listing. The first few pages contain descriptions of the data structures, in particular the dynamic concurrently structures of the hardware are declared on page 2 right; the name is dcs. Much of the main () routine, starting on page 4 left, is concerned with initialization of the simulated memory and other data structures.
The major execution loop of the simulator starts on page 6 5 right, 12th line down (the while loop). Each iteration of the loop corresponds to one hardware machine cycle. The first function executed in the loop is the load () function which loads instructions into the Instruction Queue, and also sets corresponding entries of the static concurrency structures. In many, if not most, cases, no instructions will be loaded, and the load () function will take 0 time (otherwise, the current cycle may have to be effectively lengthened). Continuing to refer to page 5 right, the next relevant code is in the section in case 1: of the switch (ddct) {construct. The next five function calls are the heart of the machine cycle simulation; the rest of the while loop consists of output specification statements, which are not relevant to the application claims. In hardware, the actions of these functions would be overlapped in time, keeping the cycle time reasonable.
The first function, eidetr (), is one of the most relevant sections of code; it starts on page 22 right. Its primary functions are to determine those instruction instances (iteration) eligible for execution in the current cycle, and for assignment instructions, to determine the inputs to each instruction instance. The first code in the function page 22 right to page 23 right top, determines whether procedural dependencies have been resolved or not. The next small piece of code on page 23 right determines saeve terms for use in the SEN (Sink ENable) calculations, allowing the super advanced execution by the hardware. The for loop at the bottom of page 23 right, continuing on to page 24 left, computes the SEN pointers in an incremental fashion, to reduce simulation time. Next is the DD EI calculation, which determines the final data dependency executable independence of the instructions instances. There are some further relatively minor calculations on pages 24 right through 25 right, including the final determination of semantic executable independence, and the function ends.
The next function in the main loop is asex (). In this function, those assignment instruction instances found to be ready for execution in eidetr () are actually executed, with their results being written into the Shadow Sink matrix. The Advanced Execution matrix is also updated, indicating those instances which have executed.
The next major function is memupd (), which is contained on page 29 right. First, a determination is made of which Shadow Sink registers are eligible for writing to main memory, i.e., the WSE calculations are made using the Advanced Storage matrix. Next, memory is updated with the eligible Shadow Sink values, using the addresses in Instruction Sin Address; and the Advanced Storage matrix is updated.
The next function is brex () beginning on page 27 left. In this code, the appropriate branch tests are made (very possibly more than one per cycle), and branches out of the Instruction Queue are handled.
The last major function is the dcsupd () function, which starts on page 29 right bottom. The dynamic concurrency structures are updated as indicated by branch executions. Also, fully executed iterations, in which the Advanced Execution and Advanced Storage matrix columns corresponding to that iteration and all those earlier that have all ones in them, are retired, making room for new iterations to be executed.
We have described all the major functions in the primary loop of the simcd54.c simulator program. The loop continues until a special "end-of-simulation" instruction is encountered in the test program.
Claims
I claim:
1. A central processing unit for executing a series of instructions in a computing machine having a memory for storing instructions and data elements, the central processing unit comprising: an instruction queue for storing at least a subset of the series of instructions; a plurality of processing elements coupled to said instruction queue for receiving signals indicating operations to be performed by said processing elements and for executing instructions by performing the indicated operations; loader means coupled to said instruction queue and to the memory for loading instructions from the memory to said instruction queue and for generating signals indicating relationships between the instructions stored in said instruction queue; relational matrix means coupled to said loader means for receiving an storing the signals indicating relationships between the instructions stored in said instruction queue; a branch unit, said branch unit including execution matrix means for storing signals representing the execution state of a set of iterations of each instruction stored in said instruction queue; identifying means coupled to said relational matrix means and to said execution matrix means for identifying a plurality of executable instructions from the subset of instructions in said instruction queue in response to the signals stored in the relational matrix means and the signals stored in the execution matrix means; means for coupling said identifying means to said instruction queue and to said branch unit for transmitting signals to said instruction queue and to said branch unit in response to the identified plurality of instructions; said instructions queue including means responsive to said signals from said coupling means for transmitting signals to said processing elements indicating the operations to be performed by said processing elements; said branch unit including means responsive to said signals from said coupling means for updating the execution matrix means to indicate that an instruction iteration has really executed; said branch unit including means for updating the execution matrix means in response to execution of a branch instruction to indicate that at least one instruction iteration has virtually executed; sink storage means for storing result data elements generated by the execution of instructions by said processing elements; interconnect means coupled to said instruction queue, to said processing elements, to said sink storage means, and to the memory, for transmitting data elements to and from said processing elements; and sink enable means coupled to said identifying means and to said sink storage means for generating signals for coupling selected result data elements to said interconnect means for transmission to a processing element.
2. The central processing unit of claim 1 wherein said coupling means is a resource filter.
3. The central processing unit of claim 1 wherein the identifying means comprises: means for identifying a set of procedurally executably independent instruction iterations; means for identifying at set of data executably independent instruction iterations; and means for identifying a set of instruction iterations which are both data executably independent and procedurally executably independent.
4. The central processing unit of claim 3 wherein said means for identifying a set of procedurally executably independent instructions and said means for identifying a set of data executably independent instructions function concurrently.
5. The central processing unit of claim 3 wherein: said instruction queue comprises means for storing n instructions at locations IQ(i), where i is an integer greater than zero and less than or equal to n; said sink storage means comprises a plurality of addressable register means for storing, in register location SSI(k,l), the result values generated by the execution of instruction IQ(i) in iteration (1); said relational matrix means comprises at least two data dependency matrices, each data dependency matrix DDz corresponding to a separate instruction source data element z and having a plurality of binary elements DDz(i,j) for indicating whether instruction IQ(j) is data dependent on instruction IQ(i); and said execution matrix means comprises: a real execution matrix having a plurality of binary elements RE(i,j) for indicating whether iteration (j) of instruction IQ(i) has really executed; and a virtual execution matrix having a plurality of binary elements VE(i,j) for indicating whether iteration (j) of instruction IQ(i) has virtually executed.
6. The central processing unit of claim 5 further comprising: memory update means coupled to said sink storage means, said relational matrix means, said execution matrix means, and said memory for copying data elements from said sink storage means to the memory.
7. The central processing unit of claim 6 wherein said memory update means comprises: instruction sink address means for storing a memory address for each of the data elements stored in said sink storage means; and memory update enable means for enabling the writing of a selected data element in said sink storage means to the memory at the stored memory address for the selected data element.
8. The central processing unit of claim 7 wherein said means for identifying a set of procedurally executably independent instruction iterations comprises means for identifying an instruction iteration beyond an unexecuted conditional branch instruction as procedurally executably independent.
9. The central processing unit of claim 8 wherein said means for identifying instruction iterations beyond unevaluated conditional branch instructions comprises means for identifying a set of instructions within an innermost loop.
10. The central processing unit of claim 5 wherein said means for identifying a set of data executably independent instructions comprises: means for determining, for each iteration j of each instruction IQ(i), whether a source data element z of instruction iteration (i,j) is in said memory; and means for determining, for each iteration j of each instruction IQ(i), whether a source data element z of instruction iteration (i,j) is in said sink storage means; the instruction iteration (i,j) being identified as data executably independent if all source data elements of instruction iteration (i,j) are either in the memory or in said sink storage means.
11. The central processing unit of claim 10 wherein said means for determining whether a source data element z of instruction iteration (i,j) is in said sink storage means comprises means for determining whether there is a location SSI(k,l) in said sink storage means satisfying the following conditions: SSI(k,l) has been generated by the real execution of instruction IQ(k) in iteration l; instruction IQ(i) is data dependent upon instruction IQ(k) for source data element d; and for all instruction iterations (e,f) serially between instruction iteration (k,l) and instruction iteration (i,j), either instruction IQ(i) is not data dependent on instruction IQ(e) for source data element z or instruction iteration (e,f) has virtually executed.
12. The central processing unit of claim 11 wherein said means for determining whether a source data element z for instruction iteration (i,j) is in said memory comprises means for determining whether, for all instruction iterations (e,f) serially prior to instruction iteration (i,j), either instruction IQ(i) is not data dependent on instruction IQ(e) for source data element z or instruction iteration (e,f) has virtually executed.
13. The central processing unit of claim 10 wherein said means for determining whether a source data element z for instruction iteration (i,j) is in said sink storage means comprises means for determining whether there is a location SSI(k,l) in said sink storage means satisfying the following conditions: and for all instruction iteration (e,f) serially between instruction iteration (k,l) and instruction iteration (i,j), either DDz(e,i)=0 or VE(e,f)=1.
14. The central processing unit of claim 13 wherein said means for determining whether a source data element z for instruction iteration (i,j) is in said memory comprises means for determining whether, for all instruction iterations (e,f) serially prior to instruction iteration (i,j), either DDz(e,i)=0 or VE(e,f)=1.
15. The central processing unit of claim 10 wherein said means for determining whether a source data element is in said memory and said means for determining whether a source data element is in said sink storage means function concurrently.
16. The central processing unit of claim 15 wherein said means for determining whether a source data element is in said memory is operative to concurrently make such determination for each iteration of each instruction; and said means for determining whether a source data element is in said sink storage means is operative to concurrently make such determination for each iteration of each instruction.
17. The central processing unit of claim 10 wherein said means for identifying a set of data executably independent instructions comprises: means for concurrently determining, for each instruction iteration (i,j), and each source data element z, whether all source data elements of instruction iteration (i,j) are either in the memory or in said sink storage means.
18. A method for concurrently executing a series of instructions in a computing machine having a central processing unit and a memory for storing instructions and data elements, comprising the steps of: loading at least a subset of the series of instructions from the memory in an instruction queue; substantially concurrently with said loading steps: generating signals indicating relationships between the instructions loaded in said instruction queue; storing in a relational matrix means the signals indicating relationships between the instructions stored in said instruction queue; storing in an execution matrix means signals representing the execution state of a set of iterations of each instruction stored in said instruction queue; identifying a first plurality of executable instructions from the subset of instructions in said instruction queue in response to the signals stored in said relational matrix means and said execution matrix means; thereafter concurrently executing a selected subset of the first plurality of identified instructions using a plurality of processing elements; updating the execution matrix means to indicate that the instructions executed by the plurality of processing elements have really executed and to indicate, in response to the execution of a branch instruction, that some instructions have virtually executed; storing in a sink storage matrix result data elements generated by the execution of instructions by the plurality of processing elements; using the updated execution matrix means to repeat the identifying step to identify a second plurality of executable instructions; and concurrently executing a selected subset of the identified second plurality of instructions using at least one of the data elements stored in the sink storage matrix.
19. The method of claim 18 wherein the identifying step comprises: identifying a set of procedurally executably independent instruction iterations; identifying a set of data executably independent instruction iterations; and identifying a set of instruction iterations which are both data executably independent and procedurally executably independent.
20. The method of claim 19 wherein: said loading step comprises the step of storing in said instruction queue n instructions at locations IQ(i), where i is an integer greater than zero and less than or equal to n; said step of storing date elements in the sink storage matrix comprises the step of storing, in location SSI(k,l), the result values generated by the execution of instruction IQ(k) in iteration (l); said step of storing signals in the relational matrix means comprises the step of storing a plurality of binary elements DDz(i,j) indicating whether instruction IQ(j) is data dependent on instruction IQ(i) for source data element z; and said step of storing signals in the execution matrix means comprises the steps of: storing in a real execution matrix a plurality of binary elements RE(i,j) indicating whether iteration (j) of instruction IQ(i) has really executed; and storing in a virtual execution matrix a plurality of binary elements VE(i,j) indicating whether iteration (j) of instruction IQ(i) has virtually executed.
21. The method of claim 20 wherein said step of identifying a set of procedurally executably independent instructions and said step of identifying a set of data executably independent instructions are performed concurrently.
22. The method of claim 20 further comprising the step of: copying selected data elements from said sink storage matrix to the memory.
23. The method of claim 22 wherein said step of copying selected data elements to memory comprises the steps of: storing a memory address for each of the data elements stored in said sink storage matrix; and enabling selected data elements in said sink storage matrix to be copied to the memory.
24. The method of claim 23 wherein said step of identifying a set of procedurally executably independent instruction iterations comprises the step of identifying an instruction iteration beyond an unexecuted conditional branch instruction as procedurally executably independent.
25. The method of claim 24 wherein said step of identifying instruction iterations beyond unevaluated conditional branch instructions comprises the step of identifying a set of instructions within a innermost loop.
26. The method of claim 20 wherein said step of identifying a set of data executably independent instruction iterations comprises: determining, for each iteration j of each instruction IQ(i), whether a source data element z of instruction iteration (i,j) is in said sink storage matrix; and identifying the instruction iteration (i,j) as data executably independent if all source data elements of instruction iteration (i,j) are either in said memory or in said sink storage matrix.
27. The method of claim 26 wherein said step of identifying a set of data executably independent instructions comprises: concurrently determining, for each instruction iteration (i,j) and each source data element z, whether all source data elements of instruction iteration (i,j) are either in the memory or in said sink storage matrix.
28. The method of claim 26 wherein said step of determining whether a source data element z for iteration j of instruction IQ(i) is in said sink storage matrix comprises the step of determining whether there is a location SSI(k,l) in said sink storage matrix satisfying the following conditions: SSI(k,l) has been generated by the real execution of instruction IQ(k) in iteration l; instruction IQ(i) is data dependent upon instruction IQ(k) for source data element d; and for all instruction iterations (e,f) serially between instruction iteration (k,l) and instruction iteration (i,j), either instruction IQ(i) is not data dependent on instruction IQ(e) for source data element z or instruction iteration (e,f) has virtually executed.
29. The method of claim 28 wherein said step of determining whether a source data element z for instruction iteration (i,j) is in the memory comprises the step of determining whether, for all instruction iterations (e,f) serially prior to instruction iteration (i,j), either instruction IQ(i) is not data dependent on instruction IQ(e) for source data element z or instruction iteration (e,f) has virtually executed.
30. The method of claim 6 wherein the step of determining whether a source data element z for instruction iteration (i,j) is in said sink storage matrix comprises the step of determining whether there is a location SSI(k,l) in said sink storage matrix satisfying the following conditions: and for all instruction iterations (e,f) serially between instruction iteration (k,l) and instruction iteration (i,j), either DDz(e,i)=0 or VE(e,f)=1.
31. The method of claim 30 wherein the step of determining whether a source data element z for instruction iteration (i,j) is in said memory comprises the step of determining whether, for all instruction iterations (e,f) serially prior to instruction iteration (i,j), either DDz(e,i)=0 or VE(e,f)=1.
32. The method of claim 26 wherein said step of determining whether a source data element is in said and said step of determining whether a source data element is in sink storage matrix are performed concurrently.
33. The method of claim 32 wherein said step of determining whether a source data element is in said is performed concurrently for each iteration of each instruction; and said step of determining whether a source data element is in sink storage matrix is performed for each iteration of each instruction.
Patent Citations (3)
Non-Patent Literature (18)
- R. M. Tomasulo, "An Efficient Algorithm for Expoiting Multiple Arithmetic Units", IBM Journal pp. 25-33, Jan. 1967.
- G. S. Tjaden and M. J. Flynn, "Detection and Parallel Execution of Independent Instructions". IEEE Transactions on Computers C-19 (10) pp. 889-895, Oct. 1970.
- G. S. Tjaden, "Representation of Concurrency with Ordering Matrices", PhD Thesis, The Johns Hopkins University, 1972.
- G. S. Tjaden and M. J. Flynn, "Representation of Concurrency with Ordering Matrices", IEEE Transactions on Computers, C-22(8) pp. 752-761, Aug., 1973.
- E. M. Riseman and C. C. Foster, "The Inhibition of Potential Parallelism by Conditional Jumps", IEEE Transactions on Computers, pp. 1405-1411, Dec., 1972.
- R. M. Keller, "Look-Ahead Processors", ACM Computing Surveys, 7(4) pp. 177-195, Dec., 1975.
- J. A. Fisher, "Trace Scheduling: A Technique for Global Microcode Compaction", IEEE Transactions on Computers, C-30(7), Jul., 1981.
- R. P. Colwell, R. P. Nix, J. J. O'Donnell, D. B. Papworth and P. K. Rodman, "A VLIW Architecture for a Trace Scheduling Compiler", In Proceedings of the Second International Conference Architectural Support for Programming Languages and Operating Systems, (ASLOS II), pp. 180-192. ACM-IEEE, Sep. 1987.
- J. E. Smith, "A Study of Branch Prediction Strategies", In Proceedings of the 8th Annual Symposium on Computer Architecture, pp. 135-148, ACM-IEEE, 1981.
- J. K. F. Lee and A. J. Smith, "Branch Prediction Strategies and Branch Target Buffer Design", Computer, IEEE Computer Society 17(1) pp. 6-22, Jan., 1984.
- J. E. Thornton, "Design of a Computer System: The Control Data 6600", pp. 125-140. Scott Foresman & Co., 1970.
- S. Weiss and J. E. Smith, "Instruction Issue Logic in Pipelined Supercomputers", IEEE Transactions on Computers c-33(11), Nov., 1984.
- Y. Patt, W. Hwu and M. Shebanow, "HPS, a New Microarchitecture: Rationale and Introduction", In Proceedings of MICRO-18, pp. 100-108. ACM, Dec., 1985.
- R. D. Acosta, J. Kjelstrup and H. C. Torng, "An Instruction Issuing Approach to Enhancing Performance in Multiple Functional Unit Processors". IEEE Transactions on Computers C-35 pp. 815-828, Sep., 1986.
- S. McFarling and J. Hennessay, "Reducing in Cost of Branches", In Proceedings of the 13th Annual Symposium on Computer Architecture, pp. 396-403. ACM-IEEE, Jun. 1986.
- R. G. Wedig, "Detection of Concurrency in Directly Executed Language Instruction Streams", PhD Thesis, Stanford University, Jun., 1982.
- R. Perron and C. Mundie, "The Architecture of the Alliant FX/8 Computer", In Proceedings of COMPCON 86, pp. 390-393. IEEE, Mar., 1986.
- Cydrome, Inc., "CYDRA 5 Directed Dataflow Architecture", Technical Report, Cydrome, Inc. 1589 Centre Pointe Drive, Milpitas, Calif 95035, 1987.