 |
 |
|
|
|
|
Title: |
US6112299:
Method and apparatus to select the next instruction in a superscalar or a very long instruction word computer having N-way branching
[ Derwent Title ]

|
Country: |
US United States of America

|
| |
Inventor: |
Ebcioglu, Kemal; Somers, NY
Kiefer, Kenneth J.; Rochester, MN
Luick, David Arnold; Rochester, MN
Silberman, Gabriel Mauricio; Millwood, NY
Winterfield, Philip Braun; Rochester, MN

|
Assignee: |
International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company

|
Published / Filed: |
2000-08-29
/ 1997-12-31

|
Application Number: |
US1997000001527

|
IPC Code: |
Advanced:
G06F 9/32;
G06F 9/38;
G06F 12/08;
Core:
more...
IPC-7:
G06F 9/38;

|
ECLA Code: |
G06F9/32B4; G06F9/38E2; G06F9/38F; G06F9/38F2; G06F9/38T;

|
U.S. Class: |
Current:
712/236;
711/127;
712/024;
712/E09.05;
712/E09.055;
712/E09.056;
712/E09.071;
712/E09.077;
Original:
712/236;
712/024;
711/127;

|
Field of Search: |
712/236,24
711/127

|
Priority Number: |
| 1997-12-31 |
US1997000001527 |

|
Abstract: |
In a computer capable of executing a superscalar and a very long instruction word instruction wherein the computer has compiled a number of primitive operations that can be executed in parallel into a single instruction having multiple parcels and each of the parcels correspond to an operation, the invention is an improved instruction cache to store all potential subsequent instructions and a method to select the subsequent instruction when several possible branches of execution are probable and must be evaluated. All branch conditions and all addresses of potential subsequent instructions of an instruction are replicated and stored in the instruction cache. All potential subsequent instructions are stored in the same block of the instruction cache having the same next address; individual instructions are identified by the replicated offset addresses. Further the instruction cache is divided into minicaches, each minicache to store one parcel, which allows rapid autonomous execution of each parcel. Simultaneously, all branch conditions are evaluated in parallel to determine the next instruction and all offset addresses are decoded in parallel. Only after the control flow or the branch taken, or the subsequent or next instruction is determined, are the results of that branch stored and the decoded addresses are used to late select the next instruction from the instruction cache.

|
Attorney, Agent or Firm: |
Ojanen, Karuna ;

|
Primary / Asst. Examiners: |
Treat, William M.;

|
Maintenance Status: |
E2 Expired Check current status

|
INPADOC Legal Status: |
Show legal status actions
Family Legal Status Report

|
Parent Case: |
This application is related to following co-pending applications: U.S. Pat. No. 5,805,850, filed Jan. 30, 1997 entitled Very Long Instruction Word (VLIW) Computer Having Efficient Instruction Code Format; U.S. Pat. No. 5,793,944, filed Sep. 13, 1996 entitled System for Restoring Register Data in a Pipelined Data Processing System Using Register File Save/Restore Mechanism; U.S. Pat. No. 5,875,346 filed Sep. 13, 1996 entitled System For Restoring Register Data in a Pipelined Data Processing System Using Latch Feedback Assemblies; U.S. Pat. No. 5,924,117, filed Dec. 16, 1996 entitled Multiported and Interleaved Cache Memory; U.S. Pat. No. 5,890,009, filed Dec. 12, 1996 entitled VLIW Architecture and Method for Expanding a Parcel. All of the above applications are assigned to the assignee herein and all of the above applications are herein incorporated by reference.

|
Designated Country: |
AT BE CH CY DE DK ES FI FR GB GR IE IT LI LU MC NL PT SE CA CN CZ EP HU IL JP KR PL RU

|
Family: |
Show 6 known family members

|
First Claim:
Show all 17 claims |
What is claimed is:
1. A method of digital computing, comprising:
- (a) replicating all target addresses and all branch conditions contained within all branch parcels of an instruction having multiple parcels, some parcels being the branch parcels and some parcels being operational parcels, all parcels capable of independent execution in a processor;
- (b) loading the instruction having multiple parcels with the replicated target addresses and branch conditions into an instruction cache;
- (c) selecting the instruction for execution;
- (d) executing the operational parcels in a plurality of execution units of the processor, each execution unit dedicated to a respective each one of the parcels;
- (e) simultaneously evaluating all branch conditions of all branch parcels of the instruction to determine a control flow branch taken;
- (f) simultaneously decoding all target addresses of the instruction with decode logic circuits;
- (g) correlating one each of the evaluated branch conditions to one each of the decoded target addresses, and to the execution results of the operational parcels, and, as a result,
- (h) selecting the control flow branch taken for execution;
- (i) storing the execution results of the control flow branch taken; and
- (j) selecting a next instruction of the control flow branch taken for execution.

|
Background / Summary: |
Show background / summary

|
Drawing Descriptions: |
Show drawing descriptions

|
Description: |
Show description

|
Forward References: |
Show 12 U.S. patent(s) that reference this one

|
 |
 |
|
|
|
|
Foreign References: |

|
Other Abstract Info: |
DERABS G1999-396808

|
Other References: |
IBM Research Report, RC 13795 (#59501), Nov. 23, 1987, "Some Design Ideas for a VLIW Architecture for Sequential-Natured Software" by Kemal Ebcioglu.
IEEE Computer, Jun. 1993, pp. 39-56, "An Architectural Framework for Supporting Heterogeneous Instruction-Set Architectures" by Gabriel M. Silberman and Kemal Ebcioglu.
(18 pages)
Cited by 18 patents
[ISI abstract]
IEEE Comp-Con 84 Proceedings, pp. 299-305, "VLIW Machines: Multiprocessors We Can Actually Program" by Joseph A. Fisher and John J. O'Donnell.
IEEE Proceedings of the 10th Symposium on Computer Architectures, pp. 140-150, Jun. 1983, "Very Long Instruction Word Architectures and the ELI-512" by Joseph A. Fisher.
IEEE CS Press, Los Alamitos, Calif., Order No. 805, 1987, pp. 180-192, "A VLIW Architecture for a Tarce Scheduling Compiler" by Robert P. Colwell et al.
IEEE Proceedings of the 26th Annual International Symposium on Microarchitecture, 1993, pp. 193-201, "MIDEE: Smoothing Branch and Instruction Cache Miss Penalties on Deep Pipelines" by Nathalie Drach and Andre Seznec.
IEEE Proceedings of the 1993 International Conference on Computer Design: VLSI Press, pp. 126-131, "Speculative Computation for Coprocessor Synthesis" by Ulrich Holtmann and Rolf Ernst.
IEEE Transactions on Parallel and Distributed Systems, vol. 6, No. 8, Aug. 1993, pp. 850-862, "Generalized Multiway Branch Unit for VLIW Microprocessors" by Soo-Mook Moon and Scott D. Carson.
IEEE Proceedings of the 28th Annual International Symposium on Microarchitecture, 1995, pp. 303-312, "Partitioned Register File for TTAs" by Johan Janssen and Henk Corporaal.
IEEE Proceedings of the 29th Annual Simulation Symposium, 1996, pp. 221-232, "Architectural Simulation System for M.f.a.s.t." by C.H.L. Moller and G.G. Pechanek.
Computer Architecture News, vol. 18, No. 4, pp. 35-51, Dec. 1990, "The Effect of Employing Advanced Branching Mechanisms in Supescalar Processors" by Yen-Jen Oyang et al.
Proceedings of the 1995 International Conference on Parallel Processing, Aug. 1995, pp. 215-218, "Profile-Guided Multi-Heuristic Branch Prediction" by Pohua Chang and Utpal Banerjee.
J. Korean Inst. Telemat. Electron. (South Korea), vol. 30B, No. 11, pp. 11-16, Nov. 1993, entitled "A Software and Hardware Scheme for Reducing the Branch Penalty in Parallel Computers" by Chan Sook Ham et al.
Microprocessing and Microprogramming, vol. 36, No. 5, Oct. 1993, pp. 259-278, entitled "ALU Design and Processor Branch Architecture" by Gordon B. Steven et al.
(20 pages)
Cited by 4 patents
[ISI abstract]
International Journal of Parallel Programming, vol. 23, No. 3, Jun. 1995, pp. 221-243, entitled "Enhancing Instruction Scheduling With a Block-Structured ISA" by Stephen Melvin et al.
(23 pages)
[ISI abstract]
Technical Report of IEICE, VLD96-77, CPSY96-89 (Dec. 1996), pp. 95-102, "Program Optimization on Instruction Cache at Runtime" by Toshitaka Miura and Yoichi Muraoka.
Technical Report, School of Science and Engineering, Waseda University, CPSY90-53, pp. 91-96, "A Fine Grained Parallel Architecture for Effective Execution of Conditional Structure" by Eishun Suzuki et al.

|


|
Nominate this for the Gallery...

|
|