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

• US 10,621,192 B2
• Filed: 04/17/2017
• Issued: 04/14/2020
• Est. Priority Date: 10/23/2012
• Status: Active Grant

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Ip Reservoir, LLC
• Inventors: Henrichs, Michael John, Lancaster, Joseph M., Chamberlain, Roger Dean, White, Jason R., Sprague, Kevin Brian, Tidwell, Terry
• Primary Examiner(s): Kyle, Tamara T
• Assistant Examiner(s): Hoffler, Raheem
• Application Number:
  US15/489,065
• Publication Number:
  US 20170220655A1
• Time in Patent Office: 1,093 Days
• Field of Search: 707602
• CPC Class Codes: G06F 16/254 Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G16H 10/60 for patient-specific data, e.g. for electronic patient records

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.

Claims

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.