Work Files Saved Searches
   My Account                                                  Search:   Quick/Number   Boolean   Advanced   Derwent    Help   


 The Delphion Integrated View

  Buy Now:   Buy PDF- 29pp  PDF  |   File History  |   Other choices   
  Tools:  Citation Link  |  Add to Work File:    
  View:  Expand Details   |  INPADOC   |  Jump to: 
  Go to:  Derwent  
 Email this to a friend  Email this to a friend 
       
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

View Images High
Resolution

 Low
 Resolution

 
29 pages

 
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          Buy Now: 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

       
U.S. References: Go to Result Set: All U.S. references   |  Forward references (12)   |   Backward references (26)   |   Citation Link

Buy
PDF
Patent  Pub.Date  Inventor Assignee   Title
Buy PDF- 43pp US4295193  1981-10 Pomcrene  International Business Machines Corporation Machine for multiple instruction execution
Buy PDF- 9pp US4777587  1988-10 Case et al.  Advanced Micro Devices, Inc. System for processing single-cycle branch instruction in a pipeline having relative, absolute, indirect and trap addresses
Buy PDF- 36pp US4833599  1989-05 Colwell et al.  Multiflow Computer, Inc. Hierarchical priority branch handling for parallel execution in a parallel processor
Buy PDF- 11pp US5127092  1992-06 Gupta et al.  North American Philips Corp. Apparatus and method for collective branching in a multiple instruction stream multiprocessor where any of the parallel processors is scheduled to evaluate the branching condition
Buy PDF- 7pp US5301340  1994-04 Cook  International Business Machines Corporation IC chips including ALUs and identical register files whereby a number of ALUs directly and concurrently write results to every register file per cycle
Buy PDF- 11pp US5317703  1994-05 Hiraoka et al.  Hitachi, Ltd. Information processing apparatus using an advanced pipeline control method
Buy PDF- 20pp US5333280  1994-07 Ishikawa et al.  NEC Corporation Parallel pipelined instruction processing system for very long instruction word
Buy PDF- 9pp US5333283  1994-07 Emma et al.  International Business Machines Corporation Case block table for predicting the outcome of blocks of conditional branches having a common operand
Buy PDF- 12pp US5381533  1995-01 Peleg et al.  Intel Corporation Dynamic flow instruction cache memory organized around trace segments independent of virtual address line
Buy PDF- 24pp US5396640  1995-03 Ikenaga et al.  Mitsubishi Denki Kabushiki Kaisha Boosting method and apparatus in a parallel computer
Buy PDF- 17pp US5404469  1995-04 Chung et al.  Industrial Technology Research Institute Multi-threaded microprocessor architecture utilizing static interleaving
Buy PDF- 14pp US5442760  1995-08 Rustad et al.  Dolphin Interconnect Solutions AS Decoded instruction cache architecture with each instruction field in multiple-instruction cache line directly connected to specific functional unit
Buy PDF- 14pp US5442762  1995-08 Kato et al.  Fujitsu Limited Instructing method and execution system for instructions including plural instruction codes
Buy PDF- 14pp US5450556  1995-09 Slavenburg et al.  North American Philips Corporation VLIW processor which uses path information generated by a branch control unit to inhibit operations which are not on a correct path
Buy PDF- 18pp US5450557  1995-09 Kopp et al.  Loral Aerospace Corp. Single-chip self-configurable parallel processor
Buy PDF- 130pp US5471593  1995-11 Branigin   Computer processor with an efficient means of executing many instructions simultaneously
Buy PDF- 9pp US5481736  1996-01 Schwartz et al.  Hughes Aircraft Company Computer processing element having first and second functional units accessing shared memory output port on prioritized basis
Buy PDF- 16pp US5485629  1996-01 Dulong  Intel Corporation Method and apparatus for executing control flow instructions in a control flow pipeline in parallel with arithmetic instructions being executed in arithmetic pipelines
Buy PDF- 30pp US5500942  1996-03 Eickemeyer et al.  International Business Machines Corporation Method of indicating parallel execution compoundability of scalar instructions based on analysis of presumed instructions
Buy PDF- 30pp US5502826  1996-03 Vassiliadis et al.  International Business Machines Corporation System and method for obtaining parallel existing instructions in a particular data processing configuration by compounding instructions
Buy PDF- 133pp US5509129  1996-04 Guttag et al.   Long instruction word controlling plural independent processor operations
Buy PDF- 39pp US5511172  1996-04 Kimura et al.  Matsushita Electric Co. Ind, Ltd. Speculative execution processor
Buy PDF- 10pp US5513363  1996-04 Kumar et al.  Hewlett-Packard Company Scalable register file organization for a computer architecture having multiple functional units or a large register file
Buy PDF- 7pp US5517442  1996-05 Kirihata et al.  International Business Machines Corporation Random access memory and an improved bus arrangement therefor
Buy PDF- 46pp US5517628  1996-05 Morrison et al.  Biax Corporation Computer with instructions that use an address field to select among multiple condition code registers
Buy PDF- 17pp US5574939  1996-11 Keckler et al.  Massachusetts Institute of Technology Multiprocessor coupling system with integrated compile and run time scheduling for parallelism
       
Foreign References:
Buy
PDF
Publication Date IPC Code Assignee   Title
Buy PDF- 12pp EP0496407 1992-07  G06F 9/38 NEC CORPORATION Parallel pipelined instruction processing system for very long instructionword 
Buy PDF- 16pp EP0592125 1994-04  G06F 9/38 International Business Machines Corporation Method and system for reduced run-time delay during conditional branch execution in pipelined processor systems 
Buy PDF- 25pp EP0770955 1997-05  G06F 9/38 SGS-THOMSON MICROELECTRONICS LTD. Cache memory 
  JP49083342 1974-08       
  JP01214981 1989-08       
  JP02077940 1990-03       
  JP04239324 1992-08  G06F 9/38    
  JP06139075 1994-05       
  JP06208463 1994-07  G06F 9/38    
  JP07084797 1995-03       
  JP07182169 1995-07       
  JP07281896 1995-10       
  JP08063357 1996-03       
  JP08249180 1996-09  G06F 9/38    
Buy PDF- 49pp WO9427216 1994-11  G06F 9/30 MASSACHUSETTS INST TECHNOLOGY MULTIPROCESSOR COUPLING SYSTEM WITH INTEGRATED COMPILE AND RUN TIME SCHEDULING FOR PARALLELISM 
Buy PDF- 73pp WO9629645 1996-09  G06F 9/38 IBM DEUTSCHLAND GMBH OBJECT-CODE COMPATIBLE REPRESENTATION OF VERY LONG INSTRUCTION WORD PROGRAMS 


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.


  • Inquire Regarding Licensing

    Powered by Verity


    Plaques from Patent Awards      Gallery of Obscure PatentsNominate this for the Gallery...

    Thomson Reuters Copyright © 1997-2010 Thomson Reuters 
    Subscriptions  |  Web Seminars  |  Privacy  |  Terms & Conditions  |  Site Map  |  Contact Us  |  Help