raphael@ms.uky.edu (Raphael A. Finkel) (02/17/88)
Raphael A. Finkel (raphael@ms.uky.edu) Yackos, DIG
POT 959
Computer Science Department
University of Kentucky
Lexington, KY 40506-0027
1. DIG: Distributed implementation of Graphs
The success of DIB, the Distributed Implementation of
Backtracking, suggests that similar packages can be designed
for algorithm classes besides We are investigating two new
application packages for distributed computation. The first
is a distributed incremental problem solver (DIPS), for
which we have identified uses such as programmed-logic-array
folding, parser generation, and heuristic solution to the
traveling salesperson problem. DIPS is meant to generalize
several situations we have recently encountered: Algorithms
develop information incrementally and are able to expand the
frontier of knowledge along different paths simultaneously.
However, to the extent that exploration is based on stale
information, progress is either slower or less fruitful.
The second package is a distributed implementation of graph
algorithms (DIG), which will be useful for grid-based
numerical algorithms, graph-based optimization problems,
relaxation, and others. Information of interest to the
application may be stored in each vertex and in each edge.
(In comparison, DIB allows information to be stored with
each node of a tree.) Like DIB, work will be automatically
distributed in a fault-tolerant fashion.
1.1. Yackos: Yet another communication-kernel operating
system
Yackos is a communication-kernel operating system being
implemented on the Sequent multicomputer. It attempts to
provide an exceptionally simple communication interface to
processes in order to provide very high bandwidth
communications with very low latency. It achieves this goal
by the following methods:
* The communication primitives are very low level. Message
buffers are taken from free queues and placed on outgoing
queues. There are two fixed message sizes, each with its
own queues. Destinations are given as process
identifiers.
* Communication does not necessarily require kernel calls.
Queues and other context information are shared between
the kernel and the process. The process may inspect this
information at any time. The only kernel calls are (1)
to block the caller until any queue changes state, and
(2) to tell the kernel to look at the queues and send any
messages on the output queues.
* On multiprocessors such as the Sequent, the kernel can
run simultaneously with the processes without requiring
any context switch.