Accessing data in multi-dimensional tensors using adders

Patent metadata

Field	Value
Publication number	US-9946539-B1
Application number	US-201715603061-A
Country	US
Kind code	B1
Filing date	May 23, 2017
Priority date	May 23, 2017
Publication date	Apr 17, 2018
Grant date	Apr 17, 2018

Abstract

Methods, systems, and apparatus, including an apparatus for accessing a N-dimensional tensor, the apparatus including, for each dimension of the N-dimensional tensor, a partial address offset value element that stores a partial address offset value for the dimension based at least on an initial value for the dimension, a step value for the dimension, and a number of iterations of a loop for the dimension. The apparatus includes a hardware adder and a processor. The processor obtains an instruction to access a particular element of the N-dimensional tensor. The N-dimensional tensor has multiple elements arranged across each of the N dimensions, where N is an integer that is equal to or greater than one. The processor determines, using the partial address offset value elements and the hardware adder, an address of the particular element and outputs data indicating the determined address for accessing the particular element of the N-dimensional tensor.

First claim

What is claimed is:

1. An apparatus for processing an instruction for accessing an N-dimensional tensor, the apparatus comprising:
for each dimension of the N-dimensional tensor, a partial address offset value element that stores a partial address offset value for the dimension, the partial address offset value for each dimension being based at least on an initial value for the dimension, a step value for the dimension, and a number of iterations of a loop for the dimension, wherein each partial address offset value element comprises hardware storage circuitry;
one or more hardware adders; and
one or more hardware processors configured to execute one or more instructions of an instruction set executable by the one or more hardware processors, wherein execution of the one or more instructions causes the one or more hardware processors to perform operations comprising:
obtain an instruction to access a particular element of the N-dimensional tensor, wherein the N-dimensional tensor has multiple elements arranged across each of the N dimensions, and wherein N is an integer that is equal to or greater than two;
obtain, for each dimension of the N-dimensional tensor, a current partial address offset value for the dimension from the partial address offset value element for the dimension;
determine, using the one or more hardware adders, a memory address of the particular element, including determining, using the one or more hardware adders, a sum of the obtained current partial address offset values, the determined memory address of the particular element being different from a value of the particular element stored at the determined memory address of the particular element;
output data indicating the determined address for accessing the particular element of the N-dimensional tensor; and
update the partial address offset value for at least one of the dimensions by adding, using the one or more hardware adders, the step value for the at least one dimension to the current partial address offset value for the at least one dimension.

2. The apparatus of claim 1 , further comprising for each dimension:
an initial value element that stores the initial value for the dimension; and
a step value element that stores the step value for the dimension.

3. The apparatus of claim 2 , wherein each partial address offset value element, each initial value element, and each step value element comprises a hardware register.

4. The apparatus of claim 1 , wherein the one or more hardware processors are further configured to:
determine, for each dimension, the partial address offset value for the dimension after each iteration of a nested loop for the dimension by adding the step value to a previous partial address offset value for the dimension.

5. The apparatus of claim 4 , further comprising, for each dimension, a limit value element that stores a limit value for the dimension, wherein the one or more hardware processors are further configured to:
determine, for each dimension, whether the determined partial address offset value for the dimension equals the limit value for the dimension; and
in response to determining that the determined partial address offset value for a first dimension that corresponds to a first nested loop equals the limit value for the first dimension:
resetting the partial address offset value for the first dimension to the initial value for the first dimension; and
updating, for a second dimension that corresponds to a second nested loop in which the first nested loop is nested and using the one or more hardware adders, the partial address offset value for the second dimension to equal a sum of the step value for the second dimension and the partial address offset value for the second dimension.

6. The apparatus of claim 1 , wherein the step value for each dimension is a predetermined value based on a number of elements in one or more of the dimensions.

7. The apparatus of claim 1 , wherein:
the one or more processors determine a respective memory address for each element of the N-dimensional tensor in a sequence based on the loops for the dimensions; and
the one or more processors update the partial address offset value for each dimension after an iteration of the loop for the dimension by:
adding the step value for the dimension to a current partial address value for the dimension; and
determining whether the updated partial address offset value for the dimension is equal to an end value for the dimension;
when the updated partial address offset value for the dimension equals the end value for the dimension, updating the partial address offset value for the dimension to equal the initial value for the dimension; and
when the updated partial address offset value for the dimension does not equal the end value for the dimension, storing the updated partial address offset value for the dimension in the updated partial address offset value element for the dimension.

8. A system comprising:
one or more processing units configured to perform linear algebra operations on an N-dimensional tensor, wherein the N-dimensional tensor has multiple elements arranged across each of the N dimensions, and wherein N is an integer that is equal to or greater than two;
for each dimension of the N dimensions, a partial address offset value element that stores a partial address offset value for the dimension, the partial address offset value for each dimension being based at least on an initial value for the dimension, a step value for the dimension, and a number of iterations of a loop for the dimension, wherein each partial address offset value element comprises hardware storage circuitry;
circuitry that includes:
one or more hardware adders; and
one or more hardware processors that are configured to:
obtain an instruction to access a particular element of the N-dimensional tensor;
obtain, for each dimension of the N-dimensional tensor, a current partial address offset value for the dimension from the partial address offset value element for the dimension;
determine, using the one or more hardware adders, a memory address of the particular element, including determining, using the one or more hardware adders, a sum of the obtained current partial address offset values, the determined memory address of the particular element being different from a value of the particular element stored at the determined memory address of the particular element;
output data indicating the determined memory address for accessing the particular element of the N-dimensional tensor; and
update the partial address offset value for at least one of the dimensions by adding, using the one or more hardware adders, the step value for the at least one dimension to the current partial address offset value for the at least one dimension.

9. The system of claim 8 , further comprising for each dimension:
an initial value element that stores the initial value for the dimension; and
a step value element that stores the step value for the dimension.

10. The system of claim 9 , wherein each partial address offset value element, each initial value element, and each step value element comprises a hardware register.

11. The system of claim 8 , wherein the one or more processors are further configured to:
determine, for each dimension, the partial address offset value for the dimension after each iteration of a nested loop for the dimension by adding the step value to a previous partial address offset value for the dimension.

12. The system of claim 11 , further comprising, for each dimension, a limit value element that stores a limit value for the dimension, wherein the one or more process

Assignees

• Google Llc

Inventors

• Temam Olivier
• Khaitan Harshit
• Narayanaswami Ravi
• Woo Dong Hyuk

Classifications

• G06N3/045

  Combinations of networks · CPC title

• G06F9/325

  for loops, e.g. loop detection or loop counter · CPC title

• G06F17/16 Primary

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

• G06N3/063

  using electronic means · CPC title

• G06F2212/454

  Vector or matrix data · CPC title