Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-12-24
2002-06-25
Chaki, Kakali (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000
Reexamination Certificate
active
06412105
ABSTRACT:
I. FIELD OF THE INVENTION
The present invention relates to processors and computing devices and more particularly to compiler techniques for optimizing multi-way decision statements and belonging to a set conditions.
II. BACKGROUND OF THE INVENTION
Many practical applications require processing of very large amounts of information in a short period of time. One of the basic approaches to minimizing the time to perform such computations is to apply some sort of parallelism, so that tasks which are logically independent can be performed in parallel. This can be done, for example, by executing two or more instructions per machine cycle, i.e., by means of instruction-level parallelism. Thus, in a class of computers using superscalar processing, hardware is used to detect independent instructions and execute them in parallel, often using techniques developed in the early supercomputers.
Another approach to exploiting instruction level parallelism is used by the Very Long Instruction Word (VLIW) processor architectures in which the compiler performs most instruction scheduling and parallel dispatching at compile time, reducing the operating burden at run time. By moving the scheduling tasks to the compiler, a VLIW processor avoids both the operating latency problems and the large and complex circuitry associated with on-chip instruction scheduling logic. Both superscalar and VLIW processors take advantage of techniques know as pipelining for instruction scheduling optimization.
As known, each VLIW instruction includes multiple independent operations for execution by the processor in a single cycle. A VLIW compiler processes these instructions according to precise conformance to the structure of the processor, including the number and type of the execution units, as well as execution unit timing and latencies. The compiler groups the operations into a wide instruction for execution in one cycle. At run time, the wide instruction is applied to the various execution units with little decoding. The execution units in a VLIW processor typically include arithmetic units such as floating point arithmetic units. An example of a VLIW processor that includes floating point execution units is described by R. K. Montoye, et al. in “Design of the IBM RISC System/6000 floating point execution unit”, IBM J.Res. Develop., V. 43 No.1, pp. 61-62, January 1990. Additional examples are provided in U.S. Pat. No. 5,418,975 incorporated herein by reference.
Predicated and speculative computations are employed in VLIW processing as known in the art, see e.g.,
Parallel and Distributed Computing Handbook,
Albert Y. Zomaya, Editor, McGraw-Hill 1996, chapter 21, Superscalar and VLIW Processors, pp. 621-647, incorporated herein by reference. The results of speculatively executed instructions may be retired or discarded.
It is also known that profile data that characterizes program behavior can be obtained by performing test runs of the program. Such a technique is employed, for example, for profiled branch prediction.
Redundant speculative calculations may reduce effectiveness of software pipelining. Such calculations may occur during compilation of multi-way branch statements for VLIW pipelining. In general, multi-way branch statements can be expresses in the C language (used throughout this specification) as follows:
if (expression)
statement(s)
else if (expression)
statement(s)
else if (expression)
statement(s)
else
statement(s)
A “switch” statement is a multi-way decision statement that tests whether an expression matches one of a number of constant values. For example, in C, the switch statement is expressed as follows:
switch (expression)
case const
—
1:
statement(s)
case const
—
2:
case const
—
3:
.
.
.
case const_m:
statement(s)
case const_n:
statements(s)
default:
statement(s)
This multi-way branch in the switch statement is a barrier to flow transformations aimed at efficient use of hardware for predicated and speculative calculations. Implementation of the entire switch statement by constructing a set of conditionals, which are subsequently transformed to the predicated form, may lead to redundant speculative calculations.
Accordingly multi-way decisions, such as in the switch statements, require efficient compilation for software pipelining. Thus, it is desirable to improve compilation of multi-way brunch statements, and in particular switch statements, so as to reduce redundant speculative computations.
III. SUMMARY OF THE INVENTION
Computer method of compiling a multi-way decision statement for VLIW processing is described. The method comprises: (a) generating profile data for a multi-way decision statement, such as a switch statement; identifying at least one most probable alternative of the multi-way decision and a set of constants associated with the identified alternative using the profile data; determining a probable subset of the identified constants based on the profile data; constructing a conditional statement for the identified alternative using the probable subset of constants; and moving out the identified at least one alternative from the multi-way decision statement.
The condition for the alternative that has been moved out of the multi-way decision (e.g., case statement) is constructed using the probable subset of constants so as to form the condition such as illustrated below.
int x; const int c
1
, c
2
, . . . , cN;
if (x==c
1
¦¦ x==c
2
¦¦ . . . ¦¦ x==cN) (1)
This condition is then transformed as follows:
If (cmax−cmin)<wint (wint is width in bits of integers used in this condition; cmin=min(c
1
, c
2
, . . . , cN); cmax=max(c
1
, c
2
, . . . , cN)), then the conditional statement (1) is equivalent to:
if (x<wint && (1<<(x−cmin) & cmask) !=0), (2)
where cmask=(1<<(c
1
−cmin)¦ . . . ¦ 1<<(cN−cmin)) is a constant bit mask.
If cmax<wint expression (2) is simplified as follows:
if (x<wint && (1<<x & cmask
2
) !=0), (3)
where cmask
2
=(1<<c
1
¦ . . . ¦
1 <<cN)
Expression (3) is further simplified as follows if cmax<wint and x<wint:
if ((1<<x & cmask
2
) !=0)
IV. BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1
illustrates a high level flowchart of compilation of the switch statement.
REFERENCES:
patent: 5339420 (1994-08-01), Hoxey
patent: 5742803 (1998-04-01), Igarashi et al.
patent: 5805893 (1998-09-01), Sproul et al.
patent: 5857104 (1999-01-01), Natarjan et al.
patent: 5878261 (1999-03-01), Holler et al.
patent: 6006033 (1999-12-01), Heisch
patent: 6035122 (2000-03-01), Ando
patent: 6049669 (2000-04-01), Holler
patent: 6115809 (2000-09-01), Mattson, Jr. et al.
Nakatani et al., “Using a lookahead window in a compaction-based parallelizing compiler”, IEEE, 1994, pp. 57-68.*
Fisher et al., “Pedicting conditional branch directions from previous runs of a program”, ASPLOS, ACM, 1992, pp. 85-95.*
Karplus et al., “Efficient hardware for multi-way jumps and pre-fetches”, ACM, 1985, pp. 11-18.*
Aho, Alfred V., et al.,Compilers: Principles, Techniques, and Tools, 1998, pp. 497-500.
Kasinsky Alexander I.
Maslennikov Dmitry M.
Tikhonov Valentine G.
Volkonsky Vladimir Y.
Chaki Kakali
Elbrus International Limited
Townsend and Townsend / and Crew LLP
LandOfFree
Computer method and apparatus for compilation of multi-way... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer method and apparatus for compilation of multi-way..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer method and apparatus for compilation of multi-way... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2947026