Evaluating the state of the art of parallel programming systems

This paper describes our plans to evaluate the present state of affairs concerning parallel programming and its systems. Three subprojects are proposed: a survey among programmers and scientists, a comparison of parallel programming systems using a standard set of test programs, and a wiki resource for the parallel programming community - the Parawiki. We would like to invite you to participate and turn these subprojects into true community efforts.

Mechanisms of residue mulch-induced cereal growth increases in West Africa

The use of crop residues (CR) has been widely reported as a means of increasing crop yields across West Africa. However, little has been done to compare the magnitude and mechanisms of CR effects systematically in the different agro-ecological zones of the region. To this end, a series of field trials with millet (Pennisetum glaucum L.), sorghum [Sorghum bicolor (L.) Moench], and maize (Zea mays L.) was conducted over a 4-yr period in the Sahelian, Sudanian, and Guinean zones of West Africa. Soils ranged in pH from 4.1 to 5.4 along a rainfall gradient from 510 to 1300 mm. Treatments in the factorial experiments were three CR rates (0,500, and 2000 kg ha^-1)and several levels of phosphorus and nitrogen. The results showed CR-induced total dry matter (TDM) increases in cereals up to 73% for the Sahel compared with a maximum of 16% in the wetter Sudanian and Guinean zones. Residue effects on weakly buffered Sahelian soils were due to improved P availability and to a protection of seedlings against wind erosion. Additional effects of CR mulching on topsoil properties in the Sahel were a decrease in peak temperatures by 4°C and increased water availability. These mulch effects on soil chemical and physical properties strongly decreased from North to South. Likely explanations for this decrease are the decline of dust deposition and wind erosion hazards, the higher soil clay content, lower air temperature, and a faster decomposition rate of mulch material with increasing rainfall from the Sahel to the Sudanian and Guinean zones.

Observations on the Publicity and Usage of Parallel Programming Systems and Languages: A Survey Approach

In this publication, we report on an online survey that was carried out among parallel programmers. More than 250 people worldwide have submitted answers to our questions, and their responses are analyzed here. Although not statistically sound, the data we provide give useful insights about which parallel programming systems and languages are known and in actual use. For instance, the collected data indicate that for our survey group MPI and (to a lesser extent) C are the most widely used parallel programming system and language, respectively.

Molecular mechanisms controlling the precision of chemokine guided cell migration

By the end of the first day of embryonic development, zebrafish primordial germ cells (PGCs) arrive at the site where the gonad develops. In our study we investigated the mechanisms controlling the precision of primordial germ cell arrival at their target. We found that in contrast with our expectations which were based on findings in Drosophila and mouse, the endoderm does not constitute a preferred migration substrate for the PGCs. Rather, endoderm derivatives are important for later stages of organogenesis keeping the PGC clusters separated. It would be interesting to investigate the precise mechanism by which endoderm controls germ cell position in the gonad. In their migration towards the gonad, zebrafish germ cells follow the gradient of chemokine SDF-1a, which they detect using the receptor CXCR4b that is expressed on their membrane. Here we show that the C-terminal region of CXCR4b is responsible for down-regulation of receptor activity as well as for receptor internalization. We demonstrate that receptor molecules unable to internalize are less potent in guiding germ cells to the site where the gonad develops, thereby implicating chemokine receptor internalization in facilitating precision of migration during chemotaxis in vivo. We demonstrate that while CXCR4b activity positively regulates the duration of the active migration phases, the down-regulation of CXCR4b signalling by internalization limits the duration of this phase. This way, receptor signalling contributes to the persistence of germ cell migration, whereas receptor down-regulation enables the cells to stop and correct their migration path close to the target where germ cells encounter the highest chemokine signal. Chemokine receptors are involved in directing cell migration in different processes such as lymphocyte trafficking, cancer and in the development of the vascular system. The C-terminal domain of many chemokine receptors was shown to be essential for controlling receptor signalling and internalization. It would therefore be important to determine whether the role for receptor internalization in vivo as described here (allowing periodical corrections to the migration route) and the mechanisms involved (reducing the level of signalling) apply for those other events, too.

A User-Centric Perspective on Parallel Programming with Focus on OpenMP

The process of developing software that takes advantage of multiple processors is commonly referred to as parallel programming. For various reasons, this process is much harder than the sequential case. For decades, parallel programming has been a problem for a small niche only: engineers working on parallelizing mostly numerical applications in High Performance Computing. This has changed with the advent of multi-core processors in mainstream computer architectures. Parallel programming in our days becomes a problem for a much larger group of developers. The main objective of this thesis was to find ways to make parallel programming easier for them. Different aims were identified in order to reach the objective: research the state of the art of parallel programming today, improve the education of software developers about the topic, and provide programmers with powerful abstractions to make their work easier. To reach these aims, several key steps were taken. To start with, a survey was conducted among parallel programmers to find out about the state of the art. More than 250 people participated, yielding results about the parallel programming systems and languages in use, as well as about common problems with these systems. Furthermore, a study was conducted in university classes on parallel programming. It resulted in a list of frequently made mistakes that were analyzed and used to create a programmers' checklist to avoid them in the future. For programmers' education, an online resource was setup to collect experiences and knowledge in the field of parallel programming - called the Parawiki. Another key step in this direction was the creation of the Thinking Parallel weblog, where more than 50.000 readers to date have read essays on the topic. For the third aim (powerful abstractions), it was decided to concentrate on one parallel programming system: OpenMP. Its ease of use and high level of abstraction were the most important reasons for this decision. Two different research directions were pursued. The first one resulted in a parallel library called AthenaMP. It contains so-called generic components, derived from design patterns for parallel programming. These include functionality to enhance the locks provided by OpenMP, to perform operations on large amounts of data (data-parallel programming), and to enable the implementation of irregular algorithms using task pools. AthenaMP itself serves a triple role: the components are well-documented and can be used directly in programs, it enables developers to study the source code and learn from it, and it is possible for compiler writers to use it as a testing ground for their OpenMP compilers. The second research direction was targeted at changing the OpenMP specification to make the system more powerful. The main contributions here were a proposal to enable thread-cancellation and a proposal to avoid busy waiting. Both were implemented in a research compiler, shown to be useful in example applications, and proposed to the OpenMP Language Committee.

On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata

This paper contributes to the study of Freely Rewriting Restarting Automata (FRR-automata) and Parallel Communicating Grammar Systems (PCGS), which both are useful models in computational linguistics. For PCGSs we study two complexity measures called 'generation complexity' and 'distribution complexity', and we prove that a PCGS Pi, for which the generation complexity and the distribution complexity are both bounded by constants, can be transformed into a freely rewriting restarting automaton of a very restricted form. From this characterization it follows that the language L(Pi) generated by Pi is semi-linear, that its characteristic analysis is of polynomial size, and that this analysis can be computed in polynomial time.

Segregation unter Stagnationsbedingungen

Anlass der Untersuchung sind Verstärkungen von strukturwandel- und globalisierungsbedingten Wandlungen unter Schrumpfungs- und Stagnationsbedingungen. Denn Stagnations- und Schrumpfungstendenzen in einer Region sind selektiv, sie begünstigen über verschiedene Mechanismen Polarisierungen und Marginalisierungen: Die allgemeine Entspannung am Wohnungsmarkt hat erhöhte Mobilität und damit sozialräumliche Segregierungen und Polarisierungen der Wohnungsversorgung zur Folge. Leerstände und ausbleibende Investitionen begünstigen Polarisierungen von baulich-räumlichen Qualitäten. Diese beiden Entwicklungen überlagern sich im Stadtraum und verstärken sich gegenseitig. Dabei verbessert sich die Wohnungsversorgung in den benachteiligten Quartieren kaum, so die Ausgangshypothesen. Die Untersuchung fragt nach den Wirkungen des Nebeneinanders von Wachstums-, Stagnations- und Schrumpfungserscheinungen auf unterschiedlichen Maßstabsebenen, dem Zusammenspiel von sozialstrukturellen und qualitativen Veränderungen der baulich-räumlichen Gegebenheiten in den Quartieren sowie in innerstädtischer Differenzierung. Dabei interessieren besonders die Einflüsse eines regional entspannten Wohnungsmarktes und dessen Folgen für die Verwertungsstrategien im Wohnungsbestand auf Segregationsprozesse und die Wohnungsversorgung. Als Fallbeispiel der Untersuchung dient die Stadt Kassel. Der sozialräumliche Fokus liegt auf drei Typen benachteiligter Quartiere: Neben den in der aktuellen Diskussion zumeist betrachteten gründerzeitlichen Arbeiterquartieren und den Großsiedlungen der 1960/70er Jahre wurden auch die peripheren Geschosswohnungsbausiedlungen der 1950er/60er Jahre in die Untersuchung einbezogen, um den unterschiedlichen Rahmenbedingungen und Wirkungen in den Quartierstypen auf die Spur zu kommen und damit letztlich Grundlagen für stadtentwicklungspolitische Strategien zu erarbeiten. Die kleinräumigen Analysen von sozialräumlicher und baulich-räumlicher Struktur sowie zur Wohnungsversorgung deckten Parallelen und gegenläufige Entwicklungen zwischen den unterschiedlichen Quartierstypen auf; es ergaben sich verschiedene Anhaltspunkte zur Erhärtung der Ausgangsthesen. So wurde z.B. deutlich, dass sich unter den Marktbedingungen stagnierender Städte die Wohnflächenversorgung in den benachteiligten Quartieren kaum verbessert. Hierin zeigt sich ein entscheidender Unterschied zu stark schrumpfenden Städten, in denen sich die Versorgungslage (fast) durchgängig verbessert. Wohnungsmarktbarrieren wirken offensichtlich unter Stagnationsbedingungen für bestimmte Bevölkerungsgruppen weiter. Da sich ihre Wirkung aber für weitere Kreise der Bevölkerung abschwächt, verschärfen sich sozialräumliche Konzentrationen. Vor allem aber wurden Überlagerung und gegenseitige Verstärkung dieser sozialräumlichen mit baulich-räumlichen Polarisierungen deutlich, die vor allem aus stadträumlich konzentrierten Investitionen in den Gebäude- und Wohnungsbestand resultieren. Letztlich zeigt sich damit, dass regulierende Eingriffe nicht nur im Rahmen des Umbaus und der Erneuerung der Quartiere erforderlich sind, sondern insbesondere auch in den Wohnungsmarkt und dies auch bei entspannter regionaler Marktlage. Andernfalls ist weder eine angemessene Wohnungsversorgung aller Bevölkerungsgruppen noch der Zusammenhalt der Stadt(Gesellschaft) zu gewährleisten. Dabei ist die Stadtpolitik permanent mit der Gleichzeitigkeit von (wirtschaftlicher) Standortpolitik und sozialer Stadtentwicklung konfrontiert, die sie im Sinne einer nachhaltigen Entwicklung gegeneinander und miteinander abwägen muss.

Systems of Parallel Communicating Restarting Automata

In der vorliegenden Dissertation werden Systeme von parallel arbeitenden und miteinander kommunizierenden Restart-Automaten (engl.: systems of parallel communicating restarting automata; abgekürzt PCRA-Systeme) vorgestellt und untersucht. Dabei werden zwei bekannte Konzepte aus den Bereichen Formale Sprachen und Automatentheorie miteinander vescrknüpft: das Modell der Restart-Automaten und die sogenannten PC-Systeme (systems of parallel communicating components). Ein PCRA-System besteht aus endlich vielen Restart-Automaten, welche einerseits parallel und unabhängig voneinander lokale Berechnungen durchführen und andererseits miteinander kommunizieren dürfen. Die Kommunikation erfolgt dabei durch ein festgelegtes Kommunikationsprotokoll, das mithilfe von speziellen Kommunikationszuständen realisiert wird. Ein wesentliches Merkmal hinsichtlich der Kommunikationsstruktur in Systemen von miteinander kooperierenden Komponenten ist, ob die Kommunikation zentralisiert oder nichtzentralisiert erfolgt. Während in einer nichtzentralisierten Kommunikationsstruktur jede Komponente mit jeder anderen Komponente kommunizieren darf, findet jegliche Kommunikation innerhalb einer zentralisierten Kommunikationsstruktur ausschließlich mit einer ausgewählten Master-Komponente statt. Eines der wichtigsten Resultate dieser Arbeit zeigt, dass zentralisierte Systeme und nichtzentralisierte Systeme die gleiche Berechnungsstärke besitzen (das ist im Allgemeinen bei PC-Systemen nicht so). Darüber hinaus bewirkt auch die Verwendung von Multicast- oder Broadcast-Kommunikationsansätzen neben Punkt-zu-Punkt-Kommunikationen keine Erhöhung der Berechnungsstärke. Desweiteren wird die Ausdrucksstärke von PCRA-Systemen untersucht und mit der von PC-Systemen von endlichen Automaten und mit der von Mehrkopfautomaten verglichen. PC-Systeme von endlichen Automaten besitzen bekanntermaßen die gleiche Ausdrucksstärke wie Einwegmehrkopfautomaten und bilden eine untere Schranke für die Ausdrucksstärke von PCRA-Systemen mit Einwegkomponenten. Tatsächlich sind PCRA-Systeme auch dann stärker als PC-Systeme von endlichen Automaten, wenn die Komponenten für sich genommen die gleiche Ausdrucksstärke besitzen, also die regulären Sprachen charakterisieren. Für PCRA-Systeme mit Zweiwegekomponenten werden als untere Schranke die Sprachklassen der Zweiwegemehrkopfautomaten im deterministischen und im nichtdeterministischen Fall gezeigt, welche wiederum den bekannten Komplexitätsklassen L (deterministisch logarithmischer Platz) und NL (nichtdeterministisch logarithmischer Platz) entsprechen. Als obere Schranke wird die Klasse der kontextsensitiven Sprachen gezeigt. Außerdem werden Erweiterungen von Restart-Automaten betrachtet (nonforgetting-Eigenschaft, shrinking-Eigenschaft), welche bei einzelnen Komponenten eine Erhöhung der Berechnungsstärke bewirken, in Systemen jedoch deren Stärke nicht erhöhen. Die von PCRA-Systemen charakterisierten Sprachklassen sind unter diversen Sprachoperationen abgeschlossen und einige Sprachklassen sind sogar abstrakte Sprachfamilien (sogenannte AFL's). Abschließend werden für PCRA-Systeme spezifische Probleme auf ihre Entscheidbarkeit hin untersucht. Es wird gezeigt, dass Leerheit, Universalität, Inklusion, Gleichheit und Endlichkeit bereits für Systeme mit zwei Restart-Automaten des schwächsten Typs nicht semientscheidbar sind. Für das Wortproblem wird gezeigt, dass es im deterministischen Fall in quadratischer Zeit und im nichtdeterministischen Fall in exponentieller Zeit entscheidbar ist.