Suggested by Martin:

%A John T. Feo, ed.
%Z LLNL
%T A Comparative Study of Parallel Programming Languages:
The Salishan Problems
%S Special Topics in Supercomputing
%V 6
%I North Holland
%C Amsterdam
%D 1992
%K book, text, Hamming's Problem (primes), paraffins problem, skyline
matrix,
doctor's office problem,
languages: Ada, C*, Haskell, Id, OCCAM, PCN, Scheme, SISAL,
dynamic dataflow, functional, imperative,

1. Hamming's Problem
---------------------
Given a set of primes {a,b,c..} of unknown size and an integer
n, output in increasing order and without duplicates all integers of the
form
a^i * b^j *c^k ... <= n
Observe that if r is in the output stream, then,
a*r, b*r, c*r, ... <= n
are also in the output stream.

The problem tests a language's ability to express recursive stream
computations and producer/consumer parallelism, and to support dynamic task
creation.

2. Paraffins Problem
---------------------
Given an integer n, output the chemical structure of all paraffin
molecules for i<=n, without repetitions and in order of increasing
size. Include all isomers, but no duplicates. The chemical formula for
paraffin molecules is C[i]H[2i+2]. You may choose any representation for the
molecules, so long as it clearly distinguishes among isomers.
The problem addresses the representation of recursive tree structures,
the creations and manipulation of those structures and nested loop
parallelism.

3. The Doctor's Office
-----------------------
Given a set of patients, a set of doctors, and a receptionist,
model the following interactions: initially, all patients are well, and
all doctors are in FIFO queue awaiting sick patients. At random times,
patients become sick and enter a FIFO queue for treatment by one of the
doctors. The receptionist handles the two queues, assigning patients to
doctors in a first-in-first-out manner. Once a doctor and patient are
paired,
the doctor diagnoses the illness and cures the patient in a random amount
of time. The patient is then released, and the doctor rejoins the doctor
queue to await another patient. The output of the problem is intentionally
unspecified.
The problem tests the language`s ability to program a set of
concurrent, asynchronous processes with circular dependencies.

4. Skyline Matrix Solver
-------------------------
Solve the system of linear equations.
Ax = b
without pivoting where A is ann by n skyline matrix. A skyline matrix
has nonzero values in row i in column k through i, 1 <= k <= i, and
nonzero values in column k through j, 1 <= k <= j.

The problem tests the ability to define array structures that include
nonessential elements (i.e. the zeros), and given those structure,
efficiency of parallel and iterative array computations.