Source: http://www.google.co.uk/patents/EP0087978A2?cl=en
Timestamp: 2018-01-22 06:49:11
Document Index: 13025141

Matched Legal Cases: ['art; 2', 'art 1', 'art 5', 'art 9', 'art 9', 'art 9', 'art 9', 'art 5', 'art 5', 'art 9', 'art 9', 'art 12']

Patent EP0087978A2 - Information processing unit - Google Patents
In a data flow type information processing unit, an instruction indicates whether operand data for use with this instruction has become active, and an instruction execution part is started by a control signal indicating that all operands necessary for executing the instruction have become active, whereby...http://www.google.co.uk/patents/EP0087978A2?cl=en&utm_source=gb-gplus-sharePatent EP0087978A2 - Information processing unit
Publication number EP0087978 A2
Application number EP19830301103
Also published as CA1204516A, CA1204516A1, DE3379850D1, EP0087978A3, EP0087978B1, US4675806
Publication number 1983301103, 83301103, 83301103.4, EP 0087978 A2, EP 0087978A2, EP-A2-0087978, EP0087978 A2, EP0087978A2, EP19830301103, EP83301103
Patent Citations (4), Referenced by (2), Classifications (9), Legal Events (17)
EP 0087978 A2
In a data flow type information processing unit, an instruction indicates whether operand data for use with this instruction has become active, and an instruction execution part is started by a control signal indicating that all operands necessary for executing the instruction have become active, whereby the instruction and data can be moved by separate circuits. The processing unit has a data memory (3) for operand data, an instruction memory (2) for instructions, an instruction fetch part (5) for fetching an executable instruction from the instruction memory (2) and an operation unit (7) for loading desired operand data from the data memory (3) to execute the fetched instruction.
1. An information processing unit which makes an instruction executable on the basis of the determination that operand data necessary for executing the instruction becomes or will become effective and properly executes the instruction by hardware and in which the instruction has an operation code field, an input field having a sufficient number of bits to indicate whether the operand data to be used by the instruction is active or non-active, and a destination field for specifying the input field of another instruction to be linked with the instruction and the instruction is arranged so that when it is executed, it is indicated in the input field of the another instruction specified by the destination field that the operand data is active, the information processing unit comprising:
an instruction memory for storing the instructions;
an instruction fetch part for fetching an executable instruction or instructions from the instruction memory; and
an operation unit for loading desired operand data from the data memory to execute the fetched instruction or instructions in parallel.
2. An information processing unit according to claim 1 wherein operation pipelines by a.plurality of operators are operable in parallel but asynchronously in the operation unit.
3. An information processing unit according to claim 1 wherein the operation unit performs vector processing which stores a plurality of data in one data register and executes a plurality of the same operations by the data at a time.
4. An information processing unit according to claim 3 wherein when the numbers of data registers are assigned, the operation unit limits the execution of a program by software to a range in which not to exceed the number of registers provided by hardware.
5. An information processing unit according to claim 3 wherein when the number of register is exceeded, the operation unit saves data by hardware into a memory or another register to release the data register from its busy state.
The present invention relates to an information processing unit and, more particularly, to a data flow type information processing unit.
In a Von Neumann type information processing unit, the execution of an instruction is subject to what is called sequential control but, in a data flow type information processing unit, an instruction can be executed when data necessary therefor is available and the sequence of the execution of instructions can be freely determined by hardware and, further, a plurality of instructions can be executed in parallel. Therefore, a data flow type information processing unit is effective, for example, for the implementation of a vector processor which executes vector instructions in parallel.
However, the application of the configuration of a conventional data flow type information processing unit to an information processing unit for scentific computations encounters various problems. A major one of the problems is that, in the conventional data flow type information processing unit, an instruction and data (values) are mixed into one packet for transfer. On account of this, in the conventional data flow type information processing unit, a hardware circuit for moving an instruction and a circuit for transferring data cannot be separated, which offsets one of the advantages that break what is called the Von Neumann bottleneck.
An embodiment of the present invention can provide an information processing unit which performs instruction processing on the basis of the dependency of an instruction on data and in which paths for the instruction and the data are separated and the data is transferred in dependence on control.
An embodiment of the present invention can provide an information processing unit in which a desired one of instructions is determined on the basis of a proper sequence and, when it is assigned a register number, a register number assign processor automatically assigns a register in which to set the processing result by hardware processing and the software side is required only to output a data flow graph.
An embodiment of the present invention can provide an information processing unit in which register numbers are prepared corresponding to instructions, thereby to permit identification of data.
An embodiment of the present invention can provide an information processing unit in which when an instruction is issued to an operation unit, the content of an input field of the instruction is cleared to make it non-active, enabling the instruction to be utilized as the next instruction.
According to the present invention, in an information processing unit of the type that makes an instruction executable on the basis of the determination that operand data necessary for executing the instruction becomes or will become effective and properly executes the instruction by hardware, the instruction used has an operation code field, an input field having a sufficient number of bits to indicate whether operand data to be used by the instruction is active or non-active, and a destination field for specifying an input field of an instruction to be linked with this instruction, and this instruction is arranged so that when it is executed, it is indicated in the input field of the instruction designated by the destination field that the operand data is active. The processing unit is provided with an instruction memory for storing the abovesaid instruction fetch part for fetching an executable instruction from the instruction memory, and an operation unit for loading desired operand data from the data memory to execute the fetched instructions in parallel.
An embodiment of the present invention can provide a data flow type information processing unit arranged so that an input field of an instruction is given information indicating whether operand data to be used by the instruction has already been made active, and that the operand data is transferred in dependence on control corresponding to an instruction.
Figs.IA and IB are schematic diagrams showing examples of instruction formats for use in embodiments of the present invention;
Figs.2A and 2B are schematic diagrams explanatory of linkage of control according to embodiments of the present invention;
Fig.3 is a block diagram illustrating the hardware arrangement of an embodiment of the present invention;
Fig.4A is a flowchart, and Fig. 4B is. an associated list, explanatory of an instruction processing operation in an embodiment of the present invention;
Fig.5 is a timing chart explanatory of execution of an instruction in the embodiment shown in Fig. 3;
Fig.6 is a block diagram illustrating the hardware arrangement of another embodiment of the present invention; and
Fig.7 is a timing chart explanatory of the execution of an instruction in the embodiment shown in Fig.6.
In embodiments of the present invention, instructions related to operations have such an instruction format as shown in Fig.lA which comprises an instruction code (OP) field, two input fields (Rl,R2), and a destination field (D). On the other hand, instructions related to control, such as copy, switch and union, have such an instruction format as shown in Fig.lB which comprises an instruction code (OP) field, an input field (R1) and two destination fields (D1, D2). The input field and the destination field need not always be one or two in number but may also be three or more in number.
Now, assuming such graph type instruction control linkage as shown in Fig. 2A in which "instructions ① and ③ are first executed to make an instruction executable and then an instruction ④ is executed to make instructions ⑤ and ⑥ executable", the content of the destination field of the preceding instruction determines its linkage with the input field of the instruction to be executed next as shown in Fig. 2B. That is to say, by the determination that operand data becomes or will become active as a result of the execution of the instruction ①, a certain value is set in the input field R1 of the instruction ② specified by the destination field D of the instruction ① indicating that one of the operand data to be used by the instruction ② has become active. Similarly, by the determination that operand data becomes or will become active as a result of the execution of the instruction ③ a certain value is set in the input field R2 of the instruction ② specified by the destination field D of the instruction ③ indicating that another one of the operand data to be used by the instruction ② has become active. And, by completion of the execution of the instruction a certain value is set in the input field R1 of the instruction ④ specified by the destination field D of the instruction ② indicating that the instruction ④ has become executable. Likewise, by completion of the execution of the instruction ④, values are set in the input fields of the instructions ⑤ and ⑥ specified by the destination fields D1 and D2 of the instruction ④, whereby the instruction ④ is linked with-the instructions ⑤ and ⑥.
In the case of the present invention, it is sufficient theoretically that the input field shown in Figs. lA and 1B is a 1-bit field (indicating that the operand data has becomes active), but it is preferable that the input field be of an 8-bit field length, as shown in Figs. 1A and 1B, to permit writing therein the number of the register in which the operand data is being set, thereby indicating that the operand data has become active, coupled with writing of the register number.
Incidentally, the instructions for use in the present invention are (i) four operations, such as ADD, MULTIPLY, DIVIDE and so forth., (ii) ordinary instructions, such as COMPARE, LOGICAL, SHIFT, MASKLOGICAL, LOAD, STORE and so forth, (iii) control instructions, such as COPY, SWITCH, UNION and so forth, (iv) function link instructions, such as APPLY and so on, and (v) interface instruction for external part, such as input/output. It is also possible that these instructions are each provided both as a vector instruction and as a scalar instruction, if necessary.
Fig. 3 illustrates the hardware structure of an embodiment of the present invention. In Fig. 3, reference numeral 1 indicates an interface for external part; 2 designates an instruction memory-having stored therein such instructions as shown in Figs. 1A and 1B; 3 identifies a data memory having stored therein operand data; 4 denotes a memory controller which performs processing of accessing the data memory 3 to load desired operand data in a register of the register number specified by the contents of the input fields Rl and R2 or restoring operation results in the data memory 3; 5 represents an instruction fetch part which checks whether instructions read out from the instruction memory 2 are executable and fetches the executable instruction; and 6 shows a register number assign processor in which when resources to be used by the executable instruction, such as an operator, a register and so forth, are usable, it is determined to issue the instruction, the number of a register for storing a destination operand of the instruction is assigned and hardware performs automatic assign processing. The assigned register number is provided to the instruction fetch part, which writes the register number into the input field of another instruction specified by the destination field of the abovesaid instruction. Reference numeral 7 refers to an operation unit, which comprises a single or a plurality of operation parts and executes a desired operation; 8 signifies a register group; and 9 indicates an active instruction list part, in which executable but queued instructions are held in the form of a list. The abovesaid data memory and instruction memory may also be physically the same memory.
A description will be given,with reference to the flow-chart of Figs. 4A & 4B, of iheoperation of the embodiment shown in Fig. 3.
(1) The interface for external part 1 has interfaces with a central processing unit, an input/output device and so on, and performs processing of transferring data between other devices and the data memory 3. Furthermore, it performs processing of writing an instruction into the instruction memory 2 as required.
(2) Now, let it be assumed that it is determined that the execution of an instruction is completed or will be complete. In this state, address information based on the content of the destination field of the instruction is set in an address register for the instruction memory 2.
(3) By this, one instruction is fetched from the instruction memory 2.
(4) If the fetched instruction contains the input field of another instruction, the instruction fetch part 5 checks whether the input field is active.
(5) If the input field is not active, an already assigned register number is written into the input field specified by the destination field and the fetched instruction is returned to the instruction memory 2.
(6) If the input field is active, the register number is assigned and the execution of the instruction is started. At this time, however, i-f a desired operation unit or the like is busy, address information representating the instruction is registered in the active instruction list part 9 and the assigned register number is written into the input field of that one of the instructions in the instruction memory 2 which is specified by the destination field of the instruction.
(7) If another instruction has been registered in the active instruction list part 9, then it is fetched from the instruction memory 2 for execution next. In the event that another instruction has not been registered in the active instruction list part 9, the instruction memory 2 is accessed, for instance, in accordance with the content of a sequential memory in search for an active instruction. Of course, the active instruction list part 9 may be dispensed with and, in such a case, an executable instruction is executed after the desired operation unit or the like is released from the busy state but the accuracy of parallel execution of instructions is decreased, resulting in impaired performance.
(8) When the desired operation part or the like is not busy during the processing (6), if the same processing as mentioned above in (6) is performed, the instruction is left in the executable state. To avoid this, the instruction fetch part 5 clears the content of the input field of the fetched instruction and rewrites it into the instruction memory 2 on the assumption that it is determined that the instruction is completed or will be completed.
(9) The register number assign processor 6 determines, by hardware processing, the register number to be written into the input field of an instruction specified by the destination field and then issues an instruction to the operation unit 7.
(10) On the other hand, the instruction fetch part 5 sets the content of the abovesaid destination field in an address register (not shown) of the instruction memory 2.
(11) In the operation unit 7 a plurality of instruction usually run in parallel.
(12) When an interrupt occurs, for instance, a fixed address is'produced as in the case of the conventional data flow type information processing unit and an interrupt-servicing program which starts with an instruction stored at that address is executed.
(13) Upon completion of a certain instruction, the operation unit 7 sets the operation results in a register predetermined by the register number assign processor 6. In the above, if a plurality of set conditions are present when setting the address register of the instruction memory 2, then an address on a specified condition is set through using a proper priority circuit.
Fig. 5 shows an example of a timing chart of the execution of an instruction according to the present invention. In a time slot T1, an instruction is fetched; in a time slot T2, the instruction is decoded; in a time slot T3, it is checked whether the instruction is executable, and the register number is assigned; in a time slot T4, the instruction is issued to the operation unit 7; in time slots T5 to T8, an operation is executed; in the time slot T8, an address based on the content of the destination field of the instruction is set in the address register of the instruction memory 2; and in a time slot T9, the next instruction is fetched which is linked with the instruction executed. When the operation unit happens to be busy in the above, the instruction is registered in the active instruction list part 9 in the time slot T4 and processing of fetching another instruction from the active instruction list part 9 takes place in the time slot T5 and, in the time slot T6, the address setting is performed.
In the case where the instruction contains two destination fields, one of two next instructions is fetched on the basis of the content of a first one of two destination fields and then the other next instruction is fetched on the basis of the content of the second destination field. The instructions 2 to 5 are processed one after another in a pipeline fashion as shown in Fig. 5.
In the present invention, for example, a plurality of operators in the operation unit 7 need not always be synchronized in operation but the pipelines may also operate in parallel and asynchronously.
The abovesaid data register can easily be applied to vector processing, too, in which a plurality of data (vector data) are all stored in one register and a plurality of the same operations are executed by these data at a time. Scalar processing which processes a single data can also be simplified by considering that it is a special case of handling a single data in the vector processing. When the register number are assigned, they may sometimes exceed the number of registers that hardware has, causing a deadlock. This can be avoided by a system in which program execution is limited by software within a range in which the register numbers do not exceed a specified number of registers, or a system in which the data is saved by hardware into a memory or another register, thereby to release the data register from the busy state.
Figs. 6 and 7 show the hardware structure of another embodiment of the present invention and a timing chart of the execution of an instruction in the embodiment, respectively. An instruction group is preset by an external control circuit in an instruction memory 21. Upon application of external data, an address is set in an address register 11 and the instruction@ is read out from the instruction memory 21 and set in an instruction register 15. Thereafter the external data is applied from an input 26 and provided via registers 18 and 19 to a data memory 22. The address of the data memory 22 is supplied from an address register 16 via registers 13 and 14. Since it is known that the instruction read out into the instruction register 15 is an external set instruction, the instruction@ is read out on the basis of the content of its destination field (that is, the Rl part of the instruction ②). The instruction ② set in the instruction register 15 cannot be executed because its R2 part is not active. Then the operation shifts to processing of the instruction ③ resulting from the arrival of external data. The data entered from the input 26 is provided to the register 18. The destination of the instruction ③ is the R2 part of the instruction ② and the instruction ② has already been stored in the instruction register 15 until then. Since its Rl part is active, the instruction ② is executable. Then the instruction ② is provided to an operator 23 via the register 18. At this time, data corresponding to the Rl part is read out from the data memory 22 by the address of the address register 16 based on the instruction ② stored in the instruction register 15 and the data thus read out isprovided to the register 17, from which it is applied to the operator 18 together with the abovesaid data stored in the register 18. As a result of this, the instruction ② is executed and the execution result is.:applied to the register 18. The output of the register 18 is provided to the register 19 and, at this time, the destination of the instruction ② sent via the registers 13 and 14 is provided via the address register 16 to the data memory 22, by which the result of execution of the instruction ② in the register 19 is written into the data memory 22. Since the destination of the instruction is ④ the abovesaid execution result is written into the data memory 22 at an address corresponding to the instruction ④. The instruction ④ is a two-branch instruction and, consequently, data ④ and
are written into the data memory 22 at addresses corresponding to the instructions ⑤ and ⑥ respectively. In this case, the instructions ②, ④ and
are written into the data memory 22 via a route [address register 11 → register 13 + register 14 + address register 16]. Since the data is the same as the result of execution of the instruction ②, the same data as the instruction ② is held in the registers 18 and 19. The instructions ⑤ and ⑥ are linked with the next instructions and the processing therefor is performed in the same way as mentioned above; hence no description will be given thereof.
In the above, if the number of words of the instruction memory and the data memory are selected to be the same, data does not overflow. The addresses of the instruction memory and the data memory have one-to-one correspondence. Incidentally, since the data memory is not used in some cases, the number of words of the data memory may be smaller than the number of words of the instruction memory but, in such a case, an address converter or associative storage is needed. In the timing chart of Fig.7 the esecution of an instruction is performed in one cycle; but, if several cycles are required for the execution of an instruction, an instruction fetch must be delayed for several cycles correspondingly.
Registers 24 and 25 may carry the instruction code of an instruction set in the instruction register 15 to the operator 23 to determine the operation to be effected.
Address register part 12 and the illustrated + (+1) counter may be for address incrementing ( or decrementing).
FR2083696A1 * Title not available
WO1998037485A1 * 19 Feb 1998 27 Aug 1998 Richard Byron Wilmot Method and apparatus for forwarding of operands in a computer system
Cooperative Classification G06F9/3889, G06F9/4436, G06F9/38
28 Jan 1987 17Q First examination report
Ref document number: 3379850
18 Apr 1990 26 Opposition filed
19 Jun 1991 27O Opposition rejected
2 Mar 2000 PG25 Lapsed in a contracting state announced via postgrant inform. from nat. office to epo
25 Oct 2000 GBPC Gb: european patent ceased through non-payment of renewal fee