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.

Pedestrian Motion Prediction: A Graph Based Approach

A novel pedestrian motion prediction technique is presented in this paper. Its main achievement regards to none previous observation, any knowledge of pedestrian trajectories nor the existence of possible destinations is required; hence making it useful for autonomous surveillance applications. Prediction only requires initial position of the pedestrian and a 2D representation of the scenario as occupancy grid. First, it uses the Fast Marching Method (FMM) to calculate the pedestrian arrival time for each position in the map and then, the likelihood that the pedestrian reaches those positions is estimated. The technique has been tested with synthetic and real scenarios. In all cases, accurate probability maps as well as their representative graphs were obtained with low computational cost.

Sucrose is a signal molecule in assimilate partitioning

The proton–sucrose symporter mediates the key transport step in the resource distribution system that allows many plants to function as multicellular organisms. In the results reported here, we identify sucrose as a signaling molecule in a previously undescribed signal-transduction pathway that regulates the symporter. Sucrose symporter activity declined in plasma membrane vesicles isolated from leaves fed exogenous sucrose via the xylem transpiration stream. Symporter activity dropped to 35–50% of water controls when the leaves were fed 100 mM sucrose and to 20–25% of controls with 250 mM sucrose. In contrast, alanine symporter and glucose transporter activities did not change in response to sucrose treatments. Decreased sucrose symporter activity was detectable after 8 h and reached a maximum by 24 h. Kinetic analysis of transport activity showed a decrease in Vmax. RNA gel blot analysis revealed a decrease in symporter message levels, suggesting a drop in transcriptional activity or a decrease in mRNA stability. Control experiments showed that these responses were not the result of changing osmotic conditions. Equal molar concentrations of hexoses did not elicit the response, and mannoheptulose, a hexokinase inhibitor, did not block the sucrose effect. These data are consistent with a sucrose-specific response pathway that is not mediated by hexokinase as the sugar sensor. Sucrose-dependent changes in the sucrose symporter were reversible, suggesting this sucrose-sensing pathway can modulate transport activity as a function of changing sucrose concentrations in the leaf. These results demonstrate the existence of a signaling pathway that can control assimilate partitioning at the level of phloem translocation.

The Yeast Dynactin Complex Is Involved in Partitioning the Mitotic Spindle between Mother and Daughter Cells during Anaphase B

Although vertebrate cytoplasmic dynein can move to the minus ends of microtubules in vitro, its ability to translocate purified vesicles on microtubules depends on the presence of an accessory complex known as dynactin. We have cloned and characterized a novel gene, NIP100, which encodes the yeast homologue of the vertebrate dynactin complex protein p150glued. Like strains lacking the cytoplasmic dynein heavy chain Dyn1p or the centractin homologue Act5p, nip100Δ strains are viable but undergo a significant number of failed mitoses in which the mitotic spindle does not properly partition into the daughter cell. Analysis of spindle dynamics by time-lapse digital microscopy indicates that the precise role of Nip100p during anaphase is to promote the translocation of the partially elongated mitotic spindle through the bud neck. Consistent with the presence of a true dynactin complex in yeast, Nip100p exists in a stable complex with Act5p as well as Jnm1p, another protein required for proper spindle partitioning during anaphase. Moreover, genetic depletion experiments indicate that the binding of Nip100p to Act5p is dependent on the presence of Jnm1p. Finally, we find that a fusion of Nip100p to the green fluorescent protein localizes to the spindle poles throughout the cell cycle. Taken together, these results suggest that the yeast dynactin complex and cytoplasmic dynein together define a physiological pathway that is responsible for spindle translocation late in anaphase.

Raft-partitioning of the ubiquitin ligases Cbl and Nedd4 upon IgE-triggered cell signaling

The high affinity receptor for IgE, FcɛRI on mast cells and basophils plays an essential role in immunological defense. Upon multivalent antigen binding, FcɛRI becomes phoshorylated by the protein-tyrosine kinase Lyn, as a result of receptor clustering in lipid rafts. FcɛRI has been shown to be ubiquitinated. Ubiquitination can lead to degradation by proteasomes, but it can also act as a sorting signal to internalize proteins destined to the endosomal/lysosomal pathway. We have analyzed whether FcɛRI ubiquitination takes place within rafts. We report biochemical and imaging evidence in rat basoleukemia cells for the presence of ubiquitinated FcɛRI in clustered rafts upon receptor activation. Moreover, we demonstrated that the ubiquitin ligases Cbl and Nedd4 colocalize with FcɛRI patches and showed that both ligases become associated with lipid rafts after activation of IgE signaling. Because Cbl is known to interact with the FcɛRI signaling complex, ubiquitination is likely to be an important parameter regulating IgE-triggered signaling occurring in rafts.

Modification of Carbon Partitioning, Photosynthetic Capacity, and O2 Sensitivity in Arabidopsis Plants with Low ADP-Glucose Pyrophosphorylase Activity1

Wild-type Arabidopsis plants, the starch-deficient mutant TL46, and the near-starchless mutant TL25 were evaluated by noninvasive in situ methods for their capacity for net CO2 assimilation, true rates of photosynthetic O2 evolution (determined from chlorophyll fluorescence measurements of photosystem II), partitioning of photosynthate into sucrose and starch, and plant growth. Compared with wild-type plants, the starch mutants showed reduced photosynthetic capacity, with the largest reduction occurring in mutant TL25 subjected to high light and increased CO2 partial pressure. The extent of stimulation of CO2 assimilation by increasing CO2 or by reducing O2 partial pressure was significantly less for the starch mutants than for wild-type plants. Under high light and moderate to high levels of CO2, the rates of CO2 assimilation and O2 evolution and the percentage inhibition of photosynthesis by low O2 were higher for the wild type than for the mutants. The relative rates of 14CO2 incorporation into starch under high light and high CO2 followed the patterns of photosynthetic capacity, with TL46 showing 31% to 40% of the starch-labeling rates of the wild type and TL25 showing less than 14% incorporation. Overall, there were significant correlations between the rates of starch synthesis and CO2 assimilation and between the rates of starch synthesis and cumulative leaf area. These results indicate that leaf starch plays an important role as a transient reserve, the synthesis of which can ameliorate any potential reduction in photosynthesis caused by feedback regulation.

Recursive partitioning for tumor classification with gene expression microarray data

Precise classification of tumors is critically important for cancer diagnosis and treatment. It is also a scientifically challenging task. Recently, efforts have been made to use gene expression profiles to improve the precision of classification, with limited success. Using a published data set for purposes of comparison, we introduce a methodology based on classification trees and demonstrate that it is significantly more accurate for discriminating among distinct colon cancer tissues than other statistical approaches used heretofore. In addition, competing classification trees are displayed, which suggest that different genes may coregulate colon cancers.

Nitric oxide partitioning into mitochondrial membranes and the control of respiration at cytochrome c oxidase

An emerging and important site of action for nitric oxide (NO) within cells is the mitochondrial inner membrane, where NO binds to and inhibits members of the electron transport chain, complex III and cytochrome c oxidase. Although it is known that inhibition of cytochrome c oxidase by NO is competitive with O2, the mechanisms that underlie this phenomenon remain unclear, and the impact of both NO and O2 partitioning into biological membranes has not been considered. These properties are particularly interesting because physiological O2 tensions can vary widely, with NO having a greater inhibitory effect at low O2 tensions (<20 μM). In this study, we present evidence for a consumption of NO in mitochondrial membranes in the absence of substrate, in a nonsaturable process that is O2 dependent. This consumption modulates inhibition of cytochrome c oxidase by NO and is enhanced by the addition of exogenous membranes. From these data, it is evident that the partition of NO into mitochondrial membranes has a major impact on the ability of NO to control mitochondrial respiration. The implications of this conclusion are discussed in the context of mitochondrial lipid:protein ratios and the importance of NO as a regulator of respiration in pathophysiology.

Drying Increases Intracellular Partitioning of Amphiphilic Substances into the Lipid Phase1 : Impact on Membrane Permeability and Significance for Desiccation Tolerance

Previously we proposed that endogenous amphiphilic substances may partition from the aqueous cytoplasm into the lipid phase during dehydration of desiccation-tolerant organ(ism)s and vice versa during rehydration. Their perturbing presence in membranes could thus explain the transient leakage from imbibing organisms. To study the mechanism of this phenomenon, amphiphilic nitroxide spin probes were introduced into the pollen of a model organism, Typha latifolia, and their partitioning behavior during dehydration and rehydration was analyzed by electron paramagnetic resonance spectroscopy. In hydrated pollen the spin probes mainly occurred in the aqueous phase; during dehydration, however, the amphiphilic spin probes partitioned into the lipid phase and had disappeared from the aqueous phase below 0.4 g water g−1 dry weight. During rehydration the probes reappeared in the aqueous phase above 0.4 g water g−1 dry weight. The partitioning back into the cytoplasm coincided with the decrease of the initially high plasma membrane permeability. A charged polar spin probe was trapped in the cytoplasm during drying. Liposome experiments showed that partitioning of an amphiphilic spin probe into the bilayer during dehydration caused transient leakage during rehydration. This was also observed with endogenous amphipaths that were extracted from pollen, implying similar partitioning behavior. In view of the fluidizing effect on membranes and the antioxidant properties of many endogenous amphipaths, we suggest that partitioning with drying may be pivotal to desiccation tolerance, despite the risk of imbibitional leakage.

A Fiberless Seed Mutation in Cotton Is Associated with Lack of Fiber Cell Initiation in Ovule Epidermis and Alterations in Sucrose Synthase Expression and Carbon Partitioning in Developing Seeds1

Fiber cell initiation in the epidermal cells of cotton (Gossypium hirsutum L.) ovules represents a unique example of trichome development in higher plants. Little is known about the molecular and metabolic mechanisms controlling this process. Here we report a comparative analysis of a fiberless seed (fls) mutant (lacking fibers) and a normal (FLS) mutant to better understand the initial cytological events in fiber development and to analyze the metabolic changes that are associated with the loss of a major sink for sucrose during cellulose biosynthesis in the mutant seeds. On the day of anthesis (0 DAA), the mutant ovular epidermal cells lacked the typical bud-like projections that are seen in FLS ovules and are required for commitment to the fiber development pathway. Cell-specific gene expression analyses at 0 DAA showed that sucrose synthase (SuSy) RNA and protein were undetectable in fls ovules but were in abundant, steady-state levels in initiating fiber cells of the FLS ovules. Tissue-level analyses of developing seeds 15 to 35 DAA revealed an altered temporal pattern of SuSy expression in the mutant relative to the normal genotype. Whether the altered programming of SuSy expression is the cause or the result of the mutation is unknown. The developing seeds of the fls mutant have also shown several correlated changes that represent altered carbon partitioning in seed coats and cotyledons as compared with the FLS genotype.

Postseptational chromosome partitioning in bacteria.

Mutations in the spoIIIE gene prevent proper partitioning of one chromosome into the developing prespore during sporulation but have no overt effect on partitioning in vegetatively dividing cells. However, the expression of spoIIIE in vegetative cells and the occurrence of genes closely related to spoIIIE in a range of nonsporulating eubacteria suggested a more general function for the protein. Here we show that SpoIIIE protein is needed for optimal chromosome partitioning in vegetative cells of Bacillus subtilis when the normal tight coordination between septation and nucleoid partitioning is perturbed or when septum positioning is altered. A functional SpoIIIE protein allows cells to recover from a state in which their chromosome has been trapped by a closing septum. By analogy to its function during sporulation, we suggest that SpoIIIE facilitates partitioning by actively translocating the chromosome out of the septum. In addition to enhancing the fidelity of nucleoid partitioning, SpoIIIE also seems to be required for maximal resistance to antibiotics that interfere with DNA metabolism. The results have important implications for our understanding of the functions of genes involved in the primary partitioning machinery in bacteria and of how septum placement is controlled.

Electroencephalogram based Causality Graph Analysis in Behavior Tasks of Parkinson’s Disease Patients

Electroencephalographic (EEG) signals of the human brains represent electrical activities for a number of channels recorded over a the scalp. The main purpose of this thesis is to investigate the interactions and causality of different parts of a brain using EEG signals recorded during a performance subjects of verbal fluency tasks. Subjects who have Parkinson's Disease (PD) have difficulties with mental tasks, such as switching between one behavior task and another. The behavior tasks include phonemic fluency, semantic fluency, category semantic fluency and reading fluency. This method uses verbal generation skills, activating different Broca's areas of the Brodmann's areas (BA44 and BA45). Advanced signal processing techniques are used in order to determine the activated frequency bands in the granger causality for verbal fluency tasks. The graph learning technique for channel strength is used to characterize the complex graph of Granger causality. Also, the support vector machine (SVM) method is used for training a classifier between two subjects with PD and two healthy controls. Neural data from the study was recorded at the Colorado Neurological Institute (CNI). The study reveals significant difference between PD subjects and healthy controls in terms of brain connectivities in the Broca's Area BA44 and BA45 corresponding to EEG electrodes. The results in this thesis also demonstrate the possibility to classify based on the flow of information and causality in the brain of verbal fluency tasks. These methods have the potential to be applied in the future to identify pathological information flow and causality of neurological diseases.

Topological SLAM using a graph-matching based method on omnidirectional images

Comunicación presentada en el XI Workshop of Physical Agents, Valencia, 9-10 septiembre 2010.

An application of fuzzy logic for hardware/software partitioning in embedded systems

Hardware/Software partitioning (HSP) is a key task for embedded system co-design. The main goal of this task is to decide which components of an application are to be executed in a general purpose processor (software) and which ones, on a specific hardware, taking into account a set of restrictions expressed by metrics. In last years, several approaches have been proposed for solving the HSP problem, directed by metaheuristic algorithms. However, due to diversity of models and metrics used, the choice of the best suited algorithm is an open problem yet. This article presents the results of applying a fuzzy approach to the HSP problem. This approach is more flexible than many others due to the fact that it is possible to accept quite good solutions or to reject other ones which do not seem good. In this work we compare six metaheuristic algorithms: Random Search, Tabu Search, Simulated Annealing, Hill Climbing, Genetic Algorithm and Evolutionary Strategy. The presented model is aimed to simultaneously minimize the hardware area and the execution time. The obtained results show that Restart Hill Climbing is the best performing algorithm in most cases.