Barrel compactor system, method and device

• US 10,581,455 B2
• Filed: 03/09/2018
• Issued: 03/03/2020
• Est. Priority Date: 03/31/2015
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Theivendran, Premshanth, Wang, Weihuang, Hotha, Sowmya, Atluri, Srinath
• Primary Examiner(s): Zhao, Wei
• Application Number:
  US15/917,284
• Publication Number:
  US 20180198462A1
• Time in Patent Office: 725 Days
• CPC Class Codes: H03M 7/3059 Digital compression and data reduction techniques where the original information is represented by a subset or similar information, e.g. lossy compression
• CPC Class Codes: H03M 7/6011 Encoder aspects

Abstract

A packet processing system having a barrel compactor that extracts a desired data subset from an input dataset (e.g. an incoming packet). The barrel compactor is able to selectively shift one or more of the input data units of the input dataset based on individual shift values for those data units. Additionally, in some embodiments one or more of the data units are able to be logically combined to produce a desired logical output unit.

Claims

1. A barrel compactor system for extracting a subset of data from a plurality of data units that together form an input dataset, the system comprising:

a data unit shift generator that generates a discrete shift value for at least one of the data units within the subset of the input dataset; and

a barrel compactor comprising a plurality of logic cells arranged in an array, wherein the barrel compactor receives the input dataset, and shifts the at least one of the data units of the subset based on the discrete shift value such that the subset is in a different position within the input dataset.

2. The system of claim 1, wherein when in the different position within the input dataset, all of the data units of the subset are adjacent to each other.

3. The system of claim 2, wherein when in the different position within the input dataset, a rightmost data unit of the subset is in a rightmost position of the input dataset or a leftmost data unit of the subset is in a leftmost position of the input dataset.

4. The system of claim 3, wherein the array comprises a plurality of rows and a column for each of the plurality of data units of the input dataset, wherein the logic cells of each of the columns are coupled together in series by a plurality of data pass lines.

5. The system of claim 4, wherein for one or more of the rows of one or more of the columns, each of the logic cells of the one or more rows of the one or more columns is coupled with the logic cell of the next row of a different one of the columns via a data shift line.

6. The system of claim 5, wherein the different one of the columns is a predetermined number of columns away from the column including the logic cell of the one or more rows of the one or more columns.

7. The system of claim 6, wherein the predetermined number of columns away is the same for all of the logic cells in the same one of the rows.

8. The system of claim 7, wherein the barrel compactor receives the input dataset by inputting a different one of the data units with each of the columns such that the input dataset is received by the array in parallel, and further wherein each of the shift values is transmitted through the array along with the associated one of the data units.

9. The system of claim 8, wherein upon receiving one of the data units and the associated shift value from either one of the shift lines or one of the pass lines during a cycle, each of the logic cells:

transmit the data unit and the associated shift value down one of the pass lines to the next logic cell of the column if the shift value does not indicate a shift is necessary by the row that the logic cell is a part of; and

transmit the data unit and the associated shift value to the logic cell of the next row of the different one of the columns via the data shift line if the shift value indicates that a shift is necessary by the row that the logic cell is a part of.

10. The system of claim 9, further comprising a data subset identifier that generates a qualifier value for each of the data units of the input dataset.

11. The system of claim 10, wherein the qualifier value indicates if the data unit is a part of the subset, wherein each of the qualifier values is transmitted through the array along with the associated one of the data units.

12. The system of claim 11, wherein upon receiving both one of the data units and the associated shift value from one of the shift lines and one of the data units and the associated shift value from one of the pass lines during the same cycle, each of the logic cells:

discard the one of the data units and the associated shift value from the one of the pass lines; and

select the one of the data units and the associated shift value from the one of the shift lines for transmission based on the associated shift value.

13. The system of claim 11, wherein upon receiving both one of the data units, the associated shift value and the associated qualifier value from one of the shift lines and one of the data units, the associated shift value and the associated qualifier value from one of the pass lines during the same cycle, each of the logic cells:

discard the one of the data units, the associated shift value and the associated qualifier value from the one of the pass lines if the associated qualifier value from the one of the pass lines indicates that the one of the data units from the one of the pass lines is not a part of the subset;

discard the one of the data units, the associated shift value and the associated qualifier value from the one of the shift lines if the associated qualifier value from the one of the shift lines indicates that the one of the data units from the one of the shift lines is not a part of the subset;

if the associated qualifier value from the one of the pass lines indicates that the one of the data units from the one of the pass lines is a part of the subset, select the one of the data units, the associated shift value and the associated qualifier value from the one of the pass lines for transmission based on the associated shift value from the one of the pass lines; and

if the associated qualifier value from the one of the shift lines indicates that the one of the data units from the one of the shift lines is a part of the subset, select the one of the data units, the associated shift value and the associated qualifier value from the one of the shift lines for transmission based on the associated shift value from the one of the shift lines.

14. The system of claim 12, wherein the data shift unit generator inserts a zero in a location between one or more of the data units of the subset as organized in the different position by reducing the shift values of all of the data units to either the right or the left of the location by one.

15. The system of claim 14, wherein each of the logic cells comprise a multiplexor.

16. The system of claim 15, wherein the data unit shift generator generates the shift value for each of the data units of the subset based on the qualifier values of the plurality of data units.

17. The system of claim 16, wherein the data unit shift generator generates the shift value for each of the data units of the subset based on the qualifier values of the plurality of data units by:

using the qualifier values to identify the data units that are a part of the subset;

calculating a first number of the data units that are between one side of the input dataset and a closest one of the data units of the subset to the one side; and

for each gap between one of the data units of the subset and a next of the data units of the subset, calculating a gap size that is equal to a number of the data units within the gap.

18. The system of claim 17, wherein the data unit shift generator determines the shift value of each of the data units of the subset by summing the first number and the gap size of each of the gaps between the data unit and the one side of the input dataset.

19. The system of claim 18, wherein each of the data units is selected from the group consisting of a bit, a byte or a word.

20. The system of claim 19, wherein, for each of the rows of the array, each of the shift values indicate whether a shift is necessary for the row.

21. A barrel compactor for extracting a subset of data from a plurality of data units that together form an input dataset, the barrel compactor comprising a plurality of logic cells arranged in an array, wherein at least one of the data units of the subset has a discrete corresponding shift value and the barrel compactor shifts the at least one of the data units of the subset based on the discrete shift value, wherein each of the plurality of logic cells are implemented via a non-transitory computer-readable medium.

22. The barrel compactor of claim 21, wherein when in the different position within the input dataset, all of the data units of the subset are adjacent to each other.

23. The barrel compactor of claim 22, wherein when in the different position within the input dataset, a rightmost data unit of the subset is in a rightmost position of the input dataset or a leftmost data unit of the subset is in a leftmost position of the input dataset.

24. The barrel compactor of claim 23, wherein the array comprises a plurality of rows and a column for each of the plurality of data units of the input dataset, wherein the logic cells of each of the columns are coupled together in series by a plurality of data pass lines.

25. The barrel compactor of claim 24, wherein for one or more of the rows of one or more of the columns, each of the logic cells of the one or more rows of the one or more columns is coupled with the logic cell of the next row of a different one of the columns via a data shift line.

26. The barrel compactor of claim 25, wherein the different one of the columns is a predetermined number of columns away from the column including the logic cell of the one or more rows of the one or more columns.

27. The barrel compactor of claim 26, wherein the predetermined number of columns away is the same for all of the logic cells in the same one of the rows.

28. The barrel compactor of claim 27, wherein the barrel compactor receives the input dataset by inputting a different one of the data units with each of the columns such that the input dataset is received by the array in parallel, and further wherein each of the shift values is transmitted through the array by the logic cells along with the associated one of the data units.

29. The barrel compactor of claim 28, wherein upon receiving one of the data units and the associated shift value from either one of the shift lines or one of the pass lines during a cycle, each of the logic cells:

transmit the data unit and the associated shift value down one of the pass lines to the next logic cell of the column if the shift value does not indicate a shift is necessary by the row that the logic cell is a part of; and

transmit the data unit and the associated shift value to the logic cell of the next row of the different one of the columns via the data shift line if the shift value indicates that a shift is necessary by the row that the logic cell is a part of.

30. The barrel compactor of claim 29, wherein each of the data units of the input dataset have a qualifier value that indicates if the data unit is a part of the subset.

31. The barrel compactor of claim 30, wherein each of the qualifier values is transmitted by the logic cells through the array along with the associated one of the data units.

32. The barrel compactor of claim 31, wherein upon receiving both one of the data units and the associated shift value from one of the shift lines and one of the data units and the associated shift value from one of the pass lines during the same cycle, each of the logic cells:

discard the one of the data units and the associated shift value from the one of the pass lines; and

select the one of the data units and the associated shift value from the one of the shift lines for transmission based on the associated shift value.

33. The barrel compactor of claim 31, wherein upon receiving both one of the data units, the associated shift value and the associated qualifier value from one of the shift lines and one of the data units, the associated shift value and the associated qualifier value from one of the pass lines during the same cycle, each of the logic cells:

discard the one of the data units, the associated shift value and the associated qualifier value from the one of the pass lines if the associated qualifier value from the one of the pass lines indicates that the one of the data units from the one of the pass lines is not a part of the subset;

discard the one of the data units, the associated shift value and the associated qualifier value from the one of the shift lines if the associated qualifier value from the one of the shift lines indicates that the one of the data units from the one of the shift lines is not a part of the subset;

if the associated qualifier value from the one of the pass lines indicates that the one of the data units from the one of the pass lines is a part of the subset, select the one of the data units, the associated shift value and the associated qualifier value from the one of the pass lines for transmission based on the associated shift value from the one of the pass lines; and

if the associated qualifier value from the one of the shift lines indicates that the one of the data units from the one of the shift lines is a part of the subset, select the one of the data units, the associated shift value and the associated qualifier value from the one of the shift lines for transmission based on the associated shift value from the one of the shift lines.

34. The barrel compactor of claim 32, wherein the barrel compactor inserts a zero in a location between one or more of the data units of the subset as organized in the different position by reducing the shift values of all of the data units to either the right or the left of the location by one.

35. The barrel compactor of claim 34, wherein each of the logic cells comprise a multiplexor.

36. The barrel compactor of claim 35, wherein the barrel compactor generates the shift value for each of the data units of the subset based on the qualifier values of the plurality of data units.

37. The barrel compactor of claim 36, wherein the barrel compactor generates the shift value for each of the data units of the subset based on the qualifier values of the plurality of data units by:

using the qualifier values to identify the data units that are a part of the subset;

calculating a first number of the data units that are between one side of the input dataset and a closest one of the data units of the subset to the one side; and

for each gap between one of the data units of the subset and a next of the data units of the subset, calculating a gap size that is equal to a number of the data units within the gap.

38. The barrel compactor of claim 37, wherein the barrel compactor determines the shift value of each of the data units of the subset by summing the first number and the gap size of each of the gaps between the data unit and the one side of the input dataset.

39. The barrel compactor of claim 38, wherein each of the data units is selected from the group consisting of a bit, a byte or a word.

40. The barrel compactor of claim 39, wherein, for each of the rows of the array, each of the shift values indicate whether a shift is necessary for the row.

41. A method of extracting a subset of data from a plurality of data units that together form an input dataset, the method comprising:

receiving the input dataset with a barrel compactor comprising a plurality of logic cells arranged in an array; and

shifting one or more of the data units of the subset with the barrel compactor such that the subset is in a different position within the input dataset, wherein at least one of the data units of the subset has a discrete corresponding shift value the barrel compactor shifts the at least one of the data units of the subset based on the discrete shift value.

42. The method of claim 41, wherein when in the different position within the input dataset, all of the data units of the subset are adjacent to each other.

43. The method of claim 42, wherein when in the different position within the input dataset, a rightmost data unit of the subset is in a rightmost position of the input dataset or a leftmost data unit of the subset is in a leftmost position of the input dataset.

44. The method of claim 43, wherein the array comprises a plurality of rows and a column for each of the plurality of data units of the input dataset, wherein the logic cells of each of the columns are coupled together in series by a plurality of data pass lines.

45. The method of claim 44, wherein for one or more of the rows of one or more of the columns, each of the logic cells of the one or more rows of the one or more columns is coupled with the logic cell of the next row of a different one of the columns via a data shift line.

46. The method of claim 45, wherein the different one of the columns is a predetermined number of columns away from the column including the logic cell of the one or more rows of the one or more columns.

47. The method of claim 46, wherein the predetermined number of columns away is the same for all of the logic cells in the same one of the rows.

48. The method of claim 47, wherein the barrel compactor receives the input dataset by inputting a different one of the data units with each of the columns such that the input dataset is received by the array in parallel, and further wherein each of the shift values is transmitted through the array by the logic cells along with the associated one of the data units.

49. The method of claim 48, further comprising, for each of the logic cells, upon receiving one of the data units and the associated shift value from either one of the shift lines or one of the pass lines during a cycle:

transmitting with the logic cell the data unit and the associated shift value down one of the pass lines to the next logic cell of the column if the shift value does not indicate a shift is necessary by the row that the logic cell is a part of; and

transmitting with the logic cell the data unit and the associated shift value to the logic cell of the next row of the different one of the columns via the data shift line if the shift value indicates that a shift is necessary by the row that the logic cell is a part of.

50. The method of claim 49, wherein each of the data units of the input dataset have a qualifier value that indicates if the data unit is a part of the subset.

51. The method of claim 50, wherein each of the qualifier values is transmitted by the logic cells through the array along with the associated one of the data units.

52. The method of claim 51, further comprising, with each of the logic cells, upon receiving both one of the data units and the associated shift value from one of the shift lines and one of the data units and the associated shift value from one of the pass lines during the same cycle:

discarding with the logic cell the one of the data units and the associated shift value from the one of the pass lines; and

selecting with the logic cell the one of the data units and the associated shift value from the one of the shift lines for transmission based on the associated shift value.

53. The method of claim 51, further comprising, for each of the logic cells, upon receiving both one of the data units, the associated shift value and the associated qualifier value from one of the shift lines and one of the data units, the associated shift value and the associated qualifier value from one of the pass lines during the same cycle:

discarding with the logic cell the one of the data units, the associated shift value and the associated qualifier value from the one of the pass lines if the associated qualifier value from the one of the pass lines indicates that the one of the data units from the one of the pass lines is not a part of the subset;

discarding with the logic cell the one of the data units, the associated shift value and the associated qualifier value from the one of the shift lines if the associated qualifier value from the one of the shift lines indicates that the one of the data units from the one of the shift lines is not a part of the subset;

if the associated qualifier value from the one of the pass lines indicates that the one of the data units from the one of the pass lines is a part of the subset, selecting with the logic cell the one of the data units, the associated shift value and the associated qualifier value from the one of the pass lines for transmission based on the associated shift value from the one of the pass lines; and

if the associated qualifier value from the one of the shift lines indicates that the one of the data units from the one of the shift lines is a part of the subset, selecting with the logic cell the one of the data units, the associated shift value and the associated qualifier value from the one of the shift lines for transmission based on the associated shift value from the one of the shift lines.

54. The method of claim 52, further comprising inserting with the barrel compactor a zero in a location between one or more of the data units of the subset as organized in the different position by reducing the shift values of all of the data units to either the right or the left of the location by one.

55. The method of claim 54, wherein each of the logic cells comprise a multiplexor.

56. The method of claim 55, further comprising generating the shift value for each of the data units of the subset with the barrel compactor based on the qualifier values of the plurality of data units.

57. The method of claim 56, wherein the barrel compactor generates the shift value for each of the data units of the subset based on the qualifier values of the plurality of data units by:

using the qualifier values to identify the data units that are a part of the subset;

calculating a first number of the data units that are between one side of the input dataset and a closest one of the data units of the subset to the one side; and

for each gap between one of the data units of the subset and a next of the data units of the subset, calculating a gap size that is equal to a number of the data units within the gap.

58. The method of claim 57, wherein the barrel compactor determines the shift value of each of the data units of the subset by summing the first number and the gap size of each of the gaps between the data unit and the one side of the input dataset.

59. The method of claim 58, wherein each of the data units is selected from the group consisting of a bit, a byte or a word.

60. The method of claim 59, wherein, for each of the rows of the array, each of the shift values indicate whether a shift is necessary for the row.