# US 2021/0279299 A1 · Multiplication of a matrix with an input vector

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

- Number: US 2021/0279299 A1
- Document ID: US20210279299A1
- Status: Published application
- Kind: A1
- Application number: 16/812,540
- Filed: 2020-03-09
- Published: 2021-09-09
- Earliest claimed: 2020-03-09
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Leonidas Georgopoulos; Peter Staar; Michele Dolfi; Christoph Auer; Konstantinos Bekas
- Web page: https://patentgrep.com/patent/US20210279299A1

## CPC

- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G06F 11/3037: {where the computing system component is a memory, e.g. virtual memory, cache (accessing, addressing or allocating within memory systems or architectures G06F12/00; checking stores for correct operation G11C29/00)}
- G06F 11/3409: {for performance assessment}
- G06F 11/3452: {Performance evaluation by statistical analysis}
- G06F 11/3485: {for I/O devices}
- G06F 12/0871: Allocation or management of cache space
- G06F 12/0875: with dedicated cache, e.g. instruction or stack
- G06F 2201/88: Monitoring involving counting
- G06F 2201/885: Monitoring specific for caches
- G06F 2212/1016: Performance improvement
- G06F 2212/1041: Resource optimization
- G06F 2212/454: Vector or matrix data
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Aspects of the present invention disclose a method, computer program product, and system for performing a multiplication of a matrix with an input vector. The method includes one or more processors subdividing a matrix into logical segments, the matrix being given in a sparse-matrix data format. The method further includes one or more processors obtaining one or more test vectors. The method further includes one or more processors performing an optimization cycle. In an additional aspect, performing the optimization cycle further comprises, for each of the test vectors, one or more processors, performing a cache performance test.

## Claims

### Claim 1

A computer-implemented for performing a multiplication of a matrix with an input vector, the method comprising:
subdividing, by one or more processors, a matrix into logical segments, the matrix being given in a sparse-matrix data format;
obtaining, by one or more processors, one or more test vectors; and
performing, by one or more processors, an optimization cycle further comprising:
for each of the test vectors, performing, by one or more processors, a cache performance test, the cache performance test further comprising:
for each of the logical segments, performing, by one or more processors, a test multiplication by providing a respective logical segment and a respective test vector to an input of a matrix-vector multiplication algorithm, and
during the test multiplication of each segment, determining, by one or more processors, a cache performance value of a cache of a processor performing the test multiplication.

### Claim 2 (depends on 1)

The method of claim 1, wherein the optimization cycle further comprises, for each of the logical segments:
determining, by one or more processors, an aggregated cache performance from the cache performance values determined for the respective logical segment; and
assigning, by one or more processors, a weight to each element of the matrix within the respective logical segment, the weight comprising the aggregated cache performance of the logical segment.

### Claim 3 (depends on 2)

The method of claim 2, wherein the optimization cycle further comprises:
performing, by one or more processors, one or more instances of an element swap until the aggregated cache performances of the logical segments are equal within a predefined tolerance interval, the element swap comprising:
selecting, by one or more processors, two of the logical segments for swapping;
interchanging, by one or more processors, one or more pairs of elements between the selected logical segments, the interchange being performed such that a difference between the aggregated cache performances of the selected logical segments, when calculated for each selected segment after the interchange based on the weights of the elements within the segment, has a smaller absolute value than the difference between the aggregated cache performances of the selected segments before the interchange, and
after the interchange, updating, by one or more processors, the aggregated cache performance of each selected segment based on the weights of the elements within the segment.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
after exiting the optimization cycle, for each of the segments, performing, by one or more processors, the multiplication by providing the segment and the input vector to the input of the matrix-vector multiplication algorithm.

### Claim 5 (depends on 3)

The method of claim 3, wherein the assignment of the weight to each element of the matrix and the element swap being performed in response to determining that an optimization criterion is not fulfilled, the optimization criterion comprising a logical expression relating to the aggregated cache performance of at least one of the segments.

### Claim 6 (depends on 3)

The method of claim 3, further comprising:
in response to determining that an iteration criterion is fulfilled, repeating, by one or more processors, the optimization cycle, the iteration criterion being checked after at least one of the determination of the aggregated cache performance for each segment, and the update of the aggregated cache performance for each segment, wherein the iteration criterion comprises a logical expression relating to at least one of the aggregated cache performance of one or more of the segments, and a number of passed iterations.

### Claim 7 (depends on 1)

The method of claim 1, wherein the cache performance value is derived from one or more of information selected from the group consisting of: a miss count of the cache, a hit count of the cache, an access count of the cache, and a time taken for performing the multiplication of the segment.

### Claim 8 (depends on 1)

The method of claim 1, wherein the cache performance value is descriptive of a cache level greater than level one.

### Claim 9 (depends on 1)

The method of claim 1, wherein the aggregated cache performance includes one of: a sum of the cache performance values, or an average of the cache performance values.

### Claim 10 (depends on 3)

The method of claim 3, wherein the selected logical segments include a segment with a largest aggregated cache performance and a segment with a smallest aggregated cache performance.

### Claim 11 (depends on 3)

The method of claim 3, wherein the number of interchanged pairs of elements is less than or equal to half the number of elements within each of the selected logical segments.

### Claim 12 (depends on 3)

The method of claim 3, wherein at least one of the selected logical segments and the number of pairs of elements to be interchanged are chosen randomly.

### Claim 13 (depends on 3)

The method of claim 3, further comprising:
ordering, by one or more processors, the logical segments by respective aggregated cache performance before equaling the aggregated cache performances.

### Claim 14 (depends on 1)

The method of claim 1, further comprising:
receiving, by one or more processors, a graph data structure and filling the matrix with a representation of the graph data structure.

### Claim 15 (depends on 1)

The method of claim 1, wherein the matrix is given in a format selected from the group consisting of coordinate format and compressed sparse row format.

### Claim 16 (depends on 1)

The method of claim 1, wherein obtaining the one or more test vectors further comprises one of:
setting coordinates of one or more of the test vectors by random and loading a set of one or more predetermined test vectors.

### Claim 17 (depends on 1)

The method of claim 1, further comprising:
receiving, by one or more processors, a set of multiple process vectors; and
identifying, by one or more processors, one of the process vectors as the input vector, wherein obtaining the one or more test vectors comprises identifying one or more of other process vectors as the one or more test vectors.

### Claim 18

A computer program product for performing a multiplication of a matrix with an input vector, the computer program product comprising:
one or more computer readable storage media and program instructions stored on the one or more computer readable storage media, the program instructions comprising:
program instructions to subdivide a matrix into logical segments, the matrix being given in a sparse-matrix data format;
program instructions to obtain one or more test vectors; and
program instructions to perform an optimization cycle further comprising:
for each of the test vectors, program instructions to perform a cache performance test, the cache performance test further comprising:
for each of the logical segments, program instructions to perform a test multiplication by providing a respective logical segment and a respective test vector to an input of a matrix-vector multiplication algorithm, and
during the test multiplication of each segment, program instructions to determine a cache performance value of a cache of a processor performing the test multiplication.

### Claim 19

A computer system performing a multiplication of a matrix with an input vector, the computer system comprising:
one or more computer processors;
one or more computer readable storage media; and
program instructions stored on the computer readable storage media for execution by at least one of the one or more processors, the program instructions comprising:
program instructions to subdivide a matrix into logical segments, the matrix being given in a sparse-matrix data format;
program instructions to obtain one or more test vectors; and
program instructions to perform an optimization cycle further comprising:
for each of the test vectors, program instructions to perform a cache performance test, the cache performance test further comprising:
for each of the logical segments, program instructions to perform a test multiplication by providing a respective logical segment and a respective test vector to an input of a matrix-vector multiplication algorithm, and
during the test multiplication of each segment, program instructions to determine a cache performance value of a cache of a processor performing the test multiplication.

### Claim 20 (depends on 19)

The computer system of claim 19, wherein the optimization cycle further comprises program instructions, for each of the logical segments, to:
determine an aggregated cache performance from the cache performance values determined for the respective logical segment; and
assign a weight to each element of the matrix within the respective logical segment, the weight comprising the aggregated cache performance of the logical segment.
