Request: Language Evaluation Problems/Solutions

We are in the process of evaluating Sather, an object oriented
language with a parallel extension currently developed at International
Computer Science Institute, Berkeley, CA. We would like to
evaluate and compare Sather to other parallel languages based on
solutions to nontrivial problems that would show what types of
computations and forms of parallelism they can or cannot express.
For example, four such problems were suggested by the 1988
Salishan High-Speed Computing Conference, Gleneden Beach, Oregon.


We invite the proponents of other languages to forward to us
(borisv@icsi.berkeley.edu) their own solutions to the Salishan Problems.
We would like to see the solutions in many other classes of languages. We
also welcome any other problems whose computational models are likely to
provide a good basis for language comparison or evaluation.


Solutions to the Salishan problems or any other interesting problems will
be maintained in order, and will be made generally available.


The descriptions of the 4 Salishan problems and Ada, C*. Haskell, Id,
OCCAM, Program Composition Notation, and Scheme solutions are given in


J.T. Feo, editor
A Comparative Study of Parallel Programming Languages: The Salishan
Problems, Special Topics in Supercomputing, Volume 6
Elsevier Science Publishers, North-Holland, 1992
ISBN 0444881352




Short descriptions of the Salishan problems follow.




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.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.