Mixture-of-Experts (MoE) models face memory and PCIe latency bottlenecks when deployed on commodity hardware. Offloading expert weights to CPU memory results in PCIe transfer latency that exceeds GPU computation by several folds. We present PreScope, a prediction-driven expert scheduling system that addresses three key challenges: inaccurate activation prediction, PCIe bandwidth competition, and cross-device scheduling complexity. Our solution includes: 1) Learnable Layer-Aware Predictor (LLaPor) that captures layer-specific expert activation patterns; 2) Prefetch-Aware Cross-Layer Scheduling (PreSched) that generates globally optimal plans balancing prefetching costs and loading overhead; 3) Asynchronous I/O Optimizer (AsyncIO) that decouples I/O from computation, eliminating waiting bubbles. PreScope achieves 141% higher throughput and 74.6% lower latency than state-of-the-art solutions.

In federated recommendation systems, model poisoning attacks aim to manipulate the gradient information of multiple target items sent back from local clients to the central server, with the goal of abnormally increasing their exposure across the system. Existing multi-target attack approaches directly manipulate multiple target items and apply a uniform attack strategy to all target items, which may lead to suboptimal promotion effectiveness. To address this issue, we introduce ProitMTA, a novel multi-target model poisoning attack framework that introduces proxy items and provides tailored attack strategies for target items. ProitMTA employs a three-stage process that balances the promotion of multiple target items while preserving recommendation quality. First,proxy item generationuses a Gaussian Mixture Model to create proxy items that represent diverse attack strategies. Second,proxy attack constructiondesigns customized gradient manipulation strategies for each proxy item. Finally,proxy-based target item attacktransfers these strategies to actual target items, enhancing their promotion while minimizing the negative impact on system performance. Through comprehensive experiments on multiple base federated recommendation frameworks and diverse real-world datasets, we demonstrate that ProitMTA outperforms existing attack methods, achieving higher success rates in target item promotion with minimal system-wide performance degradation. Our research highlights the vulnerability of federated recommendation systems when facing multi-target poisoning attacks and underscores the importance of researching effective defense mechanisms We have released our code athttps://github.com/zdy769243418/ProitMTA.

Cross-domain sequential recommendation (CSR) has garnered significant attention. Current federated frameworks for CSR leverage information across multiple domains but often rely on user alignment, which increases communication costs and privacy risks. In this work, we propose FedCSR, a novel federated cross-domain sequential recommendation framework that eliminates the need for user alignment between platforms. FedCSR fully utilizes cross-domain knowledge to address the key challenges related to data heterogeneity both inter- and intra-platform. To tackle the heterogeneity of data patterns between platforms, we introduce Model Contrastive Learning (MCL) to reduce the gap between local and global models. Additionally, we design Sequence Contrastive Learning (SCL) to address the heterogeneity of user preferences across different domains within a platform by employing tailored sequence augmentation techniques. Extensive experiments conducted on multiple real-world datasets demonstrate that FedCSR achieves superior performance compared to existing baseline methods.

Data prefetchers play a crucial role in alleviating the memory wall by predicting future memory accesses. First-level cache prefetchers can observe all memory instructions but often rely on simpler strategies due to limited resources. While emerging machine learning-based approaches cover more memory access patterns, they typically require higher computational and storage resources and are usually deployed in the last-level cache. Other intelligent solutions for the first-level cache show only modest performance gains. To address this, we propose Amphi, the first practical and intelligent data prefetcher specifically designed for the first-level cache. Applying a binarized temporal convolutional network, Amphi significantly reduces storage overhead while maintaining performance comparable to the SOTA intelligent prefetcher. With a storage overhead of only 3.4 KB, Amphi requires only one-eighth of Pythia's storage needs. Amphi paves the way for the broader adoption of intelligence-driven prefetching solutions.

As network simulations scale to hundreds of thousands of nodes, parallel discrete event simulation (PDES) has become indispensable for sustaining performance—yet its efficacy hinges on frequent time synchronization steps. Existing synchronization algorithms suffer from the inter-machine communication overhead in distributed environments, eroding the benefits of parallelism. We observe that time synchronization in PDES often involves frequent allreduce operations, and that in-network computing has the potential to substantially accelerate such collectives. In this work, we present SINA (Synchronization using In-Network Allreduce)—the first integration of in-network computing into time synchronization to address the demands of large-scale simulations. We implemented SINA in a testbed with Mellanox SHArP-enabled switches and ConnectX-5 network cards, offloading allreduce to the network hardware while preserving software‑level correctness. Our evaluation shows that SINA achieves up to 88.6% acceleration compared to state‑of‑the‑art methods and achieves up to 67.5% optimization in topologies of tens of thousands of nodes, demonstrating its suitability for high‑performance, large‑scale parallel simulations.

Differential testing is a prevalent strategy for establishing test oracles in automated DBMS testing. However, meticulously selecting equivalent DBMSs with diverse implementations and compatible input syntax requires huge manual efforts. In this paper, we propose Thanos, a framework that finds DBMS bugs via storage engine rotation based differential testing. Our key insight is that a DBMS with different storage engines must provide consistent basic storage functionalities. Therefore, it's feasible to construct equivalent DBMSs based on storage engine rotation, ensuring that the same SQL test cases to these equivalent DBMSs yield consistent results. The framework involves four main steps: 1) select the appropriate storage engines; 2) extract equivalence information among the selected storage engines; 3) synthesize feature-orient test cases that ensure the DBMS equivalence; and 4) send test cases to the DBMSs with selected storage engines and compare the results. We evaluate Thanos on three widely used and extensively tested DBMSs, namely MySQL, MariaDB, and Percona against state-of-the-art fuzzers SQLancer, SQLsmith, and SQUIRREL. Thanos outperforms them on branch coverage by 24%-116%, and also finds many bugs missed by other fuzzers. More importantly, the vendors have confirmed 32 previously unknown bugs found by Thanos, with 29 verified as Critical.

Recently, large language models (LLMs) have shown strong potential in code generation tasks. However, there are still gaps before they can be fully applied in actual software development processes. Accurately assessing the code generation capabilities of large language models has become an important basis for evaluating and improving the models. Some existing works have constructed datasets to evaluate the capabilities of these models. However, the current evaluation process may encounter the illusion of “Specialist in Familiarity”, primarily due to three gaps: the exposure of target code, case timeliness, and dependency availability. The fundamental reason for these gaps is that the code in current datasets may have been extensively exposed and exercised during the training phase, and due to the continuous training and development of LLM, their timeliness has been severely compromised. The key to solve the problem is to, as much as possible, evaluate the LLMs using code that they have not encountered before. Thus, the fundamental idea in this paper is to draw on the concept of code obfuscation, changing code at different levels while ensuring the functionality and output. To this end, we build a code-obfuscation based benchmark OBFusEvAL. We first collect 1,354 raw cases from five real-world projects, including function description and code. Then we use three-level strategy (symbol, structure and semantic) to obfuscate descriptions, code and context dependencies. We evaluate four LLMs on Obfu-sevaland compared the effectiveness of different obfuscation strategy. We use official test suites of these projects to evaluate the generated code. The results show that after obfuscation, the average decrease ratio of test pass rate can up to 62.5%.

This brief is concerned with the prediction problem of product popularity under a social network (SN) with positive-negative diffusion (PND). First, a PND model is proposed to enable the simulation of product diffusion, and three user states are defined. Second, an optimal and precise feature vector of every user is extracted through a multi-agent-system-based attention mechanism (MASAM) that is devised. The weight matrix shared in the mechanism of all agents is learned using a distributed learning algorithm provided in MASAM. Third, an MAS model for product diffusion on SN is established based on the feature representations from MASAM. Rules for agent interaction during PND diffusion are suggested, which accelerate the simulation of information spread in SN. Finally, comprehensive experiments are conducted to verify the effectiveness and efficiency of the proposed models and algorithms in prediction and to compare their performance with baseline methods. Furthermore, a case study is provided to illustrate the applicability and extendibility of the developed algorithm.

This article addresses the issue of multiple influences maximization under dynamic link strength (MIMDLS) in multi-agent systems (MASs). Initially, a novel model for dynamic link strength within MASs is suggested to facilitate the simulation of multiple influences diffusion. Subsequently, the MIMDLS problem is formulated with both competitive and cooperative scenarios being examined. In response, two diffusion models, specifically the competitive multiple influences independent cascade (Cp-MIIC) model and the cooperative multiple influences linear threshold (Cr-MILT) model, are designed for MASs. Furthermore, a distributed deep reinforcement learning (DRL) framework is established based on MASs by incorporating asynchronous training and updating processes for seed selection in the context of multiple influences. Moreover, the developed distributed DRL algorithm encompasses the estimation of Q value as well as the management of constraints within Cp-MIIC and Cr-MILT models. Finally, comprehensive experiments are conducted to: 1) validate the effectiveness and efficiency of the proposed models and algorithms in terms of multiple influence diffusion and 2) benchmark their performance against state-of-the-art methods.

Code comment generation aims at generating natural language descriptions for a code snippet to facilitate developers' program comprehension activities. Despite being studied for a long time, a bottleneck for existing approaches is that given a code snippet, they can only generate one comment while developers usually need to know information from diverse perspectives such as what is the functionality of this code snippet and how to use it. To tackle this limitation, this study empirically investigates the feasibility of utilizing large language models (LLMs) to generate comments that can fulfill developers' diverse intents. Our intuition is based on the facts that (1) the code and its pairwise comment are used during the pre-training process of LLMs to build the semantic connection between the natural language and programming language, and (2) comments in the real-world projects, which are collected for the pre-training, usually contain different developers' intents. We thus postulate that the LLMs can already understand the code from different perspectives after the pre-training. Indeed, experiments on two large-scale datasets demonstrate the rationale of our insights: by adopting the in-context learning paradigm and giving adequate prompts to the LLM (e.g., providing it with ten or more examples), the LLM can significantly outperform a state-of-the-art supervised learning approach on generating comments with multiple intents. Results also show that customized strategies for constructing the prompts and post-processing strategies for reranking the results can both boost the LLM's performances, which shed light on future research directions for using LLMs to achieve comment generation.

Many programming languages and operating system communities maintain software repositories to build their own ecosystems. The repositories often provide management tools to help users using the packages. The tools are often, if not all the times, well-designed to handle intra-repository dependencies without considering inter-repository dependencies. The users, however, often need packages from different repositories, and thus may suffer from compatibility issues. We refer to these issues as Cross-repository Compatibility (CC) issues. Existing works typically focus on a single software repository and are insufficient to detect CC issues.

Abstract 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.

As pre-trained models automate many code intel-ligence tasks, a widely used paradigm is to fine-tune a model on the task dataset for each programming language. A recent study reported that multilingual fine-tuning benefits a range of tasks and models. However, we find that multilingual fine-tuning leads to performance degradation on recent models UniXcoder and CodeT5. To alleviate the potentially catastrophic forgetting issue in multilingual models, we fix all pre-trained model parameters, insert the parameter-efficient structure adapter, and fine-tune it. Updating only 0.6% of the overall parameters compared to full-model fine-tuning for each programming language, adapter tuning yields consistent improvements on code search and sum-marization tasks, achieving state-of-the-art results. In addition, we experimentally show its effectiveness in cross-lingual and low-resource scenarios. Multilingual fine-tuning with 200 samples per programming language approaches the results fine-tuned with the entire dataset on code summarization. Our experiments on three probing tasks show that adapter tuning significantly outperforms full-model fine-tuning and effectively overcomes catastrophic forgetting.

Software systems introduce an increasing number of configuration options to provide flexibility, and support updating the options on the fly to provide persistent services. This mechanism, however, may affect the system reliability, leading to unexpected results like software crashes or functional errors. In this paper, we refer to the bugs caused by on-the-fly configuration updates as on-the-fly configuration bugs, or OCBugs for short. In this paper, we conducted the first in-depth study on 75 real-world OCBugs from 5 widely used systems to understand the symptoms, root causes, and triggering conditions of OCBugs. Based on our study, we designed and implemented Parachute, an automated testing framework to detect OCBugs. Our key insight is that the value of one configuration option, either loaded at the startup phase or updated on the fly, should have the same effects on the target program. Parachute generates tests for on-the-fly configuration updates by mutating the existing tests and conducts differential analysis to identify OCBugs. We evaluated Parachute on 7 real-world software systems. The results show that Parachute detected 75% (42/56) of the known OCBugs, and reported 13 unknown bugs, 11 of which have been confirmed or fixed by developers until the time of writing.

Code search aims to search for relevant code snippets through queries, which has become an essential requirement to assist programmers in software development. With the availability of large and rapidly growing source code repositories covering various languages, multilingual code search can leverage more training data to learn complementary information across languages. Contrastive learning can naturally understand the similarity between functionally equivalent code across different languages by narrowing the distance between objects with the same function while keeping dissimilar objects further apart. Some works exist addressing monolingual code search problems with contrastive learning, however, they mainly exploit every specific programming language’s textual semantics or syntactic structures for code representation. Due to the high diversity of different languages in terms of syntax, format, and structure, these methods limit the performance of contrastive learning in multilingual training. To bridge this gap, we propose a unified semantic graph representation approach toward multilingual code search called MulCS. Specifically, we first design a general semantic graph construction strategy across different languages by Intermediate Representation (IR). Furthermore, we introduce the contrastive learning module integrated into a gated graph neural network (GGNN) to enhance query-multilingual code matching. The extensive experiments on three representative languages illustrate that our method outperforms state-of-the-art models by 10.7% to 77.5% in terms of MRR on average.

NVMe SSD hugely boosts the I/O speed, with up to GB/s throughput and microsecond-level latency. Unfortunately, DBMS users can often find their high-performanced storage devices tend to deliver less-than-expected or even worse performance when compared to their traditional peers. While many works focus on proposing new DBMS designs to fully exploit NVMe SSDs, few systematically study the symptoms, root causes and possible detection methods of such performance mismatches on existing databases. In this paper, we start with an empirical study where we systematically expose and analyze the performance mismatches on six popular databases via controlled configuration tuning. From the study, we find that all six databases can suffer from performance mismatches. Moreover, we conclude that the root causes can be categorized as databases' unawareness of new storage devices characteristics in I/O size, I/O parallelism and I/O sequentiality. We report 17 mismatches to developers and 15 are confirmed. Additionally, we realize testing all configuration knobs yields low efficiency. Therefore, we propose a fast performance mismatch detection framework and evaluation shows that our framework brings two orders of magnitude speedup than baseline without sacrificing effectiveness.

Intensive communication and synchronization cost for gradients and parameters is the well-known bottleneck of distributed deep learning training. Based on the observations that Synchronous SGD (SSGD) obtains good convergence accuracy while asynchronous SGD (ASGD) delivers a faster raw training speed, we propose Several Steps Delay SGD (SSD-SGD) to combine their merits, aiming at tackling the communication bottleneck via communication sparsification. SSD-SGD explores both global synchronous updates in the parameter servers and asynchronous local updates in the workers in each periodic iteration. The periodic and flexible synchronization makes SSD-SGD achieve good convergence accuracy and fast training speed. To the best of our knowledge, we strike the new balance between synchronization quality and communication sparsification, and improve the tradeoff between accuracy and training speed. Specifically, the core components of SSD-SGD include proper warm-up stage, steps delay stage, and the novel algorithm of global gradient for local update (GLU). GLU is critical for local update operations by using global gradient information to effectively compensate for the delayed local weights. Furthermore, we implement SSD-SGD on MXNet framework and comprehensively evaluate its performance with CIFAR-10 and ImageNet datasets. Experimental results show that SSD-SGD can accelerate distributed training speed under different experimental configurations, by up to 110% (or 2.1× of the original speed), while achieving good convergence accuracy.

Optimal path planning is one of the major bottlenecks for the effective navigation of robots working towards accomplishing complex missions. To overcome the bottleneck and support efficient applications, this paper presentsAAPP, an accelerative and adaptive path planner based on RRT*, a popular path planning algorithm, on GPU, to alleviate four main performance limitations, i.e., bandwidth limitation, load imbalance, high computing complexity, and the choice of parameters. First,AAPPemploys a data storage structure, named simplified compressed sparse rows (SCSR), to compress the large-scale map data and increase the utilization of bandwidth. Second, to exploit the computing performance of GPU, we propose a two-layer parallel framework for RRT* based on SCSR format, named TLRRT*, by using the dynamic parallelism technique. Third, aiming at the problems of parallel load imbalance and high computing complexity in TLRRT*, we further design a two-stage parallel framework, named TSRRT*, that fully exploits hardware heterogeneity (CPU/GPU) by scheduling tasks on CPU and GPU adaptively. Finally, we present optimizations forAAPPto adaptively select execution schemes and parameters. Experimental results on a heterogeneous CPU/GPU machine show thatAAPPyields the speedup up to$22.72\times$over the RRT* algorithm. Compared to the state-of-the-art,AAPPcan handle large-scale datasets and obtain feasible solutions with shorter trajectory lengths.

This article is concerned with the influence maximization (IM) problem under a network with probabilistically unstable links (PULs) via graph embedding for multiagent systems (MASs). First, two diffusion models, the unstable-link independent cascade (UIC) model and the unstable-link linear threshold (ULT) model, are designed for the IM problem under the network with PULs. Second, the MAS model for the IM problem with PULs is established and a series of interaction rules among agents are built for the MAS model. Third, the similarity of the unstable structure of the nodes is defined and a novel graph embedding method, termed the unstable-similarity2vec (US2vec) approach, is proposed to tackle the IM problem under the network with PULs. According to the embedding results of the US2vec approach, the seed set is figured out by the developed algorithm. Finally, extensive experiments are conducted to: 1) verify the validity of the proposed model and the developed algorithms and 2) illustrate the optimal solution for IM under different scenarios with PULs.

Multiobjective orienteering problems (MO-OPs) are classical multiobjective routing problems and have received much attention in recent decades. This study seeks to solve MO-OPs through a problem-decomposition framework, that is, an MO-OP is decomposed into a multiobjective knapsack problem (MOKP) and a traveling salesman problem (TSP). The MOKP and TSP are then solved by a multiobjective evolutionary algorithm (MOEA) and a deep reinforcement learning (DRL) method, respectively. While the MOEA module is for selecting cities, the DRL module is for planning a Hamiltonian path for these cities. An iterative use of these two modules drives the population toward the Pareto front of MO-OPs. The effectiveness of the proposed method is compared against NSGA-II and NSGA-III on various types of MO-OP instances. Experimental results show that our method performs best on almost all the test instances and has shown strong generalization ability.

Logs are pervasive in modern computing systems, and are valuable to service and system management. Nevertheless, with the rapidly growing size and complexity of computing systems, the log volume is exploding, which makes automatic log analysis imperative. Generally, in automatic log analysis, the first and fundamental step is log parsing, to which a lot of effort has been devoted. However, in most existing log parsing methods, log messages are merely treated as plain text. In natural language processing (NLP) area, it is a common practice to represent words and sentences with vectors, then the similarity between two words or sentences can be measured by the distance between their vectors. Inspired by these, we put forward a novel log parsing framework, named LPV (LogParser based onVectorization), which performs log parsing by converting log messages and log templates into vectors, with the help of a vectorization method in NLP. LPV incorporates offline and online log parsing. In the offline log parsing, the central idea is to first represent log messages with vectors, so that the similarity between two log messages can be measured by the distance between their vectors, then we cluster log messages via clustering the vectors, and finally we extract log templates from the resultant clusters. By the end of the offline log parsing, each log template is assigned with an average vector, so that in the online log parsing, the similarity between an incoming log message and each log template can also be measured by the distance between their vectors. Extensive experiments have been conducted based on several public log datasets to evaluate LPV with three different vectorization methods. The results demonstrate that, with a proper vectorization method, LPV performs competitive with state-of-the-art log parsing methods, in both effectiveness and efficiency.

With the rapid increase of public code repositories, developers maintain a great desire to retrieve precise code snippets by using natural language. Despite existing deep learning-based approaches that provide end-to-end solutions (i.e., accept natural language as queries and show related code fragments), the performance of code search in the large-scale repositories is still low in accuracy because of the code representation (e.g., AST) and modeling (e.g., directly fusing features in the attention stage). In this paper, we propose a novel learnable de ep G raph for C ode S earch (called deGraphCS ) to transfer source code into variable-based flow graphs based on an intermediate representation technique, which can model code semantics more precisely than directly processing the code as text or using the syntax tree representation. Furthermore, we propose a graph optimization mechanism to refine the code representation and apply an improved gated graph neural network to model variable-based flow graphs. To evaluate the effectiveness of deGraphCS , we collect a large-scale dataset from GitHub containing 41,152 code snippets written in the C language and reproduce several typical deep code search methods for comparison. The experimental results show that deGraphCS can achieve state-of-the-art performance and accurately retrieve code snippets satisfying the needs of the users.

The past several years have witnessed tremendous success of transformer models in natural language processing (NLP), and their current landscape is increasingly diverse. Although GPU gradually becomes the dominating workhorse and de facto standard for deep learning, there are still many scenarios where using CPU remains a prevalent choice.Recently, ARM many-core processor starts emigrating to cloud computing and high-performance computing, which is promising to deploy transformer inference. In this paper, we identify several performance bottlenecks of existing inference runtime on many-core CPU including low-core usage, isolated thread configuration, inappropriate implementation of general matrix multiply (GEMM), and redundant computations for variable-length inputs. To tackle these problems, full-stack optimizations are conducted for these challenges from service level to operator level. We explore multi-instance parallelization at the service level to improve CPU core usage. To improve parallel efficiency of the inference runtime, we design NUMA-aware thread scheduling and a look-up table for optimal parallel configurations. The GEMM implementation is tailored for some critical modules to exploit the characteristics of transformer workload. To eliminate redundant computations, a novel storage format is designed and implemented to pack sparse data and a load balancing strategy is proposed for tasks with different sparsity. Experiments show that our implementation can outperform existing solutions by 1.1x to 6x with fixed-length inputs. For variable-length inputs, it achieves 1.9x to 8x speedups on different ARM many-core processors.

Deep learning's widespread adoption in various fields has made distributed training across multiple computing nodes essential. However, frequent communication between nodes can significantly slow down training speed, creating a bottleneck in distributed training. To address this issue, researchers are focusing on communication optimization algorithms for distributed deep learning systems. In this paper, we propose a standard that systematically classifies all communication optimization algorithms based on mathematical modeling, which is not achieved by existing surveys in the field. We categorize existing works into four categories based on the optimization strategies of communication: communication masking, communication compression, communication frequency reduction, and hybrid optimization. Finally, we discuss potential future challenges and research directions in the field of communication optimization algorithms for distributed deep learning systems.

Detecting anomalies in logs is crucial for service and system management, since logs are widely used to record the runtime status, and are often the only data available for postmortem analysis. Since anomalies are usually rare in real-world services and systems, a common and feasible practice is to mine or learn normal patterns from logs, and deem those violating the normal patterns as anomalies. As log sequences are a kind of time series data, RNN (Recurrent Neural Network) and its variants have been extensively employed to capture the normal patterns. Nevertheless, the sequential nature of RNN and its variants makes them hard to parallelize and capture long-term dependencies, which may hinder their performance. To address this issue, in this paper we propose Loader, a novel semi-supervisedloganomalydetector based on Transformer, because the Transformer architecture eschews recurrence and is able to draw global dependencies. Loader leverages the Transformer encoder to capture normal patterns from normal log sequences. When detecting, it gives a set of candidate log templates, that may appear after the input log substring under normal conditions. If the template of the actual next log message is not within the candidate set, this implies an anomaly. Previous similar methods select the most possible$k$log templates as candidates in any case, so the performance is sensitive to$k$, and it is nontrivial to pick a proper$k$. To alleviate this, we design a more flexible and robust ‘top-$p$’ algorithm, which determines the candidate set based on the cumulative probability of the most possible log templates. Extensive experiments are conducted based on three public log datasets, the experimental results validate the effectiveness and competitiveness of our approach.

Congestion control is crucial for the overall performance of data center networks and still faces considerable challenges. Recently, credit-driven congestion control has been emerging to enable precise flow control for current high-speed and highly dynamic data centers. However, existing credit-driven methods essentially separate credit and data packets, i.e., credits can fully regulate data packets, but they receive little feedback from the data packets. Accordingly, these approaches inevitably struggle with lossy credits and impaired throughput. To address the issue, we present data-credit-coupling congestion control named DC4. For a better understanding of the relationship between data and credit, we revisit the principle of credit-based congestion control and make the first attempt to explore the art of presenting the data-credit plane architecture. Based on the proposed data-credit framework, DC4 transforms the interaction between credit and data packets from one-way control to two-way coordination to achieve mutual benefits and dynamic balances between the credit and data packets. We conduct extensive experiments to evaluate the performance of our design and compare it with state-of-the-art protocols, including HPCC, ExpressPass, and Aeolus. Experimental results show that DC4 outperforms data-credit-separated approaches in terms of the flow completion time, throughput, and credit waste.

Automatic configuration tuning helps users who intend to improve software performance. However, the auto-tuners are limited by the huge configuration search space. More importantly, they focus only on performance improvement while being unaware of other important user intentions (e.g., reliability, security). To reduce the search space, researchers mainly focus on pre-selecting performance-related parameters which requires a heavy stage of dynamically running under different configurations to build performance models. Given that other important user intentions are not paid attention to, we focus on guiding users in pre-selecting performance-related parameters in general while warning about side-effects on non-performance intentions. We find that the configuration document often, if it does not always, contains rich information about the parameters' relationship with diverse user intentions, but documents might also be long and domain-specific.

With the great success of pre-trained models, the pretrain-then-finetune paradigm has been widely adopted on downstream tasks for source code understanding. However, compared to costly training a large-scale model from scratch, how to effectively adapt pre-trained models to a new task has not been fully explored. In this paper, we propose an approach to bridge pre-trained models and code-related tasks. We exploit semantic-preserving transformation to enrich downstream data diversity, and help pre-trained models learn semantic features invariant to these semantically equivalent transformations. Further, we introduce curriculum learning to organize the transformed data in an easy-to-hard manner to fine-tune existing pre-trained models.

Understanding the I/O characteristics of applications on supercomputers is crucial to paving the path for application optimization and system resource allocation. We collect and analyze I/O traces of applications on a production supercomputer and reconfirm that I/O bursts exist in most applications. What's more, we find that the I/O bursts not only occur in short periods of time but also originate from a minority of adjacent compute nodes allocated to the applications, which we call spatiotemporal I/O burstiness. The concentration of I/O traffic in both time and space dimension will make applications experience poor I/O performance and incur I/O inefficiency of the storage system. Although there are some solutions, such as burst buffer, can help alleviate such inefficiency, there is still no work that measures, analyzes and further predicts the application I/O characteristic in terms of spatiotemporal burstiness, which we think is vital for application-aware optimizations, including but not limited to burst buffer allocation and job scheduling. In this paper, we first propose a mathematical model to measure the spatiotemporal I/O burstiness. Then a thorough analysis on the spatiotemporal I/O characteristic of all applications on the system is elaborated. We further make use of the job's submitting path to explore the I/O characteristic similarity among jobs, based on which a machine learning classification algorithm is proposed to accurately predict the job spatiotemporal I/O burstiness in advance. With accurate job I/O characteristic at hand, some useful suggestions are put forward to hedge the impacts of the spatiotemporal I/O burstiness.

Code comment, i.e., the natural language text to describe code, is considered as a killer for program comprehension. Current literature approaches mainly focus on comment generation or comment update, and thus fall short on explaining which part of the code leads to a specific content in the comment. In this paper, we propose that addressing such a challenge can better facilitate code understanding. We propose Fosterer, which can build fine-grained semantic interactions between code statements and comment tokens. It not only leverages the advanced deep learning techniques like cross-modal learning and contrastive learning, but also borrows the weapon of pre-trained vision models. Specifically, it mimics the comprehension practice of developers, treating code statements as image patches and comments as texts, and uses contrastive learning to match the semantically-related part between the visual and textual information. Experiments on a large-scale manually-labelled dataset show that our approach can achieve an F1-score around 80%, and such a performance exceeds a heuristic-based baseline to a large extent. We also find that Fosterer can work with a high efficiency, i.e., it only needs 1.5 seconds for inferring the results for a code-comment pair. Furthermore, a user study demonstrates its usability: for 65% cases, its prediction results are considered as useful for improving code understanding. Therefore, our research sheds light on a promising direction for program comprehension.

Meta-path-based random walk strategy has attracted tremendous attention in heterogeneous network representation, which can capture network semantics with heterogeneous neighborhoods of nodes. Despite the success of meta-path-based random walk strategy in plain heterogeneous networks which contain no attributes, it remains unexplored how meta-path-based random walk strategy could be utilized on attributed heterogeneous networks to simultaneously capture structural heterogeneity and attribute proximity. Moreover, the importance of node attributes and structural relations generally varies across data sets, thus requiring careful considerations when they are incorporated into representations. To tackle these problems, we propose a novel method, Attributed Heterogeneous Network embedding based on Aggregate-path (AHNA), which generates aggregate-path-based random walks on attributed heterogeneous networks and adaptively fuses topological structures and node attributes based on the learned importance. Specifically, AHNA first converts node attributes to additional links in the network to deal with the heterogeneity of structures and attributes, which is followed by an adaptive random walk strategy to strike the importance balance between node attributes and topological structures, thereby generating high-quality representations. Extensive experiments are conducted on three real-world data sets, where AHNA outperforms state-of-the-art approaches by up to 22.7%, 2.6%, and 2.3% on link prediction, community detection, and node classification, respectively. Moreover, our qualitative analysis indicates that AHNA can capture different balances of topological structures and node attributes on various data sets and thus boost the quality of node representations.

Convolutional neural networks (CNNS) enable machines to view the world as humans and become increasing prevalent for Internet of Things (IoT) applications. Instead of streaming the raw data to the cloud and executing CNN inference remotely, it would be very attractive to use local IoT devices to process as it enables IoT applications with independent decision-making ability. Since a single IoT device can hardly match the requirements of the CNN inference, especially for time-sensitive and high-accuracy tasks, the distributedin-situCNN inference becomes a potential solution. However, because of the inherently tightly coupled structure of existing CNN models, it is difficult to distribute the inference efficiently. In this article, we enhance the distributedin-situCNN inference in the IoT. We fundamentally reduce the communication overhead of distributed CNN inference by designing new loosely coupled structure (LCS). Experimental results demonstrate that LCS achieves the leading performance compared with other popular structures. Next, based on the LCS, we customize the partitioning method to reduce the synchronization points and design the decentralized asynchronous method to optimize communication in each synchronization point. To evaluate the effectiveness, we build a prototype system. When the number of IoT devices increases from 1 to 4, our system accelerates by up to$3.85\times $and reduces the memory footprint in each device by 70% with achieving a competitive accuracy and significantly outperforming other approaches.

As an important pipeline stage in the router of Network-on-Chips, switch allocation assigns output ports to input ports and allows flits to transit through the switch without conflicts. Previous work designed efficient switch allocation strategies by maximizing the matching efficiency in time series. However, those works neglected the interaction between different router pipeline stages. In this article, we propose the concept of Utility-of-Allocation (UoA) to indicate the quality of allocation to be practically used in on-chip routers. We demonstrate that router pipelines can interact with each other, and the UoA can be maximized if the interaction between router pipelines is taken into consideration. Based on these observations, a novel class of routers, MUA-Router, is proposed to maximize the UoA through the collaborative design (co-design) between router pipelines. MUA-Router achieves this goal in two ways and accordingly implements two novel instance router architectures. In the first, MUA-Router improves the UoA by mitigating the impact of endpoint congestion in the switch allocation, and thus Eca-Router is proposed. Eca-Router achieves an endpoint-congestion-aware switch allocation through the co-design between routing computation and switch allocation. Based on Eca-Router, CoD-Router is proposed to feed back switch allocation information to routing computation stage to provide switch allocator with more conflict-free requests. Through the co-design between pipelines, MUA-Router significantly improves the efficiency of switch allocation and the performance of the entire network. Evaluation results show that our design can achieve significant performance improvement with moderate overheads.

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.

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.

Conventional deep learning-based Relation Classification (RC) methods heavily rely on large-scale training dataset and fail to generalize to unseen classes when training data is scant. This work concentrates on RC tasks in few-shot scenarios in which models classify the unlabelled samples given only few labeled samples. Existing few-shot RC models consider the dataset as a series of individual instances and have not fully utilized interaction information among them. Interaction information is conducive to indicate the important areas and produce discriminating representations. So this paper proposes a novel interactive attention network (IAN) which uses inter-instance and intra-instance interactive information to classify the relations. Inter-instance interactive information is first introduced to solve the low-resource problem by capturing the semantic relevance between an instance pair. Intra-instance interactive information is then introduced to address the ambiguous relation classification issue by extracting the entity information inner an instance. Extensive numerical experimental results demonstrate the proposed method promotes the accuracy of down-stream task.

Communication overhead is the key challenge for distributed training. Gradient compression is a widely used approach to reduce communication traffic. When combining 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 delayed full-gradient compensation, and propose a new distributed optimization method named CD-SGD, which can hide the overhead of gradient compression, overlap part of the communication and obtain high convergence accuracy. The local update operation in CD-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 CD-SGD. We prove that CD-SGD has convergence guarantee and it achieves at least convergence rate. We conduct extensive experiments on MXNet to verify the convergence properties and scaling performance of CD-SGD. Experimental results on a 16-GPU cluster show that convergence accuracy of CD-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.

Applications depend on libraries to avoid reinventing the wheel. Libraries may have incompatible changes during evolving. As a result, applications will suffer from compatibility failures. There has been much research on addressing detecting incompatible changes in libraries, or helping applications co-evolve with the libraries. The existing solution helps the latest application version work well against the latest library version as an afterthought. However, end users have already been suffering from the failures and have to wait for new versions. In this paper, we propose DepOwl, a practical tool helping users prevent compatibility failures. The key idea is to avoid using incompatible versions from the very beginning. We evaluated DepOwl on 38 known compatibility failures from StackOverflow, and DepOwl can prevent 35 of them. We also evaluated DepOwl using the software repository shipped with Ubuntu-19.10. DepOwl detected 77 unknown dependency bugs, which may lead to compatibility failures.

Large-scale deep neural networks training have been widely deployed on dense-GPU public cloud clusters. Intensive communication and synchronization cost for gradients and parameters is becoming the bottleneck of distributed deep learning training. Horovod is one of the most popular distributed communication frameworks to address the scale-out issue of deep learning training on GPU clusters. Existing public-cloud GPU datacenters, such as Amazon EC2 and Alibaba GPU cloud, are usually equipped with commodity high-speed Ethernet and TCP networking. In current vanilla Horovod, however, we observe that one GPU device is merely associated with at most one proxy communication process. The proxy process is responsible for dealing with all the communication operations of parameter all-reduce for one or multiple GPUs. Such configuration makes communication interface based on TCP protocols suffer from limited network goodput and incur training performance penalties. In this paper, we make the first attempt to improve the message passing interface of Horovod and address the mismatching between the computation and communication capability when deploying Horovod in TCP-based public-cloud GPU clusters. We propose FastHorovod to exploit more cost-efficient auxiliary communication processes on CPU to expedite parallel message-passing schedule for GPU. We conduct extensive experiments against state-of-the-art Horovod. The experiment results show that our design can significantly accelerate the distributed training communication on TCP-based public-cloud GPU clusters, and FastHorovod improves the training speed of AlexNet and VGG16 models by 64.5% and 72.6% respectively.

Configuration error injection testing (CEIT) could systematically evaluate software reliability and diagnosability to runtime configuration errors. This paper explores the challenges and opportunities of applying CEIT technique. We build an extensible, highly-modularized CEIT framework named CeitInspector to experiment with various CEIT techniques. Using CeitInspector, we quantitatively measure the effectiveness and efficiency of CEIT using six mature and widely-used server applications. During this process, we find a fair number of test cases are left unstudied by the prior research work. The injected configuration errors in these cases often indicate latent misconfigurations, which might be ticking time bombs in the system and lead to severe damage. We conduct an in-depth study regarding these cases to reveal the root causes, and explore possible remedies. Finally, we come up with actionable suggestions guided by our study to improve the effectiveness and efficiency of the existing CEIT techniques.

Misconfigurations have become the dominant causes of software failures in recent years, drawing tremendous attention for their increasing prevalence and severity. Configuration constraints can preemptively avoid misconfiguration by defining the conditions that configuration options should satisfy. Documentation is the main source of configuration constraints, but it might be incomplete or inconsistent with the source code. In this regard, prior researches have focused on obtaining configuration constraints from software source code through static analysis. However, the difficulty in pointer analysis and context comprehension prevents them from collecting accurate and comprehensive constraints. In this paper, we observed that software logs often contain configuration constraints. We conducted an empirical study and summarized patterns of configuration-related log messages. Guided by the study, we designed and implemented ConfInLog, a static tool to infer configuration constraints from log messages. ConfInLog first selects configuration-related log messages from source code by using the summarized patterns, then infers constraints from log messages based on the summarized natural language patterns. To evaluate the effectiveness of ConfInLog, we applied our tool on seven popular open-source software systems. ConfInLog successfully inferred 22~163 constraints, in which 59.5%~ 61.6% could not be inferred by the state-of-the-art work. Finally, we submitted 67 documentation patches regarding the constraints inferred by ConfInLog. The constraints in 29 patches have been confirmed by the developers, among which 10 patches have been accepted.

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 .

Script is the structured knowledge representation of prototypical real-life event sequences. Learning the commonsense knowledge inside the script can be helpful for machines in understanding natural language and drawing commonsensible inferences. Script learning is an interesting and promising research direction, in which a trained script learning system can process narrative texts to capture script knowledge and draw inferences. However, there are currently no survey articles on script learning, so we are providing this comprehensive survey to deeply investigate the standard framework and the major research topics on script learning. This research field contains three main topics: event representations, script learning models, and evaluation approaches. For each topic, we systematically summarize and categorize the existing script learning systems, and carefully analyze and compare the advantages and disadvantages of the representative systems. We also discuss the current state of the research and possible future directions.

Hierarchical organization is widely used in high-radix routers to enable efficient scaling to higher switch port count. A general-purpose hierarchical router must be symmetrically designed with the same input buffer depth, resulting in a large amount of unused input buffers due to the different link lengths. Sharing input buffers between different input ports can improve buffer utilization, but the implementation overhead also increases with the number of shared ports. Previous work allowed input buffers to be shared among all router ports, which maximizes the buffer utilization but also introduces higher implementation complexity. Moreover, such design can impair performance when faced with long packets, due to the head-of-line blocking in intermediate buffers. In this work, we explain that sharing unused buffers between a subset of router ports is a more efficient design. Based on this observation, we propose Centralized Input Buffer Design in Hierarchical High-radix Routers (CIB-HIER), a novel centralized input buffer design for hierarchical high-radix routers. CIB-HIER integrates multiple input ports onto a single tile and organizes all unused input buffers in the tile as a centralized input buffer. CIB-HIER only allows the centralized input buffer to be shared between ports on the same tile, without introducing additional intermediate virtual channels or global scheduling circuits. Going beyond the basic design of CIB-HIER, the centralized input buffer can be used to relieve the head-of-line blocking caused by shallow intermediate buffers, by stashing long packets in the centralized input buffer. Experimental results show that CIB-HIER is highly effective and can significantly increase the throughput of high-radix routers.

With a variety of tumor subtypes, personalized treatments need to identify the subtype of a tumor as accurately as possible. The development of DNA microarrays provides an opportunity to predict tumor classification. One strategy is to use gene expression profiling to extend current biological insights into the disease. However, overfitting problems exist in most machine learning methods when classifying tumor gene expression profile data characterized by high dimensional, small samples and nonlinearities. As a new machine learning methods, dictionary learning has become a more effective algorithm for gene expression profile classification. Here, a new method called discriminant projection shared dictionary learning (DPSDL) is proposed for classifying tumor subtypes using LINCS gene expression profile data. The method trains a shared dictionary, embeds Fisher discriminant criteria to obtain a class-specific sub-dictionary and coding coefficients. At the same time, a projection matrix is trained to widen the distance between different classes of samples. Experimental results show that our method performs better classification based on gene expression profile than the other dictionary learning methods and machine learning methods.

This article is concerned with the multitask multiagent allocation problem via many-objective optimization for multiagent systems (MASs). First, a novel layered MAS model is constructed to address the multitask multiagent allocation problem that includes both the original task simplification and the many-objective allocation. In the first layer of the model, the deep Q-learning method is introduced to simplify the prioritization of the original task set. In the second layer of the model, the modified shift-based density estimation (MSDE) method is put forward to improve the conventional strength Pareto evolutionary algorithm 2 (SPEA2) in order to achieve many-objective optimization on task assignments. Then, an MSDE-SPEA2-based method is proposed to tackle the many-objective optimization problem with objectives including task allocation, makespan, agent satisfaction, resource utilization, task completion, and task waiting time. As compared with the existing allocation methods, the developed method in this article exhibits an outstanding feature that the task assignment and the task scheduling are carried out simultaneously. Finally, extensive experiments are conducted to: 1) verify the validity of the proposed model and the effectiveness of two main algorithms and 2) illustrate the optimal solution for task allocation and efficient strategy for task scheduling under different scenarios.

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.

With the prevalence of web services, a large number of similar web services are provided by different providers. To select the optimal service among these service candidates, Quality of Service (QoS), representing the non-functional characteristics, plays an important role. To obtain the QoS values of web services, a number of web service QoS prediction methods have been proposed. Collaborative web service QoS prediction is one of the most popular approaches. Based on the historical QoS data, collaborative QoS prediction methods employ memory-based collaborative filtering (CF), model-based CF, or their hybrids to predict QoS values. However, these methods usually only consider the QoS information of similar users and services, neglecting the correlation between them. To enhance the prediction accuracy, we propose a novel method to predict QoS values based on factorization machine, which leverages not only QoS information of users and services but also the user and service neighbor’s information. To evaluate our approach, we conduct experiments on a large-scale real-world dataset with 1,974,675 web service invocations. The experiment results show that our approach achieves higher prediction accuracy than other QoS prediction methods.

Proactive transports nowadays have drawn much attention because of fast convergence, near-zero queueing and low latency. Proactive protocols, however, need an extra RTT to allocate ideal sending rate for new flows. To solve this, some studies, such as pHost, Homa, send unscheduled packets with line rate in the first RTT, which will causes severe network congestion. To avoid the queue buildup, Aeolus directly drops unscheduled packets when congestion occurs. Nevertheless, based on our experiment, a considerable part of small flows (0-100 KB) will be completed in the first RTT under 100 Gbps network, so that dropping unscheduled packets will severely affect performance of the small flows. In this paper we propose SSP, a new scheme aimed to eliminate the extra RTT delay and improve the flow completion time (FCT) of small flows under the proactive mechanism. Like pHost and Homa, SSP sends unscheduled packets at line rate when new flow arrives. Different from Aeolus, SSP selectively drops scheduled packets once queue buildup happens in the switch, thus protecting unscheduled packets which are more likely belong to small flows. Besides, based on the short-job-first (SJF) principle, we give relative higher priorities for small flows at the sender. Our simulation results with realistic workloads show that SSP can improve the FCT of small flows significantly. Specifically, under Web Search workload, SSP facilitates nearly 63% of 0-100 KB flows to complete one RTT faster. Also, SSP reduces the tail FCT by 56.8% at the 99th percentile compared with Expresspass and 29.2% compared with Aeolus while not leads to large queue buildup.

As the first and foremost step of typical automatic log analysis, log parsing has attracted a lot of interest. Most of existing studies treat log messages as pure strings and rely on string matching or string distance. In NLP, word2vec has shown very efficient and effective in representing words with low dimensional vectors. Inspired by this, in this paper we propose a novel method, called LPV (Log Parser based on Vectorization), for both offline and online log parsing. The central idea of our method in offline log parsing is to first convert log messages into vectors, and measure the similarity between two log messages by the distance between two vectors, then log messages can be clustered via clustering the vectors, and log templates can be extracted from the resulting clusters. For online log parsing, we also assign log templates with some kind of average vectors, so that the similarity between an incoming log message and each log template can also be measured by the distance between two vectors. We have conducted extensive experiments based on three widely used log datasets, and the results demonstrate that our proposed method LPV can achieve a competitive performance, compared against state-of-the-art log parsing methods.

High-performance computing (HPC) systems keep increasing in size and bandwidth, thus requiring larger and higher-bandwidth interconnection networks. The race to exascale just exacerbated this trend. The resulting longer average distance and more links between modules makes the use of optical fiber mandatory. However, the system meets the challenge of cable packaging complexity, cable tolerance, and cable maintainability. Splitter cable, like multi-core fiber (MCF), is a new and cost-effective approach that has the potential to replace a bundle of fibers between any pairs of modules with a single cable, thus lowering the packaging complexity and enhancing the maintainability. To the best of our knowledge, we are the first to formally study the problem of building a cost-effective HPC network topology using multicore fiber. In this paper, a new diameter-3 topology is proposed, namely Bundlefly. It achieves a flexible tradeoff between intra-module radixes and inter-module radixes of routers with merely moderate radix to build a diameter-3 exascale interconnection network. It is suitable for the use of multi-core fiber for the requirement of inter-module bandwidth and cable packaging complexity. We analyze the properties of Bundlefly and present effective routing algorithms. We simulate and analyze the performance of Bundlefly against state-of-the-art topologies. The results show that Bundlefly with flexible configurations can achieve better performance than most existing topologies.

Performance bugs are often hard to detect due to their non fail-stop symptoms. Existing debugging techniques can only detect performance bugs with known patterns (e.g., inefficient loops). The key reason behind this incapability is the lack of a general test oracle. Here, we argue that the performance (e.g., throughput, latency, execution time) expectation of configuration can serve as a strong oracle candidate for performance bug detection. First, prior work shows that most performance bugs are related to configurations. Second, the configuration change reflects common expectation on performance changes. If the actual performance is contrary to the expectation, the related code snippet is likely to be problematic.

The training of modern deep learning neural network calls for large amounts of computation, which is often provided by GPUs or other specific accelerators. To scale out to achieve faster training speed, two update algorithms are mainly applied in the distributed training process, i.e., the Synchronous SGD algorithm (SSGD) and Asynchronous SGD algorithm (ASGD). SSGD obtains good convergence point while the training speed is slowed down by the synchronous barrier. ASGD has faster training speed but the convergence point is lower when compared to SSGD. To sufficiently utilize the advantages of SSGD and ASGD, we propose a novel technology named One-step Delay SGD (OD-SGD) to combine their strengths in the training process. Therefore, we can achieve similar convergence point and training speed as SSGD and ASGD separately. To the best of our knowledge, we make the first attempt to combine the features of SSGD and ASGD to improve distributed training performance. Each iteration of OD-SGD contains a global update in the parameter server node and local updates in the worker nodes, the local update is introduced to update and compensate the delayed local weights. We evaluate our proposed algorithm on MNIST, CIFAR-10, and ImageNet datasets. Experimental results show that OD-SGD can obtain similar or even slightly better accuracy than SSGD, while its training speed is much faster, which even exceeds the training speed of ASGD.

Molecular dynamics (MD) is a computer simulation method of studying physical movements of atoms and molecules that provide detailed microscopic sampling on molecular scale. With the continuous efforts and improvements, MD simulation gained popularity in materials science, biochemistry and biophysics with various application areas and expanding data scale. Assisted Model Building with Energy Refinement (AMBER) is one of the most widely used software packages for conducting MD simulations. However, the speed of AMBER MD simulations for system with millions of atoms in microsecond scale still need to be improved. In this paper, we propose a parallel acceleration strategy for AMBER on the Tianhe-2 supercomputer. The parallel optimization of AMBER is carried out on three different levels: fine grained OpenMP parallel on a single CPU, single node CPU/MIC parallel optimization and multi-node multi-MIC collaborated parallel acceleration. By the three levels of parallel acceleration strategy above, we achieved the highest speedup of 25-33 times compared with the original program.

In order to make the query retrieve much more related products, some query rewrite methods have been proposed to obtain a set of candidate queries which can infer users' search intents and reduce the vocabulary gap between the original query and title of related products. However, previous studies ignore that some candidate queries may change users' search intents and retrieve irrelevant products. As a result, users' search experience will be impacted significantly. To reduce this influence, we need to design a semantic matching model to determine whether the candidate query change the original query's search intents (semantics). In addition, building a semantic matching model faces the following challenges: 1) Queries are usually very short and have limited information. It is very hard to learn an effective semantic matching model with the textual information of queries and candidate queries. 2) In order to get a generalized and effective mode, sufficient data samples are required to train the model. However, the cost of labeling is very huge. In order to address the above challenges, we propose an active and deep semantic matching framework (ActiveMatch) which is composed of two components. One component is the deep semantic matching (DSM) model which can make full use of the search log information to enhance the representation of queries and candidate queries. Then, it can estimate the semantic similarity between the original query and the candidate query more accurately. The other component is an uncertainty and novelty sampling (UNS) strategy which selects the samples to label based on the difficulty of the model estimating and the probability of the occurrence of new words. It not only reduces the cost of labeling but also ensures the effectiveness of the model. The experimental results on the Taobao e-commercial search platform verify the effectiveness of our framework.

Hierarchical high-radix router microarchitecture consisting of small SRAM-based intermediate buffers have been used in large-scale supercomputers interconnection networks. While hierarchical organization enables efficient scaling to higher switch port count, it requires intermediate buffers that can cause performance bottleneck. Shallow intermediate buffers can cause head-of-line blocking and result in backpressure towards the input buffers to reduce overall performance. Increasing intermediate buffer size overcomes this problem but is infeasible since the amount of intermediate buffer is proportional to O(p2) where p is the router radix. Adopting new memory technology with higher density can increase intermediate buffer size but is not practical in decentralized, small-size intermediate buffers.

Most software systems frequently encounter errors when interacting with their environments. When errors occur, error-handling code must execute flawlessly to facilitate system recovery. Implementing correct error handling is repetitive but non-trivial, and developers often inadvertently introduce bugs into error-handling code. Existing tools require correct error specifications to detect error-handling bugs. Manually generating error specifications is error-prone and tedious, while automatically mining error specifications is hard to achieve a satisfying accuracy. In this paper, we propose EH-Miner, a novel and practical tool that can automatically detect error-handling bugs without the need for error specifications. Given a function, EH-Miner mines its error-handling rules when the function is frequently checked by an equivalent condition, and handled by the same action. We applied EH-Miner to 117 applications across 15 software domains. EH-Miner mined error-handling rules with the precision of 91.1% and the recall of 46.9%. We reported 142 bugs to developers, and 106 bugs had been confirmed and fixed at the time of writing. We further applied EH-Miner to Linux kernel, and reported 68 bugs for kernel-4.17, of which 42 had been confirmed or fixed.

Software encounters ungraceful exits due to either bugs in the interrupt/signal handler code or the intention of developers to debug the software. Users may suffer from ”weird” problems caused by leftovers of the ungraceful exits. A common practice to fix these problems is rebooting, which wipes away the stale state of the software. This solution, however, is heavyweight and often leads to poor user experience because it requires restarting other normal processes. In this paper, we design SafeExit, a tool that can automatically detect and pinpoint the root causes of the problems caused by ungraceful exits, which can help users fix the problems using lightweight solutions. Specifically, SafeExit checks the program exit behaviors in the case of an interrupted execution against its expected exit behaviors to detect the missing cleanup behaviors required for avoiding the ungraceful exit. The expected behaviors are obtained by monitoring the program exit under a normal execution. We apply SafeExit to 38 programs across 10 domains. SafeExit finds 133 types of cleanup behaviors from 36 programs and detects 2861 missing behaviors from 292 interrupted executions. To predict missing behaviors for unseen input scenarios, SafeExit trains prediction models using a set of sampled input scenarios. The results show that SafeExit is accurate with an average F-measure of 92.5%.

GEneral Matrix Multiply (GEMM) is the most fundamental computational kernel routine in the BLAS library. To achieve high performance, in-memory data must be prefetched into fast on-chip caches before they are used. Two techniques, software prefetching and data packing, have been used to effectively exploit the capability of on-chip least recent used (LRU) caches, which are popular in traditional high-performance processors used in high-end servers and supercomputers. However, the market has recently witnessed a new diversity in processor design, resulting in high-performance processors equipped with shared caches with non-LRU replacement policies. This poses a challenge to the development of high-performance GEMM in a multithreaded context. As several threads try to load data into a shared cache simultaneously, interthread cache conflicts will increase significantly. We present a Shared Cache Partitioning (SCP) method to eliminate interthread cache conflicts in the GEMM routines, by partitioning a shared cache into physically disjoint sets and assigning different sets to different threads. We have implemented SCP in the OpenBLAS library and evaluated it on Phytium 2000+, a 64-core AArch64 processor with private LRU L1 caches and shared pseudo-random L2 caches (per four-core cluster). Our evaluation shows that SCP has effectively reduced the conflict misses in both L1 and L2 caches in a highly optimized GEMM implementation, resulting in an improvement of its performance by 2.75% to 6.91%.

With the fast development of deep learning (DL), the communication is increasingly a bottleneck for distributed workloads, and a series of optimization works have been done to scale out successfully. Nevertheless, the network behavior has not been investigated much yet. We intend to analyze the network behavior and then carry out some research through network simulation. Under this circumstance, an accurate communication measurement is necessary, as it is an effective way to study the network behavior and the basis for accurate simulation. Therefore, we propose to capture the deep learning communication (DLC) trace to achieve the measurement. To the best of our knowledge, we make the first attempt to capture the communication trace for DL training. In this article, we first provide detailed analyses about the communication mechanism of MXNet, which is a representative framework for distributed DL. Secondly, we define the DLC trace format to describe and record the communication behaviors. Third, we present the implementation of method for trace capturing. Finally, we make some statistics and analyses about the distributed DL training, including communication pattern, overlap ratio between computation and communication, computation overhead, synchronization overhead, update overhead, and so forth. Both the statistics and analyses are based on the trace files captured in a cluster with six machines. On the one hand, our trace files provide a sketch on the DLC, which contributes to understanding the communication details. On the other hand, the captured trace files can be used for figuring out various overheads, as they record the communication behaviors of each node.

As the scale and complexity of software expands, the issue of software performance is attracting increasing attention. The causes of performance problems mainly fall into two categories: software bugs and the resource contention among multiple software programs. Software bugs are usually caused by inefficient or unnecessary computation in source code. However, the performance problems caused by resource contention among multiple software programs are usually ignored by most researchers. Unlike software bugs, resource contention is not a bug; as a result, it is difficult to identify the concrete reason for a performance problem given that they share the same symptoms, such as long response time or low system throughput. In this paper, we investigate the performance problems caused by resource contention from a configuration perspective. By studying the response time distribution of software as the workload changes, we find that there is an inflection point of response time with the change of workload. Based on our observations, we design and implement a tool, Relax, to automatically detect and resolve resource contention. Relax combines resource request delay at the inflection point and the system resource usage rate to identify the performance problems caused by resource contention. Moreover, inspired by the congestion control algorithm in computer networks, Relax uses the square-increase and multiplicative-decrease method to adjust the resource-related configurations so as to resolve the contention. Our experiments show that Relax can effectively detect and resolve resource contention, and shorten the total software response time by 15.8% ~ 22.8%.

As the critical pipeline stage in on-chip routers, switch allocation assigns output ports to input ports and allow flits transiting through the switch without conflicts. Previous works strive to design efficient switch allocaiton strategies by maximizing the matching at each cycle, with the information from the current cycle or multiple cycles in time series. However, those works have not taken endpoint congestion into considerations. Tree-saturation, caused by endpoint congestion, can degrade NoC performance due to the congestion fanning out from the original point to upstream routers. In this paper, a novel router design, Eca-Router, is proposed to relieve the impact of endpoint congestion by switch allocation optimization. Eca-Router detects endpoint congestion by recording the destinations of packets in switch allocation. Endpoint congestion is decided in switch allocation once there are multiple input ports competing for the same output port and the packets in these input ports contain the same destination. During switch allocation, requests that contribute to endpoint congestion will be given lower priority to be allocated, and starvation control is also introduced to ensure allocation fairness. Evaluation results show that Eca-Router is efficient in reducing packet latency.

As software configurations continue to grow in complexity, misconfiguration has become one of major causes of software failure. Software configuration errors can have catastrophic consequences, seriously affecting the normal use of software and quality of service. And misconfiguration diagnosis faces many challenges, such as path-explosion problems and incomplete statistical data. Our study of the log that is generated in response to misconfigurations by six widely used pieces of software highlights some interesting characteristics. These observations have influenced the design of MisconfDoctor, a misconfiguration diagnosis tool via log-based configuration testing. Through comprehensive misconfiguration testing, MisconfDoctor first extracts log features for every misconfiguration and builds a feature database. When a system misconfiguration occurs, MisconfDoctor suggests potential misconfigurations by calculating the similarity of the new exception log to the feature database. We use manual and real-world error cases from Httpd, MySQL and PostgreSQL in order to evaluate the effectiveness of the tool. Experimental results demonstrate that the tool's accuracy reaches 85% when applied to manual-error cases, and 78% for real-world cases.

Many mixed-criticality systems are composed of a RTOS (Real-Time Operating System) and a GPOS (General Purpose Operating System), and we define them as mixed-time-sensitive systems. Complexity, isolation, real-time latency, and overhead are the main metrics to evaluate such a mixed-time-sensitive system (MTSS). These metrics may conflict with each other, so it is difficult for them to be consistently optimized. Most existing implementations only optimize part of the above metrics but not all. As the first contribution, this paper provides a detailed analysis of performance influencing factors which are exerted by various runtime mechanisms of existing MTSSs. We figure out the difference in performance across system designs, including task switch, memory management, interrupt handling, and resource isolation. We propose the philosophy of utilizing TrustZone characteristics to optimize various mechanisms in MTSS. The second contribution is to propose a TrustZone-based solution - termed TZDKS - for MTSS. Appropriate utilization of TrustZone extensions helps TZDKS to implement (i) virtualization environment for GPOS and RTOS, (ii) high efficient task switch, memory access, interrupt handling and device access which are verified by experiments. Therefore, TZDKS can achieve a full-scale balance amongst aforementioned metrics.

Failure-diagnosis logs can dramatically reduce the system recovery time when software systems fail. Log automation tools can assist developers to write high quality log code. In traditional designs of log automation tools, they define log placement rules by extracting syntax features or summarizing code patterns. These approaches are, however, limited since the log placements are far beyond those rules but are according to the intention of software code. To overcome these limitations, we design and implement SmartLog, an intention-aware log automation tool. To describe the intention of log statements, we propose the Intention Description Model (IDM). SmartLog then explores the intention of existing logs and mines log rules from equivalent intentions. We conduct the experiments based on 6 real-world open-source projects. Experimental results show that SmartLog improves the accuracy of log placement by 43% and 16% compared with two state-of-the-art works. For 86 real-world patches aimed to add logs, 57% of them can be covered by SmartLog, while the overhead of all additional logs is less than 1%.

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 .

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 .

High-performance computing (HPC) is essential for both traditional and emerging scientific fields, enabling scientific activities to make progress. With the development of high-performance computing, it is foreseeable that exascale computing will be put into practice around 2020. As Moore’s law approaches its limit, high-performance computing will face severe challenges when moving from exascale to zettascale, making the next 10 years after 2020 a vital period to develop key HPC techniques. In this study, we discuss the challenges of enabling zettascale computing with respect to both hardware and software. We then present a perspective of future HPC technology evolution and revolution, leading to our main recommendations in support of zettascale computing in the coming future.

As data sets become larger and more complicated, an extreme learning machine (ELM) that runs in a traditional serial environment cannot realize its ability to be fast and effective. Although a parallel ELM (PELM) based on MapReduce to process large-scale data shows more efficient learning speed than identical ELM algorithms in a serial environment, some operations, such as intermediate results stored on disks and multiple copies for each task, are indispensable, and these operations create a large amount of extra overhead and degrade the learning speed and efficiency of the PELMs. In this paper, an efficient ELM based on the Spark framework (SELM), which includes three parallel subalgorithms, is proposed for big data classification. By partitioning the corresponding data sets reasonably, the hidden layer output matrix calculation algorithm, matrix decomposition algorithm, and matrix decomposition algorithm perform most of the computations locally. At the same time, they retain the intermediate results in distributed memory and cache the diagonal matrix as broadcast variables instead of several copies for each task to reduce a large amount of the costs, and these actions strengthen the learning ability of the SELM. Finally, we implement our SELM algorithm to classify large data sets. Extensive experiments have been conducted to validate the effectiveness of the proposed algorithms. As shown, our SELM achieves an speedup on a cluster with ten nodes, and reaches a speedup with 15 nodes, an speedup with 20 nodes, a speedup with 25 nodes, a speedup with 30 nodes, and a speedup with 35 nodes.

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 proposed 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.

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.

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.

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.

Co-evolution exists ubiquitously in biological systems. At the molecular level, interacting proteins, such as ligands and their receptors and components in protein complexes, co-evolve to maintain their structural and functional interactions. Many proteins contain multiple functional domains interacting with different partners, making co-evolution of interacting domains occur more prominently. Multiple methods have been developed to predict interacting proteins or domains within proteins by detecting their co-variation. This strategy neglects the fact that interacting domains can be highly co-conserved due to their functional interactions. Here we report a novel algorithm to detect signals of both co-positive selection (co-variation) and co-purifying selection (co-conservation). Preliminary results show that our algorithm performs well and outperforms the popular co-variation analysis program CAPS. Our algorithm can be widely used to predict interacting domains in protein and nucleotide sequences and to analyze protein-ncRNA complexes.

Molecular docking is an important method in computational drug discovery. In large-scale virtual screening, millions of small drug-like molecules (chemical compounds) are compared against a designated target protein (receptor). Depending on the utilized docking algorithm for screening, this can take several weeks on conventional HPC systems. However, for certain applications including large-scale screening tasks for newly emerging infectious diseases such high runtimes can be highly prohibitive. In this paper, we investigate how the massively parallel neo-heterogeneous architecture of Tianhe-2 Supercomputer consisting of thousands of nodes comprising CPUs and MIC coprocessors that can efficiently be used for virtual screening tasks. Our proposed approach is based on a coordinated parallel framework called mD3DOCKxb in which CPUs collaborate with MICs to achieve high hardware utilization. mD3DOCKxb comprises a novel efficient communication engine for dynamic task scheduling and load balancing between nodes in order to reduce communication and I/O latency. This results in a highly scalable implementation with parallel efficiency of over 84% (strong scaling) when executing on 8,000 Tianhe-2 nodes comprising 192,000 CPU cores and 1,368,000 MIC cores.

Misconfigurations are not only prevalent, but also costly on diagnosing and troubleshooting. Unlike software bugs, misconfigurations are more vulnerable to users' mistakes. Improving system reaction to misconfigurations would ease the burden of users' diagnoses. Such effort can greatly benefit from a comprehensive study of system reaction ability towards misconfigurations based on errors injection method. Unfortunately, few such studies have achieved the above goal in the past, primarily because they fail to provide rich error types or only rely on generic alternations to generate misconfigurations. In this paper, we studied 8 mature opensource and commercial software and summarized a fine-grained classification of option types. On the basis of this classification, we could extract syntactic and semantic constraints of each type to generate misconfigurations. We implemented a tool named ConfTest to conduct misconfiguration injection and further analyze system reaction abilities to various of misconfigurations. We carried out comprehensive analyses upon 4 open-source software systems. Our evaluation results show that our option classification covers over 96% of 1582 options from Httpd, Yum, PostgreSQL and MySQL.Our constraint is more fined-grained and the accuracy is more than 90% of of real constraints through manual verification. We compared the capability in finding bad system reactions between ConfTest and ConfErr, showing that the ConfTest can find nearly 3 times the bad reactions found by ConfErr.

Misconfigurations have drawn tremendous attention for their increasing prevalence and severity, and the main causes are the complexity of configurations as well as the lack of domain knowledge for software. To diagnose misconfigurations, one typical approach is to find out the conditions that configuration options should satisfy, which we refer to as configuration constraints. Current researches only handled part of the situations of configuration constraints in source code, which provide only limited help for misconfiguration diagnosis. To better extract configuration constraints, we conduct a comprehensive manual study on the existence and variance of the configuration constraints in source code from five pieces of popular open-source software. We summarized several findings from different aspects, including the general statistics about configuration constraints, the general features for specific configurations, and the obstacles in extraction of configuration constraints. Based on the findings, we propose several suggestions to maximize the automation of constraints extraction.

Error-handling (EH) code snippets are widely used for troubleshooting in software projects. Analyzing these snippets help to better understand how developers handle errors. However, the identification of such error-handling code snippets from the large-scale software is non-trivial, since traditional methods meet a challenge of scalability. In this paper, we analyze a large number of error-handling code snippets and get same interesting and useful observations. We extract seven features according to these observations. Based on these features, we design an automatic approach to identify error-handling codes using static program analysis and machine learning algorithms. Finally, we evaluate this approach and select the optimal feature subset from all feature combinations. Our evaluation demonstrates the high F-Score of up to 0.85 in identifying error-handling code snippets.

Cost-effective adaptive routing has a significant impact on overall performance for high-radix hierarchical topologies, such as Dragonfly, which achieve a lower network diameter than traditional topologies, Torus and Fat tree, but exhibit a lower degree of adaptiveness for shortest-path rout- ing. Existing adaptive routing methods for those hierarchical topologies improve the adaptiveness by increasing path length, i.e. local or global adaptive routing, and thus suffer from complex and costly deadlock avoidance. This work aims to maximize the routing adaptiveness at the minimum cost of deadlock avoidance. We propose a label routing method for high-radix hierarchical networks. This label routing utilizes a co-design methodology and coordinates the two pipelines, input queue and routing computation, in the router microarchitec- ture. Packets in the input buffer are labeled by our routing algorithm depending on network states. We reorganize the input buffer and develop a label routing algorithm, named Green-Red Routing, GRR. GRR relaxes the requirement of using virtual channels to eliminate routing deadlock, and mitigates buffer resources dedicated to deadlock avoidance. GRR manages the buffer resources and balance its utilization elaborately, and achieve fully adaptive routing efficiently. We conduct extensive experiments to evaluate the performance of GRR on Dragonfly and compare it with state-of-the-art works. The results show that GRR achieves 10%-35% higher performance than existing routing algorithms under most traffic patterns.

We present, VIP, an approach to boosting the precision of Virtual call Integrity Protection for large-scale real-world C++ programs (e.g., Chrome) by using pointer analysis for the first time. VIP introduces two new techniques: (1) a sound and scalable partial pointer analysis for discovering statically the sets of legitimate targets at virtual callsites from separately compiled C++ modules and (2) a lightweight instrumentation technique for performing (virtual call) integrity checks at runtime. VIP raises the bar against vtable hijacking attacks by providing stronger security guarantees than the CHA-based approach with comparable performance overhead.

Misconfigurations have become a major cause of software failures.Most research focuses on misconfiguration diagnosis and troubleshooting, which occur after the misconfigurations have happened.Actually, if we can prevent misconfiguration before software runs, many potential catastrophic failures of systems can be avoided, thus reducing customers' downtime and support costs.In software configuration, we found that most configuration options have specific constraints, which have a strong connection with the configuration option type.If we can check the configuration settings against the inferred type before the software runs, many misconfigurations can be prevented.In this paper, we explore a name-based method called ConfTypeInferer to automatically infer the type of configuration options, which can help users to correctly configure and check settings, thus preventing misconfigurations proactively.We manually studied several popular open-source software projects to investigate the classification and naming conventions of configuration option.Based on these findings, we designed and implemented the ConfTypeInferer.We performed comprehensive experiments to evaluate the effectiveness of our method.

Molecular dynamics (MD) is a computer simulation method of studying physical movements of atoms and molecules that provide detailed microscopic sampling on molecular scale. With the continuous efforts and improvements, MD simulation gained popularity in materials science, biochemistry and biophysics with various application areas and expanding data scale. Assisted Model Building with Energy Refinement (AMBER) is one of the most widely used software packages for conducting MD simulations. However, the speed of AMBER MD simulations for system with millions of atoms in microsecond scale still need to be improved. In this paper, we propose a parallel acceleration strategy for AMBER on Tianhe-2 supercomputer. The parallel optimization of AMBER is carried out on three different levels: fine grained OpenMP parallel on a single MIC, single-node CPU/MIC collaborated parallel optimization and multi-node multi-MIC collaborated parallel acceleration. By the three levels of parallel acceleration strategy above, we achieved the highest speedup of 25-33 times compared with the original program. Source Code: https://github.com/tianhe2/mAMBER.

Network-on-chip system plays an important role to improve the performance of chip multiprocessor systems. As the complexity of the network increases, congestion problem has become the major performance bottleneck and seriously influence the performance of NoCs. Prior works have focused on designing effective routing algorithm based on collecting contention and congestion information to load balance the traffic. However, most prior works do not consider balancing the traffic load during switch allocation. Due to the lack of congestion information in switch allocation stage, switch allocator performs allocation only based on packet requests and thus aggravates the congestion in the ports of switch. In this paper, we propose CCAS, a new switch allocation strategy to add the contention and congestion information into the switching process to load balance the traffic and achieve efficient switch allocation. We carefully design CCAS to balance the trade-off between traffic load balance and the matching efficiency in switch allocation. We evaluate our design under synthetic traffic and traces of PARSEC benchmarks. Our evaluations show that CCAS can achieve remarkable latency reduction compared to other switch allocation strategies.

Tree traversals are widely used irregular applications. Given a tree traversal algorithm, where a single tree is traversed by multiple queries (with truncation), its efficient parallelization on GPUs is hindered by branch divergence, load imbalance and memory-access irregularity, as the nodes and their visitation orders differ greatly under different queries. We leverage a key insight made on several truncation-induced tree traversal regularities to enable as many threads in the same warp as possible to visit the same node simultaneously, thereby enhancing both GPU resource utilization and memory coalescing at the same time. We introduce a new parallelization approach, RegTT, to orchestrate an efficient execution of a tree traversal algorithm on GPUs by starting with BFT (Breadth-First Traversal), then reordering the queries being processed (based on their truncation histories), and finally, switching to DFT (Depth-First Traversal). RegTT is general (without relying on domain-specific knowledge) and automatic (as a source-code transformation). For a set of five representative benchmarks used, RegTT outperforms the state-of-the-art by 1.66x on average.

Interconnection network plays an essential role in the architecture of large-scale high performance computing (HPC) systems. In the paper, we construct a novel family of low-diameter topologies, Galaxyfly, using techniques of algebraic graphs over finite fields. Galaxyfly is guaranteed to retain a small constant diameter while achieving a flexible tradeoff between network scale and bisection bandwidth. Galaxyfly lowers the demands for high radix of network routers and is able to utilize routers with merely moderate radix to build exascale interconnection networks. We present effective congestion-aware routing algorithms for Galaxyfly by exploring its algebraic property. We conduct extensive simulations and analysis to evaluate the performance, cost and power consumption of Galaxyfly against state-of-the-art topologies. The results show that our design achieves better performance than most existing topologies under various routing algorithms and traffic patterns, and is cost-effective to deploy for exascale HPC systems.

We present an efficient GPU implementation of Andersen's whole-program inclusion-based pointer analysis, a fundamental analysis on which many others are based, including optimising compilers, bug detection and security analyses. Andersen's algorithm makes extensive modifications to the graph that represents the pointer-manipulating statements in a program. These modifications are highly irregular, input-dependent and statically unpredictable, making it much more challenging to balance such graph workloads across a multitude of GPU cores than those dealt with by traditional graph algorithms such as DFS and BFS. To parallelise Andersen's analysis efficiently on GPUs, we introduce an imbalance-aware workload partitioning scheme that divides its workload dynamically among the concurrent warps, initially in a warp-centric manner (during the coarsegrain stage) but later switches to a task-pool-based model when a workload imbalance is detected (during the fine-grain stage). We improve further its performance by using an adaptive group propagation scheme to reduce some redundant traversals. For a set of 14 C benchmarks evaluated, our parallel implementation of Andersen's analysis achieves a significant speedup of 46 percent on average over the state-of-the art on an NVIDIA Tesla K20c GPU.

Whole genome re-sequencing plays a crucial role in biomedical studies. The emergence of genomic big data calls for an enormous amount of computing power. However, current computational methods are inefficient in utilizing available computational resources. In this paper, we address this challenge by optimizing the utilization of the fastest supercomputer in the world - TH-2 supercomputer. TH-2 is featured by its neo-heterogeneous architecture, in which each compute node is equipped with 2 Intel Xeon CPUs and 3 Intel Xeon Phi coprocessors. The heterogeneity and the massive amount of data to be processed pose great challenges for the deployment of the genome analysis software pipeline on TH-2. Runtime profiling shows that SOAP3-dp and SOAPsnp are the most time-consuming components (up to 70% of total runtime) in a typical genome-analyzing pipeline. To optimize the whole pipeline, we first devise a number of parallel and optimization strategies for SOAP3-dp and SOAPsnp, respectively targeting each node to fully utilize all sorts of hardware resources provided both by CPU and MIC. We also employ a few scaling methods to reduce communication between different nodes. We then scaled up our method on TH-2. With 8192 nodes, the whole analyzing procedure took 8.37 hours to finish the analysis of a 300 TB dataset of whole genome sequences from 2,000 human beings, which can take as long as 8 months on a commodity server. The speedup is about 700x.

Multi-NoC (multiple network-on-chip) has demonstrated its advantages in power gating for reducing leakage power. This work presents 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 performance-aware traffic allocation policy, Chameleon is able to achieve both high power efficiency and good performance at varying network utilization. Our experimental results show that Chameleon delivers an average of 3.39% higher performance than Catnap, the best in the literature. More importantly, Chameleon consumes an average of 17.16% less power than Catnap.

Summary Open Computing Language (OpenCL) is an open, functionally portable programming model for a large range of highly parallel processors. To provide users with access to the underlying platforms, OpenCL has explicit support for features such as local memory and vector data types (VDTs). However, these are often low‐level, hardware‐specific features, which can be detrimental to performance on different platforms. In this paper, we focus on VDTs and investigate their usage in a systematic way. First, we propose two different approaches (inter‐vdtandintra‐vdt) to use VDTs in OpenCL kernels, and show how to translate scalar OpenCL kernels to vectorized ones. After obtaining vectorized code, we evaluate the performance effects of using VDTs with two types of benchmarks: micro‐benchmarks and macro‐benchmarks. With micro‐benchmarks, we study the execution model of VDTs and the role of the compiler‐aided vectorizer on five devices. With macro‐benchmarks, we explore the changes of memory access patterns before and after using VDTs, and the resulting performance impact. Not only our evaluation provides insights into how OpenCL's VDTs are mapped on different processors, but it also indicates that using such data types introduces changes in both computation and memory accesses. Based on the lessons learned, we discuss how to deal with performance portability in the presence of VDTs. Copyright © 2014 John Wiley & Sons, Ltd.

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.

Greedy geographic routing is widely adopted in practical wireless networks due to its simplicity. However, greedy geographic routing alone cannot guarantee the delivery of packets due to the existence of local minima. A number of solutions have been proposed to address this issue, such as face routing, landmark-based routing, network segmentation or virtual coordinate based methods, etc. However, these solutions either have various limitations, such as depending on exact node locations, requiring costly preprocessing of the global network topology, or have obvious performance shortcomings, such as severe load-imbalance, large path stretch factors, etc. In this work, we attempt to combine the advantages of existing solutions, and present a hierarchical greedy geographic routing scheme. This design, FLYER, neither depends on exact node locations, nor needs to store any global state information in each node, which makes it applicable and scalable in large-scale practical systems. Moreover, our routing scheme is able to produce route paths with lower stretch factors and more load-balancing property than existing solutions. The algorithm works in a completely localized fashion, and the additional storage and computation complexity is extremely low. Extensive simulations are conducted, and the results demonstrate the superior performance of our approach against the state-of-the-art methods.

Maintaining data availability is one of the biggest challenges in Decentralized Online Social Networks (DOSN). In the existing work of improving data availability in DOSN, it is often assumed that the friends of a user are always capable of contributing sufficient storage capacity to store all the data published by the user. However, this assumption is not always true for today's Online Social Networks (OSNs) for the following reasons. On one hand, the increasingly more data are being generated on the OSNs nowadays. On the other hand, current users often use the smart mobile devices to access the OSNs. These two factors cause the shortage of the storage capacity in DOSN, where the published data are supposed to be stored within a friend circle. The limitation of the storage capacity may jeopardize the data availability. Therefore, it is desired to know the relation between the storage capacity contributed by the OSN users and the level of data availability that the OSN can achieve. This paper addresses this issue. In this paper, the data availability model over storage capacity is established. Further, a novel method is proposed to predict the data availability on the fly. Extensive simulation experiments have been conducted to evaluate the effectiveness of the data availability model and the on-the-fly prediction. The data availability model can be used by the OSN designers to determine the storage capacity for the published data in order to achieve the desired data availability. The on-the-fly prediction method can help the data replication and storage policies make judicious decisions at runtime.

Node failures often occur in large-scale data centers today. Erasure coded storage system provides high data reliability via data reconstruction. Existing work can improve reconstruction performance, while considering the transmission of recovery data as the main source of reconstruction overheads. Transmission costs are highly related with network topology, which is unfortunately overlooked. An ideal connected topology assumes that two nodes in a data center has a direct link. The unmatching design between the network model and the practical topology may lead to an underestimated transmission costs. In this paper, we propose an erasure coded storage system for data reconstruction, which uses the practical network topology to minimize the reconstruction transmission costs. First, we identify the aggregation feature of erasure coding reconstruction and propose Aggregation Decoding, which splits the decoding process into several sub-decoding operations during reconstruction routing to reduce overall recovery data to be transmitted. We further improve Aggrecode to construct efficient route basing on the location of participating nodes to exploit the aggregation feature of Aggregation Decoding. We formulate this routing problem as a relaxed Steiner Tree problem. We design two heuristic routing algorithms based on ant-colony optimization specialized for two failure recovery cases, e.g., node recovery and degraded read. Our analytical results demonstrate the important properties of Aggrecode. These properties are evaluated by extensive experiments deployed on popular data center topologies, such as Torus, Fat-tree, DCell and BCube. The results show that Aggrecode can reduce data transmission costs by at least 37.12% for all settings.

We present an end-to-end optimization of the innovative Arbitrary high-order DERivative Discontinuous Galerkin (ADER-DG) software SeisSol targeting Intel® Xeon Phi coprocessor platforms, achieving unprecedented earthquake model complexity through coupled simulation of full frictional sliding and seismic wave propagation. SeisSol exploits unstructured meshes to flexibly adapt for complicated geometries in realistic geological models. Seismic wave propagation is solved simultaneously with earthquake faulting in a multiphysical manner leading to a heterogeneous solver structure. Our architecture aware optimizations deliver up to 50% of peak performance, and introduce an efficient compute-communication overlapping scheme shadowing the multiphysics computations. SeisSol delivers near-optimal weak scaling, reaching 8.6 DP-PFLOPS on 8,192 nodes of the Tianhe-2 supercomputer. Our performance model projects reaching 18 -- 20 DP-PFLOPS on the full Tianhe-2 machine. Of special relevance to modern civil engineering needs, our pioneering simulation of the 1992 Landers earthquake shows highly detailed rupture evolution and ground motion at frequencies up to 10 Hz.

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.

The processing of massive small files is a challenge in the design of distributed file systems. Currently, the combined-block-storage approach is prevalent. However, the approach employs traditional file systems like ExtFS and may cause inefficiency for random access to small files. This paper focuses on optimizing the performance of data servers in accessing massive 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 aims to substitute the traditional file system on data servers that are mainly used to store small files, and it can greatly simplify the original data access procedure. The new metadata proposed in this paper occupies only a fraction of the original 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 1KB to 64KB, iFlatLFS is faster than Ext4 by 48% and 54% 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% on average for random read access and hybrid access (the mix of read and write accesses), respectively.

Fault resilience has became a major issue for HPC systems, in particular in the perspective of future E-scale systems, which will consist of millions of CPU cores and other components. Fault tolerant MPI was proposed to offer support of software level fault tolerance approaches. However, the widely used MPI implementations, such as MPICH and Mvapich2, provide limited support for fault tolerance. This paper proposes NR-MPI, a Non-stop and Fault Resilient MPI. NR-MPI implements the semantics of FT-MPI based on MPICH. Specifically, this paper focuses on failure detection in MPI library, online failure recovery of communicators for multiple failures, friendly programming interface extending for NR-MPI. Furthermore, to support failure recovery of applications, NR-MPI implements data backup and restore interfaces based on double in-memory checkpoint/restart. We conduct experiments with NPB benchmarks on TH-1A supercomputer. Experimental results show that NR-MPI based fault tolerant programs can recover from failures online without restarting, and the overhead is small even for applications with tens of thousands of cores.

Wormhole attack is a severe threat to wireless ad hoc and sensor networks. Most of previous countermeasures either require specialized hardware devices or make strong assumptions on the network in order to capture the specific symptom induced by wormholes. Those requirements and assumptions limit the applicability of those approaches. Recently, some approaches based on topological or graph theoretical techniques are proposed to recognize wormholes using only connectivity information, shedding light on the challenging issue of connectivity-based wormhole detections. Unfortunately, those state-of-the-art connectivity-based countermeasures either present the principle of tracing wormholes in continuous domain, which makes it costly to transform them into protocols in discrete networks, or only explore localized (unstable) symptom of wormholes, accordingly incurring high false positive or negative rate. In this work, we make the first attempt towards establishing a graph theoretical method, called Worm Planar, that merely utilizes localized connectivity information and is able to capture the global essential symptoms of wormholes directly in the discrete networks. Worm Planar exploits location free network planarization technique to perform connectivity-based wormhole detection. Our new insights into the symptoms of wormholes make Worm Planar orthogonal to existing connectivity-based methods. We formally prove the correctness and evaluate the effectiveness of our approach through extensive simulations and comparisons with the state-of-the-art approaches. Simulation results demonstrate that Worm Planar is able to accurately identify and isolate wormholes for a large class of network instances.

Fault-tolerance is essential in extreme-scale data processing systems. Pro-active fault-tolerance scheme (such as the speculative execution in MapReduce framework), can dramatically improve the response time of job executions when the failure becomes norm rather than an exception. Efficient pro-active fault-tolerance schemes require precise knowledge on the task executions, which has been an open challenges for decades. To well address the issue, in this paper we design and implement RiskI, a profile-based prediction algorithm in conjunction with a risk-aware task assignment algorithm to accelerate task executions, taking the uncertainty nature of tasks into account. Our design demonstrates that the nature uncertain not only brings great challenges but also new opportunities. With a careful design, we can benefit from such uncertainties. We implement the idea in Hadoop 0.21.0 systems and the experimental results show that compared with the traditional LATE algorithm, the response time can be improved by 46% with the same system throughput.

This poster presents a hierarchical greedy geographic routing scheme in wireless networks, which performs greedy geographic routing with guaranteed delivery under uncertain locations on a landmark graph by leveraging a fine-grained connectivity-based planarization algorithm. This design neither depends on exact node locations, nor needs to store any global state information in each node. The algorithm works in a completely localized fashion, and the additional storage and computation complexity is extremely low. Our simulations demonstrate that the routing scheme is able to produce route paths with lower stretch factors and more load-balancing property than the state-of-the-art methods.

This paper introduces a novel wireless collaborated hybrid data center architecture called RF-HYBRID that could optimize the effect of wireless transmission while reduce the complexity of wired network. RF-HYBRID improves throughput and packet delivery latency through flexible wireless detours and shortcuts, with a comprehensive routing and congestion control method.

Extracting planar graph from network topologies is of great importance for efficient protocol design in wireless ad hoc and sensor networks. Previous techniques of planar topology extraction are often based on ideal assumptions, such as UDG communication model and accurate node location measurements. To make these protocols work effectively in practice, we need extract a planar topology in a location-free and distributed manner with small stretch factors. The planar topologies constructed by current location-free methods often have large stretch factors. In this paper, we present a fine-grained and location-free network planarization method under ρ-quasi-UDG communication model with ρ≥1/√2. Compared with existing location-free planarization approaches, our method can extract a provably connected planar graph, called topological planar simplification (TPS), from the connectivity graph in a fine-grained manner using local connectivity information. We evaluate our design through extensive simulations and compare with the state-of-the-art approaches. The simulation results show that our method produces high-quality planar graphs with a small stretch factor in practical large-scale networks.

In order to provide reliable data delivery and system management for large-scale wireless sensor networks (WSNs), tracing the route paths of packets in a lightweight manner is crucial and critical. Real-time path tracing technology enables us to observe every data transmission and analyze network dynamics in a fine-grained fashion. Due to resource constraints of WSNs, however, it is difficult, if not impossible, to integrate into each packet with its full path information. We attempt to capture such information with inserting a small and constant overhead into each packet. In this design, PathZip, each sensor node performs lightweight hash-based computations to passively label every packet forwarded. Meanwhile, the sink extracts the label information so as to leverage the pre-knowledge on the network to compute the full packet path. Both topology-aware and geometry-assistant techniques are utilized by PathZip in order to exploit different network knowledge and reduce the computation and storage overhead greatly. We conduct theoretical analysis and extensive simulations to evaluate the performance of our design. The results show that our method is effective to trace the full route path in large-scale WSNs, and outperforms the state-of-the-art methods.

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.

Extracting planar graph from network topologies is of great importance for efficient protocol design in wireless ad hoc and sensor networks. Previous techniques of planar topology extraction are often based on ideal assumptions, such as UDG communication model and accurate node location measurements. To make these protocols work effectively in practice, we need extract a planar topology in a location-free and distributed manner with small stretch factor. Current location-free methods cannot provide any guarantee on the stretch factor of the constructed planar topologies. In this work, we present a fine-grained and location-free network planarization method. Compared with existing location-free planarization approaches, our method can extract a high-quality planar graph, called TPS (Topological Planar Simplification), from the communication graph using local connectivity information. TPS is proved to be a planar graph and has a constant stretch factor for a large class of network instances. We evaluate our design through extensive simulations and compare with the state-of-the-art approaches. The simulation results show that our method produces planar graphs with a small constant stretch factor, often less than 1.5.

Many efforts have been made for addressing coverage problems in sensor networks. They fall into two categories, full coverage and barrier coverage, featured as static coverage. In this work, we study a new coverage scenario, sweep coverage, which differs with the previous static coverage. In sweep coverage, we only need to monitor certain points of interest (POIs) periodically so the coverage at each POI is time-variant, and thus we are able to utilize a small number of mobile sensors to achieve sweep coverage among a much larger number of POIs. We investigate the definitions and model for sweep coverage. Given a set of POIs and their sweep period requirements, we prove that determining the minimum number of required sensors (min-sensor sweep-coverage problem) is NP-hard, and it cannot be approximated within a factor of 2. We propose a centralized algorithm with constant approximation ratio 3 for the min-sensor sweep-coverage problem. We further characterize the nonlocality of the problem and design a distributed sweep algorithm, DSWEEP, cooperating sensors to provide efficiency with the best effort. We conduct extensive simulations to study the performance of the proposed algorithms. Our simulations show that DSWEEP outperforms the randomized scheme in both effectiveness and efficiency.

Wormhole attack is a severe threat to wireless ad hoc and sensor networks. Most existing countermeasures either require specialized hardware devices or make strong assumptions on the network in order to capture the specific (partial) symptom induced by wormholes. Those requirements and assumptions limit the applicability of previous approaches. In this paper, we present our attempt to understand the impact and inevitable symptom of wormholes and develop distributed detection methods by making as few restrictions and assumptions as possible. We fundamentally analyze the wormhole problem using a topology methodology and propose an effective distributed approach, which relies solely on network connectivity information, without any requirements on special hardware devices or any rigorous assumptions on network properties. We formally prove the correctness of this design in continuous geometric domains and extend it into discrete domains. We evaluate its performance through extensive simulations.

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.

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 has been 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 towards 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.

In this work, we present an efficient fine-grained sharing approach of encrypted files. A concept named safe capsule (SC) is proposed as the organization unit for files. By using safe capsule, user can provide one of the fine-grained access permissions of their own data to others, such as read-only. Data are encrypted(decrypted) transparently when writing(reading) to keep its privacy.

Mobile sensors are often employed for enhancing the sensing coverage and assisting the data gathering in wireless sensor networks. Equipped with unlimited mobility, they are able to move anywhere within the monitored field. Despite the promising simulation (or testbed) result and theoretical conclusion in paper, we have to realize the assumption on unlimited mobility has limitations and is practically unrealistic in many applications.

Wormhole attack is a severe threat against wireless ad hoc and sensor networks. It can be launched without compromising any legitimate node or cryptographic mechanisms, and often serves as a stepping stone for many serious attacks. Most existing countermeasures often make critical assumptions or require specialized hardware devices in the network. Those assumptions and requirements limit the applicability of previous approaches. In this work, we explore the impact of wormhole attacks on network connectivity topologies, and develop a simple distributed method to detect wormholes, called WormCircle-. WormCircle relies solely on local connectivity information without any requirements on special hardware devices or making any rigorous assumptions on network properties. We establish the correctness of this design in continuous geometric domains and extend it into discrete networks. We evaluate the effectiveness in randomly deployed sensor networks through extensive simulations.

Location-free boundary recognition is crucial and critical for many fundamental network functionalities in wireless ad hoc and sensor networks. Previous designs, often coarse-grained, fail to accurately locate boundaries, especially when small holes exist. To address this issue, we propose a fine-grained boundary recognition approach using connectivity information only. This algorithm accurately discovers inner and outer boundary cycles without using location information. To the best of our knowledge, this is the first design being able to determinately locate all hole boundaries no matter how small the holes are. Also, this distributed algorithm does not rely on high node density. We formally prove the correctness of our design, and evaluate its effectiveness through extensive simulations.

In wireless sensor networks, mobile sensors are often employed for enhancing the sensing coverage and detection accuracy. Current approaches assume mobile sensors with the capability of arbitrary movement. The usage of such sensors with unlimited mobility, however, requires complicated sensor manufactures and high intelligence of movement which are practically unrealistic in many practical applications. We investigate the usage of cable-based mobile sensors which move along pre-deployed cables to accomplish sensing tasks at different positions. A target area is said to be reachable, if for any point in this area, at least one mobile sensor can move along the cable and achieve coverage to the point within a specified delay bound. We propose to achieve k reachability for the sensing field with minimum mobile sensors along the cable. Further, during special events, mobile sensors need to move and help surveillance. We need adjust the positions of the rest of mobile sensors accordingly to balance the reachability within the area. We prove the NP-hardness of the targeted problems and give heuristic approaches. Through comprehensive simulations, we evaluate the performance of this design and show its effectiveness.

Many efforts have been made for addressing coverage problems in sensor networks. They fall into two categories, full coverage and barrier coverage, featured as static coverage. In this work, we study a new coverage scenario, sweep coverage, which differs with the previous static coverage. In sweep coverage, we only need to monitor certain points of interest (POIs) periodically so the coverage at each POI is time-variant, and thus we are able to utilize a small number of mobile sensors to achieve sweep coverage among a much larger number of POIs. We investigate the definitions and model for sweep coverage. Given a set of POIs and their sweep period requirements, we prove that determining the minimum number of required sensors (min-sensor sweep-coverage problem) is NP-hard, and it cannot be approximated within a factor of 2. We propose a centralized algorithm with constant approximation ratio 2 + epsi for the simplified problem where all sweep periods are identical. We further characterize the non-locality of the problem and design a distributed sweep algorithm, DSWEEP, cooperating sensors to provide required sweep requirements with the best effort. We conduct extensive simulations to study the performance of the proposed algorithms. Our simulations show that DSWEEP outperforms the randomized scheme in both effectiveness and efficiency.

There have been works done by utilizing mobile sensors as supplementary to assist the sensing coverage for the static sensor nodes in possible event happenings. Most of them assume that the mobile sensors are equipped with unlimited mobility and thus can move anywhere within the monitored field. However, the assumption of unlimited mobility has its own limitations and is unrealistic in many practical applications. Alternatively, we consider pre-deploying cables within the monitored field so that mobile sensors move along cables to destinations. In this case, we can far more relax the requirements on the mobile sensors and achieve more realistic usage despite of the complex field landforms. We find that existing cables deployed in the tunnel are perfect carriers for deploying mobile nodes which help get rid of the complex circumstance in the underground tunnel.

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 finding optimized self-monitoring topology for WSNs. We show the problem is NP-complete even under the unit disk graph (UDG) model, and give the upper bound on the approximation ratio. We further propose two distributed polynomial algorithms with provable approximation ratio to address this issue. Through comprehensive simulations, we evaluate the effectiveness of this design.

WSN congestion occurs when offered traffic load exceeds available capacity. It causes overall channel quality to degrade and drop rates to rise. Furthermore, redundant transmissions are always adopted to guarantee reliable data delivery, which may deteriorate congestion since they bring on more contention and in reverse hampers the reliability. In this paper, we propose a framework to avoid, detect and mitigate congestion effectively. In this framework, a congestion aware traffic allocation (COTA) is used in multipath routing to balance traffic around the whole network COTA uses some heuristic information to analyze the potential congestion region and avoid traversing these regions. A runtime traffic adjustment CODEM is presented to use accurate metrics to detect and mitigate congestion. Compared with previous works, our work can control congestion while achieving the desired reliability at the same time. Comprehensive simulations have validated the distinguished performance in several aspects of our framework.

In this paper, weighted factors are given to authentication rules to express their importance, and the control flags are given to multiple authentication rules to express their stack relationship and reflect their effect on the authentication conclusions. Based on the research on weighted model in fuzzy logic, this paper puts forwards the control flags-based weighted authentication trustworthiness model. The model firstly calculates the trustworthiness of a single weighted authentication rule, then, according to the control flags corresponding to each authentication rule, calculates the user's authentication trustworthiness under multiple authentication rules. By comparing user's authentication trustworthiness with system access trustworthiness threshold, the system forms the final authentication conclusion. The model describes the uncertainties in authentication system comprehensively, and enhances the security under multiple authentication rules.