Method and apparatus for accelerated record layout detection

• US 10,133,802 B2
• Filed: 04/23/2015
• Issued: 11/20/2018
• Est. Priority Date: 10/23/2012
• Status: Active Grant

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Ip Reservoir, LLC
• Inventors: Lancaster, Joseph M., Sprague, Kevin Brian
• Primary Examiner(s): Uddin, Md I
• Application Number:
  US14/694,595
• Publication Number:
  US 20150310078A1
• Time in Patent Office: 1,307 Days
• Field of Search: 707705, 707736, 707756, 707602, 707709, 707755
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 21/71 to assure secure computing or processing of information

Abstract

Various methods and apparatuses are described for performing high speed translations of data. In an example embodiment, record layout detection can be performed for data. In another example embodiment, data pivoting prior to field-specific data processing can be performed.

Claims

1. An apparatus for processing a record to determine its record layout, the apparatus comprising:

a hardware record layout detector for processing a plurality of records, the records comprising data arranged in a format and exhibiting any of a plurality of different record layouts within the format, wherein the hardware record layout detector is deployed on at least one of a reconfigurable logic device, a graphics processing unit (GPU), a multi-core processor, and a cell processor, wherein the hardware record layout detector comprises (1) a plurality of data analysis components arranged in parallel, and (2) logic downstream from the parallel data analysis components; and

a memory;

wherein the parallel data analysis components are configured to analyze the records in parallel, each parallel data analysis component configured to (1) test data in the records against a corresponding condition, and (2) output data indicative of whether the tested data satisfies the corresponding condition, wherein the corresponding conditions for the parallel data analysis components in the aggregate serve as criteria for determining whether the record exhibits any of a plurality of different record layouts, and wherein the corresponding conditions include byte offsets that identify record portions to be processed by different ones of the parallel data analysis components;

wherein the memory is configured to store a configuration table, the configuration table configured to store data representative of the corresponding conditions;

wherein the hardware record layout detector is further configured to define the corresponding conditions for the parallel data analysis components based on the corresponding conditions data in the configuration table; and

wherein the logic is configured to process the output data from the parallel data analysis components to determine, for each of a plurality of the records, whether that record exhibits a record layout from among the plurality of different record layouts;

wherein the hardware record layout detector, in response to a determination that the record exhibits a record layout from among the plurality of different record layouts, is further configured to associate the record with data indicative of the determined record layout; and

wherein the hardware record layout detector is adaptable to detect a new record layout in response to an update to the configuration table that adds corresponding conditions for the new record layout to the configuration table.

2. The apparatus of claim 1 wherein the data analysis components and the logic are deployed on a reconfigurable logic device.

3. The apparatus of claim 2 wherein the records comprise a plurality of records having a fixed field format.

4. The apparatus of claim 2 wherein the records comprise a plurality of records having a mapped field format.

5. The apparatus of claim 4 wherein the mapped field format is a mapped variable field format.

6. The apparatus of claim 2 wherein the records comprise a plurality of records having a delimited data format.

7. The apparatus of claim 2 wherein the reconfigurable logic device is configured to stream the records through the data analysis components and the logic such that the data analysis components and the logic perform their operations on the streaming records.

8. The apparatus of claim 7 further comprising:

a first set of the data analysis components and the logic arranged as a first record layout detection module for records having a first format;

a second set of the data analysis components and the logic arranged as a second record layout detection module for records having a second format; and

a multiplexer configured to selectively deliver records to the first record layout detection module or the second record layout detection module based on the formats for the records.

9. The apparatus of claim 8 wherein the first format comprises a member of the group consisting of a fixed field format, a mapped field format, and a delimited data format;

and

wherein the second format comprises a member of the group consisting of a fixed field format, a mapped field format, and a delimited data format such that the second format is not the first format.

10. The apparatus of claim 7 further comprising:

a first set of the data analysis components and the logic arranged as a first record layout detection module for records having a first format;

a second set of the data analysis components and the logic arranged as a second record layout detection module for records having a second format;

a third set of the data analysis components and the logic arranged as a third record layout detection module for records having a third format; and

a multiplexer configured to selectively deliver records to the first record layout detection module, the second record layout detection module, or the third record layout detection module based on the formats for the records.

11. The apparatus of claim 10 wherein the first format comprises a fixed field format, wherein the second format comprises a mapped field format, and wherein the third format comprises a delimited data format.

12. The apparatus of claim 1 wherein each of a plurality of the data analysis components comprises a data range collector component and a data checker component, the data range collector component configured to identify portions of a record to be tested against a condition, and the data checker component configured to test the identified portion of the record against the condition.

13. The apparatus of claim 12 wherein each of a plurality of the data range collector components is further configured to identify the record portion based on a byte offset.

14. The apparatus of claim 13 wherein a plurality of the data range collector components are configured with different byte offsets such that those data range collector components identify different record portions based on the different byte offsets.

15. The apparatus of claim 14 wherein the configuration table is further configured to store the different byte offsets, and wherein the hardware logic detector is further configured to define the byte offsets for the data range collector components based on the different byte offsets in the configuration table.

16. The apparatus of claim 12 wherein each of a plurality of the data range collector components is further configured to identify the record portion based on a field identifier.

17. The apparatus of claim 16 wherein a plurality of the data range collector components are configured with different field identifiers such that those data range collector components identify different record portions based on the different field identifiers.

18. The apparatus of claim 17 wherein the configuration table is further configured to store the different field identifiers, and wherein the hardware logic detector is further configured to define the field identifiers for the data range collector components based on the different field identifiers in the configuration table.

19. The apparatus of claim 12 wherein the data range collector component and the data checker component of each data analysis unit are configured as a predicate evaluation logic pipeline such that the data range collector component and the data checker component of each predicate evaluation logic pipeline are configured to operate simultaneously.

20. The apparatus of claim 1 wherein the data analysis components and the logic are deployed on a field programmable gate array (FPGA).

21. The apparatus of claim 1 wherein the hardware record layout detector is further configured to perform its operations on records that are streamed through the hardware record layout detector.

22. The apparatus of claim 1 wherein the corresponding conditions include field identifiers that identify record portions to be processed by different ones of the parallel data analysis components.

23. The apparatus of claim 1 wherein the different record layouts have different sets of corresponding conditions that must be satisfied in order to identify a record as having one of the different record layouts, and wherein the logic comprises combinatorial logic configured to (1) determine, for each record layout, whether all of the corresponding conditions for that record layout are satisfied.

24. A method comprising:

adapting a hardware record layout detector to detect a new record layout in streaming records, wherein the hardware record layout detector is deployed on at least one of a reconfigurable logic device, a graphics processing unit (GPU), a multi-core processor, and a cell processor, wherein the hardware record layout detector comprises (1) a plurality of data analysis components arranged in parallel, and (2) logic downstream from the parallel data analysis components, and wherein the adapting step comprises;

changing a configuration table in a memory, wherein the configuration table comprises data that defines a plurality of portions of records to be tested to determine their record layouts, wherein the portion definition data is indicative of a plurality of byte offsets for record portions to be tested against a predicate for a record layout test, and wherein the changing step comprises changing the portion definition data in the configuration table; and

modifying the hardware record layout detector to detect the new record layout based on the changed configuration table;

the modified hardware record layout detector processing the streaming records to determine whether any of the streaming records exhibit the new record layout, wherein the processing step comprises;

the parallel data analysis components analyzing the streaming records in parallel, wherein the analyzing step comprises each parallel data analysis component (1) testing data in the streaming records against a corresponding condition that is defined based on data in the changed configuration table, and (2) outputting data indicative of whether the tested data satisfies the corresponding condition, wherein a plurality of the corresponding conditions for the parallel data analysis components in the aggregate serve as criteria for determining whether the record exhibits the new record layout; and

the logic processing the output data from the parallel data analysis components to determine whether the any of the streaming records exhibit the new record layout.

25. The method of claim 24 wherein the hardware record layout detector is deployed on a reconfigurable logic device.

26. The method of claim 25 wherein the configuration table further comprises data that defines a plurality of predicates for a record layout test;

and

wherein the changing step comprises changing the predicate data in the configuration table.

27. The method of claim 24 wherein the portion definition data further comprises data that is indicative of a plurality of field identifiers for fields of the records to be tested against a predicate for a record layout test.

28. The method of claim 24 wherein the hardware record layout detector is deployed on a field programmable gate array (FPGA).

29. A method comprising:

streaming a plurality of records through a hardware record layout detector, the records comprising data arranged in a format and exhibiting any of a plurality of different record layouts within the format, wherein the hardware record layout detector is deployed on at least one of a reconfigurable logic device, a graphics processing unit (GPU), a multi-core processor, and a cell processor, and wherein the hardware record layout detector comprises (1) a plurality of data analysis components arranged in parallel, and (2) logic downstream from the parallel data analysis components;

the parallel data analysis components analyzing the streaming records in parallel, wherein the analyzing step comprises each parallel data analysis component (1) testing data in the streaming records against a corresponding condition, and (2) outputting data indicative of whether the tested data satisfies the corresponding condition, wherein the corresponding conditions for the parallel data analysis components in the aggregate serve as criteria for determining whether the records exhibit any of a plurality of different record layouts and wherein the corresponding conditions include byte offsets that identify record portions to be processed by different ones of the parallel data analysis components;

accessing a configuration table from a memory, the configuration table storing data representative of the corresponding conditions;

the hardware record layout detector defining the corresponding conditions for the parallel data analysis components based on the corresponding conditions data in the accessed configuration table;

the logic processing the output data from the parallel data analysis components for each of a plurality of the streaming records to determine which of the different record layouts are exhibited by those streaming records;

the hardware record layout detector, in response to a determination that a streaming record exhibits a record layout from among the plurality of different record layouts, associating that streaming record with data indicative of the determined record layout; and

adapting the hardware record layout detector to detect a new record layout in response to an update to the configuration table that adds corresponding conditions for the new record layout to the configuration table.

30. The method of claim 29 wherein the streaming records comprise a plurality of records that are arranged in a format but exhibit a plurality of different record layouts within the format.

31. The method of claim 29 wherein the corresponding conditions include field identifiers that identify record portions to be processed by different ones of the parallel data analysis components.

32. The method of claim 29 wherein the different record layouts have different sets of corresponding conditions that must be satisfied in order to identify a streaming record as having one of the different record layouts, and wherein the logic processing step comprises the logic applying combinatorial logic to the output data to determine whether all of the corresponding conditions for any of the record layouts are satisfied.

33. The method of claim 29 wherein the hardware record layout detector is deployed on a reconfigurable logic device.

34. The method of claim 33 wherein the reconfigurable logic device comprises a field programmable gate array (FPGA).

35. The method of claim 29 wherein the data of the streaming records comprise a plurality of data characters arranged in the format in a plurality of fields, the method further comprising:

a processor, based on the determined record layout for a streaming record, selectively targeting a field in that streaming record for a data processing operation without analyzing the data characters of that streaming record.

36. The method of claim 35 wherein the streaming records comprise a plurality of record headers and a plurality of field headers, the record headers comprising data indicative of where boundaries exist between a plurality of records in the streaming records, the field headers comprising data indicative of where boundaries exist between the fields in the streaming records, and wherein the selectively targeting step comprises a processor selectively targeting fields in a plurality of the streaming records for the data processing operation based on data in the field headers.

37. The method of claim 35 further comprising:

upstream from the hardware record layout detector, a processor translating the streaming records from a delimited data format to another format; and

wherein the hardware record layout detector operates on the streaming records in the another format.

38. The method of claim 37 wherein the another format comprises at least one of a fixed field format and a mapped field format.