Homework 1: Sorter Architecture and Analysis

This is a paper-and-pencil, analytical assignment. You should prepare a 1-page draft of your solution, then make an appointment with Sanjay and discuss your solution. You may then revise your solution and submit it. The due date is Thu, Jan 31.

Problem Statement

Precisely describe, the architecture of a P-processor sorter, used to sort N inputs. First consider the case when P=N, and then extend your analysis to the case for N=kP, where k is some integer (this case will require k passes through the array). Some questions to think of:

• How to load and unload the array. Sure, pushing in MAXINT after the data is good, but after that how do you reuse the arch? With a global reset? When can this occur?
• How many cycles does it take to get the data completely out of the array (for one-pass as well as for the multi-pass case)?
• For the one-pass case:
  • How many cycles dos it take till the FIRST output appears?
  • How many cycles dos it take till the first PROCESSOR is done?
  • How many cycles dos it take till the LAST output appears?
  • When does the i-th processor START?
  • When is the i-th processor DONE?
• For the k-pass case, the essential question that you MUST figure out is how to "tightly" interleave multiple passes, without a global reset. Once that is done, you need to think of similar questions as above for the multi-pass case.