User: Guest  Login
If you experience problems opening the document, please try this link.
Original title:
Transformation parallel ablaufender Programme
Translated title:
Transformation of parallel running programs
Information about the author:
Prof. Dr. Dr. h.c. Manfred Broy, Ordinarius für Informatik an der TU München, erhielt den Leibnizpreis 1994.
Year:
1980
Document type:
Dissertation
Institution:
Fakultät für Mathematik
Advisor:
Bauer, Friedrich Ludwig (Prof. Dr. Dr. h.c.)
Referee:
Seegmüller, Gerhard (Prof. Dr.)
Format:
Text
Language:
de
Subject group:
DAT Datenverarbeitung, Informatik
Keywords:
mathematische Semantik, funktionale Äquivalenz, Nicht-Determinismus, Parallelität, gemeinsamer Speicher
Translated keywords:
mathematical semantics, functional equivalence, nondeterminism, parallelism, shared memory
Controlled terms:
Programmtransformation; Parallelverarbeitung
Abstract:
Entwickelt man Programme durch schrittweisen Übergang von abstrakten zu konkreteren Formulierungen und damit durch allmähliche Ergänzung einer Spezifikation zu einem vollständigen Programm – einer effizienten Version eines Algorithmus, so stehen die einzelnen Glieder in der Kette der Entwicklung in bestimmten Relationen zueinander. Meistens sind sie im Sinn der mathematischen Semantik („funktional“) äquivalent. Die Definition der funktionalen Äquivalenz genügt im allgemeinen um die mathematische Semantik einer Programmiersprache zu charakterisieren.

Wie für die mathematische Semantik lassen sich auch Klassen von Kongruenzrelationen auf Programm(ausdrück)en definieren, die verschiedene Begriffe von „operativ äquivalent“ formal fassbar machen und bedeutend feiner sind, als die durch die mathematische Semantik erzeugte Kongruenzrelation. Die verschiedenen Versionen eines Programms in einer Programmentwicklung sind natürlich im allgemeinen operativ keineswegs äquivalent.

Eine zusätzliche Dimension erhält die Begriffswelt operativer Semantik, wenn auch parallel ablaufende Programm(teil)e betrachtet werden. In allgemeinen Programmsystemen mit parallel ablaufenden Teilen treten charakteristische Phänomene auf, die formale Aussagen über die operative und mathematische Semantik solcher Programme stark erschweren:

- Die Kommunikation zwischen parallel ablaufenden Prozessen bewirkt logische Abhängigkeiten zwischen Programmteilen, die in Aufschreibung (und Ablauf) stark von einander entfernt sind.
- Zusätzlich tritt Nichtdeterminismus als Abstraktion der nicht determinierten zeitlichen Verzahnung der Kommunikationsaktionen parallel ablaufender Prozesse auf.

Gerade hierbei lassen sich Kongruenzrelationen und definierende Transformationen erfolgreich für die Definition der Semantik einsetzen.

In vielen Ansätzen zur Behandlung von Parallelität in Programmiersprachen sind die obigen Phänomene zusätzlich überlagert durch Probleme der Synchronisation, die insbesondere einen breiten Raum einnehmen, wenn über „gemeinsame“ Programmvariable kommuniziert wird. Häufig werden dann zur Definition der Semantik quasiparallele Vorstellungen verwendet. Dabei werden gewisse „atomare“ Aktionen in beliebiger Weise gemischt. Dieses Zurückgehen auf eine Sequentialisierung kann jedoch nicht immer voll befriedigen, weil dadurch häufig weder eine ausreichende Begriffsbildung „echter“ Parallelität, noch eine von möglichen Implementierungen her angemessene Beschreibung erreicht wird. Andere Ansätze trennen parallele Programme völlig von üblichen Sprachelementen sequentieller Programmiersprachen.

Im Gegensatz dazu wird in dieser Arbeit ein Versuch unternommen, von einer im Prinzip funktionalen Programmiersprache ausgehend Sprachelemente für die parallele Programmierung herzuleiten und diese damit mit klassischen sequentiellen Sprachelementen zu integrieren.
Translated abstract:
If programs are developed by step by step transformation from abstract to more concrete formulations and thus by gradual complementation of a specification to a complete program – an efficient version of an algorithm – the single elements in the chain of the development are in particular relation to each other. Mostly they are equivalent in the sense of the mathematical semantic (“functional”). The definition of the functional equivalence is generally sufficient to characterise the mathematic semantic of a programming language.

Classes of congruence relations on programming-terms can be defined in the same way as for the mathematical semantics, which formally realise several terms of “operative equivalent” and which are considerably more subtle than the congruence relation generated by the mathematical semantics. Naturally, the different versions of a program in a program development are in general by no means operatively equivalent.

An additional dimension is given to the vocabulary of concepts of the operative semantics, if parallel running programs (or parts of programs) are observed. In general program-systems with parallel running parts characteristic phenomenons arise, which strongly hinder the formal conclusions about the operative and the mathematical semantics of such programs:

- The communication between parallel running processes causes logical dependence between program parts, which are far apart from each other regarding the notation (and run).
- In addition non-determinism is arising as abstraction of the non determised, temporal interlocking of the communication-actions of parallel running processes.

Especially in this context congruence relations and defining transformations can be successfully employed for the definition of the semantics.

In many approaches dealing with the parallelism in programming languages, the above described phenomenons are additionally superimposed by problems of the synchronisation, which take up a broad space, especially if it is communicated using shared program-variables. Frequently, quasi-parallel perceptions are used for the definition of the semantics. Thereby certain “atomic” actions are mixed in any manner. This retrograding to a sequencing can, however, not always completely satisfy, because thereby often neither a sufficient concept formation of “true” parallelism nor one from possible implementations adequate description can be reached. Other approaches completely separate parallel programs from the common language elements of sequential programming languages.

In contrary thereto, an attempt is made within this work to deduce language elements for parallel programming starting from a principally functional programming language and to integrate them with classical sequential language elements.
Publication :
Alumni & Career Service
Notes:
Die Retrodigitalisierung konnte dank Spenden von Alumni der TU München finanziert werden.
Date of submission:
21.11.1979
Oral examination:
04.02.1980
Pages:
158
BVB-ID:
BV000995839
Last change:
29.02.2008
 BibTeX