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.

Evolving Distributed Algorithms with Genetic Programming

Distributed systems are one of the most vital components of the economy. The most prominent example is probably the internet, a constituent element of our knowledge society. During the recent years, the number of novel network types has steadily increased. Amongst others, sensor networks, distributed systems composed of tiny computational devices with scarce resources, have emerged. The further development and heterogeneous connection of such systems imposes new requirements on the software development process. Mobile and wireless networks, for instance, have to organize themselves autonomously and must be able to react to changes in the environment and to failing nodes alike. Researching new approaches for the design of distributed algorithms may lead to methods with which these requirements can be met efficiently. In this thesis, one such method is developed, tested, and discussed in respect of its practical utility. Our new design approach for distributed algorithms is based on Genetic Programming, a member of the family of evolutionary algorithms. Evolutionary algorithms are metaheuristic optimization methods which copy principles from natural evolution. They use a population of solution candidates which they try to refine step by step in order to attain optimal values for predefined objective functions. The synthesis of an algorithm with our approach starts with an analysis step in which the wanted global behavior of the distributed system is specified. From this specification, objective functions are derived which steer a Genetic Programming process where the solution candidates are distributed programs. The objective functions rate how close these programs approximate the goal behavior in multiple randomized network simulations. The evolutionary process step by step selects the most promising solution candidates and modifies and combines them with mutation and crossover operators. This way, a description of the global behavior of a distributed system is translated automatically to programs which, if executed locally on the nodes of the system, exhibit this behavior. In our work, we test six different ways for representing distributed programs, comprising adaptations and extensions of well-known Genetic Programming methods (SGP, eSGP, and LGP), one bio-inspired approach (Fraglets), and two new program representations called Rule-based Genetic Programming (RBGP, eRBGP) designed by us. We breed programs in these representations for three well-known example problems in distributed systems: election algorithms, the distributed mutual exclusion at a critical section, and the distributed computation of the greatest common divisor of a set of numbers. Synthesizing distributed programs the evolutionary way does not necessarily lead to the envisaged results. In a detailed analysis, we discuss the problematic features which make this form of Genetic Programming particularly hard. The two Rule-based Genetic Programming approaches have been developed especially in order to mitigate these difficulties. In our experiments, at least one of them (eRBGP) turned out to be a very efficient approach and in most cases, was superior to the other representations.

Contact Sensing: A Sequential Decision Approach to Sensing Manipulation Contact

This paper describes a new statistical, model-based approach to building a contact state observer. The observer uses measurements of the contact force and position, and prior information about the task encoded in a graph, to determine the current location of the robot in the task configuration space. Each node represents what the measurements will look like in a small region of configuration space by storing a predictive, statistical, measurement model. This approach assumes that the measurements are statistically block independent conditioned on knowledge of the model, which is a fairly good model of the actual process. Arcs in the graph represent possible transitions between models. Beam Viterbi search is used to match measurement history against possible paths through the model graph in order to estimate the most likely path for the robot. The resulting approach provides a new decision process that can be use as an observer for event driven manipulation programming. The decision procedure is significantly more robust than simple threshold decisions because the measurement history is used to make decisions. The approach can be used to enhance the capabilities of autonomous assembly machines and in quality control applications.

A sequential two meal challenge reveals abnormalities in postprandial TAG but not glucose in men with increasing numbers of metabolic syndrome components

Objective To examine the impact of increasing numbers of metabolic syndrome (MetS) components on postprandial lipaemia. Methods Healthy men (n = 112) underwent a sequential meal postprandial investigation, in which blood samples were taken at regular intervals after a test breakfast (0 min) and lunch (330 min). Lipids and glucose were measured in the fasting sample, with triacylglycerol (TAG), non-esterified fatty acids and glucose analysed in the postprandial samples. Results Subjects were grouped according to the number of MetS components regardless of the combinations of components (0/1, 2, 3 and 4/5). As expected, there was a trend for an increase in body mass index, blood pressure, fasting TAG, glucose and insulin, and a decrease in fasting high-density lipoprotein cholesterol with increasing numbers of MetS components (P≤0.0004). A similar trend was observed for the summary measures of the postprandial TAG and glucose responses. For TAG, the area under the curve (AUC) and maximum concentration (maxC) were significantly greater in men with ≥ 3 than < 3 components (P < 0.001), whereas incremental AUC was greater in those with 3 than 0/1 and 2, and 4/5 compared with 2 components (P < 0.04). For glucose, maxC after the test breakfast (0-330 min) and total AUC (0-480 min) were higher in men with ≥ 3 than < 3 components (P≤0.001). Conclusions Our data analysis has revealed a linear trend between increasing numbers of MetS components and magnitude (AUC) of the postprandial TAG and glucose responses. Furthermore, the two meal challenge discriminated a worsening of postprandial lipaemic control in subjects with ≥ 3 MetS components.

An approximate dynamic programming approach for improving accuracy of lossy data compression by Bloom filters

Bloom filters are a data structure for storing data in a compressed form. They offer excellent space and time efficiency at the cost of some loss of accuracy (so-called lossy compression). This work presents a yes-no Bloom filter, which as a data structure consisting of two parts: the yes-filter which is a standard Bloom filter and the no-filter which is another Bloom filter whose purpose is to represent those objects that were recognised incorrectly by the yes-filter (that is, to recognise the false positives of the yes-filter). By querying the no-filter after an object has been recognised by the yes-filter, we get a chance of rejecting it, which improves the accuracy of data recognition in comparison with the standard Bloom filter of the same total length. A further increase in accuracy is possible if one chooses objects to include in the no-filter so that the no-filter recognises as many as possible false positives but no true positives, thus producing the most accurate yes-no Bloom filter among all yes-no Bloom filters. This paper studies how optimization techniques can be used to maximize the number of false positives recognised by the no-filter, with the constraint being that it should recognise no true positives. To achieve this aim, an Integer Linear Program (ILP) is proposed for the optimal selection of false positives. In practice the problem size is normally large leading to intractable optimal solution. Considering the similarity of the ILP with the Multidimensional Knapsack Problem, an Approximate Dynamic Programming (ADP) model is developed making use of a reduced ILP for the value function approximation. Numerical results show the ADP model works best comparing with a number of heuristics as well as the CPLEX built-in solver (B&B), and this is what can be recommended for use in yes-no Bloom filters. In a wider context of the study of lossy compression algorithms, our researchis an example showing how the arsenal of optimization methods can be applied to improving the accuracy of compressed data.

Augmented Lagrangian methods under the constant positive linear dependence constraint qualification

Two Augmented Lagrangian algorithms for solving KKT systems are introduced. The algorithms differ in the way in which penalty parameters are updated. Possibly infeasible accumulation points are characterized. It is proved that feasible limit points that satisfy the Constant Positive Linear Dependence constraint qualification are KKT solutions. Boundedness of the penalty parameters is proved under suitable assumptions. Numerical experiments are presented.

Development of a sequential injection-square wave voltammetry method for determination of paraquat in water samples employing the hanging mercury drop electrode

This work describes the development and optimization of a sequential injection method to automate the determination of paraquat by square-wave voltammetry employing a hanging mercury drop electrode. Automation by sequential injection enhanced the sampling throughput, improving the sensitivity and precision of the measurements as a consequence of the highly reproducible and efficient conditions of mass transport of the analyte toward the electrode surface. For instance, 212 analyses can be made per hour if the sample/standard solution is prepared off-line and the sequential injection system is used just to inject the solution towards the flow cell. In-line sample conditioning reduces the sampling frequency to 44 h(-1). Experiments were performed in 0.10 M NaCl, which was the carrier solution, using a frequency of 200 Hz, a pulse height of 25 mV, a potential step of 2 mV, and a flow rate of 100 mu L s(-1). For a concentration range between 0.010 and 0.25 mg L(-1), the current (i(p), mu A) read at the potential corresponding to the peak maximum fitted the following linear equation with the paraquat concentration (mg L(-1)): ip = (-20.5 +/- 0.3) Cparaquat -(0.02 +/- 0.03). The limits of detection and quantification were 2.0 and 7.0 mu g L(-1), respectively. The accuracy of the method was evaluated by recovery studies using spiked water samples that were also analyzed by molecular absorption spectrophotometry after reduction of paraquat with sodium dithionite in an alkaline medium. No evidence of statistically significant differences between the two methods was observed at the 95% confidence level.

Developing a fluorimetric sequential injection methodology to study adsorption/desorption of glyphosate on soil and sediment samples

This paper describes the development of a sequential injection method to automate the fluorimetric determination of glyphosate based on a first step of oxidation to glycine by hypochlorite at 48 degrees C, followed by reaction with the fluorogenic reagent o-phthaldialdehyde in presence of 2-mercaptoethanol in borate buffer (pH > 9) to produce a fluorescent 1-(2`-hydroxyethylthio)-2-N-alkylisoindole. The proposed method has a linear response for glyphosate concentrations between 0.25 and 25.0 mu mol L(-1), with limits of detection and quantification of 0.08 and 0.25 mu mol L(-1), respectively. The sampling rate of the method is 18 samples per hour, consuming only a fraction of reagents consumed by the chromatographic method based on the same chemistry. The method was applied to study adsorption/desorption properties in a soil and in a sediment sample. Adsorption and desorption isotherms were properly fitted by Freundlich and Langmuir equations, leading to adsorption capacities of 1384 +/- 26 and 295 +/- 30 mg kg(-1) for the soil and sediment samples, respectively. These values are consistent with the literature, with the larger adsorption capacity of the soil being explained by its larger content of clay minerals, while the sediment was predominantly sandy. (C) 2011 Elsevier B.V. All rights reserved.

Square wave adsorptive cathodic stripping voltarnmetry automated by sequential injection analysis - Potentialities and limitations exemplified by the determination of methyl parathion in water samples

This paper describes the development and evaluation of a sequential injection method to automate the determination of methyl parathion by square wave adsorptive cathodic stripping voltammetry exploiting the concept of monosegmented flow analysis to perform in-line sample conditioning and standard addition. Accumulation and stripping steps are made in the sample medium conditioned with 40 mmol L-1 Britton-Robinson buffer (pH 10) in 0.25 mol L-1 NaNO3. The homogenized mixture is injected at a flow rate of 10 mu Ls(-1) toward the flow cell, which is adapted to the capillary of a hanging drop mercury electrode. After a suitable deposition time, the flow is stopped and the potential is scanned from -0.3 to -1.0 V versus Ag/AgCl at frequency of 250 Hz and pulse height of 25 mV The linear dynamic range is observed for methyl parathion concentrations between 0.010 and 0.50 mgL(-1), with detection and quantification limits of 2 and 7 mu gL(-1), respectively. The sampling throughput is 25 h(-1) if the in line standard addition and sample conditioning protocols are followed, but this frequency can be increased up to 61 h(-1) if the sample is conditioned off-line and quantified using an external calibration curve. The method was applied for determination of methyl parathion in spiked water samples and the accuracy was evaluated either by comparison to high performance liquid chromatography with UV detection, or by the recovery percentages. Although no evidences of statistically significant differences were observed between the expected and obtained concentrations, because of the susceptibility of the method to interference by other pesticides (e.g., parathion, dichlorvos) and natural organic matter (e.g., fulvic and humic acids), isolation of the analyte may be required when more complex sample matrices are encountered. (C) 2007 Elsevier B.V. All rights reserved.

Sequential cost-reimbursement rules

This paper studies cost-sharing rules under dynamic adverse selection. We present a typical principal-agent model with two periods, set up in Laffont and Tirole's (1986) canonical regulation environment. At first, when the contract is signed, the firm has prior uncertainty about its efficiency parameter. In the second period, the firm learns its efficiency and chooses the level of cost-reducing effort. The optimal mechanism sequentially screens the firm's types and achieves a higher level of welfare than its static counterpart. The contract is indirectly implemented by a sequence of transfers, consisting of a fixed advance payment based on the reported cost estimate, and an ex-post compensation linear in cost performance.

Robust State-Derivative Feedback LMI-Based Designs for Linear Descriptor Systems

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Fast sequential multi-element determination of Ca, Mg, K, Cu, Fe, Mn and Zn for foliar diagnosis using high-resolution continuum source flame atomic absorption spectrometry: Feasibility of secondary lines, side pixel registration and least-squares background correction

The fast sequential multi-element determination of Ca, Mg, K, Cu, Fe, Mn and Zn in plant tissues by high-resolution continuum source flame atomic absorption spectrometry is proposed. For this, the main lines for Cu (324.754 nm), Fe (248.327 nm), Mn (279.482 nm) and Zn (213.857 nm) were selected, and the secondary lines for Ca (239.856 nm), Mg (202.582 nm) and K (404.414 nm) were evaluated. The side pixel registration approach was studied to reduce sensitivity and extend the linear working range for Mg by measuring at wings (202.576 nm; 202.577 nm; 202.578 nm; 202.580 nm: 202.585 nm; 202.586 nm: 202.587 nm; 202.588 nm) of the secondary line. The interference caused by NO bands on Zn at 213.857 nm was removed using the least-squares background correction. Using the main lines for Cu, Fe, Mn and Zn, secondary lines for Ca and K, and line wing at 202.588 nm for Mg, and 5 mL min(-1) sample flow-rate, calibration curves in the 0.1-0.5 mg L-1 Cu, 0.5-4.0 mg L-1 Fe, 0.5-4.0 mg L-1 Mn, 0.2-1.0 mg L-1 Zn, 10.0-100.0 mg L-1 Ca, 5.0-40.0 mg L-1 Mg and 50.0-250.0 mg L-1 K ranges were consistently obtained. Accuracy and precision were evaluated after analysis of five plant standard reference materials. Results were in agreement at a 95% confidence level (paired t-test) with certified values. The proposed method was applied to digests of sugar-cane leaves and results were close to those obtained by line-source flame atomic absorption spectrometry. Recoveries of Ca, Mg, K, Cu, Fe, Mn and Zn in the 89-103%, 84-107%, 87-103%, 85-105%, 92-106%, 91-114%, 96-114% intervals, respectively, were obtained. The limits of detection were 0.6 mg L-1 Ca, 0.4 mg L-1 Mg, 0.4 mg L-1 K, 7.7 mu g L-1 Cu, 7.7 mu g L-1 Fe, 1.5 mu g L-1 Mn and 5.9 mu g L-1 Zn. (C) 2009 Elsevier B.V. All rights reserved.

Evaluation of alternate lines of Fe for sequential multi-element determination of Cu, Fe, Mn and Zn in soil extracts by high-resolution continuum source flame atomic absorption spectrometry

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Relação entre modelos de programação não-linear com incerteza no conjunto de restrições

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)