Search

There are massive jobs submitted in the supercomputer, and the job management system is typically deployed to schedule these jobs and allocate compute resources. FCFS (First Come First Serve) is a popular scheduling policy and the job's priority is determined based on the arrival time. However, under the FCFS strategy, if existing idle resources cannot meet the requirement of the head job in the waiting queue, they cannot be allocated to other jobs, which suffers from resource waste. To optimize the resource utilization, the backfilling method is proposed, which allocates the reserved idle compute nodes to a small-size and short-running non-head job, on the premise of not delaying the original head job. Obtaining the job's runtime in advance is necessary for backfilling and the traditional method relies on the user's estimation. Unfortunately, the estimated runtime provided by users is generally overestimated. Many studies extract features from historical job logs and adopt machine learning to predict the runtime. However, traditional features are insufficient to characterize the job. In this paper, we collect job logs from two supercomputers and present a novel runtime prediction framework called PREP. PREP explores the job's running path as a new feature, which implies plentiful information about the job's properties, such as the user, the project, the scale of data sets, and the parameters used. As there is a strong correlation between the job's runtime and its running path, we group jobs with similar paths into a cluster and train a runtime prediction model for each cluster respectively. Extensive evaluations demonstrate that introducing the new feature can achieve higher prediction accuracy (88.5% and 82.3% in two production supercomputers respectively), and our framework has a more desirable prediction performance than other popular strategies like Last-2 and IRPA. In addition, the predicted runtime is inserted into the real job trace of a slurm simulator to verify the advantages of PREP. • PREP explores the job's running path as a new feature to support runtime prediction. • A strong correlation between the job's runtime and its running path is evaluated. • Multiple machine learning algorithms are adopted and compared when predicting. • PREP framework suits different types of supercomputers and gain desirable prediction result. [ABSTRACT FROM AUTHOR]

Background: The Type II clustered regularly interspaced short palindromic repeats (CRISPR) and CRISPR-associated proteins (Cas) is a powerful genome editing technology, which is more and more popular in gene function analysis. In CRISPR/Cas, RNA guides Cas nuclease to the target site to perform DNA modification. Results: The performance of CRISPR/Cas depends on well-designed single guide RNA (sgRNA). However, the off-target effect of sgRNA leads to undesired mutations in genome and limits the use of CRISPR/Cas. Here, we present OffScan, a universal and fast CRISPR off-target detection tool. Conclusions: OffScan is not limited by the number of mismatches and allows custom protospacer-adjacent motif (PAM), which is the target site by Cas protein. Besides, OffScan adopts the FM-index, which efficiently improves query speed and reduce memory consumption. [ABSTRACT FROM AUTHOR]

Misconfigurations have become one of the major causes of software failures because of their increasing prevalence and severity. The complexity of configurations and users’ lack of domain knowledge are the main reasons for massive misconfigurations. Users usually identify and diagnose misconfigurations by making a comparison against the conditions that configuration options should satisfy, which we refer to as configuration constraints; however, sometimes it is hard for users to accomplish this work. Some work has been done on obtaining configuration constraints, especially from source code; nevertheless, only part of the situation has been considered, such as if-statement code snippets, limiting its help in misconfiguration diagnosis. In order to better extract configuration constraints for users’ guidance and misconfiguration diagnosis, we carried out a comprehensive manual study on the existence and variance of the configuration constraints in the source code of five different pieces of widely used open-source software. Three categories of findings are summarized based on our study, namely the general statistics, the general features of specific kinds of constraints, and the obstacles to the automatic extraction of configuration constraints. With these findings, we proposed several suggestions to maximize the automatic extraction of configuration constraints. The results show that our suggestions could improve the extraction of configuration constraints compared to existing methods. [ABSTRACT FROM AUTHOR]

Multiple sequence alignment (MSA) is an essential prerequisite and dominant method to deduce the biological facts from a set of molecular biological sequences. It refers to a series of algorithmic solutions for the alignment of evolutionarily related sequences while taking into account evolutionary events such as mutations, insertions, deletions, and rearrangements under certain conditions. These methods can be applied to DNA, RNA, or protein sequences. In this work, we take advantage of a center-star strategy to reduce the MSA problem to pairwise alignments, and we use a suffix tree to match identical substrings between two pairwise sequences. Multiple sequence alignment based on a suffix tree and center-star strategy (MASC) can accomplish MSA in O( mn ), which is linear time complexity, where m is the number of sequences and n is the average length of sequences. Furthermore, we execute our method on the Spark-distributed parallel framework to deal with ever-increasing massive data sets. Our method is significantly faster than previous techniques, with no loss in accuracy for highly similar nucleotide sequences like homologous sequences, which we experimentally demonstrate. Comparing with mainstream MSA tools (e.g., MAFFT), MASC could finish the alignment of 67,200 sequences, longer than 10,000 bps, in 9 minutes, which takes MAFFT >3.5 days. [ABSTRACT FROM AUTHOR]

In this paper, two accelerated divide-and-conquer (ADC) algorithms are proposed for the symmetric tridiagonal eigenvalue problem, which cost O(N2r) flops in the worst case, where N is the dimension of the matrix and r is a modest number depending on the distribution of eigenvalues. Both of these algorithms use hierarchically semiseparable (HSS) matrices to approximate some intermediate eigenvector matrices, which are Cauchy-like matrices and are off-diagonally low-rank. The difference of these two versions lies in using different HSS construction algorithms, one (denoted by ADC1) uses a structured low-rank approximation method and the other (ADC2) uses a randomized HSS construction algorithm. For the ADC2 algorithm, a method is proposed to estimate the off-diagonal rank. Numerous experiments have been carried out to show their stability and efficiency. These algorithms are implemented in parallel in a shared memory environment, and some parallel implementation details are included. Comparing the ADCs with highly optimized multithreaded libraries such as Intel MKL, we find that ADCs could be more than six times faster for some large matrices with few deflations. [ABSTRACT FROM AUTHOR]

In this paper we propose a novel divide-and-conquer (DC) algorithm to compute the SVD of banded matrices, and further accelerate it by using rank-structured matrix techniques, especially the hierarchically semiseparable (HSS) matrix. The DC algorithm for the symmetric banded eigenvalue problem can also be accelerated similarly. For matrices with few deflations, the banded DC algorithms require more flops than the classical DC algorithm, and thus they are suitable for narrowly banded matrices. While, if there exist many deflations, the banded DC algorithms can be faster than the classical ones for matrices with relatively large bandwidths. Numerous experiments have been done to test the proposed algorithms. Some of the tested matrices are from construction and some are from real applications. Comparing with the DC algorithm in Intel MKL, our proposed algorithms can be hundreds times faster for matrices with narrow bandwidths or many deflations. [ABSTRACT FROM AUTHOR]

Coverage problem is a fundamental issue in wireless ad hoc and sensor networks. Previous techniques for coverage scheduling often require accurate location information or range measurements, which cannot be easily obtained in resource-limited ad hoc and sensor networks. Recently, a method based on algebraic topology is proposed to achieve coverage verification using only connectivity information. The topological method sheds some light on the issue of location-free coverage. Unfortunately, the needs of centralized computation and rigorous restriction on sensing and communication ranges greatly limit the applicability in practical large-scale distributed sensor networks. In this work, we make the first attempt toward establishing a graph theoretical framework for connectivity-based coverage with configurable coverage granularity. We propose a novel coverage criterion and scheduling method based on cycle partition. Our method is able to construct a sparse coverage set in a distributed manner, using purely connectivity information. Compared with existing methods, our design has a particular advantage, which permits us to configure or adjust the quality of coverage by adequately exploiting diverse sensing ranges and specific requirements of different applications. We formally prove the correctness and evaluate the effectiveness of our approach through extensive simulations and comparisons with the state-of-the-art approaches. [ABSTRACT FROM AUTHOR]

Hierarchical high-radix router microarchitecture consisting of small SRAM-based intermediate buffers has been used in large-scale supercomputers interconnection networks. While hierarchical organization enables efficient scaling to higher switch port count, it requires intermediate buffers which can cause performance bottleneck. Shallow intermediate buffers can cause head-of-line blocking to create backpressure towards input buffers and reduce overall performance. Increasing intermediate buffer size overcomes this problem but becomes infeasible due to the large overhead. In this work, we propose to organise decentralized intermediate buffers as a centralized buffer and leverage alternate memory technology to increase its capacity. In particular, we exploit the high-density nature of Spin-Torque Transfer Magnetic RAM (STT-MRAM) to increase intermediate buffer depth while also providing near-zero leakage power. STT-MRAM has disadvantages such as higher write latency and higher write energy. To overcome these disadvantages, we propose DeepHiR, a novel deep hybrid buffer organization (STT-MRAM and SRAM) combined with a centralized buffer organization to provide high performance with minimal cost. Although the deep intermediate buffer provided by DeepHiR can effectively improve router performance, a large amount of input buffer will still cause a lot of hardware overhead. At the same time, deeper intermediate buffers also makes it take longer for the backpressure to propagate to the source node, thereby reducing the performance of DeepHiR. Therefore, we further propose ElasHiR, which leverages elastic input buffer design in the centralized row buffer to allow a part of the centralized row buffer to act as input buffer. ElasHiR adopts reduced input buffers and automatically determines the length of input buffer in the centralized row buffer. This design minimizes the buffer resource while achieving excellent efficiency. Evaluation results show that DeepHiR can achieve 56.7 percent performance improvement in packet latency under synthetic traffic, and the cost of energy and area is moderate. ElasHiR can reduce the input buffer by 93.8 percent with performance comparable to DeepHiR. [ABSTRACT FROM AUTHOR]

Interconnection networks play an essential role in the architecture of high-performance computing (HPC) systems. In this article, we explore the Galaxyfly family to build flexible-scale interconnection networks. Galaxyfly is guaranteed to retain a small constant diameter while achieving a flexible tradeoff between network scale and bisection bandwidth. Galaxyfly not only supports small-scale interconnection networks with smaller diameter but also lowers the demands for high-radix routers and is able to utilize routers with moderate radix to build exascale interconnection networks. We analyze the constructible configuration of Galaxyfly and evaluate the properties of Galaxyfly. We conduct extensive simulations and analysis to evaluate the performance, cost, and power consumption of Galaxyfly on physical layout against state-of-the-art topologies. The results show that our design achieves better performance than most existing topologies under typical HPC workloads, and is cost-effective to deploy for exascale HPC systems. [ABSTRACT FROM AUTHOR]

The vulnerabilities in Ethereum virtual machine (EVM) may lead to serious problems for the Ethereum ecosystem. With lots of techniques being developed for the validation of smart contracts, the testing of EVM has not been well‐studied. In this paper, we propose EVMFuzz, the first that uses the differential fuzzing technique to detect vulnerabilities in EVM. The core idea of EVMFuzz is to continuously generate seed contracts for different EVMs' execution, so as to find as many inconsistencies among execution results as possible, and eventually discover vulnerabilities with output cross‐referencing. First, we present the evaluation metric for the internal inconsistency indicator. Then, we construct seed contracts via predefined mutators and employ a dynamic priority scheduling algorithm to guide seed contract selection and maximize the inconsistency. Finally, we leverage different EVMs as cross‐referencing oracles avoiding manual checking. For evaluation, we selected four widely used EVMs for the test, conducted large‐scale mutation on 36,295 real‐world smart contracts, and generated 253,153 smart contracts as initial seeds. Accompanied by manual root cause analysis, we found five previously unknown security bugs and all had been included in the common vulnerabilities and exposures (CVE) database. This paper proposes EVMFuzz, the first that uses the differential fuzzing technique to detect vulnerabilities in Ethereum virtual machine (EVM). EVMFuzz found five previously unknown security bugs in four widely used EVMs, and all had been included in the common vulnerabilities and exposures (CVE) database. [ABSTRACT FROM AUTHOR]

Omics, such as genomics, transcriptome and proteomics, has been affected by the era of big data. A huge amount of high dimensional and complex structured data has made it no longer applicable for conventional machine learning algorithms. Fortunately, deep learning technology can contribute toward resolving these challenges. There is evidence that deep learning can handle omics data well and resolve omics problems. This survey aims to provide an entry-level guideline for researchers, to understand and use deep learning in order to solve omics problems. We first introduce several deep learning models and then discuss several research areas which have combined omics and deep learning in recent years. In addition, we summarize the general steps involved in using deep learning which have not yet been systematically discussed in the existent literature on this topic. Finally, we compare the features and performance of current mainstream open source deep learning frameworks and present the opportunities and challenges involved in deep learning. This survey will be a good starting point and guideline for omics researchers to understand deep learning. [ABSTRACT FROM AUTHOR]

In recent years, misconfigurations have become one of the major causes of software system failures, resulting in numerous service outages. What is worse, misconfigurations are also costly to diagnose and troubleshoot. This remains a great challenge for sysadmins (system administrators) to detect, diagnose, or troubleshoot these misconfigurations. Unlike software bugs, misconfigurations are more vulnerable to sysadmins’ mistakes. Developers and researchers are attempting to improve system reactions to misconfigurations to ease the burden of sysadmins’ diagnoses. Such efforts would greatly benefit from the techniques that can comprehensively detect bad system reactions through injected misconfigurations. Unfortunately, few such studies have achieved the above goal in the past, primarily because they only relied on generic alterations and failed to find a way to systematically generate misconfigurations. In this paper, we study eight mature open-source and commercial software packages and summarize a fine-grained classification of option types. Based on this classification, we use Augmented Backus–Naur Form to summarize and extract syntactic and semantic constraints of each type. In order to generate comprehensive misconfigurations in the test systems, we propose misconfiguration generation methods for our constraints. We implement a tool named Configuration Vulnerability Detector (ConfVD) to conduct misconfiguration injection and further analyze the systems’ reaction abilities to various misconfigurations. We carried out comprehensive analyses upon Apache Httpd, MySQL, PostgreSQL, and Yum. The results of our analysis show that our option classification covers 96% of 1582 options from the above-mentioned systems. Our constraints are more fine grained than previous works and their accuracy was found to be 91% (ascertained by manual verification). Our technique could improve generic alteration approaches without constraints, and we found that ConfVD could find nearly three times the bad reactions that were found by ConfErr. In total, we found 65 bad reactions from the systems being tested and our fine-grained constraints contributed 27.7% more bad reactions than techniques only using coarse-grained constraints. [ABSTRACT FROM AUTHOR]

As the core count grows rapidly, NoC (Network-on-Chip) consumes an increasing fraction of the modern processors/SoCs (System-on-Chips) power. It is thus very important to design energy-efficient NoC architecture. Multi-NoC (Multiple Network-on-Chip) has demonstrated its advantages in power gating for reducing leakage power, which constitutes a significant fraction of NoC power. In this paper, we propose Chameleon, a novel heterogeneous Multi-NoC design. Chameleon employs a fine-grained power gating algorithm which exploits power saving opportunities at different levels of granularity simultaneously. Integrated with a congestion-aware traffic allocation policy, Chameleon is able to achieve both high performance and low power at varying network utilization. Our experimental results on both synthetic and real workloads show that Chameleon delivers an average of 2.61 % higher performance than Catnap, the best in the literature. More importantly, Chameleon consumes an average of 27.75 % less power than Catnap. [ABSTRACT FROM AUTHOR]

Data reliability is a significant issue in large-scale storage systems. Erasure codes provide high data reliability via data recovery, which however generates a large amount of data transmission in the network. The bandwidth cost of the data transmission in recovery significantly impacts the performance of the located cluster. Existing work considers the single-failure as the most common failure pattern and mainly focuses on reducing the data transmission cost of single-failure recovery, which unfortunately fails to efficiently support the multi-failure recovery. In this work, first, we provide the Mean Time To Multi-Failure metric based on Markov model to demonstrate the frequency and pattern of multi-failure in erasure-coded storages. Then, we propose REDU to reduce the duplication and redundancy in multi-failure recovery of erasure-coded storages. In REDU, we propose merging-based de-duplication to reduce duplicated data transmission, and aggregating-based de-redundancy to reduce redundant information transmission, and we also propose cooperative routing to efficiently use the two schemes above based on the practical cluster topology. The analysis and experimental results demonstrate the importance of multi-failure recovery problem and the efficiency of REDU. [ABSTRACT FROM AUTHOR]

Communication overhead is the key challenge for distributed training. Gradient compression is a widely used approach to reduce communication traffic. When combined with a parallel communication mechanism method like pipeline, gradient compression technique can greatly alleviate the impact of communication overhead. However, there exist two problems of gradient compression technique to be solved. Firstly, gradient compression brings in extra computation cost, which will delay the next training iteration. Secondly, gradient compression usually leads to a decrease in convergence accuracy. In this paper, we combine parallel mechanism with gradient quantization and periodic full-gradient compensation, and propose a new distributed optimization method named CP-SGD, which can hide the overhead of gradient compression, overlap part of the communication and obtain high convergence accuracy. The local update operation in CP-SGD allows the next iteration to be launched quickly without waiting for the completion of gradient compression and the current communication process. Besides, the accuracy loss caused by gradient compression is solved by k-step correction method introduced in CP-SGD, which provides a gradient correction every k iterations. We prove that CP-SGD has a convergence guarantee and it achieves at least O (1 K + 1 K) convergence rate, where K is the number of iterations. We conduct extensive experiments on MXNet to verify the convergence properties and scaling performance of CP-SGD. Experimental results on a 32-GPU cluster show that convergence accuracy of CP-SGD is close to or even slightly better than that of S-SGD, and its end-to-end time is 30% less than 2-bit gradient compression under a 56Gbps bandwidth environment. In addition, we analyze the performance of CP-SGD when training on 8, 16 and 32 GPUs. It is found that CP-SGD is suitable for most compression-supported update algorithms, and its scalability is approximately linear. • CP-SGD: Distributed Stochastic Gradient Descent with Compression and Periodic Compensation. • CP-SGD help distributed deep learning train with high-accuracy and friendly-communication simultaneously. • Combining the advantages of parallel mechanism and gradient compression. • K-step correction technique makes CP-SGD achieve codesign optimizations and improve compression-based methods greatly. • CP-SGD suits most compression-supported update algorithms and gradient compression strategies. [ABSTRACT FROM AUTHOR]

Local monitoring is an effective mechanism for the security of wireless sensor networks (WSNs). Existing schemes assume the existence of sufficient number of active nodes to carry out monitoring operations. Such an assumption, however, is often difficult for a large-scale sensor network. In this work, we focus on designing an efficient scheme integrated with good self-monitoring capability as well as providing an infrastructure for various security protocols using local monitoring. To the best of our knowledge, we are the first to present the formal study on optimizing network topology for edge self-monitoring in WSNs. We show that the problem is NP-complete even under the unit disk graph (UDG) model and give the upper bound on the approximation ratio in various graph models. We provide polynomial-time approximation scheme (PTAS) algorithms for the problem in some specific graphs, for example, the monitoring-set-bounded graph. We further design two distributed polynomial algorithms with provable approximation ratio. Through comprehensive simulations, we evaluate the effectiveness of our design. [ABSTRACT FROM AUTHOR]

Decentralized Online Social Network (DOSN) services have been proposed to protect data privacy. In DOSN, the data published by a user and their replicas are only stored in the friend circle of the user. Although full replication can improve Data Availability (DA), pure DOSNs may not deliver sustainable DA. This paper proposes a Cloud-assisted data replication and storage scheme, called Cadros, to improve the DA in DOSN. This paper conducts quantitative analysis about the storage capacity of Cadros, and further models and predicts the level of DA that Cadros can achieve. The data in Cadros are partitioned in such a way that the overhead caused by storing the data in the Cloud is minimized while satisfying the desired DA. This paper also proposes the data placement strategies to realize the desired DA and improve other performance. Experiments have been conducted to verify the effectiveness of Cadros. [ABSTRACT FROM AUTHOR]

Community search has attracted widespread attention in many fields, such as protein interaction networks, social networks, and knowledge graphs. It aims to find cohesive subgraphs that are closely related to a query vertex q in a graph G. Existing community search researches based on attribute graphs rarely consider the semantic information of attributes and interpretability of the community. In this paper, we study Community Search over Semantic-based Attribute Graphs (CSSAG), where the attribute of each vertex in the graph G is a semantic graph. To guarantee both the attribute and structure cohesiveness of the community, we introduce the maximal common subgraph and minimal degree metric to measure the cohesiveness of the attribute and structure, respectively. In this way, we can get more understandable and diverse cohesive subgraphs as depicted in the experiment. Also, we design three different online query algorithms by integrating new pruning strategies to shift the search space. Extensive experiments on real-world networks show that our approaches are effective and efficient. [ABSTRACT FROM AUTHOR]

Influence Maximization aims to find the top- K influential individuals to maximize the influence spread within a social network, which remains an important yet challenging problem. Most existing greedy algorithms mainly focus on computing the exact influence spread, leading to low computational efficiency and limiting their application to real-world social networks. While in this paper we show that through supervised sampling, we can efficiently estimate the influence spread at only negligible cost of precision, thus significantly reducing the execution time. Motivated by this, we propose ESMCE, a power-law exponent supervised Monte Carlo estimation method. In particular, ESMCE exploits the power-law exponent of the social network to guide the sampling, and employs multiple iterative steps to guarantee the estimation accuracy. Moreover, ESMCE shows excellent scalability and well suits large-scale social networks. Extensive experiments on six real-world social networks demonstrate that, compared with state-of-the-art greedy algorithms, ESMCE is able to achieve almost two orders of magnitude speedup in execution time with only negligible error (2.21 % on average) in influence spread. [ABSTRACT FROM AUTHOR]

Abstract: In this paper it is presented a compensated de Casteljau algorithm to accurately evaluate a bivariate polynomial in Bernstein–Bézier form. The principle is to apply error-free transformations to improve the traditional de Casteljau algorithm. A forward error and a running error analysis are performed. Finally, some numerical experiments illustrate the accuracy of the proposed algorithm in ill-conditioned problems. [Copyright &y& Elsevier]

As the link speed has grown steadily from 10 Gbps to 100 Gbps, high-speed data center networks (DCNs) require more efficient congestion management. Therefore, proactive transports, especially credit-based congestion control, nowadays have drawn much attention because of fast convergence, near-zero queueing and low latency. However, in real deployment scenarios, it is hard to guarantee one protocol to be deployed in every host at one time. Thus, when the credit-based protocols are deployed into DCNs incrementally, the network will convert to multi-protocol state and face the following fundamental challenges: (i) unfairness, (ii) non-convergence, and (iii) high buffer occupancy. In this paper, we propose a new protocol, called CCRP, aiming for converging credit-based and reactive protocols in data centers. Targeting the mostly deployed protocol, i.e. DCQCN based on explicit congestion notification (ECN), in DCNs, CCRP leverages the forward ECN to detect the network congestion in data queue and optimizes feedback control of the credit-based transports. Our experiment results show that this design can address the unfair link allocation and converge with reactive protocols rapidly. Furthermore, CCRP achieves high utilization and low buffer occupancy at the same time. [ABSTRACT FROM AUTHOR]

It is promising to deploy CNN inference on local end-user devices for high-accuracy and time-sensitive applications. Model parallelism has the potential to provide high throughput and low latency in distributed CNN inference. However, it is non-trivial to use model parallelism as the original CNN model is inherently tightly-coupled structure. In this article, we propose DeCNN, a more effective inference approach that uses decoupled CNN structure to optimize model parallelism for distributed inference on end-user devices. DeCNN is novel consisting of three schemes. Scheme-1 is structure-level optimization. It exploits group convolution and channel shuffle to decouple the original CNN structure for model parallelism. Scheme-2 is partition-level optimization. It is based on channel group to partition the convolutional layers, and then leverages input-based method to partition the fully connected layers, further exposing high degree of parallelism. Scheme-3 is communication-level optimization. It uses inter-sample parallelism to hide communications for better performance and robustness, especially in the weak network connections. We use ImageNet classification task to evaluate the effectiveness of DeCNN on a distributed multi-ARM platform. Notably, when using the number of devices from 1 to 4, DeCNN can accelerate the inference of large-scale ResNet-50 by 3.21×, and reduce 65.3 percent memory footprint, with 1.29 percent accuracy improvement. [ABSTRACT FROM AUTHOR]

Background: VISPR is an interactive visualization and analysis framework for CRISPR screening experiments. However, it only supports the output of MAGeCK, and requires installation and manual configuration. Furthermore, VISPR is designed to run on a single computer, and data sharing between collaborators is challenging. Results: To make the tool easily accessible to the community, we present VISPR-online, a web-based general application allowing users to visualize, explore, and share CRISPR screening data online with a few simple steps. VISPR-online provides an exploration of screening results and visualization of read count changes. Apart from MAGeCK, VISPR-online supports two more popular CRISPR screening analysis tools: BAGEL and JACKS. It provides an interactive environment for exploring gene essentiality, viewing guide RNA (gRNA) locations, and allowing users to resume and share screening results. Conclusions: VISPR-online allows users to visualize, explore and share CRISPR screening data online. It is freely available at http://vispr-online.weililab.org, while the source code is available at https://github.com/lemoncyb/VISPR-online. [ABSTRACT FROM AUTHOR]

Abstract In this study, we use a new method to improve the cooperation among agents in dynamic complex networks with source exchanging environments. As we know, in real life if we want to complete a task, cooperating with others will be better. The more resources partners have, the higher their effectiveness will be. Working with a strong man could help us progress faster, so do agents. Inspired by this, we first find a set of "strongers" agents in a complex network and establish allocations to improve cooperation. We then provide the experiment results and related analysis. [ABSTRACT FROM AUTHOR]

The cloud computing paradigm enables providing resources on demand. However, most of them focus on a single type of application requiring separate quality of service. In the context that mix heterogeneous workloads are co-scheduled in the cloud, resource multiplexing is the key to improve resource utilization under premise of performance guaranteing. In this paper, we propose a resource stealing mechanism to improve resource multiplexing of cloud resources. It enables free resource fragments reserved by some workloads being utilized by others. To meet certain service level agreement, resource preemption is adopted as a complement to resource stealing. It ensures each workload with a minimum amount of resources when required. Moreover, we propose an adaptive joint resource provisioning algorithm. It integrates our resource multiplexing method into elastic resource provisioning. Experimental results reveal that the proposed algorithms improve resource utilization and workload performance simultaneously. [ABSTRACT FROM AUTHOR]

Single Nucleotide Polymorphism (SNP) detection is a fundamental procedure of whole genome analysis. SOAPsnp, a classic tool for detection, would take more than one week to analyze one typical human genome, which limits the efficiency of downstream analyses. In this paper, we present mSNP, an optimized version of SOAPsnp, which leverages Intel Xeon Phi coprocessors for large-scale SNP detection. Firstly, we redesigned the essential data structures of SOAPsnp, which significantly reduces memory footprint and improves computing efficiency. Then we developed a coordinated parallel framework for a higher hardware utilization of both CPU and Xeon Phi. Also, we tailored the data structures and operations to utilize the wide VPU of Xeon Phi to improve data throughput. Last but not the least, we proposeed a read-based window division strategy to improve throughput and obtain better load balance. mSNP is the first SNP detection tool empowered by Xeon Phi. We achieved a 38x single thread speedup on CPU, without any loss in precision. Moreover, mSNP successfully scaled to 4,096 nodes on Tianhe-2. Our experiments demonstrate that mSNP is efficient and scalable for large-scale human genome SNP detection. [ABSTRACT FROM AUTHOR]

Traditional input-queued routers in network-on-chips (NoCs) only have a small number of virtual channels (VCs) and packets in a VC are organized in a fixed order. Such design is susceptible to head-of-line (HoL) blocking as only the packet at the head of a VC can be allocated by the switch allocator. Since switch allocation is the critical pipeline stage in on-chip routers, HoL blocking significantly degrades the performance of NoCs. In this paper, we propose to schedule packets in input buffers utilizing reorder buffer (RoB) techniques. We design VCs as RoBs to allow packets located not at the head of a VC to be allocated before the head packets. RoBs reduce the conflicts in switch allocation and mitigate the HoL blocking and thus improve the NoC performance. However, it is hard to reorder all the units in a VC due to circuit complexity and power overhead. We propose RoB-Router, which leverages elastic RoBs in VCs to only allow a part of a VC to act as RoB. RoB-Router automatically determines the length of RoB in a VC based on the number of buffered flits. This design minimizes the resource while achieving excellent efficiency. Furthermore, we propose two independent methods to improve the performance of RoB-Router. One is to optimize the packet order in input buffers by redesigning VC allocation strategy. The other combines RoB-Router with current most efficient switch allocator TS-Router. We perform evaluations and the results show that our design can achieve 46 and 15.7 percent performance improvement in packet latency under synthetic traffic and traces from PARSEC than TS-Router, and the cost of energy and area is moderate. Additionally, average packet latency reduction by our two improving methods under uniform traffic is 13 and 17 percent respectively. [ABSTRACT FROM AUTHOR]

Background: Novel sequence motifs detection is becoming increasingly essential in computational biology. However, the high computational cost greatly constrains the efficiency of most motif discovery algorithms. Results: In this paper, we accelerate MEME algorithm targeted on Intel Many Integrated Core (MIC) Architecture and present a parallel implementation of MEME called MIC-MEME base on hybrid CPU/MIC computing framework. Our method focuses on parallelizing the starting point searching method and improving iteration updating strategy of the algorithm. MIC-MEME has achieved significant speedups of 26.6 for ZOOPS model and 30.2 for OOPS model on average for the overall runtime when benchmarked on the experimental platform with two Xeon Phi 3120 coprocessors. Conclusions: Furthermore, MIC-MEME has been compared with state-of-arts methods and it shows good scalability with respect to dataset size and the number of MICs. Source code: https://github.com/hkwkevin28/MIC-MEME. [ABSTRACT FROM AUTHOR]

Background: Frequent subgraphs mining is a significant problem in many practical domains. The solution of this kind of problem can particularly used in some large-scale drug molecular or biological libraries to help us find drugs or core biological structures rapidly and predict toxicity of some unknown compounds. The main challenge is its efficiency, as (i) it is computationally intensive to test for graph isomorphisms, and (ii) the graph collection to be mined and mining results can be very large. Existing solutions often require days to derive mining results from biological networks even with relative low support threshold. Also, the whole mining results always cannot be stored in single node memory. Results: In this paper, we implement a parallel acceleration tool for classical frequent subgraph mining algorithm called cmFSM. The core idea is to employ parallel techniques to parallelize extension tasks, so as to reduce computation time. On the other hand, we employ multi-node strategy to solve the problem of memory constraints. The parallel optimization of cmFSM is carried out on three different levels, including the fine-grained OpenMP parallelization on single node, multi-node multi-process parallel acceleration and CPU-MIC collaborated parallel optimization. Conclusions: Evaluation results show that cmFSM clearly outperforms the existing state-of-the-art miners even if we only hold a few parallel computing resources. It means that cmFSM provides a practical solution to frequent subgraph mining problem with huge number of mining results. Specifically, our solution is up to one order of magnitude faster than the best CPU-based approach on single node and presents a promising scalability of massive mining tasks in multi-node scenario. More source code are available at:Source Code: https://github.com/ysycloud/cmFSM. [ABSTRACT FROM AUTHOR]

In many scenarios, particularly scientific AI applications, algorithm engineers widely adopt more complex convolution, e.g. 3D CNN, to improve the accuracy. Scientific AI applications with 3D-CNN, which tends to train with volumetric datasets, substantially increase the size of the input, which in turn potentially restricts the channel sizes (e.g. less than 64) under the constraints of limited device memory capacity. Since existing convolution implementations tend to split and parallelize computing the small channel convolution from channel dimension, they usually cannot fully exploit the performance of GPU accelerator, in particular that configured with the emerging tensor core. In this work, we target on enhancing the performance of small channel 3D convolution on the GPU platform configured with tensor cores. Our analysis shows that the channel size of convolution has a great effect on the performance of existing convolution implementations, that are memory-bound on tensor core. By leveraging the memory hierarchy characteristics and the WMMA API of tensor core, we propose and implement holistic optimizations for both promoting the data access efficiency and intensifying the utilization of computing units. Experiments show that our implementation can obtain 1.1x–5.4x speedup comparing to the cuDNN's implementations for the 3D convolutions on different GPU platforms. We also evaluate our implementations on two practical scientific AI applications and observe up to 1.7x and 2.0x overall speedups compared with using cuDNN on V100 GPU. [ABSTRACT FROM AUTHOR]

The development of third-generation sequencing technology has brought significant changes and influences on genomics. Compared to the second-generation sequencing methods, the third-generation technologies produce around 100 times longer reads to reveal new genomic variations that complete long-term gaps in the human reference genome. However, these reads' excessive length and high error rate severely increase the amount of data and alignment cost. The traditional data analysis platform and serial sequence alignment method can not effectively deal with large-scale long read alignment. There is a critical need for a novel data analysis platform that can deliver fast alignment of large-scale sequences to solve the problem of long read alignment. High-performance computing platforms and efficient, scalable algorithms based on these platforms have significant potential to impact sequence analysis approaches. This paper presented minimapR, a multi-level parallel long-read alignment tool based on minimap2, a popular third-generation read aligner. MinimapR is developed based on the new high-performance distributed framework Ray. Ray fully integrates with the Python environment and can be easily installed with pip. MinimapR can utilize the power of multiple computing nodes, significantly accelerating alignment speeds without sacrificing sensitivity. The minimapR tool was tested on 64 nodes and demonstrated a 50 fold increase in speed with 78 % parallel efficiency. The source code and user manual of minimapR are freely available at https://github.com/Geehome/minimapR. [ABSTRACT FROM AUTHOR]

As mobile devices continuously generate streams of images and videos, intelligent mobile vision applications are rapidly emerging. An ideal object detection system for mobile vision applications should be accurate and real-time. Nevertheless, it is non-trivial to achieve these goals utilizing resource-constrained mobile devices. In this work, we propose an efficient and robust intelligent mobile vision system AREdge via small object aware parallel offloading. We find that the detection performance of small objects is a core factor that affects detection accuracy. To tackle this, we design a local lightweight DNN model that runs on mobile devices to detect big objects fast and identify the regions of interest (RoIs) that may have small objects. These areas are then cropped and offloaded to multiple edge servers for more accurate detection based on complex and large-scale DNN models. To further improve the performance, we propose a dynamic area-aware parallel offloading scheme for fine-grained parallel execution on multiple edge servers. Experimental results show that the accuracy of AREdge is 214. 27 % higher than that of the local detection in small objects. It also reduces the detection latency by 20. 68 % on average over the offloading method based on full images and well-used object detection models. [ABSTRACT FROM AUTHOR]

In this article, we present a new hybrid algorithm to enable and scale the high-performance conjugate gradients (HPCG) benchmark on large-scale heterogeneous systems such as the Tianhe-2. Based on an inner–outer subdomain partitioning strategy, the data distribution between host and device can be balanced adaptively. The overhead of data movement from both the MPI communication and the PCI-E transfer can be significantly reduced by carefully rearranging and fusing operations. A variety of parallelization and optimization techniques for performance-critical kernels are exploited and analyzed to maximize the performance gain on both host and device. We carry out experiments on both a small heterogeneous computer and the world’s largest one, the Tianhe-2. On the small system, a thorough comparison and analysis has been presented to select from different optimization choices. On Tianhe-2, the optimized implementation scales to the full-system level of 3.12 million heterogeneous cores, with an aggregated performance of 623 Tflop/s and a parallel efficiency of 81.2%. [ABSTRACT FROM AUTHOR]

The processing of massive numbers of small files is a challenge in the design of distributed file systems. Currently, the combined-block-storage approach is prevalent. However, the approach employs the traditional file systems such as ExtFS and may cause inefficiency when accessing small files randomly located in the disk. This paper focuses on optimizing the performance of data servers in accessing massive numbers of small files. We present a Flat Lightweight File System (iFlatLFS) to manage small files, which is based on a simple metadata scheme and a flat storage architecture. iFlatLFS is designed to substitute the traditional file system on data servers and can be deployed underneath distributed file systems that store massive numbers of small files. iFlatLFS can greatly simplify the original data access procedure. The new metadata proposed in this paper occupies only a fraction of the metadata size based on traditional file systems. We have implemented iFlatLFS in CentOS 5.5 and integrated it into an open source Distributed File System (DFS), called Taobao FileSystem (TFS), which is developed by a top B2C service provider, Alibaba, in China and is managing over 28.6 billion small photos. We have conducted extensive experiments to verify the performance of iFlatLFS. The results show that when the file size ranges from 1 to 64 KB, iFlatLFS is faster than Ext4 by 48 and 54 percent on average for random read and write in the DFS environment, respectively. Moreover, after iFlatLFS is integrated into TFS, iFlatLFS-based TFS is faster than the existing Ext4-based TFS by 45 and 49 percent on average for random read access and hybrid access (the mix of read and write accesses), respectively. [ABSTRACT FROM AUTHOR]

Energy efficiency is becoming an important requirement in more and more computing systems for optimizing resource allocation and task scheduling. By switching active copper Ethernet links to a low power model the IEEE 802.3az protocol can reduce the network energy consumption when no traffic exists. However, the effect of 802.3az heavily depends on network traffic patterns, which makes its utilization challenging in scheduling computing tasks. In this research, we examined the 802.3az technology with the goal of deploying it in distributed computing systems such as clusters. We devised an energy budget calculator that includes the energy model of 802.3az compliant Ethernet devices and supports the resource management service. We show a few practical examples of how applications can better plan their execution by integrating this knowledge in their decision strategies. We also present a solution for enhancing the calculator by using a semantic energy information system. [ABSTRACT FROM AUTHOR]

Numerical simulation of subcellular Ca2+ dynamics with a resolution down to one nanometre can be an important tool for discovering the physiological cause of many heart diseases. The requirement of enormous computational power, however, has made such simulations prohibitive so far. By using up to 12,288 Intel Xeon Phi 31S1P coprocessors on the new hybrid cluster Tianhe-2, which is the new number one supercomputer of the world, we have achieved 1.27 Pflop/s in double precision, which brings us much closer to the nanometre resolution. This is the result of efficiently using the hardware on different levels: (1) a single Xeon Phi (2) a single compute node that consists of a host and three coprocessors, and (3) a huge number of interconnected nodes. To overcome the challenge of programming Intel’s new many-integrated core (MIC) architecture, we have adopted techniques such as vectorization, hierarchical data blocking, register data reuse, offloading computations to the coprocessors, and pipelining computations with intra-/inter-node communications. [ABSTRACT FROM AUTHOR]

In this paper, we modify a classical downdating SVD algorithm and reduce its complexity significantly. We use a structured low-rank approximation algorithm to compute an hierarchically semiseparable (HSS) matrix approximation to the eigenvector matrix of a diagonal matrix plus rank-one modification. The complexity of our downdating algorithm is analyzed. We further show that the structured low-rank approximation algorithm is backward stable. Numerous experiments have been done to show the efficiency of our algorithm. For some matrices with large dimensions, our algorithm can be much faster than that using plain matrix–matrix multiplication routine in Intel MKL in both sequential and parallel cases. [ABSTRACT FROM AUTHOR]

Theeffects of intrinsic structural flexibility of calmodulin proteinon the mechanism of its allosteric conformational transition are investigatedin this article. Using a novel in silico approach, the conformationaltransition pathways of intact calmodulin as well as the isolated N-and C- terminal domains are identified and energetically characterized.It is observed that the central α-helix linker amplifies thestructural flexibility of intact Ca2+-free calmodulin,which might facilitate the transition of the two domains. As a result,the global conformational transition of Ca2+-free calmodulinis initiated by the barrierless transition of two domains and proceedsthrough the barrier associated unwinding and bending of the centralα-helix linker. The binding of Ca2+cations to calmodulinfurther increases the structural flexibility of the C-terminal domainand results in a downhill transition pathway of which all regionstransit in a concerted manner. On the other hand, the separation ofthe N- and C-terminal domains from calmodulin protein loses the mediatingfunction of central α-helix linker, leading to more difficultconformational transitions of both domains. The present study providesnovel insights into the correlation of the integrity of protein, thestructural flexibility, and the mechanism of conformational transitionof proteinlike calmodulin. [ABSTRACT FROM AUTHOR]

Influence Maximization aims to find the top-$(K)$ influential individuals to maximize the influence spread within a social network, which remains an important yet challenging problem. Proven to be NP-hard, the influence maximization problem attracts tremendous studies. Though there exist basic greedy algorithms which may provide good approximation to optimal result, they mainly suffer from low computational efficiency and excessively long execution time, limiting the application to large-scale social networks. In this paper, we present IMGPU, a novel framework to accelerate the influence maximization by leveraging the parallel processing capability of graphics processing unit (GPU). We first improve the existing greedy algorithms and design a bottom-up traversal algorithm with GPU implementation, which contains inherent parallelism. To best fit the proposed influence maximization algorithm with the GPU architecture, we further develop an adaptive $(K)$-level combination method to maximize the parallelism and reorganize the influence graph to minimize the potential divergence. We carry out comprehensive experiments with both real-world and sythetic social network traces and demonstrate that with IMGPU framework, we are able to outperform the state-of-the-art influence maximization algorithm up to a factor of 60, and show potential to scale up to extraordinarily large-scale networks. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents a compensated algorithm for the evaluation of the -th derivative of a polynomial in power basis. The proposed algorithm makes it possible the direct evaluation without obtaining the -th derivative expression of the polynomial itself, with a very accurate result to all but the most ill-conditioned evaluation. Forward error analysis and running error analysis are performed by an approach based on the data dependency graph. Numerical experiments illustrate the accuracy and efficiency of the algorithm. [Copyright &y& Elsevier]

Abstract: This paper presents a compensated algorithm to accurately evaluate a polynomial expressed in Chebyshev basis of the first and second kind with floating-point coefficients. The principle is to apply error-free transformations to improve the traditional Clenshaw algorithm. The new algorithm is as accurate as the Clenshaw algorithm performed in twice the working precision. Forward error analysis and numerical experiments illustrate the accuracy and properties of the proposed algorithm. [Copyright &y& Elsevier]

Abstract: Recent years have witnessed great success of manifold learning methods in understanding the structure of multidimensional patterns. However, most of these methods operate in a batch mode and cannot be effectively applied when data are collected sequentially. In this paper, we propose a general incremental learning framework, capable of dealing with one or more new samples each time, for the so-called spectral embedding methods. In the proposed framework, the incremental dimensionality reduction problem reduces to an incremental eigen-problem of matrices. Furthermore, we present, using this framework as a tool, an incremental version of Hessian eigenmaps, the IHLLE method. Finally, we show several experimental results on both synthetic and real world datasets, demonstrating the efficiency and accuracy of the proposed algorithm. [Copyright &y& Elsevier]

First principles calculation reveals that W-Cu interfaces have high interface strength when the number of overlayers is less than 2, and that (111)Cu/(110)W and (110)Cu/(110)W interfaces with one overlayer are both energetically favorable with big negative interface energies. Calculation also shows that negative interface energy serves as the driving force for interdiffusion and alloying of immiscible W and Cu, and that interface orientation fundamentally induces different behaviors of work functions of W-Cu interfaces. The calculated results agree well with experimental observations, and clarify two experimental controversies regarding interface stability and work function of W-Cu interfaces in the literature. [ABSTRACT FROM AUTHOR]