BAP Online Manuals : BAP Overview : Introduction : About Brain Aid Prolog
Previous: Introduction
Next: Things you MUST know!

1.2.1. About Brain Aid Prolog

The BRAIN AID PROLOG system and programming model is an implementation of a standard prolog on a parallel architecture with a "communicating sequential processes" model.

Although this general description should be sufficient for experts, we in the following will give more details and additional information as an introduction to our system.

To the PROLOG programmer:

Brain Aid Prolog (BAP) is yet another approach to make the power of the new parallel technology usable to the "real world programmer". We took a standard PROLOG compiler and added a runtime environment that suits parallel architectures. Together with your favorite editor on the host computer you gain a quite flexible and pleasant to use programming environment.

Though we tried to stay as close to known sequential PROLOG implementations as possible, the parallel nature of BAP causes some differences:

Communicating Sequential Processes:

.. is the name of the parallel paradigm we chose to realize BAP. CSP means that parallel execution is based on independently running sequential processes. In BAP, these processes communicate and synchronize exclusively by exchanging messages.

This means that each PROLOG process behaves just like any sequential PROLOG engine (this includes that each process owns a private database to which other processes have no access). Things get more interesting when you try to make several of these processes run concurrently.

Topology Independence

BAP is based on concurrently running processes. The main idea is to keep the two levels of an application - the application code and the distribution of the concurrent processes - as far apart as possible. You will find a few examples within your distribution, that run as well on a single node as on a 16 Transputer machine without ANY changes (it nearly becomes a little boring that this is so easy and that not even the topology of the network matters). The only difference is the execution time. To really use the power of a bigger network (32 - 4096 nodes) a little more effort is required, as communication time becomes more important and the speedup will not be linear with the number or Transputer nodes.

Messages

A message in BAP can be any PROLOG term. Messages are not flat memory chunks that are send around. Instead, everything you can "put" into a variable can be a message: A single integer or the entire parse tree of a compiler. You neither have to worry about the message size nor about the routing path through the network.

WIO Introduction:

The BRAIN AID PROLOG system is a parallel PROLOG system designed for use on parallel Transputer machines. It provides several operating system like features that are rather unknown to the Transputer OCCAM or C programmers. These features include network resource management, multiple process host communication, multiple applications, source level debugging and many more.

Some of these features require host communication abilities that can not be satisfied by the standard I/O servers found with the standard development tools for OCCAM or C. It was necessary to develop an enhanced server: WIO, the Windows I/O server.

The traditional approach to host I/O on Transputer systems is based on OCCAM protocols and requires a specific process on the host Transputer. Only this process communicates with the host server.

BAP contains a transparent message passing system. The host server is fully integrated into this scheme and now seems to be just another PROLOG process somewhere in the network, receiving and sending PROLOG messages from any process wishing to communicate with it. No extra interface process on the host Transputer is required.

To allow any process to request I/O functions at any time naturally requires a host operating system that is capable of multitasking.

WIO is a BAP host server software running under MS-Windows. Although this is not really an operating system, Windows' multitasking capabilities are sufficient to run a host server for your Transputer system.

WIO also is responsible for network management, reset and application loading. These functions are accessed via the Console window .

Another important task is the support of source level debugging of parallel processes, and maintenance of graphics windows.

Host server programs for the BAP system are available for other front end computers as well (UNIX and X- Windows, for example). Contact support for details.

The host server / back end model

Experienced Transputer users should skip this chapter, but users new to the Transputer architecture might be worried by the idea of having two or more (or far more) computers at work at once.

The idea is to have one computer, the host computer (in most cases your PC or workstation) do all the interaction with the user, with the others working quietly in the background.

The Transputer is (or was) a powerful RISC processor equipped with fast communication hardware and a complete memory interface on chip. This makes it possible to design cheap processing modules (or īnodesī) that can easily be assembled to large machines. Specialised hardware for disk I/O or graphics can be added, but this is usually taken care of by the host computer.

On your PC or workstation you will start an application, the host server program, that controls communication with the Transputer network via a link interface. This software (in our case usually WIO or XWIO) interacts with the user and provides file system access to the Transputers.

To run PROLOG programs, you need not worry about programming your host computer or designing communication protocols, all this is done by the runtime system and the host server.

Boot process:

To help with difficulties during the bootstrap of your machine, we will explain the boot process of PROLOG and WIO in detail.

On reset (at primary Reset menu item is selected) WIO will activate the link's reset signal (or call the link driver DLL reset entry) and boot the transputer with a boot binary. This is a straight forward transputer boot which should work on any board correctly connected to the PC. In case of problems check the link address entry in the setup dialog or your link driver's configuration and your transputer's cabling and power supply. Success of this phase is indicated by the message "System Reset" on the console window.

In most transputer systems a reset of the root node will have reset all nodes in the network ("global reset"). This is sufficient for BAP and does not pose any problems. Systems with a neighbour reset via register (Parsytec nodes) require a reset from the booting transputer. This process is done by the BAP boot phase. Other forms of active reset must be supported externally. In most cases it is possible to write a short program (in OCCAM or the like) that resets the whole network and terminates without booting nodes. This must be executed before every reset by BAP.

If you encounter trouble or have an exotic hardware, please contact support . Note that we will need precise information about your hardware to be able to help.

The second step depends on your selection of network topology file. The simple case is a precompiled network file with the ending ".BOO" which contains all link connections in your network and the order in which nodes are booted. This is the most efficient way to boot larger networks.

The alternative is the selection "generic" in the support . Note that we will need precise information about your hardware to be able to help.

The second step depends on your selection of network topology file. The simple case is a precompiled network file with the ending ".BOO" which contains all link connections in your network and the order in which nodes are booted. This is the most efficient way to boot larger networks.

The alternative is the selection "generic" in the setup dialog , which will boot the file "GENERIC.BOO". This is a small program that explores the network by trying to boot along every available link. The network will be reset, connected and booted just like the precompiled version, but link communication and reset order will not be optimised for performance. The topology information found by GENERIC.BOO is written to the current directory into a file "FOUND.NET". By compiling this file with the NETCOM tool, you can create an optimised file for later use. With less than four nodes, generic booting will not cost performance, but larger networks can be severely slowed down.

After booting, the console window will display some network information, and the kernel start-up phase begins with a short welcome message. At this point the BAP runtime system is running on all nodes and PROLOG files are being loaded from disk.

The kernel automatically starts a first PROLOG process on every node. This will the start a number of servers for PROLOG tasks. node 0 additionally boots the system manager process.

The system manager receives messages from all servers in the network and keeps a database of available resources. The servers will then enter a task loop waiting for messages. We now have a complete BAP system running. The only thing missing is a user program to run.

As soon as the system manager is up and running, it sends a ready message to the host server (WIO, in most cases) who will respond with a simple run(shell) command. You can change this command with the default file option in the setup dialog.

For details on the PROLOG processes refer to Tutorial .

PROLOG Processes

The BAP system appears as a pool of processes in the network waiting for tasks.

Every PROLOG process is capable of executing standard sequential PROLOG programs. The programs or tasks making up a BAP application are distributed to the servers by the system manager. This allows simple load balancing without explicit placing of processes or even knowledge of the network's size.

A close look at the process of actually starting the shell program on the network explains several aspects of the BAP programming model.

WIO (the host server program) has no information about network size or available resources. It sends its run request to the system manager (The same thing happens when you select the 'Open' menu item with an .LKD file).

The system manager checks its database for available resources (servers) and selects one of them. The selection process guarantees a fairly even distribution of tasks on the network, provided the programs are of roughly the same size.

It will then send the request (e.g. run(shell) ) directly to the server who is suspended in a rec_msg call waiting for messages.

The server then satisfies the request by calling the goal. The run predicate loads a binary (here "SHELL.LKD" and executes a goal ("shell").

We now have an application running somewhere in the network. If this application requires additional computing power (that is other servers), it will simply send requests to the system manager to allocate resources. This functionality is provided by the dcall predicates or by the object layer.

You can start additional applications in the network (select the Open menu item) without interfering with the running shell or other applications provided there are servers left in the system manager's database. In case there are no servers left, the request will be stored until servers finish their current tasks and report back to the system manager. This method creates a potential danger of deadlocks. To avoid this, it is possible to dynamically create additional servers.

As you will have noted, any server can execute any program. This implies that a server called by the system manager has a private empty database. In fact every process has its own database which is flushed before the server calls back the system manager.

If you require persistent data between calls, you can write your own message loop to avoid the termination of the server. This has the disadvantage of having vast resources of RAM bound to a process which might be suspended. To avoid this, the object layer stores ist data between calls in object databases. So instead of refering to a server with via a ProcessID, an ObjectID relating to an object database is provided that can be linked to any process on the same node . Thus, storage besides the database contents ( Prolog Stack, Trail, etc. ) is only needed during computation.

Later versions of BAP running on more complex hardware (with more memory) will create servers dynamically and destroy them instead of having suspended processes waiting everywhere. Currently the cost of the creation of a server is too high to do so for every remote call.

Related topics: Tutorial

Routing

The BAP runtime system provides an abstraction layer on top of the Transputer hardware that greatly simplifies parallel programming in PROLOG.

In traditional Transputer environments you had to explicitly place processes on computing nodes, establish channels between processes and define communication protocols along these channels. Communication between processes on different nodes was difficult, because each Transputer has only four external links, multiplexing software was required to share these channels...

Communication with BAP is completely message oriented. Any process anywhere on the network can send a message to any other process if it knows the recipient's address.

The router software running in the BAP operating system transports the messages along links to the correct process's message base (mailbox).

The addresses used for routing consist of a Transputer id and a process id unique for a process on the specified node. This information should never be hard-coded into a PROLOG program, as the placement of processes is done dynamically. The only fixed addresses in the network are the system manager at (1,1) and the host server at (0,0).

This method of virtualising the Transputer network allows scalable parallel applications and independence from machine size. It simplifies programming and allows the programmer to concentrate more interesting issues.

Nevertheless there is a performance trade-off caused by the message routing process, link bandwidth is not used with maximum efficiency and the automated placing does not produce optimal results. PROLOG processes tend to do much more processing than communication, and this should be the goal of the programmer. Do not try extreme fine grain parallelism with a CSP model.

A specific and optimised placing of processes on computing nodes is possible for the experienced programmer. After profiling your processes, you can make more detailed requests to the system manager to get resources on distinct Transputers. Refer to the library reference for details.

The low level router needs topology information describing the hardware connections between Transputers to deliver it's messages. This information, stored in the routing table, is provided at boot time by the ".BOO" file or by the generic network booter.

".BOO" files are generated by the NETCOM network compiler tool. Usually you will simply compile the generic booter's output "FOUND.NET" to create an optimised network file, but it is possible to manually edit the ".NET" files to boot only parts of the network or exclude link connections.

The PROLOG to C library contains a method for accessing hardware links directly to communicate with processors running "alien" operating systems.


BAP Online Manuals : BAP Overview : Introduction : About Brain Aid Prolog
Previous: Introduction
Next: Things you MUST know!