Use of shared memory in the context of embedded multi-core processors: exploration of the technology and its limits

Modern embedded systems embrace many-core shared-memory designs. Due to constrained power and area budgets, most of them feature software-managed scratchpad memories instead of data caches to increase the data locality. It is therefore programmers’ responsibility to explicitly manage the memory transfers, and this make programming these platform cumbersome. Moreover, complex modern applications must be adequately parallelized before they can the parallel potential of the platform into actual performance. To support this, programming languages were proposed, which work at a high level of abstraction, and rely on a runtime whose cost hinders performance, especially in embedded systems, where resources and power budget are constrained. This dissertation explores the applicability of the shared-memory paradigm on modern many-core systems, focusing on the ease-of-programming. It focuses on OpenMP, the de-facto standard for shared memory programming. In a first part, the cost of algorithms for synchronization and data partitioning are analyzed, and they are adapted to modern embedded many-cores. Then, the original design of an OpenMP runtime library is presented, which supports complex forms of parallelism such as multi-level and irregular parallelism. In the second part of the thesis, the focus is on heterogeneous systems, where hardware accelerators are coupled to (many-)cores to implement key functional kernels with orders-of-magnitude of speedup and energy efficiency compared to the “pure software” version. However, three main issues rise, namely i) platform design complexity, ii) architectural scalability and iii) programmability. To tackle them, a template for a generic hardware processing unit (HWPU) is proposed, which share the memory banks with cores, and the template for a scalable architecture is shown, which integrates them through the shared-memory system. Then, a full software stack and toolchain are developed to support platform design and to let programmers exploiting the accelerators of the platform. The OpenMP frontend is extended to interact with it.

Effectiveness of abstract interpretation in automatic parallelization: a case study in logic programming

We report on a detailed study of the application and effectiveness of program analysis based on abstract interpretation to automatic program parallelization. We study the case of parallelizing logic programs using the notion of strict independence. We first propose and prove correct a methodology for the application in the parallelization task of the information inferred by abstract interpretation, using a parametric domain. The methodology is generic in the sense of allowing the use of different analysis domains. A number of well-known approximation domains are then studied and the transformation into the parametric domain defined. The transformation directly illustrates the relevance and applicability of each abstract domain for the application. Both local and global analyzers are then built using these domains and embedded in a complete parallelizing compiler. Then, the performance of the domains in this context is assessed through a number of experiments. A comparatively wide range of aspects is studied, from the resources needed by the analyzers in terms of time and memory to the actual benefits obtained from the information inferred. Such benefits are evaluated both in terms of the characteristics of the parallelized code and of the actual speedups obtained from it. The results show that data flow analysis plays an important role in achieving efficient parallelizations, and that the cost of such analysis can be reasonable even for quite sophisticated abstract domains. Furthermore, the results also offer significant insight into the characteristics of the domains, the demands of the application, and the trade-offs involved.

Hammer: an Android based application for end-user industrial robot programming

This paper presents a novel tablet based end-user interface for industrial robot programming (called Hammer). This application makes easier to program tasks for industrial robots like polishing, milling or grinding. It is based on the Scratch programming language, but specifically design and created for Android OS. It is a visual programming concept that allows non-skilled programmer operators to create programs. The application also allows to monitor the tasks while it is being executed by overlapping real time information through augmented reality. The application includes a teach pendant screen that can be customized according to the operator needs at every moment.

A framework for mixed-criticality partitioned real-time embedded systems

Los sistemas empotrados son cada día más comunes y complejos, de modo que encontrar procesos seguros, eficaces y baratos de desarrollo software dirigidos específicamente a esta clase de sistemas es más necesario que nunca. A diferencia de lo que ocurría hasta hace poco, en la actualidad los avances tecnológicos en el campo de los microprocesadores de los últimos tiempos permiten el desarrollo de equipos con prestaciones más que suficientes para ejecutar varios sistemas software en una única máquina. Además, hay sistemas empotrados con requisitos de seguridad (safety) de cuyo correcto funcionamiento depende la vida de muchas personas y/o grandes inversiones económicas. Estos sistemas software se diseñan e implementan de acuerdo con unos estándares de desarrollo software muy estrictos y exigentes. En algunos casos puede ser necesaria también la certificación del software. Para estos casos, los sistemas con criticidades mixtas pueden ser una alternativa muy valiosa. En esta clase de sistemas, aplicaciones con diferentes niveles de criticidad se ejecutan en el mismo computador. Sin embargo, a menudo es necesario certificar el sistema entero con el nivel de criticidad de la aplicación más crítica, lo que hace que los costes se disparen. La virtualización se ha postulado como una tecnología muy interesante para contener esos costes. Esta tecnología permite que un conjunto de máquinas virtuales o particiones ejecuten las aplicaciones con unos niveles de aislamiento tanto temporal como espacial muy altos. Esto, a su vez, permite que cada partición pueda ser certificada independientemente. Para el desarrollo de sistemas particionados con criticidades mixtas se necesita actualizar los modelos de desarrollo software tradicionales, pues estos no cubren ni las nuevas actividades ni los nuevos roles que se requieren en el desarrollo de estos sistemas. Por ejemplo, el integrador del sistema debe definir las particiones o el desarrollador de aplicaciones debe tener en cuenta las características de la partición donde su aplicación va a ejecutar. Tradicionalmente, en el desarrollo de sistemas empotrados, el modelo en V ha tenido una especial relevancia. Por ello, este modelo ha sido adaptado para tener en cuenta escenarios tales como el desarrollo en paralelo de aplicaciones o la incorporación de una nueva partición a un sistema ya existente. El objetivo de esta tesis doctoral es mejorar la tecnología actual de desarrollo de sistemas particionados con criticidades mixtas. Para ello, se ha diseñado e implementado un entorno dirigido específicamente a facilitar y mejorar los procesos de desarrollo de esta clase de sistemas. En concreto, se ha creado un algoritmo que genera el particionado del sistema automáticamente. En el entorno de desarrollo propuesto, se han integrado todas las actividades necesarias para desarrollo de un sistema particionado, incluidos los nuevos roles y actividades mencionados anteriormente. Además, el diseño del entorno de desarrollo se ha basado en la ingeniería guiada por modelos (Model-Driven Engineering), la cual promueve el uso de los modelos como elementos fundamentales en el proceso de desarrollo. Así pues, se proporcionan las herramientas necesarias para modelar y particionar el sistema, así como para validar los resultados y generar los artefactos necesarios para el compilado, construcción y despliegue del mismo. Además, en el diseño del entorno de desarrollo, la extensión e integración del mismo con herramientas de validación ha sido un factor clave. En concreto, se pueden incorporar al entorno de desarrollo nuevos requisitos no-funcionales, la generación de nuevos artefactos tales como documentación o diferentes lenguajes de programación, etc. Una parte clave del entorno de desarrollo es el algoritmo de particionado. Este algoritmo se ha diseñado para ser independiente de los requisitos de las aplicaciones así como para permitir al integrador del sistema implementar nuevos requisitos del sistema. Para lograr esta independencia, se han definido las restricciones al particionado. El algoritmo garantiza que dichas restricciones se cumplirán en el sistema particionado que resulte de su ejecución. Las restricciones al particionado se han diseñado con una capacidad expresiva suficiente para que, con un pequeño grupo de ellas, se puedan expresar la mayor parte de los requisitos no-funcionales más comunes. Las restricciones pueden ser definidas manualmente por el integrador del sistema o bien pueden ser generadas automáticamente por una herramienta a partir de los requisitos funcionales y no-funcionales de una aplicación. El algoritmo de particionado toma como entradas los modelos y las restricciones al particionado del sistema. Tras la ejecución y como resultado, se genera un modelo de despliegue en el que se definen las particiones que son necesarias para el particionado del sistema. A su vez, cada partición define qué aplicaciones deben ejecutar en ella así como los recursos que necesita la partición para ejecutar correctamente. El problema del particionado y las restricciones al particionado se modelan matemáticamente a través de grafos coloreados. En dichos grafos, un coloreado propio de los vértices representa un particionado del sistema correcto. El algoritmo se ha diseñado también para que, si es necesario, sea posible obtener particionados alternativos al inicialmente propuesto. El entorno de desarrollo, incluyendo el algoritmo de particionado, se ha probado con éxito en dos casos de uso industriales: el satélite UPMSat-2 y un demostrador del sistema de control de una turbina eólica. Además, el algoritmo se ha validado mediante la ejecución de numerosos escenarios sintéticos, incluyendo algunos muy complejos, de más de 500 aplicaciones. ABSTRACT The importance of embedded software is growing as it is required for a large number of systems. Devising cheap, efficient and reliable development processes for embedded systems is thus a notable challenge nowadays. Computer processing power is continuously increasing, and as a result, it is currently possible to integrate complex systems in a single processor, which was not feasible a few years ago.Embedded systems may have safety critical requirements. Its failure may result in personal or substantial economical loss. The development of these systems requires stringent development processes that are usually defined by suitable standards. In some cases their certification is also necessary. This scenario fosters the use of mixed-criticality systems in which applications of different criticality levels must coexist in a single system. In these cases, it is usually necessary to certify the whole system, including non-critical applications, which is costly. Virtualization emerges as an enabling technology used for dealing with this problem. The system is structured as a set of partitions, or virtual machines, that can be executed with temporal and spatial isolation. In this way, applications can be developed and certified independently. The development of MCPS (Mixed-Criticality Partitioned Systems) requires additional roles and activities that traditional systems do not require. The system integrator has to define system partitions. Application development has to consider the characteristics of the partition to which it is allocated. In addition, traditional software process models have to be adapted to this scenario. The V-model is commonly used in embedded systems development. It can be adapted to the development of MCPS by enabling the parallel development of applications or adding an additional partition to an existing system. The objective of this PhD is to improve the available technology for MCPS development by providing a framework tailored to the development of this type of system and by defining a flexible and efficient algorithm for automatically generating system partitionings. The goal of the framework is to integrate all the activities required for developing MCPS and to support the different roles involved in this process. The framework is based on MDE (Model-Driven Engineering), which emphasizes the use of models in the development process. The framework provides basic means for modeling the system, generating system partitions, validating the system and generating final artifacts. The framework has been designed to facilitate its extension and the integration of external validation tools. In particular, it can be extended by adding support for additional non-functional requirements and support for final artifacts, such as new programming languages or additional documentation. The framework includes a novel partitioning algorithm. It has been designed to be independent of the types of applications requirements and also to enable the system integrator to tailor the partitioning to the specific requirements of a system. This independence is achieved by defining partitioning constraints that must be met by the resulting partitioning. They have sufficient expressive capacity to state the most common constraints and can be defined manually by the system integrator or generated automatically based on functional and non-functional requirements of the applications. The partitioning algorithm uses system models and partitioning constraints as its inputs. It generates a deployment model that is composed by a set of partitions. Each partition is in turn composed of a set of allocated applications and assigned resources. The partitioning problem, including applications and constraints, is modeled as a colored graph. A valid partitioning is a proper vertex coloring. A specially designed algorithm generates this coloring and is able to provide alternative partitions if required. The framework, including the partitioning algorithm, has been successfully used in the development of two industrial use cases: the UPMSat-2 satellite and the control system of a wind-power turbine. The partitioning algorithm has been successfully validated by using a large number of synthetic loads, including complex scenarios with more that 500 applications.

Tools for embedded computing systems software.

"Preprint for a workshop sponsored by NASA Langley Research Center, Hampton, Virginia, and the American Institute of Aeronautics and Astronautics, New York, and held in Hampton, Virginia, November 7-8, 1978."

Mathematical Programming Models for Influence Maximization on Social Networks

In this dissertation, we apply mathematical programming techniques (i.e., integer programming and polyhedral combinatorics) to develop exact approaches for influence maximization on social networks. We study four combinatorial optimization problems that deal with maximizing influence at minimum cost over a social network. To our knowl- edge, all previous work to date involving influence maximization problems has focused on heuristics and approximation. We start with the following viral marketing problem that has attracted a significant amount of interest from the computer science literature. Given a social network, find a target set of customers to seed with a product. Then, a cascade will be caused by these initial adopters and other people start to adopt this product due to the influence they re- ceive from earlier adopters. The idea is to find the minimum cost that results in the entire network adopting the product. We first study a problem called the Weighted Target Set Selection (WTSS) Prob- lem. In the WTSS problem, the diffusion can take place over as many time periods as needed and a free product is given out to the individuals in the target set. Restricting the number of time periods that the diffusion takes place over to be one, we obtain a problem called the Positive Influence Dominating Set (PIDS) problem. Next, incorporating partial incentives, we consider a problem called the Least Cost Influence Problem (LCIP). The fourth problem studied is the One Time Period Least Cost Influence Problem (1TPLCIP) which is identical to the LCIP except that we restrict the number of time periods that the diffusion takes place over to be one. We apply a common research paradigm to each of these four problems. First, we work on special graphs: trees and cycles. Based on the insights we obtain from special graphs, we develop efficient methods for general graphs. On trees, first, we propose a polynomial time algorithm. More importantly, we present a tight and compact extended formulation. We also project the extended formulation onto the space of the natural vari- ables that gives the polytope on trees. Next, building upon the result for trees---we derive the polytope on cycles for the WTSS problem; as well as a polynomial time algorithm on cycles. This leads to our contribution on general graphs. For the WTSS problem and the LCIP, using the observation that the influence propagation network must be a directed acyclic graph (DAG), the strong formulation for trees can be embedded into a formulation on general graphs. We use this to design and implement a branch-and-cut approach for the WTSS problem and the LCIP. In our computational study, we are able to obtain high quality solutions for random graph instances with up to 10,000 nodes and 20,000 edges (40,000 arcs) within a reasonable amount of time.

Tori embedded in S³ with dense asymptotic lines

In this paper are given examples of tori T² embedded in S³ with all their asymptotic lines dense.

Embedded librarian: relato de uma experiência na Psicologia brasileira

O presente relato apresenta as principais atividades e desafios de um embedded librarian, ou bibliotecário integrado, junto aos diversos grupos envolvidos nos processos de comunicação científica e, mais especificamente, relacionados aos periódicos científicos da área de Psicologia. A existência de um bibliotecário integrado a esses grupos favoreceu a comunicação e interação entre eles e contribuiu também para a qualificação de um conjunto de periódicos científicos da área.

Electron dephasing scattering rate in two-dimensional GaAs/InGaAs heterostructures with embedded InAs quantum dots

We report a comprehensive study of weak-localization and electron-electron interaction effects in a GaAs/InGaAs two-dimensional electron system with nearby InAs quantum dots, using measurements of the electrical conductivity with and without magnetic field. Although both the effects introduce temperature dependent corrections to the zero magnetic field conductivity at low temperatures, the magnetic field dependence of conductivity is dominated by the weak-localization correction. We observed that the electron dephasing scattering rate tau(-1)(phi), obtained from the magnetoconductivity data, is enhanced by introducing quantum dots in the structure, as expected, and obeys a linear dependence on the temperature and elastic mean free path, which is against the Fermi-liquid model. (c) 2008 American Institute of Physics. [DOI: 10.1063/1.2996034]

Nonlinear diffraction of light beams propagating in photorefractive media with embedded reflecting wire

The theory of nonlinear diffraction of intensive light beams propagating through photorefractive media is developed. Diffraction occurs on a reflecting wire embedded in the nonlinear medium at a relatively small angle with respect to the direction of the beam propagation. It is shown that this process is analogous to the generation of waves by a flow of a superfluid past an obstacle. The ""equation of state"" of such a superfluid is determined by the nonlinear properties of the medium. On the basis of this hydrodynamic analogy, the notion of the ""Mach number"" is introduced where the transverse component of the wave vector plays the role of the fluid velocity. It is found that the Mach cone separates two regions of the diffraction pattern: inside the Mach cone oblique dark solitons are generated and outside the Mach cone the region of ""optical ship waves"" (the wave pattern formed by a two-dimensional packet of linear waves) is situated. Analytical theory of the ""optical ship waves"" is developed and two-dimensional dark soliton solutions of the generalized two-dimensional nonlinear Schrodinger equation describing the light beam propagation are found. Stability of dark solitons with respect to their decay into vortices is studied and it is shown that they are stable for large enough values of the Mach number.

A study of disorder effects in random (Al(x)Ga(1-x)As)(n)(Al(y)Ga(1-y)As)(m) superlattices embedded in a wide parabolic potential

A photoluminescence (PL) study of the individual electron states localized in a random potential is performed in artificially disordered superlattices embedded in a wide parabolic well. The valence band bowing of the parabolic potential provides a variation of the emission energies which splits the optical transitions corresponding to different wells within the random potential. The blueshift of the PL lines emitted by individual random wells, observed with increasing disorder strength, is demonstrated. The variation of temperature and magnetic field allowed for the behavior of the electrons localized in individual wells of the random potential to be distinguished.

Embedded DSP-Based Compact Fuzzy System and Its Application for Induction-Motor V/f Speed Control

This paper presents a compact embedded fuzzy system for three-phase induction-motor scalar speed control. The control strategy consists in keeping constant the voltage-frequency ratio of the induction-motor supply source. A fuzzy-control system is built on a digital signal processor, which uses speed error and speed-error variation to change both the fundamental voltage amplitude and frequency of a sinusoidal pulsewidth modulation inverter. An alternative optimized method for embedded fuzzy-system design is also proposed. The controller performance, in relation to reference and load-torque variations, is evaluated by experimental results. A comparative analysis with conventional proportional-integral controller is also achieved.

Modeling and analysis of laminate composite plates with embedded active-passive piezoelectric networks

The objective of this work is to present the finite element modeling of laminate composite plates with embedded piezoelectric patches or layers that are then connected to active-passive resonant shunt circuits, composed of resistance, inductance and voltage source. Applications to passive vibration control and active control authority enhancement are also presented and discussed. The finite element model is based on an equivalent single layer theory combined with a third-order shear deformation theory. A stress-voltage electromechanical model is considered for the piezoelectric materials fully coupled to the electrical circuits. To this end, the electrical circuit equations are also included in the variational formulation. Hence, conservation of charge and full electromechanical coupling are guaranteed. The formulation results in a coupled finite element model with mechanical (displacements) and electrical (charges at electrodes) degrees of freedom. For a Graphite-Epoxy (Carbon-Fibre Reinforced) laminate composite plate, a parametric analysis is performed to evaluate optimal locations along the plate plane (xy) and thickness (z) that maximize the effective modal electromechanical coupling coefficient. Then, the passive vibration control performance is evaluated for a network of optimally located shunted piezoelectric patches embedded in the plate, through the design of resistance and inductance values of each circuit, to reduce the vibration amplitude of the first four vibration modes. A vibration amplitude reduction of at least 10 dB for all vibration modes was observed. Then, an analysis of the control authority enhancement due to the resonant shunt circuit, when the piezoelectric patches are used as actuators, is performed. It is shown that the control authority can indeed be improved near a selected resonance even with multiple pairs of piezoelectric patches and active-passive circuits acting simultaneously. (C) 2010 Elsevier Ltd. All rights reserved.

Positioning of Deadeners for Vibration Reduction in Vehicle Roof Using Embedded Sensitivity

The noise, vibration and harshness (NVH) performance of passenger vehicles strongly depends on the fluid-structure interaction between the air in the vehicle cavity and the sheet metal structure of the vehicle. Most of the noise and vibration problems related to this interaction come from resonance peaks of the sheet metal, which are excited by external forces (road, engine, and wind). A reduction in these resonance peaks can be achieved by applying bitumen damping layers, also called deadeners, in the sheet metal. The problem is where these deadeners shall be fixed, which is usually done in a trial-and-error basis. In this work, one proposes the use of embedded sensitivity to locate the deadeners in the sheet metal of the vehicle, more specifically in the vehicle roof. Experimental frequency response functions (FRFs) of the roof are obtained and the data are processed by adopting the embedded sensitivity method, thus obtaining the sensitivity of the resonance peaks on the local increase in damping due to the deadeners. As a result, by examining the sensitivity functions, one can find the optimum location of the deadeners that maximize their effect in reducing the resonance peaks of interest. After locating the deadeners in the optimum positions, it was possible to verify a strong reduction in resonance peaks of the vehicle roof, thus showing the efficiency of the procedure. The main advantage of this procedure is that it only requires FRF measurements of the vehicle in its original state not needing any previous modification of the vehicle structure to find the sensitivity functions. [DOI: 10.1115/1.4000769]