Reformatting Matrices to Improve Computing Efficiency

Patent metadata

Field	Value
Publication number	US-2022012010-A1
Application number	US-202117485455-A
Country	US
Kind code	A1
Filing date	Sep 26, 2021
Priority date	Nov 29, 2018
Publication date	Jan 13, 2022
Grant date	—

Abstract

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.

First claim

What is claimed is:

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 a buffer coupled between each input of the plurality of inputs N and a corresponding input of the sorting network; 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; 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.

Assignees

• IBM

Inventors

• Kumar Manoj
• Pattnaik Pratap C
• Ekanadham Kattamuri
• Tseng Jessica
• Moreira Jose E

Classifications

• G06F7/26 Primary

  the sorted data being recorded on the original record carrier within the same space in which the data had been recorded prior to their sorting, without using intermediate storage · CPC title

• G06F7/24

  Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers {sorting methods in general}(G06F7/36 takes precedence) · CPC title

• G06F17/16

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title

• G06F7/78

  for changing the order of data flow, e.g. matrix transposition or LIFO buffers; Overflow or underflow handling therefor · CPC title

• G06F7/08 Primary

  Sorting, i.e. grouping record carriers in numerical or other ordered sequence according to the classification of at least some of the information they carry (by merging two or more sets of carriers in ordered sequence G06F7/16) · CPC title