Each processor has N input connections and N output connections.
Each processor runs a single function called run()
communication clock cycle. (Note: the communication clock cycle is
the frequency at which messages can be sent or received. It is
significantly slower than the processor clock cycle.) For each
communications cycle run is called with an array of inputs,
containing one value for each of the input connections. As the
function runs it can send one message out along each of its N output
connections. (Note: The outputs messages are collected and sent out
all at once at the beginning of the next communication cycle. In
other words, all communication is synchronous.)
When the parallel machine is turned on, the value for
CURRENT is initialized to an integer. (Note: Every processor
has its own independent value of CURRENT.) On the first communication
cycle the function first_cyle is run. From then on the function
run is called for each subsequent cycle.
You are given the following definitions:
sorted = sort_ints(inputs);
CURRENT = sorted[N/2];
for (i = 0; i<N; i++)
for (i = 0; i<N; i++)
Note: the variable N is set to the number of connections.
expression N/2 yields the largest integer less than or equal to
You are told that these functions are useful for building
machine that can sort integers quickly. (Note: sort_ints takes
an array of ints and returns an array which is sorted smallest to
A) You are given 5 processors labelled A through E, each
with 3 inputs
and 3 outputs. Based on the definitions above, draw a connection
diagram so that the parallel system will eventually sort the numbers
initially stored in CURRENT (the smallest value should appear in
A, the largest value in E).
B) Place the values 3 in A, 4 in B, 2 in C, 1 in D, and
5 in E. Show
values for CURRENT and the messages on the second cycle. Show the
values for CURRENT and the messsage on the 10th cycle.
C) In the general case where there are M processors and
arranged in this fashion, how many communication cycles are required
to sort the numbers? Please use "theta" notation.
E) Ben Bitdiddle shows up and suggests that instead we
machine with processors that have M+1 connections. "That would make the
machine really fast!", he says. Could the programs given above be
used to wire up a machine with M processors, M+1 inputs connections, and
M+1 output connections? Describe how this would work. How many
communication cyles are required to sort the numbers?
F) Does Ben's idea make any sense? Is this really
going to save
anything over a serial implementation.
G) (Extra Credit) Alyssa shows up and suggests that it
might be better
to build a machine with 4 input connections and 4 outputs. Can you
propose a wiring scheme for such a machine? How would it work? Would
it work better than the original 2 input design?