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

 

Recommended reading (material to be covered in class on Feb. 7, 2011)

        Parhami

Chapter 6, Carry-Lookahead Adders

Sections 6.1, Unrolling the Carry Recurrence

Section 6.2, Carry-Lookahead Adder Design

Chapter 7, Variations in Fast Adders 

Section 7.3, Carry-Select Adders.

Section 7.4, Conditional-Sum Adder

Chapter 7.5, Hybrid Designs and Optimizations

Chapter 28, Reconfigurable Arithmetic

Section 28.2, Adder Designs for FPGAs


Homework Assignment 1

due Monday, Feb 14, 2011, 4:30 PM

Please submit printed and/or handwritten reports in class.
Please submit all VHDL source codes, including testbenches, using Blackboard.

Problem 1

Part 1: Analytical

Design on paper and analyze:

using the following assumptions:

1. each adder is

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.

For each adder:

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

Model ripple-carry adder, bit-serial adder, and digit-serial adder in VHDL. Use generics for k and d. Use "+" for the ripple-carry adder and the ripple-carry-adder part of the digit-serial adder.

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.

Bonus Task 1

Repeat your experiments, generate graphs, and extend your report for Altera Cyclone II.

Bonus Task 2

What formulas the best describe the delays of ripple-carry adders for Spartan 3 and Cyclone II FPGAs? What are the differences in constants used in these formulas?

Hints

Use ATHENa and its feature called Generics Search to automate and speed up the collection of results.