Thesis
Claudio Fleiner
Today's processors provide more and more processing power, yet there are many applications whose processing demand cannot be met by a single processor in the near future, besides, the demand for more processing power seems to increase at least as fast as the speed of new processors and the only way to complete such calculation-intensive programs is to execute them on many processors at once. The history of parallel computers of the last several years suggests that the distributed, parallel computer model will gain widespread acceptance as the most important one. In this model a computer consists of several node, each with its own processors and memory, As such a computer does not offer one global memory space, but rather a separate memory per node (distributed memory), it is no longer possible to directly use the shared memory programming paradigm. However, as it is generally easier to program with shared memory rather than using message based communications, several new languages and language extensions that simulate shared memory have been suggested.
Such a parallel, distributed language has not only to provide special support for managing parallelism and synchronization, the specification and implementation of the language has to address the issue of distributed memory as well. One of the most important issues is the selection of the memory consistency model, which defines when writes of one node are observed by the other nodes of the distributed computer. Many vital optimizations used by compilers for serial languages are often not possible if the memory model is too restrictive, but a weaker memory model makes the language harder to use.
This thesis discusses several problems and solutions for such languages. It uses the language pSather, an object oriented, parallel language developed at the International Computer Science Institute in Berkeley as an example. A very flexible synchronization construct including different implementations of it, is introduced that allows the user to define new synchronization primitives, and avoids deadlocks and starvations in many common cases.
Several memory consistency models and their implications for programmers and the compiler, especially regarding optimizations, are discussed. The effect of several optimizations (adaptations of optimizations used in serial compilers and special parallel optimizations) and their implementation will be shown. The effect of those optimizations will be measured by using test programs written in pSather. The results clearly indicate that a weaker memory model is necessary to achieve the desired efficiency and speedup, even though usage of the language becomes less convenient. However, pSather offers some constructs that solve some of the problems.
The thesis concludes with a summary of the results and some ideas for additional work.
Die heutigen Prozessoren werden zwar immer schneller, trotzdem gibt es nach wie vor viele Anwendungen, deren Verlangen nach Rechenleistung wesentlich grösser ist als die Prozessoren, die in naher Zukunft verfügbar sein werden. Ausserdem steigt der Bedarf nach mehr Rechenleistung mindestens so schnell wie die Leistung der neuen Prozessoren. Die einzige Möglichkeit, um solche rechenintensiven Anwendungen zu implementieren sind parallele Rechner. Die Entwicklung der parallelen Computer der letzten Jahre deutet darauf hin, dass verteilte, aus mehreren Knoten mit eigenem Speicher und einem oder mehreren Prozessoren bestehende Parallelrechner die grösste Verbreitung haben werden. Solche Rechner bieten allerdings nicht mehr einen globalen Speicher an, sondern jeder Knoten des Rechners hat seinen eigenen, privaten Speicherbereich (distributed memory). so dass das gemeinsame Speicherbenutzungsmodel (shared memory) nicht mehr zutrifft. Nun ist es aber schwieriger, Programme zu schreiben, deren Teilstücke nur mit Hilfe von Meldungen, die verschickt werden, Daten austauschen können. Aus diesem Grund wurden verschiedene neue Sprachen und Spracherweiterungen vorgeschlagen, die einen gemeinsamen Speicher simulieren.
Eine parallele, verteile Sprache muss es nicht nur erlauben, die einzelnen Teile zu verwalten und zu synchronisieren, sondern sowohl in der Definition der Sprache wie auch in der Implementierung muss die Simulation des gemeinsamen Speichers klar definiert sein. Einer der wichtigsten Punkte hier ist die Wahl und Definition des Speichermodels (memory consistency model), das u.a. festhält, wann ein Knoten die Änderungen, die ein anderer Konten im Speicher gemacht hat, sieht. Viele der in seriellen Sprachen häufig eingesetzten Optimierungen sind nicht möglich, wenn das Speichermodel zu restriktiv ist, anderseits sind laxere Modelle schwieriger zu programmieren.
Diese Dissertation diskutiert verschiedene Probleme und Lösungsmöglichkeiten für parallele, verteilte Sprachen. Diese werden an der Sprache pSather erläutert. Diese objekt-orientiert, parallele Sprache wurde am International Computer Science Institute in Berkeley entwickelt. U.a. wird ein sehr flexibler Synchronisationbefehl eingeführt, der es dem Benutzer erlaubt, neue Synchronizationsmodelle zu implementieren und der gleichzeitig in vielen Fällen sowohl "Deadlock" wie auch "Starvation" verhindern kann.
Verschiedene Speichermodelle und deren Auswirkungen für den Programmierer und den Übersetzer, speziell im Bezug auf Optimierungen, werden vorgestellt und diskutiert. Der Effekt der verschiedenen Optimierungen (sowohl von Optimierungen die von seriellen Sprachen bekannt sind und angepasst wurden wie auch spezielle parallele Optimierungen) und deren Implementierungen werden vorgestellt. Die Auswirkungen der Optimierungen werden mit verschiedenen Testprogrammen, die in pSather geschrieben sind, gemessen. Die Resultate zeigen eindeutig dass laxere Speichermodelle notwendig sind, um die gewünschte Geschwindigkeit zu erreichen und das dies den Nachteil einer etwas komplexeren Programmierung klar aufwiegt.