Electrical computers and digital processing systems: processing – Architecture based instruction processing
Reexamination Certificate
2000-09-28
2004-09-28
Tsai, Henry W. H. (Department: 2183)
Electrical computers and digital processing systems: processing
Architecture based instruction processing
C712S024000
Reexamination Certificate
active
06799262
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention is directed to an apparatus and method for rapidly creating instruction groups for explicitly parallel architectures. More particularly, the present invention is directed to an apparatus and method for creating instruction groups for the IA64 architecture.
2. Description of Related Art
Explicitly parallel architectures, such as IA64, require the compiler (or assembler programmer) tog identify instructions that can be run safely in parallel. A group of such instructions is called an instruction group. IA64 allows instruction groups of arbitrary size and theoretically all instructions within the group could be executed concurrently. However, any given implementation of the architecture, e.g., Itanium, has resource restrictions that limit the number and types of instructions that can be executed in parallel. Such restrictions include the number and type of execution units and the number of instruction packages (bundles) that can be dispatched concurrently.
For static compilers, long compile times are undesirable but minimizing compile time usually is not of paramount importance. However, dynamic or Just-In-Time compilers may become unusable if their compile times are elongated. Because the compilation typically occurs during the invocation of a method/function, compile time becomes a direct component of response time.
Thus, it would be beneficial to have an apparatus and method for quickly creating instruction groups that will maximize instruction level parallelism for any given implementation of an explicitly parallel architecture, and in particular IA64 architectures.
SUMMARY OF THE INVENTION
The present invention provides a mechanism by which instruction groups may be rapidly formed during the compilation of a computer program. With the present invention, it is assumed that a previous compilation phase has generated a stream of intermediate instructions that represents instructions that are arranged in natural program order. The intermediate instructions identify the instruction type and identify all sources and target registers. Additionally, each instruction has a “hoist” field that is initialized to zero.
With the present invention, prior to performing the instruction group creation, the apparatus and method of the present invention gathers information about the underlying architecture for use in the instruction group creation phase. The information gathered includes the number of each type of execution unit available and the number of bundles that can be dispatched concurrently by the architecture.
The instruction group creation of the present invention includes three phases: a first phase for performing initial grouping, a second phase for hosting instructions from further down in the program instruction order if the instruction is not able to be added during the initial grouping phase, and a third optional phase for counting the number of bundles formed to thereby inform a Just-In-Time compiler of the amount of space need to be allocated in a code buffer. Other features and advantages of the present invention will be described in, or will become apparent in view of, the following detailed description of the preferred embodiments.
REFERENCES:
patent: 4435753 (1984-03-01), Rizzi
patent: 4642764 (1987-02-01), Auslander et al.
patent: 4782444 (1988-11-01), Munshi et al.
patent: 4833599 (1989-05-01), Colwell et al.
patent: 4961141 (1990-10-01), Hopkins et al.
patent: 5057837 (1991-10-01), Colwell et al.
patent: 5448746 (1995-09-01), Eickemeyer et al.
patent: 5497499 (1996-03-01), Garg et al.
patent: 5502827 (1996-03-01), Yoshida
patent: 5504932 (1996-04-01), Vassiliadis et al.
patent: 5574928 (1996-11-01), White et al.
patent: 5600810 (1997-02-01), Ohkami
patent: 5613121 (1997-03-01), Blainey
patent: 5627981 (1997-05-01), Adler et al.
patent: 5628016 (1997-05-01), Kukol
patent: 5634023 (1997-05-01), Adler et al.
patent: 5669001 (1997-09-01), Moreno
patent: 5748936 (1998-05-01), Karp et al.
patent: 5761470 (1998-06-01), Yoshida
patent: 5768510 (1998-06-01), Gish
patent: 5778219 (1998-07-01), Amerson et al.
patent: 5812850 (1998-09-01), Wimble
patent: 5819058 (1998-10-01), Miller et al.
patent: 5826054 (1998-10-01), Jacobs et al.
patent: 5828886 (1998-10-01), Hayashi
patent: 5848246 (1998-12-01), Gish
patent: 5922065 (1999-07-01), Hull et al.
patent: 5966537 (1999-10-01), Ravichandran
patent: 6018799 (2000-01-01), Wallace et al.
patent: 6035120 (2000-03-01), Ravichandran
patent: 6041399 (2000-03-01), Terada et al.
patent: 6061781 (2000-05-01), Jain et al.
patent: 6101592 (2000-08-01), Pechanek et al.
patent: 6108771 (2000-08-01), Gaertner et al.
patent: 6110226 (2000-08-01), Bothner
patent: 6151703 (2000-11-01), Crelier
patent: 6158048 (2000-12-01), Lueh et al.
patent: 6237077 (2001-05-01), Sharangpani et al.
patent: 6240510 (2001-05-01), Yeh et al.
patent: 6286135 (2001-09-01), Santhanam
patent: 6286346 (2001-09-01), Hocken, Jr. et al.
patent: 6301705 (2001-10-01), Doshi et al.
patent: 6311325 (2001-10-01), Levine et al.
patent: 6317872 (2001-11-01), Gee et al.
patent: 6317876 (2001-11-01), Kunz et al.
patent: 6321322 (2001-11-01), Pechanek et al.
patent: 6324687 (2001-11-01), Beadle et al.
patent: 6336213 (2002-01-01), Beadle et al.
patent: 6339841 (2002-01-01), Merrick et al.
patent: 6385660 (2002-05-01), Griesemer et al.
patent: 6408433 (2002-06-01), Click, Jr. et al.
patent: 6412105 (2002-06-01), Maslennikov et al.
patent: 6427234 (2002-07-01), Chambers et al.
patent: 6442676 (2002-08-01), Guenthner
patent: 6446195 (2002-09-01), Ganapathy et al.
patent: 6466972 (2002-10-01), Paul et al.
patent: 6487601 (2002-11-01), Hubacher et al.
patent: 6507946 (2003-01-01), Alexander, III et al.
patent: 6513109 (2003-01-01), Gschwind et al.
patent: 6539473 (2003-03-01), Hubacher et al.
patent: 6560624 (2003-05-01), Otani et al.
patent: 6567974 (2003-05-01), Czajkowski
patent: 6571385 (2003-05-01), Muthukumar et al.
patent: 6604167 (2003-08-01), Blandy et al.
patent: 6615403 (2003-09-01), Muthukumar et al.
patent: 6622234 (2003-09-01), Pechanek et al.
patent: 6622238 (2003-09-01), Benjamin et al.
patent: 6640313 (2003-10-01), Quach
patent: 6640315 (2003-10-01), Hwu et al.
patent: 6675375 (2004-01-01), Czajkowski
Fitzgerald et al., “Marmot: An Optimizing Compiler for Java”, Microsoft Research, Jun. 16, 1999, Technical Report MSR-TR-99-33, pp. 1-29.
Azevedo et al., “Java Annotation-Aware Just-In-Time (AJIT) Compilation System”, ACM 1999, San Francisco, CA, USA, pp. 142-151.
Larus et al., “SPIM S20: A MIPS R2000 Simulator”, Computer Sciences Department, University of Wisconsin, Madison, copyright 1990-1997, pp. 1-25.
Aho et al., “Compilers: Principles, Techniques, and Tools”, copyright 1986, Bell Telephone Labs, Inc., 4 pages.
Sinclair et al., “ASIC Design for Conditional Nested Loops with Predicate Registers”, Aug. 11, 1999, Circuits and Systems, 1999, 42ndMidwest Symposium, vol. 2, pp. 874-877.
“The Java Virtual Machine Specification”, Sun Microsystems, Inc., copyright 1997, http://www.java.sun.com/docs/books/vmspec/html/Instructions2.doc14.html.
Fernandez, “Simple and Effective Link-Time Optimization of Modula-3 Programs”, Nov. 7, 1994, pp. 1-7.
Ishizaki et al., Design, Implementation, and Evaluation of Optimizations in a Just-In-Time Compiler, ACM, Jun. 1999, pp. 119-122.
Blandy Geoffrey Owen
Johnson Andrew
Shi Danling
Emile Volel
International Business Machines - Corporation
Tsai Henry W. H.
Walder, Jr. Stephen J.
Yee Duke W.
LandOfFree
Apparatus and method for creating instruction groups for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for creating instruction groups for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for creating instruction groups for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3215630