Circuitry for parallel processing of commands in a digital computer

The subject of the invention is a system for parallel processing of orders in a digital computer.

The work of well-known digital computers that execute orders one by one in sequential order has improved significantly due to the improvement of system technology. Such computers that execute orders one by one are sometimes called scalar computers. However, technological possibilities are limited, so computer designers had to use other means to achieve a significant improvement in their work.

Also known are super-scalar computers that improve work by executing more than one order at a time from a single instruction stream. Such known super-scalar computers usually decide during the execution of orders whether a given number of orders can be executed in parallel. This decision is based on the operational order codes and data dependencies that may occur between neighboring orders. Operating codes specify the individual hardware components that each command will use, and it is usually not possible for two or more commands to use the same hardware component at the same time, or to execute an order that depends on the results of the previous order (data dependency). These hardware and data dependencies prevent certain command combinations from being executed in parallel.

In this case, the running commands are instead executed themselves in a non-parallel manner. This, of course, worsens the work of the super-scalar computer.

Known super-scalar computers provide some improvement in work, but also have disadvantages that would be desirable to minimize. On the one hand, deciding when executing commands that can be executed in parallel takes a small but noticeable amount of time that cannot be easily masked by imposing it on other normal device operations. This disadvantage becomes more pronounced when the complexity of building the instruction set increases. Another disadvantage is that the execution of decisions must be repeated constantly, each time when the same orders are to be executed a second or next time.

A known device of this type is presented in Patent Application No. P-289 722 disclosing a computer architecture with a set of sequential orders. In application4

165 491 Patent Patent P-289 723 presents a general-purpose computer system for parallel processors at the instruction level. In contrast, Patent Application No. P-289 721 discloses a computer system that reduces data dependency.

Patent application P-289 722 presents one of the features of a computer with a set of sequential orders, consisting in not making decisions related to parallel execution during its duration, but making it at an earlier stage of the entire order processing process. For example, this can be done before the command buffer memory on those computers that have the command buffer memory or the command column memory. In another example, this can be done before the instruction cache on those computers that carry the instructions through the cache. Another feature of this computer is the recording of the results of making parallel processing decisions in such a way that such results are achieved when the same orders are used a second or next time.

The essence of the system for parallel processing of orders in a digital computer, according to the invention, containing memory circuits, is that it comprises a connecting circuit whose input is connected to the output of the first memory circuit, preferably of high capacity and low speed, and the output is connected to the second input a memory circuit, preferably a low-capacity and high-speed cache, a circuit for downloading and issuing orders, whose input is connected to the output of the second memory circuit, and at least two functional command processing units whose inputs are connected to the output of the download and issue of circuits.

Preferably, according to the invention, the connecting circuit comprises an instruction input register with at least three memory tables, the input of which is connected to the output of the first memory circuit, at least one complexity signal analyzer, whose input is connected to the output of the instruction input register, tag generation circuit whose at least two inputs are connected to two outputs of the complexity signal analyzer, instruction output register with at least three memory tables, of which at least three inputs are connected to three marker generation circuit outputs, where the instruction output register output is connected to the input of the second memory circuit.

Further benefits are obtained when, according to the invention, the complexity signal analyzer comprises a first instruction compliance detection circuit whose two instruction operational code inputs 0 and an instruction operational code 1 are connected to the instruction input register output, a second instruction instruction detection circuit whose two operational code inputs instruction 1 and the operational code of instruction 2 are attached to the command input register output, the first and second registers detection detection circuit, whose inputs are connected to the output of the instruction input register, the first element I, whose first input is connected to the output of the first instruction compliance detection circuit, the second input is connected to the output of the first dependency detection circuit, and the output is connected to the first input of the tag generation circuit, and the second element I, whose first input is connected to the output of the second instruction compliance detection circuit, the second input is connected to the output of the second register dependency detection circuit, and the output is connected to the second input of the tag generation circuit.

Further advantages of the invention are obtained when the first and second instruction compliance detection circuits comprise three decoders, each with an instruction operating code input 0, with an instruction operational code input 1, and with an operational instruction code input 2 connected to the instruction input register output, third element I whose first input is connected to the first output of the first decoder and the second input is connected to the first output of the second decoder, the fourth element I, whose first input is connected to the second output of the first decoder and the second input is connected to the first output of the second decoder, the fifth element I, whose first input is connected to the first output of the second decoder, and the second input is connected to the first output of the third decoder , sixth element I, whose first input is connected to the second output of the second decoder, and the second input is attached to the first output of the third decoder, the first OR element whose first input is attached to

165 491 output of the third element I, the second input is connected to the output of the fourth element, I and the output is connected to the first input of the tag generation circuit, and the second OR element whose first input is connected to the output of the fifth element I, the second input is connected to the sixth output element I, and the output is connected to the second input of the tag generation circuit.

It is also advantageous if, according to the invention, the tag generation circuit comprises a first NIE element whose input is connected to the first output of the complex signal analyzer and the output is connected to the input of the instruction output register, the second NO element whose input is connected to the second output of the complex signal analyzer, the third OR element whose first input is connected to the first output of the complexity signal analyzer, the second input is connected to the output of the second element NIE, and the output is connected to the output of the instruction output register.

In addition, in the system according to the invention, functional instruction processing units constitute a branch instruction processing unit, an arithmetic logic unit for address generation, a universal arithmetic logic unit, and an arithmetic unit for eliminating data dependencies.

An advantage of the inventive solution is that by storing caching markers in the cache, it is possible to use the markers again at all times as long as the commands tested remain in the cache. Orders often remain cached long enough to be used more than once.

The subject of the invention is shown in the embodiment in the drawing, in which Fig. 1 shows a block diagram of a system for parallel processing of orders in a digital computer, Fig. 2 - part of the instruction stream having markers and marker fields, Fig. 3 - block diagram of a connecting circuit for a system of Fig. 1, Fig. 4 - block diagram of the complexity signal analyzer for the circuit of Fig. 3, Fig. 5 - detection circuit diagram for the analyzer of Fig. 4, Fig. 6 - a table explaining the operation of the detection circuit of Fig. 5, Fig. 7 - a block diagram of another system for parallel instruction processing explaining how complex instructions can be processed in parallel by the processing units of multiple functional instructions, Fig. 8 - a sequence of instructions that can be processed through the arrangement of Fig. 7 and Fig. 9 - an explanatory table for processing the instruction sequence of Fig. 9 by the arrangement of Fig. 7.

Figure 1 is a block diagram of a system for parallel order processing in a digital computer. This system is capable of processing two or more instructions in parallel. It has a first memory circuit 10 for storing commands and data to be processed. This memory circuit 10 is a high capacity and low speed memory, which may be, for example, a memory unit of the high capacity system of the lower part of the memory hierarchy system or the like. The system then includes a linkage circuit 11, whose input 11a is connected to the output Da of the first memory circuit 10, for receiving the instructions of the first memory circuit 10 and the associated half markers that indicate which of these commands can be processed in parallel with each other. The linking circuit 11 analyzes input commands to determine which of them can be processed in parallel. In addition, it produces for these analyzed orders tag information or half tags that indicate which commands can be processed in parallel with each other and which cannot be processed in parallel with each other.

The circuit of Fig. 1 further includes a second memory circuit 12, connected through its input 12a to output 11b of the linkage circuit 11, for the purposes of receiving and remembering the instructions being analyzed and the associated half marks. This second memory circuit 12 is a cache of complex instructions. Cache is a low capacity and high speed memory system commonly used to improve the speed of a computer by reducing the frequency of access to the first low speed memory circuit.

The circuit of Fig. 1 also includes a 16 command download and issuing circuit connected through its input 16a to the output 12b of the second memory circuit 12 for delivery

165 491 stored adjacent instructions to various functional processing units 13, 14, 15 orders, when the order marker fields indicate that they can be processed in parallel. Output 16b of the download and issue 16 commands circuit is connected to inputs 13a, 14a, 15a of these functional processing units. The 16-command download and issue circuit provides commands from the second memory circuit 12, examines their tag fields and operational code fields, and based on these tests sends orders to the appropriate of functional units 13, 14, 15.

Units 13, 14, 15 of orders work in parallel with each other in a simultaneous manner and each of them is capable of processing one or more types of computer orders. Examples of functional processing units 13, 14, 15 that can be used are: general purpose arithmetic logic unit, address generation arithmetic logic unit, data dependency arithmetic logic unit, branch instruction processing unit, data shift unit, floating point processing unit and so on A given system may contain two or more types of these functional units. For example, a system may contain two or more general purpose arithmetic logic units. The particular configuration of functional processing units will depend on the type of system being considered.

In the case where the requested instruction occurs in the second memory circuit 12, i.e. in the cache of compound orders, the correct address is sent to the cache for delivery from my requested order. If the command requested is not in the cache, it must be provided from the first memory circuit 10 and entered into the cache. This is sometimes referred to as losing the cache. In the event of a loss, the address of the requested command is sent to the first memory circuit 10. In response to this, the circuit begins to carry or read the command line that contains the requested command. These commands are transferred to the input of the 11 orders linkage circuit, which begins to analyze these input commands and generate the correct marker field for each order. Marked orders are then delivered to the second memory circuit 12 of the complex orders and remembered therein for subsequent use, when needed, by the functional processing units 13, 14 and 15 of the instructions.

Command analysis carried out in a circuit of connecting 11 commands requires a certain, relatively short time. However, the instruction linking analysis is only performed when the instruction cache is lost and is therefore relatively rare. Figure 2 shows part of the stream of compound orders or with markers that could appear at the output of the 11 command linking circuit in Fig. 1. Each instruction Instruction . has a tag field added to it through the 11-command linking circuit. Orders with stamps, such as those shown in Fig. 2, are stored in the second memory circuit of 12 complex orders. If necessary, orders with markers in this memory circuit are provided by the 16 orders download and issue circuit. When the tagged instructions are received by the 16 instruction download and issue circuit, their tag fields are examined to determine whether they can be processed in parallel and their operational code fields are examined to determine which of the available functional units is most appropriate for their processing If the tag fields indicate that two or more instructions are suitable for parallel processing, then they are sent to the appropriate functional units in accordance with the coding of their operational code fields. Such orders are then processed simultaneously with each other by the respective functional processing units 13, 14, 15.

When encountering an order that is not appropriate for parallel processing. it is sent to the correct processing unit. as defined by its operating code, and is then processed itself and independently by the selected processing unit. In the best case, when many orders are always processed in parallel, the speed of the instructions would be N times faster than when the orders are executed one after the other, with N being the number of orders in the group that are processed in parallel.

165 491

Figure 3 shows in more detail the internal structure of the instruction linking circuit 11 according to the invention for the system of Figure 1. The command linking circuit 11 is for the case in which a maximum of two instructions can be processed in parallel at a given time.

In this case, a one-bit tag field is used. The boolean value of tag 1 means that the order is the first order. The boolean value of the 0 tag means that the order is the second order and can be executed in parallel with the course of the first command. An instruction having the logical value of tag 1 may be executed either alone or simultaneously and in parallel with the next instruction depending on the logical value of the tag for such a subsequent instruction. Each pairing of instructions having the logical value of tag 1 with the next instruction having the logical value of tag 0 creates a compound order for the purpose of parallel execution, that is, the instructions in such a pair can be processed in parallel with each other. When the marker bits for two consecutive orders have each value equal to 1, the first of these instructions is executed alone in a non-parallel order. In the worst case, all orders in the sequence would have a boolean value of 1. In the worst case, all orders would be executed one after the other in a non-parallel order.

The 11 instruction combination circuit of Fig. 3 contains an input register of 21 commands for receiving multiple consecutive instructions from the first memory circuit 10. The 11 instruction combination circuit also includes a plurality of instruction analyzers based on rules. Each such instruction analyzer analyzes a different pair of adjacent instructions in the output of the instruction 21 and produces a signal of complexity that indicates whether two instructions in a pair can or cannot be processed in parallel. Output 21b of the instruction input register 21 is connected to input 22a of the first analyzer 22 of complexity signals.

In Figure 3, multiple analyzers 22, 23, 24, 25 for complexity signals are shown. Each of these analyzers 22, 23, 24, 25 has two command analysis systems. Thus, each of these analyzers 22, 23, 24, 25 produces two signals of complexity. For example, the first complexity signal analyzer 22 produces a first complexity signal M01 that indicates whether Instr. 0 and Instr. 1 may or may not be processed in parallel. The complexity signal analyzer 22 also produces a second M12 complexity signal that indicates whether Instr. 1 and Instr. 2 may or may not be processed in parallel.

Similarly, the second complexity signal analyzer 23 generates the first possible complexity signal M23, which indicates whether Instr. 2 and Instr. 3 may or may not be processed in parallel, and a second M34 signal of complexity that indicates whether Instr. 3 and Instr. 4 may or may not be processed in parallel. The third analyzer of 24 complexity signals produces the first M45 signal of complexity, which indicates whether Instr. 4 and Instr. 5 may or may not be processed in parallel, and a second M56 signal of complexity that indicates whether Instr. 5 and Instr. 6 may or may not be processed in parallel. The fourth complexity analyzer produces the first M67 complexity signals that indicates whether Instr. 6 and Instr. 7 may or may not be processed in parallel, and a second M78 signal of complexity that indicates whether Instr. 7 and Instr. 8 may or may not be processed in parallel.

The 11 instruction linkage circuit further includes a 26 tag generation circuit. For the first analyzer of 22 complexity signals, its outputs 22b and 22c are connected to two inputs M01a and M12a of the 26 tag circuit generation. This circuit is sensitive to complexity signals appearing at the outputs of analyzers 22, 23, 24, 25 for the production of individual marker fields for various commands in the input register of 21 orders. These fields T0, T1, T2, ... markers are supplied to the inputs 27a, 27b, 27c of the output 27 orders with tags as the commands themselves, obtained from the output lines TAG0, TAG1, TAG2 of the input 21 orders. Thus, in the output register 27 commands of this linkage, the tag T0 field for Instr.0, the tag T1 field for Instr. 1 etc.

In this embodiment, each field T0, T1, T2 ... of the tags is contained in a single binary bit. A tag boolean value of 1 indicates that the immediately following order is the first order. A tag boolean value of 0 indicates that the immediately following instruction is the second instruction. An order with value

165 491 a logical tag of 1 followed by an instruction having a logical tag of 0, indicates that these two orders can be executed in parallel with each other. The orders with markers in the output register 27 of this combining circuit are provided from output 27d to the second memory circuit 12 of the compound instructions in Fig. 1 and are remembered therein. The hardware size of the register shown in Fig. 3, can be reduced by remembering the compound orders directly in the second memory circuit 12 compound orders.

Figure 4 shows the internal structure of the first complexity signal analyzer 22 in Figure 3 in more detail. The other complexity signals analyzers 23, 24, 25 have a similar structure. The complexity signal analyzer 22 shown in FIG. 4 includes a first instruction compliance detection circuit 30 for testing the operation code input OP0 of the 0 instruction OP0 and the input operation code 30b of the instruction OP1 1 and determining whether the two operating codes are compatible for parallel execution. The first detection circuit 30 is constructed according to predetermined rules for selecting which pairs of operating codes are compatible for parallel execution. More specifically, this detection circuit includes logic circuits for implementing rules that determine which types of instructions are compatible for parallel execution in a particular computer system comprising the system of the invention. If the operating codes for the commands 0 and 1 are compatible, then the first detection circuit 30 generates a logic signal on its output 30c with a value of 1. If they do not match, this circuit generates a logic value 0 on its output 30c.

The complexity signal analyzer 22 further includes a second instruction compliance detection circuit 31 for testing the input codes OP1, OP2 of commands 1 and 2 and determining whether they are compatible for parallel execution. The second detection circuit 31 is built in the same way as the first detection circuit 30, according to the same predefined rules used for the first detection circuit 30 for selection which operating code pairs are compatible for parallel execution in the case of instructions 1 and 2. Thus, this detection circuit includes logic circuits for implementing rules that determine which types of instructions are compatible for parallel execution, wherein these rules are the same as those used in the first detection circuit 30. If the operational codes for commands 1 and 2 match, then the second detection circuit 31 produces a binary output with a logic value 1. Otherwise it produces a binary output with a logic value 0.

The complexity signal analyzer 22 further includes a first detection circuit 32 of a first register dependency for detecting contradictions using general-purpose registers, designated by fields R1 and R2 of instructions 0 and 1. These general-purpose registers will be discussed in more detail below. Among other things, the first detection circuit 32 register dependencies can be built properly for detecting the occurrence of a data dependency state in which the second instruction (instruction 1) needs to use the results obtained by the operation of the previous instruction (instruction 0). In this case, either the second order can be executed by the dependency reduction system by executing in parallel with the first order, or the execution of the second command must wait for the completion of the previous order and therefore cannot be carried out in parallel with the previous order. A technique to bypass certain data dependencies of this type will be discussed later. If there are no register dependencies on the inputs 32a that prevent the execution of commands 0 and 1 in parallel, then a logical value of 1 is given on the output 32b of this register dependency detection circuit. If there is a dependency, a logical value of 0 is given.

The complexity signal analyzer 22 further includes a second detection circuit 33 for register dependencies for detecting contradictions using general purpose registers, designated by fields 31 and 32 of instructions 1 and 2. The second detection circuit 33 of the register dependencies has the same structure as the first detection circuit discussed above and produces on the output 33b a binary output signal with a value equal to 1, if there are no register dependencies on the outputs 33a or the dependencies can be implemented by systems that reduce data dependency, otherwise, a binary output with a value of 0.

165 491

Outputs 30a and 32b of the first detection compliance circuit 30 and the first detection circuit 32 of the register dependencies respectively are connected to two inputs 34a, 34b of the first element I 34. Output 34c of the first element I 34 has a logical value of 1 if the two operational codes considered match and if there are no registry dependencies. This Boolean value 1 at the output 34c of this element indicates that the two commands under consideration are possible to be assembled, i.e. they are executable in parallel. If, on the other hand, the first element I 34 has a logical value of 0 at the output, then two orders are not possible to submit. Thus, the first signal M01 of complexity is generated at the output of the first element I 34, which indicates whether instructions 0 and 1 can or cannot be processed in parallel. This M01 signal is supplied to the M01a input of a 26 tag generation circuit.

Outputs 31c and 33b, respectively, of the second instruction compliance detection circuit 31 and the second register dependency detection circuit 33 are connected to the two inputs 35a, 35b of the second element 35. The second element I 35 produces at output 35c a second signal M12 of complexity, which has a logical value of 1, if the considered operational codes (operational codes for orders 1 and 2) match and if there are no register dependencies for orders 1 and 2 or dependencies register that can be implemented by systems that reduce data dependency. Otherwise the second element I 35 has a logical value of 0. The output 35c of the second element I 35 is connected to the second input M12a of the 26 tag generation circuit.

The other complexity signal analyzers 23, 24, 25 shown in Fig. 3 have the same internal structure as shown in Fig. 4 for the first complexity signal analyzer 22.

Figure 5 shows an embodiment of detection circuits that can be used to implement the complexity signal analyzer 22 and part of the marker generator 26, which is used to produce the first three markers, TAG 0, TAG 1 and TAG 2. In the example of Fig. 5, there are two categories of orders that are marked as category A and category B. It is assumed that the rules for combining these categories of orders are as follows:

(1) A can always connect with A (2) A can never connect with B (3) B can never connect with B (4) B can always connect with A (5) Rule (4) has advantage over the rule (1).

These rules respond to requests for orders.

Then it is assumed that these rules are such that when there will be no problems with register dependencies, because the course of the rules indicates that in the event of any dependence, such dependence is always possible to be implemented by systems that reduce data dependency. In other words, it is assumed in the example of Fig. 5 that the detection circuits 32 and 33 of the register dependencies of Fig. 4 are not needed. In this case, components I 34 and 35 are also unnecessary and signal M01 appears on output 30c of the first instruction compliance detection circuit 30, and signal Ml2 appears on output 31c of the second detection circuit 31.

With these assumptions, Fig. 5 shows internal logic circuits that can be used for the instruction compliance detection circuits 30 and 31 of Figure 4. The first instruction compliance detection circuit 30 shown in Figure 5 includes decoders 40 and 41, subsequent components I 42 and 43 and the OR element 44. The second instruction compliance detection circuit 31, in turn, includes decoders 41 and 45, the next elements 46 and 47 and the next OR element 48. The middle decoder 41 is divided by both detection circuits 30 and 31.

The first detection circuit 30 examines the operating codes OP0 and OP1 of commands 0 and 1 to determine their compliance for parallel execution purposes. This is done in accordance with the rules (1) - (4) above. The first decoder 40 checks the operating code of the first command given on output 40a and if it is a category A operating code, on output line A connected to output 40b of the first decoder 40 there is a logical value of 1. If OP0 is an operating code of category B, then on output line B connected to output 40c there is a logical value 1. If OP0 does not belong to either category A or category B, then both outputs of the first decoder 40 have a logical value of 0. Second decoder 41 performs a similar type of decoding for the second OP 1 operational code.

165 491

The third element 142 used in the system according to the invention implements the above rule (1). If the I, OP0 input code of the I, OP0 inputs 42a, 42b is the category A operating code and OP1 is also the A category code, then the third element I 42 generates an output signal with the logic value at output 42c. Otherwise, the output signal of the third element I 42 has a logical value of 0. The third element I 43 implements the above rule (4). If the first operating code is an operating code of category B and the second operating code is an operating code of category A, then the third element I 43 produces an output with a logical value of 1. Otherwise it produces an output with a logical value of 0. If the third element I 42 or the next fourth element I 43 produces an output signal of value 1, it introduces the output signal at the output 44c of the first element OR 44 to logical value 1, in this case the signal M01 of complexity has a logical value of 1. This logical value 1 indicates that the first and second orders (orders 0 and 1) are compatible for parallel execution.

If any other combination of operating code categories is detected by decoders 40 and 41, then the output signals of the third element I 42 and the fourth element I 43 leave a logical value of 0 and the signal M01 of complexity has a logical value of 0 indicating the impossibility of submission. Thus, the occurrence of the combinations indicated by the above rules (2) and (3) does not cause that elements I 42 and 43 leave the M01 signal with a logical value of 0. If there are further categories of operational codes in addition to categories A and B, their appearance in the stream of orders does not stimulate the outputs of decoders 40 and 41. Therefore, they similarly give the signal M01 complexity with a logical value of 0. The second detection circuit 31 compliance of orders performs a similar type of code analysis operational for the second and third orders (orders 1 and 2) and is built like the first detection circuit 30. If the second OP1 operating code is a category A operating code and the third OP2 operating code is a category A operating code, then, according to rule (1), the fifth element I 46 produces an output with a logical value of 1 and the second signal M12 of complexity obtains a logical value of 1 indicating the option of submission. If, on the other hand, OP1 is an operating code of category B and OP2 is an operating code of category A, then, according to rule (4), the sixth element I 47 is stimulated to produce logical value 1 for the second signal M12 complexity. For any combination of operational codes other than those shown in Rules (1) and (4), the M12 signal has a logical value of 0.

M01 and M12 complexity signals are supplied to the inputs M01a, M12a circuit 26 generation markers. Fig. 5 shows a logic that can be used in a 26 tag generation circuit for response to M01 and M12 signals of complexity for generating the required tag logic values ​​for tags 0, 1 and 2.

The table in Fig. 6 shows the logical values ​​that are implemented by the 26 marker generation circuit for markers 0, 1 and 2. The marker logic value 1 indicates that the corresponding instruction is the first instruction for the purpose of parallel execution. A boolean value of 0 of the tag indicates that the corresponding instruction is the second instruction for parallel execution. The only pairs of instructions that are combined and executed in parallel are those for which the first instruction in pair has a logical value of 1 marker and the second instruction in the pair has a logical value of 0 marker. Each order having a logical value of 1 tag followed by another order having a logical value of 1 tag is executed one at a time, not in parallel with the next order.

For the first row case in Fig. 6, all three bits of the markers have the value 1. This means that each of the instructions 0 and 1 will be executed individually, not in parallel. For the second row in Fig. 6, orders 0 and 1 will be executed in parallel if marker 0 has the required logic value 1 and marker 1 has the required logic value 0. For the third row in Fig. 6, the instruction 0 will be executed individually, while the instructions 1 and 2 will be performed in parallel with each other. For the fourth row, orders 0 and 1 will be executed in parallel one after the other.

For these cases, when tag 2 has a logical value of 1, the state of the corresponding instruction depends on the logical value of tag 3. If tag 3 has a logical value of 0, then instructions 2 and 3 can be executed in parallel. If, on the other hand, tag 3

165 491 has a logical value of 1, then instruction 2 will be executed individually, not in parallel. It should be noted that the logic implemented for the 26 mark generation circuit does not allow the occurrence of two consecutive marker bits with values ​​0.

Figure 6 shows the logic needed for part of the circuit to generate the 26 markers shown in Figure 5. As shown in Figure 6, the marker 0 will always have a logic value of 1. This is achieved by providing a constant logic value 1 on the first output line 50 the 26 mark generation circuit that forms the 0 mark output limit. Figure 6 then shows that the logical value of marker 1 is always opposite to the logical value of signal M01 of complexity. This result is obtained by connecting the second output line 51 of marker 1 to the output of the first NIE 52 element whose input 52a is connected to the M01 signal line.

The logical value of marker 2 on the third output line 53 is determined by the third OR element 54 and the second element NOT 55. One input 54a of the third element OR 54 is connected to the M01 signal line. If the logical value of the M01 signal is 1 then the marker 2 is 1. This applies to the value of marker 2 in the second and fourth rows of Fig. 6. The second input 54b of the third OR element 54 is connected to the output 55b of the second element NO 55, whose output 55 is connected to the M12 signal line. If the M12 signal has a logical value of 0, this value is inverted by the second element NOT 55 to supply the logical value 1 to the second input 54b of the third element OR 54. This causes marker 2 on the third output line 53 to have a logical value of 1. This applies to the value marker 2 in the first row of fig. 6. Note that in the third row, marker 2 must have a logical value of 0. This will be because in this case the M01 signal will have a value of 0 and the M12 signal will have a value of 1, which is inverted by the second element NO 55 to produce a value of 0 on the second input 54b of the third element OR 54.

The table of Fig. 6 contains a priority rule for the fourth order in case each of the M01 and M12 signals has a logical value of 1. This fourth order case can be generated by the BAA instruction category sequence. This could be accomplished by the tag sequence 101 as shown in Fig. 6 or, otherwise, by the tag sequence 110. In the present embodiment, rule (5) is implemented and the sequence 101 shown in Fig. 6 is selected. In other words, BA pairing is considered preferable to AA pairing.

Formula 1, 1 for M01i Μ12 signals can also be generated by the AAA operating code sequence. In this case, the tag sequence 101 of Fig. 6 is re-selected. This is better because it provides a value of 1 for tag 2 and thus potentially combines instruction 2 with instruction 3 if instruction 2 matches instruction 3.

Figure 7 is a block diagram of another parallel instruction processing system according to the invention using link tags to provide parallel computer instruction processing. The instruction linking unit 20 used in the solution of Fig. 7 can be the linking circuit 11 of Fig. 3 and then adds a one-bit marker field to each instruction. These tag fields are used to identify which instruction pairs can be processed in parallel. These tagged orders are provided and stored in the second memory circuit 12, cache type, compound orders. The output / supply control unit 60 provides orders with markers from the second memory circuit 12 as needed, and prepares them for processing by appropriate or appropriate of the many functional processing units 61, 62, 63 and 64 orders. The output / delivery control unit 60 examines the marker fields and operational code fields of the received commands. If the tag fields indicate that two successive instructions can be processed in parallel, then the output / supply unit 60 sends them to the appropriate of the functional processing units 61, 62, 63, 64, as their operating codes specify, and are they are processed in parallel by selected processing units. If the tag fields indicate that a specific order is to be processed individually, not in parallel, then the output / delivery control unit 60 transfers it to the specified processing unit, as defined by its operating code, and is itself processed or executed.

165 491

The first functional processing unit 61 is a branch instruction processing unit for processing branch type instructions. The second functional processing unit 62 is a three-input arithmetic-logic unit for generating addresses, which is used to calculate the address of the instruction memory and which sends operands to and from the operands. The third functional processing unit 63 is a universal arithmetic and logic unit that is used to perform mathematical and logical operations. The fourth functional processing unit 64 in this example is an arithmetic logical unit for eliminating data dependencies. This data dependency reduction unit 64 is an input arithmetic logic unit capable of performing two arithmetic / logic operations in a single computer cycle.

The system shown in Fig. 7 also includes a set of general purpose registers 65, used in carrying out certain computer instructions. Typically, these general purpose registers 65 are used to temporarily store data operation arguments and address operation arguments, as counters or for other data processing purposes. A typical computer uses sixteen such general-purpose registers. In the present embodiment, general purpose registers 65 are assumed to be of a multiple type in which two or more registers can be accessed simultaneously.

The system of Fig. 7 further has a fast data cache 66 for storing data operands obtained from the first memory circuit 10. Data from cache 66 may also be transferred back to the first memory circuit 10. The data cache 66 may be of a known type and its operation with respect to the first memory circuit 10 can take place in a known manner.

Figure 8 shows an example of a sequence of compound or tag orders that can be processed by the system of Figure 7. In this example, the following commands are submitted in the following sequence: loading 11, adding 12, comparing 13, conditional branching 14 and remembering 15. Tickets the markers for these orders are 1, 1.0, 1 and 0, respectively. As a result of the organization of the processing system of Fig. 7, the loading order is processed individually. Add and compare orders are processed as a complex order and processed in parallel with each other. Branching and remembering commands are also processed as a complex order and are also processed in parallel with each other.

The table in Fig. 9 provides further information regarding each of the orders in Fig. 8. The R / M column in Fig. 9 indicates the content of the first field in each instruction, which is usually used to identify the general purpose of among the m ^ 65 which contains first operand. The exception is the case of the branching instruction in which the R / M field contains a conditional code mask. Column R / X in Fig. 9 indicates the content of the second field in each order, which field is usually used to identify the second of the general-purpose registers 65. Yes and records! may contain drng and an operand, or it may contain the value (K) of the addressed index. Column B in Fig. 9 indicates the content of the third possible field in each instruction, which field may be an identifier code C from among general purpose registers 65 that contains the value of the primary address. Zero in column B means no B or no field corresponding address component in field B. Field D in Fig. 9 means the content of the next field in each command, which when used for address generation contains the value of the displacement of the address. Zero in column D may also indicate the absence of a corresponding field in a specific, prudent order, or, otherwise, an address displacement value of zero.

Let us now consider the processing of the load order in Fig. 8, in which the output / delivery control unit 60 determines from the marker bits for this load order and the next add order that the load order is to be processed individually. The action implemented by this load order is to receive the operand from memory, in this case the data cache 66, and place such operand in the general register R2. The memory address from which this operation argument is to be supplied is determined by adding to the index value in register X the basic value in register B and the displacement value D. The output / supply control unit 60 forwards this operation of generating addresses to the arithmetic-logic unit

165 491 address generation In this case, this unit 62 adds to the address index value in register X (zero value in the smaller example), the value of the primary address contained in the general use register R7 and the value of the displacement address (zero value in this example) contained in the order itself . The resulting calculated memory address that appears at the output of the address generation arithmetic logic unit 62 provided at the data cache address input 66 for access to the required operation argument. This available operation argument is loaded into general register R2 in register set 65.

Let us now consider the processing of add and compare commands in which these commands are received by the output / delivery control unit 60. This control unit 60 examines the markers for combining these two commands and determines that they can be executed in parallel. As can be seen from Fig. 9, the comparison order has a visible dependence of the data on the addition order, since the addition must be completed before comparing R3. However, this relationship can be controlled by the arithmetic logic unit 64 for eliminating data dependencies. As a result, these two orders can be processed in parallel in the system of Fig. 7.

In particular, the control unit 60 transfers the addition order processing to the universal arithmetic unit 63 and transfers the comparison order processing to the arithmetic unit 64 for eliminating data dependencies. Universal arithmetic-logic unit 63 adds the contents of the general-purpose R2 register to the contents of the general-purpose R3 register and places the result of the addition back from the general-purpose R3 register. At the same time, the arithmetic-logic unit 64 for eliminating data dependencies performs the following mathematical operation: R3 + R2 - R4. The conditional code for the result of this operation is sent to the conditional code register located in the processing unit of the 61 branch orders. The data dependency is reduced because the arithmetic logical unit 64 of the data dependency elimination as a result calculates the sum of R3 + R2 and then compares this sum with R4 to determine the conditional code. In this way, this unit 64 does not have to wait for the results of the universal arithmetic technology unit 63 which carries out the addition order. In this particular case, the numerical results calculated by the arithmetic-logical unit 64 of dependency elimination and appearing at its output are not returned back to the general-purpose registers 65. In this case, this unit 64 only sets the conditional code.

Let us now consider the processing of the branching order and the remembering order, shown in Fig. 8, in which these orders are received from the cache of 12 complex orders by the output / delivery suction unit 60. The control unit 60 determines based on the marker bits of these instructions that they can be processed in parallel with each other. It then determines, based on the operational codes of the two orders, that the branch order should be processed by the processing unit 61 branch orders and the remembering order should be processed by the arithmetic logical unit 62 of address creation. delivered to the processing unit 61 branching orders. Similarly, the value of the address in register X and the value of the primary address in register B for this branch instruction are obtained from general purpose registers 65 and provided to the processing unit 61 of branch orders. In this example, the X value is zero and the basic value is obtained from the general-purpose register R7. The displacement D value has a hexadecimal value of twenty while the masking M field has a mask position value of eight.

The branch instruction processing unit 61 begins to calculate the potential branch address (0 + R7 + 20) and simultaneously compares the conditional code obtained from the previous compare order with the field M for masking the compare code. If the conditional code value is the same as the masking code value, the necessary branch condition is met and the branch address calculated by the branch instruction processing unit 61 is then loaded into the instruction counter in control unit 60. This instruction counter controls the receipt of orders from the cache of 12 complex orders .

165 491

If, on the other hand, the condition is not met (the known conditional determined by previous orders is not eight), then no branching is carried out and no branching address is supplied to the instruction counter in control unit 60.

At the same time that the branch instruction processing unit 61 is busy performing branching instruction processing, the address generation arithmetic logic unit 62 is busy performing the address calculation (0 + R7 + 0) for the remembering instructions. The address calculated by this unit 62 is provided to the data cache 66. If no branching is carried out by the processing branch 61 of the branching instructions, then the store instruction runs towards remembering the operand of the operation in general register R3 within the data cache 66 at the address calculated by the arithmetic logic unit of 62 addresses. If, on the other hand, the branching condition is met and the branching is carried out, then the contents of the general register R3 are not stored in the data cache 66.

The above sequence of instructions in Fig. 8 is given only as an example. The exemplary processing system of Fig. 7 is also capable of processing various other instruction sequences. The example of Fig. 8 clearly shows, however, the utility of compound instruction markers in determining which instruction pairs can be processed in parallel.

<td>TAG 0</td><td>INSTR. 0</td><td>TAG 1</td><td>INSTR. 1</td><td>TAG 2</td><td>INSTR.2</td><td>TAG 3</td><td>INSTR.3</td>

FIG. 2

<td>MY</td><td>M12</td><td> 0</td><td>t</td><td> 2</td>

<td> 0</td><td> 0</td><td> 1</td><td> 1</td><td> 1</td>

<td> 1</td><td> 0</td><td> 1</td><td> 0</td><td> 1</td>

<td> 0</td><td> 1</td><td> 1</td><td> 1</td><td> 0</td>

<td> 1</td><td> 1</td><td> 1</td><td> 0</td><td> 1</td>

FIG. 6

165 491

Circumference of orders

Γ 'from block 10

- 21a

Jnstr. 1 Jnstr 2 Jnstr 3 Jnstr 4 Jnstr 5 Jnstr 6 Jnstr7 Jnstr 8

21b22a22

Lć24

<td></td><td>--M34 M45 ---!</td><td>k-M56 | M67 --- 1</td><td></td>

-M78

<td colspan="9"></td>

<td>-TAG 0 Jnstr. 0 A7O1₍</td><td>-TAG 1 Jnstr 1 27bX,</td><td>-TAG 2 Jnstr. 2 27CI</td><td>-TAG 3 Jnstr. 3 L</td><td>-TAG 4 Jnstr. 4 ł '</td><td>-TAG 5 Jnstr 5 ł '</td><td>-TAG 6 Jnstr 6 L</td><td>-TAG 7 Jnstr. 7 , Ł</td><td>-TAG 8 Jnstr. 8 L</td>

<td colspan="6">TO | JnstrO | T1 | Jnstr 1 | T2 | Jnstr.2 | T3 | Jnstr. 3 | T4 | Jnstr4 | T5 | Jnstr.5</td><td>'6 Jnp.6</td><td>"7 | Jnstr. 7</td><td>B Jnstr. 8</td>

2727d to block 12

FIG. 3

165 491

<img file="PL165491B1_D0001.tif" />

TAG ABOUT TAG1 TAG 2

<img file="PL165491B1_D0002.tif" />

165 491

INSTRUCTIONS —-1 FIG. 7 ~ ^ 20

-,- DATA

<img file="PL165491B1_D0003.tif" />

CONDITIONAL CODE

LOAD 1 ADD ABOUT | COMPARE 1 | fiD35AŁĘZ ABOUT [REMEMBER

INSTRUCTIONS INSTRUCTIONS

COMPLEX COMPLEX

8 discloses

<td>NO</td><td>CODE OP</td><td>R / W</td><td>R / X</td><td> 8</td><td>D</td><td>ACTION</td>

<td> 11</td><td>LOAD</td><td>R2</td><td> 0</td><td>R7</td><td> 0</td><td>REMEMBER —— R2 (MEMORY AORES® 0 + R7 «· 0)</td>

<td>I2</td><td>ADD</td><td>R3</td><td>R2</td><td> 0</td><td> 0</td><td>R3 + R2—— R3</td>

<td>I3</td><td>COMPARE</td><td>R3</td><td>R4</td><td> 0</td><td> 0</td><td>R3 (c) R4 —- CONDITIONAL CODE</td>

<td>I4</td><td>ROZGAŁĘŹ CONDITIONALLY</td><td> 8</td><td> 0</td><td>R7</td><td> 20</td><td>ADDRESS (OR7 + 20) FOR COUNTER INSTRUCTIONS IF FULFILLED WAR (CC-8)</td>

<td>I5</td><td>REMEMBER</td><td>R3</td><td> 0</td><td>R7</td><td> 0</td><td>R3 —— REMEMBER (ADR. = 0 + R7 * 0, (IF THE CONDITION IS NOT FULFILLED)</td>

FIG.9

165 491

<img file="PL165491B1_D0004.tif" />

FIG. 1

Department of Publications of the Republic of Poland. Edition of 90 copies. Price: 1 (PLN 00)