# US 10,503,691 B2 · Associative computer providing semi-parallel architecture

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,503,691 B2
- Document ID: US10503691B2
- Status: Granted
- Kind: B2
- Application number: 15/334,398
- Filed: 2016-10-26
- Published: 2018-04-26
- Granted: 2019-12-10
- Earliest claimed: 2016-10-26
- Assignees: Wisconsin Alumni Research Foundation
- Applicants: Wisconsin Alumni Research Foundation
- Inventors: Jing Li; Soroosh Khoram
- Web page: https://patentgrep.com/patent/US10503691B2

## CPC

- G06F 15/7839: {with memory}
- G06F 7/38: Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
- G06F 15/7821: {Tightly coupled to memory, e.g. computational memory, smart memory, processor in memory}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

An associative processor separates the arithmetic operation of addition from the carry process to pre-compute contingent carries before the addition which then allows improved parallelism in the addition process. A portion of the contingent carry computation may also be conducted in parallel. The result is higher-speed operations resulting from increased parallelism.

## Claims

### Claim 1

An associative processor comprising:
a plurality of rows of content addressable memory, each row operating to define stored data; and
a controller communicating with the rows to search the rows in parallel for a pattern distinct from the stored data and to write to the rows in parallel according to a pattern distinct from the stored data;
the controller operating to:
(a) load each row with stored data representing two words being addends to be summed, each word including multiple subwords;
(b) apply search and write cycles in parallel to the subwords using first predetermined patterns to determine whether an addition of the subwords would produce a carry-out bit under both states of an assumed carry-in bit of one and an assumed of carry-in bit of zero to determine a contingent carry relationship of each subword, the search and write cycles providing a logical comparison of the first predetermined patterns to the stored data of the subwords to store a result indicating the contingent carry relationships for the subwords;
(c) apply search and write cycles to the subwords using second predetermined patterns to propagate carry bits through the subwords according to the contingent carry relationship of each subword and a carry-in bit of zero for the least significant subwords, the search and write cycles providing a logical comparison of the second predetermined patterns to the stored data of the subwords to propagate carry bits through the subwords; and
(d) apply search and write cycles on the subwords using third predetermined patterns to add corresponding subwords using the propagated carry bits, the search and write cycles providing a logical comparison of the third predetermined patterns to the stored data of the subwords to add the corresponding carry bits.

### Claim 2 (depends on 1)

The associative processor of claim 1 wherein step (b) operates on multibit subwords in parallel.

### Claim 3 (depends on 2)

The associative processor of claim 2 wherein step (c) operates on multibit subwords in series.

### Claim 4 (depends on 1)

The associative processor of claim 1 wherein step (d) operates on multibit subwords in parallel.

### Claim 5 (depends on 1)

The associative processor of claim 1 wherein the subwords have multiple bits of each operand.

### Claim 6 (depends on 5)

The associative processor of claim 5 wherein the words are of length m and each subword has a bit length rounded to the nearest integer value of a value indicated by the letter l in the formula:
m
l
=
3
2
⁢
m
.

### Claim 7 (depends on 6)

The associative processor of claim 6 wherein the words are of length 64 and the subwords have a bit length of four.

### Claim 8 (depends on 1)

The associative processor of claim 1 wherein the subwords have only a single bit of each operand.

### Claim 9 (depends on 1)

The associative processor of claim 1 wherein the first predetermined patterns are limited to two patterns identifying whether corresponding bits of a subword are identical being either both ones or both zeros.

### Claim 10 (depends on 1)

The associative processor of claim 1 wherein the third predetermined patterns are limited to patterns in which the added bits produce a result different from a default result loaded into the words.

### Claim 11 (depends on 1)

The associative processor of claim 1 wherein the third predetermined patterns are only unique patterns associated with carry-free addition.

### Claim 12 (depends on 1)

The associative processor of claim 1 further including a subword tag bit associated with each subword.

### Claim 13 (depends on 12)

The associative processor of claim 12 wherein the subword tag bit operates to be set or reset depending on a search applied to the associated subword and to selectively control a writing of the associated subword according to whether the tag bit is set or reset.

### Claim 14 (depends on 12)

The associative processor of claim 12 further including a word tag bit associated with each word operating to be set or reset depending on a search applied to the associated word and selectively control a writing of the associated word according to whether it is set or reset and communicating with other word tag bits in a reduction tree circuit.

### Claim 15 (depends on 14)

The associative processor of claim 14 wherein the word tag bit of a given word is a logical AND of the subword tag bits on subwords of the given word.

### Claim 16 (depends on 12)

The associative processor of claim 12 further including a key register and a mask register wherein the key register holds values for matching or writing and the mask register indicates values that have “don't care” states matching all values during searching and changing no values during writing.

### Claim 17 (depends on 16)

The associative processor of claim 16 wherein each bit of each word is associated with a carry-in bit, a first carry-out bit assuming a one-valued carry-in bit, a second carry-out bit assuming a zero-valued carry-in bit, a result bit, and first and second addend bits and wherein the contingent carry relationship is stored in the first and second carry-out bits.

### Claim 18

An method of operating an associative memory to provide for associative processing, the associative memory providing a plurality of rows of content addressable memory, each row operating to define stored data and a controller communicating with the rows to search the rows in parallel for a pattern distinct from the sorted data and to write to the rows in parallel according to a pattern distinct from the stored data; the method comprising the steps of:
(a) loading each row with stored data representing two words being addends to be summed, each word including multiple subwords representing successive bits of the words;
(b) applying search and write cycles in parallel to the subwords using first predetermined patterns to determine whether an addition of the subwords would produce a carry-out bit under both states of an assumed carry-in bit of one and an assumed carry-in bit of zero to determine a contingent carry relationship of each subword, the search and write cycles providing a logical comparison of the first predetermined patterns to the stored data of the subwords to store a result indicating the contingent carry relationships for the subwords;
(c) applying search and write cycles to the subwords using second predetermined patterns to propagate carry bits through the subwords according to the contingent carry relationship of each subword and a carry-in bit of zero for the least significant subwords, the search and write cycles providing a logical comparison of the second predetermined patterns to the stored data of the subwords to propagate carry bits through the subwords; and
(d) applying search and write cycles on the subwords using third predetermined patterns to add corresponding subwords using the propagated carry bits, the search and write cycles providing a logical comparison of the third predetermined patterns to the stored data of the subwords to add the corresponding carry bits.