BU/CLA CS-551
Parallel Computing: Models, Languages, and Architectures
UNITY Specification of parallel programs to compute the rank of a
vector element
Define the rank of an element A[j] in an integer array A[0..N] as the
number of items in A[0..N] smaller than A[j] plus the number of items
in A[0..N] equal to A[j] with subscripts smaller than j.
- Write a Unity program to set the element R[j] of an integer array
R[N] equal to the rank of A[j] in the array A.
- Rewrite your program for the following architectures:
- A sequential architecture.
- A synchronous shared memory SIMD architecture with N processors.
- A synchronous shared memory SIMD architecture with N/k processors,
where k = 1, 2, ... is the virtual processing ratio.
- A synchronous shared memory architecture with N^2 processors.
- In each one of the above cases, estimate the time complexity
(assume that each state change is equivalent to a unit of time).
This document has been prepared by Professor Azer Bestavros
<best@cs.bu.edu> as the WWW Home Page for
CS-551, which is
part of the NSF-funded
undergraduate curriculum on parallel
computing at BU.
Date of last update: October 20, 1994.