Allocation of Parallel Real-Time Tasks in Distributed Multi-core Architectures supported by an FTT-SE Network

Distributed real-time systems such as automotive applications are becoming larger and more complex, thus, requiring the use of more powerful hardware and software architectures. Furthermore, those distributed applications commonly have stringent real-time constraints. This implies that such applications would gain in flexibility if they were parallelized and distributed over the system. In this paper, we consider the problem of allocating fixed-priority fork-join Parallel/Distributed real-time tasks onto distributed multi-core nodes connected through a Flexible Time Triggered Switched Ethernet network. We analyze the system requirements and present a set of formulations based on a constraint programming approach. Constraint programming allows us to express the relations between variables in the form of constraints. Our approach is guaranteed to find a feasible solution, if one exists, in contrast to other approaches based on heuristics. Furthermore, approaches based on constraint programming have shown to obtain solutions for these type of formulations in reasonable time.

Non-preemptive and SRP-based fullypreemptive scheduling of real-time Software Transactional Memory

Recent embedded processor architectures containing multiple heterogeneous cores and non-coherent caches renewed attention to the use of Software Transactional Memory (STM) as a building block for developing parallel applications. STM promises to ease concurrent and parallel software development, but relies on the possibility of abort conflicting transactions to maintain data consistency, which in turns affects the execution time of tasks carrying transactions. Because of this fact the timing behaviour of the task set may not be predictable, thus it is crucial to limit the execution time overheads resulting from aborts. In this paper we formalise a FIFO-based algorithm to order the sequence of commits of concurrent transactions. Then, we propose and evaluate two non-preemptive and one SRP-based fully-preemptive scheduling strategies, in order to avoid transaction starvation.

Parallel Software framework for time-critical many-core systems

The recent technological advancements and market trends are causing an interesting phenomenon towards the convergence of High-Performance Computing (HPC) and Embedded Computing (EC) domains. On one side, new kinds of HPC applications are being required by markets needing huge amounts of information to be processed within a bounded amount of time. On the other side, EC systems are increasingly concerned with providing higher performance in real-time, challenging the performance capabilities of current architectures. The advent of next-generation many-core embedded platforms has the chance of intercepting this converging need for predictable high-performance, allowing HPC and EC applications to be executed on efficient and powerful heterogeneous architectures integrating general-purpose processors with many-core computing fabrics. To this end, it is of paramount importance to develop new techniques for exploiting the massively parallel computation capabilities of such platforms in a predictable way. P-SOCRATES will tackle this important challenge by merging leading research groups from the HPC and EC communities. The time-criticality and parallelisation challenges common to both areas will be addressed by proposing an integrated framework for executing workload-intensive applications with real-time requirements on top of next-generation commercial-off-the-shelf (COTS) platforms based on many-core accelerated architectures. The project will investigate new HPC techniques that fulfil real-time requirements. The main sources of indeterminism will be identified, proposing efficient mapping and scheduling algorithms, along with the associated timing and schedulability analysis, to guarantee the real-time and performance requirements of the applications.

Geometry based visualization with OpenCL

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

A system’s approach to cache hierarchy-aware decomposition of data-parallel computations

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

Development of novel ionic liquids based on biological molecules

Ionic Liquids (ILs) belong to a class of compounds with unusual properties: very low vapour pressure; high chemical and thermal stability and the ability to dissolve a wide range of substances. A new field in research is evaluating the possibility to use natural chiral biomolecules for the preparation of chiral ionic liquids (CILs). This important challenge in synthetic chemistry can open new avenues of research in order to avoid some problems related with the intrinsic biodegradability and toxicity associated to conventional ILs. The research work developed aimed for the synthesis of CILs, their characterization and possible applications, based on biological moieties used either as chiral cations or anions, depending on the synthetic manipulation of the derivatives. Overall, a total of 28 organic salts, including CILs were synthesized: 9 based on L-cysteine derivatives, 12 based on L-proline, 3 based on nucleosides and 4 based on nucleotides. All these new CILs were completely characterized and their chemical and physical properties were evaluated. Some CILs based on L-cysteine have been applied for discrimination processes, including resolution of racemates and as a chiral catalyst for asymmetric Aldol condensation. L-proline derived CILs were also studied as chiral catalysts for Michael reaction. In parallel, the interactions of macrocyclic oligosugars called cyclodextrins (CDs) with several ILs were studied. It was possible to improve the solubility of CDs in water and serum. Additionally, fatty acids and steroids showed an increase in water solubility when ILs-CDs systems were used. The development of efficient and selective ILs-CDs systems is indispensable to expand the range of their applications in host-guest interactions, drug delivery systems or catalytic reactions. Novel salts derived from nucleobases were used in order to enhance the fluorescence in aqueous solution. Additionally, preliminary studies regarding ethyl lactate as an alternative solvent for asymmetric organocatalysis were performed.

A public transport bus assignment problem: parallel metaheuristics assessment

Combinatorial Optimization Problems occur in a wide variety of contexts and generally are NP-hard problems. At a corporate level solving this problems is of great importance since they contribute to the optimization of operational costs. In this thesis we propose to solve the Public Transport Bus Assignment problem considering an heterogeneous fleet and line exchanges, a variant of the Multi-Depot Vehicle Scheduling Problem in which additional constraints are enforced to model a real life scenario. The number of constraints involved and the large number of variables makes impracticable solving to optimality using complete search techniques. Therefore, we explore metaheuristics, that sacrifice optimality to produce solutions in feasible time. More concretely, we focus on the development of algorithms based on a sophisticated metaheuristic, Ant-Colony Optimization (ACO), which is based on a stochastic learning mechanism. For complex problems with a considerable number of constraints, sophisticated metaheuristics may fail to produce quality solutions in a reasonable amount of time. Thus, we developed parallel shared-memory (SM) synchronous ACO algorithms, however, synchronism originates the straggler problem. Therefore, we proposed three SM asynchronous algorithms that break the original algorithm semantics and differ on the degree of concurrency allowed while manipulating the learned information. Our results show that our sequential ACO algorithms produced better solutions than a Restarts metaheuristic, the ACO algorithms were able to learn and better solutions were achieved by increasing the amount of cooperation (number of search agents). Regarding parallel algorithms, our asynchronous ACO algorithms outperformed synchronous ones in terms of speedup and solution quality, achieving speedups of 17.6x. The cooperation scheme imposed by asynchronism also achieved a better learning rate than the original one.

Al-doped ZnO ceramic sputtering targets based on nanocrystalline powders produced by emulsion detonation synthesis – deposition and application as a transparent conductive oxide material

Transparent conducting oxides (TCOs) have been largely used in the optoelectronic industry due to their singular combination of low electrical resistivity and high optical transmittance. They are usually deposited by magnetron sputtering systems being applied in several devices, specifically thin film solar cells (TFSCs). Sputtering targets are crucial components of the sputtering process, with many of the sputtered films properties dependent on the targets characteristics. The present thesis focuses on the development of high quality conductive Al-doped ZnO (AZO) ceramic sputtering targets based on nanostructured powders produced by emulsion detonation synthesis method (EDSM), and their application as a TCO. In this sense, the influence of several processing parameters was investigated from the targets raw-materials synthesis to the application of sputtered films in optoelectronic devices. The optimized manufactured AZO targets present a final density above 99 % with controlled grain size, an homogeneous microstructure with a well dispersed ZnAl2O4 spinel phase, and electrical resistivities of ~4 × 10-4 Ωcm independently on the Al-doping level among 0.5 and 2.0 wt. % Al2O3. Sintering conditions proved to have a great influence on the properties of the targets and their performance as a sputtering target. It was demonstrated that both deposition process and final properties of the films are related with the targets characteristics, which in turn depends on the initial powder properties. In parallel, the influence of several deposition parameters in the film´s properties sputtered from these targets was investigated. The sputtered AZO TCOs showed electrical properties at room temperature that are superior to simple oxides and comparable to a reference TCO – indium tin oxide (ITO), namely low electrical resistivity of 5.45 × 10-4 Ωcm, high carrier mobility (29.4 cm2V-1s-1), and high charge carrier concentration (3.97 × 1020 cm-3), and also average transmittance in the visible region > 80 %. These superior properties allowed their successful application in different optoelectronic devices.

Parallel improved Schnorr-Euchner enumeration SE++ for the CVP and SVP

The Closest Vector Problem (CVP) and the Shortest Vector Problem (SVP) are prime problems in lattice-based cryptanalysis, since they underpin the security of many lattice-based cryptosystems. Despite the importance of these problems, there are only a few CVP-solvers publicly available, and their scalability was never studied. This paper presents a scalable implementation of an enumeration-based CVP-solver for multi-cores, which can be easily adapted to solve the SVP. In particular, it achieves super-linear speedups in some instances on up to 8 cores and almost linear speedups on 16 cores when solving the CVP on a 50-dimensional lattice. Our results show that enumeration-based CVP-solvers can be parallelized as effectively as enumeration-based solvers for the SVP, based on a comparison with a state of the art SVP-solver. In addition, we show that we can optimize the SVP variant of our solver in such a way that it becomes 35%-60% faster than the fastest enumeration-based SVP-solver to date.

Fine time scaling of purifying selection on human nonsynonymous mtDNA mutations based on the worldwide population tree and mother-child pairs

A high-resolution mtDNA phylogenetic tree allowed us to look backward in time to investigate purifying selection. Purifying selection was very strong in the last 2,500 years, continuously eliminating pathogenic mutations back until the end of the Younger Dryas (∼11,000 years ago), when a large population expansion likely relaxed selection pressure. This was preceded by a phase of stable selection until another relaxation occurred in the out-of-Africa migration. Demography and selection are closely related: expansions led to relaxation of selection and higher pathogenicity mutations significantly decreased the growth of descendants. The only detectible positive selection was the recurrence of highly pathogenic nonsynonymous mutations (m.3394T>C-m.3397A>G-m.3398T>C) at interior branches of the tree, preventing the formation of a dinucleotide STR (TATATA) in the MT-ND1 gene. At the most recent time scale in 124 mother-children transmissions, purifying selection was detectable through the loss of mtDNA variants with high predicted pathogenicity. A few haplogroup-defining sites were also heteroplasmic, agreeing with a significant propensity in 349 positions in the phylogenetic tree to revert back to the ancestral variant. This nonrandom mutation property explains the observation of heteroplasmic mutations at some haplogroup-defining sites in sequencing datasets, which may not indicate poor quality as has been claimed.

An atlas of human gene expression from massively parallel signature sequencing (MPSS).

We have used massively parallel signature sequencing (MPSS) to sample the transcriptomes of 32 normal human tissues to an unprecedented depth, thus documenting the patterns of expression of almost 20,000 genes with high sensitivity and specificity. The data confirm the widely held belief that differences in gene expression between cell and tissue types are largely determined by transcripts derived from a limited number of tissue-specific genes, rather than by combinations of more promiscuously expressed genes. Expression of a little more than half of all known human genes seems to account for both the common requirements and the specific functions of the tissues sampled. A classification of tissues based on patterns of gene expression largely reproduces classifications based on anatomical and biochemical properties. The unbiased sampling of the human transcriptome achieved by MPSS supports the idea that most human genes have been mapped, if not functionally characterized. This data set should prove useful for the identification of tissue-specific genes, for the study of global changes induced by pathological conditions, and for the definition of a minimal set of genes necessary for basic cell maintenance. The data are available on the Web at http://mpss.licr.org and http://sgb.lynxgen.com.

Low-frequency drug-resistant HIV-1 and risk of virological failure to first-line NNRTI-based ART: a multicohort European case-control study using centralized ultrasensitive 454 pyrosequencing.

OBJECTIVES: It is still debated if pre-existing minority drug-resistant HIV-1 variants (MVs) affect the virological outcomes of first-line NNRTI-containing ART. METHODS: This Europe-wide case-control study included ART-naive subjects infected with drug-susceptible HIV-1 as revealed by population sequencing, who achieved virological suppression on first-line ART including one NNRTI. Cases experienced virological failure and controls were subjects from the same cohort whose viraemia remained suppressed at a matched time since initiation of ART. Blinded, centralized 454 pyrosequencing with parallel bioinformatic analysis in two laboratories was used to identify MVs in the 1%-25% frequency range. ORs of virological failure according to MV detection were estimated by logistic regression. RESULTS: Two hundred and sixty samples (76 cases and 184 controls), mostly subtype B (73.5%), were used for the analysis. Identical MVs were detected in the two laboratories. 31.6% of cases and 16.8% of controls harboured pre-existing MVs. Detection of at least one MV versus no MVs was associated with an increased risk of virological failure (OR = 2.75, 95% CI = 1.35-5.60, P = 0.005); similar associations were observed for at least one MV versus no NRTI MVs (OR = 2.27, 95% CI = 0.76-6.77, P = 0.140) and at least one MV versus no NNRTI MVs (OR = 2.41, 95% CI = 1.12-5.18, P = 0.024). A dose-effect relationship between virological failure and mutational load was found. CONCLUSIONS: Pre-existing MVs more than double the risk of virological failure to first-line NNRTI-based ART.

Including the workload effect in the parallel program signature

Performance prediction and application behavior modeling have been the subject of exten- sive research that aim to estimate applications performance with an acceptable precision. A novel approach to predict the performance of parallel applications is based in the con- cept of Parallel Application Signatures that consists in extract an application most relevant parts (phases) and the number of times they repeat (weights). Executing these phases in a target machine and multiplying its exeuction time by its weight an estimation of the application total execution time can be made. One of the problems is that the performance of an application depends on the program workload. Every type of workload affects differently how an application performs in a given system and so affects the signature execution time. Since the workloads used in most scientific parallel applications have dimensions and data ranges well known and the behavior of these applications are mostly deterministic, a model of how the programs workload affect its performance can be obtained. We create a new methodology to model how a program’s workload affect the parallel application signature. Using regression analysis we are able to generalize each phase time execution and weight function to predict an application performance in a target system for any type of workload within predefined range. We validate our methodology using a synthetic program, benchmarks applications and well known real scientific applications.

An antibody-based ELISA for quantification of Ani s 1, a major allergen from Anisakis simplex.

Anisakis simplex is a nematode parasite that can infect humans who have eaten raw or undercooked seafood. Larvae invading the gastrointestinal mucosa excrete/secrete proteins that are implicated in the pathogenesis of anisakiasis and can induce IgE-mediated symptoms. Since Ani s 1 is a potent secreted allergen with important clinical relevance, its measurement could assess the quality of allergenic products used in diagnosis/immunotherapy of Anisakis allergy and track the presence of A. simplex parasites in fish foodstuffs. An antibody-based ELISA for quantification of Ani s 1 has been developed based on monoclonal antibody 4F2 as capture antibody and biotin-labelled polyclonal antibodies against Ani s 1 as detection reagent. The dose-response standard curves, obtained with natural and recombinant antigens, ranged from 4 to 2000 ng/ml and were identical and parallel to that of the A. simplex extract. The linear portion of the dose-response curve with nAni s 1 was between 15 and 250 ng/ml with inter-assay and intra-assays coefficients of variation less than 20% and 10%, respectively. The assay was specific since there was no cross-reaction with other extracts (except Ascaris extracts) and was highly sensitive (detection limit of 1·8 ng/ml), being able to detect Ani s 1 in fish extracts from codfish and monkfish.

Plane-to-plane positioning from image-based visual servoing and structured light

In this paper we face the problem of positioning a camera attached to the end-effector of a robotic manipulator so that it gets parallel to a planar object. Such problem has been treated for a long time in visual servoing. Our approach is based on linking to the camera several laser pointers so that its configuration is aimed to produce a suitable set of visual features. The aim of using structured light is not only for easing the image processing and to allow low-textured objects to be treated, but also for producing a control scheme with nice properties like decoupling, stability, well conditioning and good camera trajectory