[Kung 82] Reading Assignment

This assignment requires you to read [Kung 1982], and prepare a short, 1-page critique of the paper. You should work individually, and bring your critique it to class on Tuesday 12 Feb. At a minimum, your critique should address the following points:

• Introduction & Conclusions Sections: Critique the claims and predictions that Kung makes, with your 20-20 hindsight of 25 years. Which of them do you think were questionable even then? Which are still valid and which are not? Cite any recent work/trends that you may be aware of (e.g. special purpose computing on graphics processors, FPGAs etc.)

• Systolic Convolution Arrays: The convolution problem has two parameters: N, the number of weights in the filter, and M the number of samples in the input stream. For each of the arrays described in the paper, derive formulas in terms of these parameters for the following performance metrics (not all of them may be relevant, these are just the common metric in evaluating systolic and special-purpose architectures, and you might as well get used to seeing them):
  • Total execution time (for one instance of the problem);
  • Number of PEs;
  • Work (product of the above two) and how it compares to a sequential algorithm;
  • Problem latency (number of cycles until the first output appears);
  • Problem instance period (number of cycles between successive problem instances);
  • PE efficiency or duty-cycle (percentage of cycles that the PE is active, e.g., if every PE is only active every alternate cycle, the PE efficiency is 50%);
  Based on the above, recommend an architecture for the two following cases:
  • M is much much larger than N; and
  • when the two are comparable.

Reference: