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.

Generating Compliant Motion of Objects with an Articulated Hand

The flexibility of the robot is the key to its success as a viable aid to production. Flexibility of a robot can be explained in two directions. The first is to increase the physical generality of the robot such that it can be easily reconfigured to handle a wide variety of tasks. The second direction is to increase the ability of the robot to interact with its environment such that tasks can still be successfully completed in the presence of uncertainties. The use of articulated hands are capable of adapting to a wide variety of grasp shapes, hence reducing the need for special tooling. The availability of low mass, high bandwidth points close to the manipulated object also offers significant improvements I the control of fine motions. This thesis provides a framework for using articulated hands to perform local manipulation of objects. N particular, it addresses the issues in effecting compliant motions of objects in Cartesian space. The Stanford/JPL hand is used as an example to illustrate a number of concepts. The examples provide a unified methodology for controlling articulated hands grasping with point contacts. We also present a high-level hand programming system based on the methodologies developed in this thesis. Compliant motion of grasped objects and dexterous manipulations can be easily described in the LISP-based hand programming language.

Pi: A Parallel Architecture Interface for Multi-Model Execution

This thesis defines Pi, a parallel architecture interface that separates model and machine issues, allowing them to be addressed independently. This provides greater flexibility for both the model and machine builder. Pi addresses a set of common parallel model requirements including low latency communication, fast task switching, low cost synchronization, efficient storage management, the ability to exploit locality, and efficient support for sequential code. Since Pi provides generic parallel operations, it can efficiently support many parallel programming models including hybrids of existing models. Pi also forms a basis of comparison for architectural components.

Parallel Methods for Synthesizing Whole-Hand Grasps from Generalized Prototypes

This report addresses the problem of acquiring objects using articulated robotic hands. Standard grasps are used to make the problem tractable, and a technique is developed for generalizing these standard grasps to increase their flexibility to variations in the problem geometry. A generalized grasp description is applied to a new problem situation using a parallel search through hand configuration space, and the result of this operation is a global overview of the space of good solutions. The techniques presented in this report have been implemented, and the results are verified using the Salisbury three-finger robotic hand.

Design and Control of an Anthropomorphic Robotic Finger with Multi-point Tactile Sensation

The goal of this research is to develop the prototype of a tactile sensing platform for anthropomorphic manipulation research. We investigate this problem through the fabrication and simple control of a planar 2-DOF robotic finger inspired by anatomic consistency, self-containment, and adaptability. The robot is equipped with a tactile sensor array based on optical transducer technology whereby localized changes in light intensity within an illuminated foam substrate correspond to the distribution and magnitude of forces applied to the sensor surface plane. The integration of tactile perception is a key component in realizing robotic systems which organically interact with the world. Such natural behavior is characterized by compliant performance that can initiate internal, and respond to external, force application in a dynamic environment. However, most of the current manipulators that support some form of haptic feedback either solely derive proprioceptive sensation or only limit tactile sensors to the mechanical fingertips. These constraints are due to the technological challenges involved in high resolution, multi-point tactile perception. In this work, however, we take the opposite approach, emphasizing the role of full-finger tactile feedback in the refinement of manual capabilities. To this end, we propose and implement a control framework for sensorimotor coordination analogous to infant-level grasping and fixturing reflexes. This thesis details the mechanisms used to achieve these sensory, actuation, and control objectives, along with the design philosophies and biological influences behind them. The results of behavioral experiments with a simple tactilely-modulated control scheme are also described. The hope is to integrate the modular finger into an %engineered analog of the human hand with a complete haptic system.

Virtual Model Control of a Biped Walking Robot

The transformation from high level task specification to low level motion control is a fundamental issue in sensorimotor control in animals and robots. This thesis develops a control scheme called virtual model control which addresses this issue. Virtual model control is a motion control language which uses simulations of imagined mechanical components to create forces, which are applied through joint torques, thereby creating the illusion that the components are connected to the robot. Due to the intuitive nature of this technique, designing a virtual model controller requires the same skills as designing the mechanism itself. A high level control system can be cascaded with the low level virtual model controller to modulate the parameters of the virtual mechanisms. Discrete commands from the high level controller would then result in fluid motion. An extension of Gardner's Partitioned Actuator Set Control method is developed. This method allows for the specification of constraints on the generalized forces which each serial path of a parallel mechanism can apply. Virtual model control has been applied to a bipedal walking robot. A simple algorithm utilizing a simple set of virtual components has successfully compelled the robot to walk eight consecutive steps.

Observations on Cortical Mechanisms for Object Recognition andsLearning

This paper sketches a hypothetical cortical architecture for visual 3D object recognition based on a recent computational model. The view-centered scheme relies on modules for learning from examples, such as Hyperbf-like networks. Such models capture a class of explanations we call Memory-Based Models (MBM) that contains sparse population coding, memory-based recognition, and codebooks of prototypes. Unlike the sigmoidal units of some artificial neural networks, the units of MBMs are consistent with the description of cortical neurons. We describe how an example of MBM may be realized in terms of cortical circuitry and biophysical mechanisms, consistent with psychophysical and physiological data.

Role of Low-level Mechanisms in Brightness Perception

Brightness judgments are a key part of the primate brain's visual analysis of the environment. There is general consensus that the perceived brightness of an image region is based not only on its actual luminance, but also on the photometric structure of its neighborhood. However, it is unclear precisely how a region's context influences its perceived brightness. Recent research has suggested that brightness estimation may be based on a sophisticated analysis of scene layout in terms of transparency, illumination and shadows. This work has called into question the role of low-level mechanisms, such as lateral inhibition, as explanations for brightness phenomena. Here we describe experiments with displays for which low-level and high-level analyses make qualitatively different predictions, and with which we can quantitatively assess the trade-offs between low-level and high-level factors. We find that brightness percepts in these displays are governed by low-level stimulus properties, even when these percepts are inconsistent with higher-level interpretations of scene layout. These results point to the important role of low-level mechanisms in determining brightness percepts.