Techniques for improving the inherent parallelism in programs /

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

Generic systolic array for genetic algorithms

The authors present a systolic design for a simple GA mechanism which provides high throughput and unidirectional pipelining by exploiting the inherent parallelism in the genetic operators. The design computes in O(N+G) time steps using O(N2) cells where N is the population size and G is the chromosome length. The area of the device is independent of the chromosome length and so can be easily scaled by replicating the arrays or by employing fine-grain migration. The array is generic in the sense that it does not rely on the fitness function and can be used as an accelerator for any GA application using uniform crossover between pairs of chromosomes. The design can also be used in hybrid systems as an add-on to complement existing designs and methods for fitness function acceleration and island-style population management

Sistema operacional e biblioteca de funções para plataformas MPSOC: um estudo de caso para simuladores de reservatórios

The increasingly request for processing power during last years has pushed integrated circuit industry to look for ways of providing even more processing power with less heat dissipation, power consumption, and chip area. This goal has been achieved increasing the circuit clock, but since there are physical limits of this approach a new solution emerged as the multiprocessor system on chip (MPSoC). This approach demands new tools and basic software infrastructure to take advantage of the inherent parallelism of these architectures. The oil exploration industry has one of its firsts activities the project decision on exploring oil fields, those decisions are aided by reservoir simulations demanding high processing power, the MPSoC may offer greater performance if its parallelism can be well used. This work presents a proposal of a micro-kernel operating system and auxiliary libraries aimed to the STORM MPSoC platform analyzing its influence on the problem of reservoir simulation

Speedup and scalability analysis of Master-Slave applications on large heterogeneous clusters

Although cluster environments have an enormous potential processing power, real applications that take advantage of this power remain an elusive goal. This is due, in part, to the lack of understanding about the characteristics of the applications best suited for these environments. This paper focuses on Master/Slave applications for large heterogeneous clusters. It defines application, cluster and execution models to derive an analytic expression for the execution time. It defines speedup and derives speedup bounds based on the inherent parallelism of the application and the aggregated computing power of the cluster. The paper derives an analytical expression for efficiency and uses it to define scalability of the algorithm-cluster combination based on the isoefficiency metric. Furthermore, the paper establishes necessary and sufficient conditions for an algorithm-cluster combination to be scalable which are easy to verify and use in practice. Finally, it covers the impact of network contention as the number of processors grow. (C) 2007 Elsevier B.V. All rights reserved.

Programmable logic design of a compact Genetic Algorithm for phasor estimation in real-time

The main objective of this work is to present an efficient method for phasor estimation based on a compact Genetic Algorithm (cGA) implemented in Field Programmable Gate Array (FPGA). To validate the proposed method, an Electrical Power System (EPS) simulated by the Alternative Transients Program (ATP) provides data to be used by the cGA. This data is as close as possible to the actual data provided by the EPS. Real life situations such as islanding, sudden load increase and permanent faults were considered. The implementation aims to take advantage of the inherent parallelism in Genetic Algorithms in a compact and optimized way, making them an attractive option for practical applications in real-time estimations concerning Phasor Measurement Units (PMUs).

Many-core Algorithms for Combinatorial Optimization

Combinatorial Optimization is becoming ever more crucial, in these days. From natural sciences to economics, passing through urban centers administration and personnel management, methodologies and algorithms with a strong theoretical background and a consolidated real-word effectiveness is more and more requested, in order to find, quickly, good solutions to complex strategical problems. Resource optimization is, nowadays, a fundamental ground for building the basements of successful projects. From the theoretical point of view, Combinatorial Optimization rests on stable and strong foundations, that allow researchers to face ever more challenging problems. However, from the application point of view, it seems that the rate of theoretical developments cannot cope with that enjoyed by modern hardware technologies, especially with reference to the one of processors industry. In this work we propose new parallel algorithms, designed for exploiting the new parallel architectures available on the market. We found that, exposing the inherent parallelism of some resolution techniques (like Dynamic Programming), the computational benefits are remarkable, lowering the execution times by more than an order of magnitude, and allowing to address instances with dimensions not possible before. We approached four Combinatorial Optimization’s notable problems: Packing Problem, Vehicle Routing Problem, Single Source Shortest Path Problem and a Network Design problem. For each of these problems we propose a collection of effective parallel solution algorithms, either for solving the full problem (Guillotine Cuts and SSSPP) or for enhancing a fundamental part of the solution method (VRP and ND). We endorse our claim by presenting computational results for all problems, either on standard benchmarks from the literature or, when possible, on data from real-world applications, where speed-ups of one order of magnitude are usually attained, not uncommonly scaling up to 40 X factors.

MEIA SYSTEMS: Membrane Encrypted Information Applications Systems

Membrane computing is a recent area that belongs to natural computing. This field works on computational models based on nature's behavior to process the information. Recently, numerous models have been developed and implemented with this purpose. P-systems are the structures which have been defined,developed and implemented to simulate the behavior and the evolution of membrane systems which we find in nature. What we show in this paper is a new model that deals with encrypted information which provides security the membrane systems communication. Moreover we find non deterministic and random applications in nature that are suitable to MEIA systems. The inherent parallelism and non determinism make this applications perfect object to implement MEIA systems.

Distributed Estimation of Distribution Algorithms for continuous optimization: how does the exchanged information influence their behavior?

One of the most promising areas in which probabilistic graphical models have shown an incipient activity is the field of heuristic optimization and, in particular, in Estimation of Distribution Algorithms. Due to their inherent parallelism, different research lines have been studied trying to improve Estimation of Distribution Algorithms from the point of view of execution time and/or accuracy. Among these proposals, we focus on the so-called distributed or island-based models. This approach defines several islands (algorithms instances) running independently and exchanging information with a given frequency. The information sent by the islands can be either a set of individuals or a probabilistic model. This paper presents a comparative study for a distributed univariate Estimation of Distribution Algorithm and a multivariate version, paying special attention to the comparison of two alternative methods for exchanging information, over a wide set of parameters and problems ? the standard benchmark developed for the IEEE Workshop on Evolutionary Algorithms and other Metaheuristics for Continuous Optimization Problems of the ISDA 2009 Conference. Several analyses from different points of view have been conducted to analyze both the influence of the parameters and the relationships between them including a characterization of the configurations according to their behavior on the proposed benchmark.

Securing implementations of feedback-shift-register-based ciphers using compiler optimizations and co-processors

Los algoritmos basados en registros de desplazamiento con realimentación (en inglés FSR) se han utilizado como generadores de flujos pseudoaleatorios en aplicaciones con recursos limitados como los sistemas de apertura sin llave. Se considera canal primario a aquel que se utiliza para realizar una transmisión de información. La aparición de los ataques de canal auxiliar (en inglés SCA), que explotan información filtrada inintencionadamente a través de canales laterales como el consumo, las emisiones electromagnéticas o el tiempo empleado, supone una grave amenaza para estas aplicaciones, dado que los dispositivos son accesibles por un atacante. El objetivo de esta tesis es proporcionar un conjunto de protecciones que se puedan aplicar de forma automática y que utilicen recursos ya disponibles, evitando un incremento sustancial en los costes y alargando la vida útil de aplicaciones que puedan estar desplegadas. Explotamos el paralelismo existente en algoritmos FSR, ya que sólo hay 1 bit de diferencia entre estados de rondas consecutivas. Realizamos aportaciones en tres niveles: a nivel de sistema, utilizando un coprocesador reconfigurable, a través del compilador y a nivel de bit, aprovechando los recursos disponibles en el procesador. Proponemos un marco de trabajo que nos permite evaluar implementaciones de un algoritmo incluyendo los efectos introducidos por el compilador considerando que el atacante es experto. En el campo de los ataques, hemos propuesto un nuevo ataque diferencial que se adapta mejor a las condiciones de las implementaciones software de FSR, en las que el consumo entre rondas es muy similar. SORU2 es un co-procesador vectorial reconfigurable propuesto para reducir el consumo energético en aplicaciones con paralelismo y basadas en el uso de bucles. Proponemos el uso de SORU2, además, para ejecutar algoritmos basados en FSR de forma segura. Al ser reconfigurable, no supone un sobrecoste en recursos, ya que no está dedicado en exclusiva al algoritmo de cifrado. Proponemos una configuración que ejecuta múltiples algoritmos de cifrado similares de forma simultánea, con distintas implementaciones y claves. A partir de una implementación sin protecciones, que demostramos que es completamente vulnerable ante SCA, obtenemos una implementación segura a los ataques que hemos realizado. A nivel de compilador, proponemos un mecanismo para evaluar los efectos de las secuencias de optimización del compilador sobre una implementación. El número de posibles secuencias de optimizaciones de compilador es extremadamente alto. El marco de trabajo propuesto incluye un algoritmo para la selección de las secuencias de optimización a considerar. Debido a que las optimizaciones del compilador transforman las implementaciones, se pueden generar automáticamente implementaciones diferentes combinamos para incrementar la seguridad ante SCA. Proponemos 2 mecanismos de aplicación de estas contramedidas, que aumentan la seguridad de la implementación original sin poder considerarse seguras. Finalmente hemos propuesto la ejecución paralela a nivel de bit del algoritmo en un procesador. Utilizamos la forma algebraica normal del algoritmo, que automáticamente se paraleliza. La implementación sobre el algoritmo evaluado mejora en rendimiento y evita que se filtre información por una ejecución dependiente de datos. Sin embargo, es más vulnerable ante ataques diferenciales que la implementación original. Proponemos una modificación del algoritmo para obtener una implementación segura, descartando parcialmente ejecuciones del algoritmo, de forma aleatoria. Esta implementación no introduce una sobrecarga en rendimiento comparada con las implementaciones originales. En definitiva, hemos propuesto varios mecanismos originales a distintos niveles para introducir aleatoridad en implementaciones de algoritmos FSR sin incrementar sustancialmente los recursos necesarios. ABSTRACT Feedback Shift Registers (FSR) have been traditionally used to implement pseudorandom sequence generators. These generators are used in Stream ciphers in systems with tight resource constraints, such as Remote Keyless Entry. When communicating electronic devices, the primary channel is the one used to transmit the information. Side-Channel Attack (SCA) use additional information leaking from the actual implementation, including power consumption, electromagnetic emissions or timing information. Side-Channel Attacks (SCA) are a serious threat to FSR-based applications, as an attacker usually has physical access to the devices. The main objective of this Ph.D. thesis is to provide a set of countermeasures that can be applied automatically using the available resources, avoiding a significant cost overhead and extending the useful life of deployed systems. If possible, we propose to take advantage of the inherent parallelism of FSR-based algorithms, as the state of a FSR differs from previous values only in 1-bit. We have contributed in three different levels: architecture (using a reconfigurable co-processor), using compiler optimizations, and at bit level, making the most of the resources available at the processor. We have developed a framework to evaluate implementations of an algorithm including the effects introduced by the compiler. We consider the presence of an expert attacker with great knowledge on the application and the device. Regarding SCA, we have presented a new differential SCA that performs better than traditional SCA on software FSR-based algorithms, where the leaked values are similar between rounds. SORU2 is a reconfigurable vector co-processor. It has been developed to reduce energy consumption in loop-based applications with parallelism. In addition, we propose its use for secure implementations of FSR-based algorithms. The cost overhead is discarded as the co-processor is not exclusively dedicated to the encryption algorithm. We present a co-processor configuration that executes multiple simultaneous encryptions, using different implementations and keys. From a basic implementation, which is proved to be vulnerable to SCA, we obtain an implementation where the SCA applied were unsuccessful. At compiler level, we use the framework to evaluate the effect of sequences of compiler optimization passes on a software implementation. There are many optimization passes available. The optimization sequences are combinations of the available passes. The amount of sequences is extremely high. The framework includes an algorithm for the selection of interesting sequences that require detailed evaluation. As existing compiler optimizations transform the software implementation, using different optimization sequences we can automatically generate different implementations. We propose to randomly switch between the generated implementations to increase the resistance against SCA.We propose two countermeasures. The results show that, although they increase the resistance against SCA, the resulting implementations are not secure. At bit level, we propose to exploit bit level parallelism of FSR-based implementations using pseudo bitslice implementation in a wireless node processor. The bitslice implementation is automatically obtained from the Algebraic Normal Form of the algorithm. The results show a performance improvement, avoiding timing information leakage, but increasing the vulnerability against differential SCA.We provide a secure version of the algorithm by randomly discarding part of the data obtained. The overhead in performance is negligible when compared to the original implementations. To summarize, we have proposed a set of original countermeasures at different levels that introduce randomness in FSR-based algorithms avoiding a heavy overhead on the resources required.

Bird responses at inherent and induced edges in the Murray Mallee, South Australia. 1. Differences in abundance and diversity

We quantified differences in the abundance and diversity of bird species at inherent (naturally occurring) and induced (human-created) edges in the Murray Mallee, South Australia, to explore the effects of anthropogenic landscape modification. Bird species were classified into edge response categories based on numerical differences in abundance between the edge and interior of habitat patches. 'Open-country' species (e.g. Australian Magpie and Little Raven) increased in abundance near induced edges, but were rarely recorded > 200 m into patch interiors or at inherent edges. The Australian Ringneck, Red Wattlebird, Spiny-cheeked Honeyeater, Singing Honeyeater and White-eared Honeyeater increased in abundance near each inherent edge and were classified as 'edge-users'. However, their responses at induced edges varied between sites. The Yellow-plumed Honeyeater, Spotted Pardalote, White-browed Babbler, Chestnut Quail-thrush and Southern Scrub-robin decreased in abundance near one or more induced edges and were classified as 'edge-avoiders' at these sites. The Yellow-plumed Honeyeater, Spotted Pardalote, Chestnut Quail-thrush and Southern Scrub-robin are considered mallee habitat specialists in eastern Australia. These species may be particularly affected by anthropogenic modification of mallee vegetation.

Bird responses at inherent and induced edges in the Murray Mallee, South Australia. 2. Nest predation as an edge effect

We assayed nest predation as an edge effect, using artificial ground nests, at inherent (naturally occurring) and induced (human-created) edges, in the Murray Mallee, South Australia. Nests were constructed at distances between 0-120 m away from habitat edges. The relative predation rate on nests generally increased close to induced edges with a significant difference (P < 0.05) recorded for two out of five experiments. Predation rate at inherent edges was similar from the edge to the interior, and was lower than that recorded at induced edges. Our results suggest that increased predator numbers, activity or efficiency at locating nests occurred close to the induced edges at our study sites.

Plasma nitrate/nitrite (NOx) is not a useful biomarker to predict inherent cardiopulmonary bypass inflammatory response

Background and Aim: There were strong evidences that nitric oxide has capital importance in the progressive vasodilatation associated with varied circulatory shock forms, including systemic inflammatory response syndrome (SIRS), in patients undergoing cardiac surgeries for cardiopulmonary bypass (CPB). If CPB procedures, per se, are the inciting stimulus for inflammation, plasma nitrate/nitrite (NOx) excretion would be expected to be higher in these patients rather than in patients operated without CPB. In consequence, we hypothesized that increased levels of NOx would be predictive for vasoplegic syndrome. Methods: Thirty patients were assigned to three groups: Group 1-coronary artery bypass graft (CABG) roller pump CPB; Group 2-CABG centrifugal vortex pump CPB; and Group 3-heart valve surgery roller pump CPB. Sampling of venous blood for chemiluminescence plasma NOx dosage was achieved at the following time points: (1) before anesthesia induction; (2) after anesthesia induction; (3) before heparin infusion; (4) after heparin infusion; (5) CPB-30 minutes; (6) CPB-60 minutes; (7) before protamine infusion; (8) after protamine infusion; and (9) on return to the recovery area. Results: There were no intergroup differences regarding age and anesthetic regimen, and the number of arteries grafted was not different between the CABG groups. There were no NOx statistic differences, neither among the three groups of patients or among the surgery time. In addition, there was no correlation among NOx, lactate, and hemoglobin. Conclusions: Considering the inflammatory process intrinsic to CPB, this study reinforces the idea that plasma NOx is not useful as a biomarker of inflammatory response onset, which may or may not lead to SIRS and/or vasoplegic syndrome.

Increased arterial stiffness in nonobese women with polycystic ovary syndrome (PCOS) without comorbidities: one more characteristic inherent to the syndrome?

Background Polycystic ovary syndrome (PCOS) is associated with adverse metabolic effects. Some cardiovascular disease (CVD) risk markers are increased in women with PCOS. However, early markers of atherosclerosis are also associated with obesity and insulin resistance, which are related to PCOS. These markers may result either directly from PCOS or indirectly as a consequence of the comorbidities associated with the syndrome. Context To assess the presence of early CVD markers in young, nonobese women with PCOS. Patients Forty women with PCOS and 50 healthy women with regular menstrual cycles, matched for age and body mass index (BMI). Measurements The following CVD markers were assessed by ultrasonography: common carotid artery (CCA) stiffness index (beta), distensibility and intima-media thickness (IMT), and brachial artery flow-mediated dilatation (FMD). Inflammatory markers, including interleukin (IL)-6, tumour necrosis factor (TNF)-alpha, homocysteine, C-reactive protein (CRP), glycaemia, lipid profile and insulin, were also assessed. Results CCA beta was higher in PCOS than in control women (3 center dot 72 +/- 0 center dot 96 vs. 3 center dot 36 +/- 0 center dot 96, P = 0 center dot 04) and CCA distensibility was lower (0 center dot 31 +/- 0 center dot 08 vs. 0 center dot 35 +/- 0 center dot 09 mmHg(-1), P = 0 center dot 02). Waist circumference, total testosterone and the Free Androgen Index (FAI) were higher in PCOS patients than in controls (78 center dot 2 +/- 10 center dot 0 vs. 71 center dot 5 +/- 7 center dot 2 cm, P = 0 center dot 001; 88 center dot 1 +/- 32 center dot 4 vs. 57 center dot 1 +/- 21 center dot 2 ng/dl, P < 0 center dot 01; 12 center dot 7 +/- 15 center dot 7%vs. 4 center dot 7 +/- 2 center dot 3%, P < 0 center dot 01, respectively), while SHBG was reduced (37 center dot 9 +/- 19 center dot 1 vs. 47 center dot 8 +/- 18 center dot 3 nmol/l, P = 0 center dot 01). The remaining variables did not differ between the groups. Conclusions Young women with PCOS exhibit changes in vascular elasticity even in the absence of classical risk factors for CVD, such as hypertension and obesity.

Influence of root parallelism on the stability of extraction-site closures

Introduction: In premolar extraction cases, root parallelism is recommended to preserve the stability of space closures. The influence of the degree of root parallelism on relapse of tooth extraction spaces has been a controversial topic in the literature. The aim of this study was to compare the angle between the long axes of the canine and the second premolarin patients with and without stability of extraction-space closures. Methods: A sample of 56 patients, treated with 4 premolar extractions, was divided into 2 groups: group 1, consisting of 25 patients with reopening of extraction spaces; and group 2, consisting of 31 patients without reopening of extraction spaces. Panoramic radiographs of each patient were analyzed at the posttreatment and 1-year posttreatment stages. The data were statistically analyzed by using chi-square tests, t tests, analysis of variance (ANOVA), and Pearson correlation coefficients. Results: The results showed that the groups did not differ regarding the angle between the canine and the second premolar, and there was no correlation between angular changes and reopening of extraction spaces, showing that dental angular changes are not determining factors for relapse, and other factors should be investigated. Conclusions: The final angle and the posttreatment changes observed in the angle between the long axes of the canine and the second premolar showed no influence on the relapse of extraction spaces. (Am J Orthod Dentofacial Orthop 2011; 139: e505-e510)