michaelslab

The collaboration project is a framework for Ada which simplifies the utilization of multiple processors. Even thought the concept is applicable to a broader range of problems we address a specific class of problems.

Lets assume the task is to compute the result \(x_{m}\) from a given start value \( x_{o} \) by computing  for a given \( m\in\mathbb{N} \) the expression

$$ x_{t+1}=H(x_{t}) (t\in 0..m) $$(1)

where \( H:M^{n}\rightarrow M^{n} \)

A speedup of the computation can be achieved if it is possible to compute P subspaces \(M_{j}\) of \(M^{n}\) in parallel, which means that \(H_{j}=H\upharpoonleft M_{j}\;(j=1..P)\).

The developer has to provide a calculation recipe \( (\{M_{j}\},H) \) for (1) which is to be processed by the collaboration of workers. The recipe consist of the function \(H\) and the algorithm which defines the \(M_{j}\) which we will call partitions in the following.

Collaboration API

In order for an API being easy to use, it should be build on a well known metaphor. The Collaboration package presented here provides an API which allows the easy utilization of Multicore CPU's since it is based on the commonly known model of a group of workers. Each worker is working independent of others on some part of the final product which is assembled after all parts are produced.

The proposed API is based on the metaphor of a team of worker (Fig. 1), called a collaboration, sharing the work among them. Initially a collaboration is empty and as much worker as needed can join the collaboration. If there is no work available the worker will wait until some work becomes available.

Basic Idea

Fig. 1 - Collaboration Model

The so called client will submit a recipe to the collaboration for processing. A recipe specifies the calculation formula and the algorithm to calculate the partition \(M_{j}\) for \(j\in\mathbb{N}\)

All workers will start processing by taking a work package in form of a partition until no more work is available any more. In order to collect the execution result the client has to join the team and assemble the results after all workers are done.

The Collaboration API follows this model (see Fig. 2); a worker task which is assigned to a dedicated CPU needs to join a collaboration by calling the Join method. The Join method will block the worker task until the recipe has been made available by the client task.

The client will prepare the input data and calls the method Fork (4) to submit the recipe to the workers. The client has now the option doing something different or join the Collaboration by calling the Join method (5).

The worker will eventually wake up from the join and will call the getPartition to get the next partition id which is to be processed and calls the Compute method with this partition id.

while true loop
    Join(This );                  ( 1 )
    P := GetPartition ( This ) ;  ( 2 )
    Compute ( This , P ) ;        ( 3 )
end loop ;

. . .
end Worker_Task ;

in the main task;

... prepare recipe data ...
Fork ( This );                    ( 4 )
Join ( This );                    ( 5 )

... start processing ..
Fig. 2 - Collaboration API

Measurements done

The achived performance is shown in the picture below, The green line represents the estimated best execution theoretically possible. The yellow like shows the execution time without any parallelism. The red and blue line is representing the execution time of the same job using the collaboration framework but with different partitioning methods. As expected both execution times are converging with increasing number of particles towards the green line.

Basic Idea

Fig. 3 - Measurement results

 

 

Project Home

The source code of the project is hosted at:

https://github.com/merdmann/Collaboration

The idea of this project is not just to provide an implementation but a formal prove at the same time.