Brain Aid Prolog Abstract
This file is intended to give you a brief idea about BAP. Please
see the tutorial for details.
The BAP system consists of the following components:
Low Level Message Router
The router provides the connection between processes. Processes
are identified by a unique ID, allowing messages to be sent to any
processes at any time. The low level router works transparently
and allows to see any kind of network as a 'pool of processes'.
The actual topology may affect communication performance, but is
in general hidden to the user (it is possible to place processes
directly on certain processors).
Responsible for memory management, loading and execution of applications
and the process management.
PROLOG Runtime System
This component includes several libraries, predefined predicates
such as i/o functions, object management and an interface to C -
routines. Code modules can be recompiled at runtime and replaced
even in a running application.
The compiler is the central part of BAP. The BAP PROLOG dialect
is based on the standard as defined by Clocksin and Mellish, 1984.
Variables are not typed, but an optional type checking (for debugging
purposes) is available. The BAP compiler is written in PROLOG and
runs as an application on the Transputer system. It is not necessary
to leave the development environment or reset the Transputer network
to run the compiled programs.
Host Server System
The I/O server system is available for MS WINDOWS and X Windows. Together
with the runtime system, the host server provides a comfortable development
environment, including source level debugging of multiple processes.
Other features are graphics output, file I/O to the host file system
and all the little details provided by modern windows environments.
The concepts used to implement BAP are based on the idea that programming
on parallel systems should be as easy as programming on sequential
computers. Although parallelism seems to be inherent in any natural
process, the programmers mind is trained to break down a problem into
small steps which are executed sequentially. We try to use both ideas
by letting the programmer decide at which level the parallelism should
start. Systems that provide automatic parallelization will never be
able to optimize code as well as a programmer with all his knowledge
of the problem. We do not think it wise to ignore the programmer's
intelligence. As a result we decided to base our system on the well
known sequential PROLOG language and provide efficient extensions
for communication and synchronization.
The Compiler produces genuine assembler code for the Transputer. This
allows direct access to the Transputer communication hardware.
The process of compiling PROLOG files can be executed concurrently,
as single predicates do not contain dependencies needed before linking.
The source files are splitted into smaller chunks by the use of
keywords, which for example indicate the start of a new predicate
description. These chunks may be treated separately until linking
is required. Furthermore, scanning, parsing, code generation and
linking may be executed in pipelines.
PROLOG programs are built up of MODULES with external references
made public by IMPORT and EXPORT statements.
These modules are loaded on demand from the host server or from
neighbour nodes that loaded these modules before. The exported predicates
can be called by name. This allows interpreting shells and interactive
debugging. Single modules may be replaced by newer versions even
in a running application. This allows immediate examination of changes
The debugger traces processes at source level. Several debugging
sessions can run parallel on the host server, enabling comfortable
tracing of complex parallel constructs. Debug windows show the executed
sources as well as the parameters actually passed to and returned
from subgoals. Trace can be switched on and off by the host system
and/or the program. Another debugging feature is the message spy
facility that can be used to intercept messages to any object.
There are no limitations to the number of PROLOG processes or
objects started on each Transputer node, except for the amount of
memory available. This allows the development of even highly parallelized
applications on small machines. They can later be executing on larger
Some standard benchmarks might give an idea of the current speed of
the system. The listing given in Appendix A has been compiled exactly
as printed here, so it also demonstrates the use of BAP. The benchmarks
are sequential PROLOG programs running on a single Transputer T800
20MHz. The benchmarks were taken from 'IMPLEMENTING PROLOG v2 by D.
Warren, D.A.I Research Report No. 40'.
The output after a bench(1000) call was the following:
Time: 35.70 ms
Time: 32.85 ms
Time: 3.13 ms
Time: 3.40 ms
Time: 2.25 ms
Time: 2.25 ms
We expect speed improvements with the introduction of typed variables
related code optimizations. Some of the optimizations possible with
sequential machines cannot be used, for instance an atom table is
not possible without a shared memory between processors.
The following example shows the well known queens problem solved by
a simple farm concept built from message passing primitives. The 'exec'
predicate interprets its arguments as a goal to be executed on a concurrent
process. 'Send_msg' and 'rec_msg' are used to synchronize the termination
of the main process to enable timing. They could be used to collect
the results by the client process, but in this case we preferred to
direct output directly onto the screen.
A call to pqueens(8) is executed in 77.3 seconds on a single T800
20MHz. With 4 nodes in a pipeline topology the program reached a
time of 20.4 seconds.