Method for efficient buffer tag allocation

• US 7,107,367 B1
• Filed: 08/12/2003
• Issued: 09/12/2006
• Est. Priority Date: 08/12/2003
• Status: Expired due to Fees

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Hughes, William A.
• Primary Examiner(s): Bragdon, Reginald G.
• Assistant Examiner(s): Vo, Thomas D.
• Application Number:
  US10/639,128
• Time in Patent Office: 1,127 Days
• Field of Search: 711167-169, 711/170, 709/238, 710/220, 712/202, 718102-107
• US Class Current: 710/39
• CPC Class Codes: G06F 13/1673 using buffers

Abstract

A method and mechanism for allocating transaction tags. A request queue includes a counter whose value is used to identify a corresponding tag of a plurality of unique tags. The queue is configured to increment the counter and use the current count value to index into a buffer pool. If the tag corresponding to the currently indexed buffer pool entry is available for allocation, a determination is made as to whether the currently identified tag is corresponds to the last tag which has been de-allocated. If the identified available buffer pool entry/tag matches the last tag which was de-allocated, the queue continues the process of counter incrementation and searching of the buffer pool for an available entry to select for allocation. When a request is received, the currently selected tag is allocated. Additional circuitry may be used to identify a fallback tag in the event a request is received while the queue is searching for a tag. In such an event, the fallback tag may be allocated.

Claims

1. A method for allocating a tag, said method comprising:

incrementing a counter responsive to determining a tag of a plurality of unique tags has not been selected for allocation;

utilizing a value of said counter to identify a first tag of said tags;

determining whether said first tag is available for allocation;

repeating said incrementing, utilizing, and determining if said first tag is not available for allocation; and

selecting said first tag for allocation if said first tag is available for allocation and said first tag does not correspond to a tag most recently de-allocated.

2. The method as recited in claim 1, wherein said method further comprises selecting said first tag for allocation in response to detecting said first tag is available for allocation, said first tag corresponds to a tag most recently de-allocated, and said first tag is an only tag of said tags available for allocation.

3. The method as recited in claim 1, further comprising repeating said incrementing, utilizing, and determining in response to detecting said first tag is available for allocation, said first tag corresponds to a tag most recently de-allocated, and said first tag is not an only tag of said tags available for allocation.

4. The method as recited in claim 3, further comprising storing said first tag as a fallback tag in response to detecting said first tag is available for allocation, said first tag corresponds to a tag most recently de-allocated, and said first tag is not an only tag of said tags available for allocation.

5. The method as recited in claim 1, further comprising determining a fallback tag concurrently with said incrementing, utilizing, and determining.

6. The method as recited in claim 1, further comprising:

detecting a received transaction; and

allocating a tag for said transaction in response to determining said transaction corresponds to a request.

7. The method as recited in claim 6, wherein said tag allocated for said request corresponds to said first tag.

8. The method as recited in claim 7, wherein in response to detecting a tag has not been selected for allocation, said tag allocated for said request corresponds to a fallback tag.

9. The method as recited in claim 6, wherein in response to detecting said transaction corresponds to a completion indication, said method further comprises:

de-allocating a tag which corresponds to the received transaction; and

storing an indication that said de-allocated tag is a tag most recently de-allocated.

10. A request queue comprising:

a buffer pool including a plurality of entries, each said entry being indicative of a unique tag; and

a control unit, wherein said control unit is configured to;

increment a counter responsive to determining no tag of said entries has been selected for allocation;

utilize a value of said counter to identify a first entry of said entries;

determine whether a first tag corresponding to said first entry is available for allocation;

repeat said incrementing, utilizing, and determining in response to detecting said first tag is not available for allocation; and

select said first tag for allocation in response to detecting said first tag is available for allocation and said first tag does not correspond to a tag most recently de-allocated.

11. The queue as recited in claim 10, wherein said control unit is further configured to select said first tag for allocation in response to detecting said first tag is available for allocation, said first tag corresponds to a tag most recently de-allocated, and said first tag is an only tag of said tags available for allocation.

12. The queue as recited in claim 10, wherein said control unit is further configured to repeat said incrementing, utilizing, and determining in response to detecting said first tag is available for allocation, said first tag corresponds to a tag most recently de-allocated, and said first tag is not an only tag corresponding to said entries which is available for allocation.

13. The queue as recited in claim 12, wherein said control unit is further configured to store said first tag as a fallback tag in response to detecting said first tag is available for allocation, said first tag corresponds to a tag most recently de-allocated, and said first tag is not an only tag of said tags available for allocation.

14. The queue recited in claim 10, wherein said control unit is further configured to determine a fallback tag concurrently with said incrementing, utilizing, and determining.

15. The queue as recited in claim 10, wherein said control unit is further configured to:

detect a received transaction; and

allocate a tag for said transaction in response to determining said transaction corresponds to a request.

16. The queue as recited in claim 15, wherein said tag allocated for said request corresponds to said first tag.

17. The queue as recited in claim 16, wherein in response to detecting a tag has not been selected for allocation, said tag allocated for said request corresponds to a fallback tag.

18. The queue as recited in claim 15, wherein in response to detecting said transaction corresponds to a completion indication, said control unit is further configured to:

de-allocate a tag which corresponds to the received transaction; and

store an indication that said de-allocated tag is a tag most recently de-allocated.

19. The queue as recited in claim 10, wherein said queue is coupled to receive requests from one or more bus mastering devices.

20. A system comprising:

a bus master including a bus interface coupled to a bus; and

a request queue coupled to said bus master via said bus;

wherein said request queue is configured to;

increment a counter responsive to determining no tag of said entries has been selected for allocation;

utilize a value of said counter to identify a first entry of said entries;

determine whether a first tag corresponding to said first entry is available for allocation;

repeat said incrementing, utilizing, and determining in response to detecting said first tag is not available for allocation; and

select said first tag for allocation in response to detecting said first tag is available for allocation and said first tag does not correspond to a tag most recently de-allocated.

21. The system as recited in claim 20, wherein said queue is further configured to select said first tag for allocation in response to detecting said first tag is available for allocation, said first tag corresponds to a tag most recently de-allocated, and said first tag is an only tag of said tags available for allocation.

22. The system as recited in claim 20, wherein said queue is further configured to repeat said incrementing, utilizing, and determining in response to detecting said first tag is available for allocation, said first tag corresponds to a tag most recently de-allocated, and said first tag is not an only tag corresponding to said entries which is available for allocation.

23. The system as recited in claim 22, wherein said queue is further configured to store said first tag as a fallback tag in response to detecting said first tag is available for allocation, said first tag corresponds to a tag most recently de-allocated, and said first tag is not an only tag of said tags available for allocation.

24. The system as recited in claim 20, wherein said queue is further configured to:

detect a received transaction; and

allocate a tag for said transaction in response to determining said transaction corresponds to a request.