Problem 1. Consider the following combinational logic circuit constructed from 6 modules. In the diagram below, each combinational component is marked with its propagation delay in seconds; contamination delays are zero for each component.
latency = longest path from X to C(X) = 1 + 30 + 20 + 2 = 53
throughput = 1/latency for combinational circuits = 1/53
We need 4 registers:
throughput = 1/(max pipeline stage delay) = 1/30
latency = (1/throughput)*(number of pipeline stages) = 30 * 3 = 90
throughput = 1/(max pipeline stage delay) = 1/20
latency = (1/throughput)*(number of pipeline stages) = 20 * 4 = 80
A.
Problem 2. Partial Products, Inc., has hired you as its vice president in charge of marketing. Your immediate task is to determine the sale prices of three newly announced multiplier modules. The top-of-the-line Cooker is a pipelined multiplier. The Sizzler is a combinational multiplier. The Grunter is a slower sequential multiplier. Their performance figures are as follows (T is some constant time interval):
Throughput Latency Cooker 1/T 5T Sizzler 1/4T 4T Grunter 1/32T 32TCustomers follow a single principle: Buy the cheapest combination of hardware that meets my performance requirements. These requirements may be specified as a maximum allowable latency time, a minimum acceptable throughput, or some combination of these. Customers are willing to try any paralleled or pipelined configuration of multipliers in an attempt to achieve the requisite performance. You may neglect the cost (both financial and as a decrease in performance) of any routing, latching, or other hardware needed to construct a configuration. Concentrate only on the inherent capabilities of the arrangement of multipliers itself.
It has been decided that the Cooker will sell for $1000. The following questions deal with determining the selling prices of Sizzlers and Grunters.
If there is a performance requirement for the latency to be <= 4T, then there is no combination of Cookers that will meet this performance requirement. So it is in theory possible to sell some Sizzlers at any price. Using multiple Cookers can further improve the overall multiplier throughput, but their latency cannot be shortened.
The minimum price for a Sizzler is $250.01 if we want to continue to sell Cookers. If the price of a Sizzler is less than that, 4 Sizzlers could be used in parallel to achieve the same throughput as a Cooker with a better latency in the bargain.
The maximum price for the Grunter is $999.99 since for applications that can accept long latencies (>= 32T) it's worth buying a Grunter if it saves any money at all.
There is no minimum price for a Grunter that would cause every customer to buy Grunters instead of Cookers. The latency of the Grunter will always be 32T, so when performance requirements demand latencies < 32T, Grunters won't do the job.
Sizzlers will be considered when they cost $250 or less. Grunters may be considered when they cost $124.93 or less. To see this, consider the case when Sizzlers cost $125.01. Buying seven Sizzlers would yield a latency of 40T at a cost of $875.07. The customer cannot afford another Sizzler, but adding a single Grunter for $124.93 will reduce the latency to 36T. All optimal configurations are explored below:
Problem 3. Peculiar Peripherals, Inc. Builds a combinational encryption device constructed of nine modules as follows:
The device takes an integer value X and computes an encrypted version C(X). In the diagram above each combinational component is marked with its propagation delay in microseconds; contamination delays are zero for each component.
Latency = 5 + 3 + 1 + 5 + 3 + 3 + 5 = 25us. Throughput = 1/25us.
We can remove some of the registers implied by contours (eg, those shown with dotted lines) without decreasing the throughput. There are several equivalent variations of this diagram.
There a six registers in each input-output path and the clock period is 5, so latency = 30 and throughput = 1/5.
Problem 4. Consider the following combinational encryption device constructed from six modules:
The device takes an integer value, X, and computes an encrypted version C(X). In the diagram above, each combinational component is marked with its propagation delay in seconds; contamination delays are zero for each component.
In answering the following questions assume that registers added to the circuit introduce no additional delays (i.e., the registers have a contamination and propagation delay of zero, as well as zero setup and hold times). Any modifications must result in a circuit that obeys our rules for a well-formed pipeline and that computes the same results as the combinational circuit above. Remember that our pipeline convention requires that every pipeline stage has a register on its output.
When answering the questions below, if you add a register to one of the arrows in the diagram, count it as a single register. For example, it takes two registers to pipeline both inputs to the rightmost module (the one with latency 4).
Latency = delay along longest path from input to output = 2 + 3 + 4 = 9.
Three. Playing by our pipelining rules, we always add a register to the output. The increase the throughput we need to add other register that bisect the circuit. The cheapest place to do this is just before the "4" module, requiring two additional registers.
The best throughput we can achieve with 5 registers is 1/5: place 3 (!) registers on the output and two registers on the arcs leading to the "4" module. If we use 4 registers to divide the circuit between the "2" and "3" modules, the resulting throughput is 1/7.
Yes: 1/4, because the best we can do by just adding registers is to segregate the "4" module into its own pipeline stage.
Lower bound on latency = 9. We can never make the latency less by adding pipeline registers; usually the latency increases.
Problem 5. Consider the following pipelined circuit: The number written on top of each combinational element indicates its propagation delay in nanoseconds. Assume that the pipeline registers shown are ideal (they have a propagation delay, contamination delay, hold-time and a set-up time of 0 ns).
8ns since we have to leave time for the logic between registers A and C to do its stuff.
32ns = 4 pipeline stages at 8ns clock period.
Removing F and G combines the last two pipeline stages into a single pipeline stage. The latency improves to 24ns and the throughput stays 1/8ns.
We can do it with four registers if we allow ourselves to use only a single register on values that go to multiple inputs:
The clock period would be set by the delay of the pipeline stage containing the "8" module: tCLK = tPD,REG + 8 + tS,REG = 11ns. So the throughput would be 1/11ns.
tS,X = 7 + tS,REG = 8ns.
We need to add 2 new registers:
Problem 6. You have the task of pipelining a combinational circuit consisting entirely of 2-input NAND gates with 1ns propagation delay by adding registers having tS=1ns, tH=1 ns, tPD=2 ns and tCD=1 ns. The propagation delay of the original combinational circuit is 20 ns.
If the combinational circuit has a tPD of 20ns when built from 1ns components, there must be an input-output path involving 20 components. To get maximal throughput, we'd place each component in its own pipeline stage for a total of 20 stages. Each stage requires tPD,REG + tPD,NAND + tS,REG = 2 + 1 + 1 = 4ns to do its job. So the latency of the circuit pipelined for maximal throughput is 80ns.
Problem 7. Circuits Maximus, Inc. makes circuits which compute the maximum of two unsigned binary numbers. They are constructed using combinational 1-bit Maximizes modules which are cascaded to deal with longer words, as shown below:
This diagram show a 4-bit Maximizer chain which computes at the M outputs the larger of the A or B input operands. Each Maximizer module takes the Ith bit of each of two binary operands, A and B, as well as comparison outputs from the next higher-order Maximizer module in a chain, as shown below:
A "1" on either of the inputs AGin and BGin from the next higher-order module signals that A or B, respectively, is greater; both inputs are zero if the higher-order bits are identical. The M module computes the output values AGout and BGout from AGin, BGin, Ai and Bi and sends these outputs values to the next lower-order M module. It also passes either Ai or Bi as the Mi output, denoting the Ith bit of the maximum of A and B.
An implementation has been developed for the M module that has 10ns propagation delay and a 2ns contamination delay.
In this circuit, the maximum of four 4-bit unsigned numbers is computed and appears at the output M3..M0. What is the latency and throughput of this combinational circuit, assuming that each M module has a propagation delay of 10ns?
The longest path from inputs to outputs passes through 6 M modules, so the latency is 60 and the throughput is 1/60.
The solution below uses a different technique for pipelining a circuit. Start by labeling each module with its maximum "distance" from the inputs, i.e., the largest number of components that have to be traversed on some path from the inputs to the module in question. Label all outputs with the length (in modules) of the longest path from input to output label each input with "0". The number of pipeline registers required on each wire is the difference between the label at the start of the arrow and the end of the arrow.
A common mistake: forgetting to add the necessary pipeline registers on the input and output arrows.
Problem 8. The following combinational circuit takes a single input and produces a visual output by lighting the light on the center component module.
Consider the result of pipelining the above circuit for maximum throughput, using the minimum number of registers necessary. The result would be a pipeline such that input asserted during clock period I produces the proper output on the light during clock period I+K (we want minimal K which gives maximal throughput).
Using the pipelining technique described in the previous problem, we can see from the labels that 7 registers would be required on the wire marked X: