7.3 Circuits

Families of Circuits
Representation of Circuits

Many abstract models of parallel machines have been offered in the literature, besides those of PRAM's. However, unlike the case for the abstract models of sequential machines, there is no obvious way for relating the different abstract models of parallel machines. Therefore, the lowest common denominator of such models, that is, their hardware representations, seems a natural choice for analyzing the models for the resources that they require.

Here the representations are considered in terms of undirected acyclic graphs, called combinatorial Boolean circuits or simply circuits. Each node in a circuit is assumed to have an indegree no greater than 2, and an outdegree of unbounded value. Each node of indegree 0 is labeled either with a variable name, with the constant 0, or with the constant 1. Each node of indegree 1 is labeled with the Boolean function ¬. Each node of indegree 2 is labeled either with the Boolean functions $/\$ or $\/$ .

Each node of indegree greater than 0 is called a gate. A gate is said to be a NOT gate if it is labeled with ¬, an AND gate if labeled with $/\$ , and an OR gate if labeled with $\/$ . Nodes labeled with variable names are called input nodes. Nodes of outdegree 0 are called output nodes. A node labeled with 0 is called a constant node 0. A node labeled with 1 is called a constant node 1.

A circuit c that has n input nodes and m output nodes computes a function f: {0, 1}ⁿ {0, 1}^m in the obvious way.

Example 7.3.1 The circuit in Figure 7.3.1

Figure 7.3.1

Parity checker.

has 7 × 4 + 8 + 1 = 37 nodes, of which 8 are input nodes and 1 is an output node.

The circuit computes the parity function for n = 8 input values. The circuit provides the output of 0 for the case where a₁ a₈ has an odd number of 1's. The circuit provides the output of 1 for the case where a₁ a₈ has an even number of 1's.

The circuit's strategy relies on the following two observations.

The parity function does not change its value when a 0 is removed from its input string.
The parity function does not change its value if a pair of 1's is replaced with a 0 in its input string.

Each group XOR of gates outputs 1 if its input values are not equal, and 0 if its input values are equal. Each level of XOR's in the circuit reduces the size of the given input by half.

Example 7.3.2 The circuit in Figure 7.3.2

Figure 7.3.2

Adder.

is an adder that computes the sum d = a + b. d₀ d_n/2, a₁ a_n/2, and b₁ b_n/2 are assumed to be the binary representations of d, a, and b, respectively. Each LOCAL ADDER in the circuit has an input that consists of two corresponding bits of a and b, as well as a carry from the previous LOCAL ADDER. The output of each LOCAL ADDER is the corresponding bit in d, as well as a new carry to be passed on to the next LOCAL ADDER.

The size of a circuit is the number of gates in it. The depth of a circuit is the number of gates in the longest path from an input node to an output node.

Example 7.3.3 In the circuit of Figure 7.3.1 each XOR has size 4 and depth 3. The whole circuit has size 29 and depth 10.

In the circuit of Figure 7.3.2 each LOCAL ADDER has size 11 and depth 6. The whole circuit has size 11n/2 and depth 5 + 2(n/2 - 2) + 3 = n + 4.

Families of Circuits

C = (c₀, c₁, c₂, . . . ) is said to be a family of circuits if c_n is a circuit with n input nodes for each n 0. A family C = (c₀, c₁, c₂, . . . ) of circuits is said to have size complexity Z(n) if Z(n) (size of c_n) for all n 0. The family is said to have depth complexity D(n) if D(n) (depth of c_n) for all n 0.

A family C = (c₀, c₁, c₂, . . . ) of circuits is said to compute a given function f: {0, 1}* {0, 1}* if for each n 0 the circuit c_n computes the function f_n: {0, 1}ⁿ {0, 1}^k for some k 0 that depends on n. f_n is assumed to be a function that satisfies f_n(x) = f(x) for each x in {0, 1}ⁿ.

A function f is said to be of size complexity Z(n) if it is computable by a family of circuits of size complexity Z(n). The function f is said to have depth complexity D(n) if it is computable by a family of circuits with depth complexity D(n).

A family C = (c₀, c₁, c₂, . . . ) of circuits is said to decide a language L in {0, 1}* if the characteristic function of L is computable by C. (f is the characteristic function of L if f(x) = 1 for each x in L, and f(x) = 0 for each x not in L.) The size and depth complexities of a language are the size and depth complexities of its characteristic function.

Example 7.3.4 The language { a₁ a_n | a₁, . . . , a_n are in {0, 1}, and a₁ a_n has an even number of 1's } is decidable by a family of circuits similar to the circuit in Figure 7.3.1. The language has depth complexity O(log n), and size complexity O(n/2 + n/4 + + 1) = O(n).

Representation of Circuits

In what follows, we will assume that each circuit c has a representation of the following form. Associate the number 0 with each constant node 0 in c, the number 1 with each constant node 1 in c, and the numbers 2, . . . , n + 1 with the n input nodes of c. Associate consecutive numbers starting at n + 2, with each of c's gates. Then a representation of c is a string of the form E(u₁) E(u_m)F(v₁) F(v_k).

u₁, . . . , u_m are the gates of c, and v₁, . . . , v_k are the output nodes. E(u) is equal to (g, t, g_L, g_R), where g is the number assigned to gate u, t is the type of u in {¬, $\/$ , $/\$ }, and g_L and g_R are the numbers assigned to the immediate predecessors of u. In particular, g_L = g_R when t = ¬. F(v) is equal to (g), where g is the number assigned to gate v.

Example 7.3.5 Figure 7.3.3

Figure 7.3.3

A circuit with enumerated nodes.

provides a circuit whose nodes are enumerated. The circuit has the following representation.

[next] [prev] [prev-tail] [front] [up]