System for preparing commands for a parallel command processor and system provided with a mechanism enabling to execute a jump command in the middle of composite reference command for associated request

The subject of the invention is a computer system for processing orders, especially designed for the parallel execution of two or more orders and for performing jumps inside a compound order.

Traditional computers that download and execute sequences of subsequent commands are referred to as "scalar" computers. A new one is being developed with each new generation of computers

166 513 mechanism accelerating the work of traditional scalar computers. A new mechanism for increasing the speed of calculations was used in the computer architecture with a reduced set of orders (RISC), which uses a limited set of very simple instructions executing at a high speed. Another mechanism to accelerate operations may be to use more complex commands to perform more computational functions per command and thereby reduce the number of instructions in the program. Applying any of the above methods to increase the speed of calculations to existing scalar computers would require a significant change in their architecture and set of orders. Such far-reaching changes are burdened with costs, increased downtime and, in the initial period, reduced reliability and readiness of computers to work.

Recently, superscalar computers have been developed that have further increased computing speed. These computers are basically scalar computers in which the increased computing power was obtained by their adaptation to perform simultaneously more than one instruction taken from the sequence stream of subsequent individual scalar instructions. In these computers, the decision as to whether two or more orders can be executed in parallel is made when the instructions are executed. This decision is based on the order operation code (OP codes) and on the relationships between data that can bind orders. The OP code specifies the hardware requirements required to carry out the order. In general, it is not possible to execute two or more commands in parallel using the same hardware (hardware dependency) or the same arguments (dependency on shared data). Both types of dependencies prevent parallel execution of some command combinations. In these cases, certain orders are executed sequentially. This, of course, reduces the computing power of superscalar computers.

Superscalar computers have disadvantages that they attempt to minimize. To resolve orders that can be executed in parallel during the execution of orders, a specific time is required. This time can be reduced by applying it to other machine operations. This defect increases with the complexity of the instruction set architecture. Decisions on the parallel execution of orders must be repeated each time the same orders are executed.

Acceleration of operations using a reduced instruction set architecture (RISC), architecture with a set of compound instructions or traditional superscalar techniques is potentially too expensive or burdened with too many disadvantages to be used for existing scalar computers. Therefore, it would be beneficial to increase the computing power of these computers by concurrent or concurrent execution of orders without changing the existing set of instructions, without changing the machine architecture or extending the time of executing orders.

A number of these and other problems have been presented in the patent literature. U.S. Patent 5,197,135 describes memory management for a processor with a set of scalable compound orders with internal memory for storing instructions. On the other hand, in another U.S. Patent No. 5,301,131, an overflow determination in three-arithmetic logical units for a processor with a set of scalable compound orders is described, while in U.S. Patent No. 5,295,249, a preprocessor for caching instructions is described. .

The essence of the instruction processing computer system according to the invention, comprising a main memory to which an I / O adapter is attached, an instruction cache memory attached to the main memory, and an instruction retrieval and sending unit attached to the instruction cache memory, the instruction retrieval and sending unit being attached to the functional units through the decoder is that it contains an instruction set, whose input is attached to the I / O adapter output and the output is attached to the main memory input. In another embodiment of the computer system of the invention, the system is further expanded with a cache control unit whose input is connected to the output of the command retrieval and sending unit, and the output is connected to the command cache input, wherein the cache control unit is output preferably a memory management unit whose output is connected to the main memory input.

166 513

In turn, the essence of the instruction processing computer system, according to a variant of the invention, comprising the main memory to which the I / O adapter is attached, the instruction cache memory attached to the main memory, and the instruction download and send unit attached to the instruction cache memory, the sending orders is attached through the decoder to the functional units, is that it contains an order submission team, whose input is attached to the main memory output and the output is attached to the command cache input. In another embodiment of a variation of the computer system of the invention, the system is further expanded with a cache control unit whose input is connected to the output of the command retrieval and sending unit and the output is connected to the command cache input, wherein the cache control unit is output preferably a memory management unit whose output is connected to the main memory input.

The computer system according to the invention provides decoding of order submission options based on a scalar machine base instruction string, generates compound instruction strings, enables the collection and decoding of compound and individual orders, provides a program operating on compound orders, maintaining the sequentiality of executing scalar machine base instructions when executing compound orders. The system also makes it possible to perform jumps inside compound orders. Therefore, in order to perform jumps of compound orders, it is checked whether they contain the attached control bits. An invalidation mechanism is also introduced, depending on the control bits, enabling the cancellation of the execution of subcommands that occur in jump commands, or in subsequent compound orders, provided that their execution would cause incorrect program behavior.

The subject of the invention is shown in the embodiment in the drawing, in which Fig. 1 shows a general block diagram of a part of a computer system capable of placing orders in scalar order sequences for concurrent execution, Fig. 2 - a time chart for single-processor implementation, showing the parallelism of certain orders , selectively grouped into sequences of compound orders, Fig. 3 - block diagram of the computer system according to the invention, Fig. 4A - a general block diagram illustrating the method of processing existing programs to determine the sequence of orders that can be executed as individual orders placed in a computer to perform compound orders, Fig. 4B - a fragment of the recommended implementation of the computer system in accordance with the subject of the invention, Fig. 5 the path of the program to transform the original code to execute the program, fig. 6 - block diagram showing the program generation from orders placed on the basis of the program stored in the assembler, Fig. 7 - block diagram of the system for executing compound orders, Fig. 8 and Fig. 9 respectively show the scheme of the system for executing compound orders and the scheme of program generation from orders given for the case in which the order to which the jump is made is at the beginning or in the middle of the order, and fig. 10 presents notation of tag formats.

Figure 1 shows a typical embodiment of a portion of a computer system for digital data processing. This system is capable of executing two or more commands in parallel. To enable concurrent execution of a group of two or more orders, the computer system includes a set of functional units that can work in parallel in a concurrent manner, each of which can process one or more types of machine orders. The system allows you to place orders for their parallel or concurrent execution. In this sense, "submission refers to the grouping of orders from a scalar instruction sequence, where the group size is scalable from 1 to N. The scalar instruction sequences can, for example, be taken from an existing set of scalar instructions, such as those used in the IBM System / 370 system. It is understood, however, that submission is intended to facilitate the simultaneous retrieval and execution of orders on all computer systems with an architecture that enables the processing of multiple orders per cycle.

When ordering, adjacent scalar orders are grouped for parallel or concurrent execution. In particular, the instruction assembly looks for instruction classes that can be executed in parallel. After finding the appropriate order sequences, a compound order is created.

166 513

As shown in Fig. 1, the instruction set 20 fetches a stream of binary scalar instructions 21 and selectively groups some of the adjacent scalar instructions to form a nested compound order. The resulting stream of compound orders 22 contains scalar commands for single execution and compound orders formed of scalar orders for parallel execution. After the scalar command is given to the 24 instruction processing unit, it is directed to one of many suitable execution units for sequential execution. After giving the order submitted to the 24 instruction processing unit, its component scalar orders are given to the appropriate execution unit for parallel execution. Typical functional units are, for example but not limited to, arithmetic logic units (ALU) 26.28, floating point arithmetic units (FP) 30 and address generation units (AU) 32.

As shown in Figure 2, command submission can be implemented in a single processor environment in which each functional unit executes a scalar (S) order or, alternatively, a compound instruction (CS). As shown in the figure, the instruction stream 33 containing the sequence of scalar instructions and compound scalar instructions has control bits or markers (T) associated with each of the compound instructions. Thus, the first scalar instruction 34 can be executed individually by functional unit A in cycle 1; the triple folded command 36 identified by the T3 tag can have its three complex scalar commands executed in parallel in functional units A, C and D in cycle 2; the next compound instruction 38 identified by the T2 tag may have its two scalar compound commands executed in parallel in functional units A and B in cycle 3; the next scalar instruction 40 can be executed individually by functional unit C in cycle 4; a large group of compound orders 42 may have its four folded scalar commands executed in parallel in functional units A, B, C, D in cycle 5; and the third scalar instruction 44 can be executed individually by functional unit A in cycle 6.

One example of a computer system architecture that can be adapted to operations on compound orders is an architecture at the level of machine orders of the IBM System / 370 system in which multiple scalar orders can be sent for execution in each machine cycle according to Fig. 2. In this context, the machine cycle refers to the single stage of pipeline processing required to execute the scalar instruction.

It is beneficial that the order placement process takes place before they are downloaded, so that they can be executed once for an order or orders carried out repeatedly. It was proposed to place the order submission unit in the computer's real memory for hardware submission, after compilation, but before sending the order for execution. This type of folding is considered to be preferred over other solutions and referred to as "intra-memory folding *.

In-memory folding is shown in figure 3 with respect to the computer system of the invention. The hierarchically organized memory includes an I / O adapter 1 that has interfaces with auxiliary memory and real computer memory. Real memory consists of main memory 46 with high capacity and medium speed as well as main memory 46 with high capacity and medium speed and cache memory of 48 commands, fast but with relatively low capacity. Main memory 46 and cache 48 are referred to herein as real memory or simply memory. The stream of commands downloaded from the cache 48 using the I / O adapter 41 is stored in blocks called "pages: in main memory 46. Uninterrupted command strings, called" lines **, are sent from main memory 46 to the 48 commands cache, where are available for quick transmission for processing in the unit for downloading and sending 50 orders. Orders downloaded from cache 48 are fed to decoder 52, where they are decoded and forwarded to functional units 56, 58, ..., 60 for execution.

At run time, if there is a reference to an instruction in the program, the instruction address is given to the cache control unit 62, which uses it to retrieve one or more commands, including the addressed command, from the cache 48 to the queue at the download and send unit 50 orders. If the addressed order is in

166 513 cache 48, there is talk of "hit - otherwise -" miss. Missing causes the cache control unit 62 to send the requested command line address to the memory management unit 64. This assembly includes management functions that include, for example, real memory management functions that use the row address provided by the cache control unit 62 to determine if the page containing the addressed row is in main memory 46. If the page is in main memory 46, then the real memory management assembly 64 will use the row address to send the row containing the missing command from main memory 46 to cache 48. If the line containing the requested order is not in main memory 46, the operating system activates the next memory management function, providing it with the identifier of the page containing the line needed. This function will send an address to the I / O adapter 41 specifying the page containing the line. The adapter 41 retrieves the page from cache 48 and delivers it to main memory 46. To find a place for a downloaded page, the memory management unit 64 selects a page in main memory 46 to be replaced by the downloaded page. In a system architecture with a set of scalable compound orders (SCISM), the replaced page is returned to the cache 48 by the input / output adapter 41 without the information contained in the compound instruction markers. In this way, the commands that will most likely be required during the execution of the instruction sequence are adjacent to the functional units 50, 58, 60 in the cache 48. The hierarchical organization of memory allows quick access to commands that are required but are not in the cache 48 .

In the SCISM architecture, in-memory order submission can be performed using a 70-command order assembly functionally located between the I / O adapter 41 and the main memory 46 so that the scalar instruction stream can be assembled at the input to or inside the main memory 46. With this location orders can be submitted while downloading pages.

Alternatively, the instruction assembly 70 may occupy the space indicated in figure 732 between main memory 46 and the instruction 48 cache, and compound instructions are created line by line during download to cache 48, which may be the preferred embodiment.

The specific technique for submitting orders is the choice of the designer. However, for illustrative purposes, one of the techniques for creating orders made from adjacent scalar instructions may be presented. For example, the order may take 6 bytes (3 half words), 4 bytes (2 half words) or 2 bytes (1 half words) of text. In this example, the rule specifying the rules for submitting variable-length orders states that all 2 or 4 byte orders are placed together. Thus, a 2-byte instruction can be executed in parallel with another 2 or 4-byte instruction as well as a 4-byte instruction can be executed in parallel with another 2 or 4-byte instruction. The rule states that 6 byte orders are not submitted. Thus, a 6 byte instruction can only be executed one at a time. Of course, the submission process is not limited only to these sample rules but can be governed by a series of rules that define criteria for the parallel execution of orders in a specific configuration for a given computer architecture.

The instruction set in this example is taken from the System / 370 architecture. Based on the examination of the operation code of each OP instruction, its length can be determined by the instruction length code (ILC) contained in the operation code. Other bits of the operation code specify the type of instruction. After specifying the type and length of the order, a folding marker is generated to determine whether the order should be submitted with the next or subsequent orders for parallel execution, or whether it should be executed one at a time.

In this example, the tag format is chosen so that when two adjacent orders can be combined, the tag bits for the first instruction are "1 and" 0 for the second. However, if the first and second orders cannot be submitted, the marker for the first order is "0", and the second and third orders are considered for submission. After processing the instruction byte stream according to the selected submission rules and specifying the bits for submission for different scalar orders, you can achieve an increase in the degree of parallelism in order execution by examining larger groups of instructions and then selecting the best combination of N instructions to submit.

166 513

There is a need to have a system which is generally described in figure 4-A. Both programs written in a higher-order language (Figure 5) and programs written in assembler (Figure 6) must be processed to determine the sequence of instructions that can be executed as individual compound orders on a computer capable of performing compound orders.

Fig. 4-A shows the sequence to which the program is subjected, given at the input of the command order assembly, which produces a program consisting of instructions based on rules that reflect the achitecture of the system and equipment. These rules are referred to as folding rules. The program created by the instruction assembly can then be directly executed in the system for executing compound orders, as shown in figure 7.

Figure 5 shows a typical program path from the source code in a higher order language to the actual implementation, which may be considered one of the possible implementations suggested by Figs. 4-A. An alternative solution for programs written in assembler is shown on the basis of Fig. 6.

It can be seen from Fig. 5 that there are many places in the computer system, both in software and hardware, where orders can be made. Each of them has its pros and cons. As shown in Fig. 5, the program goes through several stages from the source program to final execution. At compilation, the source program is translated into machine code and stored in disk storage 45. During the execution phase, the program is read from the disk memory 45 and loaded into the main memory 47, located in a specific configuration of the system 49, where the orders are executed using the processing units 53, 54, 55 of the instructions. Orders can be made anywhere along the route shown. Generally, the closer the instruction processing unit (IPU) is to the instruction assembly, the sharper the time constraints become. If the order submission team is further away from the IPUs, more orders may be considered to determine their best grouping for submission and thus increase the speed of operation.

Figure 6 is a block diagram of program generation with orders submitted based on a program stored in assembler according to specific assembly rules 57, taking into account the architecture of the system and equipment. The assembler program is fed to the assembly assembly 59, viewing the assembler program in blocks consisting of mi-, m2 ... m_ncommands and the output generating program with compound orders. The submission team 59 analyzes subsequent instruction blocks. The blocks are numbered from 1 to n. The component commands of block n are designated I, m where m changes to 1 to the number corresponding to the number of instructions in the block. The number of instructions in each of the blocks 61, 63, 65 in the instruction stream containing the group of instructions taken into account when placing orders depends on the implementation of the assembly 59 and may be different in each block.

As shown in Fig. 6, the assembly assembly 59 performs m orders in pairs. In the first step, the first and second orders are considered, whether they can be combined into a folded order. Then the second and third, third and fourth orders are examined in the same way until the end of the block. After identifying the different possible C1-C5 pairs, the assembly assembly 59 selects the preferred compound orders and identifies optimally grouped compound orders with identifying bits or markers.

If optimal grouping is not possible, all of the foldable, adjacent scalar orders can be identified so that a jump to any of the orders placed inside any of the compound orders can use any of the pairs of compound orders encountered. In the event that there are multiple folding assemblies 59, multiple successive blocks can be assembled from the instruction stream.

Figure 7 is a block diagram of a system for executing a program containing compound orders, generated by hardware order assembly 66 or software assembly means 67. A stream of bytes containing compound instructions is fed into the cache memory (CI) 68, which acts as a memory buffer ensuring fast

166 513 access to orders placed. The 69 orders download and sending team retrieves orders placed from the cache 68 and transmits individual component orders to the appropriate functional units for parallel execution.

It should be emphasized that functional units (EU) 71, such as arithmetic technology units (ALU), in a computer operating on compound orders may perform individual scalar distributions or scalar orders placed in parallel with other scalar compound orders. The parallel execution process can take place in different types of execution units, such as the mentioned ALU units, floating point units (FP) 73, memory address generation units (AU), or in execution units of the same type, depending on the architecture and specific configuration of the computer.

The first tag format shown in the example above contains one bit, added to every two bytes of text (instructions and data). In general, information tags can be added to each of the orders in the byte stream - that is, both each of the non-folded and compound scalar orders, occurring in a pair, a trio or a larger group can be tagged. In the description, identification bits are understood to mean the portion of the tag that is specifically used to identify and distinguish between these scalar compound orders that form groups of compound orders, from other non-scalar scalar instructions in the program that are downloaded and executed individually.

In the event that more than two scalar orders can be combined into a compound order, it may be beneficial to add additional identification bits. The minimum number of bits required to indicate a specific number of scalar orders that have undergone the submission process is determined by the binary logarithm (at base 2), rounded up to the nearest integer, from the maximum number of scalar commands that can be combined into a group, forming one compound order. For example, if the maximum is 2, one identification bit is enough for each order. If the maximum is 3 or 4, two identification bits are required. If the maximum is 5, 6, 7 or 8, three identification bits are required for each order placed.

A second tag format using the coding scheme mentioned is shown in Table 1.

Table 1

<td>beaten identification</td><td>encoded importance</td><td>number commands folding</td>

<td> 00</td><td>this order is not sent to the next one</td><td> 0</td>

<td> 01</td><td>this order is submitted with the next one</td><td> 2</td>

<td> 10</td><td>this order is made with two more</td><td> 3</td>

<td> 11</td><td>this order is made with the next three</td><td> 4</td>

Assuming that the orders are aligned in such a way that each halfword requires a tag, note that the instruction processing unit (IPU) ignores all except the tag for the first order when retrieving the orders. Otherwise, the halfwords are checked by examining the information bits to determine if they are starting a compound order. According to Table 1, for the compound order, which is not the first in order, the identifying bits are equal to 0. If the halfword designates a compound instruction containing two scalar instructions, the identification bits for the first instruction are _p 1 "and" 0 "for the second order. If the halfword designates a compound order containing three scalar orders, the identification bits for the first order are "2", for the second order "1" and "0" for the third order. In other words, the identification bits for each halfword determine whether this specific halfword is the beginning of a compound order, while indicating the number of orders that make up the compound order.

The coding of compound orders described above implies that if three orders are placed in a triple group, the second and third orders are also placed in a double group. Otherwise, if there is a jump to the second order in the triple group, the identification bit for the second order equal to "1" means that the second and third orders will be executed in parallel as a folding pair, although the first order in the triple group was not executed.

166 513

In the present invention, the instruction stream is subjected to the instruction ordering operation only once for a specific configuration of the computer system, and the collection of the compound instruction occurs together with the download of identification bits for that instruction. This eliminates the need for inefficient determination and last-minute selection of certain scalar commands for parallel execution, which occurs when retrieving the same or different commands for execution in a superscalar machine.

Creating instructions from the stream of input commands at known reference points that indicate the start of an order is a simple operation. The reference point is information which of the bytes that may contain the order or data is the first byte of the order. This type of information can be obtained using a marker field or other indicator that provides information about the location of the boundaries between orders. In many computer systems, this type of reference point is known only to the compiler during compilation and to the computer central processing unit (CPU) during instruction collection. If the instruction operation is performed after compilation, the compiler could indicate with the help of pointers which bytes contain the first byte of the instruction and which contain the data. This additional information enables the folding assembly to be implemented more efficiently because the exact locations of the orders are known. Of course, the compiler can differentiate between orders and data by providing information to the assembly team to identify boundaries between orders.

In a system where 4-byte orders are aligned with an accuracy of four bytes, each tag is associated with 4 bytes of text. If the orders can be aligned any one marker is needed for each byte. However, for a certain type of computer architecture, variable length commands are possible, with additional mixed instructions and data, which complicates the ordering process. Of course, the boundaries between commands must be known at the time of program execution. However, since the submission process is best done before executing orders, you need a method for placing orders without knowing where the sequence of orders begins and without knowing which bytes are the data. This method should apply to all acceptable types of computer architecture, including computer architecture with a reduced instruction set (RISC), in which instructions are usually of a fixed length and not mixed with data. The implementation of this type of function, which is generally shown in Figs. 4-A, is obtained with the help of an assembly of instructions for compound orders.

A preferred embodiment of the computer system according to the invention is shown in figure 4-B. Although the submission process can be implemented programmatically, the recommended implementation of the submission process is to use the order submission team. Figs. 4-B show a typical portion of a computer system or digital data processing system including the cache management unit 144. The system can execute two or more commands in parallel. It has the first mechanism for remembering orders and data to be processed in the form of a series of base instructions for a scalar computer. This mechanism is referred to as high-level memory. This is 136 main storage with high capacity and low speed. It can also be a high-capacity system memory unit, or it can be the bottom level of a hierarchical memory system.

The computer system of Figs. 4-B also includes an instruction set 137 or mechanism for receiving instructions from the main memory 136 and for associating with them markers which determine which of these instructions can be processed in parallel with others. The 137 orders assembly analyzes the commands taken to determine which of them can be processed in parallel. In addition, this team provides the analyzed orders with markers that determine which of them can be executed in parallel and which individually.

The computer system of Figs. 4-B also includes a second memory mechanism coupled to the instruction assembly 137 for retrieving and storing analyzed instructions and associated markers, so that these stored compound orders can be retrieved for execution. This second or subsequent memory mechanism is represented by a cache of 138 compound orders. Cache 138 is a fast, low-capacity memory that is used by analogy to cache in computer systems to increase their processing power by reducing the frequency of references to free main memory 136.

166 513

Figure 4-B also shows a number of functional processing units 139, 140,141. Functional units 139, 140, 141 operate in parallel in a concurrent manner, each of which is capable of processing one or more types of machine orders on its own. Examples of functional units that can be used are: general purpose arithmetic logic unit (ALU), ALU unit for address generation, ALU unit based on data dependencies, jump order processing unit, data shifting unit, floating point processing unit, etc. Your computer system may contain two or more functional units. For example, a given computer system may contain two or more general purpose arithmetic logic units (ALUs). Similarly, computer systems do not have to include each of the types of functional units listed. Their configuration depends on the chosen computer system architecture.

The computer system of Figs. 4-B also includes a mechanism for collecting and sending orders, coupled to a cache of 138 compound orders, used to pass subsequent instructions from this memory to various functional units 139, 140, 141, when the order markers indicate that they can they must be performed in parallel. This mechanism also gives individual commands to individual functional units 139, 140, 141, when markers indicate that they cannot be executed in parallel and must be processed individually. This mechanism is implemented by the unit receiving and sending 142 orders. This unit retrieves instructions from the cache 138 and analyzes the marker bits as well as the field of command operational codes, performs decoding functions and, based on this analysis as well as other signals controlling the pipelining, sends the analyzed order to one of the appropriate functional units 138, 140, 141. The submission of instructions within the cache 138 is accomplished by the instruction assembly 137 so that the submission of each row of the cache 138 takes place at its input. During the download of each row from main memory 136 to cache 138, it is analyzed for submission to the assembly of 137 orders and passed, together with marker information bits, to be stored in the cache 138 of compound orders.

Before the 138 cache is stored, the poem must be assembled in the assembly assembly

137 commands that generate a set of marker bits. Marker bits can be attached directly to the instructions they concern. They can also be delivered in parallel with the orders themselves. In any case, these bits are stored with their corresponding instruction lines in the cache 138. If necessary, the instruction is cached

138 it is downloaded along with the marker bits by the unit for downloading and sending 142 instructions. This unit and the compound instruction cache 138 are designed in such a way that the maximum order length can be retrieved from the compound instruction cache 138 and sent to functional units 139, 140, 141, etc. When the commands are downloaded to the download and sending unit 142, their marker bits are checked to determine by decoding whether they can be executed in parallel, and the operational codes are examined to determine which of the available functional units 139, 140, 141 will be the most appropriate to process them . If the tag bits indicate that two or more commands can be processed in parallel, they are sent to the respective functional units 139, 140, 141 based on their operational codes. They are then processed concurrently in these functional units. When it encounters an order that cannot be executed in parallel, it is sent to the appropriate functional unit 139, 140, 141 based on its operating code, where it is then processed individually.

In the ideal case, if a series of orders is always processed in parallel, the computer system would execute orders faster by N times faster than if the orders were executed individually, where N is the number of orders processed in parallel in the group.

As previously shown, the control field or tag contains information delimiting the boundaries of compound orders, but may also contain additional information if required by the specific implementation. For example, for the third form of the tag format, the control field (tag) can be defined as an 8-bit field.

t0 t1 t2 t3 t4 te te t7

166 513 in which the following bits are defined as follows:

Bit The function is if equal to 1, the order of the compound t1, and the order equal to 1, will execute, two, Irł ^ d ^ and ^ e parallelee t2 if equal to 1, the folded order has more than one execution cycle t3 eh equal to 1, therefore the post-processing operation t4 if the order is a jump order, then if this bit is equal to 1, it is anticipated that this order will be executed ts if equal to 1, then this order has a memory connection with the previous order submitted also 1, request for dynamic order for execution 17 IcśH equal 1, oo order e ^ n use ALU unit

In general, the folding assembly 137 picks up commands that can be executed in parallel and ensures that there are no associations between the compound instructions of the compound order that cannot be handled in hardware. After finding compatible instruction sequences, a compound order is created. For example, orders for System / 370 can be divided into the following classes:

1. foomat RR - -oozazz charging, logical a ο ^ η ^ γ ^ η! pooównmia

LOR - load restoration

LPR - load positive value

LNR - load negative value

LR - load registry

LTR - load and test

NR - logical product

OR - logical sum

XR - sum modulo two

AR - add

SR - subtract

ALR - add logically

SLR - go logically

CLR - compare logically

CR - compare

2. RS format - shift orders (without memory access)

SRL - move right logically

SLL - move left logically

SRA - move right arithmetically

SLA - move left arithmetically

SRDL - move right logically

SLDL - move left logically

SRDA - move right arithmetically

SLDA - move left arithmetically

3. Conditional jump orders - dependent on counter and index value

BCT, perform, stroke depending on the counter (RX format)

BCTR, make the jump depending on the counter (RR format)

BXH - jump if index high (RS format)

BXLE - jump if index value is low (RS format)

4. Conditional jump orders - dependent on the condition being met

BC, ^ make a jump if the bathtub is finished (RX format)

BCR, jump if condition met (RR format)

166 513

5. Jump and joining orders

<td>BALL</td><td>- jump and connect (RX format)</td>

<td>Balraj</td><td>- jump and connect (RR format)</td>

<td>BASS</td><td>- jump and remember (RX format)</td>

<td>Basra</td><td>- jump and remember (RR format)</td>

<td colspan="2">6. Orders to save to memory</td>

<td>STCM</td><td>- remember characters with mask, remember 0-4 battes, RS format)</td>

<td>MVI</td><td>- download directly (t bjtt, SI format)</td>

<td>ST</td><td>- remember ^ (4 years)</td>

<td>STC</td><td>- remember ^ ta- (tl ^^ t))</td>

<td>STH</td><td>- remember ^ semi-wise (2 bjtty)</td>

<td> 7.</td><td>Charging orders</td>

<td>LH</td><td>- aadu- again 0 όϋ ^ γ)</td>

<td>L</td><td>- aadj- (- hj ^ y)</td>

<td> 8.</td><td>Launch the address</td>

<td>AND ⁹.</td><td>Foęma ^ fX - arithmetic, logic, insertion and comparison commands</td>

<td>AH</td><td>- &lt;Jo &lt;d ^ - J ^ «Words</td>

<td>N</td><td>- foggy action</td>

<td>ABOUT</td><td>- the sum of fog ^ na</td>

<td>S</td><td>- and ^ &lt;l ^ jjan</td>

<td>SH</td><td>- and ^ &lt;r ^ rⁿiit for friday</td>

<td>SL</td><td>- from ^ nu- ^ ίεζηίε</td>

<td>X</td><td>- sum of modufo two</td>

<td>IC</td><td>- enter ^ i ^ k</td>

<td>ICM</td><td>- insert a character with a mask φοόΐβΓΖ 0-4 patches))</td>

<td>C</td><td>- compare</td>

<td>CH</td><td>- compare the halfword</td>

<td>CL</td><td>- compare fogiczme</td>

<td>CLI</td><td>- compare ^ ΐεζηΐε directly</td>

<td>CLM</td><td>- compare log ^ with ^ e character with mask</td>

10. TM - test with a mask

Other System / 370 orders are not taken into account when submitting orders to be carried out in the present invention. This does not exclude the possibility of performing assembly operations on them in future solutions of computers with compound orders.

One of the most common program sequences is to execute TM or RX format comparison class instructions, the result of which controls the execution of a "jump if condition fulfilled" command that immediately follows the comparison class command. The speed of operation can be increased by executing "compare and" jump commands in parallel, which is sometimes implemented dynamically in powerful command processors. A certain difficulty lies in the identification of individual orders from the "compare and" jump class, performed for typical architecture during the decoding process. This problem is avoided in the present invention in which order analysis of individual classes is performed in advance. As a result, a compound order is created that can be executed.

Depending on the hardware solutions, many instruction classes can be executed in parallel. In addition to the fold orders that have already been presented in the "compare and" jump classes, compound orders of other classes can also be analyzed, for example loading and RR format commands, jump and address loading commands, etc. A folded order can contain even many orders from the same class, for example arithmetic format RR, as long as the processor has the necessary number of execution units at its disposal.

166 513

In each practical implementation of the instruction processor, there is an upper limit on the number of instructions included in the compound order. This limitation must be known to the team performing the order placement operations so that the resulting folding orders are not longer than the above limitation, caused by the hardware solution used. Note that m is exactly a consequence of hardware solutions. It does not limit the scope of orders that can be analyzed by software to check if they can be submitted. In general, the wider the scope of the analysis, the greater the degree of parallelism that can be achieved, as the ordering team can then detect the more promising ordering options. For illustration, consider the following example:

XI

X2

LOAD Rl, (X) ADD R3, R1 SUB Rl, R2 COMP R1, R3 X3 X4 on which the folding operation can be performed •, κού ^ ειζ, on which the folding operation can be performed; load X memories to R1; R3 = R + R1 ; R1 = R1-R2 compare R1 with R3 on which you can ^ ^ and ^^^ j ^ fold on which you can perform the operation slkł ^ t ^^ and ^^ a

If the upper limit m caused by the hardware solution is 2, then there are several ways to perform the submission operation on the above sequence of instructions depending on the scope of the analysis performed by the instruction assembly. For an analysis scope of 4, the assembly team would generate the following pairs &lt;X1&gt;, &lt;X2 LOAD&gt; &lt;ADD SUB&gt; &lt;COMPP X3&gt; &lt;X4&gt;, completely removing the hazard between LOAD, ADD, SUB and COMP. On the other hand, a superscalar machine with p = 2, putting orders into pairs in a command sending team using the FIFO principle (first on input - first on output), would generate the following pairs &lt;X1 X2&gt; &lt;LOAD ADD&gt; &lt;SUB COMP&gt; &lt;x3 X4&gt;, charged with interconnected orders. LOAD and ADD commands cannot, unfortunately, be executed in parallel, because ADD requires the result of the load operation. Similarly, SUB and COMP cannot be performed in parallel. Therefore, it is not possible to accelerate the operation in this way.

The described system presents the ways of generating a program consisting of compound orders and additionally proposes to associate markers with orders in a relatively constant way. Since there is no guarantee that there will be no jump in the middle of the submitted order, it has not yet been explained how to provide information about the submission and, more importantly, how to ensure the correctness of program execution in the event of jumps to any position. This problem is, in fact, solved by the order picking and sending unit 142 for execution in Figs. 4-B, which will be explained further below. To begin with, let us assume the fourth type of definition of the T folding tag, such that T = 1 if the associated instruction either starts the folding order or is the order to perform a single. In addition, T = 0 for the storage order (different from the first one) included in the folding order. Assuming then that the unit for collecting and sending 142 orders to be executed can download a maximum length folding order (as specified above), when downloading an order in response to a completed jump, it always downloads a block of text equal to the maximum length of the folded order, starting exactly under destination address of the jump order and then executes all orders retrieved from T = 0 as compound orders, up to the place in the downloaded text where the order with T = 1 appears, indicating the next order placed. If the bit T at the destination address of the jump order is equal to 1, it means the beginning of a compound order, which can be executed directly. This situation is shown in figure 8 and figure 9. Figure 10 shows the notation of the following form: Fm, where n is the number of the placed order, and m is the number of the order within the folded order n. The permissible range of changes m is from 1 to the maximum length of the folded order, which in this example is 3. Order 2 from folded order 1 is a jump order that can be executed along two paths a and b. S heavy a leads to the middle order (I2) of the order folding j, while path b leads to the first folding order j. When the jump order is executed along path a, the hardware system

166 513 takes a maximum length compound order, that is, three 'orders, and then executes the compound orders I2' and I3. The remainder of the orders received, namely^k1, is recognized as the initial order of a new compound order or a single order (because it has T = 1) and is in the reserve, while the next block of text is downloaded for the next execution. If the jump order is executed along path b to the first order placed j, the hardware system re-downloads a block of text equal to the maximum length of the order placed, thus providing the complete order I * 2, j The execution of this order takes place directly.

The above method may equally well be used for other markup formats, namely the second format previously shown.

Note that the jump order B1 in fig. 10 it is made with the order following it, but because the jump is performed, the previously downloaded text following the order, regardless of whether it consists of compound orders of the compound instruction containing the jump or of subsequent single or compound orders or simply data ( in systems that allow mixing of data and instructions) it cannot cause the machine to be updated if the program is to behave correctly. In addition, retrieving an order from the address to which the jump is being performed may result in retrieving the next folding order containing the next jump order, which may also be followed by a text that should not cause a modification of the machine condition provided that the second jump order is executed. The sequence of subsequent jump commands can be repeated to infinity. In both cases, the solution to maintaining the correct behavior of the program is to prevent commands that should not be executed from updating the machine's state. Thus, the results of executing the pre-downloaded text that follows the executed jump order sequentially should be canceled. You can save it in the following rules:

1. Start the execution of a folded order containing any jump order inside the folded order.

2. If the order placed actually contains a jump order, do not allow any order following the jump order, whether within the same compound order as the jump order, or the next folding order or simple order, to modify the state of the machine.

3. If the jump order is executed, cancel the results of each order that follows the jump command. However, do not cancel the order in which the jump occurred.

ORDER CYCLES

<td colspan="2"></td><td>1 CYCLE</td><td>2 CYCLE</td><td>3 CYCLE</td><td>cy⁴kl</td><td>5 CYCLE</td><td>6, CYCLE 1</td>

<td>UNIT FUNCTIONAL</td><td>AND</td><td>s 1 1 ^S</td><td>CS</td><td>^CS</td><td></td><td>CS</td><td>and 1 1 s * ^s !</td>

<td>UNIT functional</td><td>B</td><td> | -</td><td>and _ 1</td><td>CS</td><td> —</td><td>cs</td><td> 1 1 1</td>

<td>UNIT ^ Nkcjonalna</td><td>C</td><td> 1</td><td>ί cs 1</td><td> —</td><td>s</td><td>CS</td><td> 1 - ! 1</td>

<td>UNIT FUNCTIONAL</td><td> 0</td><td> 1 1 !</td><td>ί CS 1 1</td><td> —</td><td> —</td><td>cs</td><td>1 - and 1 J</td>

FOLDING ORDERS

<img file="PL166513B1_D0001.tif" />

FOLDING ORDERS

SCALAR S-ORDER

Cs = FOLDING SCALAR ORDER

FOLDING ORDER T-MARKER f | &lt;S, 2 (XONOPROCESSOR EXECUTION AND

<img file="PL166513B1_D0002.tif" />

Figure 3

<img file="PL166513B1_D0003.tif" />

Fig. 4A

<img file="PL166513B1_D0004.tif" />

4b

<img file="PL166513B1_D0005.tif" />

Fig. 5

PROGRAM IN ASEMBLER LANGUAGE

PROGRAM WITH ORDERS \

a \

&gt;5 \

<img file="PL166513B1_D0006.tif" />

POSSIBLE FOLDING COMBINATIONS

<img file="PL166513B1_D0007.tif" />

Fig. 7

PAWEC

<img file="PL166513B1_D0008.tif" />

Fig. 8

ASEMBLER PROGRAM&gt; 1 1 2

PROGRAM

WITH FOLDING ORDERS ^mV 'S 1

<td></td><td></td><td>TEAM</td>

<td></td><td></td><td>SKŁAOANIA</td>

EIG9 ^m2_s

<img file="PL166513B1_D0009.tif" />

η ', 1 n 2

<img file="PL166513B1_D0010.tif" />

<img file="PL166513B1_D0011.tif" />

FIG.1O

B = JUMP ORDER

<img file="PL166513B1_D0012.tif" />

UP Department of Publications. Circulation of 90 copies Price PLN 1.00