Sat, 24 Jun 1995 04:26:53 GMT

Related articles |
---|

Request: Language Evaluation Problems/Solutions borisv@ginkgo.CS.Berkeley.EDU (1995-06-24) |

Newsgroups: | comp.compilers |

From: | borisv@ginkgo.CS.Berkeley.EDU (Boris Vaysman) |

Summary: | Language Evaluation Problems/Solutions |

Keywords: | OOP, parallel, question |

Organization: | University of California, Berkeley |

Date: | Sat, 24 Jun 1995 04:26:53 GMT |

Status: | RO |

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.

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.