Method and apparatus for accelerated format translation of data in a delimited data format

Abstract

Various methods and apparatuses are described for performing high speed format translations of incoming data, where the incoming data is arranged in a delimited data format. As an example, the data in the delimited data format can be translated to a fixed field format using pipelined operations. A reconfigurable logic device can be used in exemplary embodiments as a platform for the format translation.

What is claimed is: 
     
       1. A method for low latency and high throughput data translation, the method comprising:
 receiving, by a pipeline, an incoming stream comprising a plurality of bytes arranged in a delimited data format, the incoming byte stream being representative of data arranged in a plurality of fields, the incoming byte stream comprising a plurality of data characters, a plurality of shield characters, and a plurality of field delimiter characters, the field delimiter characters defining a plurality of boundaries between the fields, wherein the pipeline is deployed on at least one of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), (3) an application-specific integrated circuit (ASIC), and/or (4) a chip multi-processor (CMP); 
 the pipeline processing the bytes of the received byte stream as the bytes stream through the pipeline, wherein the processing step includes the pipeline translating the received byte stream to an outgoing byte stream arranged in a fixed field format, the outgoing byte stream comprising a plurality of the data characters of the received byte stream arranged in a plurality of fixed-size fields and stripped of the field delimiter characters and the shield characters; 
 wherein the processing step comprises the pipeline repeatedly performing a shield character masking step and a field delimiter finding step in parallel and in a pipelined manner as the bytes stream through the pipeline to create the outgoing byte stream; 
 wherein the shield character masking step comprises the pipeline generating a shield character mask based on the shield characters in the received byte stream, wherein the shield character mask distinguishes between bytes in the received byte stream that may include field delimiter characters and bytes in the received byte stream that do not include field delimiter characters; and 
 wherein the field delimiter finding step comprises the pipeline identifying the field delimiter characters in the received byte stream based on the shield character mask. 
 
     
     
       2. The method of  claim 1  wherein the field delimiter finding step further comprises the pipeline tracking locations in the received byte stream corresponding to the identified field delimiter characters. 
     
     
       3. The method of  claim 2  wherein the field delimiter finding step further comprises the pipeline stripping the identified field delimiter characters from the received byte stream. 
     
     
       4. The method of  claim 2  wherein the processing step further comprises the pipeline repeatedly performing the shield character masking step, the field delimiter finding step, a shield character removing step, and a fixed field arranging step in parallel and in the pipelined manner as the bytes stream through the pipeline to create the outgoing byte stream;
 wherein the shield character removing step comprises the pipeline (1) distinguishing between (i) the shield characters in the received byte stream and (ii) data characters in the received byte stream that happen to match the shield character to thereby identify the shield characters in the received byte stream, and (2) removing the identified shield characters from the received byte stream; and 
 wherein the fixed field arranging step comprises the pipeline arranging the data characters of the received byte stream into the fixed-size fields based on the tracked locations of the identified field delimiter characters to thereby create the outgoing byte stream. 
 
     
     
       5. The method of  claim 1  wherein the incoming byte stream comprises a plurality of records in the delimited data format, each record comprising data arranged in at least one of the fields, the incoming byte stream further comprising a plurality of record delimiter characters, the record delimiter characters defining a plurality of boundaries between the records;
 wherein the outgoing byte stream comprises the records of the incoming byte stream arranged in the fixed field format, wherein the data characters of the received byte stream are arranged in the fixed-size fields and stripped of the field delimiter characters, the record delimiter characters, and the shield characters; 
 wherein the shield character mask distinguishes between bytes in the received byte stream that may include field delimiter characters and/or record delimiter characters and bytes in the received byte stream that do not include field delimiter characters or record delimiter characters; and 
 wherein the field delimiter finding step is part of a delimiter finding step that also comprises the pipeline identifying the record delimiter characters in the received byte stream based on the shield character mask. 
 
     
     
       6. The method of  claim 1  further comprising:
 a computer system selectively targeting a field of the outgoing byte stream for processing without analyzing the data characters of the outgoing byte stream. 
 
     
     
       7. The method of  claim 6  further comprising:
 the computer system performing a field-specific data processing operation on the selectively targeted field of the outgoing byte stream. 
 
     
     
       8. The method of  claim 7  wherein the field-specific data processing operation comprises a data quality checking operation as part of an extract, transfer, load (ETL) procedure. 
     
     
       9. The method of  claim 1  wherein the pipeline is deployed on a reconfigurable logic device. 
     
     
       10. The method of  claim 1  wherein the pipeline is deployed on a GPU. 
     
     
       11. The method of  claim 1  wherein the processing step comprises the pipeline performing the processing step on a plurality of bytes of the received byte stream per clock cycle. 
     
     
       12. The method of  claim 1  wherein the delimited data format is a comma separated value (CSV) format. 
     
     
       13. The method of  claim 1  wherein the step of generating the shield character mask comprises:
 the pipeline processing the byte stream through a state machine that includes (1) a first state that will mark the shield character mask to identify a byte as a candidate to be a field delimiter and (2) a second state that will mark the shield character mask to identify a byte as not a candidate to be a field delimiter; 
 the pipeline controllably transitioning between the first state and the second state for the bytes of the byte stream based on a detection for each byte in the byte stream as to whether it matches the shield character; and 
 the pipeline producing the shield character mask as the bytes are processed through the state machine. 
 
     
     
       14. The method of  claim 13  wherein the controllably transitioning step comprises the pipeline toggling between the first and second states on each detection of a byte in the byte stream that matches the shield character. 
     
     
       15. The method of  claim 13  further comprising:
 the pipeline associating bytes of the byte stream with corresponding portions of the shield character mask, and wherein the shield character mask portions comprise a plurality of flags that indicate whether their associated bytes in the byte stream are candidates to be a field delimiter. 
 
     
     
       16. The method of  claim 15  wherein the field delimiter finding step comprises:
 the pipeline determining which bytes of the byte stream are candidates to be a field delimiter based on their corresponding flags in shield character mask; 
 the pipeline comparing the bytes determined to be field delimiter candidates with the field delimiter character to determine whether there is a match; and 
 the pipeline identifying the field delimiter characters based on matches found by the comparing step. 
 
     
     
       17. The method of  claim 16  wherein the step of determining which bytes of the byte stream are candidates to be a field delimiter based on their corresponding flags in shield character mask comprises combining the bytes of the byte stream with their corresponding flags in the shield character mask via combinatorial AND logic. 
     
     
       18. The method of  claim 1  further comprising:
 the pipeline associating bytes of the byte stream with corresponding portions of the shield character mask, wherein the shield character mask portions comprise a plurality of flags that indicate whether their associated bytes in the byte stream are candidates to be a field delimiter. 
 
     
     
       19. The method of  claim 18  wherein the field delimiter finding step comprises:
 the pipeline determining which bytes of the byte stream are candidates to be a field delimiter based on their corresponding flags in shield character mask; 
 the pipeline comparing the bytes determined to be field delimiter candidates with the field delimiter character to determine whether there is a match; and 
 the pipeline identifying the field delimiter characters based on matches found by the comparing step. 
 
     
     
       20. The method of  claim 18  wherein the step of generating the shield character mask comprises processing the byte stream through a state machine to produce the flags for the shield character mask. 
     
     
       21. An apparatus for low latency and high throughput data translation, the apparatus comprising:
 at least one of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), (3) an application-specific integrated circuit (ASIC), and/or (4) a chip multi-processor (CMP) on which a pipeline is deployed; 
 wherein the pipeline is configured to receive an incoming stream comprising a plurality of bytes arranged in a delimited data format, the incoming byte stream being representative of data arranged in a plurality of fields, the incoming byte stream comprising a plurality of data characters, a plurality of shield characters, and a plurality of field delimiter characters, wherein the field delimiter characters define a plurality of boundaries between the fields; 
 wherein the pipeline is further configured to process the bytes of the received byte stream as the bytes stream through the pipeline to translate the received byte stream to an outgoing byte stream arranged in a fixed field format, the outgoing byte stream comprising a plurality of the data characters of the received byte stream arranged in a plurality of fixed-size fields and stripped of the field delimiter characters and the shield characters; 
 wherein the pipeline comprises a plurality of processing modules that are configured to operate in parallel and in a pipelined manner to create the outgoing byte stream as the bytes stream through the pipeline, wherein the processing modules comprise a first processing module and a second processing module; 
 wherein the first processing module is configured to generate a shield character mask based on the shield characters in the received byte stream, wherein the shield character mask distinguishes between bytes in the received byte stream that may include field delimiter characters and bytes in the received byte stream that do not include field delimiter characters; and 
 wherein the second processing module is configured to identify the field delimiter characters in the received byte stream based on the shield character mask. 
 
     
     
       22. The apparatus of  claim 21  wherein the second processing module is further configured to track locations in the received byte stream corresponding to the identified field delimiter characters. 
     
     
       23. The apparatus of  claim 22  wherein the second processing module is further configured to strip the identified field delimiter characters from the received byte stream. 
     
     
       24. The apparatus of  claim 22  wherein the processing modules further comprise a third processing module and a fourth processing module;
 wherein the third processing module is configured to (1) distinguish between (i) the shield characters in the received byte stream and (ii) data characters in the received byte stream that happen to match the shield character to thereby identify the shield characters in the received byte stream, and (2) remove the identified shield characters from the received byte stream; and 
 wherein the third processing module is configured to arrange the data characters of the received byte stream into the fixed-size fields based on the tracked locations of the identified field delimiter characters to thereby create the outgoing byte stream. 
 
     
     
       25. The apparatus of  claim 21  wherein the incoming byte stream comprises a plurality of records in the delimited data format, each record comprising data arranged in at least one of the fields, the incoming byte stream further comprising a plurality of record delimiter characters, wherein the record delimiter characters define a plurality of boundaries between the records;
 wherein the outgoing byte stream comprises the records of the incoming byte stream arranged in the fixed field format, wherein the data characters of the received byte stream are arranged in the fixed-size fields and stripped of the field delimiter characters, the record delimiter characters, and the shield characters; 
 wherein the shield character mask distinguishes between bytes in the received byte stream that may include field delimiter characters and/or record delimiter characters and bytes in the received byte stream that do not include field delimiter characters or record delimiter characters; and 
 wherein the second processing module is further configured to identify the record delimiter characters in the received byte stream based on the shield character mask. 
 
     
     
       26. The apparatus of  claim 21  further comprising:
 another processor that is configured to selectively target a field of the outgoing byte stream for processing without analyzing the data characters of the outgoing byte stream. 
 
     
     
       27. The apparatus of  claim 26  wherein the another processor is further configured to perform a field-specific data processing operation on the selectively targeted field of the outgoing byte stream. 
     
     
       28. The apparatus of  claim 27  wherein the field-specific data processing operation comprises a data quality checking operation as part of an extract, transfer, load (ETL) procedure. 
     
     
       29. The apparatus of  claim 21  wherein the pipeline is deployed on a reconfigurable logic device. 
     
     
       30. The apparatus of  claim 21  wherein the pipeline is deployed on a GPU. 
     
     
       31. The apparatus of  claim 21  wherein the pipeline is further configured to process a plurality of bytes of the received byte stream per clock cycle. 
     
     
       32. The apparatus of  claim 21  wherein the delimited data format is a comma separated value (CSV) format. 
     
     
       33. The apparatus of  claim 21  wherein the first processing module comprises a state machine that includes (1) a first state that will mark the shield character mask to identify a byte as a candidate to be a field delimiter and (2) a second state that will mark the shield character mask to identify a byte as not a candidate to be a field delimiter;
 wherein the state machine is configured to process the bytes of the byte stream and controllably transition between the first state and the second state for the processed bytes of the byte stream based on a detection for each byte in the byte stream as to whether it matches the shield character; and 
 wherein the state machine is further configured to produce the shield character mask as the bytes are processed therethrough. 
 
     
     
       34. The apparatus of  claim 33  wherein the state machine is further configured to controllably transition between the first and second states by toggling between the first and second states on each detection of a byte in the byte stream that matches the shield character. 
     
     
       35. The apparatus of  claim 33  wherein the pipeline is further configured to associate bytes of the byte stream with corresponding portions of the shield character mask, and wherein the shield character mask portions comprise a plurality of flags that indicate whether their associated bytes in the byte stream are candidates to be a field delimiter. 
     
     
       36. The apparatus of  claim 35  wherein the second processing module is further configured to:
 determine which bytes of the byte stream are candidates to be a field delimiter based on their corresponding flags in shield character mask; 
 compare the bytes determined to be field delimiter candidates with the field delimiter character to determine whether there is a match; and 
 identify the field delimiter characters based on matches found by the comparisons. 
 
     
     
       37. The apparatus of  claim 36  wherein the second processing module comprises combinatorial AND logic that combines the bytes of the byte stream with their corresponding flags in the shield character mask to determine which bytes of the byte stream are candidates to be a field delimiter. 
     
     
       38. The apparatus of  claim 21  wherein the pipeline is further configured to associate bytes of the byte stream with corresponding portions of the shield character mask, wherein the shield character mask portions comprise a plurality of flags that indicate whether their associated bytes in the byte stream are candidates to be a field delimiter. 
     
     
       39. The apparatus of  claim 38  wherein the second processing module is further configured to:
 determine which bytes of the byte stream are candidates to be a field delimiter based on their corresponding flags in shield character mask; 
 compare the bytes determined to be field delimiter candidates with the field delimiter character to determine whether there is a match; and 
 identify the field delimiter characters based on matches found by the comparisons. 
 
     
     
       40. The apparatus of  claim 38  wherein the first processing module comprises a state machine that processes the byte stream to produce the flags for the shield character mask.