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 computing device comprising:
a processor;
a memory coupled to the processor;
a switching functional unit having N inputs and M outputs;
a control unit coupled to the processor and the switching functional unit, and configured to provide instructions to:
receive, from the memory, at the N inputs of the switching functional unit, a sectioned array of n records, wherein each record comprises a key-value pair;
in a first stage number operation of the switching functional unit,
for each record:
extract an R number of most significant bits of the key to create a control string for the record; and
sort the record into one of M outputs of the switching functional unit based on the control string; and
store records of the M outputs as M batches, in the memory;
for a total of X stage operations of the switching functional unit, for each next stage number operation, iteratively perform, for each of the M (stage number−1) batches stored in the memory:
receive, from the memory, at the N inputs of the switching functional unit, each record of the batch;
for each record of the batch:
extract a next R number of most significant bits of the key to create a new control string for the record; and
sort the record into one of the M outputs of the switching functional unit based on the new control string; and
store the records of the M outputs as M batches, in the memory.
2. The computing device of claim 1 , wherein the total X stage operations=log M n to sort all n records.
3. The computing device of claim 1 , wherein X is based on a predetermined granularity of a number of records for each batch.
4. The computing device of claim 1 , wherein each control string indicates to which of the M outputs the corresponding record belongs.
5. The computing device of claim 1 , wherein the number R is based on log(M)/log(2).
6. The computing device of claim 1 , wherein a number of bits of a key in a key value pair is based on log(n)/log(2).
7. The computing device of claim 1 , wherein n>M.
8. The computing device of claim 1 , wherein a total of log M n stages of the switching functional unit are used to sort all n records.
9. The computing device of claim 1 , wherein each stage involves M (stage−1) SFU operations of the switching functional unit to sort all records.
10. The computing device of claim 1 , wherein the control unit is further configured to, in a last stage of the X stages of operations, if an R number of previously unextracted number of most significant bits of a key of a key-value pair are not available, extracting a remaining number of most significant bits of the key to create a new control string for a record.
11. A non-transitory computer readable storage medium tangibly embodying a computer readable program code having computer readable instructions that, when executed, causes a computing device to carry out a method of sorting a content of a memory, the method comprising:
receiving, 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:
extracting an R number of most significant bits of a key of the key-value pair to create a control string; and
sorting the record into one of the M outputs of the switching functional unit based on the control string; and
storing 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 performing, for each of the M (stage number−1) batches stored in the memory:
receiving each record of the batch from the memory;
for each record of the batch:
extracting 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
storing the records of the M outputs as a sorted sectioned array of M batches, in the memory.
12. The non-transitory computer readable storage medium of claim 11 , wherein each control string indicates to which of the M outputs the corresponding record belongs.
13. The non-transitory computer readable storage medium of claim 11 , wherein a total of log M n stages of the switching functional unit are used to sort all n records.
14. The non-transitory computer readable storage medium of claim 11 , wherein each stage involves M (stage−1) SFU operations of the switching functional unit to sort all records.