Method and apparatus for sequencing computer instruction execution in a data processing system

• US 5,889,999 A
• Filed: 05/15/1996
• Issued: 03/30/1999
• Est. Priority Date: 05/15/1996
• Status: Expired due to Fees

• Current Assignee: Freescale Semiconductor, Inc. (NXP Semiconductors NV)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Smith, Roger A., Breternitz, Mauricio Jr.
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): DAM, TUAN QUANG
• Application Number:
  US08/647,863
• Time in Patent Office: 1,049 Days
• Field of Search: 395/709, 395/708, 395/705, 395/704, 395/702, 395/183.11, 395/183.15, 395/183.21, 395/185.04, 395/377, 395/583, 395/584, 395/586, 395/580, 395/392, 395/395 , 395/577, 395/381-383, 395/390-391, 395/670, 395/672
• US Class Current: 717/158
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 2201/865 Monitoring of software
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836

Abstract

A method and apparatus for sequencing computer instructions in memory (24) to provide for more instruction efficient execution by a central processing unit (CPU) (22) begins by executing the computer instructions via the CPU (22) and creating a trace file (FIG. 2) in memory (24). The trace file is then scanned using a window size greater than two (i.e., more than two instructions or basic blocks/ groups of instructions are selected as each window) and correlations are determined between several pairs of instructions in each window (FIGS. 9 and 10). The correlations obtained by the window procedure are then analyzed (FIG. 11) to determine an efficient ordering of computer instructions for subsequent execution by any target CPU.

Claims

1. A method for sequencing computer instructions for execution in a data processing system, the method comprising the steps of:

(a) providing, within a memory, a computer program containing basic blocks wherein each basic block contains at least one computer instruction and the computer program contains many computer instructions;

(b) executing the computer program by reading the many computer instructions from memory and executing the many computer instructions via a central processing unit (CPU);

(c) storing, in the memory during the step of executing, a trace data file which indicates an execution order of the basic blocks, the execution order indicating when in time any basic block is executed with respect to other basic blocks, the execution order having a beginning and an end;

(d) selecting a sequence of M basic blocks from the trace data file to form a selected group, M being a finite positive integer greater than two;

(e) accumulating, in memory for the selected group, correlation information pertaining to the sequence of M basic blocks from the trace data file by scanning a selection window through the M basic blocks and correlating each of the M basic blocks to each M-1 other basic blocks in the sequence of M basic blocks;

(f) selecting a different sequence of M basic blocks as the selected group;

(g) repeating steps (e) through (g) until a selected number of sequences of M basic blocks in the trace data file are processed; and

(h) using the correlation information obtained via steps (e) through (g) to order the basic blocks for subsequent execution.

2. The method of claim 1 wherein the step (c) further comprises:

inserting computer instructions into the computer program to write trace information to the trace data file.

3. The method of claim 1 wherein the step (c) further comprises:

periodically interrupting an execution of the computer program in order to write trace information to the trace data file.

4. The method of claim 1 wherein the step (e) further comprises:

constructing a directed graph of nodes and edges wherein each node represents a basic block and wherein each edge between two nodes of the basic block contain the correlation information pertaining to the sequence of M basic blocks.

5. The method of claim 4 wherein the step (e) further comprises:

constructing, in memory, a node for each basic block in the computer program;

identifying pairs of basic blocks in the sequence of M basic blocks, the first element of each pair coming before the second element of each pair in the sequence of M basic blocks;

creating, for each pair of basic blocks in the sequence of M basic blocks, an edge between the node representing the first element and the node representing the second element if no edge currently exists, a count of the edge being set to zero; and

incrementing, for each pair of basic blocks in the sequence of M basic blocks, the count of the edge by one.

6. The method of claim 1 wherein the step (f) further comprises:

selecting the different sequence of M basic blocks such that a beginning of the different sequence of M basic blocks in the trace data file is N locations from a beginning of the selected group from step (d) in the trace data file where N is a finite integer.

7. The method of claim 6 wherein the step (f) further comprises:

selecting the different sequence of M basic blocks such that the sequence from step (d) overlaps the different sequence selected in step (f).

8. The method of claim 1 wherein the step (h) comprises:

using the correlation information to sequence the basic blocks to optimize pipeline performance of a CPU used to execute the computer program after the performance of step (h).

9. The method of claim 1 wherein the step (h) comprises:

using the correlation information to sequence the basic blocks to optimize instruction cache performance of a CPU used to execute the computer program after the performance of step (h).

10. The method of claim 1 wherein the step (h) further comprises:

duplicating one basic block in the computer program to create a duplicated basic block; and

adding the duplicated basic block to the computer program for execution by a computer.

11. The method of claim 10 wherein the step (h) further comprises:

altering a control flow structure of the computer program in response to the formation of the duplicated basic block so that both the one basic block and the duplicated basic block are executed at different times when the computer program is executed by the computer.

12. The method of claim 1 wherein the step (h) comprises:

using the correlation information to improve branch prediction efficiency of a CPU used to execute the computer program after performing step (h).

13. The method of claim 1 wherein the step (h) comprises:

finding the correlation information by summing the correlation information after dividing the correlation information by fanout values.

14. A sequencer for sequencing computer instructions which are to be executed via a data processing system, the sequencer being stored on computer readable media and comprising:

computer instructions for initiating execution of a computer program stored in computer memory, the execution being performed by reading computer instructions which form basic blocks of computer code from computer memory and executing the computer instructions via a central processing unit (CPU);

computer instructions for storing, in the computer memory while the execution is being performed, a trace data file which indicates an execution order of the basic blocks, the execution order indicating when in time any basic block is executed with respect to other basic blocks in the computer program, the execution order having a beginning and an end;

computer instructions for iteratively choosing different sequences of partially overlapping M basic blocks from the trace data file to form selected groups of M basic blocks, M being a finite positive integer greater than two, and for each of the M basic blocks in each selected group accumulating, in memory for each selected group, correlation information between all pairs of the M basic blocks located within each selected group; and

computer instructions for using the correlation information to sequence the basic blocks of the computer program in an execution order for execution by a computer.

15. The sequencer of claim 14 further comprising:

computer instructions which use the correlation information to improve branch prediction efficiency of a computer used to execute the computer program after the basic blocks have been sequenced by the sequencer.

16. The sequencer of claim 14 further comprising:

computer instructions which are executed to insert trace computer instructions into the computer program, the trace computer instructions performing write operations to computer memory which creates the trace data file.

17. The sequencer of claim 14 further comprising:

computer instructions which are executed to construct a directed graph of nodes and edges wherein each node represents a basic block of the computer program and wherein each edge between two nodes of the basic block contain the correlation information pertaining to the sequences of M basic blocks.

18. A data processing system comprising:

a central processing unit (CPU);

computer memory coupled to the central processing unit comprising;

computer instructions for initiating execution of a computer program stored in computer memory, the execution being performed by reading computer instructions which form basic blocks of computer code from computer memory and executing the computer instructions via the central processing unit (CPU);

computer instructions for storing, in the computer memory while the execution is being performed, a trace data file which indicates an execution order of the basic blocks, the execution order indicating when in time any basic block is executed with respect to other basic blocks in the computer program, the execution order having a beginning and an end;

computer instructions for iteratively choosing different sequences of M basic blocks from the trace data file to form selected groups of basic blocks, M being a finite positive integer greater than two, and for each of the M basic blocks in each selected group accumulating in memory for each selected group, correlation information between each unique pair of the M basic blocks located within each selected group so that some basic blocks that do not lie directly adjacent each other in the trace data file are correlated to each other; and

computer instructions for using the correlation information to sequence the basic blocks of the computer program in an execution order for execution by a computer.

19. A data processing system comprising:

means for initiating execution of a computer program stored in computer memory, the execution being performed by reading computer instructions which form basic blocks of computer code from computer memory and executing the computer instructions via a central processing unit (CPU);

means for storing a trace data file in the computer memory while execution is being performed by the means for executing, the trace data file indicating an execution order of the basic blocks, the execution order indicating when in time any basic block is executed with respect to other basic blocks in the computer program, the execution order having a beginning and an end;

means for iteratively choosing different sequences of M basic blocks from the trace data file to form selected groups of basic blocks, M being a finite positive integer greater than two, and for each of the M basic blocks in each selected group accumulating, in memory for each selected group, correlation information between each unique pair of the M basic blocks located within each selected group so that some basic blocks that do not lie directly adjacent each other in the trace data file are correlated to each other; and

means for using the correlation information to sequence the basic blocks of the computer program in an execution order for execution by a computer.

20. A method for sequencing executable code and mass manufacturing the executable code onto computer readable media to improve computer performance, the method comprising the steps of:

initiating execution of a computer program stored in computer memory, the execution being performed by reading computer instructions which form basic blocks of computer code from computer memory and executing the computer instructions via a central processing unit (CPU);

storing, in the computer memory while the execution is being performed, a trace data file which indicates an execution order of the basic blocks, the execution order indicating when in time any basic block is executed with respect to other basic blocks in the computer program, the execution order having a beginning and an end;

iteratively choosing different sequences of M basic blocks from the trace data file to form selected groups of basic blocks, M being a finite positive integer greater than two, and for each of the M basic blocks in each selected group accumulating, in memory for each selected group, correlation information between each unique pair of two of the M basic blocks located within each selected group so that each selected group of basic blocks produces a plurality of correlation changes within the correlation information;

using the correlation information to sequence the basic blocks of the computer program to form an executable sequenced computer program; and

embodying the executable sequenced computer program on one or more computer readable media for execution by a computer.

21. The method of claim 20 wherein the one or more computer readable media is a media selected from the group consisting of:

read only memory (ROM), electrically erasable memory (EPROM, EEPROM, flash), random access memory (RAM), compact disks (CDs), magnetic disks, and computer tape storage.

22. A method for sequencing computer instructions for execution in a data processing system, the method comprising the steps of:

(a) providing, within a memory, a computer program containing basic blocks wherein each basic block contains at least one computer instruction;

(b) executing the computer program by reading the basic blocks from memory and executing the basic blocks via a central processing unit (CPU);

(c) storing, in the memory during the step of executing, a trace data file which indicates an execution order of the basic blocks, the execution order indicating when in time any basic block is executed with respect to other basic blocks, the execution order having a beginning and an end;

(d) selecting a sequence of M basic blocks from the trace data file to form a selected group, M being a finite positive integer greater than two;

(e) accumulating, in memory for the selected group, correlation information pertaining to the sequence of M basic blocks from the trace data file;

(f) selecting a different sequence of M basic blocks as the selected group;

(g) repeating steps (e) through (g) until a selected number of sequences of M basic blocks in the trace data file are processed; and

(h) using the correlation information obtained via steps (e) through (g) to order the basic blocks for subsequent execution by selectively arranging the correlation information into at least one matrix (Wij), which has rows and columns, and analyzing the at least one matrix using matrix operations to determine an ordering of the basic blocks.

23. The method of claim 22 wherein step (h) further comprises:

constructing a matrix (Wij) wherein prior-analyzed basic blocks in a directed control flow graph formed from the correlation information create a first dimension (k) of the matrix and candidate basic blocks in the directed control flow graph which are being analyzed for insertion into a reordered instruction file form a second dimension (n) of the matrix, so that the matrix is either nxk or kxn in dimension.

24. The method of claim 23 wherein step (h) further comprises:

summing all correlation information along from 1 to n for each row of the matrix (Wij), these sums being referred to a sum for each row.

25. The method of claim 24 wherein step (h) further comprises:

dividing each correlation value in each row of the matrix by the sum of that row to get a divided value and subtracting 1/n from each divided value to form a nxk or kxn transformed matrix (Pij).

26. The method of claim 25 wherein step (h) further comprises:

multiplying each entry each row of the matrix (Pij) by the maximum value in that row of the matrix (Wij) to obtain rank values; and

summing all of the values in the columns of the (Pij) matrix to arrive at n rank factors.

27. The method of claim 26 wherein step (h) further comprises:

using the n rank factors to determine which of the n candidate basic blocks should next be inserted into the reordered instruction file.

28. The method of claim 22 wherein step (h) further comprises:

constructing a matrix wherein prior-analyzed basic blocks in a directed control flow graph formed from the correlation information create a first dimension (k) of the matrix and candidate basic blocks in the directed control flow graph which are being analyzed for insertion into a reordered instruction file form a second dimension (n) of the matrix, so that the matrix is either nxk or kxn in dimension.

29. The method of claim 28 wherein step (h) further comprises:

summing all correlation information along from 1 to n for each column of the matrix, these sums being referred to the sum for each column.

30. The method of claim 29 wherein step (h) further comprises:

dividing each correlation value in each column of the matrix by the sum of that column to get a divided value and subtracting 1/n from each divided value to form a nxk or kxn transformed matrix (Pij).

31. The method of claim 30 wherein step (h) further comprises:

multiplying each entry each column of the matrix (Pij) by the maximum value in that column of the matrix (Wij) to obtain rank values; and

summing all of the values in the rows of the (Pij) matrix to arrive at n rank factors.

32. The method of claim 31 wherein step (h) further comprises:

using the n rank factors to determine which of the n candidate basic blocks should next be inserted into the reordered instruction file.

33. The method of claim 22 wherein step (e) processes information from step (c) periodically as the trace data file is being created so that a largest size of the trace data file in memory at any one time is reduced.