Design of totally self-checking asynchronous sequential machines.

Thesis (M.Sc.)--University of Illinois at Urbana-Champaign.

Multicore Scheduling of Real-Time Irregular Parallel Algorithms in Linux

Face à estagnação da tecnologia uniprocessador registada na passada década, aos principais fabricantes de microprocessadores encontraram na tecnologia multi-core a resposta `as crescentes necessidades de processamento do mercado. Durante anos, os desenvolvedores de software viram as suas aplicações acompanhar os ganhos de performance conferidos por cada nova geração de processadores sequenciais, mas `a medida que a capacidade de processamento escala em função do número de processadores, a computação sequencial tem de ser decomposta em várias partes concorrentes que possam executar em paralelo, para que possam utilizar as unidades de processamento adicionais e completar mais rapidamente. A programação paralela implica um paradigma completamente distinto da programação sequencial. Ao contrário dos computadores sequenciais tipificados no modelo de Von Neumann, a heterogeneidade de arquiteturas paralelas requer modelos de programação paralela que abstraiam os programadores dos detalhes da arquitectura e simplifiquem o desenvolvimento de aplicações concorrentes. Os modelos de programação paralela mais populares incitam os programadores a identificar instruções concorrentes na sua lógica de programação, e a especificá-las sob a forma de tarefas que possam ser atribuídas a processadores distintos para executarem em simultâneo. Estas tarefas são tipicamente lançadas durante a execução, e atribuídas aos processadores pelo motor de execução subjacente. Como os requisitos de processamento costumam ser variáveis, e não são conhecidos a priori, o mapeamento de tarefas para processadores tem de ser determinado dinamicamente, em resposta a alterações imprevisíveis dos requisitos de execução. `A medida que o volume da computação cresce, torna-se cada vez menos viável garantir as suas restrições temporais em plataformas uniprocessador. Enquanto os sistemas de tempo real se começam a adaptar ao paradigma de computação paralela, há uma crescente aposta em integrar execuções de tempo real com aplicações interativas no mesmo hardware, num mundo em que a tecnologia se torna cada vez mais pequena, leve, ubíqua, e portável. Esta integração requer soluções de escalonamento que simultaneamente garantam os requisitos temporais das tarefas de tempo real e mantenham um nível aceitável de QoS para as restantes execuções. Para tal, torna-se imperativo que as aplicações de tempo real paralelizem, de forma a minimizar os seus tempos de resposta e maximizar a utilização dos recursos de processamento. Isto introduz uma nova dimensão ao problema do escalonamento, que tem de responder de forma correcta a novos requisitos de execução imprevisíveis e rapidamente conjeturar o mapeamento de tarefas que melhor beneficie os critérios de performance do sistema. A técnica de escalonamento baseado em servidores permite reservar uma fração da capacidade de processamento para a execução de tarefas de tempo real, e assegurar que os efeitos de latência na sua execução não afectam as reservas estipuladas para outras execuções. No caso de tarefas escalonadas pelo tempo de execução máximo, ou tarefas com tempos de execução variáveis, torna-se provável que a largura de banda estipulada não seja consumida por completo. Para melhorar a utilização do sistema, os algoritmos de partilha de largura de banda (capacity-sharing) doam a capacidade não utilizada para a execução de outras tarefas, mantendo as garantias de isolamento entre servidores. Com eficiência comprovada em termos de espaço, tempo, e comunicação, o mecanismo de work-stealing tem vindo a ganhar popularidade como metodologia para o escalonamento de tarefas com paralelismo dinâmico e irregular. O algoritmo p-CSWS combina escalonamento baseado em servidores com capacity-sharing e work-stealing para cobrir as necessidades de escalonamento dos sistemas abertos de tempo real. Enquanto o escalonamento em servidores permite partilhar os recursos de processamento sem interferências a nível dos atrasos, uma nova política de work-stealing que opera sobre o mecanismo de capacity-sharing aplica uma exploração de paralelismo que melhora os tempos de resposta das aplicações e melhora a utilização do sistema. Esta tese propõe uma implementação do algoritmo p-CSWS para o Linux. Em concordância com a estrutura modular do escalonador do Linux, ´e definida uma nova classe de escalonamento que visa avaliar a aplicabilidade da heurística p-CSWS em circunstâncias reais. Ultrapassados os obstáculos intrínsecos `a programação da kernel do Linux, os extensos testes experimentais provam que o p-CSWS ´e mais do que um conceito teórico atrativo, e que a exploração heurística de paralelismo proposta pelo algoritmo beneficia os tempos de resposta das aplicações de tempo real, bem como a performance e eficiência da plataforma multiprocessador.

Discrete wavelet transform signal analyzer

This paper addresses the problem of processing biological data, such as cardiac beats in the audio and ultrasonic range, and on calculating wavelet coefficients in real time, with the processor clock running at a frequency of present application-specified integrated circuits and field programmable gate array. The parallel filter architecture for discrete wavelet transform (DWT) has been improved, calculating the wavelet coefficients in real time with hardware reduced up to 60%. The new architecture, which also processes inverse DWT, is implemented with the Radix-2 or the Booth-Wallace constant multipliers. One integrated circuit signal analyzer in the ultrasonic range, including series memory register banks, is presented. © 2007 IEEE.

Static Analysis of Usefulness States in Transition P Systems

Transition P Systems are a parallel and distributed computational model based on the notion of the cellular membrane structure. Each membrane determines a region that encloses a multiset of objects and evolution rules. Transition P Systems evolve through transitions between two consecutive configurations that are determined by the membrane structure and multisets present inside membranes. Moreover, transitions between two consecutive configurations are provided by an exhaustive non-deterministic and parallel application of evolution rules. But, to establish the rules to be applied, it is required the previous calculation of useful, applicable and active rules. Hence, computation of useful evolution rules is critical for the whole evolution process efficiency, because it is performed in parallel inside each membrane in every evolution step. This work defines usefulness states through an exhaustive analysis of the P system for every membrane and for every possible configuration of the membrane structure during the computation. Moreover, this analysis can be done in a static way; therefore membranes only have to check their usefulness states to obtain their set of useful rules during execution.

An integrated scheduling problem of PCB components on sequential pick-and-place machines:mathematical models and heuristic solutions

This paper formulates several mathematical models for determining the optimal sequence of component placements and assignment of component types to feeders simultaneously or the integrated scheduling problem for a type of surface mount technology placement machines, called the sequential pick-andplace (PAP) machine. A PAP machine has multiple stationary feeders storing components, a stationary working table holding a printed circuit board (PCB), and a movable placement head to pick up components from feeders and place them to a board. The objective of integrated problem is to minimize the total distance traveled by the placement head. Two integer nonlinear programming models are formulated first. Then, each of them is equivalently converted into an integer linear type. The models for the integrated problem are verified by two commercial packages. In addition, a hybrid genetic algorithm previously developed by the authors is adopted to solve the models. The algorithm not only generates the optimal solutions quickly for small-sized problems, but also outperforms the genetic algorithms developed by other researchers in terms of total traveling distance.

Smart machines in day-to-day financial management:

Starting from Novabase’s challenge to launch in the UK Millennials a personal financial advisor mobile application, this work project aims to build a planning model to frame a business side of a launch strategy for mobile application in similar market and category. This study culminates on the design of SPOSTAC planning model. The created framework is intended to effectively and efficiently plan a launch strategy, being structured based on seven sequential elements: Situation, Product, Objectives, Strategy, Tactics, Action, and Control.

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.

KrigInv: An efficient and user-friendly implementation of batch-sequential inversion strategies based on kriging

Several strategies relying on kriging have recently been proposed for adaptively estimating contour lines and excursion sets of functions under severely limited evaluation budget. The recently released R package KrigInv 3 is presented and offers a sound implementation of various sampling criteria for those kinds of inverse problems. KrigInv is based on the DiceKriging package, and thus benefits from a number of options concerning the underlying kriging models. Six implemented sampling criteria are detailed in a tutorial and illustrated with graphical examples. Different functionalities of KrigInv are gradually explained. Additionally, two recently proposed criteria for batch-sequential inversion are presented, enabling advanced users to distribute function evaluations in parallel on clusters or clouds of machines. Finally, auxiliary problems are discussed. These include the fine tuning of numerical integration and optimization procedures used within the computation and the optimization of the considered criteria.

Computer control of machines utilising independent drive mechanisms

The thesis describes an investigation into methods for the specification, design and implementation of computer control systems for flexible manufacturing machines comprising multiple, independent, electromechanically-driven mechanisms. An analysis is made of the elements of conventional mechanically-coupled machines in order that the operational functions of these elements may be identified. This analysis is used to define the scope of requirements necessary to specify the format, function and operation of a flexible, independently driven mechanism machine. A discussion of how this type of machine can accommodate modern manufacturing needs of high-speed and flexibility is presented. A sequential method of capturing requirements for such machines is detailed based on a hierarchical partitioning of machine requirements from product to independent drive mechanism. A classification of mechanisms using notations, including Data flow diagrams and Petri-nets, is described which supports capture and allows validation of requirements. A generic design for a modular, IDM machine controller is derived based upon hierarchy of control identified in these machines. A two mechanism experimental machine is detailed which is used to demonstrate the application of the specification, design and implementation techniques. A computer controller prototype and a fully flexible implementation for the IDM machine, based on Petri-net models described using the concurrent programming language Occam, is detailed. The ability of this modular computer controller to support flexible, safe and fault-tolerant operation of the two intermittent motion, discrete-synchronisation independent drive mechanisms is presented. The application of the machine development methodology to industrial projects is established.

Analyzing the n→π* Electronic Transition of Formaldehyde in Water. A Sequential Monte Carlo/Time-Dependent Density Functional Theory

The n→π* absorption transition of formaldehyde in water is analyzed using combined and sequential classical Monte Carlo (MC) simulations and quantum mechanics (QM) calculations. MC simulations generate the liquid solute-solvent structures for subsequent QM calculations. Using time-dependent density functional theory in a localized set of gaussian basis functions (TD-DFT/6-311++G(d,p)) calculations are made on statistically relevant configurations to obtain the average solvatochromic shift. All results presented here use the electrostatic embedding of the solvent. The statistically converged average result obtained of 2300 cm-1 is compared to previous theoretical results available. Analysis is made of the effective dipole moment of the hydrogen-bonded shell and how it could be held responsible for the polarization of the solvent molecules in the outer solvation shells.

Determination of picloram in waters by sequential injection chromatography with UV detection

This paper describes a sequential injection chromatography procedure for determination of picloram in waters exploring the low backpressure of a 2.5 cm long monolithic C18 column. Separation of the analyte from the matrix was achieved in less than 60 s using a mobile phase composed by 20:80 (v v-1) acetonitrile:5.0 mmol L-1 H3PO4 and flow rate of 30 μL s-1. Detection was made at 223 nm with a 40 mm optical path length cell. The limits of detection and quantification were 33 and 137 μg L-1, respectively. The proposed method is sensitive enough to monitor the maximum concentration level for picloram in drinking water (500 μg L-1). The sampling frequency is 60 analyses per hour, consuming only 300 μL of acetonitrile per analysis. The proposed methodology was applied to spiked river water samples and no statistically significant differences were observed in comparison to a conventional HPLC-UV method.

Development of a flow through photo-reactor to study degradation of organic compounds by Sequential Injection Analysis (SIA)

This work describes a photo-reactor to perform in line degradation of organic compounds by photo-Fenton reaction using Sequential Injection Analysis (SIA) system. A copper phthalocyanine-3,4',4²,4²¢-tetrasulfonic acid tetrasodium salt dye solution was used as a model compound for the phthalocyanine family, whose pigments have a large use in automotive coatings industry. Based on preliminary tests, 97% of color removal was obtained from a solution containing 20 µmol L-1 of this dye.

Sequential hygienic behavior in Carniolan honey bees (Apis mellifera carnica)

We examined the sequence, order or steps of hygienic behavior (HB) from pin-killed pupae until the removal of them by the bees. We conducted our study with four colonies of Apis mellifera carnica in Germany and made four repetitions. The pin-killing method was used for evaluation of the HB of bees. The data were collected every 2 h after perforation, totaling 13 observations. Additionally, for one hygienic colony and another non-hygienic colony, individual analyses of each dead pupa were made at every observation, including all details, steps or sequences of HB. The bees recognize the cells containing dead pupae within 2 h after perforation, initially making a hole in the capping, which is the beginning of HB. Uncapping of the dead brood cell reached maximum values from 4 to 6 h after perforation; after 24 h, practically all cells were already uncapped. Another variable, called brood partially removed, was analyzed 4 h after perforation, after the cells had been perforated, which involved uncapping, followed by partial or total removal of the brood. Maximum values of brood partially removed were found 10 h after perforation, though such cells could be found up to 48 h after perforation. The most frequent sequence of events in both colonies was: capped cell -> punctured cell. brood partially removed -> empty cell. A new model of three pairs of recessive genes (uncapping u1, u2 and remover r) was proposed in order to explain the genetic control of the HB in Apis mellifera. We recommend evaluating HB 24 h after perforation and using a correction factor to compensate for control removal levels. We found a series of details of HB, which allow a study of how various factors may affect the sequence of the activities involved in HB and investigation of the genetics that controls this process.

Sequential analysis of global gene expression profiles in immature and in vitro matured bovine oocytes: potential molecular markers of oocyte maturation

Background: Without intensive selection, the majority of bovine oocytes submitted to in vitro embryo production (IVP) fail to develop to the blastocyst stage. This is attributed partly to their maturation status and competences. Using the Affymetrix GeneChip Bovine Genome Array, global mRNA expression analysis of immature (GV) and in vitro matured (IVM) bovine oocytes was carried out to characterize the transcriptome of bovine oocytes and then use a variety of approaches to determine whether the observed transcriptional changes during IVM was real or an artifact of the techniques used during analysis. Results: 8489 transcripts were detected across the two oocyte groups, of which similar to 25.0% (2117 transcripts) were differentially expressed (p < 0.001); corresponding to 589 over-expressed and 1528 under-expressed transcripts in the IVM oocytes compared to their immature counterparts. Over expression of transcripts by IVM oocytes is particularly interesting, therefore, a variety of approaches were employed to determine whether the observed transcriptional changes during IVM were real or an artifact of the techniques used during analysis, including the analysis of transcript abundance in oocytes in vitro matured in the presence of a-amanitin. Subsets of the differentially expressed genes were also validated by quantitative real-time PCR (qPCR) and the gene expression data was classified according to gene ontology and pathway enrichment. Numerous cell cycle linked (CDC2, CDK5, CDK8, HSPA2, MAPK14, TXNL4B), molecular transport (STX5, STX17, SEC22A, SEC22B), and differentiation (NACA) related genes were found to be among the several over-expressed transcripts in GV oocytes compared to the matured counterparts, while ANXA1, PLAU, STC1and LUM were among the over-expressed genes after oocyte maturation. Conclusion: Using sequential experiments, we have shown and confirmed transcriptional changes during oocyte maturation. This dataset provides a unique reference resource for studies concerned with the molecular mechanisms controlling oocyte meiotic maturation in cattle, addresses the existing conflicting issue of transcription during meiotic maturation and contributes to the global goal of improving assisted reproductive technology.

Dynamic polarizability, Cauchy moments, and the optical absorption spectrum of liquid water: A sequential molecular dynamics/quantum mechanical approach

The dynamic polarizability and optical absorption spectrum of liquid water in the 6-15 eV energy range are investigated by a sequential molecular dynamics (MD)/quantum mechanical approach. The MD simulations are based on a polarizable model for liquid water. Calculation of electronic properties relies on time-dependent density functional and equation-of-motion coupled-cluster theories. Results for the dynamic polarizability, Cauchy moments, S(-2), S(-4), S(-6), and dielectric properties of liquid water are reported. The theoretical predictions for the optical absorption spectrum of liquid water are in good agreement with experimental information.