Processing of high priority data elements in systems comprising a host processor and a co-processor

• US 20070283131A1
• Filed: 01/30/2006
• Published: 12/06/2007
• Est. Priority Date: 01/30/2006
• Status: Abandoned Application

• Current Assignee: ATI Technologies ULC (Advanced Micro Devices, Inc.)
• Original Assignee: ATI Technologies Incorporated (Advanced Micro Devices, Inc.)
• Inventors: Chan, Hing, Sagalovitch, Serguei, Yurin, Alexei
• Application Number:
  US11/342,906
• Publication Number:
  US 20070283131A1
• Time in Patent Office: Days
• US Class Current: 712/203
• CPC Class Codes: G06F 9/485 Task life-cycle, e.g. stopping, restarting, resuming execution G06F9/4881 takes precedence
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

To provide for the processing of priority data elements between a host processor and a co-processor that exchange such data elements using a queue, the host processor determines a priority of a data element received from an application. If the priority is higher than a lowest possible priority value, at least one lower priority data element within the queue may be identified and modified thereby temporarily removing it from the queue. When the priority data element is written into the queue a query packet is included that will cause the co-processor to return information regarding a last executed queued data element. Based on the returned information, the host processor can determine one or more unmodified data elements (uniquely corresponding to the one or more modified queued data elements) to be written into the queue in accordance with a sequence of the previously modified queued data elements.

Claims

1. In a system comprising a host processor interacting with a co-processor via at least a queue, a method in the host processor for processing a priority data element to be written into the queue by the host processor, the method comprising:

determining a priority of the priority data element;

when the priority of the priority data element is higher than a lowest possible priority value, comparing the priority of the priority data element with a priority of at least one queued data element to determine at least one lower priority queued data element, wherein each of the at least one lower priority queued data element has a priority lower than the priority for the priority data element; and

modifying one or more of the at least one lower priority queued data element to provide at least one modified queued data element such that the at least one modified queued data element is temporarily removed from the queue.

2. The method of claim 1, further comprising:

writing at least one data element into the queue to provide the at least one queued data element, wherein each of the at least one queued data element comprises a pointer to an immediately preceding queued data element, a pointer to an immediately subsequent queued data element and a priority indicator.

3. The method of claim 2, wherein comparing the priority of the priority data element further comprises:

accessing the priority indicator of a current queued data element of the at least one queued data element to determine the priority of the current queued data element;

determining that the current queued data element is a lower priority queued data element based on the priority indicator of current queued data element;

when the current queued data element is a lower priority queued data element, modifying the current queued data element such that the co-processor will skip processing of the current queued data element; and

when the current queued data element is a lower priority queued data element, determining a location within the queue of a next queued data element of the at least one queued data element based on either the pointer to the immediately preceding queued data element of the current queued data element or the pointer to the immediately subsequent queued data element of the current queued data element.

4. The method of claim 3, further comprising:

writing each of the at least one queued data element into a shadow buffer accessible by the host processor to provide at least one shadowed data element, wherein accessing the current priority indicator of the current queued data element and determining a location within the queue of the next queued data element are performed based on uniquely corresponding shadowed data elements of the at least one shadowed data element.

5. The method of claim 1, further comprising:

writing the priority data element and a query data element into the queue subsequent to the at least one modified queued data element to provide a queued priority data element and a queued query data element, wherein the queued query data element, when processed by the co-processor, cause the co-processor to provide the host processor with information regarding a last-executed queued data element in the queue.

6. The method of claim 5, further comprising:

determining, for each modified queued data element of the at least one modified queued data element based on the information regarding the last-executed queued data element, an unmodified data element uniquely corresponding to the modified queued data element to provide at least one unmodified data element; and

writing the at least one unmodified data element into the queue in accordance with a sequence of the at least one modified queued data element.

7. The method of claim 6, further comprising:

modifying a sequence indicator of the queued priority data element based on the information regarding the last-executed queued data element.

8. A processor-readable medium having stored thereon processor-executable instructions that, when executed by a processor that interacts with a co-processor via at least a queue, cause the processor to:

determine a priority of a priority data element to be written into the queue;

when the priority of the priority data element is higher than a lowest possible priority value, compare the priority of the priority data element with a priority of at least one queued data element to determine at least one lower priority queued data element, wherein each of the at least one lower priority queued data element has a priority lower than the priority for the priority data element; and

modify one or more of the at least one lower priority queued data element to provide at least one modified queued data element such that the at least one modified queued data element is temporarily removed from the queue.

9. The processor-readable medium of claim 8, further comprising processor-executable instructions that, when executed by the processor, cause the processor to:

write at least one data element into the queue to provide the at least one queued data element, wherein each of the at least one queued data element comprises a pointer to an immediately preceding queued data element, a pointer to an immediately subsequent queued data element and a priority indicator.

10. The processor-readable medium of claim 9, further comprising processor-executable instructions that, when executed by the processor, cause the processor to:

access the priority indicator of a current queued data element of the at least one queued data element to determine the priority of the current queued data element;

determine that the current queued data element is a lower priority queued data element based on the priority indicator of current queued data element;

when the current queued data element is a lower priority queued data element, modify the current queued data element such that the co-processor will skip processing of the current queued data element; and

when the current queued data element is a lower priority queued data element, determine a location within the queue of a next queued data element of the at least one queued data element based on either the pointer to the immediately preceding queued data element of the current queued data element or the pointer to the immediately subsequent queued data element of the current queued data element.

11. The processor-readable medium of claim 10, further comprising processor-executable instructions that, when executed by the processor, cause the processor to:

write each of the at least one queued data element into a shadow buffer accessible by the host processor to provide at least one shadowed data element, wherein accessing the current priority indicator of the current queued data element and determining a location within the queue of the next queued data element are performed based on uniquely corresponding shadowed data elements of the at least one shadowed data element.

12. The processor-readable medium of claim 8, further comprising processor-executable instructions that, when executed by the processor, cause the processor to:

write the priority data element and a query data element into the queue subsequent to the at least one modified queued data element to provide a queued priority data element and a queued query data element, wherein the queued query data element, when processed by the co-processor, cause the co-processor to provide the host processor with information regarding a last-executed queued data element in the queue.

13. The processor-readable medium of claim 12, further comprising processor-executable instructions that, when executed by the processor, cause the processor to:

determine, for each modified queued data element of the at least one modified queued data element based on the information regarding the last-executed queued data element, an unmodified data element uniquely corresponding to the modified queued data element to provide at least one unmodified data element; and

write the at least one unmodified data element into the queue in accordance with a sequence of the at least one modified queued data element.

14. The processor-readable medium of claim 13, further comprising processor-executable instructions that, when executed by the processor, cause the processor to:

modify a sequence indicator of the queued priority data element based on the information regarding the last-executed queued data element.

15. A system comprising:

a storage device comprising a queue;

a co-processor coupled to the storage device; and

a host-processor coupled to the storage device and operative to;

determine a priority of a priority data element to be written into the queue;

when the priority of the priority data element is higher than a lowest possible priority value, compare the priority of the priority data element with a priority of at least one queued data element to determine at least one lower priority queued data element, wherein each of the at least one lower priority queued data element has a priority lower than the priority for the priority data element; and

modify one or more of the at least one lower priority queued data element to provide at least one modified queued data element such that the at least one modified queued data element is temporarily removed from the queue.

16. The system of claim 15, wherein the host processor is further operative to:

write at least one data element into the queue to provide the at least one queued data element, wherein each of the at least one queued data element comprises a pointer to an immediately preceding queued data element, a pointer to an immediately subsequent queued data element and a priority indicator.

17. The system of claim 16, wherein the host processor is further operative to:

access the priority indicator of a current queued data element of the at least one queued data element to determine the priority of the current queued data element;

determine that the current queued data element is a lower priority queued data element based on the priority indicator of current queued data element;

when the current queued data element is a lower priority queued data element, modify the current queued data element such that the co-processor will skip processing of the current queued data element; and

when the current queued data element is a lower priority queued data element, determine a location within the queue of a next queued data element of the at least one queued data element based on either the pointer to the immediately preceding queued data element of the current queued data element or the pointer to the immediately subsequent queued data element of the current queued data element.

18. The system of claim 17, further comprising:

another storage device coupled to the host processor and comprising a shadow buffer, wherein the host processor is further operative to write each of the at least one queued data element into a shadow buffer accessible by the host processor to provide at least one shadowed data element, wherein accessing the current priority indicator of the current queued data element and determining a location within the queue of the next queued data element are performed based on uniquely corresponding shadowed data elements of the at least one shadowed data element.

19. The system of claim 15, wherein the host processor is further operative to:

write the priority data element and a query data element into the queue subsequent to the at least one modified queued data element to provide a queued priority data element and a queued query data element, wherein the queued query data element, when processed by the co-processor, cause the co-processor to provide the host processor with information regarding a last-executed queued data element in the queue.

20. The system of claim 19, wherein the host processor is further operative to:

determine, for each modified queued data element of the at least one modified queued data element based on the information regarding the last-executed queued data element, an unmodified data element uniquely corresponding to the modified queued data element to provide at least one unmodified data element; and

write the at least one unmodified data element into the queue in accordance with a sequence of the at least one modified queued data element.

21. The system of claim 20, wherein the host processor is further operative to:

modify a sequence indicator of the queued priority data element based on the information regarding the last-executed queued data element.

22. A processor-readable medium having stored thereon a data element structure, comprising:

a first data field comprising commands to processed by a co-processor; and

a priority field comprising a priority indication, wherein during processing of the commands, the priority indication is examined to determine whether the commands should be processed by the co-processor with a higher priority than other commands to be processed by the co-processor.

23. The processor-readable medium of claim 22, the data element structure further comprising:

a first pointer field comprising a pointer to an immediately preceding data element structure.

24. The processor-readable medium of claim 22, the data element structure further comprising:

a second pointer field comprising a pointer to an immediately subsequent data element structure.