CprE 583 Adaptive Computing Systems

Assignment 4 Distributed on: October 17, 2000

Due on: November 7, 2000

Reading: Dependence Graphs, Signal Flow Graphs, and Mapping Literature.

Problem 1

Canonical mapping: For the DG as shown in Figure(a):

  1. Which of the following sets of scheduling and projection is permissible?

  2. Give the projected SFG for each permissible set.
 

Problem 2

Generalized mapping: For the DG as shown in Figure (b) of Problem 1, which of the following sets of scheduling is permissible?

Problem 3

Binary number multiplication: For the problem of binary number long multiplication, assume that the multiplicand is of length 5 bits and the multiplier is of length 4 bits.

  1. Derive a DG for this problem. The granularity of the node operation of this DG should be in full adders level.
  2. Which projection direction can be applied to obtain an SFG with a serial multiplicand input? How many PEs are needed?
  3. Which projection direction can be applied to obtain an SFG with a serial multiplier input? How many PEs are needed?
  4. Is it possible to obtain a projection SFG that has the property that both multiplicand and multiplier are input serially?
  5. Is it possible to use index transformation to reduce the number of PEs needed?
  6. Implement your design of (2) and (3) any FPGA in lab.