Method of instruction sequence identification in byte flow and at least two instructions flagging for parallel execution

The following related applications are commonly owned by successors and are classified as follows: "The equipment of computers with associated dependencies" (document EN 990 014 filed December 4, 1990, ser. Np ^ -Q77504,910; and Machine Architecture to converts of technical units in a set of compound instructions (doc. EN 990 020), filed May 4, 1990,, 07/51 9 »38>.

Field of technology

The invention relates to the parallel processing of instructions by a computer, and more particularly to the processing of a binary information stream containing information to identify those instructions that may be executed in parallel by a specific computer assembly.

Prior art

The concept of parallel instruction compilation has helped increase the performance of computer systems. Parallel assembly is based on separate functional units that can execute two or more identical or different instructions simultaneously.

Another technique used to increase the performance of computer systems is concatenated processing. Concatenated processing provides a parallel processing procedure because it allows multiple instructions to be executed in parallel.

However, the success of parallel execution or concatenated processing is often not achieved due to delays caused by interlocking during data transmission and due to interlocking depending on the instrumentation. An example of data-dependent interlocking is so-called write-read blocking, where the first instruction must write its result before the second instruction can be read and then used. An example of interlocking by hardware is the moment where the first instruction must use a special instrument component of the hardware and the second instruction must also use the same special component of the hardware.

One of the previously used techniques to eliminate mutual blocking (sometimes called chain hazards) is dynamic scheduling. Dynamic scheduling means that shortly before the start, the opcodes in the instruction stream are decoded to determine if the instructions can be executed in parallel. Computers practicing one type of such dynamic scheduling are sometimes called superscalar resources. The dynamic scheduling criteria are uniform for the architecture of each instruction set, as well as the basic implementation of that architecture in any given instruction processing unit. The efficiency of dynamic scheduling is therefore limited by the complexity of the architecture, which leads to extensive logic determining which combinations of instructions can be executed in parallel, thus increasing the cycle time of the operating base unit. Increased instrumentation and cycle time for dynamic scheduling is becoming a major problem for architectures that have hundreds of different instructions.

Several attempts have also been made to increase efficiency by means of so-called static scheduling, which is performed before the instruction flow is recalled from memory for calculation. Static scheduling is achieved by moving the code and thus reordering the instruction sequence before calculation, the photo reordering creates an equivalent instruction flow that makes much more use of instrumentation through parallel processing. Such static scheduling is typically performed at the time of translation into a machine-oriented language. However, the reordered instructions remain in their original state, and normal parallel processing still requires some form of dynamic determination just before the instructions are executed in order to decide whether to execute the next two instructions in series or in parallel.

There are other shortcomings with dynamic scheduling, static scheduling, or a combination thereof. For example, each scalar instruction needs to be re-examined each time it is called to execute, deciding whether it is eligible for parallel execution. There is no provision for identifying and pre-marking those scalar instructions that are capable of executing in parallel.

Another disadvantage of dynamic scheduling in the implementation of superscalar machines is the method of assessing scalar instructions for possible parallel processing. Superscalar machines test her scalar instructions based on descriptions of their opcode, and there is no provision for computer hardware to be taken into account. Instructions are also issued by the first ranked method, the first selected, thereby eliminating the possibility of forming groups to prevent or reduce the occurrence of interlocking.

In several existing technical solutions, the requirements of technical equipment for parallel processing of instructions are taken into account. One such solution is a machine for processing very long instruction words, in which an ingenious compiler rearranges the instructions so that machine scheduling of instructions is simplified. With this approach to the solution, the compiler must be more complex than standard compilers, so a larger window can be used to find more parallelisms in the instruction flow. The resulting instructions may not necessarily be target code compatible with the existing architecture, thereby solving one problem while creating new problems. In fact, other new problems also arise due to the frequent branching that limits its parallelism.

A recent innovation in an effort to make much more complete use of parallel instruction execution is called Computer Hardware with Associated Data Dependencies. The compound instruction is created by pre-processing the instruction stream to find sets with two or more adjacent scalar instructions that can be executed in parallel. Certain types of interlocking instructions may be composed for parallel execution in some cases where interlocking is capable of grouping in a particular configuration of computer hardware. In other configurations where reciprocal groupings are ineligible, instruction with data dependent or hardware dependent, interlocks are excluded from the groups forming the compound instructions. Each compound instruction is identified by control information such as designations assigned to the compound instruction and the length of the compound instruction capable of being converted from a set of two scalar instructions to any maximum number of individual scalar instructions that can be processed together by specific computer hardware implementation.

If an instruction is called for execution, the limits of the instructions must be known for proper execution. However, where the instruction flow is preprocessed to form compound instructions, the limits of the instructions are often not apparent by simply testing a byte string. This is especially true for architectures that allow variable instruction lengths. Additional complications arise when the architecture allows data and instructions to be mixed with each other.

In an architecture, such as the IBM 370 system, both of the above shortcomings cause a very complicated problem in pre-processing the instruction stream to locate suitable groups of scalar instructions. First, the instructions have three possible lengths - two bytes or four bytes or six bytes. Although the actual length of a special instruction is indicated in the first two bits of the instruction opcode, the beginning of an instruction in a byte string cannot normally be identified by a mere check. Second, instructions and data can be mixed with each other. For these reasons, the existence or non-existence of a reference point in the byte flow of an instruction is critical to the present invention. A reference point is defined as knowledge of the beginning of an instruction or where the limits of an instruction are. If no additional information is supplied to the instruction flow, the limits of the instruction are usually known only from the compilation time or the computation time when the instructions are called by the base unit.

The essence of the invention

Brief content and objects of the invention.

According to said introduction, it is an object of the invention to provide technical means for generating compound instructions from a stream of binary instructions without knowing the beginning of the instructions and without knowing which syllables contain data instead of instructions.

Another object of the invention is to add control information to an instruction stream containing group information indicating where a compound instruction begins, as well as an indication of the number of scalar instructions that are included in the compound instruction.

Another object is to provide technical means that would be applicable to complex instruction architectures of variable instruction length and data mixed with instructions, and which are also applicable to displaced instruction counter architectures in which instructions are of constant length and in which data is not mixed with instructions.

Still another object is to provide a method of pre-processing an instruction stream to compile compound instructions that have still retained their original contents. A parallel object is to construct compound instructions without changing the target code of the scalar instructions that make up the compound instruction, thereby allowing existing programs to improve the efficiency of the compound instruction processing machine while maintaining compatibility with earlier scalar instruction machines.

Another object is to determine a method of pre-processing an instruction flow to create compound instructions, and which method can be implemented by software or technical means at various points in the computer system prior to executing the instruction. A concurrent object is to provide a method of pre-processing operations that control the flow of binary instructions as part of a subsequent compiler or part of the input memory._}or a portion of the fast buffer of the instruction composing unit and which allows the composite instructions to start at the beginning of the syllable flow without the instruction limits being known.

According to the invention, the aim is to achieve the above-mentioned objects by pre-processing a set of instructions (or a program) in order to statistically determine which instructions can be composed into compound instructions. Such processing is done in a typical connection into one set of program resources or technical means, which finds classes of instructions that can be executed in parallel in the arrangement of a special computer system. Instruction classes and composition rules are implementation specifics and will vary depending on the number and type of functional implementation units. While maintaining their original sequence and intact target code, individual instructions will be selectively grouped and combined with one or more other contiguous scalar instructions to create a compound instruction byte stream that includes both compound scalar instructions for parallel execution and uncompound scalar instructions for individual implementation. The control information is appended to identify information related to the execution of the compound instructions.

The present invention provides a technique for composing two or

v. a plurality of scalar instructions from one instruction stream without knowing the start time or length of each individual instruction. All possible instruction sequences are judged according to the sequence of the predetermined field position for the assumed instruction length. On IBM / 370, the length of the instruction is part of the opcode. In other systems, the instruction length is part of the operand.

In some cases of practical use of the technique according to the invention, a valid convergence arises between the two possible sequences of instructions, thus narrowing the possible selections of instruction limits. In other cases, where no valid convergence occurs, various possible sequences of instructions are followed until the end of the syllable flow. The actual limits of the instructions are not known unless the instructions are called for execution. Thus, all credible instructions, as well as all interfering instructions, are encoded with identification marking bits on the basis of special rules authoritative for the configuration of the technical means. In the IBM / 370 system architecture, cell instructions are two, four, or six syllable lengths, based on the length codes in the instruction. The value of each identification tag bit (based on the assumed position of the opcode) is recorded for each possible two, four, or six syllable instruction. Once the actual limit of the instruction is determined for calculation, the corresponding correct mark values ​​are used to identify the beginning of the compound instruction or the beginning of the unfolded instruction, and other incorrect generated marks are omitted.

Overview of figures in the drawings

The above and other objects, features and advantages of the invention will be apparent to those skilled in the art in view of the following description and the accompanying drawings.

Brief description of the drawings

Giant. 1 is a basic diagram of a higher level of the invention;

Giant. 2 is a timing diagram of a sequence processor implementation showing the parallel execution of certain non-blocked instructions that have been selectively grouped into a compound instruction flow;

Giant. 3 is a timing diagram of a multiprocessor implementation showing the parallel execution of scalar and compound instructions that are not interlocked;

Giant. 4 is divided into FIGS. 4A, 4B and illustrates the selective categorization of instructions executed by an existing scalar device;

Giant. 5 shows a typical program path from the initial code to the actual calculation;

Giant. 6 is a flowchart showing a program generation of a set of compound instructions from a language program assembler;

Giant. 7 is a flowchart showing the execution of a compound instruction set program;

Giant. 8 is an analytical diagram for instruction flow texts with identifiable reference points;

Giant. 9 is an analytical diagram for instruction flow texts with variable length instructions without a reference point, showing its parallel sets of possible composite identification bits;

Giant. 1

Giant. 1

Giant. 1

Giant. 1

Giant. 1

Giant. 1

Giant. 1 is a worst case analysis diagram of an instruction flow text with mutually mixed data and instructions of variable length, without a reference point, showing their parallel sets of possible composite identification bits;

shows a logical implementation of a composite instruction device for processing the instruction flow texts according to Figs. 9 and 10;

the worst case analytical diagram of the instruction text of Fig. 10, showing sets of possible compound identification bits to form groups of up to four scalar instructions for generating each compound instruction;

a flowchart for composing the instruction flow with a label for identifying the instruction limit reference points;

how different groups of valid non-blocked pairs of instructions form multiple compound instructions for sequential or branched target execution; shows how different groups of valid unblocked triples of instructions form multiple compound instructions for sequential or branched target execution; divided into Figs. 10A and 16B, shows a flowchart for instructing the instruction flow as in Fig. 9 · • τ'ί'Ζί.'Ι · / ΡΚίΤ; ... ''. 'Τ'

- 10 Example of an embodiment of the invention

Detailed description of the connection into one unit according to the invention.

As shown in the various drawings described in more detail below, a recent innovation called a Machine Capable of Converting Composite Instruction Set Units provides a flow of scalar instructions to be assembled or grouped together before instruction instruction decoding so that they are already marked and identified for simultaneous parallel computation by appropriate instruction sets. basic units. Because this composition does not change the target code, existing programs can improve performance while maintaining compatibility with previously implemented systems.

As generally shown in FIG. 1, the instruction composition unit 20 takes over the stream 21 of binary scalar instructions (including or without data content) and selectively groups several adjacent scalar instructions to form encoded compound instructions. The resulting composite instruction stream 22 therefore combines scalar instructions incapable of parallel computation and composes instructions formed by groups of scalar instructions that are capable of parallel execution. If the scalar instruction is offered to the instruction base unit 24, it is routed to the appropriate functional unit for serial execution. If a compound instruction is offered to the instruction base unit 24, each of its scalar components is introduced to the respective functional unit or pooling unit for simultaneous parallel execution. Typical functional units include, but are not limited to, an arithmetic and logic unit 26, 28, a floating point arithmetic unit 30, and a memory address generation unit 32. An example of a unit associating dependent data is described in co-pending ser. No. 07 / 504,910 on the title Technical equipment of devices associating dependent data submitted on 4.4.1990.

It should be appreciated that the technique of the invention is extended with the intention of simplifying the parallel issuance and execution of instructions in all computer architectures that process multiple instructions in a single cycle (although certain instructions

XZTJZ ·; -.

may require more than a barley cycle to perform).

As can be seen in Figure 2, the invention can be implemented in an embodiment of a sequential processor, where each functional operating unit processes a scalar instruction (S) or alternatively a compound scalar instruction (CS). As can be seen from the drawing, the instruction stream 33 containing sequential scalar and compound scalar instructions is provided with a control notation (T) assigned to each compound instruction. Thus, the first scalar instruction 34 can only be executed by functional unit A in cycle 1; the triple compound instruction 36 identified by the designation T3 may have its three compound scalar instructions executed in parallel by the functional units A, C and D in cycle 2; another compound instruction 38 identified by T2 may have its pair of compound scalar instructions executed in parallel by function units A and B in cycle 3i, the second scalar instruction 40 may be executed singly by function unit C in cycle 4; a large group of compound instructions 42 may have its four scalar instructions executed in parallel by the functional units AD in cycle 5f, and the third scalar instruction 44 may be executed individually by the functional unit A in cycle 6.

It is important to note that multiple compound instructions are capable of parallel processing in certain computing architectures. For example, the invention can potentially be implemented by multiprocessor equipment, as shown in Figure 3, where a compound instruction processed as a parallel call unit is one of the basic units. As shown in the drawing, the same instruction stream 33 could only be processed in two cycles as follows. In the first cycle, the central processing unit CPU £ 1 executes the first scalar instruction 34; the CPU # 2 functional units execute the triple compound instruction 36; and functional CPU units #⁷ 3 executes two compound scalar instructions in a compound instruction 38. In the second cycle, the CPU 1 executes the second scalar instruction £ 0; functional units of the basic unit CPU #⁷ 2 executes four compound scalar instructions in compound instruction 42; and CPU base unit function unit # 3 .ksíssws ·;

tí- '.' executes the third scalar instruction 44.

An example of a computer architecture that can be adapted to process compound instructions is the IBM System / 370 instruction level architecture, in which multiple scalar instructions can be issued to execute in each machine cycle. In this sense, the machine cycle corresponds to any concatenated steps or steps required to execute a scalar instruction. Scalar instructions work with operands with the content of unambiguous parameters. When a scalar flow is composed, adjacent scalar instructions are selectively grouped for simultaneous or parallel execution.

Instruction sets for various IBM system / 370 architectures such as system / 370, system / 370 with extended architecture (370-XA), operating system architecture (370-ESA) are well known.

In this regard, we recommend the publication Principles of Operation of IBM System / 370 (publication GA22-7000-10 1987), and Principles of Operation, IBM Architecture of Operating Systems / 370 (publication SA22-7200-0 1988).

In general, the instruction composing device will look for classes of instructions that can be executed in parallel and will ensure that there is no interlocking between the members of the instruction that cannot be handled by technical means. If compatible instruction sequences are searched, a compound instruction is created.

More specifically, the system / 370 instruction set can be broken down into categories that can be executed in parallel in a special computer system architecture. Instructions in certain of these categories can be combined or composed with instructions in the same categories or with instructions in certain other categories to form a compound instruction. For example, a portion of the system / 370 instruction set may be divided into the categories shown in FIG. The principles of this categorization are based on the functional requirements of the / 370 system instructions and the use of its technical means in a typical computer system architecture. The rest of the instructions of the system / 370 are not specifically considered for stacking in this exemplary embodiment. This does not prevent them from being assembled using the technique of the present and the invention described above.

Consider, for example, instructions contained in category 1 composed of instructions from the same category in the following sequence of instructions: AR R1, R2

SR R3, R4

This sequence is without random interlock data and gives the following results, which contain two independent system instructions / 370: R1 = R1 + R2

R3 = R3 - R4

Performing such a sequence would require two independent and parallel 2: 1 ALUs, which are designed for instruction level architecture. It is to be understood, therefore, that these two instructions may be grouped in the form of compound instructions in a computer system arrangement with two such arithmetic and logic units. The above example of compound scalar instructions can be extended to all pairs of instruction sequences that do not contain data on dependent interlocks as well as dependent interlocks of hardware.

In any actual instruction processor, there is an upper limit on the number of individual instructions that can contain a compound instruction. This upper limit must be specifically incorporated into a hardware or software unit that creates compound instructions so that the compound instructions no longer contain individual instructions (e.g., a paired group, a triple group, a four-member group) than the maximum capability based on a technical means calculation. This upper limit is strictly dependent on the implementation of technical means in a special arrangement of the computer system. It does not limit the total number of instructions that can be considered for composition or the length of the group window in a given code sequence that can be analyzed for composition. In general, the greater the window length of the assembled group for folding, the greater the parallelism that can be achieved due to the greater number of advantageous combinations.

With reference to Fig. 5, there are many possible places in the computer system where association can occur both in the software and in the hardware. Each has unique advantages and disadvantages. As shown in Figure 5, there are various stages by which a program typically passes from the initial code to the actual calculation. In the compilation phase, the initial program is translated into machine code and saved on disk 46. In the computational phase, the program is read from disk 46 and stored in main memory 48 in a special configuration 50 of the computer system, where the instructions are executed by the respective instruction base units 52,

54, 56. Folding can occur at any point in the path described. In general, the closer the stacker is to the instruction base unit or the central base unit, the more the forced time becomes more urgent. If the stacker is located further away from the central base unit, multiple instructions can be tested in a large instruction flow window to determine the best grouping for stacking with improved operational efficiency. However, such early assembly leads to a greater number of impacts on the design of the rest of the system, depending on additional development and cost requirements.

The flowchart in Fig. 6 shows the program generation of a set of compound instructions from the language program assembler depending on the set adapted to the rules 58 for the composition, which affect both the system architecture and the hardware. The assembler program supplies input to the software compositing device 59, which creates a program of compound instructions. Subsequent blocks of instructions of a predetermined length are analyzed by the software compositing device 59. The length of each block 60, 62, 64 in the syllable stream that contains the group of instructions considered for folding depends on the complexity of the folding device.

As shown in Fig. 6, this special folding device is designed for two-way folding of m numbers of instructions with a fixed length in each block. The primary first step is considered if the first and second instructions form a foldable pair, and then if the second and third form a foldable pair, and then if the third and fourth form a foldable pair all the way to the end of the block. Once the various possible collapsible pairs C1-C5 have been identified, the composition device can select a preferred sequence of compound instructions and use markings or identification bits to identify the optimal sequence of compound instructions.

If there is no optimal sequence, all of the collapsible adjacent scalar instructions can be identified so that the branch to the target located between the various compound instructions can use any of the compound pairs it encounters (see Figure 14). Where multiple composite units are available, multiple subsequent blocks in the instruction flow could be stacked simultaneously.

However, for pre-processing an instruction stream, it is more advantageous to indicate where the instructions begin in order to create compound instructions, if there are already known reference points.

As is known, a reference point means recognizing which syllable of a text is the first syllable in an instruction. This knowledge can be obtained from any of the marked fields or other indications that provide information on the location of the instruction limits. In many computer systems, such a reference point is clearly known only to the compiler at compile time and only to the central base unit when invoking instructions. Such a reference point is not known between the compilation time and the invocation of the instruction unless a special marking scheme is adopted.

The flowchart in FIG. 7 shows the execution of a compound instruction set program that has been generated by the hardware of preprocessor 66 or programmed proprocessor 67. The compound instruction syllable stream enters a compound instruction cache 68 that serves as a buffer to provide quick access to compound instructions. The compound instruction issued by the logic 69 retrieves the compound instructions from the cache and drops its individual compound instructions into the respective functional units for parallel calculation.

It should be emphasized that the compound instruction calculation units 71 as well as the arithmetic and logic units in the compound instruction computer system are capable of calculating either scalar instruction one after the other or alternatively scalar instructions in parallel with other compound scalar instructions. Such parallel computation can be performed in various types of arithmetic units such as arithmetic and logic units, floating point arithmetic units 73, memory address generation units 75, or multiple functional units of the same type depending on computer architecture and specific computer system configuration.

After completing the compilation after the compilation time, the compiler can indicate by marking which syllables contain the first syllable of the instruction and which contain the data. The result of this special information is an increase in the efficiency of the composition, as the exact locations of the instructions are known. However, the compiler may otherwise distinguish between instructions and data in order to provide device-specific information for assembly by indicating instruction limits.

In an exemplary two-way composition performed according to this application, composition information is added to the instruction flow as one bit for every two syllables of the text (instructions and data). A label containing control information can generally be added to each instruction in the flow of compound syllables, that is, to each non-compound scalar instruction as well as to each compound scalar instruction contained in a pair, triple, or larger compound group. The identification syllables used herein refer to that portion of the designation that is used to identify and distinguish those compound scalar instructions forming a compound group from the remaining non-compound scalar instructions. Such uncompounded scalar instructions remain in the compound instruction program and are executed individually when invoked.

In a system with all 4-syllable instructions aligned to the four-syllable address limit, each four-syllable text is assigned one label. Similarly, if the instructions can be freely aligned, one label is required for each syllable of the text.

The case of composing a maximum of two instructions represents the smallest grouping of scalar instructions to form a compound instruction and uses the following preferential coding procedure for identification bits. Because all system instructions / 370 are aligned to the half-word boundary (two syllables) of lengths of either two, four, or six syllables, one label with identification bits is required for each half-word. In the example of this small grouping, the identification bit 1 ”indicates that the instruction starting with the considered syllable is compounded with the following instruction, while O indicates that the instruction starting with the considered syllable is not compounded. The identification bit associated with the halfwords is rejected as not containing the first syllable of the instruction. The identification bit for the first syllable in the second instruction is also rejected. As a result of this method of encoding the identification bits in the simplest case, only one bit of information is needed for the central base unit to identify the compound instruction during execution.

Where more than two scalar instructions may be grouped together, an additional identification bit may be required to form the compound instruction. The minimum number of bits to indicate the specific number of scalar instructions actually compounded is the logo rhythm at base 2 (rounded to the nearest integer) of the maximum number of instructions that can be grouped to create the compound instruction. For example, if the maximum is two, then one identification bit is required for each compound instruction. If the maximum is three or four, then two bits are required for each compound instruction. If the maximum is five, six, seven, or eight, then three identification bits are required for each compound instruction. This coding scheme is shown in Table 1:

TABLE 1

Identification Total

Encoded Bits means Composite

This instruction is not composed of 00 with any of the following instructions

This instruction consists of one following instruction two

This instruction consists of two following three instructions

This instruction consists of three

1 following the instructions four

It is understood, therefore, that each halfword needs a label, but the central base unit rejects all but one for the first instruction that is selected from the instruction stream. In other words, the syllable is examined by checking its identification bits to determine if it is a compound instruction. If it is not the beginning of a compound instruction, its identification bits are zero. If the syllable is the beginning of a compound instruction, the identification bits are 1 for the first instruction and 0 for the second instruction. If the syllable is the beginning of a compound instruction containing three scalar instructions, the identification bits are 2 ”for the first instruction and l for the second instruction and 0 for the third instruction. In other words, the identification bits indicate for each halfword whether or not this particular syllable is the beginning of a compound instruction, while at the same time indicating the number of instructions that make up the compound group.

This method of encoding compound instructions assumes that if three instructions are formed to form a triple group, the second and third instructions to form a paired group are also compounded. In other words, if branching to the second instruction occurs in the triple group, the identification bit I for the second instruction indicates that the second and third instructions will be executed as a composite pair in parallel even if the first instruction in the triple group is not executed.

It will be apparent to those skilled in the art that the present invention requires that the instruction stream be compounded only once for a particular computer system configuration, after which any invocation of the compound instructions will also cause the identification bits assigned to them to be invoked. This eliminates the need for inefficient determination of the last minute and selection of certain scalar instructions for parallel execution, which occurs repeatedly each time the same or different instructions for execution in a so-called superscalar machine are called.

Despite all the advantages of composing the flow of binary instructions in certain computer architectures, this procedure becomes difficult when a technique is developed to determine the boundaries of instructions in a syllable chain. Such determination becomes complicated when variable length instructions are allowed and even more complicated when data and instructions can be mixed. However, the limits of the instructions must be known at the time of execution in order to achieve accurate execution. However, once the composition is preferably performed, sufficient time is required before executing the instruction, the technique for composing the instructions, without knowing where the instructions begin and without knowing which syllables are data. This technique should be applied to all accepted types of architectures, including computer architectures with truncated instruction sets, in which the instructions are of constant length and are not mixed with data.

According to the present invention, there are several variations of the technique depending on the information currently available on the particular flow of instructions that are compiled. The various combinations of typically adequate information are shown in Table 2:

TABLE 2 - Syllable chain information

<td>Case</td><td>Instruction length</td><td>Data mixed</td><td>Reference point</td>

<td>AND</td><td>solid</td><td>No</td><td>Yes</td>

<td>B</td><td>variable</td><td>No</td><td>Yes</td>

<td>C</td><td>fixed or variable</td><td>Yes</td><td>Yes</td>

<td>D</td><td>solid</td><td>No</td><td>No</td>

<td>E</td><td>variable</td><td>No</td><td>No</td>

<td>F</td><td>solid</td><td>Yes</td><td>No</td>

<td>G</td><td>variable</td><td>Yes</td><td>No</td>

It should be noted that in some cases of fixed and variable length, the instructions are identified as different cases. This is because the existence of variable length instructions creates more uncertainty where the reference point is not known, resulting in more potential composite bits. In other words, when sequences of potential instructions are generated using the technique of the invention, there are no compound identification marks for syllables in the middle of any fixed length of instructions. The total number of identifiers, i.e. required according to the preferred coding scheme, is small (i.e. one identifier for every four syllables for instructions with a fixed length of four syllables). However, the unique technique of the invention also works well with instructions of fixed or variable lengths, because if the beginning of the instruction is known, it is always possible to find the length somewhere in the instructions.

In system / 370 instructions, the length is encoded in the opcode, while in other systems, the length is encoded in operands.

In the case of A with a fixed length of instructions without mixed data and with a known reference point for the location of the operand, the folding can follow the applicable rules for this particular computer configuration. If the length is fixed, the sequence of scalar instructions is normally determined, and each instruction in the sequence can be considered a possible candidate for parallel execution with the following instruction. The first encoded value in the control designation means that the instruction is not collapsible with the next instruction, while the second encoded value in the control designation means that the instruction is collapsible for parallel execution with the next instruction.

Similarly, in the case of B with a variable instruction length without mixed data and with a known reference point for instructions (and therefore also for an instruction length code), folding can proceed in a conventional manner. As shown in Fig. 8, the operands indicate a sequence of 70 instructions as follows: the first instruction is 6 syllables long, the second and third are 2 syllables long, the fourth is 4 syllables long, the fifth is 2 syllables long, the sixth is 6 syllables long and the seventh and the eighth is 2 syllables each.

For the purpose of illustration, the folding technique used is shown for forming compound instructions from adjacent pairs of scalar instructions (Figs. 8-9) as well as for forming compound instructions formed into larger groups of scalar instructions (Fig. 12). Exemplary rules for joining into one whole shown in the drawings are additionally defined so as to give all instructions of length 2 syllables or 3 syllables the possibility of composition with each other (ie a two-syllable instruction is capable of parallel composition in. this special arrangement of a computer with another two-syllable or another four-syllable instruction). The rules further dictate that not all instructions with a length of 6 syllables are complex at all (ie, a six-syllable instruction is only capable of executing a single execution in this particular computer configuration). Of course, the invention is not limited to these exemplary compositing rules, but is applicable to any set of compositing rules that define criteria for executing existing instructions in parallel in a specific configuration for a given computer architecture.

The set of rules used for the exemplary folding techniques of the invention is derived from the System / 370 architecture.

By testing the opcode for each instruction, the type and length of each instruction can be determined, and then a control label containing identification bits for said specific instruction is generated, as described in more detail below. However, the present invention is not limited to any specific architecture or set of instructions, and the above compilation rules are only an occasional example.

The preferred encoding of compound instructions in these illustrated connections into one unit is described below. If two adjacent instructions can be folded, their identification bits generated for storage are 1 for the first compound instruction and 0 for the second compound instruction. However, if the first and second instructions cannot be folded, the identification bit for the first instruction is 0 and then the second and third instructions are considered for composing. Once the instruction syllable stream has been pre-processed according to this technique and the identification bits have been encoded for different scalar instructions, more optimal results can be obtained to achieve parallel execution by using a larger window to search for larger groups and then selecting the best combination of adjacent pairs for composition.

The C-vector 72 in Fig. 8 shows the values ​​of the identification bits (called folding bits in the drawings) for this particular sequence of 70 instructions, where a reference point indicating the beginning of the first instruction is known. Based on the values ​​of these identification bits, the second and third instructions form a composite pair as indicated by the identification bit 1 for the second instruction. The fourth and fifth instructions form another composite pair as indicated by identification bit 1 for the fourth instruction. The seventh and eighth instructions also form a composite pair as indicated by identification bit 1 for the seventh instruction.

The C-vector 72 in Fig. 8 is also relatively easily generated in case B when there are no data syllables compatible with the instruction syllables and where the instructions are all the same length with known limits.

A somewhat more complicated situation occurs in the case of C, where

- 23 instructions are mixed with non-instructions, with a reference point still existing to indicate the beginning of the instruction. The basic diagram in Fig. 13 shows one way of indicating an instruction reference point, where each halfword has been marked with a flag indicating whether or not it contains the first syllable of the instruction. This can occur with both fixed length and variable instruction length. By introducing a reference point, it is not necessary to evaluate the data part of the syllable stream for a possible composition. Accordingly, the composing unit can skip and omit all non-instructional syllables.

Case D is not a difficult problem with fixed-length instructions without mixed data, since the instructions and data are typically aligned within predetermined syllable limits. So the table shows that the reference point is not known and is in fact normally determined based on the alignment requirements.

Case E is a much more complex situation where the syllable flow contains instructions of variable length (no data), but it is not known where the first instruction begins. Because the maximum length of an instruction is six syllables, and because the instructions are aligned to two-syllable limits, there are three possible starting points for the first flow instruction. Accordingly, the invention provides the possibility to take into account all possible starting points for the first instruction in the text of the syllable stream 79, as can be seen from FIG.

Sequence 1 assumes that the first instruction starts with the first syllable and proceeds with folding under this assumption. The field length value for the first syllable is 6, indicating that the next instruction begins with the seventh syllable; the field length value for the seventh syllable is 2, indicating that the next instruction begins with the ninth syllable; the field length value for the ninth syllable is 2 indicating that the next instruction begins with the eleventh syllable; the field length value for the eleventh syllable is 4 indicating that the next instruction begins with the fifteenth syllable; the field length value for the fifteenth syllable is 2, indicating that the next instruction begins with the seventeenth syllable; the field length value for the seventeenth syllable is 6 indicating that the next instruction begins with the twenty-third syl24 bica; the field length value for the twenty-third is 2, indicating that the next instruction begins with the twenty-fifth syllable; the field length value for the twenty-fifth syllable is 2, indicating that the next instruction begins (not shown) with the twenty-second syllable.

In this example join, the whole length of the array is also the determining value of the vector C for each possible instruction. Therefore, the C-vector 74 for sequence 1 has a value of 1 only for the first instruction of a possible compound pair formed by combinations of two-syllable and four-syllable instructions.

Sequence 2 assumes that the first instruction begins with the third syllable (beginning of the second half-word) and continues based on this assumption. The field length value for the third syllable is 2, indicating that the next instruction begins with the fifth syllable. By proceeding through each possible instruction, which is based on the field length value of the preceding instruction, the entire potential of the instructions in sequence 2 is generated along the possible identification bits, as shown by the C-vector 76.

Sequence 3 assumes that the first instruction begins with the fifth syllable (beginning of the third halfword) and continues as forwarded. The field length value for the fifth syllable is 4, meaning that the next instruction begins with the ninth syllable. By continuing through each possible instruction, which is based on the field length value of the previous instruction, the full potential of the instructions in sequence 3 is generated along the possible identification bits, as shown by C-vector 78.

In some cases, the three sequences of potential instructions converge into a single sequence. The convergence rate depends on the specific bits that are reserved in the potential operand field for the instruction length. In some syllable instruction streams, there is no convergence during the assembly of a special window (for example, a sequence of instructions in which all lengths have a value of Four syllables). In other cases, convergence within the same instruction limits could occur when composing a sequence of two different sequences out of phase. However, out-of-phase convergence is always corrected by the next uncomplicable instruction, if not earlier.

In Fig. 9, attention is paid to the three sequences that converge within the instruction limits at the end 80 of the eighth syllable.

It is also noted that when other sequences begin at the end of the sixth, eighth, and tenth syllables, they also converge rapidly. Sequences 2 and 3 when converging to the limits of the instruction at the end 82 of the fourth syllable are out of phase with folding until the end of the sixteenth syllable. In other words, these two sequences take into account different pairs of instructions based on the same sequence of instructions. Because the seventh syllable begins with an uncomplicable instruction in 84, the out-of-phase convergence is terminated. In a situation where each instruction window under review contains more than two instructions, different sequences may converge earlier because the same optimal pairing may be selected by the two instruction compilation devices.

If no valid convergence occurs, all three possible sequences of instructions must continue until the end of the window. However, where a valid convergence occurs and is detected, the number of sequences from three to two is combined (one of the identical sequences becomes ineligible for operation) and in some cases from two to one. Where a larger number of instruction sequences is to be expected due to unknown instruction limits, the folding speed will be lower than when folding in Fig. 8 with a factor equal to the number of active sequences (assuming a single unit capable of folding). If the convergence is fast, the exemplary folding speed shown in Figures 8 and 9 will actually be equivalent.

Thus, before converging, the experimental limits of the instruction for each possible instruction sequence are determined and identification bits are allocated for each such instruction indicating the location of potential compound instructions. It can be seen from Figure 9 that this technique generates three separate identification bits for each of the two syllables of the text. In order to match the preprocessing in the AD cases, it is desirable to reduce the three possible sequences to a single sequence of identification bits, where only one bit is assigned to each halfword. Because only a single piece of information is needed as to whether a common instruction is composed of the following instruction, the three bits can be logically read as 0 to create a single sequence in the CC vector 86.

The various procedures in the folding method shown in Fig. 9, as described above, are shown in the flowchart in Fig. 16.

For the purposes of parallel execution, the combined identification bits of the combined CC-vector are equivalent to the separate C-vectors of the individual three sequences 1 - 3. This can be shown with reference to the CC-vector in Fig. 9. If sequence 1 is followed and the first syllable is taken into account for executing either due to normal sequential processing or branching, an instruction is invoked according to its associated identification bits. If the identification bit is "0", the first instruction is executed in series as a single instruction. The identification bits associated with the third and fifth syllables are ignored. The next instruction in sequence 1 begins with the seventh syllable, so that such an instruction is called by the central base unit via its identification bit, which is I. Because this marks the beginning of a compound instruction, the next instruction is also called (its identification bit 1 in CC vector 86 is neglected, so its identification bit in C vector 74 is different and insignificant) for parallel execution with an instruction that begins with the seventh syllable. . The CC vector works so satisfactorily for sequence 1 if it is shown to be the actual sequence of the instruction.

When proceeding along sequence 2, and if the third syllable is considered for execution either due to normal sequential processing or branching, an instruction is invoked according to its associated identification bits. Because the identification bit is 1 and indicates the beginning of a compound instruction, another instruction is also called (its identification bit 1 in CC-vector 86 is neglected and the fact that its identification bit in C-vector 76 is different is irrelevant) for parallel execution with an instruction that begins with the third syllable. Thus, the CC vector works satisfactorily for sequence 2 if it is shown to be a true instruction sequence.

If we follow sequence 3 and take into account the third syllable for execution, either for reasons of normal sequential processing or branching, the instruction is called according to its associated identification bits. Because the identification bit is I and indicates the beginning of a compound instruction, another instruction is also called (its identification bit in CC-vector 86 is ignored and the fact that its identification bit in C-vector 78 is different without meaning) for parallel execution with the instruction which begins with the fifth syllable. Thus, the CC vector proves satisfactory for sequence 3 if it is shown to be indeed an instruction sequence.

The combined identification bits in the CC vector thus allow any of the three possible sequences of purely parallel execution for compound instructions or individual for non-compound instructions.

The associated identification bits also work well for branching. For example, if a branch occurs at the beginning 88 of the ninth syllable, then the instruction must begin with the ninth syllable. The identification bit 1 associated with the ninth syllable is used to correct parallel execution with the next instruction following it.

A beneficial advantage provided by the associated identification bits in the CC vector is the creation of multiple valid sequences of compound bits based on which instruction is addressed to the branch target. Differently composed instructions can be formed from the same syllable flow as best shown in Figures 14-15.

Figure 14 shows possible combinations of compound instructions when the computer configuration provides for starting and executing no more than two instructions. Where the instruction stream 90 containing the compound instructions is processed into one normal sequence, there will be a compound instruction for parallel execution, consisting in decoding the identification bit for the first syllable in the CC vector 92. However, if a branch to the fifth syllable occurs, a compound instruction II will be issued for parallel execution based on decoding the identification bit for the fifth syllable.

Similarly, normal sequencing of another compound syllable stream 94 results in sequentially executed compound instructions IV, VI, and VIII (component instructions in each compound instruction are executed in parallel). Branching in the third syllable of a compound syllable stream results in sequential execution of compound instructions V and VII, and an instruction beginning with the fifteenth syllable (forming the second part of compound instruction VIII) will be issued and executed individually, all based on identification bits in CC vector 96.

Branching in the seventh syllable results in sequential execution in compound instructions VI and VIII, and branching in the eleventh syllable results in sequential branching in compound instruction VIII.

The branching in the ninth syllable, on the other hand, results in sequential execution in compound instruction VII (it is shaped by the second part of compound instruction VI and the first part of compound instruction VIII).

Thus, identification bits 1 in the CC vector 96 for compound instructions IV, VI and VIII are neglected when any of compound instructions V or VII is executed. Alternatively, identification bits 1 in CC vector 96 for compound instructions V and VII are neglected when any of compound instructions IV, VI or VIII is executed.

Figure 15 shows possible combinations of compound instructions when the computer configuration provides parallel issuance and execution of up to three instructions. Where the instruction stream 98 containing the compound instructions is processed in a normal sequence, the compound instructions X (triple group) and XIII (pen group) will be executed. Branching in the eleventh syllable, on the other hand, results in the execution of a compound instruction XI (triple group) and branching in the thirteenth syllable results in the execution of a compound instruction XII (different triple group).

Bits 2 of the identifier in the CC vector 99 for the compound instructions XI and XII are neglected when the compound instructions X and XIII are executed. On the other hand, when the compound instruction XI is executed, the identifier bits for the other three compound instructions X, XII, XIII are neglected. Similarly, when a compound instruction XII is executed, the identifier bits for the other three compound instructions X, XI, XIII are neglected.

Case G is the most complex case dealing with an instruction flow with data mixed with variable-length instructions, without any known reference point at the beginning of any instruction. This can occur when pages are cached or cached when the reference point is unknown. The first one-piece connection (not shown) dealing with case G is identical to that used in case E, but there is an additional difference due to the fact that the data are mixed with the instructions. If convergence occurs, a new sequence must always start instead of each sequence eliminated by the convergence. This is because convergence could arise in a syllable containing data; as a result, all three compound sequences could converge into a disruptive sequence of instructions that are not actually instructions at all. This could possibly be corrected when a sequence of actual instructions meets one of the sequences. In the meantime, some complicated instructions could not be found. The resulting flow of compound instructions would still be processed accurately, but few compound instruction pairs would be marked for parallel execution, and therefore the performance of the central base unit would be reduced.

The preferred technique for case G is shown in FIG. 10 for the same syllable flow 79 as in FIG. A new sequence of possible instructions begins in each halfword, regardless of the part of the instruction length of the potential opcode field. As in other cases, two adjacent potential instructions are tested and the respective identifier bits in different C-vectors 100 are determined. This is repeated later at the beginning of two syllables (one halfword). As in the case of E, the different values ​​of the C-vector for the same half-word are operationally examined together (see FIG. 11) in order to generate the associated identification bits of the concurrent combined CC-vector 102. It should be noted that in this particular union, where the composer identifies a compound instruction by writing 1 for the first syllable only, and where in Fig. 10 each potential sequence is only two instructions long, a single bit resulting in tests of each sequence using coding scheme for two-way composition. Consequently, to create the CC-vector 102 in this case, all the first identification bits are concatenated in each sequence, thus creating the same CC-vector, which would generally be the result of an operational examination of different C-vector values.

If a syllable is selected for execution, it must indeed be an instruction if the program is correct, and the identification bit of the corresponding CC vector associated with the syllable is tested to determine if the syllable is the beginning of the compound instruction. The designations associated with the data are always invalid for the duration of the execution of the actual instructions, both scalar instructions executed individually and compound instructions executed in parallel.

If the branch instruction is composed of data, the branch must be accepted (assuming a perfect program) and the second instruction in the pair that was to be executed in parallel is canceled if the branch was not accepted. This capability must already exist in the execution unit if the branching is to be performed in parallel with the following chained instruction.

It is important to note that the associated composite sequences in the CC-vectors 88, 102 in Figures 9-and 10 are not the same even though the text is identical. Since it is known from Fig. 9 that the text does not contain data mixed with instructions, convergence occurs at a known reference point. The special values ​​1 in the CC-vector 102 occur after the reference point in FIG. 9 is known, and these special 1s do not correspond to the halfwords with which the instructions begin, because they are recorded for possible data in the existing text. However, if the text contains only instructions, as assumed in the technique of case E shown in Fig. 9, the different combined sequences in the two CC-vectors 88, 102 will nevertheless result in the execution of an identical program depending on the advantages of the invention.

Case F containing fixed-length instructions mixed with data and without an instruction reference point is a simplified version of Case G. If two syllable-length instructions are aligned within half-words, then potential instruction sequences are started with each half-word and the instruction length need not be used to generating potential sequences.

The most unfavorable case of the technique in Fig. 10 relates to the case G, where a larger number of possible instruction sequences are tested than in the case of the AF case technique. This may require more time or more composition units to generate the necessary identification bits in the implementation-dependent tags.

There are many possible constructions of the unit for composing an instruction depending on its location and knowledge of textual contents. In the simplest situation, it would be desirable for the compiler to indicate by indicating which syllables contain the first syllable of the instruction and which contain the data. This special information results in a much more efficient composition unit, as the exact locations of the instructions are known (see Fig. 13). This means that the composition can always be performed as in the C case situations in order to generate a C-vector of identification bits for each compound instruction (see Fig. 8). The compiler could thus add other information such as static branching predictions or even insert guidelines into the composition unit.

Other procedures can be used to distinguish data from instructions, where the instruction stream is to be composed and stored in memory. For example, if parts of the data are sparse, a simple address list containing data would require less space than a label. Such combinations of technical and software means for composition provide many variations for the efficient creation of compound instructions.

Fig. 11 shows a flow chart of a possible implementation of a unit for composing and manipulating instruction streams in each case of an E, F or G category. The multiple number of composition units 104, 106, 108 is shown, and in order to increase efficiency, this number may be as large as the number of halfwords contained in the text buffer. In this arrangement used in the case of G, the three folding units can start to process the sequences of the respective first, third and fifth syllables. After completing the possible instruction sequence, each companion begins testing the next possible sequence shifted by six syllables from its previous sequence. Each compaunder creates compound identification bits (C-vector values) for each halfword in the text. Three sequences of the three compounds are operationally examined by unit 110, and the resulting associated identification bits (CC vector values) are stored in memory along with their corresponding text syllables.

Figure 12 shows the worst case composition technique as used in case G for large groups of up to four instructions in each compound instruction. Again, we consider the same syllable flow 79. Each syllable at the beginning of a halfword is examined as if it were the beginning of an instruction, and its opcode was evaluated to locate a potential sequence of three additional instructions. If it cannot be composed, the value of its identification bit is O ”. If it can be composed with another potential instruction, the identification bit is 1 for the first instruction in the pair and "0" for the second instruction in the pair. If it is found that it cannot be composed with other potential instructions, the corresponding folding bits at the beginning of the first instruction are "2", 1 and 0. This method assumes that a branch in the middle of a large group of compound instructions can form a triple or paired group. the final subset of a large group.

Referring to Figure 10, syllables beginning with each half-word must be examined to determine the limits of a potential instruction. Each tested sequence creates a sequence of identification bits called C-vectors 112. A composite sequence of identification bits called CC-vector values ​​114 is formed by selecting a maximum value from all the individual identification bits associated with said halfwords. When a large group of compound instructions is issued and executed, the central base unit neglects all compound bits associated with syllables other than the first sla33 of the group. In this encoding method, the composite identification bits in the CC vector 114 indicate the beginning of the compound instruction as well as indicate the number of instructions compiling the compound instruction.

Depending on the actual rules used for the composition, some optimizations of the composition technique may occur, especially for a large group. For example, the start of the fifth sequence in the ninth syllable 116 assumes instruction lengths of 2, 4, 2 and 6 syllables. Since six-syllable instructions are incomprehensible in this example, it makes no sense to try to compose the other three potential instructions (eleven, fifteen, and seventeen-syllable) because they have already been compiled as much as possible. The identification bits in this regard for potential instructions beginning with the eleventh and fifteenth syllables have already been marked in the C-vectors 112 and 118, 120, respectively. Assuming that the ninth syllable begins the instruction sequence at position 116, the thirteenth syllable does not begin the instruction. However, this optimality just described still requires that the thirteenth syllable be examined at location 122 as the beginning of a possible instruction, as this has not been considered before.

However, the method of composing a large group will continue for all half-words of the text, even if the example shown in Fig. 12 ends with the fifteenth syllable.

In order to reduce the number of bits for conversion, there may be alternative representations of the composite information. Identification bits for composition, for example, could be converted to various formats once a proper instruction limit has been determined. For example, one bit for an instruction can be achieved by the following encoding: a value of 1 means pass with the next instruction and a value of 0 means not fold with the next instruction. A compound instruction consisting of a group of four individual instructions will have a sequence of identification bits for the composition (1,1,1,0). With respect to other previously described compound instructions, the composition identification bits associated with half-words that are not instructions and therefore do not have opcodes are neglected at the time of execution.

While exemplary preferred embodiments of the invention have been described, it will be apparent to those skilled in the art to consider various modifications and changes that may be derived from the spirit and scope of the invention as defined in the following claims.