Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Combinational CircuitYan Gu2nd Presentation for CS 6260What is Combinational Circuits? Combinational Circuits refers to a family of models of computations. in general terms, a combinational circuit is defined as a device taking a number of inputs at one end and producing a number of outputs at the other end.features combinational circuit is made up of a number of interconnected components arranged in columns called stages. each component can be viewed as a simple processor. It has a constant fan-in----- that is , a constant number of input lines. These lines carry data from the outside world or from a constant number of components in a previous stage. each component also has a constant fan-out-------- that is , a constant number of components in a subsequent stage. each component, having received its inputs, computes a certain function of these inputs in one time unit and produces the result as output.No feedback: no component can be used more than once while computing the circuit’s output for a given inputThe Size of a combinational circuit is defined as the number of components it uses. The depth is the number of stages in the circuit----- that is , the maximum number of components on a path from input to output. The Width of a circuit is the maximum number of components in a stage. The product of the depth and width provides an upper bound on the size of the circuit.Depth and Width of a combinational circuit:WidthOutputInputDepth......An omega circuitRow012 3 4 5 6 71 2 3012 3 4 5 6 7An omega circuit, has n inputs and n outputs, it consists of logn columns (stages), numbered 1,2, …,logn from left to right, with n rows (input and out lines) per column, numbered 0,1,…, n-1 from top to bottom. There are n/2 processors per stage, each with two input and two output lines .the processors in stage j are connected to those in stage j+1, j=1,2,…,(logn)-1, by a perfect-shuffle interconnection. Thus, output line I in stage j is connected to input line 2i in stage j+1, for 1=<i=<(n/2)-1, and to input line 2i+1-n in stage j+1, for (n/2)=<i=<n-1. the circuit has a depth of logn, a width of n/2, and a size of (n/2)logn. In this example of figure, n=8A butterfly circuit012345670 1 23RowButterfly circuit, has n inputs and n outputs, it consists of 1+logn columns, number0,1,…,logn,whith n rows per column, numbered 0,1,…,n-1.let P(i,j) represent the processor in row i and column j. for 0=<j<logn, P(i,j) is connected to P(i, j+1) and P(k,j+1), where the binary representations of i and k Differ only in their jth least significant bit. The circuit has a depth of 1+logn, a width of n, and a size of n+nlogn. In the example of figure , n=8.A merging circuit2478135612345678a Merging circuit receives as input two sequences of data, each consisting of n/2 values sorted in nondecreasing order. It produces as output these two sequence combined into a single sequence of n data values sorted in nondecreasing order. One such circuit, known as the odd-even merging circuit, is shown for n =8. it consists of logn stages, with at most n/2 processors per stage. each processor is a comparator :it receives two values as input and produces the smaller of the two on its top output line and larger on the bottom line. The circuit has a depth of logn, a width of n/2, and a size of 1+(n/2)x((logn)-1).An odd-even-merge sorting circuit 4872156312345678A sorting circuit receives as input a sequence of ndata values and produces as output these same data values arranged in nondecreasing order.one such circuit, know as the odd-even-merge sorting circuit is shown in the figure, it consists of O(logn) stages, with at most n/2 processor per stage. Each processor is a comparator . The circuit has a depth of O(logn), a width of O(n), and a size of O(nlogn).A (theoretically) efficient sorting circuitInputs (n)Outputs (n)4421387215638756214356871234567812345678A (theoretically) efficient sorting circuit consists of a complete tree with leave, 1+logn levels. And a total of 2n-1 nodes. each nonleaf node is circuit made of comparators. The circuit in a node is capable of receiving a set of m numbers, 2=<m=<n, and splitting it into two sets: the node’s top child receives a set of m/2 numbers, each of which is smaller than or equal to the m/2 numbers st to the node’s bottom child. in this way, if n numbers in arbitray order are fed to the root as input, they emerge from the leaves sorted in nondecreasing order from top to bottom .this circuit, referred to as the sorting-by-splitting circuit, has a depth of O(logn), a width of O(n), and a size of O(nlogn)A memory access unit for the RAMProcessorMAUMemoryU000U001U010U011U100U101U110U111In the RAM, there is one processor and a memory consisting of M locations .the model allows the processor to specify an arbitrary memory location from which it wishes to read or to which it wishes to write. The job of the MAU is to set up a path from the processor to the chosen memory location. a MAU for the RAM can be implemented as a binary tree of switches. The tree’s root is connected to the processor, and each of the leaves to a distinct memory location. The tree has 1+logM stages, numbered 1, 2,..,1+logM, with the root at stage 1. the tree links are assumed to be two-way communication lines, a switch can therefore send or receive a datum to or from one of its children and parents. this MAU has depth O (logM) AND width O (M), since the tree has 2M -1 switches, its size is O(M.)A naive MAU for the PRAM U1U2U3U4P1P2P3123412341234123123123123M Memory LocationProcessor Tree Memory Location TreeMAUIn PRAM, there are N processor and M memory locations. The model allows each processor to specify an Arbitrary memory location to which it wishes to gain access. several processors are allowed to read from or Write into the same memory location. a MAU for the PRAM creates paths from the processors to the memory Location. Each processor is connected to the root of a binary tree with M leaves numbered 1 to M, and each Memory location U is connected to a binary tree with N leaves numbered 1 to N. the MAU has a width ofO(N x M), a depth of O(logM + logN), and a size of O(N x M).An efficient MAU for the PRAMSorting CircuitMerging Circuit............U1U2UMP1P2PNN ProcessorsMAUM Memory LocationsAn efficient MAU for the PRAM consists of a sorting circuit