Entry allocation in a circular buffer using wrap bits indicating whether a queue of the circular buffer has been traversed

• US 5,584,038 A
• Filed: 04/17/1996
• Issued: 12/10/1996
• Est. Priority Date: 03/01/1994
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Griffith, Steven J., Glew, Andrew F., Fetterman, Michael A., Hinton, Glenn J., Colwell, Robert P., Papworth, David B., Gupta, Shantanu R., Hegde, Narayan
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US08/633,905
• Time in Patent Office: 237 Days
• Field of Search: 395/800, 395/375, 395/437, 395/250
• US Class Current: 712/23
• CPC Class Codes: G06F 5/14 for overflow or underflow handling, e.g. full or empty flags
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/384 Register renaming
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables
• CPC Class Codes: G06F 9/3854 Instruction completion, e.g. retiring, committing or graduating
• CPC Class Codes: G06F 9/3856 Reordering of instructions, e.g. using queues or age tags
• CPC Class Codes: G06F 9/3858 Result writeback, i.e. updating the architectural state or memory
• CPC Class Codes: G06F 9/3863 using multiple copies of the architectural state, e.g. shadow registers

Abstract

An allocator assigns entries for a circular buffer. The allocator receives requests for storing data in entries of the circular buffer, and generates a head pointer to identify a starting entry in the circular buffer for which circular buffer entries are not allocated. In addition to pointing to an entry in the circular buffer, the head pointer includes a wrap bit. The allocator toggles the wrap bit each time the allocator traverses the linear queue of the circular buffer. A tail pointer is generated, including the wrap bit, to identify an ending entry in the circular buffer for which circular buffer entries are allocated. In response to the request for entries, the allocator sequentially assigns entries for the requests located between the head pointer and the tail pointer. The allocator has application for use in a microprocessor performing out-of-order dispatch anti speculative execution. The allocator is coupled to a reorder buffer, configured as a circular buffer, to permit allocation of entries. The allocator utilizes an all or nothing allocation policy, such that either all or no incoming instructions are allocated during an allocation period.

Claims

1. A method for allocating entries in a circular buffer, said method comprising the steps of:

receiving at least one request for storing data in entries of said circular buffer;

generating a head pointer to identify a starting entry in said circular buffer for which circular buffer entries are not allocated, said head pointer including a wrap bit to specify whether said head pointer has traversed a linear queue of said circular buffer;

generating a tail pointer to identify an ending entry in said circular buffer for which circular buffer entries are allocated including a wrap bit to specify whether said tail pointer has traversed a linear queue of said circular buffer; and

allocating free entries in said circular buffer by utilizing said head pointer and said tail pointer to sequentially allocate entries between said starting entry and said ending entry.

2. The method for allocating entries in a circular buffer as claimed in claim 1, wherein said step of allocating free entries in said circular buffer comprises the steps of:

generating a speculative address for each request to identify potential allocation entries in said circular buffer by incrementing said head pointer one entry for each request, and by toggling said wrap bit if, after allocation of the last entry in a linear queue of said circular buffer, said speculative address identifies the first entry in a linear queue of said circular buffer; and

comparing each speculative address, including said wrap bit, to said tail pointer, wherein a match between one of said plurality of speculative addresses with said tail pointer indicates said circular buffer does not contain enough unallocated entries to support all of said requests.

3. The method for allocating entries in a circular buffer as claimed in claim 2, further comprising the steps of:

incrementing said head pointer one entry designation for each of said plurality of speculative addresses allocated to generate a new head pointer; and

storing said new head pointer for use in subsequent circular buffer allocation.

4. The method for allocating entries in a circular buffer as claimed in claim 1, wherein the step of allocating entries in said circular buffer comprises the step of:

determining whether said circular buffer contains enough unallocated entries to support said requests for storing data;

allocating a circular buffer entry for each of said plurality of requests when said circular buffer contains enough unallocated entries to support all of said requests for storing data; and

allocating no circular buffer entries when said circular buffer does not contains enough unallocated entries to support all of said plurality of requests for storing data.

5. An apparatus for allocating entries in a circular buffer, said apparatus comprising:

a head pointer circuit coupled to said circular buffer for generating a head pointer to identify a starting entry in said circular buffer for which circular buffer entries are not allocated, said head pointer including a wrap bit to specify whether said head pointer has traversed a linear queue of said circular buffer;

a tail pointer circuit coupled to said circular buffer for generating a tail pointer to identify an ending entry in said circular buffer for which circular buffer entries are allocated including a wrap bit to specify whether said tail pointer has traversed a linear queue of said circular buffer; and

an allocation circuit coupled to said head pointer circuit, said tail pointer circuit and said circular buffer, said allocation circuit being constructed to receive at least one request for storing data in entries of said circular buffer, and being constructed to allocate free entries in said circular buffer by utilizing said head pointer and said tail pointer to sequentially allocate entries between said starting entry and said ending entry.

6. The apparatus for allocating entries in a circular buffer as claimed in claim 5, wherein said allocation circuit comprises:

an adder circuit for generating a speculative address for each request to identify potential allocation entries in said circular buffer, said adder circuit being constructed to receive said head pointer and incrementing said head pointer one entry for each request, and said adder circuit being constructed to toggle said wrap bit if, after allocation of the last entry in a linear queue of said circular buffer, said speculative address identifies the first entry in a linear queue of said circular buffer; and

a comparator circuit coupled to receive each speculative address and said tail pointer, said comparator circuit being constructed to compare each speculative address, including said wrap bit, to said tail pointer, wherein a match between one of said plurality of speculative addresses with said tail pointer indicates said circular buffer does not contain enough unallocated entries to support all of said requests.

7. The apparatus for allocating entries in a circular buffer as claimed in claim 6, further comprising:

a multiplexor coupled to said adder circuit for selecting said speculative address comprising the largest speculative address to generate a new head pointer; and

a register for storing said new head pointer for use in subsequent circular buffer allocation.

8. The apparatus for allocating entries in a circular buffer as claimed in claim 5, wherein said allocation circuit comprises:

a buffer entry circuit for determining whether said circular buffer contains enough unallocated entries to support said requests for storing data; and

an all or nothing allocation circuit coupled to said buffer entry circuit for allocating a circular buffer entry for each of said plurality of requests when said circular buffer contains enough unallocated entries to support all of said requests for storing data, and for allocating no circular buffer entries when said circular buffer does not contains enough unallocated entries to support all of said plurality of requests for storing data.