METHOD AND SYSTEM FOR REORDERING THE REQUEST QUEUE OF A HARDWARE ACCELERATOR

• US 20110276737A1
• Filed: 04/21/2011
• Published: 11/10/2011
• Est. Priority Date: 05/31/2010
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Zheng, Jun, Xie, Dong, Feng, Kuan, Mei, Xiaolu, Chang, Xiaotao
• Application Number:
  US13/091,511
• Publication Number:
  US 20110276737A1
• Time in Patent Office: Days
• US Class Current: 710/112
• CPC Class Codes: G06F 9/3881 Arrangements for communication of instructions and data

Abstract

The invention discloses a system and method for reordering the request queue of the hardware accelerator, wherein, the request queue stores therein a plurality of coprocessor request blocks (CRBs) to be input into the hardware accelerator. The system including: content addressable memory connected to the request queue for storing the state pointer of each CRB in the request queue at a same physical storage location in the request queue, receiving the state pointer of a new CRB in response to the new CRB asking to join in the request queue and outputting the physical storage location of a CRB in the request queue whose state pointer stored in the content addressable memory is the same as the state pointer of the new CRB; and CRB insertion module for receiving the physical storage location of a CRB in the request queue whose state pointer is the same as the state pointer of the new CRB and inputting the new CRB in the request queue and the CRB in the request queue whose state pointer is the same as the state pointer of the new CRB adjacently into the hardware accelerator in the order of entering the request queue. The system and method can improve the process efficiency of the hardware accelerator.

Claims

1. A system for reordering a request queue for a hardware accelerator comprising:

a processor; and

a computer memory holding computer program instructions that when executed by the processor performs the method comprising;

storing a plurality of compressor request blocks (CRBs) to be input into the hardware accelerator in a request queue;

receiving a state pointer from a new CBR joining the request queue;

determining the physical location of an already stored CRB in said request queue, said already stored CRB having a state pointer that is the same as the state pointer of the new CRB; and

inputting the new CRB in the request queue so that said already stored CRB and the new CRB are adjacent to each other in the request queue in the order of entry of the stored CRB and the new CRB into the queue, wherein stored CRB and the new CRB are input to the hardware accelerator in said order.

2. The system of claim 1 wherein said performed method further includes mapping the state pointer of the already stored CRB and the state pointer of the new CRB wherein the entry data representing the new CRB has less digits before determining the physical location of a CRB.

3. The system of claim 2, wherein each CRB stored in the queue includes:

a pointer item pointing to the next CRB is the request queue to be input into the hardware accelerator, and

a message including the sequence number of said CRB within all CRBs in the message.

4. The system of claim 3, wherein said performed method inputs the new CRB in the request queue so that said already stored CRB and the new CRB are adjacent to each other in the request queue in the order of entry of the stored CRB and the new CRB into the queue, wherein stored CRB and the new CRB are input to the hardware accelerator in said order including:

selecting between the stored CRB and the new CRB, the one having the largest sequence number in said message to be processed, and

modifying said pointer item of the new CRB so as to point to said already stored CRB as the next CRB to be input.

5. The system of claim 4, wherein:

each CRB includes two (2) state description bits;

a first state description bit indicating whether the state of each processed CRB bit is stored in memory;

a second state description bit indicating whether processing of the CRB needs to retrieve the current state of said previously stored message; and

said performed method further includes updating the two (2) state description bits of a new CRB in response to said new CRB joining said request queue.

6. The system of claim 5, wherein the performed method further includes:

locking the input of the already stored CRB to said hardware accelerator in response to said new CRB joining said request queue; and

removing said lock upon the completion of the new CRB joining said queue.

7. The system of claim 3 wherein the new CRB includes a message including the sequence number of the new CRB within all CRBs in the message.

8. The system of claim 7 wherein said performed method of inputting the new CRB in the request queue so that said already stored CRB and the new CRB are adjacent to each other in the request queue in the order of entry of the stored CRB and the new CRB into the queue includes:

selecting between the stored CRB and the new CRB, the one having the largest sequence number in said message to be input into the hardware accelerator; and

right shifting by one each CRB in said request queue following the CRB being input; and

inserting a new CRB into the queue location of the next CRB being input to said hardware accelerator.

9. The system of claim 8, wherein:

each CRB includes two (2) state description bits;

a first state description bit indicating whether the state of each processed CRB hit is stored in memory;

a second state description bit indicating whether processing of the CRB needs to retrieve the current state of said previously stored message; and

said method further includes updating the two (2) state description bits of a new CRB in response to said new CRB joining said request queue.

10. The system of claim 9, wherein the performed method further includes:

locking the input of the already stored CRB to said hardware accelerator in response to said new CRB joining said request queue; and

removing said lock upon the completion of the new CRB joining said queue.

11. The system of claim 1 further including an integrated circuit chip including said processor, computer memory, request queue, CRBs and hardware accelerator.

12. A method for reordering a request queue for a hardware accelerator comprising:

storing a plurality of compressor request blocks (CRBs) to be input into the hardware accelerator in a request queue;

receiving a state pointer from a new CRB joining the request queue;

determining the physical location of an already stored CRB in said request queue, said already stored CRB having a state pointer that is the same as the state pointer of the new CRB; and

inputting the new CRB in the request queue so that said already stored CRB and the new CRB are adjacent to each other in the request queue in the order of entry of the stored CRB and the new CRB into the queue, wherein stored CRB and the new CRB are input to the hardware accelerator in said order.

13. The method of claim 12 further including mapping the state pointer of the already stored CRB and the state pointer of the new CRB wherein the entry data representing the new CRB has less digits before determining the physical location of a CRB.

14. The method of claim 13, wherein each CRB stored in the queue includes:

a pointer item pointing to the next CBR in the request queue to be input into the hardware accelerator, and

a message including the sequence number of said CRB within all CRBs in the message.

15. The method of claim 14, wherein said inputting of the new CRB in the request queue so that said already stored CRB and the new CRB are adjacent to each other in the request queue in the order of entry of the stored CRB and the new CRB into the queue, wherein stored CRB and the new CRB are input to the hardware accelerator in said order including:

selecting between the stored CRB and the new CRB, the one having the largest sequence number in said message to be processed, and

modifying said pointer item of the new CRB so as to point to said already stored CRB as the next CRB to be input.

16. The method of claim 15, wherein:

each CRB includes two (2) state description bits;

a first state description hit indicating whether the state of each processed CRB bit is stored in memory;

a second state description bit indicating whether processing of the CRB needs to retrieve the current state of said previously stored message; and

said method further includes updating the two (2) state description bits of a new CRB in response to said new CRB joining said request queue.

17. The method of claim 16 further including:

locking the input of the already stored CRB to said hardware accelerator in response to said new CRB joining said request queue; and

removing said lock upon the completion of the new CRB joining said queue.

18. The method of claim 14 wherein the new CRB includes a message including the sequence number of the new CRB within all CRBs in the message.

19. The method of claim 18 wherein said inputting of the new CRB in the request queue so that said already stored CRB and the new CRB are adjacent to each other in the request queue in the order of entry of the stored CRB and the new CRB into the queue includes:

selecting between the stored CRB and the new CRB, the one having the largest sequence number in said message to be input into the hardware accelerator; and

right shifting by one each CRB in said request queue following the CRB being input; and

inserting a new CRB into the queue location of the next CRB being input to said hardware accelerator.

20. The method of claim 19, wherein:

each CRB includes two (2) state description bits;

a first state description bit indicating whether the state of each processed CRB bit is stored in memory;

a second state description bit indicating whether processing of the CRB needs to retrieve the current state of said previously stored message; and

said method further includes updating the two (2) state description bits of a new CRB in response to said new CRB joining said request queue.

21. The method of claim 20 further including:

locking the input of the already stored CRB to said hardware accelerator in response to said new CRB joining said request queue; and

removing said lock upon the completion of the new CRB joining said queue.