Problem Set for Seminar 18

The two papers that we are reading for monday describe a method for transforming loop based codes into systolic structures that are suitable for VLSI implementation. Using the techniques presented show how the following two loops would be implemented on a 1-d array with nearest neighboor communiccation links. Be careful to take into account the data dependencies that come about due to pipelining variables, sometime referred to as relabeling. For each loop show

the loop after all variables have been pipelined
The data dependencies
A transformation matric and the new index set and data dependencies.
specify the running time. Use PI_max - PI_min.

Loop 1:

sum = 0;
for (int i=0; i < Inputs; i++)
   sum = sum + x[i];

Loop 2:

for (int i=0; i < Inputs; i++) {
  y[i] = 0;
  for (j=0; j < Taps; j++)
     y[i] = y[i] + x[i+j] * w[j]
}

Problem Set for Seminar 18

Loop 1:

Loop 2:

Review by: YOUR NAME GOES HERE