Process for dividing instructions of a computer program into instruction groups for parallel processing

• US 5,712,996 A
• Filed: 09/14/1995
• Issued: 01/27/1998
• Est. Priority Date: 03/15/1993
• Status: Expired due to Fees

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: Schepers, Jorg
• Primary Examiner(s): Lall, Parshotam S.
• Assistant Examiner(s): PATEL, GAUTAM
• Application Number:
  US08/513,976
• Time in Patent Office: 866 Days
• Field of Search: 395/706, 395/709, 395/392
• US Class Current: 712/216
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/3853 of compound instructions
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units

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.

Claims

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.