Source: http://www.google.com/patents/US5915110?dq=6,907,387
Timestamp: 2014-07-23 06:18:07
Document Index: 364677855

Matched Legal Cases: ['Application No. 08', 'Application No. 08', 'Application No. 08', 'Application No. 08', 'Application No. 08', 'Application No. 09']

Patent US5915110 - Branch misprediction recovery in a reorder buffer having a future file - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign in<nobr>Advanced Patent Search</nobr>PatentsA reorder buffer for a microprocessor comprising a control unit, an instruction storage, and future file. The future file has storage locations associated with each register implemented in the microprocessor. The future file is configured to store a reorder buffer tag that corresponds to the last instruction,...http://www.google.com/patents/US5915110?utm_source=gb-gplus-sharePatent US5915110 - Branch misprediction recovery in a reorder buffer having a future fileAdvanced Patent SearchPublication numberUS5915110 APublication typeGrantApplication numberUS 08/975,011Publication dateJun 22, 1999Filing dateNov 20, 1997Priority dateJul 26, 1996Fee statusPaidPublication number08975011, 975011, US 5915110 A, US 5915110A, US-A-5915110, US5915110 A, US5915110AInventorsDavid B. Witt, Thang M. TranOriginal AssigneeAdvanced Micro Devices, Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (37), Non-Patent Citations (26), Referenced by (9), Classifications (18), Legal Events (4) External Links: USPTO, USPTO Assignment, EspacenetBranch misprediction recovery in a reorder buffer having a future fileUS 5915110 AAbstract A reorder buffer for a microprocessor comprising a control unit, an instruction storage, and future file. The future file has storage locations associated with each register implemented in the microprocessor. The future file is configured to store a reorder buffer tag that corresponds to the last instruction, in program order, stored within the instruction storage that has a destination operand corresponding to the register associated with said storage location. The future file is further configured to store instruction results. The control unit is configured to read a particular reorder buffer tag from the future file that corresponds to a completed instruction and to compare the particular reorder buffer tag with the completed instruction's result tag. If the two tags compare equal, the control unit is configured to write any result data corresponding to the completed instruction into the future file. This advantageously reduces the number of comparators needed to maintain the future file. The future file is also configured to improve branch misprediction recovery speed by examining each entry in said instruction storage for a valid destination starting with the mispredicted branch instruction. This configuration advantageously allows older instructions in the instruction storage to be retired while the future file is being recovered, thereby reducing the number of instructions the control unit must process to recover the future file.
What is claimed is: 1. A reorder buffer for use in a microprocessor comprising:an instruction storage configured to store instruction information and generate reorder buffer tags corresponding to multiple instructions outstanding within said microprocessor; a future file having a plurality of storage locations associated with each register implemented in said microprocessor, wherein each storage location is configured to store a reorder buffer tag that corresponds to a particular instruction, wherein said particular instruction is the last instruction, in program order, represented within said instruction storage that has a destination operand corresponding to the register associated with said storage location, and wherein said future file is further configured to store instruction results that correspond to said particular instruction when said instruction results are provided; and a control unit coupled to said instruction storage and to said future file, wherein said control unit is configured to recover said future file upon a branch misprediction by: reading the entries in said instruction storage, in reverse program order and beginning with said mispredicted instruction; writing instruction results, if available, into said future file for each entry having a destination operand corresponding to a register; and writing a reorder buffer tag into said future file for each entry without instruction results having a destination operand corresponding to a register. 2. The reorder buffer as recited in claim 1 wherein said future file is configured to store a mask bit for each storage location within said future file.
CROSS-REFERENCE The present application is a continuation-in-part of application Ser. No. 08/690,370 filed Jul. 26, 1996, entitled "A Reorder Buffer Having a Future File for Storing Speculative Instruction Execution Results" by Thang M. Tran, now U.S. Pat. No. 5,872,751
SUMMARY OF THE INVENTION The problems outlined above are in large part solved by a reorder buffer in accordance with the present invention. A reorder buffer having features of the present invention comprises a control unit, an instruction storage, and a future file.
BRIEF DESCRIPTION OF THE DRAWINGS These and other features, aspects, and advantages of the invention will become apparent upon reading the following detailed description and upon reference to the accompanying drawings where:
DETAILED DESCRIPTION Referring now to FIG. 1, one embodiment of a reorder buffer 10 and a register file 17 is illustrated. Reorder buffer 10 comprises an instruction storage 12, a future file 14, and a control unit 16. Reorder buffer 10 is configured for use in a microprocessor (as shown in FIG. 9 and described in detail below).
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4044338 *Feb 2, 1976Aug 23, 1977Siemens AktiengesellschaftAssociative memory having separately associable zonesUS4453212 *Jul 13, 1981Jun 5, 1984Burroughs CorporationExtended address generating apparatus and methodUS4807115 *Oct 14, 1987Feb 21, 1989Cornell Research Foundation, Inc.Instruction issuing mechanism for processors with multiple functional unitsUS4858105 *Mar 26, 1987Aug 15, 1989Hitachi, Ltd.Pipelined data processor capable of decoding and executing plural instructions in parallelUS4928223 *Aug 28, 1986May 22, 1990Fairchild Semiconductor CorporationFloating point microprocessor with directable two level microinstructionsUS5053631 *Apr 2, 1990Oct 1, 1991Advanced Micro Devices, Inc.Pipelined floating point processing unitUS5058048 *Apr 2, 1990Oct 15, 1991Advanced Micro Devices, Inc.Normalizing pipelined floating point processing unitUS5129067 *Jun 6, 1989Jul 7, 1992Advanced Micro Devices, Inc.Multiple instruction decoder for minimizing register port requirementsUS5136697 *Jun 6, 1989Aug 4, 1992Advanced Micro Devices, Inc.System for reducing delay for execution subsequent to correctly predicted branch instruction using fetch information stored with each block of instructions in cacheUS5197132 *Jun 29, 1990Mar 23, 1993Digital Equipment CorporationRegister mapping system having a log containing sequential listing of registers that were changed in preceding cycles for precise post-branch recoveryUS5226126 *Feb 21, 1990Jul 6, 1993Nexgen MicrosystemsProcessor having plurality of functional units for orderly retiring outstanding operations based upon its associated tagsUS5226130 *Feb 26, 1990Jul 6, 1993Nexgen MicrosystemsMethod and apparatus for store-into-instruction-stream detection and maintaining branch prediction cache consistencyUS5345569 *Sep 20, 1991Sep 6, 1994Advanced Micro Devices, Inc.Apparatus and method for resolving dependencies among a plurality of instructions within a storage deviceUS5355457 *May 21, 1991Oct 11, 1994Motorola, Inc.Data processor for performing simultaneous instruction retirement and backtrackingUS5446912 *Dec 29, 1993Aug 29, 1995Intel CorporationPartial width stalls within register alias tableUS5524263 *Feb 25, 1994Jun 4, 1996Intel CorporationMethod and apparatus for partial and full stall handling in allocationUS5535346 *Jul 5, 1994Jul 9, 1996Motorola, Inc.Data processor with future file with parallel update and method of operationUS5548776 *Sep 30, 1993Aug 20, 1996Intel CorporationFor renaming a set of logical source registersUS5560032 *Mar 1, 1995Sep 24, 1996Seiko Epson CorporationHigh-performance, superscalar-based computer system with out-of-order instruction execution and concurrent results distributionUS5574935 *Nov 29, 1994Nov 12, 1996Intel CorporationSuperscalar processor with a multi-port reorder bufferUS5584038 *Apr 17, 1996Dec 10, 1996Intel CorporationEntry allocation in a circular buffer using wrap bits indicating whether a queue of the circular buffer has been traversedUS5623628 *Mar 2, 1994Apr 22, 1997Intel CorporationComputer system and method for maintaining memory consistency in a pipelined, non-blocking caching bus request queueUS5632023 *Jun 1, 1994May 20, 1997Advanced Micro Devices, Inc.Superscalar microprocessor including flag operand renaming and forwarding apparatusUS5651125 *Jul 10, 1995Jul 22, 1997Advanced Micro Devices, Inc.High performance superscalar microprocessor including a common reorder buffer and common register file for both integer and floating point operationsUS5689720 *Feb 15, 1996Nov 18, 1997Seiko Epson CorporationHigh-performance superscalar-based computer system with out-of-order instruction executionUS5737624 *Jan 31, 1996Apr 7, 1998Seiko Epson CorporationSuperscalar risc instruction schedulingUS5768555 *Feb 20, 1997Jun 16, 1998Advanced Micro Devices, Inc.Reorder buffer employing last in buffer and last in line bitsEP0259095A2 *Aug 26, 1987Mar 9, 1988Amdahl CorporationCache storage queueEP0381471A2 *Jan 31, 1990Aug 8, 1990Digital Equipment CorporationMethod and apparatus for preprocessing multiple instructions in a pipeline processorEP0459232A2 *May 16, 1991Dec 4, 1991National Semiconductor CorporationPartially decoded instruction cacheEP0679991A1 *Apr 12, 1995Nov 2, 1995Advanced Micro Devices Inc.Data processor for variable width operandsEP0724213A2 *Dec 20, 1995Jul 31, 1996International Business Machines CorporationA method and system for reducing dispatch latency in a processorGB2263985A * Title not availableGB2263987A * Title not availableGB2281422A * Title not availableWO1993020505A2 *Mar 26, 1993Oct 14, 1993Seiko Epson CorpSuperscalar risc instruction schedulingWO1997013201A1 *Oct 4, 1996Apr 10, 1997Advanced Micro Devices IncUnified multi-function operation scheduler for out-of-order execution in a superscalar processor* Cited by examinerNon-Patent CitationsReference1"Intel Architecture Software Developer's Manual, Volume 1: Basic Architecture", Intel Corporation, Prospect IL, 1996, 1997, Chapter 8: Programming With The Intel MMX� Technology, pp. 8-1 through 8-15.2"Intel MMX� Technology --Frequently Asked Questions" 6 pp. (see http://www.intel.com/drg/mmx/support/faq/htm).3Gaddis, et al, "FP 13.2: A 56 Entry Instruction Reorder Buffer," ISSCC96/Session 13/Microprocessors/Paper FP 13.2, 1996 IEEE International Solid-State Circuits Conference, pp. 212-213, 447.4 *Gaddis, et al, FP 13.2: A 56 Entry Instruction Reorder Buffer, ISSCC96/Session 13/Microprocessors/Paper FP 13.2, 1996 IEEE International Solid State Circuits Conference, pp. 212 213, 447.5Holstad, S., "Tutorial Tuesday: Decoding MMX" Jan. 14, 1997, Earthlink Network, Inc. copyright 1997, 5 pages. (see http://www.earthlink.net/daily/Tuesday/MMX).6 *Holstad, S., Tutorial Tuesday: Decoding MMX Jan. 14, 1997, Earthlink Network, Inc. copyright 1997, 5 pages. (see http://www.earthlink.net/daily/Tuesday/MMX).7 *Intel Architecture Software Developer s Manual, Volume 1: Basic Architecture , Intel Corporation, Prospect IL, 1996, 1997, Chapter 8: Programming With The Intel MMX Technology, pp. 8 1 through 8 15.8 *Intel MMX Technology Frequently Asked Questions 6 pp. (see http://www.intel.com/drg/mmx/support/faq/htm).9Intel, "Chapter 2: Microprocessor Architecture Overview," 1994, pp. 2-1 through 2-4.10 *Intel, Chapter 2: Microprocessor Architecture Overview, 1994, pp. 2 1 through 2 4.11Lenell, John, "A 20MHz CMOS Reorder Buffer for a Superscalar Microprocessor," 4th NASA Symposium on VLSI Design, 1992, pp. 2.3.1 -2.3.12.12 *Lenell, John, A 20MHz CMOS Reorder Buffer for a Superscalar Microprocessor, 4 th NASA Symposium on VLSI Design, 1992, pp. 2.3.1 2.3.12.13Michael Slater, "AMD's K5 Designed to Outrun Pentium," Microprocessor Report, Vol. 8, No. 14, Oct. 24, 1994, 7 pp.14 *Michael Slater, AMD s K5 Designed to Outrun Pentium, Microprocessor Report, Vol. 8, No. 14, Oct. 24, 1994, 7 pp.15Sebastian Rupley and John Clyman, "P6: The Next Step?," PC Magazine, Sep. 12, 1995, 16 pages.16 *Sebastian Rupley and John Clyman, P6: The Next Step , PC Magazine, Sep. 12, 1995, 16 pages.17Tom R. Halfill, "AMD K6 Takes On Intel P6," BYTE, Jan. 1996, 4 pages.18 *Tom R. Halfill, AMD K6 Takes On Intel P6, BYTE, Jan. 1996, 4 pages.19 *U.S. Application No. 08/690,383, filed Jul. 26, 1996.20 *U.S. Application No. 08/690,384, filed Jul. 26, 1996.21 *U.S. Application No. 08/690,385, filed Jul. 26, 1996.22 *U.S. Application No. 08/711,880, filed Sep. 12, 1996.23 *U.S. Application No. 08/974,967, filed Nov. 20, 1997.24 *U.S. Application No. 09/114,554 filed Jul. 13, 1998.25Wallace, et al, "Design and Implementation of 100 MHz Reorder Buffer," Department of Electrical and Computer Engineering, University of California, Irvine, 0-7803-2428-May 95, 1995, IEEE, pp. 42-45.26 *Wallace, et al, Design and Implementation of 100 MHz Reorder Buffer, Department of Electrical and Computer Engineering, University of California, Irvine, 0 7803 2428 May 95, 1995, IEEE, pp. 42 45.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS6493821 *Jun 9, 1998Dec 10, 2002Intel CorporationRecovery from writeback stage event signal or micro-branch misprediction using instruction sequence number indexed state information tableUS6519730 *Mar 16, 2000Feb 11, 2003Fujitsu LimitedComputer and error recovery method for the sameUS6571332 *Apr 11, 2000May 27, 2003Advanced Micro Devices, Inc.Method and apparatus for combined transaction reordering and buffer managementUS6751749Feb 22, 2001Jun 15, 2004International Business Machines CorporationMethod and apparatus for computer system reliabilityUS6772368Dec 11, 2000Aug 3, 2004International Business Machines CorporationMultiprocessor with pair-wise high reliability mode, and method thereforeUS7124285 *Mar 29, 2001Oct 17, 2006Intel CorporationPeak power reduction when updating future fileUS7600099 *Mar 8, 2007Oct 6, 2009International Business Machines CorporationSystem and method for predictive early allocation of stores in a microprocessorUS7647488 *Mar 4, 2005Jan 12, 2010Fujitsu LimitedInformation processing device with branch history restorationUS7865770 *Jan 10, 2008Jan 4, 2011Advanced Micro Devices, Inc.Processor including efficient signature generation for logic error protection* Cited by examinerClassifications U.S. Classification712/239, 712/E09.061, 712/E09.049, 712/E09.054, 712/E09.05International ClassificationG06F9/38Cooperative ClassificationG06F9/3853, G06F9/3857, G06F9/3855, G06F9/3863, G06F9/384, G06F9/3842, G06F9/3836, G06F9/3838European ClassificationG06F9/38E6, G06F9/38E, G06F9/38H2, G06F9/38E2Legal EventsDateCodeEventDescriptionNov 22, 2010FPAYFee paymentYear of fee payment: 12Nov 16, 2006FPAYFee paymentYear of fee payment: 8Sep 24, 2002FPAYFee paymentYear of fee payment: 4Nov 20, 1997ASAssignmentOwner name: ADVANCED MICRO DEVICES, INC., CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:WITT, DAVID B.;TRAN, THANG M.;REEL/FRAME:008882/0112Effective date: 19971119RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google