Performing stencil computations

Patent metadata

Field	Value
Publication number	US-9870227-B2
Application number	US-201214352870-A
Country	US
Kind code	B2
Filing date	Nov 8, 2012
Priority date	Nov 11, 2011
Publication date	Jan 16, 2018
Grant date	Jan 16, 2018

Abstract

A method and apparatus for performing stencil computations efficiently are disclosed. In one embodiment, a processor receives an offset, and in response, retrieves a value from a memory via a single instruction, where the retrieving comprises: identifying, based on the offset, one of a plurality of registers of the processor; loading an address stored in the identified register; and retrieving from the memory the value at the address.

First claim

What is claimed is:

1. A method comprising:
receiving, by a processor, an offset from a cell of a multidimensional grid, wherein the offset corresponds to an index of one of a plurality of registers of the processor; and
retrieving by the processor, via a single instruction, a value from a memory address associated with the offset in response to the receiving of the offset, wherein the retrieving comprises:
identifying, based on the offset, the one of the plurality of registers of the processor, wherein the identified register corresponds to a dimension and a polarity of the multidimensional grid;
loading the memory address stored in the identified register; and
retrieving the value from the memory address.

2. The method of claim 1 further comprising:
determining, by the processor, a first address of the memory based on:
a second address of the memory corresponding to the cell of the multidimensional grid,
a first stride value for a first dimension of the multidimensional grid, and
a first polarity; and

storing, by the processor, the first address in a first register of the processor that is associated with the first dimension and with the first polarity.

3. The method of claim 2 further comprising:
determining, by the processor, a third address of the memory based on:
the second address,
the first stride value, and
a second polarity that is the opposite of the first polarity; and

storing, by the processor, the third address in a second register of the processor that is associated with the first dimension and with the second polarity.

4. The method of claim 2 further comprising:
determining, by the processor, a third address of the memory based on:
the second address,
a second stride value for a second dimension of the multidimensional grid, and
a second polarity; and

storing, by the processor, the third address in a second register of the processor that is associated with the second dimension and with the second polarity.

5. The method of claim 4 wherein the second polarity equals the first polarity.

6. The method of claim 4 wherein the second stride value is different than the first stride value.

7. The method of claim 2 wherein the first stride value is a positive integer greater than one.

8. The method of claim 2 further comprising:
retrieving, by the processor, a value stored at the first address of the memory; and
computing, by the processor, an updated value of the cell of the multidimensional grid based on the value retrieved from the first address of the memory.

9. The method of claim 8 wherein the computing is also based on a current value of the cell of the multidimensional grid.

10. A non-transitory computer readable storage medium including instructions that, when executed by a processor, cause the processor to perform operations comprising:
predetermining, by the processor, a first address of a memory based on: a second address of the memory corresponding to a cell of a multidimensional grid, a first stride value for a first dimension of the multidimensional grid, and a first polarity;
storing, by the processor, the first address in a first register of the processor that is associated with the first dimension and with the first polarity;
predetermining, by the processor, a third address of the memory based on: the second address, a second stride value for a second dimension of the multidimensional grid, and a second polarity; and
storing, by the processor, the third address in a second register of the processor that is associated with the second dimension and with the second polarity.

11. The non-transitory computer readable storage medium of claim 10 , wherein the operations further comprise:
receiving, by the processor, an offset; and
retrieving by the processor, via a single instruction, a value from a memory in response to the receiving of the offset, wherein the retrieving comprises:
identifying, based on the offset, one of a plurality of registers of the processor,
loading an address stored in the identified register, and
retrieving from the memory the value at the address.

12. The non-transitory computer readable storage medium of claim 10 wherein the first stride value is a positive integer greater than one.

13. The non-transitory computer readable storage medium of claim 10 wherein the second stride value is a positive integer greater than one and is different than the first stride value.

14. The non-transitory computer readable storage medium of claim 10 wherein the multidimensional grid is a two-dimensional grid.

15. The non-transitory computer readable storage medium of claim 10 wherein the multidimensional grid is a three-dimensional grid.

16. A system comprising:
a plurality of registers to store data;
an arithmetic logic unit (ALU); and
a coprocessor to:
receive from the ALU an offset from a cell of a multidimensional grid wherein the offset corresponds to an index of one of a plurality of registers of the coprocessor, and
retrieve a value from a memory address associated with the offset via a single instruction, wherein to retrieve the value from memory via a single instruction the coprocessor is further to:
identify, based on the offset, the one of the plurality of registers of the coprocessor, wherein the identified register is associated with a dimension and a polarity of the multidimensional grid;
load the memory address stored in the identified register; and
retrieve the value from the memory address.

17. The system of claim 16 , wherein the coprocessor is further to:
determine a first address of the memory based on:
a second address of the memory corresponding to the cell of the multidimensional grid,
a first stride value for a first dimension of the multidimensional grid, and
a first polarity; and

store the first address in a first register of the plurality of registers that is associated with the first dimension and with the first polarity.

18. The system of claim 17 , wherein the coprocessor is further to:
determine a third address of the memory based on:
the second address,
the first stride value, and
a second polarity that is the opposite of the first polarity; and

store the third address in a second register of the plurality of registers that is associated with the first dimension and with the second polarity.

19. The system of claim 17 , wherein the coprocessor is further to:
determine a third address of the memory based on:
the second address,
a second stride value for a second dimension of the multidimensional grid, and
a second polarity; and

store the third address in a second register of the plurality of registers that is associated with the second dimension and with the second polarity.

20. The system of claim 16 wherein the ALU is further to perform a stencil computation based on the value retrieved from the memory.

Assignees

• Univ California

Inventors

• Donofrio David

Classifications

• G06F9/30007 Primary

  to perform operations on data operands · CPC title

• G06F9/3455 Primary

  using stride · CPC title

• G06F17/10

  Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} · CPC title

• G06F9/3877

  using a secondary processor, e.g. coprocessor (peripheral processor G06F13/12) · CPC title