Multiplier-based processor-in-memory architectures for image and graphics processing

• US 20030222879A1
• Filed: 04/09/2003
• Published: 12/04/2003
• Est. Priority Date: 04/09/2002
• Status: Active Grant

• Current Assignee: The Research Foundation for The State University of New York (State University of New York), University of Rochester
• Original Assignee: The Research Foundation for The State University of New York (State University of New York), University of Rochester
• Inventors: Lin, Rong, Margala, Martin
• Granted Patent: US 7,167,890 B2
• Time in Patent Office: Days
• US Class Current: 345/530
• CPC Class Codes: G06F 2207/3828 Multigauge devices, i.e. capable of handling packed numbers without unpacking them
• CPC Class Codes: G06F 7/523 Multiplying only
• CPC Class Codes: G06F 7/57 Arithmetic logic units [ALU], i.e. arrangements or devices for performing two or more of the operations covered by groups G06F7/483 – G06F7/556 or for performing logical operations G06F7/49, G06F7/491 take precedence

Abstract

A Procesor-In-Memory (PIM) includes a digital accelerator for image and graphics processing. The digital accelerator is based on an ALU having multipliers for processing combinations of bits smaller than those in the input data (e.g., 4×4 adders if the input data are 8-bit numbers). The ALU implements various arithmetic algorithms for addition, multiplication, and other operations. A secondary processing logic includes adders in series and parallel to permit vector operations as well as operations on longer scalars. A self-repairing ALU is also disclosed.

Claims

1. A computational random access memory comprising:

a memory comprising N columns, N being an integer; and

an arithmetic logic unit, in communication with the N columns in the memory, the arithmetic logic unit comprising;

M multipliers, m being an integer divisible into N, each of the m multipliers being configured to multiply two N/M-bit numbers; and

an adder stage, in communication with the M multipliers to receive outputs of the M multipliers, for forming and outputting calculation results in accordance with the outputs of the M multipliers.

2. The computational random access memory of claim 1, wherein M=2.

3. The computational random access memory of claim 1, wherein the arithmetic logic unit is configured to multiply two N-bit numbers by:

(a) multiplying, in the M multipliers, a plurality of combinations of N/M bits of the two N-bit numbers to form a plurality of partial products; and

(b) accumulating, in the adder stage, the plurality of partial products to provide a product of the two N-bit numbers.

4. The computational random access memory of claim 3, wherein the arithmetic logic unit is configured to add two N-bit numbers by multiplication by one in the multipliers and forming a sum in the adder stage.

5. The computational random access memory of claim 1, wherein:

the memory comprises a plurality of groups of N columns;

a plurality of said arithmetic logic units are provided, one for each of the plurality of groups of N columns; and

the computational random access memory further comprises a secondary processing logic, in communication with the plurality of arithmetic logic units to receive outputs of the plurality of arithmetic logic units, the secondary processing logic comprising a plurality of adders for combining calculation results from the plurality of arithmetic logic units to permit calculations on numbers of more than N bits.

6. The computational random access memory of claim 5, wherein the plurality of groups of N columns of the memory are arranged in a plurality of rows, each of the plurality of rows comprising said arithmetic logic units and said secondary processing logic.

7. The computational random access memory of claim 6, wherein, in each of the rows, the groups of columns are interconnected by a diagonal connection.

8. The computational random access memory of claim 6, wherein, in each of the rows, the groups of columns are interconnected by an N-bit word connection.

9. The computational random access memory of claim 8, wherein, in each of the rows, the groups of columns are also interconnected to a diagonal connection.

10. The computational random access memory of claim 9, further comprising a plurality of two-way shift registers, each interconnecting two of the groups of N columns in two of the rows.

11. The computational random access memory of claim 1, wherein:

the arithmetic logic unit further comprises a repair multiplier in addition to the M multipliers; and

each of the M multipliers comprises an input for receiving a repair signal which controls that multiplier to replace its output with an output received from the repair multiplier.

12. The computational random access memory of claim 11, wherein the arithmetic logic unit further comprises a repair-input muxing unit for selecting inputs to the repair multiplier.

13. A method for performing a calculation on two N-bit numbers, the method comprising:

(a) providing M multipliers, M being an integer divisible into N, each of the M multipliers being configured to multiply two N/M-bit numbers;

(b) providing an adder stage, in communication with the M multipliers to receive outputs of the M multipliers;

(c) dividing each of the N-bit numbers into M combinations of N/M bits;

(d) performing multiplications involving the M combinations of N/M bits in the M multipliers to provide outputs; and

(e) forming and outputting, in the adder stage, calculation results in accordance with the outputs of the M multipliers.

14. The method of claim 13, wherein M=2.

15. The method of claim 13, wherein, when the calculation is multiplication, the two N-bit numbers are multiplied by:

(i) multiplying, in the M multipliers, the plurality of combinations of NIM bits of the two N-bit numbers to form a plurality of partial products; and

(ii) accumulating, in the adder stage, the plurality of partial products to provide a product of the two N-bit numbers.

16. The method of claim 13, wherein, when the calculation is addition, the two N-bit numbers are added by multiplication by one in the multipliers and by forming a sum in the adder stage.

17. The method of claim 13, further comprising:

(f) further providing a repair multiplier in addition to the M multipliers;

(g) determining which, if any, of the M multipliers is not operating properly and generating a repair signal identifying said one of the M multipliers is not operating properly;

(h) controlling the multiplier which is not operating properly to replace its output with an output received from the repair multiplier.