Granularities of Parallelism

Given a problem, we can solve it by using various tols. If we use more than one tool at a time, we are solving our problem in parallel. Our problem can be anything, from psychological to manufacturing problems, provided we can specify them into set of steps where tools can be used.

To simplify our discussion, let us consider a problem which can be expressed as equations. If a boolean bariable A,B,C,D may have 2 states, true(1) or false(0). We represent the 2 states by using a number system with radix 2. The digits can have values 0 or 1. Each digit in this case is called a bit.

It is possible to use multi-valued logic variables but they can be represented by bits. In a 16-valued logic, we can represent each 16-level number with 4 bits. We can say that bit is the smallest number representation.

Let A,B,C,D be 8-bit numbers/logical values. If we use C language notation,

Assume that a problem can be specified as E = (A&B) | (C&D)

How do we implement the solving of this problem?

A B C D A B C D

│ │ │ │ │ │ │ │

│ │ │ │ --- │ │ │ │

--- ┌┴──┴─┐ ┌─┴───┴┐ ┌─┴──┴──┴──┴──┐

│ a │ │ b │ │ │

│ │ │ │ │ │

│ & │ │ & │ t │ PLA │

t │ │ │ │ │ │

└──┬──┘ └───┬──┘ └──────┬──────┘

│ │ --- │

---- │ │ │

│ │ │

│ │ E

│ │

2t │ ┌───────┐ │

│ │ c │ │ BIT-LEVEL

│ │ │ │

└─┤ | ├──┘

│ │

--- │ │

└───┬───┘

│

│

E MODULE-LEVEL

In the module-level parallelism, the timing for execution of module a,b and c is critical. The result of a and b must be sent to c and c must wait for the result from both a and b. This is called the consumer-producer problem.

In the bit-level parallelism, this problem does not exist because there is only one module and it must complete within one time tick.

In fact, modules a,b and c must be assumed to complete their jobs within one time tick. Be warned though, the PLA may be viewed as consisting of many components made up of gates and wires which may have varying speeds. Either we ignore them(by lengthening time tick, t) or use reduncandy to cancell

some errors.