Superimposing butterfly network controls for pattern combinations
A multilayer butterfly network is shown that is operable to transform and align a plurality of fields from an input to an output data stream. Many transformations are possible with such a network which may include separate control of each multiplexer. This invention supports a limited set of multiplexer control signals, which enables a similarly limited set of data transformations. This limited capability is offset by the reduced complexity of the multiplexor control circuits. This invention used precalculated inputs and simple combinatorial logic to generate control signals for the butterfly network. Controls are independent for each layer and therefore are dependent only on the input and output patterns. Controls for the layers can be calculated in parallel.
1 . A device comprising:
a control circuit configured to:
receive a first set of control signals associated with a first transformation;
receive a second set of control signals associated with a second transformation;
determine a third set of control signals associated with a combination of the first transformation and the second transformation; and
select between providing the first set of control signals, the second set of control signals, or the third set of control signals as a selected set of control signals; and
a data transformation circuit coupled to the control circuit and configured to:
receive a first set of data;
receive the selected set of control signals, wherein the selected set of control signals is associated with a transformation; and
based on the selected set of control signals, perform the transformation on the first set of data to produce a second set of data.
2 . The device of claim 1 , wherein the data transformation circuit includes:
an input configured to receive the first set of data;
a first set of multiplexers coupled to the input of the data transformation circuit; and
a second set of multiplexers coupled to the first set of multiplexers.
3 . The device of claim 2 , wherein:
the first set of multiplexers is configured to receive a first portion of the selected set of control signals;
the second set of multiplexers is configured to receive a second portion of the selected set of control signals; and
the control circuit includes:
a first set of logic configured to:
receive a first portion of the first set of control signals;
receive a first portion of the second set of control signals;
determine a first portion of the third set of control signals; and
select between providing the first portion of the first set of control signals, the first portion of the second set of control signals, or the first portion of the third set of control signals to the data transformation circuit as the first portion of the selected set of control signals; and
a second set of logic configured to:
receive a second portion of the first set of control signals;
receive a second portion of the second set of control signals;
determine a second portion of the third set of control signals; and
select between providing the second portion of the first set of control signals, the second portion of the second set of control signals, or the second portion of the third set of control signals to the data transformation circuit as the second portion of the selected set of control signals.
4 . The device of claim 3 , wherein the first portion of the selected set of control signals is exactly one bit and the second portion of the selected set of control signals is exactly one bit.
5 . The device of claim 2 , wherein first set of multiplexers and the second set of multiplexers include 2:1 multiplexers.
6 . The device of claim 2 , wherein:
each multiplexer of the first set of multiplexers is configured to receive a first bit of the selected set of control signals; and
each multiplexer of the second set of multiplexers is configured to receive a second bit of the selected set of control signals.
7 . The device of claim 2 , wherein:
the first set of multiplexers is configured to selectably switch bit positions of a first subset of the first set of data with a second subset of the first set of data; and
the second set of multiplexers is configured to:
selectably switch bit positions of a first subset of the first subset of the data with a second subset of the first subset of the data; and
selectably switch bit positions of a first subset of the second subset of the data with a second subset of the second subset of the data.
8 . The device of claim 7 , wherein, in response to the transformation being a shuffle transformation, the selected set of control signals specifies that:
the first set of multiplexers is not to switch bit positions of the first subset of the data with the second subset of the data;
the second set of multiplexers is not to switch bit positions of the first subset of the first subset of the data with the second subset of the first subset of the data; and
the second set of multiplexers is not to switch bit positions of the first subset of the second subset of the data with the second subset of the second subset of the data.
9 . The device of claim 7 , wherein, in response to the transformation being a rotate transformation, the selected set of control signals specifies that:
the first set of multiplexers is to switch bit positions of the first subset of the data with the second subset of the data;
the second set of multiplexers is not to switch bit positions of the first subset of the first subset of the data with the second subset of the first subset of the data; and
the second set of multiplexers is not to switch bit positions of the first subset of the second subset of the data with the second subset of the second subset of the data.
10 . The device of claim 7 , wherein, in response to the transformation being a rotate and shuffle transformation, the selected set of control signals specifies that:
the first set of multiplexers is to switch bit positions of the first subset of the data with the second subset of the data;
the second set of multiplexers is not to switch bit positions of the first subset of the first subset of the data with the second subset of the first subset of the data; and
the second set of multiplexers is not to switch bit positions of the first subset of the second subset of the data with the second subset of the second subset of the data.
11 . The device of claim 1 , wherein the first transformation includes a shuffle transformation, a replicate transformation, or a rotate transformation.
12 . The device of claim 1 , wherein the control circuit includes exclusive or logic configured to receive a first bit of the first set of control signals and a first bit of the second set of control signals and provide a first bit of the third set of control signals.
13 . The device of claim 12 , wherein the control circuit includes a multiplexer coupled to the exclusive or logic and configured to:
receive the first bit of the first set of control signals, the first bit of the second set of control signals, and the first bit of the third set of control signals; and
provide a first bit of the selected set of control signals to the data transformation circuit based on either the first bit of the first set of control signals, the first bit of the second set of control signals, or the first bit of the third set of control signals.
14 . A device comprising:
a processor core;
a cache memory configured to store a first set of data; and
a circuit coupled between the processor core and the cache memory that includes:
a memory interface coupled to the cache memory and configured to retrieve the first set of data from the cache memory;
a control circuit configured to:
receive a first set of control signals associated with a first transformation;
receive a second set of control signals associated with a second transformation;
determine a third set of control signals associated with a combination of the first transformation and the second transformation; and
select between providing the first set of control signals, the second set of control signals, or the third set of control signals as a selected set of control signals;
a data transformation circuit coupled to the control circuit and to the memory interface and configured to:
receive the first set of data;
receive the selected set of control signals, wherein the selected set of control signals is associated with a transformation; and
based on the selected set of control signals, perform the transformation on the first set of data to produce a second set of data; and
a register coupled between the data transformation circuit and the processor core and configured to provide the second set of data to the processor core.
15 . The device of claim 14 , wherein the data transformation circuit includes:
an input configured to receive the first set of data;
a first set of multiplexers coupled to the input of the data transformation circuit; and
a second set of multiplexers coupled to the first set of multiplexers.
16 . The device of claim 14 , wherein the first set of multiplexers is configured to receive exactly one bit of the selected set of control signals and the second set of multiplexers is configured to receive exactly one bit of the selected set of control signals.
17 . The device of claim 14 , wherein:
the first set of multiplexers is configured to selectably switch bit positions of a first subset of the first set of data with a second subset of the first set of data; and
the second set of multiplexers is configured to:
selectably switch bit positions of a first subset of the first subset of the data with a second subset of the first subset of the data; and
selectably switch bit positions of a first subset of the second subset of the data with a second subset of the second subset of the data.
18 . The device of claim 14 , wherein the first transformation includes a shuffle transformation, a replicate transformation, or a rotate transformation.
19 . The device of claim 14 , wherein the control circuit includes exclusive or logic configured to receive a first bit of the first set of control signals and a first bit of the second set of control signals and provide a first bit of the third set of control signals.
20 . The device of claim 19 , wherein the control circuit includes a multiplexer coupled to the exclusive or logic and configured to:
receive the first bit of the first set of control signals, the first bit of the second set of control signals, and the first bit of the third set of control signals; and
provide a first bit of the selected set of control signals to the data transformation circuit based on either the first bit of the first set of control signals, the first bit of the second set of control signals, or the first bit of the third set of control signals.