Hardware-based array compression

Patent metadata

Field	Value
Publication number	US-9304898-B2
Application number	US-201113497442-A
Country	US
Kind code	B2
Filing date	Aug 30, 2011
Priority date	Aug 30, 2011
Publication date	Apr 5, 2016
Grant date	Apr 5, 2016

Abstract

Technologies are generally described herein for compressing an array using hardware-based compression and performing various instructions on the compressed array. Some example technologies may receive an instruction adapted to access an address in an array. The technologies may determine whether address is compressible. If the address is compressible, then the technologies may determine a compressed address of a compressed array based on the address. The compressed array may represent a compressed layout of the array where a reduced size of each compressed element in the compressed array is smaller than an original size of each element in the array. The technologies may access the compressed array at the compressed address in accordance with the instruction.

First claim

What is claimed is:

1. A method to compress an array, comprising:
receiving, by a computer having a processor and a memory, an instruction to access the array at a first memory address;
upon receiving the instruction, determining, by the computer, the first memory address is compressible;
responsive to determining the first memory address is compressible, determining, by the computer, a first compressed memory address of a compressed array based on the first memory address, the compressed array representing a compressed layout of the array where a reduced size of individual ones of compressed elements in the compressed array is smaller than an original size of individual ones of elements in the array, wherein the first memory address is determined to be compressible when the first memory address is within a particular address range of the compressed array;
upon determining the first compressed memory address of the compressed array, accessing, by the computer, the compressed array at the first compressed memory address instead of the first memory address in accordance with the instruction;
receiving a store instruction to store second data in the array at a second memory address;
determining that the second memory address is compressible when the store instruction is received;
determining a second compressed memory address of the compressed array based on the second memory address when the second memory address is determined to be compressible;
forming, by the computer a combined index by combining an index to an overflow region in the compressed array with existing data from the compressed array at the second compressed memory address, wherein the overflow region is a portion of the particular address range that is not occupied by the compressed array, the index to the overflow region is a next available overflow element in the overflow region, and the combined index is a combination of the index to the overflow region and data from the compressed array at the second compressed memory address;
storing the combined index in the compressed array at the second compressed memory address;
updating a status bit in the compressed array to indicate that the compressed array stores the index to the overflow region within the combined index in the compressed array at the second compressed address;
storing the second data in the overflow region at the index when the status bit in the compressed array is updated to indicate that the compressed array stores the index; and
retrieving the second data from the compressed array based on the status bit.

2. The method of claim 1 , wherein the instruction comprises a load instruction; and wherein accessing the compressed array at the first compressed memory address instead of the first memory address in accordance with the instruction comprises retrieving, by the computer, data from the compressed array at the first compressed memory address instead of the first memory address in accordance with the load instruction.

3. The method of claim 2 , wherein retrieving the data from the compressed array at the first compressed first memory address instead of the first memory address in accordance with the load instruction comprises:
retrieving, by the computer, a data segment from the compressed array at the first compressed memory address, the data segment comprising the data and unneeded data;
removing, by the computer, the unneeded data from the data segment by shifting the data segment; and
upon removing the unneeded data from the data segment, forming, by the computer, the data by aligning the data segment in accordance with the array.

4. The method of claim 2 , further comprising:
upon retrieving the data from the compressed array at the first compressed memory address instead of the first memory address in accordance with the load instruction, determining, by the computer, that the status bit indicates an overflow;
in response to determining that the status bit does not indicate the overflow, outputting, by the computer, the data to a load/store queue; and
in response to determining that the status bit indicates the overflow,
computing, by the computer, an overflow address based on the data,
retrieving, by the computer, additional data from the compressed array at the overflow address, and
outputting, by the computer, the additional data to the load/store queue.

5. The method of claim 1 , further comprising:
responsive to determining that the address is not compressible, accessing, by the computer, the array at the first memory address in accordance with the instruction.

6. The method of claim 5 , wherein the instruction comprises a load instruction; and wherein accessing the array at the first memory address in accordance with the instruction comprises retrieving, by the computer, data from the array at the first memory address in accordance with the load instruction.

7. The method of claim 5 , wherein the instruction comprises a store instruction; and wherein accessing the array at the first memory address in accordance with the instruction comprises storing, by the computer, data in the array at the first memory address in accordance with the store instruction.

8. The method of claim 1 , wherein the instruction comprises a store instruction, and wherein accessing the compressed array at the first compressed memory address instead of the first memory address in accordance with the instruction comprises:
retrieving, by the computer, data from a load/store queue;
determining, by the computer, that the data is larger than the reduced size of individual ones of compressed elements in the compressed array; and
responsive to determining that the data is not larger than the reduced size of the individual ones of compressed elements in the compressed array, storing, by the computer, the data in the compressed array at the first compressed memory address.

9. The method of claim 8 , wherein storing the data in the compressed array at the first compressed memory address comprises:
forming, by the computer, a data segment by shifting and aligning the data in accordance with the compressed array;
forming, by the computer, a combined data segment by combining the data segment with existing data from the compressed array at the first compressed memory address; and
storing, by the computer, the combined data segment in the compressed array at the first compressed memory address.

10. The method of claim 1 , wherein the status bit stores a first bit value indicating that the compressed array stores the data and a second bit value indicating that the compressed array stores the index; and wherein updating the status bit in the compressed array to indicate that the compressed array stores the index comprises updating, by the computer, the status bit from the first bit value indicating that the compressed array stores the data to the second bit value indicating that the compressed array stores the index.

11. The method of claim 1 , wherein determining that the first memory address is within the particular address range of the compressed array comprises:
retrieving, by the computer, a base address from a compressed array table; retrieving, by the computer, a range from the compressed array table; and
determining, by the computer, the address range by summing the base address and the range.

12. The method of claim 1 , wherein determining the first compressed memory address of the compressed array based on the first memory address comprises:
retrieving, by the computer, a base address from a compressed array table;
retrieving, by the computer, the original size from the compressed array table;
retrieving, by the computer, the

Assignees

• Solihin Yan
• Empire Technology Dev Llc

Inventors

• Solihin Yan

Classifications

• G06F12/0223 Primary

  User address space allocation, e.g. contiguous or non contiguous base addressing · CPC title

• Y02B60/1225

  Cross-Sectional Technologies · mapped topic

• G06F17/30218

  Physics · mapped topic

• G06F2212/401

  Compressed data · CPC title

• G06F2212/656

  Address space sharing · CPC title