## Homework 1

### Required reading (material covered in class on Jan. 31, 2011)

Parhami

Chapter 5, Basic Addition and Counting.

Spartan-3 Generation FPGA User Guide : Chapter 9, Using Carry and Arithmetic Logic

### Parhami

Sections 6.1, Unrolling the Carry Recurrence

Chapter 7, Variations in Fast Adders

Chapter 7.5, Hybrid Designs and Optimizations

Chapter 28, Reconfigurable Arithmetic

Section 28.2, Adder Designs for FPGAs

### Problem 1

Part 1: Analytical

Design on paper and analyze:

• k-bit digit-serial adder (DSA) with the digit size d (a digit serial adder is an adder that in each clock cycle processes d-bits of the operands X and Y, and generates the corresponding d bits of the sum S)

using the following assumptions:

• an unsigned adder with carry in and carry out
• using a respective interface shown in slides for Lecture 1: Basic Adders
• optimized for minimum latency
• composed of AND and OR gates (with up to four inputs) and inverters only.
2. delays of all gates are independent of the number of inputs, and are equal to the delay of an inverter. Thus, you can assume that the delay of each gate and inverter is equal to 1.

3. area of each gate is proportional  to the number of inputs. For example, area of a 2-input gate is equal to the area of 2 inverters. Assume that the area of an iverter is equal to 1, area of a 2-input gate is equal to 2, etc.

4.
Area of a D flip-flop is equal to 12, its clock-to-output delay is equal to 2, and its setup time is equal to 1.

5. Do not include the areas of the surrounding input and output registers in your computations.

6. All external control signals are registered.

a. draw a schematic of this adder composed of medium level components (such as full adders, half adders, multiplexers, D flip-flops, etc.), and the detailed schematic of each medium-level combinational component, implemented using aforementioned gates only.

b. mark the critical path within each medium-level component and for the entire circuit. Assume that all inputs to the adders, including all control signals are registered. Take the register delay and register setup time into account for all adders including a ripple-carry adder.

c. determine the area and delays of each medium-level component expressed in terms of the delay and area of an inverter.

d. derive the general formulas for the minimum clock period, latency and area of all adders, in terms of the parameters k and d. For area: Do not include the areas of the surrounding input and output registers in your computations. For clock period and latency: take the register delay and register setup time into account for all adders including a ripple-carry adder

e. derive expressions for the following ratios as functions of k and d:

RA(RCA/DSA) = area of a ripple-carry adder / area of a digit-serial adder

RA(DSA/BSA) = area of a digit-serial adder / area of a bit-serial adder

RL(DSA/RCA) = latency of a digit-serial adder / latency of a ripple-carry adder

RL(BSA/DSA) =  latency of a bit-serial adder / latency of a digit-serial adder

RLA(RCA/DSA) = latency * area of a ripple-carry adder / latency * area of a digit-serial adder

RLA(DSA/BSA) = latency * area of a digit-serial adder / latency * area of a bit-serial adder

f. draw functions derived in e., as a function of k, for the following values of the parameters k and d:

d = 4, 8, 16

k = 2^i   for i=4..9.

Part 2: Experimental

Synthesize and implement your circuits for the following values of generics

k = 2^i   for i=4..9,   and d=8,

targeting Xilinx Spartan 3 FPGAs. Use the smallest device of the Spartan 3 family capable of holding any implemented adder for k=2^9=512.

When determining circuit areas, synthesize and implement your circuits without any surrounding registers.

When determining minimum clock periods, synthesize and implement your circuits with surrounding input/output registers.

Calculate all latencies as a function of the minimum clock period, and the parameters k and d.

Draw functions corresponding to the ratios defined in Part 1e.

Compare your graphs from Part 1f with graphs for Part 2. Describe your conclusions in a short report.