Sistema de reconhecimento de impressões digitais baseado em FPGA

Trabalho de Projeto para obtenção do grau de Mestre em Engenharia de Eletrónica e Telecomunicações

Despacho económico de unidades com funções de custo não convexas usando enxames

Dissertação para obtenção do grau de Mestre em Engenharia Electrotécnica Ramo de Energia

Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound

Known algorithms capable of scheduling implicit-deadline sporadic tasks over identical processors at up to 100% utilisation invariably involve numerous preemptions and migrations. To the challenge of devising a scheduling scheme with as few preemptions and migrations as possible, for a given guaranteed utilisation bound, we respond with the algorithm NPS-F. It is configurable with a parameter, trading off guaranteed schedulable utilisation (up to 100%) vs preemptions. For any possible configuration, NPS-F introduces fewer preemptions than any other known algorithm matching its utilisation bound. A clustered variant of the algorithm, for systems made of multicore chips, eliminates (costly) off-chip task migrations, by dividing processors into disjoint clusters, formed by cores on the same chip (with the cluster size being a parameter). Clusters are independently scheduled (each, using non-clustered NPS-F). The utilisation bound is only moderately affected. We also formulate an important extension (applicable to both clustered and non-clustered NPS-F) which optimises the supply of processing time to executing tasks and makes it more granular. This reduces processing capacity requirements for schedulability without increasing preemptions.

Analysis of the domain of applicability of an algorithm for a resources system selection problem for Distributed/Agile/Virtual Enterprises integration

The process of resources systems selection takes an important part in Distributed/Agile/Virtual Enterprises (D/A/V Es) integration. However, the resources systems selection is still a difficult matter to solve in a D/A/VE, as it is pointed out in this paper. Globally, we can say that the selection problem has been equated from different aspects, originating different kinds of models/algorithms to solve it. In order to assist the development of a web prototype tool (broker tool), intelligent and flexible, that integrates all the selection model activities and tools, and with the capacity to adequate to each D/A/V E project or instance (this is the major goal of our final project), we intend in this paper to show: a formulation of a kind of resources selection problem and the limitations of the algorithms proposed to solve it. We formulate a particular case of the problem as an integer programming, which is solved using simplex and branch and bound algorithms, and identify their performance limitations (in terms of processing time) based on simulation results. These limitations depend on the number of processing tasks and on the number of pre-selected resources per processing tasks, defining the domain of applicability of the algorithms for the problem studied. The limitations detected open the necessity of the application of other kind of algorithms (approximate solution algorithms) outside the domain of applicability founded for the algorithms simulated. However, for a broker tool it is very important the knowledge of algorithms limitations, in order to, based on problem features, develop and select the most suitable algorithm that guarantees a good performance.

Afetação de recursos em sistemas de produção

O problema do escalonamento, por ser um dos factores fundamentais na tomada de decisão para uma boa gestão das operações, tem sido alvo de um amplo estudo, tanto na sua componente teórica como na sua componente prática. A importância de um escalonamento correto das operações é preponderante, quando as pequenas diferenças, em termos de tempos de produção, podem ter um grande impacto na competitividade da organização. Em muitas unidades produtivas, existem máquinas capazes de realizar as mesmas operações com diferentes desempenhos. Isto pode dever-se à necessidade de flexibilizar os recursos ou mesmo a uma atualização da capacidade produtiva. Embora os problemas de máquinas diferentes em paralelo tenham sido alvo de um vasto estudo, muitos deles não são passíveis de ser resolvidos através de métodos exatos. O problema de minimização do makespan (Rm||Cmax), é NP-hard, sendo habitualmente abordado através de heurísticas. Entre as heurísticas utilizadas em problemas de minimização do makespan em máquinas diferentes em paralelo, é possível identificar duas filosofias de afectação: a que utiliza os tempos de processamento para alocar as tarefas e a que utiliza as datas de conclusão. Nesta dissertação, pretende-se dar uma contribuição para a resolução do problema de afectação de recursos em sistemas de produção. Para tal, foram propostas as heurísticas OMTC 3 e Suffrage One. A contribuição consiste na proposta de versões híbridas e modificadas das heurística MCT e Suffrage, uma vez identificadas várias características que podem limitar o seu desempenho, como o facto da heurística MCT alocar as tarefas numa ordem aleatória ou a heurística Suffrage alocar mais que uma tarefa por iteração. Finalmente, procedeu-se à realização de testes computacionais, para avaliar o desempenho das heurísticas propostas. Os testes realizados permitiram concluir que a heurística OMTC 3 apresentou um melhor desempenho que a heurística MCT.

A new approach to assess defragmentation strategies in dynamically reconfigurable FPGAs

Fragmentation on dynamically reconfigurable FPGAs is a major obstacle to the efficient management of the logic space in reconfigurable systems. When resource allocation decisions have to be made at run-time a rearrangement may be necessary to release enough contiguous resources to implement incoming functions. The feasibility of run-time relocation depends on the processing time required to set up rearrangements. Moreover, the performance of the relocated functions should not be affected by this process or otherwise the whole system performance, and even its operation, may be at risk. Relocation should take into account not only specific functional issues, but also the FPGA architecture, since these two aspects are normally intertwined. A simple and fast method to assess performance degradation of a function during relocation and to speed up the defragmentation process, based on previous function labelling and on the application of the Euclidian distance concept, is proposed in this paper.

Parallel hyperspectral compressive sensing method on GPU

Remote hyperspectral sensors collect large amounts of data per flight usually with low spatial resolution. It is known that the bandwidth connection between the satellite/airborne platform and the ground station is reduced, thus a compression onboard method is desirable to reduce the amount of data to be transmitted. This paper presents a parallel implementation of an compressive sensing method, called parallel hyperspectral coded aperture (P-HYCA), for graphics processing units (GPU) using the compute unified device architecture (CUDA). This method takes into account two main properties of hyperspectral dataset, namely the high correlation existing among the spectral bands and the generally low number of endmembers needed to explain the data, which largely reduces the number of measurements necessary to correctly reconstruct the original data. Experimental results conducted using synthetic and real hyperspectral datasets on two different GPU architectures by NVIDIA: GeForce GTX 590 and GeForce GTX TITAN, reveal that the use of GPUs can provide real-time compressive sensing performance. The achieved speedup is up to 20 times when compared with the processing time of HYCA running on one core of the Intel i7-2600 CPU (3.4GHz), with 16 Gbyte memory.

Estrutura a partir do Movimento em Sistemas Autónomos

Mestrado em Engenharia Electrotécnica e de Computadores - Ramo de Sistemas Autónomos

RealCrono –sistema de difusão de resultados em tempo real na web

A velocidade de difusão de conteúdos numa plataforma web, assume uma elevada relevância em serviços onde a informação se pretende atualizada e em tempo real. Este projeto de Mestrado, apresenta uma abordagem de um sistema distribuído de recolher e difundir resultados em tempo real entre várias plataformas, nomeadamente sistemas móveis. Neste contexto, tempo real entende-se como uma diferença de tempo nula entre a recolha e difusão, ignorando fatores que não podem ser controlados pelo sistema, como latência de comunicação e tempo de processamento. Este projeto tem como base uma arquitetura existente de processamento e publicação de resultados desportivos, que apresentava alguns problemas relacionados com escalabilidade, segurança, tempos de entrega de resultados longos e sem integração com outras plataformas. Ao longo deste trabalho procurou-se investigar fatores que condicionassem a escalabilidade de uma aplicação web dando ênfase à implementação de uma solução baseada em replicação e escalabilidade horizontal. Procurou-se também apresentar uma solução de interoperabilidade entre sistemas e plataformas heterogêneas, mantendo sempre elevados níveis de performance e promovendo a introdução de plataformas móveis no sistema. De várias abordagens existentes para comunicação em tempo real sobre uma plataforma web, adotou-se um implementação baseada em WebSocket que elimina o tempo desperdiçado entre a recolha de informação e sua difusão. Neste projeto é descrito o processo de implementação da API de recolha de dados (Collector), da biblioteca de comunicação com o Collector, da aplicação web (Publisher) e sua API, da biblioteca de comunicação com o Publisher e por fim a implementação da aplicação móvel multi-plataforma. Com os componentes criados, avaliaram-se os resultados obtidos com a nova arquitetura de forma a aferir a escalabilidade e performance da solução criada e sua adaptação ao sistema existente.

A distributed platform for the volunteer execution of workflows on a local area network

Thesis submitted in fulfilment of the requirements for the Degree of Master of Science in Computer Science

Development of polymer wicks for the fabrication of bio-medical sensors

Polymer based wicking structures were fabricated by sintering powders of polycarbonate (PC), ultra-high molecular weight polyethylene and polyamide 12, aiming at selecting a suitable material for an innovative electroencephalography (EEG) bio-electrode. Preliminary experiments showed that PC based wicks displayed the best mechanical properties, therefore more detailed studies were carried out with PC to evaluate the influence of powder granulometry and processing parameters (pressure, temperature and time) on the mechanical properties, porosity, mean pore radius and permeability of the wicks. It was concluded that the mechanical properties are significantly enhanced by increasing the processing time and pressure, although at the expense of a significant decrease of porosity and mean pore diameter (and thus permeability), particularly for the highest applied pressures (74kPa). However, a good compromise between porosity/permeability and mechanical properties could be obtained by sintering PC powders of particle sizes below 500μm at 165°C for 5min, upon an applied pressure of 56kPa. Moreover, PC proved to be chemically stable in contact with an EEG common used disinfectant. Thus, wicking structures with appropriate properties for the fabrication of reusable bio-electrodes could be fabricated from the sintering of PC powders.

Ultrasound enhances lipase-catalyzed synthesis of poly (ethylene glutarate)

The present work explores the best conditions for the enzymatic synthesis of poly (ethylene glutarate) for the first time. The start-up materials are the liquids; diethyl glutarate and ethylene glycol diacetate, without the need of addition of extra solvent. The reactions are catalyzed by lipase B from Candida antarctica immobilized on glycidyl methacrylate-ter-divinylbenzene-ter-ethylene glycol dimethacrylate at 40 °C during 18 h in water bath with mechanical stirring or 1 h in ultrasonic bath followed by 6 h in vacuum in both the cases for evaporation of ethyl acetate. The application of ultrasound significantly intensified the polyesterification reaction with reduction of the processing time from 24 to 7 h. The same degree of polymerization was obtained for the same enzyme loading in less time of reaction when using the ultrasound treatment. The degree of polymerization for long-term polyesterification was improved approximately 8-fold due to the presence of sonication during the reaction. The highest degree of polymerization achieved was 31, with a monomer conversion of 96.77%. The ultrasound treatment demonstrated to be an effective green approach to intensify the polyesterification reaction with enhanced initial kinetics and high degree of polymerization.

Flow-R, a model for susceptibility mapping of debris flows and other gravitational hazards at a regional scale

The development of susceptibility maps for debris flows is of primary importance due to population pressure in hazardous zones. However, hazard assessment by processbased modelling at a regional scale is difficult due to the complex nature of the phenomenon, the variability of local controlling factors, and the uncertainty in modelling parameters. A regional assessment must consider a simplified approach that is not highly parameter dependant and that can provide zonation with minimum data requirements. A distributed empirical model has thus been developed for regional susceptibility assessments using essentially a digital elevation model (DEM). The model is called Flow-R for Flow path assessment of gravitational hazards at a Regional scale (available free of charge under www.flow-r.org) and has been successfully applied to different case studies in various countries with variable data quality. It provides a substantial basis for a preliminary susceptibility assessment at a regional scale. The model was also found relevant to assess other natural hazards such as rockfall, snow avalanches and floods. The model allows for automatic source area delineation, given user criteria, and for the assessment of the propagation extent based on various spreading algorithms and simple frictional laws.We developed a new spreading algorithm, an improved version of Holmgren's direction algorithm, that is less sensitive to small variations of the DEM and that is avoiding over-channelization, and so produces more realistic extents. The choices of the datasets and the algorithms are open to the user, which makes it compliant for various applications and dataset availability. Amongst the possible datasets, the DEM is the only one that is really needed for both the source area delineation and the propagation assessment; its quality is of major importance for the results accuracy. We consider a 10m DEM resolution as a good compromise between processing time and quality of results. However, valuable results have still been obtained on the basis of lower quality DEMs with 25m resolution.

Beyond Smith's rule: An optimal dynamic index, rule for single machine stochastic scheduling with convex holding costs

Most research on single machine scheduling has assumedthe linearity of job holding costs, which is arguablynot appropriate in some applications. This motivates ourstudy of a model for scheduling $n$ classes of stochasticjobs on a single machine, with the objective of minimizingthe total expected holding cost (discounted or undiscounted). We allow general holding cost rates that are separable,nondecreasing and convex on the number of jobs in eachclass. We formulate the problem as a linear program overa certain greedoid polytope, and establish that it issolved optimally by a dynamic (priority) index rule,whichextends the classical Smith's rule (1956) for the linearcase. Unlike Smith's indices, defined for each class, ournew indices are defined for each extended class, consistingof a class and a number of jobs in that class, and yieldan optimal dynamic index rule: work at each time on a jobwhose current extended class has larger index. We furthershow that the indices possess a decomposition property,as they are computed separately for each class, andinterpret them in economic terms as marginal expected cost rate reductions per unit of expected processing time.We establish the results by deploying a methodology recentlyintroduced by us [J. Niño-Mora (1999). "Restless bandits,partial conservation laws, and indexability. "Forthcomingin Advances in Applied Probability Vol. 33 No. 1, 2001],based on the satisfaction by performance measures of partialconservation laws (PCL) (which extend the generalizedconservation laws of Bertsimas and Niño-Mora (1996)):PCL provide a polyhedral framework for establishing theoptimality of index policies with special structure inscheduling problems under admissible objectives, which weapply to the model of concern.

Bewertung des Risikos für Bias in kontrollierten Studien [Assessment of risk of bias in controlled studies].

BACKGROUND: Practicing physicians are faced with many medical decisions daily. These are mainly influenced by personal experience but should also consider patient preferences and the scientific evidence reflected by a constantly increasing number of medical publications and guidelines. With the objective of optimal medical treatment, the concept of evidence-based medicine is founded on these three aspects. It should be considered that there is a high risk of misinterpreting evidence, leading to medical errors and adverse effects without knowledge of the methodological background. OBJECTIVES: This article explains the concept of systematic error (bias) and its importance. Causes and effects as well as methods to minimize bias are discussed. This information should impart a deeper understanding, leading to a better assessment of studies and implementation of its recommendations in daily medical practice. CONCLUSION: Developed by the Cochrane Collaboration, the risk of bias (RoB) tool is an assessment instrument for the potential of bias in controlled trials. Good handling, short processing time, high transparency of judgements and a graphical presentation of findings that is easily comprehensible are among its strengths. Attached to this article the German translation of the RoB tool is published. This should facilitate the applicability for non-experts and moreover, support evidence-based medical decision-making.