Process for dividing instructions of a computer program into instruction groups for parallel processing
First Claim
1. A process for machine generation of secondary processable instruction groups from a program for super-scalar microprocessors,a) for each instruction of the program setting a blocking position in a value table when, before execution of an instruction directly dependent on data, a delay cycle is to be inserted, inserting a succession number into the value table which indicates how many data-dependent instructions follow directly, entering a distance value which specifies a maximum number of clock cycles up to a last of the data-dependent instructions,b) specifying in a delay cycle table for each instruction how many delay cycles occur between instructions,c) classifying each of the instructions into instruction groups as follows,aa) initially setting all the instructions as unmarked,ab) storing all instructions which have no preceding data-dependent unmarked instruction in a first list,ad) selecting instructions from the first list which can be executed after a minimum number of delay cycles, and storing the selected instructions in a second list,ae) selecting an instruction in accordance with a heuristic selection process, the heuristic process of selecting an instruction from the second list having the steps of:
- identifying each instruction in the second list which has a blocking position that is set;
when no instructions are identified, selecting from the second list an instruction having a maximum distance value and a maximum succession number;
when only one instruction is identified, selecting from the second list an instruction having a maximum distance value and a maximum succession number;
when only one instruction is identified, selecting from the second list said identified instruction;
when a plurality of instructions are identified, arbitrarily selecting an instruction from said plurality of instructions,af) classifying each selected instruction into an instruction group having components such that each selected instruction is assigned to the instruction group having an earliest permissible execution cycle, and in one of the components according to a predetermined sequence.
1 Assignment
0 Petitions
Accused Products
Abstract
In order to be able to execute rapid processing of a program on super-scalar microprocessors, the individual instructions of this program must be divided into instruction groups, which can be processed by processing units of the microprocessor, in such a way that the instructions can be processed in parallel. In this case, it is necessary to take account of data-flow dependences and control-flow dependences as well as pipeline conflicts. For this purpose, the first step is to select the instructions whose precursor instructions have already been processed and to investigate these instructions as to whether before their execution a minimum number of delay cycles is necessary, and the instructions are stored with a minimum number in a list. From these instructions, one is selected using a heuristic selection process, and this one is classified into an instruction group in which the instruction can be processed in the earliest possible execution cycle.
155 Citations
1 Claim
-
1. A process for machine generation of secondary processable instruction groups from a program for super-scalar microprocessors,
a) for each instruction of the program setting a blocking position in a value table when, before execution of an instruction directly dependent on data, a delay cycle is to be inserted, inserting a succession number into the value table which indicates how many data-dependent instructions follow directly, entering a distance value which specifies a maximum number of clock cycles up to a last of the data-dependent instructions, b) specifying in a delay cycle table for each instruction how many delay cycles occur between instructions, c) classifying each of the instructions into instruction groups as follows, aa) initially setting all the instructions as unmarked, ab) storing all instructions which have no preceding data-dependent unmarked instruction in a first list, ad) selecting instructions from the first list which can be executed after a minimum number of delay cycles, and storing the selected instructions in a second list, ae) selecting an instruction in accordance with a heuristic selection process, the heuristic process of selecting an instruction from the second list having the steps of: - identifying each instruction in the second list which has a blocking position that is set;
when no instructions are identified, selecting from the second list an instruction having a maximum distance value and a maximum succession number;
when only one instruction is identified, selecting from the second list an instruction having a maximum distance value and a maximum succession number;
when only one instruction is identified, selecting from the second list said identified instruction;
when a plurality of instructions are identified, arbitrarily selecting an instruction from said plurality of instructions,af) classifying each selected instruction into an instruction group having components such that each selected instruction is assigned to the instruction group having an earliest permissible execution cycle, and in one of the components according to a predetermined sequence.
- identifying each instruction in the second list which has a blocking position that is set;
Specification