Reformatting matrices to improve computing efficiency
A data ordering device includes a plurality of inputs N and a plurality of outputs M. There is a sorting network coupled between the plurality of inputs N and the plurality of outputs M. There are one or more latches comprising a buffer coupled between each input of the plurality of inputs N and a corresponding input of the sorting network. There are one or more latches comprising a buffer coupled between each output of the plurality of outputs M and a corresponding output of the sorting network. There is an input for a control signal operative to initiate a sorting of data between the plurality of inputs N and the plurality of outputs M. The data ordering device is coupled to a core of a central processing unit.
1 . A data ordering device, comprising:
a plurality of inputs N;
a plurality of outputs M;
a sorting network coupled between the plurality of inputs N and the plurality of outputs M;
one or more latches comprising an input buffer coupled between each input of the plurality of inputs N and a corresponding input of the sorting network;
one or more latches comprising an output buffer coupled between each output of the plurality of outputs M and a corresponding output of the sorting network, wherein the sorting network is coupled between the input buffer and the output buffer;
one or more private vector registers coupled between the plurality of inputs N and the input buffer;
one or more private vector registers coupled between the plurality of outputs M and the output buffer; and
an input for a control signal operative to initiate a sorting of data between the plurality of inputs N and the plurality of outputs M.
2 . The data ordering device of claim 1 , wherein the data ordering device is coupled to a core of a central processing unit.
3 . The data ordering device of claim 1 , wherein the data ordering device is configured to rearrange data across multiple cache lines.
4 . The data ordering device of claim 1 , wherein the data ordering device is coupled to a core of a vector processor.
5 . The data ordering device of claim 1 , wherein the data ordering device is a field programmable gate array (FPGA).
6 . The data ordering device of claim 1 , wherein the data ordering device is part of a computer system configured to provide instructions to the data ordering device as part of a machine instruction set of the computer system.
7 . The data ordering device of claim 1 , wherein the data ordering device is coupled to a control unit and functional units of the central processing unit.
8 . The data ordering device of claim 1 , wherein the data ordering device is configured to:
receive, from a memory, a sectioned array of n records, each record comprising a key-value pair;
in a first stage number operation:
for each record:
extract an R number of most significant bits of a key of the key-value pair to create a control string; and
sort the record into one of the M outputs of the switching functional unit based on the control string; and
store records of the M outputs as a sorted sectioned array of M batches, in the memory;
for a total of X stage operations, for each next stage number operation, iteratively perform, for each of the M (stage number-1) batches stored in the memory:
receive each record of the batch from the memory;
for each record of the batch:
extract a next R number of most significant bits of the key to create a new control string; and
sorting the record into one of the M outputs based on the new control string; and
store the records of the M outputs as a sorted sectioned array of M batches, in the memory.
9 . The data ordering device of claim 8 , wherein each control string indicates to which of the M outputs the corresponding record belongs.
10 . The data ordering device of claim 8 , wherein a total of log M n stages of the switching functional unit are configured to sort all n records.
11 . The data ordering device of claim 8 , wherein each stage involves M (stage-1) SFU operations of the switching functional unit to sort all records.