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 novel colorimetric assay of beta-D-glucans in basidiomycete strains by alcian blue dye in a 96-well microtiter plate

Basidiomycete strains synthesize several types of beta-D-glucans, which play a major role in the medicinal properties of mushrooms. Therefore, the specific quantification of these beta-D-glucans in mushroom strains is of great biochemical importance. Because published assay methods for these beta-D-glucans present some disadvantages, a novel colorimetric assay method for beta-D-glucan with alcian blue dye was developed. The complex formation was detected by following the decrease in absorbance in the range of 620 nm and by hypsochromic shift from 620 to 606 nm (similar to 14 nm) in UV-Vis spectrophotometer. Analysis of variance was used for optimization of the slope of the calibration curve by using the assay mixture containing 0.017% (w/v) alcian blue in 2% (v/v) acetic acid at pH 3.0. The high-throughput colorimetric assay method on microtiter plates was used for quantification of beta-D-glucans in the range of 0-0.8 mu g, with a slope of 44.15 x 10(-2) and a limit of detection of 0.017 mu g/well. Recovery experiments were carried out by using a sample of Hericium erinaceus, which exhibited a recovery of 95.8% for beta-1,3-D-glucan. The present assay method exhibited a 10-fold higher sensitivity and a 59-fold lower limit of detection compared with the published method with congo red beta-D-glucans of several mushrooms strains were isolated from fruiting bodies and mycelia, and they were quantified by this assay method. This assay method is fast, specific, simple, and it can be used to quantify beta-D-glucans from other biological sources. (C) 2015 American Institute of Chemical Engineers

The key role of coligands in novel ruthenium(II)-cyclopentadienyl bipyridine derivatives: Ranging from non-cytotoxic to highly cytotoxic compounds

A new family of eight ruthenium(II)-cyclopentadienyl bipyridine derivatives, bearing nitrogen, sulfur, phosphorous and carbonyl sigma bonded coligands, has been synthesized. Compounds bearing nitrogen bonded coligands were found to be unstable in aqueous solution, while the others presented appropriate stabilities for the biologic assays and pursued for determination of IC50 values in ovarian (A2780) and breast (MCF7 and MDAMB231) human cancer cell lines. These studies were also carried out for the [5: HSA] and [6: HSA] adducts (HSA = human serum albumin) and a better performance was found for the first case. Spectroscopic, electrochemical studies by cyclic voltammetry and density functional theory calculations allowed us to get some understanding on the electronic flow directions within the molecules and to find a possible clue concerning the structural features of coligands that can activate bipyridyl ligands toward an increased cytotoxic effect. X-ray structure analysis of compound [Ru(eta(5)-C5H5)(bipy)(PPh3)][PF6] (7; bipy = bipyridine) showed crystallization on C2/c space group with two enantiomers of the [Ru(eta(5)-C5H5)(bipy)(PPh3)](+) cation complex in the racemic crystal packing. (C) 2015 Elsevier Inc All rights reserved.

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.

Race-to-halt energy saving strategies

Energy consumption is one of the major issues for modern embedded systems. Early, power saving approaches mainly focused on dynamic power dissipation, while neglecting the static (leakage) energy consumption. However, technology improvements resulted in a case where static power dissipation increasingly dominates. Addressing this issue, hardware vendors have equipped modern processors with several sleep states. We propose a set of leakage-aware energy management approaches that reduce the energy consumption of embedded real-time systems while respecting the real-time constraints. Our algorithms are based on the race-to-halt strategy that tends to run the system at top speed with an aim to create long idle intervals, which are used to deploy a sleep state. The effectiveness of our algorithms is illustrated with an extensive set of simulations that show an improvement of up to 8% reduction in energy consumption over existing work at high utilization. The complexity of our algorithms is smaller when compared to state-of-the-art algorithms. We also eliminate assumptions made in the related work that restrict the practical application of the respective algorithms. Moreover, a novel study about the relation between the use of sleep intervals and the number of pre-emptions is also presented utilizing a large set of simulation results, where our algorithms reduce the experienced number of pre-emptions in all cases. Our results show that sleep states in general can save up to 30% of the overall number of pre-emptions when compared to the sleep-agnostic earliest-deadline-first algorithm.

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.

The key role of coligands in novel ruthenium(II)-cyclopentadienyl bipyridine derivatives: ranging from non-cytotoxic to highly cytotoxic compounds

A new family of eight ruthenium(II)-cyclopentadienyl bipyridine derivatives, bearing nitrogen, sulfur, phosphorous and carbonyl sigma bonded coligands, has been synthesized. Compounds bearing nitrogen bonded coligands were found to be unstable in aqueous solution, while the others presented appropriate stabilities for the biologic assays and pursued for determination of IC50 values in ovarian (A2780) and breast (MCF7 and MDAMB231) human cancer cell lines. These studies were also carried out for the [5: HSA] and [6: HSA] adducts (HSA=human serum albumin) and a better performance was found for the first case. Spectroscopic, electrochemical studies by cyclic voltammetry and density functional theory calculations allowed us to get some understanding on the electronic flow directions within the molecules and to find a possible clue concerning the structural features of coligands that can activate bipyridyl ligands toward an increased cytotoxic effect. X-ray structure analysis of compound [Ru(η(5)-C5H5)(bipy)(PPh3)][PF6] (7; bipy=bipyridine) showed crystallization on C2/c space group with two enantiomers of the [Ru(η(5)-C5H5)(bipy)(PPh3)](+) cation complex in the racemic crystal packing.

Time-domain optimization of amplifiers based on distributed genetic algorithms

Thesis presented in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the subject of Electrical and Computer Engineering

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%.

Novel coordination polymers with (Pyrazolato)-based tectons: catalytic activity in the peroxidative oxidation of alcohols and cyclohexane

Coupling five rigid or flexible bis(pyrazolato)based tectons with late transition metal ions allowed us to isolate 18 coordination polymers (CPs). As assessed by thermal analysis, all of them possess a remarkable thermal stability, their decomposition temperatures lying in the range of 340-500 degrees C. As demonstrated by N-2 adsorption measurements at 77 K, their Langmuir specific surface areas span the rather vast range of 135-1758 m(2)/g, in agreement with the porous or dense polymeric architectures retrieved by powder X-ray diffraction structure solution methods. Two representative families of CPs, built up with either rigid or flexible spacers, were tested as catalysts in (0 the microwave-assisted solvent-free peroxidative oxidation of alcohols by t-BuOOH, and (ii) the peroxidative oxidation of cydohexane to cydohexanol and cydohexanone by H2O2 in acetonitrile. Those CPs bearing the rigid spacer, concurrently possessing higher specific surface areas, are more active than the corresponding ones with the flexible spacer. Moreover, the two copper(I)-containing CPs investigated exhibit the highest efficiency in both reactions, leading selectively to a maximum product yield of 92% (and TON up to 1.5 x 10(3)) in the oxidation of 1-phenylethanol and of 11% in the oxidation of cydohexane, the latter value being higher than that granted by the current industrial process.

Unravelling novel modes of antimicrobial action

Dissertation presented to obtain the Ph.D. degree in Biochemistry at the Instituto de Tecnologia Química e Biológica, Universidade Nova de Lisboa