Including context in a routing algorithm for the internet of things

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para obtenção do grau de Mestre em Engenharia Informática

Algorithm-oriented design of efficient many-core architectures applied to dense matrix multiplication

Recent integrated circuit technologies have opened the possibility to design parallel architectures with hundreds of cores on a single chip. The design space of these parallel architectures is huge with many architectural options. Exploring the design space gets even more difficult if, beyond performance and area, we also consider extra metrics like performance and area efficiency, where the designer tries to design the architecture with the best performance per chip area and the best sustainable performance. In this paper we present an algorithm-oriented approach to design a many-core architecture. Instead of doing the design space exploration of the many core architecture based on the experimental execution results of a particular benchmark of algorithms, our approach is to make a formal analysis of the algorithms considering the main architectural aspects and to determine how each particular architectural aspect is related to the performance of the architecture when running an algorithm or set of algorithms. The architectural aspects considered include the number of cores, the local memory available in each core, the communication bandwidth between the many-core architecture and the external memory and the memory hierarchy. To exemplify the approach we did a theoretical analysis of a dense matrix multiplication algorithm and determined an equation that relates the number of execution cycles with the architectural parameters. Based on this equation a many-core architecture has been designed. The results obtained indicate that a 100 mm(2) integrated circuit design of the proposed architecture, using a 65 nm technology, is able to achieve 464 GFLOPs (double precision floating-point) for a memory bandwidth of 16 GB/s. This corresponds to a performance efficiency of 71 %. Considering a 45 nm technology, a 100 mm(2) chip attains 833 GFLOPs which corresponds to 84 % of peak performance These figures are better than those obtained by previous many-core architectures, except for the area efficiency which is limited by the lower memory bandwidth considered. The results achieved are also better than those of previous state-of-the-art many-cores architectures designed specifically to achieve high performance for matrix multiplication.

Detect and pointing algorithm's performance for a planar smart antenna array: a review

An adaptive antenna array combines the signal of each element, using some constraints to produce the radiation pattern of the antenna, while maximizing the performance of the system. Direction of arrival (DOA) algorithms are applied to determine the directions of impinging signals, whereas beamforming techniques are employed to determine the appropriate weights for the array elements, to create the desired pattern. In this paper, a detailed analysis of both categories of algorithms is made, when a planar antenna array is used. Several simulation results show that it is possible to point an antenna array in a desired direction based on the DOA estimation and on the beamforming algorithms. A comparison of the performance in terms of runtime and accuracy of the used algorithms is made. These characteristics are dependent on the SNR of the incoming signal.

A physical packing sequence algorithm for the container loading problem with static mechanical equilibrium conditions

The container loading problem (CLP) is a combinatorial optimization problem for the spatial arrangement of cargo inside containers so as to maximize the usage of space. The algorithms for this problem are of limited practical applicability if real-world constraints are not considered, one of the most important of which is deemed to be stability. This paper addresses static stability, as opposed to dynamic stability, looking at the stability of the cargo during container loading. This paper proposes two algorithms. The first is a static stability algorithm based on static mechanical equilibrium conditions that can be used as a stability evaluation function embedded in CLP algorithms (e.g. constructive heuristics, metaheuristics). The second proposed algorithm is a physical packing sequence algorithm that, given a container loading arrangement, generates the actual sequence by which each box is placed inside the container, considering static stability and loading operation efficiency constraints.

NoC contention analysis using a branch-and-prune algorithm

“Many-core” systems based on a Network-on-Chip (NoC) architecture offer various opportunities in terms of performance and computing capabilities, but at the same time they pose many challenges for the deployment of real-time systems, which must fulfill specific timing requirements at runtime. It is therefore essential to identify, at design time, the parameters that have an impact on the execution time of the tasks deployed on these systems and the upper bounds on the other key parameters. The focus of this work is to determine an upper bound on the traversal time of a packet when it is transmitted over the NoC infrastructure. Towards this aim, we first identify and explore some limitations in the existing recursive-calculus-based approaches to compute the Worst-Case Traversal Time (WCTT) of a packet. Then, we extend the existing model by integrating the characteristics of the tasks that generate the packets. For this extended model, we propose an algorithm called “Branch and Prune” (BP). Our proposed method provides tighter and safe estimates than the existing recursive-calculus-based approaches. Finally, we introduce a more general approach, namely “Branch, Prune and Collapse” (BPC) which offers a configurable parameter that provides a flexible trade-off between the computational complexity and the tightness of the computed estimate. The recursive-calculus methods and BP present two special cases of BPC when a trade-off parameter is 1 or ∞, respectively. Through simulations, we analyze this trade-off, reason about the implications of certain choices, and also provide some case studies to observe the impact of task parameters on the WCTT estimates.

GPU implementation of a hyperspectral coded aperture algorithm for compressive sensing

This paper presents a new parallel implementation of a previously hyperspectral coded aperture (HYCA) algorithm for compressive sensing on graphics processing units (GPUs). HYCA method combines the ideas of spectral unmixing and compressive sensing exploiting the high spatial correlation that can be observed in the data and the generally low number of endmembers needed in order to explain the data. The proposed implementation exploits the GPU architecture at low level, thus taking full advantage of the computational power of GPUs using shared memory and coalesced accesses to memory. The proposed algorithm is evaluated not only in terms of reconstruction error but also in terms of computational performance using two different GPU architectures by NVIDIA: GeForce GTX 590 and GeForce GTX TITAN. Experimental results using real data reveals signficant speedups up with regards to serial implementation.

Step count algorithm adapted to indoor localization

This paper presents a step count algorithm designed to work in real-time using low computational power. This proposal is our first step for the development of an indoor navigation system, based on Pedestrian Dead Reckoning (PDR). We present two approaches to solve this problem and compare them based in their error on step counting, as well as, the capability of their use in a real time system.

Traveled Distance Estimation Algorithm for Indoor Localization

This paper presents an ankle mounted Inertial Navigation System (INS) used to estimate the distance traveled by a pedestrian. This distance is estimated by the number of steps given by the user. The proposed method is based on force sensors to enhance the results obtained from an INS. Experimental results have shown that, depending on the step frequency, the traveled distance error varies between 2.7% and 5.6%.

Hyperspectral unmixing algorithm via dependent component analysis

This paper introduces a new method to blindly unmix hyperspectral data, termed dependent component analysis (DECA). This method decomposes a hyperspectral images into a collection of reflectance (or radiance) spectra of the materials present in the scene (endmember signatures) and the corresponding abundance fractions at each pixel. DECA assumes that each pixel is a linear mixture of the endmembers signatures weighted by the correspondent abundance fractions. These abudances are modeled as mixtures of Dirichlet densities, thus enforcing the constraints on abundance fractions imposed by the acquisition process, namely non-negativity and constant sum. The mixing matrix is inferred by a generalized expectation-maximization (GEM) type algorithm. This method overcomes the limitations of unmixing methods based on Independent Component Analysis (ICA) and on geometrical based approaches. The effectiveness of the proposed method is illustrated using simulated data based on U.S.G.S. laboratory spectra and real hyperspectral data collected by the AVIRIS sensor over Cuprite, Nevada.

A lightweight distributed super peer election algorithm for unstructured dynamic P2P systems

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para obtenção do grau de Mestre em Engenharia Electrotécnica e de Computadores

Dot-ELISA for the detection of IgM and IgG antibodies to Schistosoma mansoni worm and egg antigens, associated with egg excretion by patients

Human schistosomiasis, caused by Schistosoma mansoni, is highly prevalent in Brazil and usually diagnosed by time consuming stool analysis. Serological tests are of limited use in this disease, mainly for epidemiological studies, showing no discrimination between previous contact with the parasite and active infections. In the present study, we standardized and compared a Dot-ELISA for IgM and IgG antibodies against S. mansoni antigens from eggs and worms with a routine IgG and IgM immunofluorescence assay using similar antigens, in the study of sera from 27 patients who had quantified egg stool excretion. The positivity obtained for IgG Dot-ELISA was 96.3% and 88.9% for IgM Dot-ELISA with worm antigen and 92.6% and 90.9% with egg antigen. The IFI presented similar positivities using worm antigen, 92.6% (IgG) and 96.3% (IgM),and lower results with egg antigen, 77.8% (IgG and IgM). The patients studied were divided into two groups according to their egg excretion, with greater positivity of serological tests in higher egg excreters. When comparing the quantitative egg excretion and the serological titers of the patients, we detected a correlation only with IgM Dot-ELISA, with r=0.552 (p=0.0127). These data show that Dot-ELISA can be used for the detection of specific antibodies against S. mansoni in sera from suspected patients or in epidemiological studies and, with further purification of egg antigen and larger samples, IgM Dot-ELISA could be a possible tool for rough estimates of parasite burden in epidemiological studies.

Evaluation of the enzyme-linked-immuno-electro-diffusion-assay (ELIEDA) for the diagnosis of Schistosoma mansoni infection with low worm burden

An immunoprecipitation technique, ELIEDA (enzyme-linked-immuno-electro-diffusion assay), was evaluated for the diagnosis of Schistosoma mansoni infection with low worm burden. One hundred of serum samples from patients excreting less than 600 eggs per gram of feces (epg), with unrelated diseases and clinically healthy subjects were studied. In patients with egg counts higher than 200 epg, the sensitivities of IgM and IgG ELIEDA were 1.000 and 0.923, respectively, not differing from other Serologic techniques, such as indirect hemaglutination (IHAT), immunofluorescence (IFT) tests and immuno-electrodiffusion assay (IEDA). However in patients with low egg counts (< 100 epg), the IgG ELIEDA provided better results (0.821) than IgM ELIEDA (0.679), showing sensitivity that did not differ from that of IgG IFT (0.929), but lower than that of IgM IFT (0.964). However, its sensivity was higher than that found with IHAT (0.607) and IEDA (0.536). The specificity of IgG ELIEDA was comparable to that of other techniques. The data indicate that IgG ELIEDA might be useful for the diagnosis of slight S. mansoni infections, and the cellulose acetate membrane strips can be stored for further retrospective studies.

Egg excretion in the initial phase of experimental murine schistosomiasis mansoni: stability and association with worm burden

Stability of faecal egg excretion and correlation with results related to worm burden at the initial phase of schistosomiasis mansoni were observed in two groups of mice infected with different Schistosoma mansoni cercarial burdens, by means of analysis of quantitative parasitological studies and schistosome counts after perfusion. Thus, it may be stated that few quantitative parasitological stool examinations could be sufficient to express the infection intensity at the initial phase, on the same grounds that it was already demonstrated at the chronic phase. Furthermore, it is confirmed that the use of the number of eggs passed in the faeces as a tool to estimate the worm burden at the initial phase of schistosome infection is adequate.

Domestic Consumption Simulation and Management Using a Continuous Consumption Management and Optimization Algorithm

The recent changes concerning the consumers’ active participation in the efficient management of load devices for one’s own interest and for the interest of the network operator, namely in the context of demand response, leads to the need for improved algorithms and tools. A continuous consumption optimization algorithm has been improved in order to better manage the shifted demand. It has been done in a simulation and user-interaction tool capable of being integrated in a multi-agent smart grid simulator already developed, and also capable of integrating several optimization algorithms to manage real and simulated loads. The case study of this paper enhances the advantages of the proposed algorithm and the benefits of using the developed simulation and user interaction tool.