Shiftable memory supporting atomic operation

• US 9,576,619 B2
• Filed: 10/27/2011
• Issued: 02/21/2017
• Est. Priority Date: 10/27/2011
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Golab, Wojciech, Pickett, Matthew D., Karp, Alan H.
• Primary Examiner(s): Tsai, Henry
• Assistant Examiner(s): ROCHE, JOHN B
• Application Number:
  US14/349,678
• Publication Number:
  US 20140310453A1
• Time in Patent Office: 1,944 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 15/7821 Tightly coupled to memory, e.g. computational memory, smart memory, processor in memory
• CPC Class Codes: G06F 2209/521 Atomic
• CPC Class Codes: G06F 5/00 Methods or arrangements for data conversion without changing the order or content of the data handled
• CPC Class Codes: G06F 9/30032 Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30134 Register stacks; shift registers
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes
• CPC Class Codes: G11C 19/188 Organisation of a multiplicity of shift registers, e.g. regeneration, timing or input-output circuits
• CPC Class Codes: G11C 19/287 Organisation of a multiplicity of shift registers
• CPC Class Codes: G11C 7/1036 using data shift registers

Abstract

A shiftable memory supporting atomic operation employs built-in shifting capability to shift a contiguous subset of data from a first location to a second location within memory during an atomic operation. The shiftable memory includes the memory to store data. The memory has the built-in shifting capability. The shiftable memory further includes an atomic primitive defined on the memory to operate on the contiguous subset.

Claims

1. A shiftable memory supporting atomic operation, comprising:

a memory to store data, the memory having built-in shifting capability to shift a contiguous subset of the data from a first location to a second location within the memory, the contiguous subset of data having a size that is smaller than a total size of the memory, wherein the built-in shifting capability is to shift the contiguous subset in the memory without using a processor external of the shiftable memory to perform the shift; and

an atomic primitive implemented using a processing circuit in the memory to perform the atomic operation on the contiguous subset,

wherein the memory having the built-in shifting capability is to shift only data of the contiguous subset when the contiguous subset is shifted, wherein the memory comprises a controller to;

receive address information from the processor external of the shiftable memory, and

determine a length of the contiguous subset based on the received address information.

2. The shiftable memory of claim 1, wherein the atomic primitive comprises a shift-and-store primitive, the shift-and-store primitive to downshift the contiguous subset in the memory using the built-in shifting capability and to append data onto a beginning of the contiguous subset.

3. The shiftable memory of claim 1, wherein the atomic primitive comprises a fetch-and-shift primitive, the fetch-and-shift primitive to read data from a beginning of the contiguous subset and to upshift the contiguous subset in the memory using the built-in shifting capability.

4. The shiftable memory of claim 1, wherein the atomic primitive comprises a shift-and-store-and-increment primitive, the shift-and-store-and-increment primitive to downshift the contiguous subset in the memory using the built-in shifting capability, to append data onto a beginning of the contiguous subset, and to increment a value that identifies a bottom of a portion of the contiguous subset by an amount of the downshift.

5. The shiftable memory of claim 1, wherein the atomic primitive comprises a fetch-and-shift-and-decrement primitive, the fetch-and-shift-and-decrement primitive to read data from the beginning of the contiguous subset, to upshift the contiguous subset in the memory using the built-in shifting capability, and to decrement a value that identifies a bottom of a portion of the contiguous subset by an amount of the upshift.

6. The shiftable memory of claim 1, wherein the atomic primitive comprises one of a store-at-end primitive and a remove-from-end primitive, the store-at-end primitive to append data onto an end of a portion of the contiguous subset opposite a beginning of the contiguous subset, and the remove-from-end primitive to remove data from the end of the portion of the contiguous subset.

7. The shiftable memory of claim 1, the shiftable memory further comprising one or both of a register to identify a beginning of the contiguous subset in the memory and another register to identify an end of a portion of the contiguous subset, wherein the portion of the contiguous subset is between the beginning of the contiguous subset and an end of the contiguous subset.

8. A concurrent, multithreaded system that includes the shiftable memory of claim 1, the atomic primitive facilitating sharing of the shiftable memory by multiple threads of the multi-threaded system.

9. A shiftable memory comprising:

a memory comprising a plurality of memory cells and a built-in data shifting capability to shift a contiguous subset of data stored in the memory cells from a first location to a second location within the memory, the contiguous subset of data having a size that is smaller than a total size of the memory, the memory further comprising a controller to;

receive address information from a processor external of the shiftable memory, and

determine a length of the contiguous subset based on the received address information;

a register to identify an array defined on the memory cells, the array to contain a portion of the contiguous subset of data being shifted; and

an atomic primitive defined on the shiftable memory to operate on the portion of the contiguous subset in the array identified by the register.

10. The shiftable memory of claim 9, wherein the atomic primitive comprises one or more of:

a shift-and-store atomic primitive to downshift the contiguous subset using the built-in shifting capability of the shiftable memory and to insert data onto a beginning of the array, where the inserted data is appended to the contiguous subset; and

a fetch-and-shift atomic primitive to read data from the beginning of the array and to upshift a remaining portion of the contiguous subset using the built-in shifting capability of the shiftable memory, where the read data is removed from the contiguous subset,

wherein the beginning of the array is identified by the register.

11. The shiftable memory of claim 9, wherein the atomic primitive comprises one or more of:

a shift-and-store-and-increment atomic primitive to downshift the contiguous subset using the built-in shifting capability, to insert data onto a beginning of the array, and to increment a value to identify an end of the array opposite the beginning by an amount of the downshift;

a fetch-and-shift-and-decrement atomic primitive to read data from the beginning of the array, to upshift the contiguous subset using the built-in shifting capability, and to decrement a value to identify an end of the array opposite the beginning by an amount of the upshift;

a store-at-end atomic primitive to insert data onto an end of the contiguous subset portion in the array using a value to identify an end of the array opposite the beginning of the array and to increment the value; and

a remove-from-end atomic primitive to read data from an end of the contiguous subset portion in the array and to decrement a value that identifies the end of the array opposite the beginning of the array,

wherein the beginning of the array is identified by the register.

16. The shiftable memory of claim 9, wherein the atomic primitive is implemented with a processing circuit in the memory, and the atomic primitive is to perform an atomic operation on the portion of the contiguous subset in the array identified by the register.

12. A method of atomic operation using-a memory, the method comprising:

defining an array in memory cells of the memory, the memory having a plurality of memory cells with built-in shifting capability to shift a contiguous subset of data stored in the array from a first location to a second location, a size of the contiguous subset of data being less than a total size of the shiftable memory, the built-in shifting comprising one or both of an upshift and a downshift, wherein the built-in shifting capability shifts the contiguous subset in the memory without using a processor external of the shiftable memory to perform the shift; and

executing an atomic primitive comprising a processing circuit of the memory, the atomic primitive performing the atomic operation on the contiguous subset in the array,

wherein when the contiguous subset in the array is shifted, the shifting occurs entirely within the memory and only data of the contiguous subset is shifted, wherein the memory comprises a controller, the method further comprising;

receiving, by the controller in the memory, address information from the processor external of the shiftable memory, and

determining, by the controller, a length of the contiguous subset based on the received address information.

13. The method of claim 12, wherein executing the atomic primitive comprises one of:

performing atomically a shift-and-store primitive comprising;

downshifting the contiguous subset in the array away from a top of the array and inserting data at the top of the array using the built-in shifting capability; and

performing atomically a fetch-and-shift primitive comprising;

reading data at a top of the array and upshifting the contiguous subset in the array toward the top of the array using the built-in shifting capability.

14. The method of claim 12, wherein executing the atomic primitive comprises one of:

performing atomically a shift-and-store-and-increment primitive comprising;

downshifting the contiguous subset in the array away from a top of the array using the built-in shifting capability, inserting data at the top of the array, and incrementing a value identifying a bottom of the array;

performing atomically a fetch-and-shift-and-decrement primitive comprising;

reading data at a top of the array, upshifting the contiguous subset in the array toward the top of the array using the built-in shifting capability, and decrementing a value identifying a bottom of the array;

performing atomically store-at-end primitive comprising;

appending data onto a bottom of the contiguous subset in the array and incrementing a value identifying a bottom of the array; and

performing atomically remove-from-end primitive comprising;

decrementing a value identifying a bottom of the array and reading data at the bottom of the array.

15. The method of claim 12, wherein the atomic operation is performed in a context of a concurrent, multi-threaded system.