Database Parallelisation of Numerical Algorithms

Comparing Correctness Criteria:

We are comparing different correctness criteria of database theory on the one hand with the related theory of concurrent programming on the other hand. With this understanding, we aim to provide a theoretical basis for using database techniques to parallelise numerical algorithms. While such parallelisation may not result in faster algorithms, it may result in easier methodologies for developing parallel algorithms.

(larger image: click onto the image, please)

Actions, Transactions and Conflicts:

The idea consists in decomposing a numerical algorithm into steps and considering them as transactions that run concurrently, observing some given external partial order. Each step, in turn, is decomposed into simpler steps that are considered as actions in the database terminology. Actions from different steps that semantically commute can be executed in parallel even though they may conflict at a lower level of abstraction, i.e. even if they access some shared data. The transaction manager at such a lower level in the sense of multi-level transaction management will take care of correct shared data access.

In a first, simple approach we consider only assignments and define an action A on an arbitrary level as

A(x, f(x1, ... , xn)) := ( x = f(x1, ... ,xn) ).

variables of the assignment correspond to database objects. For example, the matrix assignment A = AB can be written as the action A(A,AB), the scalar assignment t1 = a11*b11 + a12*b21 as the action A(t1, a11*b11 + a12*b21).

Furthermore, we have to define a conflict relation CON between actions. If two actions are in conflict, they are not commutable. CON is defined as:

(A1(x, f(x1, ... , xn)), A2(y, f(y1, ... , yn))) in CON :
==> x in {y1, ... , yn} or y in {x1, ... , xn} or x=y

Moreover, in order to obtain intra-transaction parallelism we do not want to execute all actions of a certain transaction serially. Instead, in most cases it is possible to schedule certain actions of the same transaction concurrently. To determine this partial intra-transaction order we define a precedence graph for every transaction. If there are conflicting actions in a transaction, we must at least define precedences between those actions.

Example:

Matrix multiplication could consist of only one action A(A, AB) on level 3. There are no conflicts and no precedences on this level. On level 2 each action A2i-1 does not commute with A2i (\/ i in {1, ... , n}). We determine the following intra-transaction-order

{ A2i-1 --> A2i | i in {1, ... , n} }.

Finally, each action at level 2 is a transaction on level 1. On this level, all actions commute with each other within every transaction and can be scheduled concurrently, hence no precedences have to be defined here. Each action of kind A2 of level 1 is a simple, scalar assignment and therefore builds a transaction on level 0 including exactly the same action.

The actions of kind A1 of level 1 are summing up an array of products with in a level-0 transaction with the intra-transaction order

{ A(tij, 0) --> A(tij, tij+aik bkj) | i,j,k in {1, ... , n} }.

Recovery:

We will also investigate whether the recovery component of a database system can improve our parallelisation techniques or provide new expedient features. It is intended to implement all these techniques on top of (parts of) CONCERT.

References

Alonso, G., Blott, S., Fessler, A., Schek, H.-J., Correctness and Parallelism in Composite Systems. In: Proc. of the 16th Symp. on Principles of Database Systems (PODS'97), Tucson, Arizona, May 1997.

Armin Feßler, Konfliktkonsistente Serialisierbarkeit für hohe Parallelität. In: 10. Workshop "Grundlagen von Datenbanken", Konstanz, Germany, June 1998.

contacts: Prof. H.-J. Schek

!!! Dieses Dokument stammt aus dem ETH Web-Archiv und wird nicht mehr gepflegt !!!
!!! This document is stored in the ETH Web archive and is no longer maintained !!!