# US 2021/0344361 A1 · Butterfly network on load data return

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0344361 A1
- Document ID: US20210344361A1
- Status: Published application
- Kind: A1
- Application number: 17/378,886
- Filed: 2021-07-19
- Published: 2021-11-04
- Earliest claimed: 2017-07-17
- Assignees: Texas Instruments Incorporated
- Applicants: Texas Instruments Incorporated
- Inventors: Dheera Balasubramanian; Joseph Zbiciak; Duc Quang Bui; Timothy David Anderson
- Web page: https://patentgrep.com/patent/US20210344361A1

## CPC

- G06F 9/30032: {Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE}
- H03M 13/6561: {Parallelized implementations}
- G06F 9/30036: {Instructions to perform operations on packed data, e.g. vector, tile or matrix operations}
- G06F 9/30038: {using a mask}
- G06F 9/38: Concurrent instruction execution, e.g. pipeline or look ahead
- G06F 9/383: {Operand prefetching (cache prefetching G06F12/0862)}
- G06F 9/3891: {organised in groups of units sharing resources, e.g. clusters}
- H03M 13/2789: {Interleaver providing variable interleaving, e.g. variable block sizes}
- H03M 13/276: {Interleaving address generation}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

A method is shown that is operable to transform and align a plurality of fields from an input to an output data stream using a multilayer butterfly or inverse butterfly network. 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.

## Claims

### Claim 1

A device comprising:
a butterfly network that includes:
a set of inputs;
a set of outputs;
a first layer coupled to the set of inputs, wherein the first layer includes a first set of multiplexers; and
a second layer coupled to the first layer, wherein the second layer includes a second set of multiplexers;
a first control circuit having a first control circuit output coupled to a control input of each of the first set of multiplexers; and
a second control circuit having a second control circuit output coupled to a control input of each of the second set of multiplexers.

### Claim 2 (depends on 1)

The device of claim 1, wherein:
the first control circuit and the second control circuit are configured to function in parallel.

### Claim 3 (depends on 1)

The device of claim 1, wherein:
the first control circuit and the second control circuit each have a first input, a second input, and a third input.

### Claim 4 (depends on 3)

The device of claim 3, wherein:
the first input is coupled to a pattern for a shuffle function.

### Claim 5 (depends on 3)

The device of claim 3, wherein:
the second input is coupled to a pattern for a replicate function.

### Claim 6 (depends on 3)

The device of claim 3, wherein:
the third input is coupled to a pattern for a rotate function.

### Claim 7 (depends on 3)

The device of claim 3, wherein:
the first control circuit includes a first multiplexer coupled to the first input, the second input, and the third input;
the first control circuit includes a first exclusive OR (XOR) logic gate, a second XOR logic gate, and a third XOR logic gate;
each of the first, second, and third XOR logic gates is coupled to different combinations of the first input, the second input, and the third input;
the second control circuit includes a second multiplexer coupled to the first input, the second input, and the third input;
the second control circuit includes a fourth exclusive OR (XOR) logic gate, a fifth XOR logic gate, and a sixth XOR logic gate; and
each of the fourth, fifth, and sixth XOR logic gates is coupled to different combinations of the first input, the second input, and the third input.

### Claim 8 (depends on 7)

The device of claim 7, wherein:
the first multiplexer and the second multiplexer are coupled to a control signal corresponding to one of a shuffle function, a replicate function, and a rotate function.

### Claim 9 (depends on 1)

The device of claim 1, wherein:
each input of the set of inputs of the butterfly network is coupled to a plurality of data inputs of the first set of multiplexers; and
each output of the set of outputs of the butterfly network is coupled to a respective output of a respective multiplexer of the second set of multiplexers.

### Claim 10

A method of data transformation comprising:
receiving, by a memory, a request for a set of data from a streaming engine;
transmitting, by the memory, the set of data to the streaming engine;
formatting, by a butterfly network in the streaming engine, the set of data based on a formatting function, wherein the formatting includes:
receiving, at a first layer in the butterfly network, the set of data;
generating, by a first set of multiplexers in the first layer, a first data transformation, wherein each of the first set of multiplexers is configured based on a first configuration associated with the formatting function;
receiving, at a second layer in the butterfly network, the first data transformation; and
generating, by a second set of multiplexers in the second layer, a second data transformation, wherein each of the second set of multiplexers is configured based on a second configuration associated with the formatting function; and
outputting, by the streaming engine, the second data transformation to a processor.

### Claim 11 (depends on 10)

The method of claim 10, wherein:
the formatting is one of a group consisting of:
shuffle, replicate, and rotate.

### Claim 12 (depends on 10)

The method of claim 10, wherein:
the first configuration is stored in a first register; and
the second configuration is stored in a second register.

### Claim 13 (depends on 12)

The method of claim 12, wherein:
the first configuration is retrieved from the first register and applied to the first set of multiplexers prior to the first set of multiplexers receiving at the first layer the set of data; and
the second configuration is retrieved from the second register and applied to the second set of multiplexers prior to the second set of multiplexers receiving at the second layer the first data transformation.

### Claim 14 (depends on 10)

The method of claim 10, wherein:
each of the first set of multiplexers is configured by a first control circuit; and
each of the second set of multiplexers is configured by a second control circuit.

### Claim 15 (depends on 14)

The method of claim 14, wherein:
the first control circuit and the second control circuit each have a first input, a second input, and a third input.

### Claim 16 (depends on 15)

The method of claim 15, wherein:
the first input is coupled to a pattern for a shuffle formatting function;
the second input is coupled to a pattern for a replicate formatting function; and
the third input is coupled to a pattern for a rotate formatting function.

### Claim 17 (depends on 15)

The method of claim 15, wherein:
the first control circuit includes a first multiplexer coupled to the first input, the second input, and the third input;
the first control circuit includes a first exclusive OR (XOR) logic gate, a second XOR logic gate, and a third XOR logic gate;
each of the first, second, and third XOR logic gates is coupled to different combinations of the first input, the second input, and the third input;
the second control circuit includes a second multiplexer coupled to the first input, the second input, and the third input;
the second control circuit includes a fourth exclusive OR (XOR) logic gate, a fifth XOR logic gate, and a sixth XOR logic gate; and
each of the fourth, fifth, and sixth XOR logic gates is coupled to different combinations of the first input, the second input, and the third input.

### Claim 18 (depends on 17)

The method of claim 17, wherein:
the first multiplexer and the second multiplexer are coupled to the formatting function.

### Claim 19

A data transformation system comprising:
a memory storing data;
a streaming engine coupled to the memory to fetch the data; and
a butterfly network to transform the data, wherein the butterfly network includes:
a set of inputs;
a set of outputs;
a plurality of layers of multiplexers, wherein:
a first layer of the plurality of layers of multiplexers is coupled to the set of inputs;
a last layer of the plurality of layers of multiplexers is coupled to the set of outputs; and
each of the plurality of layers of multiplexers is coupled to a respective control circuit configured to control the plurality of layers of multiplexers based on a selected control signal.

### Claim 20 (depends on 19)

The data transformation system of claim 19, wherein:
the data includes N bits and the plurality of layers of multiplexers includes log2 N layers of multiplexers.
