The Makbilan Project (1989 - 1995)
The goal of the Makbilan project was to provide a platform for research
on parallel systems.
This was a shared-memory system based on Intel's single-board
computers and Multibus-II technology.
The Multibus-II allows access to the memory of other boards, but does
not support cache coherence.
Our research was not so much on the architecture, as on system support
and parallel programming.
Major projects performed were
- The ParC programming language
- The MAXI runtime system
- The Sim-ParC simulator
- Additional interconnection mechanisms
ParC
ParC is a parallel programming language, based on C, for the shared
memory programming model.
Its main feature is the use of the block structure of the language to
define the scope of shared variables.
The main language constructs (apart from thos of C) are
- parblock: specify a set of activities that should be processes
in parallel
- parfor: specify a parallel loop, where iterations should be
processed in parallel
- pbreak: break out of a parallel construct, killing all the
sibling activities created by this construct
- sync: a barrier synchronization
The parallel constructs, parblock and parfor, can be nested within
each other, and also combined with conventional C constructs such as
branching and loops.
The nesting results in a tree of activities, in which internal nodes
are activities that are blocked waiting for their children to
complete, and leaves are active.
There were also some more sophisticated constructs that allow for
performance optinization and the mapping of activities to processors.
The development of ParC was
continued for some
time by its original author,
Yosi Ben Asher,
at Haifa University.
MAXI
MAXI stands for the makbilan system.
This runtime system was based on Intel's RMK real-time kernel that ran
on each node.
Its main function was to support the constructs of the ParC
programming language, as follows:
- Parblock and parfor: the spawning activity places a spawn
descriptor in shared memory.
Each processor has a special get-work activity, which looks for such
spawn descriptors and creates new local activities accordingly.
- Pbreak: a broadcast interrupt is sent, and all processors
scan their local activities and kill those that are in the affected subtree.
- Sync: the activities that arrive at the barrier are counted
using fetch-and-add.
They use busy waiting, but yield their processor if not ready.
In addition, versions with some special features were created,
including
- Support for gang scheduling
- Support for deadlock detection
- Support for monitoring the unfolding structure of the computation,
with logging for post-mortem display
- Alternative mechanisms for support of the pbreak construct
Sim-ParC
This is a simulator for ParC that runs on a single PC.
Interconnection
Three additional interconnection mechanisms were constructed:
- A gateway board that connected two 20-slot Multibus-II cages into
one logical 40-slot multibus-II
- A crossbar switch that provides direct high-bandwidth connectivity
among processors
- An experimental optical switch connecting the processors with each
other (collaboration with P. Chavel, France).
We also have a Makbilan photo album (total
about 203 KB)
Publications
- Yosi Ben-Asher, Dror G. Feitelson, and Larry Rudolph,
``ParC - an extension
of C for shared memory parallel processing''.
Software - Pract. & Exp. 26(5), pp. 581-612,
May 1996. (126 KB)
- Yair Freidman, Dror Feitelson, and Iaakov Exman,
``The parallel break construct, or how to kill an activity tree''.
In 10th Intl. Parallel Processing Symp., pp. 230-234, Apr 1996.
©Copyright 1996 by IEEE.
Definitive version available from the
IEEE Computer Society Digital Library.
Original extended version available as
Technical Report 91-20 (65 KB).
- Dror Feitelson, Sharon Broude, and Donny Citron,
ParC Programming Manual.
Updated August 1994 (54 KB).
- Dror Feitelson, Yosi Ben-Asher, Moshe Ben-Ezra, Iaakov Exman,
Lior Picherski, Larry Rudolph, and Dror Zernik,
``Issues in run-time support for
tightly-coupled parallel processing''.
In 3rd Symp. Experiences with Distributed & Multiprocessor
Syst., pp. 27-42, USENIX, Mar 1992. (97 KB)
- Larry Rudolph, Miriam Slivkin-Allalouf, and Eli Upfal,
A Simple Load Balancing Scheme for Task Allocation
in Parallel Machines.
3rd Symp. Parallel Algorithms & Architectures, pp. 237-245, July 1991
(69 KB).
- Dror G. Feitelson, ``Deadlock detection without wait-for graphs''.
Parallel Computing 17(12), pp. 1377-1383, Dec 1991.
- Daniel Citron, Dror Feitelson, and Iaakov Exman,
``Parallel activity
roadmaps''.
In Parallel Computing: Trends and Applications,
G. R. Joubert, D. Trystram, F. J. Peters, and D. J. Evans (Eds.),
pp. 593-596, Elsevier, 1994. (66 KB)
- K. Shteiman, D. Feitelson, L. Rudolph, and I. Exman,
``Envelopes in
adaptive local queues for MIMD load balancing''.
In Parallel Processing: CONPAR 92 - VAPP V, pp. 479-484,
Springer-Verlag, Sep 1992.
Lecture Notes in Computer Science Vol. 634. (42KB)
- Martin Land,
The Makbilan Gateway: A Bus Extension Module
for Multibus II.
Technical report 93-10, Dept. Computer Science, The Hebrew University
of Jerusalem, May 1993 (40 KB).
- Y. Ben-Asher and D. G. Feitelson,
Performance and Overhead
Measurements on the Makbilan.
Technical Report 91-5, Dept. Computer Science, The Hebrew University
of Jerusalem, Oct 1991. (55 KB)
- Dror Feitelson,
Makbilan Users Guide.
Internal document, 1991 (48 KB).
- Martin Land,
Makbilan Hardware Guide.
Internal document, 1991 (37 KB).
To the Parallel
Systems Lab home page
To the Hebrew University Institute
of Computer Science home page