MOTIVATION: Analysis toolkits for shotgun metagenomic data achieve strain-level characterization of complex microbial communities by capturing intra-species gene content variation. Yet, these tools are hampered by the extent of reference genomes that are far from covering all microbial variability, as many species are still not sequenced or have only few strains available. Binning co-abundant genes obtained from de novo assembly is a powerful reference-free technique to discover and reconstitute gene repertoire of microbial species. While current methods accurately identify species core parts, they miss many accessory genes or split them into small gene groups that remain unassociated to core clusters. RESULTS: We introduce MSPminer, a computationally efficient software tool that reconstitutes Metagenomic Species Pan-genomes (MSPs) by binning co-abundant genes across metagenomic samples. MSPminer relies on a new robust measure of proportionality coupled with an empirical classifier to group and distinguish not only species core genes but accessory genes also. Applied to a large scale metagenomic dataset, MSPminer successfully delineates in a few hours the gene repertoires of 1661 microbial species with similar specificity and higher sensitivity than existing tools. The taxonomic annotation of MSPs reveals microorganisms hitherto unknown and brings coherence in the nomenclature of the species of the human gut microbiota. The provided MSPs can be readily used for taxonomic profiling and biomarkers discovery in human gut metagenomic samples. In addition, MSPminer can be applied on gene count tables from other ecosystems to perform similar analyses. AVAILABILITY AND IMPLEMENTATION: The binary is freely available for non-commercial users at www.enterome.com/downloads. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Presents corrections to the paper, “K nearest neighbour joins for big data on MapReduce: A theoretical and experimental analysis,” (Song, G., et al), IEEE Trans. Knowl. Data Eng., vol. 28, no. 9, pp. 2376–2392, Sep. 2016.

Convergence of classical parallel iterations is detected by performing a reduction operation at each iteration in order to compute a residual error relative to a potential solution vector. To efficiently run asynchronous iterations, blocking communication requests are avoided, which makes it hard to isolate and handle any global vector. While some termination protocols were proposed for asynchronous iterations, only very few of them are based on global residual computation and guarantee effective convergence. But the most effective and efficient existing solutions feature two reduction operations, which constitutes an important factor of termination delay. In this paper, we present new, non-intrusive, protocols to compute a residual error under asynchronous iterations, requiring only one reduction operation. Various communication models show that some heuristics can even be introduced and formally evaluated. Extensive experiments with up to 5,600 processor cores confirm the practical effectiveness and efficiency of our approach.

Summary To answer the question ‘How much energy is consumed for a numerical simulation running on Graphic Processing Unit?’, an experimental protocol is here established. The current provided to a graphic processing unit (GPU) during computation is directly measured using amperometric clamps. Signal processing on the intensity of the current of the power supplied to a GPU, with noise reduction technique, gives precise timing of GPU states, which allow establishing an energy consumption model of the GPU. Energy consumption of each operation, memory copy, vector addition, and element wise product is precisely measured to tune and validate the energy consumption model. The accuracy of the proposed energy consumption model compared to measurements is finally illustrated on a conjugate gradient method for a problem discretized by a finite element method. Copyright © 2015 John Wiley & Sons, Ltd.

Summary This paper describes the use of domain decomposition methods for accelerating wave physics simulation. Numerical wave‐based methods provide more accurate simulation than geometrical methods, but at a higher computation cost as well. In the context of virtual reality, the quality of the results is estimated according to human perception, what makes geometrical methods an interesting approach for achieving real‐time physically‐based rendering. Here, we investigate a geometrical method based on both beams and rays tracing, which we enhance by two levels of parallel processing. Techniques from domain decomposition methods are coupled with classical parallel computing on both shared and distributed memory. Both optic and acoustic renderings are experimented to evaluate the acceleration impact of the domain decomposition scheme. Speedup measurements clearly show the efficiency of using domain decomposition methods for real‐time simulation of wave physics. Copyright © 2015 John Wiley & Sons, Ltd.

Embedded multicore computing and applications

Multi-core processors achieve a trade-off between the performance and the power consumption by using Dynamic Voltage Scaling (DVS) techniques. In this paper, we study the power efficient scheduling problem of real-time tasks in an identical multi-core system, and present Node Scaling model to achieve power-aware scheduling. We prove that there is a bound speed which results in the minimal power consumption for a given task set, and the maximal value of task utilization,$u_{max}$, in a task set is a key element to decide its minimal power consumption. Based on the value$u_{max}$, we classify task sets into two categories: the bounded task sets and the non-bounded task sets, and we prove the lower bound of power consumption for each type of task set. Simulations based on Intel Xeon X5550 and PXA270 processors show Node Scaling model can achieve power efficient scheduling by applying to existing algorithms such as EDF-FF and SPA2. The ratio of power reduction depends on the multi-core processor's property which is defined as the ratio of the bound speed to the maximal speed of the cores. When the ratio of speeds decreases, the ratio of power reduction increases for all the power efficient algorithms.

Given a point$p$and a set of points$S$, the kNN operation finds the$k$closest points to in$S$. It is a computational intensive task with a large range of applications such as knowledge discovery or data mining. However, as the volume and the dimension of data increase, only distributed approaches can perform such costly operation in a reasonable time. Recent works have focused on implementing efficient solutions using the MapReduce programming model because it is suitable for distributed large scale data processing. Although these works provide different solutions to the same problem, each one has particular constraints and properties. In this paper, we compare the different existing approaches for computing kNN on MapReduce, first theoretically, and then by performing an extensive experimental evaluation. To be able to compare solutions, we identify three generic steps for kNN computation on MapReduce: data pre-processing, data partitioning, and computation. We then analyze each step from load balancing, accuracy, and complexity aspects. Experiments in this paper use a variety of datasets, and analyze the impact of data volume, data dimension, and the value of k from many perspectives like time and space complexity, and accuracy. The experimental part brings new advantages and shortcomings that are discussed for each algorithm. To the best of our knowledge, this is the first paper that compares kNN computing methods on MapReduce both theoretically and experimentally with the same setting. Overall, this paper can be used as a guide to tackle kNN-based practical problems in the context of big data.

Given a point p and a set of points S, the kNN operation finds the k closest points to p in S. It is a computational intensive task with a large range of applications such as knowledge discovery or data mining. However, as the volume and the dimension of data increase, only distributed approaches can perform such costly operation in a reasonable time. Recent works have focused on implementing efficient solutions using the MapReduce programming model because it is suitable for large scale data processing. Also, it can easily be executed in a distributed environment. Although these works provide different solutions to the same problem, each one has particular constraints and properties. There is no readily available comparison to help users choose the one most appropriate for their needs. This is the problem we address in this work. Firstly, we show that all kNN implementations go through a common workflow, which we use as a basis for classification. Secondly, we describe precisely the different techniques published so far. And lastly, we provide a set of objective criteria that can be used to make informed decisions.

Colors play an important role for customers to find their preference. The perception of the color depends on the devices used to show the colors and it changes with the color transformation between one device and another. This paper proposes an iterative approach for color reproduction of industrial manufacturer samples in a commercial printer device using a Compactly-Supported Radial Basis Functions (CSRBF) space mapping which avoids unnecessary printings during color reproduction. In order to illustrate an application of the proposed color reproduction, four users manually adjusted 28 samples of colors provided by painting manufacturers. The 28 samples are automatically reproduced with good accuracy according to the International Commission on Illumination (CIE) color difference formula using the proposed CSRBF-based iterative reproduction approach. The proposed CSRBF-based approach is compared with a related Artificial Neural Network (ANN) mapping. Proposed CSRBF mapping reproduced the 100% of the colors within a threshold for industrial process taking only 3.1 sec, while the ANN mapping only reproduced the 78.57% of the colors in much time (60.1 sec).

MapReduce has excellent scalability and fault-tolerance. It fits well with dominant distributed architectures of today, such as cluster or Grid, which are usually shared-nothing computing environments. However, using MapReduce for data analysis application still meets some challenges, since MapReduce is a low-level procedural programming paradigm and it does not directly support relational algebraic operators. In this work, we addressed a typical data analytic query, multiple group-by query. We parallelized the calculations involved in this type of query with MapReduce, and we introduced indexation and data partition in our work. We measured the speedup performance for implementations over both horizontally partitioned data and vertically partitioned data. We analysed the performance affecting factors from both measurement and formal estimation during this procedure.

For massive data transmission in Data Grid supporting radio and wireless, a set of novel hierarchical multicast algorithms is proposed to attain higher efficiency of data transfers. The newly-proposed algorithms first form different clusters, second calculate the space weight vector W' and the data quantity weight vector W'' in very cluster. Then the algorithms try to find a new vector W composed by linear combination of the two old ones W' and W". The space factor and data factor game and balance, and the point of game and balance is ¿i¿j=0m-1wi, j' = ßi¿j=0m-1wi, j" a built a binary simple equation, and we sought linear parameters and generate a least weight path tree, namely multicast tree, which is then constructed by using the newly-proposed algorithms to implement the inter-cluster routing. Extended simulation results indicate that the new algorithms are more suitable for Data Grid.

For attained high data multicast efficiency for the P2P Database system, the paper proposes a set of novel multicast algorithms. In contrast with the current algorithms, the new algorithms firstly divide the group members into different clusters in terms of static delay distance, then find the central node in the clusters, cal-culate the space weight of every node, search the data quantity of every node, and find the maximal data quantity node. After obtaining the spatial weight vector and the data quantity weight vector, the algorithms try to find a new vector composed by linear combination of the spatial and data weight vectors. Then the algo-rithms build binary simple equations between them, seek linear modulus and generate a least weight path tree, namely multicast tree. The multicast tree is then constructed by using the new algorithms. Extended simulation results indicate that these new algorithms are more suitable for P2P Database compared with other well-known existing multicast solutions.