Method and apparatus for multiple accesses in memory and storage system, wherein the memory return addresses of vertexes that have not been traversed

Patent metadata

Field	Value
Publication number	US-10956319-B2
Application number	US-201515310984-A
Country	US
Kind code	B2
Filing date	May 13, 2015
Priority date	May 14, 2014
Publication date	Mar 23, 2021
Grant date	Mar 23, 2021

Abstract

Provided are a method for multiple accesses in a memory, an apparatus supporting multiple accesses in the memory and a storage system. The method comprises: receiving a number N of addresses in the memory, wherein N is an integer larger than 1 and the number N of addresses are discontinuous; performing a preset operation according to the number N of addresses; and outputting the result of the operation. As a consequence, the performances of a computer system can be improved, and a user can input and use the desired addresses just as required by the user.

First claim

What is claimed is:

1. A method for multi-access in a memory, comprising:
receiving, at a memory, N addresses in the memory, wherein N is an integer greater than 1 and the N addresses are non-contiguous;
performing, at the memory, predetermined operations based on the N addresses, the predetermined operations comprising:
accessing each of the received N addresses, and determining that data stored at each of the received N addresses satisfies a predetermined condition;
replacing an original value of the data with a new value when the predetermined condition is satisfied, wherein, the new value may be one of: a constant value, a function of the original value, or a set of values corresponding to one or more of the N addresses;
and storing first addresses of the received N addresses of the data satisfying the predetermined condition in a buffer area within the memory, before the accesses on all addresses among the N addresses are finished;

and outputting results of the multi-access, comprising:
outputting the first addresses of the received N addresses stored in the buffer area as the results of the multi-access,
wherein the multi-access is traversal of a graph including a plurality of vertexes, the predetermined condition indicates whether a vertex of the plurality of vertexes has been traversed, and addresses of the vertexes which have not been traversed are the results of the multi-access.

2. The method as claimed in claim 1 , wherein:
outputting the first addresses of the received N addresses stored within the buffer area after the predetermined operations performed on the N addresses are completed.

3. The method as claimed in claim 1 , wherein each address in the N addresses is determined based on a base address and an offset, wherein the offset indicates a distance between each address in the N addresses and the base address,
wherein receiving the N addresses in the memory further comprises:
receiving the base address and N offsets; and
determining each of the N addresses from an ith address=the base address+an ith offset, 0<i≤N−1,
wherein receiving the N offsets further comprises receiving an address element size and N address indexes, and
wherein the ith offset is determined as the ith offset=an ith address index×the address element size.

4. The method as claimed in claim 3 , wherein determining that the data stored at each of the received N addresses satisfies the predetermined condition comprises:
performing at least one of arithmetic operations, relational operations and logical operations on the data stored at the N addresses.

5. The method as claimed in claim 1 , wherein determining that the data stored at each of the received N addresses satisfies the predetermined condition comprises:
performing a first operation including at least one of relational operations and logical operations on the data and a predetermined condition value; and
determining that the predetermined condition is satisfied when result of the first operation indicates true,
wherein the relational operations comprise equal to, greater than, greater than or equal to, less than, less than or equal to and not equal to, and the logical operations include AND, OR and exclusive-NOR.

6. The method as claimed in claim 1 , wherein the predetermined condition is same or different for the N addresses.

7. An apparatus for supporting multi-access in a memory, comprising:
a receiver, executed by a processor, for receiving, at the memory, N addresses in the memory, wherein N is an integer greater than 1 and the N addresses are non-contiguous;
wherein the processor configured to perform, at the memory, predetermined operations based on the N addresses, the predetermined operations comprising:
accessing each of the received N addresses, and determining that data stored at each of the received N addresses satisfies a predetermined condition;
when the predetermined condition is satisfied, replacing an original value of the data with a new value when the predetermined condition is satisfied, wherein the new value may be one of: a constant value, a function of the original value, or a set of values corresponding to one or more of the N addresses;
and storing first addresses of the received N addresses of the data satisfying the predetermined condition in a buffer area within the memory, before the accesses on all addresses among the N addresses are finished;

and an outputter, executed by the processor, for outputting results of the multi-access, the outputting comprising:
outputting the first addresses of the received N addresses stored in the buffer area as the results of the multi-access,
wherein the multi-access is traversal of a graph including a plurality of vertexes, the predetermined condition indicates whether a vertex of the plurality of vertexes has been traversed, and addresses of the vertexes which have not been traversed are the results of the multi-access.

8. The apparatus as claimed in claim 7 ,
wherein the outputter outputs the first addresses of the received N addresses stored within the buffer area after the predetermined operations performed on the N addresses are completed.

9. The apparatus as claimed in claim 7 , wherein each address in the N addresses is determined based on a base address and an offset, wherein the offset indicates a distance between each address in the N addresses and the base address,
wherein the receiver receives the base address and N offsets, and
determines each of the N addresses from an ith address=the base address+an ith offset, 0<i≤N−1,
wherein receiving the N offsets further comprises receiving an address element size and N address indexes, and wherein the ith offset is determined as the ith offset=ith address index×the address element size.

10. The apparatus as claimed in claim 7 , wherein determining, by the processor, that data stored at each of the first addresses of the received N addresses satisfies the predetermined condition comprises:
performing a first operation including at least one of relational operations and logical operations on the data and a predetermined condition value; and
determining that the predetermined condition is satisfied when result of the first operation indicates true,
wherein the relational operations comprise equal to, greater than, greater than or equal to, less than, less than or equal to and not equal to, and the logical operations include AND, OR and exclusive-NOR.

11. The apparatus as claimed in claim 7 , wherein the predetermined condition is same or different for the N addresses.

12. The apparatus as claimed in claim 7 , wherein determining that the data stored at each of the received N addresses satisfies the predetermined condition comprises:
the processor performs at least one of arithmetic operations, relational operations and logical operations on the data stored at the N addresses.

13. A memory system including an apparatus for supporting multi-access in a memory, the apparatus comprising:
a receiver, executed by a processor, for receiving, at the memory, N addresses in the memory, wherein N is an integer greater than 1 and the N addresses are non-contiguous;
wherein the processor configured to perform, at the memory, predetermined operations based on the N addresses, the predetermined operations comprising:
accessing each of the received N addresses, and determining that data stored at each of the received N addresses satisfies a predetermined condition;
replacing an original value of the data with a new value when the predetermined condition is satisfied, wherein, the new value may be one of: a constant value, a function of the original value, or a

Assignees

• Univ Tsinghua

Inventors

• Chen Wenguang
• Zheng Weimin

Classifications

• G06F12/06 Primary

  Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication (G06F12/08 takes precedence) · CPC title

• G06F13/16

  for access to memory bus (G06F13/28 takes precedence) · CPC title

• G06F9/345

  of multiple operands or results {(addressing multiple banks G06F12/06)} · CPC title

• G06F9/3004

  to perform operations on memory · CPC title