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.

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.

Agricultural practices and horizontal nutrient balances in urban gardens and the alternative use of urban agricultural land in Khartoum, Sudan

The surge in the urban population evident in most developing countries is a worldwide phenomenon, and often the result of drought, conflicts, poverty and the lack of education opportunities. In parallel with the growth of the cities is the growing need for food which leads to the burgeoning expansion of urban and peri-urban agriculture (UPA). In this context, urban agriculture (UA) contributes significantly to supplying local markets with both vegetable and animal produce. As an income generating activity, UA also contributes to the livelihoods of poor urban dwellers. In order to evaluate the nutrient status of urban soils in relation to garden management, this study assessed nutrient fluxes (inputs and outputs) in gardens on urban Gerif soils on the banks of the River Nile in Khartoum, the capital city of Sudan. To achieve this objective, a preliminary baseline survey was carried out to describe the structure of the existing garden systems. In cooperation with the author of another PhD thesis (Ms. Ishtiag Abdalla), alternative uses of cow dung in brick making kilns in urban Khartoum were assessed; and the socio-economic criteria of the brick kiln owners or agents, economical and plant nutritional value of animal dung and the gaseous emission related to brick making activities were assessed. A total of 40 household heads were interviewed using a semi-structured questionnaire to collect information on demographic, socio-economic and migratory characteristics of the household members, the gardening systems used and the problems encountered in urban gardening. Based on the results of this survey, gardens were divided into three groups: mixed vegetable-fodder gardens, mixed vegetable-subsistence livestock gardens and pure vegetable gardens. The results revealed that UA is the exclusive domain of men, 80% of them non-native to Khartoum. The harvested produce in all gardens was market oriented and represented the main source of income for 83% of the gardeners. Fast growing leafy vegetables such as Jew’s mallow (Corchorous olitorius L.), purslane (Portulaca oleracea L.) and rocket (Eruca sativa Mill.) were the dominant cultivated species. Most of the gardens (95%) were continuously cultivated throughout the year without any fallow period, unless they were flooded. Gardeners were not generally aware of the importance of crop diversity, which may help them overcome the strongly fluctuating market prices for their produce and thereby strengthen the contributions of UA to the overall productivity of the city. To measure nutrient fluxes, four gardens were selected and their nutrients inputs and outputs flows were monitored. In each garden, all plots were monitored for quantification of nutrient inputs and outputs. To determine soil chemical fertility parameters in each of the studied gardens, soil samples were taken from three selected plots at the beginning of the study in October 2007 (gardens L1, L2 and H1) and in April 2008 (garden H2) and at the end of the study period in March 2010. Additional soil sampling occurred in May 2009 to assess changes in the soil nutrient status after the River Nile flood of 2008 had receded. Samples of rain and irrigation water (river and well-water) were analyzed for nitrogen (N), phosphorus (P), potassium (K) and carbon (C) content to determine their nutrient inputs. Catchment traps were installed to quantify the sediment yield from the River Nile flood. To quantify the nutrient inputs of sediments, samples were analyzed for N, P, K and organic carbon (Corg) content, cation exchange capacity (CEC) and the particle size distribution. The total nutrient inputs were calculated by multiplying the sediment nutrient content by total sediment deposits on individual gardens. Nutrient output in the form of harvested yield was quantified at harvest of each crop. Plant samples from each field were dried, and analyzed for their N, P, K and Corg content. Cumulative leaching losses of mineral N and P were estimated in a single plot in garden L1 from December 1st 2008 to July 1st 2009 using 12 ion exchange resins cartridges. Nutrients were extracted and analyzed for nitrate (NO3--N), ammonium (NH4+-N) and phosphate PO4-3-P. Changes in soil nutrient balance were assessed as inputs minus outputs. The results showed that across gardens, soil N and P concentrations increased from 2007 to 2009, while particle size distribution remained unchanged. Sediment loads and their respective contents of N, P and Corg decreased significantly (P < 0.05) from the gardens of the downstream lowlands (L1 and L2) to the gardens of the upstream highlands (H1 and H2). No significant difference was found in K deposits. None of the gardens received organic fertilizers and the only mineral fertilizer applied was urea (46-0-0). This equaled 29, 30, 54, and 67% of total N inputs to gardens L1, L2, H1, and H2, respectively. Sediment deposits of the River Nile floods contributed on average 67, 94, 6 and 42% to the total N, P, K and C inputs in lowland gardens and 33, 86, 4 and 37% of total N, P, K and C inputs in highland gardens. Irrigation water and rainfall contributed substantially to K inputs representing 96, 92, 94 and 96% of total K influxes in garden L1, L2, H1 and H2, respectively. Following the same order, total annual DM yields in the gardens were 26, 18, 16 and 1.8 t ha-1. Annual leaching losses were estimated to be 0.02 kg NH4+-N ha-1 (SE = 0.004), 0.03 kg NO3--N ha-1 (SE = 0.002) and 0.005 kg PO4-3-P ha-1 (SE = 0.0007). Differences between nutrient inputs and outputs indicated negative nutrient balances for P and K and positive balances of N and C for all gardens. The negative balances in P and K call for adoptions of new agricultural techniques such as regular manure additions or mulching which may enhance the soil organic matter status. A quantification of fluxes not measured in our study such as N2-fixation, dry deposition and gaseous emissions of C and N would be necessary to comprehensively assess the sustainability of these intensive gardening systems. The second part of the survey dealt with the brick making kilns. A total of 50 brick kiln owners/or agents were interviewed from July to August 2009, using a semi-structured questionnaire. The data collected included general information such as age, family size, education, land ownership, number of kilns managed and/or owned, number of months that kilns were in operation, quantity of inputs (cow dung and fuel wood) used, prices of inputs and products across the production season. Information related to the share value of the land on which the kilns were built and annual income for urban farmers and annual returns from dung for the animal raisers was also collected. Using descriptive statistics, budget calculation and Gini coefficient, the results indicated that renting the land to brick making kilns yields a 5-fold higher return than the rent for agriculture. Gini coefficient showed that the kiln owners had a more equal income distribution compared to farmers. To estimate emission of greenhouse gases (GHGs) and losses of N, P, K, Corg and DM from cow dung when used in brick making, samples of cow dung (loose and compacted) were collected from different kilns and analyzed for their N, P, K and Corg content. The procedure modified by the Intergovernmental Panel on Climate Change (IPCC, 1994) was used to estimate the gaseous emissions of cow dung and fuel wood. The amount of deforested wood was estimated according to the default values for wood density given by Dixon et al. (1991) and the expansion ratio for branches and small trees given by Brown et al. (1989). The data showed the monetary value of added N and P from cow dung was lower than for mineral fertilizers. Annual consumption of compacted dung (381 t DM) as biomass fuel by far exceeded the consumption of fuel wood (36 t DM). Gaseous emissions from cow dung and fuel wood were dominated by CO2, CO and CH4. Considering that Gerif land in urban Khartoum supports a multifunctional land use system, efficient use of natural resources (forest, dung, land and water) will enhance the sustainability of the UA and brick making activities. Adoption of new kilns with higher energy efficiency will reduce the amount of biomass fuels (cow dung and wood) used the amount of GHGs emitted and the threat to the few remaining forests.

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.

Optimal control theory for a unitary operation under dissipative evolution

We show that optimizing a quantum gate for an open quantum system requires the time evolution of only three states irrespective of the dimension of Hilbert space. This represents a significant reduction in computational resources compared to the complete basis of Liouville space that is commonly believed necessary for this task. The reduction is based on two observations: the target is not a general dynamical map but a unitary operation; and the time evolution of two properly chosen states is sufficient to distinguish any two unitaries. We illustrate gate optimization employing a reduced set of states for a controlled phasegate with trapped atoms as qubit carriers and a iSWAP gate with superconducting qubits.

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 Coupled Micro-Macro Actuators

This thesis presents a new actuator system consisting of a micro-actuator and a macro-actuator coupled in parallel via a compliant transmission. The system is called the Parallel Coupled Micro-Macro Actuator, or PaCMMA. In this system, the micro-actuator is capable of high bandwidth force control due to its low mass and direct-drive connection to the output shaft. The compliant transmission of the macro-actuator reduces the impedance (stiffness) at the output shaft and increases the dynamic range of force. Performance improvement over single actuator systems was expected in force control, impedance control, force distortion and reduction of transient impact forces. A set of quantitative measures is proposed and the actuator system is evaluated against them: Force Control Bandwidth, Position Bandwidth, Dynamic Range, Impact Force, Impedance ("Backdriveability'"), Force Distortion and Force Performance Space. Several theoretical performance limits are derived from the saturation limits of the system. A control law is proposed and control system performance is compared to the theoretical limits. A prototype testbed was built using permanenent magnet motors and an experimental comparison was performed between this actuator concept and two single actuator systems. The following performance was observed: Force bandwidth of 56Hz, Torque Dynamic Range of 800:1, Peak Torque of 1040mNm, Minimum Torque of 1.3mNm. Peak Impact Force was reduced by an order of magnitude. Distortion at small amplitudes was reduced substantially. Backdriven impedance was reduced by 2-3 orders of magnitude. This actuator system shows promise for manipulator design as well as psychophysical tests of human performance.

ADAM: A Decentralized Parallel Computer Architecture Featuring Fast Thread and Data Migration and a Uniform Hardware Abstraction

The furious pace of Moore's Law is driving computer architecture into a realm where the the speed of light is the dominant factor in system latencies. The number of clock cycles to span a chip are increasing, while the number of bits that can be accessed within a clock cycle is decreasing. Hence, it is becoming more difficult to hide latency. One alternative solution is to reduce latency by migrating threads and data, but the overhead of existing implementations has previously made migration an unserviceable solution so far. I present an architecture, implementation, and mechanisms that reduces the overhead of migration to the point where migration is a viable supplement to other latency hiding mechanisms, such as multithreading. The architecture is abstract, and presents programmers with a simple, uniform fine-grained multithreaded parallel programming model with implicit memory management. In other words, the spatial nature and implementation details (such as the number of processors) of a parallel machine are entirely hidden from the programmer. Compiler writers are encouraged to devise programming languages for the machine that guide a programmer to express their ideas in terms of objects, since objects exhibit an inherent physical locality of data and code. The machine implementation can then leverage this locality to automatically distribute data and threads across the physical machine by using a set of high performance migration mechanisms. An implementation of this architecture could migrate a null thread in 66 cycles -- over a factor of 1000 improvement over previous work. Performance also scales well; the time required to move a typical thread is only 4 to 5 times that of a null thread. Data migration performance is similar, and scales linearly with data block size. Since the performance of the migration mechanism is on par with that of an L2 cache, the implementation simulated in my work has no data caches and relies instead on multithreading and the migration mechanism to hide and reduce access latencies.

Optimal Methodology for Synchronized Scheduling of Parallel Station Assembly with Air Transportation

We present an optimal methodology for synchronized scheduling of production assembly with air transportation to achieve accurate delivery with minimized cost in consumer electronics supply chain (CESC). This problem was motivated by a major PC manufacturer in consumer electronics industry, where it is required to schedule the delivery requirements to meet the customer needs in different parts of South East Asia. The overall problem is decomposed into two sub-problems which consist of an air transportation allocation problem and an assembly scheduling problem. The air transportation allocation problem is formulated as a Linear Programming Problem with earliness tardiness penalties for job orders. For the assembly scheduling problem, it is basically required to sequence the job orders on the assembly stations to minimize their waiting times before they are shipped by flights to their destinations. Hence the second sub-problem is modelled as a scheduling problem with earliness penalties. The earliness penalties are assumed to be independent of the job orders.

Room-temperature continuous-wave operation of GaInNAs/GaAs quantum dot laser with GaAsN barrier grown by solid source molecular beam epitaxy

We present the results of GaInNAs/GaAs quantum dot structures with GaAsN barrier layers grown by solid source molecular beam epitaxy. Extension of the emission wavelength of GaInNAs quantum dots by ~170nm was observed in samples with GaAsN barriers in place of GaAs. However, optimization of the GaAsN barrier layer thickness is necessary to avoid degradation in luminescence intensity and structural property of the GaInNAs dots. Lasers with GaInNAs quantum dots as active layer were fabricated and room-temperature continuous-wave lasing was observed for the first time. Lasing occurs via the ground state at ~1.2μm, with threshold current density of 2.1kA/cm[superscript 2] and maximum output power of 16mW. These results are significantly better than previously reported values for this quantum-dot system.

Proposal of a parallel architecture for a motion detection algorithm

This paper proposes a parallel architecture for estimation of the motion of an underwater robot. It is well known that image processing requires a huge amount of computation, mainly at low-level processing where the algorithms are dealing with a great number of data. In a motion estimation algorithm, correspondences between two images have to be solved at the low level. In the underwater imaging, normalised correlation can be a solution in the presence of non-uniform illumination. Due to its regular processing scheme, parallel implementation of the correspondence problem can be an adequate approach to reduce the computation time. Taking into consideration the complexity of the normalised correlation criteria, a new approach using parallel organisation of every processor from the architecture is proposed

Internacionalización de las empresas colombianas caso: Automundial S.A

Se realiza este trabajo por medio del análisis estructural, interno y competitivo de la empresa Automundial S.A. para conocer su estado actual frente a sus propias actividades y funciones para de esta forma, poder dictaminar una serie de propuestas que contribuyan al mejoramiento de la empresa y conlleven a que el direccionamiento de las estrategias empresariales se enfoquen a un proceso de internacionalización. Con la necesidad de utilizar intermediarios que los introduzcan en las economías de los países extranjeros y obtener todo el conocimiento del mercado para reducir los riesgos de perdidas, al momento de instaurar una planta de producción en ese país. Para lograr tal fin se plantea la comparación de dos empresas participantes en el sector del reencauche de llantas en Colombia, como las multinacionales Michelín y Goodyear, quienes son los competidores directos de Automundial S.A. Dicho análisis funciona como paralelo para relacionar las actividades y los procesos de dichas empresas respecto al comportamiento y trayectoria que lleva Automundial S.A. en sus 100 años de funcionamiento, siendo la empresa pionera en la producción del reencauche de llantas en Colombia. De esta forma, se logra plantear un modelo de internacionalización a través de diversas teorías de la internacionalización expuestas en este trabajo, de las cuales se apoya y da sustento académico a la ruta de exportación que debe seguir la empresa Automundial S.A. Al final de este proceso efectuado por la misma, se podrá tomar este modelo de internacionalización como un patrón de exportación conformado por etapas y pasos a ejecutar, teniendo en cuenta el crecimiento y la madurez de la empresa perteneciente al sector frente al mercado local. Dicha empresa interesada en internacionalizarse, deberá contar con un direccionamiento a querer lograr un proceso de exportación de productos o servicios a mercados extranjeros hasta la etapa de llegar a producir localmente en dicho país objetivo.