Importance

Loading Importance Indicators...

Abstract

A processor includes interconnected substrates, each with external connecting circuitry and parallel processing circuitry that can perform value assignment search for a set of variables. The parallel processing circuitry includes processing units, each with memory and processing circuitry, and transfer decision logic for determining whether to transfer the data of any of the processing units to another substrate. Each substrate has count logic for counting the processing units whose data indicates a combination of values that could be consistent with constraints being applied, each of which has a valid bit indicating that it could be consistent. The counts are transferred to each connected substrate, and the transfer decision logic at each substrate determines, for each connected substrate, whether to transmit data, receive data, or neither transmit nor receive. The transfer decision logic decides to transfer data only if there are sufficient valid processing units on one substrate and sufficient invalid processing units on the other substrate to ensure that the transfer will succeed. Balancing is performed frequently enough that all substrates have approximately equal numbers of valid processing units. Processing unit selection logic on each substrate selects processing units as sources or destinations, and the select logic can also provide an OR signal. Each pair of connected substrates has a single serial channel, so that one connected substrate transmits its count first, then the other. The same serial channels are used to obtain an intersubstrate count of processing units by assigning each substrate a level in a hierarchy at which it receives sums from some of its connected substrates, operates its own summing logic to add them to its own count, and transmits the resulting sum to another of its connected substrates.

Loading the Abstract Image...

First Claim