Method and apparatus for performing vector operations using look up tables

Patent metadata

Field	Value
Publication number	US-10409596-B2
Application number	US-201515536351-A
Country	US
Kind code	B2
Filing date	Nov 17, 2015
Priority date	Dec 15, 2014
Publication date	Sep 10, 2019
Grant date	Sep 10, 2019

Abstract

Disclosed is an apparatus comprising: a plurality of memory banks; and a controller for generating a plurality of lookup tables storing data, needed for vector arithmetic operations, copied from data stored in the plurality of memory banks, and generating vector data by reading the data in the generated lookup tables.

First claim

The invention claimed is:

1. An apparatus comprising:
a plurality of memory banks; and
a controller configured to:
generate a plurality of lookup tables in which data that is necessary for a vector operation among data stored in the plurality of memory banks is copied and stored; and
generate vector data by reading the data from the plurality of lookup tables,
wherein the controller divides the plurality of memory banks into a predetermined number of groups and generates one lookup table for each of the groups; and
the one lookup table generated for each of the groups is stored in a plurality of memory banks included in each of the group.

2. The apparatus of claim 1 , wherein the controller includes:
a lookup table generating unit configured to generate the plurality of lookup tables; and
a gather unit configured to read the data from the plurality of lookup tables and generate the vector data.

3. The apparatus of claim 1 , wherein:
the one lookup table generated for each of the groups is stored in the plurality of memory banks in an interleaving form.

4. The apparatus of claim 1 , wherein the controller accesses each of the lookup tables using an index vector including a plurality of randomly generated indexes and reads data stored at positions of the indexes in each of the lookup tables.

5. The apparatus of claim 1 , wherein the controller divides result vector data obtained by performing a predetermined vector operation on the vector data into elements and stores the result vector data divided by elements in the plurality of lookup tables.

6. The apparatus of claim 5 , wherein the controller stores each of the elements at a predetermined index position in each of the lookup tables.

7. The apparatus of claim 5 , wherein, when a value of data stored in a first index in one of the plurality of lookup tables is changed, the controller updates data stored in a first index in each of the remaining lookup tables, whose value is not changed, with the changed value.

8. The apparatus of claim 5 , further comprising a switching unit including a plurality of sub-switch units corresponding to the lookup tables,
wherein the plurality of sub-switch units determine whether to allow the controller to access a predetermined index position of each of the lookup tables.

9. The apparatus of claim 8 , wherein:
the plurality of sub-switch units include a plurality of switches corresponding to each of the plurality of memory banks; and
each of the plurality of switches determines whether the controller is accessible by each of the plurality of memory banks.

10. A method comprising:
generating a plurality of lookup tables in which data that is necessary for a vector operation among data stored in the plurality of memory banks is copied and stored; and
generating vector data by reading the data from the lookup tables,
wherein the generating of the plurality of lookup tables includes:
dividing the plurality of memory banks into a predetermined number of groups and generating one lookup table for each of the groups; and
storing the one lookup table generated for each of the groups in a plurality of memory banks included in each of the groups.

11. The method of claim 10 , wherein
the storing the one lookup table generated for each of the groups in the plurality of memory banks included in the group comprises storing the one lookup table generated for each of the groups in the plurality of memory banks included in the group in an interleaving form.

12. The method of claim 10 , wherein the generating of the vector data by reading the data from the lookup tables includes accessing each of the lookup tables using an index vector including a plurality of randomly generated indexes and reading data stored at positions of the indexes in each of the lookup tables.

13. The method of claim 10 , further comprising dividing result vector data obtained by performing a predetermined vector operation on the vector data into elements and storing the result vector data divided by elements in the plurality of lookup tables.

14. The method of claim 13 , wherein the storing of the result vector data divided by elements in the plurality of lookup tables includes storing each of the elements at a predetermined index position in each of the lookup tables.

15. The method of claim 13 , wherein the storing of the result vector data divided by elements in the plurality of lookup tables includes, when a value of data stored in a first index in any one of the plurality of lookup tables is changed, updating data stored in a first index in each of the remaining lookup tables, whose value is not changed, with the changed value.

16. The method of claim 13 , wherein:
the generating of the vector data by reading the data from the lookup tables includes generating the vector data by reading data present at a predetermined index position that is allowed to be accessed in each of the lookup tables; and
the storing of the result vector data divided by elements in the plurality of lookup tables includes storing the result vector data at the predetermined index position that is allowed to be accessed in each of the lookup tables.

17. The method of claim 15 , wherein the generating of the vector data by reading the data from the lookup tables and the storing of the result vector data divided by elements in the plurality of lookup tables include determining whether to allow access to each of the memory banks.

18. A non-transitory computer readable recording medium having stored thereon a program which, when executed by a computer, causes the computer to execute a method comprising:
generating a plurality of lookup tables into which data that is necessary for a vector operation from among data stored in a plurality of memory banks is copied and stored; and
generating vector data by reading the data from the lookup tables,
wherein the generating of the plurality of lookup tables includes:
dividing the plurality of memory banks into a predetermined number of groups and generating one lookup table for each of the groups; and
storing the one lookup table generated for each of the groups in a plurality of memory banks included in each of the groups.

Assignees

• Samsung Electronics Co Ltd

Inventors

• Cho Jung-Uk
• Kim Suk-Jin
• Suh Dong-Kwan

Classifications

• G06F12/0607

  Interleaved addressing · CPC title

• G06F12/0207

  with multidimensional access, e.g. row/column, matrix · CPC title

• G06F9/3004

  to perform operations on memory · CPC title

• G06F12/0802 Primary

  Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches · CPC title

• G06F12/02 Primary

  Addressing or allocation; Relocation (program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00) · CPC title