Search

International audience; Decision trees are efficient means for building classification models due to the compressibility, simplicity and ease of interpretation of their results. However, during the construction phase of decision trees, the outputs are often large trees that are affected by many uncertainties in the data (particularity, noise and residual variation). Combining attribute selection and data sampling presents one of the most promising research directions to overcome decision tree construction problems. However, the search space composed of all possible combinations of subsets of training samples and attributes is extremely large. In this paper, a novel approach is presented that allows generating an optimized decision tree by selecting an optimal couple of training samples and attributes subsets for training. As the search space of candidate couples of training samples and attributes subsets is extremely large, we use particle swarm optimization to make the search of an “optimal” solution tractable. The selected optimized solution helps in avoiding over-fitting and complexity problems suffered in the construction phase of decision trees. We conducted an extensive experimental evaluation on 22 datasets from the UCI Machine Learning Repository. The obtained results show that the proposed approach outperforms state-of-the-art classical as well as evolutionary decision tree construction methods in terms of simplicity, accuracy, and F-measure. We further evaluate our approach on a real-world engineering application for condition monitoring of rotating machinery under severe non-stationary conditions. The obtained results showed that the proposed approach allowed to optimize the use of instantaneous angular speed to diagnose gears defects.

International audience; The task of inferring missing links or predicting future ones in a graph based on its current structure is referred to as link prediction. Link prediction methods that are based on pairwise node similarity are well-established approaches in the literature and show good prediction performance in many realworld graphs though they are heuristic. On the other hand, graph embedding approaches learn lowdimensional representation of nodes in graph and are capable of capturing inherent graph features, and thus support the subsequent link prediction task in graph. This paper studies a selection of methods from both categories on several benchmark (homogeneous) graphs with different properties from various domains. Beyond the intra and inter category comparison of the performances of the methods, our aim is also to uncover interesting connections between Graph Neural Network(GNN)based methods and heuristic ones as a means to alleviate the black-box well-known limitation.

International audience; Functional annotation of protein is a very challenging task primarily because manual annotation requires a great amount of human efforts and still it’s nearly impossible to keep pace with the exponentially growing number of protein sequences coming into the public databases, thanks to the high throughput sequencing technology. For example, the UniProt Knowledge-base (UniProtKB) is currently the largest and most comprehensive resource for protein sequence and annotation data. According to the November, 2019 release of UniProtKB, some 561,000 sequences are manually reviewed but over 150 million sequences lack reviewed functional annotations. Moreover, it is an expensive deal in terms of the cost it incurs and the time it takes. On the contrary, exploiting this huge quantity of data is important to understand life at the molecular level, and is central to understanding human disease processes and drug discovery. To be useful, protein sequences need to be annotated with functional properties such as Enzyme Commission (EC) numbers and Gene Ontology(GO) terms. The ability to automatically annotate protein sequences in UniProtKB/TrEMBL, the non-reviewed UniProt sequence repository, would represent a major step towards bridging the gap between annotated and un-annotated protein sequences. In this paper, we extend a neighborhood based network inference technique for automatic GO annotation using protein similarity graph built on protein domain and family information. The underlying philosophy of our approach assumes that proteins can be linked through the domains, families, and superfamilies that they share. We propose an efficient pruning and post-processing technique by integrating semantic similarity of GO terms. We show by empirical results that the proposed hierarchical post-processing potentially improves the performance of other GO annotation tools as well.

International audience

Ionizing-radiation-resistant bacteria (IRRB) could be used for bioremediation of radioactive wastes and in the therapeutic industry. Limited computational works are available for the prediction of bacterial ionizing radiation resistance (IRR). In this work, we present ABClass, an in silico approach that predicts if an unknown bacterium belongs to IRRB or ionizing-radiation-sensitive bacteria (IRSB). This approach is based on a multiple instance learning (MIL) formulation of the IRR prediction problem. It takes into account the relation between semantically related instances across bags. In ABClass, a preprocessing step is performed in order to extract substructures/motifs from each set of related sequences. These motifs are then used as attributes to construct a vector representation for each set of sequences. In order to compute partial prediction results, a discriminative classifier is applied to each sequence of the unknown bag and its correspondent related sequences in the learning dataset. Finally, an aggregation method is applied to generate the final result. The algorithm provides good overall accuracy rates. ABClass can be downloaded at the following link: http://homepages.loria.fr/SAridhi/software/MIL/.

Objectives: The universal controller PID (Proportional-Integra-Derivative) is widely used in automation systems. Methods: This work is focused to develop a PID controller for a refrigeration system in order to implement it in a Field Programmable Gate Array (FPGA) by using the Very High Speed Integrated Circuit Hardware Description Language (VHDL). Firstly, the nonlinear model of the refrigeration system is presented by a third order state system and simulated under Matlab/Simulink environment to develop its PID controller, which is aimed to adjust the indoor temperature. Further, the synthetizable program of the PID algorithm has been implemented on a Map Altera DE0-nano Kit using the Quartus II software. Findings: The performance of the proposed controller has been successfully validated with good tracking results. Application: The FPGA target presents a good solution to implement the PID algorithm. Keywords: FPGA-Implementation, PID Controller, Quartus II, Refrigeration System, Temprature Control, Altera DE0-Nano Kit.

International audience

This paper invests in FPGA technology to control the speed of an autonomous car using fuzzy logic. For that purpose, we propose a co-design based on a novel fuzzy controller IP. It was developed using the hardware language VHDL and driven by the Zynq processor through an SDK software design written in C. The proposed IP acts according to the ambient temperature and the presence or absence of an obstacle and its distance from the car. The partitioning of the co-design tasks divides them into hardware and software parts. The simulation results of the fuzzy IP and those of the complete co-design implementation on a Xilinx Zynq board showed the effectiveness of the proposed controller to meet the target constraints and generate suitable PWM signals. The proposed hardware architecture based on 6-LUT blocks uses 11 times fewer logic resources than other previous similar designs. Also, it can be easily updated when new constraints on the system are to be considered, which makes it suitable for many related applications. Fuzzy computing was accelerated thanks to the use of digital signal processing blocks that ensure parallel processing. Indeed, a complete execution cycle takes only 7 us.

This paper proposes a semi-formal methodology for modeling and verification of analog circuits behavioral properties using multivariate optimization techniques. Analog circuit differential models are automatically extracted and their qualitative behavior is computed for interval-valued parameters, inputs and initial conditions. The method has the advantage of guaranteeing the rough enclosure of any possible dynamical behavior of analog circuits. The circuit behavioral properties are then verified on the generated transient response bounds. Experimental results show that the resulting state variable envelopes can be effectively employed for a sound verification of analog circuit properties, in an acceptable run-time.

International audience; Due to the recent advancement in genomic sequencing technologies, the number of protein sequences in public databases is growing exponentially. The UniProt Knowledgebase (UniProtKB) is currently the largest and most comprehensive resource for protein sequence and annotation data. The May 2019 release of the Uniprot Knowledge base (UniprotKB) contains around 158 million protein sequences. For the complete exploitation of this huge knowledge base, protein sequences need to be annotated with functional properties such as Enzyme Commission (EC) numbers and Gene Ontology terms. However, there is only about half a million sequences (UniprotKB/SwissProt) are reviewed and functionally annotated by expert curators using information extracted from the published literature and computational analyses. The manual annotation by experts are expensive, slow and insufficient to fill the gap between the annotated and unannotated protein sequences. In this paper, we present an automatic functional annotation technique using neural network based based word embedding exploiting domain and family information of proteins. Domains are the most conserved regions in protein sequences and constitute the building blocks of 3D protein structures. To do the experiment, we used fastText a , a library for learning of word embeddings and text classification developed by Facebook's AI Research lab. The experimental results show that domain embeddings perform much better than k-mer based word embeddings. a https://github.com/facebookresearch/fasttext

The Critical Assessment of Functional Annotation (CAFA) is an ongoing, global, community-driven effort to evaluate and improve the computational annotation of protein function. Here we report on the results of the third CAFA challenge, CAFA3, that featured an expanded analysis over the previous CAFA rounds, both in terms of volume of data analyzed and the types of analysis performed. In a novel and major new development, computational predictions and assessment goals drove some of the experimental assays, resulting in new functional annotations for more than 1000 genes. Specifically, we performed experimental whole-genome mutation screening in Candida albicans and Pseudomonas aureginosa genomes, which provided us with genome-wide experimental data for genes associated with biofilm formation and motility (P. aureginosa only). We further performed targeted assays on selected genes in Drosophila melanogaster, which we suspected of being involved in long-term memory. We conclude that, while predictions of the molecular function and biological process annotations have slightly improved over time, those of the cellular component have not. Term-centric prediction of experimental annotations remains equally challenging; although the performance of the top methods is significantly better than expectations set by baseline methods in C. albicans and D. melanogaster, it leaves considerable room and need for improvement. We finally report that the CAFA community now involves a broad range of participants with expertise in bioinformatics, biological experimentation, biocuration, and bioontologies, working together to improve functional annotation, computational function prediction, and our ability to manage big data in the era of large experimental screens.

This work is dedicated to the memory of David W. Ritchie, who recently passed away.; International audience; Background: Thanks to recent developments in genomic sequencing technologies, the number of protein sequences in public databases is growing enormously. To enrich and exploit this immensely valuable data, it is essential to annotate these sequences with functional properties such as Enzyme Commission (EC) numbers, for example. The January 2019 release of the Uniprot Knowledge base (UniprotKB) contains around 140 million protein sequences. However, only about half of a million of these (UniprotKB/SwissProt) have been reviewed and functionally annotated by expert curators using data extracted from the literature and computational analyses. To reduce the gap between the annotated and unannotated protein sequences, it is essential to develop accurate automatic protein function annotation techniques. Results: In this work, we present GrAPFI (Graph-based Automatic Protein Function Inference) for automatically annotating proteins with EC number functional descriptors from a protein domain similarity graph. We validated the performance of GrAPFI using six reference proteomes in UniprotKB/SwissProt, namely Human, Mouse, Rat, Yeast, E. Coli and Arabidopsis thaliana. We also compared GrAPFI with existing EC prediction approaches such as ECPred, DEEPre, and SVMProt. This shows that GrAPFI achieves better accuracy and comparable or better coverage with respect to these earlier approaches. Conclusions: GrAPFI is a novel protein function annotation tool that performs automatic inference on a network of proteins that are related according to their domain composition. Our evaluation of GrAPFI shows that it gives better performance than other state of the art methods. GrAPFI is available at https://gitlab.inria.fr/bsarker/bmc_grapfi.git as a stand alone tool written in Python.

The development of methods and tools to support the advancement in scientific and technical solutions has emerged in recent years in order to assist decisions that allow to avoid extra efforts due to the common traditional “trial and error” approach. At the same time, new challenges in terms of environmental protection have also engaged to adopt decisions having into account that climate protection needs to remain as a primer driver in the development of the aviation sector. AIRPOXY will recover all current requirements through an integrated approach where LCA (Life Cycle Assessment), LCC (Life Cycle Cost analysis), HHRA (Human Health Risk Assessment) and numerical simulation of manufacturing processes will work together in order to demonstrate and support the development of thermoformable, repairable and bondable smart epoxy based composites for aero structures. By considering all stated before, the final aim will be double. On one hand, to be informed about technical, environmental, economic and safety requirements during key stages, in order to take informed decisions and optimise it following the Eco-design principles. On the other hand, to obtain objective data to support performance in order to increase the impact of the project and support the further implementation of the technologies as the AIRPOXY solutions reach higher TRLs.

In Multiple Instance Learning (MIL) problem for sequence data, the instances inside the bags are sequences. In some real world applications such as bioinformatics, comparing a random couple of sequences makes no sense. In fact, each instance may have structural and/or functional relations with instances of other bags. Thus, the classification task should take into account this across bag relation. In this work, we present two novel MIL approaches for sequence data classification named ABClass and ABSim. ABClass extracts motifs from related instances and use them to encode sequences. A discriminative classifier is then applied to compute a partial classification result for each set of related sequences. ABSim uses a similarity measure to discriminate the related instances and to compute a scores matrix. For both approaches, an aggregation method is applied in order to generate the final classification result. We applied both approaches to solve the problem of bacterial Ionizing Radiation Resistance prediction. The experimental results of the presented approaches are satisfactory.

International audience; Huge numbers of protein sequences are now available in public databases. In order to exploit more fully this valuable biological data, these sequences need to be annotated with functional properties such as Enzyme Commission (EC) numbers and Gene Ontology terms. The UniProt Knowledgebase (UniProtKB) is currently the largest and most comprehensive resource for protein sequence and annotation data. In the March 2018 release of UniProtKB, some 556,000 sequences have been manually curated but over 111 million sequences still lack functional annotations. The ability to annotate automatically these unannotated sequences would represent a major advance for the field of bioinformatics. Here, we present a novel network-based approach called GrAPFI for the automatic functional annotation of protein sequences. The underlying assumption of GrAPFI is that proteins may be related to each other by the protein domains, families, and super-families that they share. Several protein domain databases exist such as In-terPro, Pfam, SMART, CDD, Gene3D, and Prosite, for example. Our approach uses Interpro domains, because the InterPro database contains information from several other major protein family and domain databases. Our results show that GrAPFI achieves better EC number annotation performance than several other previously described approaches.

International audience; During the last decade, cloud computing became a natural choice to host and provide various computing resources as on-demand services. The correct characterization and management of cloud environment objects (clouds, data centers, providers, services, data, users, etc.) is the first step towards effective provisioning and integration of cloud services. However, cloud computing environment is often subject to uncertainty. This could be attributed to the incompleteness and imprecision of cloud available information, as well as the highly changing conditions. The purpose of this survey is to study, criticize and classify the already existing works that deal with uncertainty in the cloud. We present a taxonomy on the uncertainty in the cloud and we study how such concept was tackled by researchers in cloud environments. Finally, we identify the challenges and the requirements to deal with uncertain data in the cloud, as well as the future directions.

The primary task of a memory-based collaborative filtering (CF) recommendation system is to select a group of nearest (similar) user neighbors for an active user. Traditional memory-based CF schemes tend to only focus on improving as much as possible the accuracy by recommending familiar items (i.e., popular items over the group). Yet, this may reduce the number of items that could be recommended and consequently weakens the chances of recommending novel items. To address this problem, it is desirable to consider recommendation coverage when selecting the appropriate group. This could help in simultaneously making both accurate and diverse recommendations. In this paper, we propose to focus mainly on the growing of the large search space of users’ profiles and to use an evolutionary multi-objective optimization-based recommendation system to pull up a group of profiles that maximizes both similarity with the active user and diversity between its members. In such manner, the recommendation system will provide high performances in terms of both accuracy and diversity. The experimental results on the Movielens benchmark and on a real-world insurance dataset show the efficiency of our approach in terms of accuracy and diversity compared to state-of-the-art competitors.

Recently, increasingly large amounts of data are generated from a variety of sources.Existing data processing technologies are not suitable to cope with the huge amounts of generated data. Yet, many research works focus on Big Data, a buzzword referring to the processing of massive volumes of (unstructured) data. Recently proposed frameworks for Big Data applications help to store, analyze and process the data. In this paper, we discuss the challenges of Big Data and we survey existing Big Data frameworks. We also present an experimental evaluation and a comparative study of the most popular Big Data frameworks with several representative batch and iterative workloads. This survey is concluded with a presentation of best practices related to the use of studied frameworks in several application domains such as machine learning, graph processing and real-world applications.

International audience; This article introduces a new technique to minimize the memory footprints of Digital Signal Processing (DSP) applications specified with Synchronous Dataflow (SDF) graphs and implemented on shared-memory Multiprocessor Systems-on-Chips (MPSoCs). In addition to the SDF specification, which captures data dependencies between coarse-grained tasks called actors, the proposed technique relies on two optional inputs abstracting the internal data dependencies of actors: annotations of the ports of actors, and script-based specifications of merging opportunities between input and output buffers of actors. Experimental results on a set of applications show a reduction of the memory footprint by 48% compared to state-of-the-art minimization techniques.

Recently, graph mining approaches have become very popular, especially in certain domains such as bioinformatics, chemoinformatics and social networks. One of the most challenging tasks is frequent subgraph discovery. This task has been highly motivated by the tremendously increasing size of existing graph databases. Due to this fact, there is an urgent need of efficient and scaling approaches for frequent subgraph discovery. In this paper, we propose a novel approach for large-scale subgraph mining by means of a density-based partitioning technique, using the MapReduce framework. Our partitioning aims to balance computational load on a collection of machines. We experimentally show that our approach decreases significantly the execution time and scales the subgraph discovery process to large graph databases.

International audience; Classification is a central task in machine learning and data mining. Decision tree (DT) is one of the most popular learning models in data mining. The performance of a DT in a complex decision problem depends on the efficiency of its construction. However, obtaining the optimal DT is not a straightforward process. In this paper, we propose a new evolutionary meta-heuristic optimization based approach for identifying the best settings during the construction of a DT. We designed a genetic algorithm coupled with a multi-task objective function to pull out the optimal DT with the best parameters. This objective function is based on three main factors: (1) Precision over the test samples, (2) Trust in the construction and validation of a DT using the smallest possible training set and the largest possible testing set, and (3) Simplicity in terms of the size of the generated candidate DT, and the used set of attributes. We extensively evaluate our approach on 13 benchmark datasets and a fault diagnosis dataset. The results show that it outperforms classical DT construction methods in terms of accuracy and simplicity. They also show that the proposed approach outperforms Ant-Tree-Miner (an evolutionary DT construction approach), Naive Bayes and Support Vector Machine in terms of accuracy and F-measure.

International audience; With the increasing size and complexity of available databases, existing machine learning and data mining algorithms are facing a scalability challenge. In many applications, the number of features describing the data could be extremely high. This hinders or even could make any further exploration infeasible. In fact, many of these features are redundant or simply irrelevant. Hence, feature selection plays a key role in helping to overcome the problem of information overload especially in big data applications. Since many complex datasets could be modeled by graphs of interconnected labeled elements, in this work, we are particularly interested in feature selection for subgraph patterns. In this paper, we propose MR-SimLab, a MapReduce-based approach for subgraph selection from large input subgraph sets. In many applications, it is easy to compute pairwise similarities between labels of the graph nodes. Our approach leverages such rich information to measure an approximate subgraph matching by aggre-gating the elementary label similarities between the matched nodes. Based on the aggregated similarity scores, our approach selects a small subset of informative representative subgraphs. We provide a distributed implementation of our algorithm on top of the MapReduce framework that optimizes the computational efficiency of our approach for big data applications. We experimentally evaluate MR-SimLab on real datasets. The obtained results show that our approach is scalable and that the selected subgraphs are informative.

International audience; Recently, distributed processing of large dynamic graphs has become very popular , especially in certain domains such as social network analysis, Web graph analysis and spatial network analysis. In this context, many distributed/parallel graph processing systems have been proposed, such as Pregel, PowerGraph, GraphLab, and Trinity. However, these systems deal only with static graphs and do not consider the issue of processing evolving and dynamic graphs. In this paper, we are considering the issues of scale and dynamism in the case of graph processing systems. We present BLADYG, a graph processing framework that addresses the issue of dynamism in large-scale graphs. We present an implementation of BLADYG on top of akka framework. We experimentally evaluate the performance of the proposed framework by applying it to problems such as distributed k-core decomposition and partitioning of large dynamic graphs. The experimental results show that the performance and scalability of BLADYG are satisfying for large-scale dynamic graphs.

In the Arabic-speaking world, textual productions on social networks are often informal and generally characterized by the use of various dialects, which can be transcribed in Latin or Arabic characters. More specifically, electronic writing in Tunisia is characterized in large part by a mixture of Tunisian dialect with other languages and by a margin of individualization giving users the freedom to write without depending on orthographic or grammatical constraints. In this work, we address the problem of the automatic Tunisian dialect identification within the electronic writings that are produced on social networks using the Latin alphabet. We propose to study and experiment two different identification approaches. Our experiments show that the best performance is obtained using a machine learning based approach using Support Vector Machines.

Big graph mining is an important research area and it has attracted considerable attention. It allows to process, analyze, and extract meaningful information from large amounts of graph data. Big graph mining has been highly motivated not only by the tremendously increasing size of graphs but also by its huge number of applications. Such applications include bioinformatics, chemoinformatics and social networks. One of the most challenging tasks in big graph mining is pattern mining in big graphs. This task consists on using data mining algorithms to discover interesting, unexpected and useful patterns in large amounts of graph data. It aims also to provide deeper understanding of graph data. In this context, several graph processing frameworks and scaling data mining/pattern mining techniques have been proposed to deal with very big graphs. This paper gives an overview of existing data mining and graph processing frameworks that deal with very big graphs. Then it presents a survey of current researches in the field of data mining / pattern mining in big graphs and discusses the main research issues related to this field. It also gives a categorization of both distributed data mining and machine learning techniques, graph processing frameworks and large scale pattern mining approaches., Submitted to Big Data Research, Elsevier

International audience; This paper introduces a new distributed memory allocation technique for applications modeled with Synchronous Dataflow (SDF) graphs. This technique builds on a State-of-the-Art shared memory allocation technique based on a weighted graph, called Memory Exclusion Graph (MEG). A MEG captures the memory reuse opportunities between memory objects that must be allocated before the execution of an SDF graph. The algorithms detailed in this paper enable a single MEG to be split into separate MEGs, each of which is associated with a memory bank accessible only by one core of the architecture. The proposed technique is implemented within a rapid prototyping framework and is evaluated by deploying real computer vision applications on a Multiprocessor System-on-Chip (MPSoC). Results show a systematic performance improvement due to better memory usage, with application speedups ranging from 2% up to 380%.

International audience; Distributed processing of large, dynamic graphs has recentlyreceived considerable attention, especially in domains suchas the analytics of social networks, web graphs and spatialnetworks.k-core decomposition is one of the significant fig-ures of merit that can be analyzed in graphs. Efficient algo-rithms to computek-cores exist already, both in centralizedand decentralized setting. Yet, these algorithms have beendesigned for static graphs, without significant support todeal with the addition or removal of nodes and edges. Typi-cally, this challenge is handled by re-executing the algorithmagain on the updated graph. In this work, we propose dis-tributedk-core decomposition and maintenance algorithmsfor large dynamic graphs. The proposed algorithms exploit,as much as possible, the topology of the graph to compute allthek-cores and maintain them in streaming settings whereedge insertions and removals happen frequently. The keyidea of the maintenance strategy is that whenever the orig-inal graph is updated by the insertion/deletion of one ormore edges, only a limited number of nodes need their core-ness to be re-evaluated. We present an implementation ofthe proposed approach on top of theakkaframework, andexperimentally show the efficiency of our approach in thecase of large dynamic networks.

Recently, distributed processing of large dynamic graphs has become very popular, especially in certain domains such as social network analysis, Web graph analysis and spatial network analysis. In this context, many distributed/parallel graph processing systems have been proposed, such as Pregel, GraphLab, and Trinity. These systems can be divided into two categories: (1) vertex-centric and (2) block-centric approaches. In vertex-centric approaches, each vertex corresponds to a process, and message are exchanged among vertices. In block-centric approaches, the unit of computation is a block, a connected subgraph of the graph, and message exchanges occur among blocks. In this paper, we are considering the issues of scale and dynamism in the case of block-centric approaches. We present BLADYG, a block-centric framework that addresses the issue of dynamism in large-scale graphs. We present an implementation of BLADYG on top of AKKA framework. We experimentally evaluate the performance of the proposed framework.

Distributed graph processing has become a very popular research topic recently, particularly in domains such as the analysis of social networks, web graphs and spatial networks. In this context, graph partitioning is an important task. Several partitioning algorithms have been proposed, such as DFEP, JABEJA and POWERGRAPH, but they are limited to static graphs only. In fact, they do not consider dynamic graphs in which vertices and edges are added and/or removed. In this paper, we propose a graph partitioning method for large dynamic graphs. We present an implementation of the proposed approach on top of the AKKA framework, and we experimentally show that our approach is efficient in the case of large dynamic graphs.

International audience; The majority of applications, ranging from the low complexity to very multifaceted entities requiring dedicated hardware accelerators, are very well suited for Multiprocessor Systems-on-Chips (MPSoCs). It is critical to understand the general characteristics of a given embedded application: its behavior and its requirements in terms of MPSoC resources.This paper presents a complete method to study the important aspect of memory characteristic of an application. This method spans the theoretical, architecture-independent memory characterization to the quasi optimal static memory allocation of an application on a real shared-memory MPSoC. The application is modeled as an Synchronous Dataflow (SDF) graph which is used to derive a Memory Exclusion Graph (MEG) essential for the analysis and allocation techniques. Practical considerations, such as cache coherence and memory broad-casting, are extensively treated. Memory footprint optimization is demonstrated using the example of a stereo matching algorithm from the computer vision domain. Experimental results show a reduction of the memory footprint by up to 43% compared to a state-of-the-art minimization technique, a throughput improvement of 33% over dynamic allocation, and the introduction of a tradeoff between multi-core scheduling flexibility and memory footprint.

International audience; This paper introduces and assesses a new technique to minimize the memory footprints of Digital Signal Processing (DSP) applications specified with Synchronous Dataflow (SDF) graphs and implemented on shared-memory Multiprocessor Systems-on-Chips (MP-SoCs). In addition to the SDF specification, which captures data dependencies between coarse-grained tasks called actors, the proposed technique relies on two optional inputs abstracting the internal data dependencies of actors: annotations of the ports of SDF actors, and script-based specifications of merging opportunities between input and output buffers of actors. An automated optimization process is used to exploit these buffer merging opportunities and to minimize the memory footprints of applications. Experimental results on a computer vision application show a reduction of the memory footprint by 34% compared to state-of-the-art minimization techniques.

The cloud computing allows to use virtually infinite resources, and seems to be a new promising opportunity to solve scientific computing problems. The MapReduce parallel programming model is a new framework favoring the design of algorithms for cloud computing. Such framework favors processing of problems across huge datasets using a large number of heterogeneous computers over the web. In this paper, we are interested in evaluating how the MapReduce framework can create an innovative way for solving operational research problems. We proposed a MapReduce-based approach for the shortest path problem in large-scale real-road networks. Such a problem is the cornerstone of any real-world routing problem including the dial-a-ride problem (DARP), the pickup and delivery problem (PDP) and its dynamic variants. Most of efficient methods dedicated to these routing problems have to use the shortest path algorithms to construct the distance matrix between each pair of nodes and it could be a time-consuming task on a large-scale network due to its size. We focus on the design of an efficient MapReduce-based approach since a classical shortest path algorithm is not suitable to accomplish efficiently such task. Our objective is not to guarantee the optimality but to provide high quality solutions in acceptable computational time. The proposed approach consists in partitioning the original graph into a set of subgraphs, then solving the shortest path on each subgraph in a parallel way to obtain a solution for the original graph. An iterative improvement procedure is introduced to improve the solution. It is benchmarked on a graph modeling French road networks extracted from OpenStreetMap. The results of the experiment show that such approach achieves significant gain of computational time.

International audience; This demonstration paper presents a multicore Real Time Operating System (RTOS) that schedules a param-eterized dataflow Model of Computation (MoC) onto a multicore Digital Signal Processor (DSP) at runtime. This RTOS called Synchronous Parameterized and Interfaced Dataflow Embedded Runtime (SPIDER) exploits the Parameterized and Interfaced Synchronous Dataflow (PiSDF) MoC and its features at runtime to identify locally static regions and to optimize their execution onto multicore platforms. The RTOS is used to dispatch a stereo matching algorithm tasks with a varying range of disparities. The platform used for this demonstration is a Texas Instruments Keystone II Multiprocessor System-on-Chip (MPSoC) device composed of 8 DSP cores, 4 ARM cores, a shared memory sub-system, Multicore Navigator and multiple dedicated accelerators.

International audience; This paper introduces a novel Real-Time Operating System (RTOS) based on a parameterized dataflow Model of Computation (MoC). This RTOS, called Synchronous Parameterized and Interfaced Dataflow Embedded Runtime (SPiDER), aims at efficiently scheduling Parameterized and Interfaced Synchronous Dataflow (PiSDF) graphs on multicore architectures. It exploits features of PiSDF to locate locally static regions that exhibit predictable application behavior. This paper uses a multicore signal processing benchmark to demonstrate that the SPiDER runtime can exploit more parallelism than a conventional multicore task scheduler. By comparing experimental results of the SPiDER runtime on an 8-core Texas Instruments Keystone I Digital Signal Processor (DSP) with those obtained from the OpenMP framework, latency improvements of up to 26% are demonstrated.

We propose an environment for the verification of analog circuits behavioral properties, where the circuit state space bounds are first computed using qualitative simulation. Then, their specified behavioral properties are verified on these bounds. The effectiveness of the method is illustrated with a tunnel diode oscillator.

International audience; The high performance Digital Signal Processors (DSP) currently manufactured by Texas Instruments are heterogeneous multiprocessor architectures. Programming these architectures is a complex task often reserved to specialized engineers because the bottlenecks of both the algorithm and the architecture need to be deeply understood in order to obtain a fairly parallel execution. The PREESM framework objective is to simplify the programming of multicore DSP systems by building on dataflow programming methods. The current functionalities of this scalable framework cover memory and time analysis, as well as automatic deadlock-free code generation. Several tutorials are provided with the tool for fast initiation of C programmers to multicore DSP programming. This paper demonstrates PREESM capabilities by comparing simulation and execution performances on a stereo matching algorithm prototyped on the TMS320C6678 8-core DSP device.

International audience; —Dataflow models of computation are widely used for the specification, analysis, and optimization of Digital Signal Processing (DSP) applications. In this paper a new meta-model called PiMM is introduced to address the important challenge of managing dynamics in DSP-oriented representations. PiMM extends a dataflow model by introducing an explicit parameter dependency tree and an interface-based hierarchical compositionality mechanism. PiMM favors the design of highly-efficient heterogeneous multicore systems, specifying algorithms with customizable trade-offs among predictability and exploita-tion of both static and adaptive task, data and pipeline paral-lelism. PiMM fosters design space exploration and reconfigurable resource allocation in a flexible dynamic dataflow context.

International audience; Currently, Multicore Digital Signal Processor (DSP) platforms are commonly used in telecommunications baseband processing. In the next few years, high performance DSPs are likely to combine many more DSP cores for signal processing with some General-Purpose Processor (GPP) cores for application control. As the number of cores increases in new DSP platform designs, scheduling of applications is becoming a complex operation. Meanwhile, the variability of the scheduled applications also tends to increase as applications become more sophisticated. Such variations require runtime adaptivity of application scheduling. This paper extends the previous work on adaptive scheduling by using the Hybrid Flow-Shop (HFS) scheduling method, which enables the device architecture to be modeled as a pipeline of Processing Elements (PEs) with multiple alternate PEs for each pipeline stage. HFS scheduling is applied to the scheduling of 3rd Generation Partnership Project (3GPP) Long Term Evolution (LTE) telecommunication standard Uplink Physical Layer data processing (PUSCH). The experiments, conducted on an ARM Cortex-A9 GPP, show that an HFS scheduling algorithm has an overhead that increases very slowly with the number of PEs. This makes the method suitable for executing the adaptive scheduling in less than 1 ms for the 501 actors of a LTE PUSCH dataflow description executed on a 256-core architecture.

The number of installations of Micro-Grid or intelligent micro power networks will increase to quadruple by 2020.The purpose is to reduce the cost and the consumption of electricity in transmission and distribution networks, using a hybrid system powered by solar and wind sources, as well as integrating storage devices. This paper reviews and discusses the Micro-Grid Model. It describes various Micro-Grid components and different configurations. It also presents the model of two generation units (Photovoltaic and Wind Turbine). Then, a comparative study of different battery types used for large-scale electricity storage is carried out, followed by a review of control strategies. Full Text: PDF DOI: http://dx.doi.org/10.11591/ijpeds.v8.i1.pp402-416

Feature extraction is an unavoidable task, especially in the critical step of preprocessing biological sequences. This step consists for example in transforming the biological sequences into vectors of motifs where each motif is a subsequence that can be seen as a property (or attribute) characterizing the sequence. Hence, we obtain an object-property table where objects are sequences and properties are motifs extracted from sequences. This output can be used to apply standard machine learning tools to perform data mining tasks such as classification. Several previous works have described feature extraction methods for bio-sequence classification, but none of them discussed the robustness of these methods when perturbing the input data. In this work, we introduce the notion of stability of the generated motifs in order to study the robustness of motif extraction methods. We express this robustness in terms of the ability of the method to reveal any change occurring in the input data and also its ability to target the interesting motifs. We use these criteria to evaluate and experimentally compare four existing extraction methods for biological sequences., The paper has been accepted by the ACM Conference on Bioinformatics, Computational Biology and Biomedicine (ACM BCB) 2012. We want to cancel the submission because of the double entries of the paper in DBLP. Thank you for your understanding

To study the LTE physical layer on multi-core architectures, a Model of Computation (MoC) is needed to specify the LTE algorithms. This MoC must have the necessary expressivity, must show the algorithm parallelism and must be capable of locating system bottlenecks.

Literature on automatic multi-core code generation was reviewed in Sect. 4.5 and scheduling strategies in Sect. 4.4.1. In this section, generated code execution schemes are defined, detailing how code is generated from a given scheduling strategy.

This chapter gives an over view of the existing work on rapid prototyping and multi-core deployment in the signal processing world. The concept of rapid prototyping was introduced in Fig. 1.2 when outlining the structure of this document. It consists of automatically generating a system simulation or a system prototype from quickly constructed models. Rapid prototyping may be used for several purposes; this study uses it to manage the parallelism of DSP architectures. Parallelism must be handled differently for the macroscopic or microscopic views of a system.

International audience; Base stations developed according to the 3GPP Long Term Evolution (LTE) standard require unprecedented processing power. 3GPP LTE enables data rates beyond hundreds of Mbits/s by using advanced technologies, necessitating a highly complex LTE physical layer. The operating power of base stations is a significant cost for operators, and is currently optimized using state-of-the-art hardware solutions, such as heterogeneous distributed systems. The traditional system design method of porting algorithms to heterogeneous distributed systems based on test-and-refine methods is a manual, thus time-expensive, task. Physical Layer Multi-Core Prototyping: A Dataflow-Based Approach provides a clear introduction to the 3GPP LTE physical layer and to dataflow-based prototyping and programming. The difficulties in the process of 3GPP LTE physical layer porting are outlined, with particular focus on automatic partitioning and scheduling, load balancing and computation latency reduction, specifically in systems based on heterogeneous multi-core Digital Signal Processors. Multi-core prototyping methods based on algorithm dataflow modeling and architecture system-level modeling are assessed with the goal of automating and optimizing algorithm porting. With its analysis of physical layer processing and proposals of parallel programming methods, which include automatic partitioning and scheduling, Physical Layer Multi-Core Prototyping: A Dataflow-Based Approach is a key resource for researchers and students. This study of LTE algorithms which require dynamic or static assignment and dynamic or static scheduling, allows readers to reassess and expand their knowledge of this vital component of LTE base station design.

In Chap. 4, an overview of the multi-core scheduling problem and solutions presented in the literature were summarized. A flexible rapid prototyping process has an important role to play in all the design steps of a multi-core DSP system.

For the LTE physical layer to be properly prototyped, the target hardware architectures need to be specified at system-level, using a simple model focusing on architectural limitations. The System-Level Architecture Model (S-LAM), which enables such specifications. Sections 5.2.4 and 5.3 explain how to compute routes between operators from an S-LAM specification and Sect. 5.4 shows how transfers on these routes are simulated. Finally, the role of the S-LAM model in the rapid prototyping process.

International audience; This paper presents an application analysis technique to define the boundary of shared memory requirements of Multiprocessor System-on-Chip (MPSoC) in early stages of development. This technique is part of a rapid prototyping process and is based on the analysis of a hierarchical Synchronous Data-Flow (SDF) graph description of the system application. The analysis does not require any knowledge of the system architecture, the mapping or the scheduling of the system application tasks. The initial step of the method consists of applying a set of transformations to the SDF graph so as to reveal its memory characteristics. These transformations produce a weighted graph that represents the different memory objects of the application as well as the memory allocation constraints due to their relationships. The memory boundaries are then derived from this weighted graph using analogous graph theory problems, in particular the Maximum-Weight Clique (MWC) problem. Stateof-the-art algorithms to solve these problems are presented and a heuristic approach is proposed to provide a near-optimal solution of the MWC problem. A performance evaluation of the heuristic approach is presented, and is based on hierarchical SDF graphs of realistic applications. This evaluation shows the efficiency of proposed heuristic approach in finding near optimal solutions.

International audience; In this paper, we propose an implementation of a synthesizable VHDL program of generalized predictive control (GPC) without constraints on a map XC3S700A Xilinx Starter Kit using the Xilinx ISE 10.1 software. The control strategy was applied to a second order state system. The VHDL language was used as a programming tool. Real variables were described with the fixed-point representation to overcome the overflow problems during the computations in the VHDL program. The use of FPGA circuits presents a good choice regarding to the problem of computation time encountered in predictive algorithms. A GPC Matlab program was also implemented in order to make a performance comparison. The simulation results show a good set-point tracking.

International audience; Multiprocessor Systems-on-Chip (MPSoC) are becoming the standard high performance Digital Signal Processing (DSP) systems. Hardware complexity abstraction is needed to enable efficient MPSoC programming. A major challenge of MPSoC programming is efficiently handling the combination of new features necessary in a MPSoC operating system: load balancing and efficient use of the parallel resources, with the more traditional features of Real-Time Operating Systems (RTOS): resource sharing between applications, task priorities and reactivity to events. This paper presents a method to combine dataflow methods and RTOS features. The resulting system prototypes an RTOS for symmetric multiprocessing MPSoCs whose inputs are dataflow graphs of applications. The prototype is built on the uC/OS-II RTOS. Experimental results are given on a 3GPP Long Term Evolution algorithm executed on a 4-core MPSoC.

To achieve reliable data transmission in a power-controlled, direct-sequence code division multiple access cellular system, we investigate two error-control schemes based on the concatenation of Reed-Solomon and convolutional codes. The first scheme is a type-I hybrid selective repeat ARQ protocol (CC/HARQ) where the error detection capability of the RS outer code is used to trigger retransmission requests. The second scheme is a type-II hybrid selective repeat ARQ protocol where the error correction capability is adapted to the varying channel conditions, The performance criteria are the protocol error probability, the throughput and delay efficiencies over a Rayleigh fading DS-CDMA channel with a Gaussian approximation for the multiple access interference. While type-I CC/HARQ yields superior throughput when the number of active users is small, the results show that type-II CC/HARQ provides reliable data transfer to the largest number of users, even in the presence of imperfect power control.