Reordering the output of recirculated transactions within a pipeline

Abstract

A mechanism is provided for recirculating transactions within a pipeline while reordering outputs. A set of transactions associated with a block of data is received and each transaction in the set of transactions is processed via the pipeline. For each transaction processed via the pipeline, responsive to the transaction exiting the pipeline, a determination is made as to whether the transaction needs further processing. Responsive to the transaction needing further processing, the transaction is re-circulated via the pipeline forming a recirculated transaction.

What is claimed is: 
     
       1. A method, in a data processing system, for recirculating transactions within a pipeline while reordering outputs, the method comprising:
 receiving a set of transactions associated with a block of data; 
 processing each transaction in the set of transactions via the pipeline; 
 for each transaction processed via the pipeline:
 as the transaction enters the pipeline, identifying a unique identifier for the transaction and a unique identifier for a subsequent transaction that will follow the transaction; 
 responsive to the transaction exiting the pipeline:
 storing results of the transaction in a results data structure according to the unique identifier; 
 determining whether the transaction needs further processing; 
 responsive to the transaction failing to need further processing, recording the unique identifier for the transaction that immediately follows the transaction in an exit data structure for use in exporting the results; and 
 responsive to the transaction needing further processing, recirculating the transaction via the pipeline forming a recirculated transaction; and 
 
 
 for each recirculated transaction processed via the pipeline:
 identifying a new unique identifier for the recirculated transaction while retaining, the unique identifier for the subsequent transaction that will follow the recirculated transaction; 
 recording the new unique identifier for the transaction in the exit data structure for use in exporting the results; and 
 processing the recirculated transaction. 
 
 
     
     
       2. The method of  claim 1 , further comprising:
 responsive to one or more results being available to be written from the results data structure, exporting the one or more results of the set of transactions as per the exit data structure. 
 
     
     
       3. The method of  claim 1 , further comprising:
 responsive to the recirculated transaction exiting the pipeline and failing to need further processing, storing the results of the recirculated transaction in the results data structure according to the new unique identifier. 
 
     
     
       4. The method of  claim 1 , wherein, responsive to the transaction being re-circulated through the pipeline, the reprocessed transaction enters the pipeline before any unprocessed transaction. 
     
     
       5. The method of  claim 1 , wherein the block of data comprises compressed symbols. 
     
     
       6. The method of  claim 1 , wherein each transaction comprises nine or more Huffman codes. 
     
     
       7. The method of  claim 1 , wherein the exit data structure is a linked list. 
     
     
       8. The method of  claim 1 , wherein the results data structure is in a static random-access memory (SRAM). 
     
     
       9. A computer program product comprising a non-transitory computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a computing device, causes the computing device to:
 receive a set of transactions associated with a block of data; 
 process each transaction in the set of transactions via a pipeline; 
 for each transaction processed via the pipeline:
 as the transaction enters the pipeline, identify a unique identifier for the transaction and a unique identifier for a subsequent transaction that will follow the transaction; 
 responsive to the transaction exiting the pipeline:
 store the results of the transaction in a results data structure according to the unique identifier; 
 determine whether the transaction needs further processing; 
 responsive to the transaction failing to need further processing, record the unique identifier for the transaction that immediately follows the transaction in an exit data structure for use in exporting the results; and 
 responsive to the transaction needing further processing, re-circulate the transaction via the pipeline forming a recirculated transaction; and 
 
 
 for each recirculated transaction processed via the pipeline:
 identify a new unique identifier for the recirculated transaction while retaining the unique identifier for the subsequent transaction that will follow the recirculated transaction; 
 record the new unique identifier for the transaction in the exit data structure for use in exporting the results; and 
 process the recirculated transaction. 
 
 
     
     
       10. The computer program product of  claim 9 , wherein the computer readable program further causes the computing device to:
 responsive to one or more results being available to be written from the results data structure, export the one or more results of the set of transactions as per the exit data structure. 
 
     
     
       11. The computer program product of  claim 9 , wherein the computer readable program further causes the computing device to:
 responsive to the recirculated transaction exiting the pipeline and failing to need further processing, store the results of the recirculated transaction in the results data structure according to the new unique identifier; and 
 responsive to one or more results being available to be written from the results data structure, export the results of the set of transactions as per the exit data structure. 
 
     
     
       12. An apparatus comprising:
 a processor; and 
 a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to: 
 receive a set of transactions associated with a block of data; 
 process each transaction in the set of transactions via a pipeline; 
 for each transaction processed via the pipeline:
 as the transaction enters the pipeline, identify a unique identifier for the transaction and a unique identifier for a subsequent transaction that will follow the transaction; 
 responsive to the transaction exiting the pipeline:
 store the results of the transaction in a results data structure according to the unique identifier; 
 determine whether the transaction needs further processing; 
 responsive to the transaction failing to need further processing, record the unique identifier for the transaction that immediately follows the transaction in an exit data structure for use in exporting the results; and 
 responsive to the transaction needing further processing, re-circulate the transaction via the pipeline forming a recirculated transaction; and 
 
 
 for each recirculated transaction processed via the pipeline:
 identify a new unique identifier for the recirculated transaction while retaining the unique identifier for the subsequent transaction that will follow the recirculated transaction; 
 record the new unique identifier for the transaction in the exit data structure for use in exporting the results; and 
 process the recirculated transaction. 
 
 
     
     
       13. The apparatus of  claim 12 , wherein the instructions further cause the processor to:
 responsive to one or more results being available to be written from the results data structure, export the one or more results of the set of transactions as per the exit data structure. 
 
     
     
       14. The apparatus of  claim 12 , wherein the instructions further cause the processor to:
 responsive to the recirculated transaction exiting the pipeline and failing to need further processing, store the results of the recirculated transaction in the results data structure according to the new unique identifier; and 
 responsive to one or more results being available to be written from the results data structure, export the results of the set of transactions as per the exit data structure.