Go to the first, previous, next, last section, table of contents.

Overview of `TOP-C'

                       "All right, Mr. Wiseguy,"  she said,  "you're so
                   clever,  you tell us what color it should be."
                       from "The Restaurant at the End of the Universe"
                       by Douglas Adams

A `TOP-C' application is compiled and run using `topcc' (similarly to `gcc') or `topc++' (similarly to `g++'). For example, 

  cp TOPC_DIR/examples/parfactor.c ./
  cp TOPC_DIR/bin/procgroup ./
  topcc -mpi parfactor.c
  # or else:  topc++ -mpi parfactor.cc
  ./a.out

For purposes of documentation, we will standardize on an explanation of topcc. Wherever topcc is mentioned, the description is equally valid for topc++.

In a `TOP-C' application, the programmer defines four callback functions and passes control to the `TOP-C' library through the following command. 

  TOPC_master_slave(GenerateTaskInput, DoTask, CheckTaskInput,
                    UpdateSharedData);

Pictorially, TOP-C arranges for the flow of control among the four callback functions as follows: 

      (ON MASTER)      task input
   GenerateTaskInput() ---------->

  task input   (ON A SLAVE)  task output
  -----------> DoTask(input) ----------->

  task output     (ON MASTER)                    action
  -----------> CheckTaskResult(input, output) ----------->

if (action == UPDATE):
  task input, task output      (ON ALL PROCESSES)
  -----------------------> UpdateSharedData(input, output)

When there is only one slave, the effect is roughly the same as the following sequential C code: 

{ void *input, *output;
  TOPC_ACTION action;
  while ( (input = GenerateTaskInput(), NOTASK != input) ) {
     action = CheckTaskResult(input, output = DoTask());
     if (action = UPDATE_ACTION) then UpdateSharedData(input, output);
  }
}

The routine CheckTaskResult() returns an action, which determines the control structure for a parallel algorithm. A common definition is: 

TOPC_ACTION CheckTaskResult( void *input, void *output )
{ if (output == NULL) return NO_ACTION;
  else if ( ! TOPC_is_up_to_date() ) return REDO;
  else return return UPDATE; }

TOPC_is_up_to_date() returns true if and only if during the interval between when the task input was originally generated and when the task output was returned by the most recent slave, no other slave process had returned a task output during the interim that had caused the shared data to be modified through an UPDATE action. An UPDATE action causes UpdateSharedData() to be invoked on each process. Further discussion can be found in the section on section TOP-C Utilities.

`TOP-C' also supports operation on SMP (shared memory) hardware. In such a case, all data is shared, by default. Hence, an UPDATE action under shared memory causes only the master process to invoke UpdateSharedData(). To avoid inconsistencies in the data, by default `TOP-C' arranges that no slave process may run DoTask() while UpdateSharedData() is running. `TOP-C' also provides support for finer levels of granularity than the procedure level and also for private variables. Further, `TOP-C' is designed so that the same application source code may operate efficiently both under distributed and under shared memory. Further discussion can be found in the section on section Modifying TOP-C Code for the Shared Memory Model.

Three Key Concepts for TOP-C

The `TOP-C' programmer's model is based on three key concepts:

  1. tasks in the context of a master/slave architecture;
  2. global shared data with lazy updates; and
  3. actions to be taken after each task.

Task descriptions (task inputs) are generated on the master, and assigned to a slave. The slave executes the task and returns the result to the master. The master may update its own private data based on the result, or it may update data on all processes. Such global updates take place on each slave after the slave completes its current task. A SPMD (Single Program Multiple Data) style of programming is encouraged.

In both shared and distributed memory architectures, one must worry about the order of reads and writes as multiple slaves autonomously update data. The utilities below are meant to ease that chore, by supporting the ease of the SPMD programming style, while still maintaining good efficiency and generality for a broad range of applications. The software can easily be ported to a variety of architectures.

Data Structures

A task input or task output is an arbitrary buffer of bytes. Internally, it is an arbibrary user-defined data structure, which is opaque to TOP-C. A task input or task output must be encapsulated by a function: `TOPC_MSG( void *data, int size )' before being passed to the system. It is the responsibility of the application writer to place the data in a task buffer.

If a heterogeneous architecture is used, there is an issue of converting data formats. This is the application's responsibility. UNIX utilities are available such as htonl(), ntohl() (for integer byte ordering), and the `XDR' library (RFC 1832, eXternal Data Depresentation, general standard, also including struct's, etc.). `Corba''s `IDL' presents another possible architecture-independent solution. Note that systems following the IEEE floating point standard should already have compatible floating point.

For a further overview, see the section, section Tracing and Other Debugging Techniques, for sequential code that is equivalent to the operation of TOPC_master_slave when there is only one slave.

Go to the first, previous, next, last section, table of contents.