Adapting large pre-trained language models to downstream tasks often entails fine-tuning millions of parameters or deploying costly dense weight updates, which hinders their use in resource-constrained environments. Low-rank Adaptation (LoRA) reduces trainable parameters by factorizing weight updates, yet the underlying dense weights still impose high storage and computation costs. Magnitude-based pruning can yield sparse models but typically degrades LoRA’s performance when applied naively. In this paper, we introduce SALR (Sparsity-Aware Low-Rank Representation), a novel fine-tuning paradigm that unifies low-rank adaptation with sparse pruning under a rigorous mean-squared-error framework. We prove that statically pruning only the frozen base weights minimizes the pruning error bound, and we recover the discarded residual information via a truncated-SVD low-rank adapter, which provably reduces per-entry MSE by a factor of (1 - r/min(d, k)). To maximize hardware efficiency, we fuse multiple low-rank adapters into a single concatenated GEMM, and we adopt a bitmap-based encoding with a two-stage pipelined decoding + GEMM design to achieve true model compression and speedup. Empirically, SALR attains 50% sparsity on various LLMs while matching the performance of LoRA on GSM8K and MMLU, reduces model size by 2x, and delivers up to a 1.7x inference speedup.

Individual investors are disadvantaged in financial markets, overwhelmed by abundant information and lacking professional analysis.Equity research reports are crucial resources, offering valuable insights.By leveraging these reports, large language models (LLMs) can enhance investors' decision-making and strengthen financial analysis.However, two key challenges limit their effectiveness: (1) the rapid evolution of market events outpaces the slow update cycles of existing knowledge bases, and (2) the long-form, unstructured nature of financial reports hinders timely, context-aware integration by LLMs.To address these challenges, we tackle both data and methodology aspects.We introduce the Event-Enhanced Automated Construction of Financial Knowledge Graph (FinKario), a dataset with over 305,360 entities, 210,328 relational triples, and 19 relation types.FinKario integrates real-time company fundamentals and events through promptdriven extraction guided by institutional templates, providing structured, accessible financial insights for LLMs.We further propose a Two-stage, Graph-based retrieval strategy (FinKario-RAG) to optimize retrieval over evolving, large-scale financial knowledge.Experiments show that FinKario with FinKario-RAG achieves superior trend prediction accuracy, outperforming financial LLMs by 18.81% and institutional strategies by 17.85% on average in backtesting.

Lossless model compression holds tremendous promise for alleviating the memory and bandwidth bottlenecks in bitexact Large Language Model (LLM) serving. However, existing approaches often result in substantial inference slowdowns due to fundamental design mismatches with GPU architectures: at the kernel level, variable-length bitstreams produced by traditional entropy codecs break SIMT parallelism; at the system level, decoupled pipelines lead to redundant memory traffic. We present ZipServ, a lossless compression framework co-designed for efficient LLM inference. ZipServ introduces Tensor-Core-Aware Triple Bitmap Encoding (TCA-TBE), a novel fixed-length format that enables constant-time, parallel decoding, together with a fused decompression-GEMM (ZipGEMM) kernel that decompresses weights on-the-fly directly into Tensor Core registers. This "load-compressed, compute-decompressed" design eliminates intermediate buffers and maximizes compute intensity. Experiments show that ZipServ reduces the model size by up to 30%, achieves up to 2.21× kernel-level speedup over NVIDIA’s cuBLAS, and expedites end-to-end inference by an average of 1.22× over vLLM. ZipServ is the first lossless compression system that provides both storage savings and substantial acceleration for LLM inference on GPUs.

Full-graph GNN training delivers high accuracy but scales poorly on multi-server clusters due to heavy, irregular inter-node embedding exchanges. We present SNI-GNN, a SmartNIC-assisted full-graph training system that reduces communication while preserving accuracy by predicting remote embeddings in-network. SNI-GNN deploys a lightweight linear-trend predictor on SmartNICs to refine cached historical embeddings, coupled with an importance-based boundary-node sampling policy and an asynchronous DPU--GPU data pipeline with intermediate-result reuse. We provide error and convergence bounds showing that predictor bias remains controlled under bounded second-order dynamics and yields standard non-convex convergence with inexact gradients. Implemented on NVIDIA BlueField-3, SNI-GNN integrates with state-of-the-art full-graph systems, cuts communication by 21--45\%, achieves 1.3--3.6$\times$ end-to-end speedups over BNS-GCN and up to 1.29$\times$ over baseline SANCUS, with accuracy loss $\leq 0.01$, and scales efficiently to 16 GPUs on graphs with up to tens of millions of edges. These results indicate SmartNIC-based in-network prediction is a practical complement to partitioning and compression techniques for communication-efficient full-graph GNN training at scale.

The high computational complexity of the self-attention mechanism constitutes a primary performance bottleneck in LLM inference. Existing sparse attention mechanisms commonly adopt coarse-grained block sparsity to align with FlashAttention’s tiling and rely on dense Tensor Cores, leaving the potential of emerging hardware Sparse Tensor Cores (SpTCs) and semi-structured sparsity largely untapped. We present DynSpAttn, a dynamic sparse attention mechanism co-designed with NVIDIA Sparse Tensor Cores. DynSpAttn introduces a dual-side 2:4 structured sparsity strategy that prunes both the Query and Score matrices, thereby transforming the dominant matrix multiplications in attention into sparse matrix multiplications (SpMMs) executable on SpTCs. To realize this transformation, DynSpAttn incorporates lightweight in-register pruners and a shuffle-free operand remapping scheme within a fully fused, I/O-aware CUDA kernel. Evaluations on RTX 4090 and L20 GPUs show that DynSpAttn achieves up to 1.70 × kernel-level preformance improvement over FlashAttention and 1.58 × end-to-end inference speedup. These results demonstrate that co-designing semi-structured sparsity with hardware support across the full attention pipeline provides a practical and efficient solution for LLM inference.

Overlapping communication and computation operators is a common practice to hide communication overheads, accelerating large language models (LLMs) training on GPU clusters. Existing systems achieve this through either intra-operator fusion (IntraFusion), which packs operators into a single large kernel, or inter-operator decomposition (InterDecom), which splits a tensor into multiple parts for pipelined execution. However, current IntraFusion methods underutilize network topology, causing suboptimal bandwidth usage on multi-GPU systems, while InterDecom struggles to determine the optimal number of decomposed parts for peak performance. To address these issues, we introduce Compass, which employs systematic optimization and comprehensive modeling. First, we design a novel IntraFusion algorithm leveraging double-ring communications to maximize bandwidth utilization in hybrid NVLink-PCIe systems, achieving 1.5x-2.5x speedups. Second, we develop a decomposition model that mathematically derives the optimal tensor decomposition degree for InterDecom, improving performance by up to 1.3x. Finally, we develop a unified performance framework that accurately determines the best strategy for different scenarios. We validate Compass through extensive evaluation across 288 configurations and end-to-end experiments on real-world applications. The results demonstrate that Compass consistently selects the optimal strategy, achieving up to a 1.42x end-to-end speedup compared to the Megatron-LM baseline.

All-Pairs Shortest Path (APSP), a fundamental problem in graph analytics, can be solved efficiently by reducing the computational workload through vertex reordering. However, it fails on GPUs due to fine-grained granularity, shape, and dependency irregularities, which cause severe hardware underutilization. We introduce ROME, a system that tames these irregularities by spatially restructuring computation into regularized workloads and temporally overlapping them with an asynchronous pipeline. ROME achieves 14.7-244.5× speedup over the state-of-the-art multicore CPU solution and 11.2-338.0× speedup over the state-of-the-art GPU solution. Notably, our results achieve mostly above 20% and up to 34.7% of peak min-plus OPs across all tested graphs.

Communication has emerged as a critical bottleneck in the distributed training of large language models (LLMs). While numerous approaches have been proposed to reduce communication overhead, the potential of lossless compression has remained largely underexplored since compression and decompression typically consume larger overheads than the benefits of reduced communication traffic. We observe that the communication data, including activations, gradients and parameters, during training often follows a near-Gaussian distribution, which is a key feature for data compression. Thus, we introduce ZipCCL, a lossless compressed communication library of collectives for LLM training. ZipCCL is equipped with our novel techniques: (1) theoretically grounded exponent coding that exploits the Gaussian distribution of LLM tensors to accelerate compression without expensive online statistics, (2) GPU-optimized compression and decompression kernels that carefully design memory access patterns and pipeline using communication-aware data layout, and (3) adaptive communication strategies that dynamically switch collective operations based on workload patterns and system characteristics. Evaluated on a 64-GPU cluster using both mixture-of-experts and dense transformer models, ZipCCL reduces communication time by up to 1.35X and achieves end-to-end training speedups of up to 1.18X without any impact on model quality.

Industrial Cyber-Physical Systems (ICPS) are increasingly vulnerable to sophisticated attacks and operational disturbances that induce subtle and hard-to-detect anomalies, particularly in industrial edge environments. Existing anomaly detection methods often rely on sufficient labeled data and involve excessive computational overhead, hindering real-time detection and lightweight deployment. To address these challenges, we propose a Multimodal Feature fusion-enhanced time series Anomaly Detection framework (MFAD) in ICPS. MFAD enhances the representation of subtle anomalies by jointly modeling temporal dynamics and industrial characteristics through a unified multimodal feature fusion mechanism. Moreover, MFAD adopts a three-stage detection strategy with adaptive thresholding, which further improves robustness under varying operating conditions, while its lightweight overall architecture supports edge deployment. In addition, we provide the Industrial Gas Cyber-Physical System (IGCPS) dataset collected from real-world industrial operations. Experiments on ICPS benchmark datasets of varying scales, including IGCPS, PUMP, WADI, and SWaT, demonstrate that MFAD achieves an F1 score exceeding 96.7% with efficient resource utilization, validating its effectiveness for real-time detection and lightweight deployment in resource-constrained industrial edge environments. Note to Practitioners—This paper is motivated by the increasing need for reliable and efficient anomaly detection in Industrial Cyber-Physical Systems (ICPS), particularly deployed in resource-constrained industrial edge environments. Existing approaches often treat temporal and industrial features separately, rely on sufficient labeled data, and require substantial computational resources, which limits their applicability in real-world industrial settings. In contrast, the proposed MFAD provides a lightweight and practical solution that integrates multimodal feature fusion with robust semi-supervised detection mechanisms to effectively capture subtle anomalies in time series industrial data. The framework is designed with deployment feasibility that it offers strong detection accuracy, low latency, and efficient resource consumption suitable for industrial edge devices. The methods presented here can inform practitioners seeking to enhance the reliability and real-time performance of ICPS anomaly detection systems. Future extensions may focus on expanding MFAD for broader online industrial applications, integrating it with more edge platforms, and enabling large-scale distributed deployment.

Deep learning methods have got a great success in high-resolution remote sensing analysis, especially Convolution Neural Network (CNN) and Transformer. However, CNNs have a failure in modeling the long-range dependency because of their fixed receptive fields and Transformers suffer from quadratic computational complexity relative to image resolution. The RWKV model achieves breakthroughs in natural language processing (NLP) through its linear-complexity sequence modeling; however, it exhibits anisotropic limitations in vision tasks due to the constraints of its one-dimensional scanning mechanism. To address these challenges, we adapt the RWKV architecture to high-resolution remote sensing and propose the Remote Sensing RWKV (RSRWKV) model, which incorporates a Linear-Complexity 2D Attention Mechanism. Specifically, RSRWKV employs a novel 2D-WKV scanning mechanism that bridges sequential processing with two-dimensional spatial reasoning while maintaining linear computational complexity. This design facilitates the aggregation of isotropic contexts in multiple spatial directions. Then, the MVC-Shift module further optimizes multiscale receptive field coverage, whereas the Efficient Channel Attention (ECA) module improves cross-channel feature interaction and semantic saliency modeling. Experimental evaluations on the NWPU RESISC45, VHR-10 v2, SSDD and GLHWater datasets demonstrate that RSRWKV surpasses CNN and Transformer baselines in classification, detection and segmentation tasks, establishing a scalable framework for high-resolution remote sensing analysis. Code available at https://github.com/Ling-yunchi/RSRWKV.

While stock prediction task traditionally relies on volume-price and fundamental data to predict the return ratio or price movement trend, sentiment factors derived from social media platforms such as StockTwits offer a complementary and useful source of real-time market information. However, we find that most social media posts, along with the public sentiment they reflect, provide limited value for trading predictions due to their noisy nature. To tackle this, we propose a novel dynamic expert tracing algorithm that filters out non-informative posts and identifies both true and inverse experts whose consistent predictions can serve as valuable trading signals. Our approach achieves significant improvements over existing expert identification methods in stock trend prediction. However, when using binary expert predictions to predict the return ratio, similar to all other expert identification methods, our approach faces a common challenge of signal sparsity with expert signals cover only about 4% of all stock-day combinations in our dataset. To address this challenge, we propose a dual graph attention neural network that effectively propagates expert signals across related stocks, enabling accurate prediction of return ratios and significantly increasing signal coverage. Empirical results show that our propagated expert-based signals not only exhibit strong predictive power independently but also work synergistically with traditional financial features. These combined signals significantly outperform representative baseline models in all quant-related metrics including predictive accuracy, return metrics, and correlation metrics, resulting in more robust investment strategies. We hope this work inspires further research into leveraging social media data for enhancing quantitative investment strategies. The code can be seen inhttps://github.com/wanyunzh/DualGAT.

Large language models (LLMs) have unlocked a plethora of powerful applications at the network edge, such as intelligent personal assistants. Data privacy and security concerns have prompted a shift towards edge-based fine-tuning of personal LLMs, away from cloud reliance. However, this raises issues of computational intensity and resource scarcity, hindering training efficiency and feasibility. While current studies investigate parameter-efficient fine-tuning (PEFT) techniques to mitigate resource constraints, our analysis indicates that these techniques are not sufficiently resource-efficient for edge devices. Other studies focus on exploiting the potential of edge devices through resource management optimization, yet are ultimately bottlenecked by the resource wall of individual devices. To tackle these challenges, we proposePAC+, a resource efficient collaborative edge AI framework for in-situ personal LLMs fine-tuning.PAC+breaks the resource wall of personal LLMs fine-tuning with a sophisticated algorithm-system co-design. (1) Algorithmically,PAC+implements a personal LLMs fine-tuning technique that is efficient in terms of parameters, time, and memory. It utilizes Parallel Adapters to circumvent the need for a full backward pass through the LLM backbone. Additionally, an activation cache mechanism further streamlining the process by negating the necessity for repeated forward passes across multiple epochs. (2) Systematically,PAC+leverages edge devices in close proximity, pooling them as a collective resource for in-situ personal LLMs fine-tuning, utilizing a hybrid data and pipeline parallelism to orchestrate distributed training. The use of the activation cache eliminates the need for forward pass through the LLM backbone, enabling exclusive fine-tuning of the Parallel Adapters using data parallelism. Extensive evaluation of the prototype implementation demonstrates thatPAC+significantly outperforms existing collaborative edge training systems, achieving up to a$9.7\times$end-to-end speedup. Furthermore, compared to mainstream LLM fine-tuning algorithms,PAC+reduces memory footprint by up to$88.16\%$.

The Artificial Intelligence Generated Content (AIGC) technique has gained significant traction for producing diverse content. However, existing AIGC services typically operate within a centralized framework, resulting in high response times. To address this issue, we integrate collaborative Mobile Edge Computing (MEC) technology to reduce processing delays for AIGC services. Current collaborative MEC methods primarily support single-server offloading or facilitate interactions among fixed Edge Servers (ESs), limiting flexibility and resource utilization across all ESs to meet the varying computing and networking requirements of AIGC services. We propose AMCoEdge, an adaptive multi-server collaborative MEC approach to enhancing AIGC service efficiency. The AMCoEdge fully utilizes the computing and networking resources across all ESs through adaptive multi-ES selection and dynamic workload allocation, thereby minimizing the offloading make-span of AIGC services. Our design features an online distributed algorithm based on deep reinforcement learning, accompanied by theoretical analyses that confirm an approximate linear time complexity. Simulation results show that our method outperforms state-of-the-art baselines, achieving at least an$11.04\%$reduction in task offloading make-span and a$44.86\%$decrease in failure rate. Additionally, we develop a distributed prototype system to implement and evaluate our AMCoEdge method for real AIGC service execution, demonstrating service delays that are$9.23\% - 31.98\%$lower than the three representative methods.

Due to the rapid development of panorama cameras, the task of estimating panorama depth has attracted significant attention from the computer vision community, especially in applications such as robot sensing and autonomous driving. However, existing methods relying on different projection formats often encounter challenges, either struggling with distortion and discontinuity in the case of equirectangular, cubemap, and tangent projections, or experiencing a loss of texture details with the spherical projection. To tackle these concerns, we present SphereFusion, an end-toend framework that combines the strengths of various projection methods. Specifically, SphereFusion initially employs$2 D$image convolution and mesh operations to extract two distinct types of features from the panorama image in both equirectangular and spherical projection domains. These features are then projected onto the spherical domain, where a gate fusion module selects the most reliable features for fusion. Finally, SphereFusion estimates panorama depth within the spherical domain. Meanwhile, SphereFusion employs a cache strategy to improve the efficiency of mesh operation. Extensive experiments on three public panorama datasets demonstrate that SphereFusion achieves competitive results with other state-of-theart methods, while presenting the fastest inference speed at only 17 ms on a$512 \times 1024$panorama image.

Recent advancements in Zero-shot Neural Architecture Search (NAS) highlight the ability of zero-cost proxies in identifying superior architecture. However, we identify a critical issue with current zero-cost proxies: they aggregate node-wise zero-cost statistics without considering that not all nodes in a neural network equally impact performance estimation. Our observations reveal that node-wise zero-cost statistics significantly vary in their contributions to performance, with each node exhibiting a degree of uncertainty. Based on this insight, we introduce a novel method called Parametric Zero-Cost Proxies (ParZC) framework to enhance the adaptability of zero-cost proxies through parameterization. To address the node indiscrimination, we propose a Mixer Architecture with Bayesian Network (MABN) to explore the node-wise zero-cost statistics and estimate node-specific uncertainty. Moreover, we propose DiffKendall as a loss function to improve ranking consistency. Comprehensive experiments on NAS-Bench-101, 201, and NDS demonstrate the superiority of our proposed ParZC compared to existing zero-shot NAS methods. Additionally, we demonstrate the versatility and adaptability of ParZC on Vision Transformer search space.

Knowledge editing (KE) has emerged as a prominent alternative that enables efficient and precise information modification inside language models.However, a critical challenge arises in continuous language model editing -a significant performance decline both in knowledge update and retention when the number of edits increases.By dissecting the perturbation weight of language model in continuous KE, we uncover that disentangled and sparsified knowledge representation can significantly alleviate the performance decline.Building on these insights, we introduce AdaEdit, a novel knowledge editing method.Extensive empirical evaluations on multiple LLMs demonstrate that our proposed methods can enhance the performance of edited LLMs in large-size continuous editing regimes, outperforming existing ones without substantially compromising the general abilities of these models.

Recent large language models (LLMs) have tended to leverage sparsity to reduce computations, employing the sparsely activated mixture-of-experts (MoE) technique. MoE introduces four modules, including token routing, token communication, expert computation, and expert parallelism, that impact model quality and training efficiency. To enable ver- satile usage of MoE models, we introduce FSMoE, a flexible training system optimizing task scheduling with three novel techniques: 1) Unified abstraction and online profiling of MoE modules for task scheduling across various MoE implementations. 2) Co-scheduling intra-node and inter-node communications with computations to minimize communication overheads. 3) To support near-optimal task scheduling, we design an adaptive gradient partitioning method for gradient aggregation and a schedule to adaptively pipeline communications and computations. We conduct extensive experiments with configured MoE layers and real-world MoE models on two GPU clusters. Experimental results show that 1) our FSMoE supports four popular types of MoE routing functions and is more efficient than existing implementations (with up to a 1.42× speedup), and 2) FSMoE outperforms the state-of-the-art MoE training systems (DeepSpeed-MoE and Tutel) by 1.18×-1.22× on 1458 MoE layers and 1.19×-3.01× on real-world MoE models based on GPT-2 and Mixtral using a popular routing function. In this work, we present a flexible training system named FSMoE to optimize task scheduling. To achieve this goal: 1) we design unified abstraction and online profiling of MoE modules across various MoE implementations, 2) we co-schedule intra-node and inter-node communications with computations to minimize communication overhead, and 3) we design an adaptive gradient partitioning method for gradient aggregation and a schedule to adaptively pipeline communications and computations. Experimental results on two clusters up to 48 GPUs show that our FSMoE outperforms the state-of-the-art MoE training systems (DeepSpeed-MoE and Tutel) with speedups of 1.18x-1.22x on 1458 customized MoE layers and 1.19x-3.01x on real-world MoE models based on GPT-2 and Mixtral.

In recent years, accurately and quickly deploying medical large language models (LLMs) has become a trend. Among these, retrieval-augmented generation (RAG) has garnered attention due to rapid deployment and privacy protection. However, the challenge hinder the practical deployment of RAG for medical diagnosis: the semantic gap between colloquial patient descriptions and the professional terminology within medical knowledge bases. We try to address the challenge from the data perspective and the method perspective. First, to address the semantic gap in existing knowledge bases, we construct DiagnosGraph, a generalist knowledge graph covering both modern medicine and Traditional Chinese Medicine. It contains 876 common diseases with the graph of 7,997 nodes and 37,201 triples. To bridge the gap between colloquial patient narratives and academic medical knowledge, DiagnosGraph also introduces 1,908 medical record by formalizing the patient chief complaint and proposing a medical diagnosis. Second, we introduce the Multi-Round Diagnostic RAG (MRD-RAG) framework. It utilizes a multi-round dialogue to refine diagnostic possibilities, emulating the clinical reasoning of a physician. Experiments conducted on four medical benchmarks, with evaluations by human physicians, demonstrate that MRD-RAG enhances the diagnostic performance of LLMs, highlighting its potential to make automated diagnosis more accurate and human-aligned. The codebase and supplementary materials can be found at our page11https://sites.google.com/view/mrd-rag.

Large Language Models (LLMs) have demonstrated remarkable capabilities, but their immense scale poses significant challenges in terms of both memory and computational costs. While unstructured pruning offers promising solutions by introducing sparsity to reduce resource requirements, realizing its benefits in LLM inference remains elusive. This is primarily due to the storage overhead of indexing non-zero elements and the inefficiency of sparse matrix multiplication (SpMM) kernels at low sparsity levels (around 50%). In this paper, we present SpInfer, a high-performance framework tailored for sparsified LLM inference on GPUs. SpInfer introduces Tensor-Core-Aware Bitmap Encoding (TCA-BME), a novel sparse format that minimizes indexing overhead by leveraging efficient bitmap-based indexing, optimized for GPU Tensor Core architectures. Furthermore, SpInfer integrates an optimized SpMM kernel with Shared Memory Bitmap Decoding (SMBD) and asynchronous pipeline design to enhance computational efficiency. Experimental results show that SpInfer significantly outperforms state-of-the-art SpMM implementations (up to 2.14× and 2.27× over Flash-LLM and SparTA, respectively) across a range of sparsity levels (30% to 70%), with substantial improvements in both memory efficiency and end-to-end inference speed (up to 1.58×). SpInfer outperforms highly optimized cuBLAS at sparsity levels as low as 30%, marking the first effective translation of unstructured pruning's theoretical advantages into practical performance gains for LLM inference.

The utilization of the sparsely activated mixture-of-experts (MoE) technique has enabled the expansion of modern large language models (LLMs) to trillion-level sizes while maintaining a sub-linear increase in computations. This involves equipping an MoE layer with multiple experts, where only one or two experts are activated for each input data. However, the dynamic activation of MoE experts introduces extensive communications, limiting the scaling efficiency of distributed systems. In this work, we propose Mast to efficiently train MoE models by pipelining and re-ordering communication and computation tasks to effectively hide communication costs. Specifically, we first propose to overlap tasks in both attention layers and MoE layers. Then we theoretically analyze the task overlaps between communications and computations, identifying the inefficiencies of existing schedules. We then develop an optimization formulation to determine a near-optimal order for task pipelining with the objective of minimizing iteration time. We conduct extensive experiments on two 32-GPU clusters employing 432 configured MoE layers and three real-world MoE models based on BERT, GPT-2 and Mistral. The experimental results demonstrate that Mast outperforms state-of-the-art MoE training systems (DeepSpeed-MoE, Tutel, PipeMoE and CoCoNet) with an average speedup 1.13 ×-1.43 × on the MoE models.

Sparsely activated Mixture-of-Experts (MoEs) models have become prominent in Large Language Models (LLMs) due to their ability to expand model capacity without proportional increases in computation. MoE layers feature multiple experts, with only a few activated per sample, enhancing model performance across various domains such as natural language generation and translation. The dynamic activation of MoE experts introduces extensive communications in distributed training. However, this dynamic activation creates communication challenges in distributed training. While previous work attempted to pipeline computation and communication through input chunking, we found that these tasks compete for Stream Multiprocessors (SMs) on GPUs, making the scheduling ineffective. In this paper, we update the optimization problem to minimize training time while accounting for SM contentions. We develop performance models for computation and communication tasks to identify MoE layer bottlenecks. By delaying GEMM launching and splitting GEMM operations, we enable communication to preempt SMs, enhancing overall efficiency and more stability.

In this paper, we present the first structural binarization method for LLM compression to less than 1-bit precision. Although LLMs have achieved remarkable performance, their memory-bound nature during the inference stage hinders the adoption of resource-constrained devices. Reducing weights to 1-bit precision through binarization substantially enhances computational efficiency. We observe that randomly flipping some weights in binarized LLMs does not significantly degrade the model's performance, suggesting the potential for further compression. To exploit this, our STBLLM employs an N:M sparsity technique to achieve structural binarization of the weights. Specifically, we introduce a novel Standardized Importance (SI) metric, which considers weight magnitude and input feature norm to more accurately assess weight significance. Then, we propose a layer-wise approach, allowing different layers of the LLM to be sparsified with varying N:M ratios, thereby balancing compression and accuracy. Furthermore, we implement a fine-grained grouping strategy for less important weights, applying distinct quantization schemes to sparse, intermediate, and dense regions. Finally, we design a specialized CUDA kernel to support structural binarization. We conduct extensive experiments on LLaMA, OPT, and Mistral family. STBLLM achieves a perplexity of 11.07 at 0.55 bits per weight, outperforming the BiLLM by 3×. The results demonstrate that our approach performs better than other compressed binarization LLM methods while significantly reducing memory requirements. Code is released at https://github.com/pprp/STBLLM.

Personalized federated learning (PFL) achieves high performance by assuming clients only meet test data locally, which does not meet many generic federated learning (GFL) scenarios. In this work, we theoretically show that PMs can be used to enhance GFL with a new learning problem named Selective FL (SFL), which involves optimizing PFL and model selection. However, storing and selecting whole models requires impractical computation and communication costs. To practically solve SFL, inspired by model components that attempt to edit a sub-model for specific purposes, we design an efficient and effective framework named Hot-Pluggable Federated Learning (HPFL). Specifically, clients individually train personalized plug-in modules based on a shared backbone, and upload them with a plug-in marker on the server modular store. In inference stage, an accurate selection algorithm allows clients to identify and retrieve suitable plug-in modules from the modular store to enhance their generalization performance on the target data distribution. Furthermore, we provide differential privacy protection during the selection with theoretical guarantee. Our comprehensive experiments and ablation studies demonstrate that HPFL significantly outperforms state-of-the-art GFL and PFL algorithms. Additionally, we empirically show HPFL's remarkable potential to resolve other practical FL problems such as continual federated learning and discuss its possible applications in one-shot FL, anarchic FL, and FL plug-in market. Our work is the first attempt towards improving GFL performance through a selecting mechanism with personalized plug-ins.

Post-training compression reduces the computational and memory costs of large language models (LLMs), enabling resource-efficient deployment. However, existing compression benchmarks focus narrowly on language modeling (e.g., perplexity) and natural language understanding tasks (e.g., GLUE accuracy), ignoring the agentic capabilities—workflow, tool use/function call, long-context understanding and real-world application. We introduce the Agent Compression Benchmark (ACBench), the first comprehensive benchmark for evaluating how compression impacts LLMs' agentic abilities. ACBench spans (1) 12 tasks across 4 capabilities (e.g., WorfBench for workflow generation, Needle-in-Haystack for long-context retrieval), (2) 4-bit quantization (GPTQ, AWQ) and 50% pruning (Wanda, SparseGPT), and (3) 15 models, including small (Gemma-2B), standard (Qwen2.5-7B), and distilled reasoning LLMs (DeepSeek-R1-Distill). Our experiments reveal compression tradeoffs: 4-bit quantization preserves workflow generation and tool use (1%--3% drop) but degrades real-world application accuracy by 10%--15%. We introduce ERank, Top-k Ranking Correlation and Energy to systematize analysis. ACBench provides actionable insights for optimizing LLM compression in agentic scenarios, bridging the gap between algorithmic efficiency and real-world applicability.

Accurate and efficient 3D scene understanding from multi-view images remains a fundamental challenge in autonomous driving. Existing methods often struggle with high-dimensional features, leading to excessive computational costs and memory usage. In this paper, we present SAFormer, a novel transformer-based framework for efficient spatially adaptive occupancy prediction. SAFormer incorporates two key techniques to reduce resource consumption: Octree-based Multi-resolution Feature (OMRF) Learning and Spatial-Adaptive Progressive Query (SAPQ). First, OMRF introduces an Octree-based hierarchical structure to compress multi-resolution 3D feature volumes. Second, SAPQ facilitates efficient information flow across different scales while effectively addressing scene sparsity. It employs a region-aware query mechanism that intelligently allocates computational resources, processing safety-critical regions at high resolution while handling background elements at lower resolutions. Experiments on the nuScenes dataset demonstrate that our method achieves state-of-the-art performance while significantly reducing inference latency (up to 3×) and memory cost (up to 2.9×). Additional experiments on SSCBench-KITTI-360 further validate our approach’s generalizability. Our approach excels in managing scene sparsity and recognizing small, safety-critical objects, highlighting its potential for practical applications in autonomous driving.

Neural Radiance Fields (NeRF) and 3D Gaussian Splatting (3DGS) have emerged as powerful tools for 3D reconstruction and SLAM tasks. However, their performance depends heavily on accurate camera pose priors. Existing approaches attempt to address this issue by introducing external constraints but fall short of achieving satisfactory accuracy, particularly when camera trajectories are complex. In this paper, we propose a novel method, RA-NeRF, capable of predicting highly accurate camera poses even with complex camera trajectories. Following the incremental pipeline, RA-NeRF reconstructs the scene using NeRF with photometric consistency and incorporates flow-driven pose regulation to enhance robustness during initialization and localization. Additionally, RA-NeRF employs an implicit pose filter to capture the camera movement pattern and eliminate the noise for pose estimation. To validate our method, we conduct extensive experiments on the Tanks&Temple dataset for standard evaluation, as well as the NeRFBuster dataset, which presents challenging camera pose trajectories. On both datasets, RA-NeRF achieves state-of-the-art results in both camera pose estimation and visual quality, demonstrating its effectiveness and robustness in scene reconstruction under complex pose trajectories.

Despite efforts to improve the quality of service (QoS) and throughput in Large Language Model (LLM) serving systems, progress is often limited by the lack of publicly available real-world workloads.Consequently, evaluations usually depend on synthetic or oversimplified load patterns, and systems that appear promising in testing frequently underperform once deployed.This work presents BurstGPT, an LLM serving workload with 10.31 million traces from regional Azure OpenAI GPT services * Both authors contributed equally to this research.

Pattern matching is a key operation in unstructured data analytics, commonly supported by regular expression (regex) engines.Bitparallel regex engines compile regexes into bitstream programs, which expose fine-grained parallelism and are well-suited for GPU execution.A straightforward strategy executes each bitstream instruction sequentially, processing all data blocks in a loop.However, this execution suffers from poor data reuse and high memory consumption, limiting throughput.Our key insight is to adopt an interleaved execution model, where all bitstream instructions are fused into a single loop and executed block-wise.While interleaved execution could improve data reuse, enabling it on GPUs is non-trivial due to cross-block data dependencies.To address this, we introduce 1) Dependency-Aware Thread-Data Mapping, which resolves cross-block dependencies via selective recomputation.We further improve interleaved execution performance with two additional optimizations: 2) Shift Rebalancing, which balances dependency chains to reduce synchronization barriers; and 3) Zero Block Skipping, which exploits bitstream sparsity to skip computation on zero blocks.Together, these techniques make interleaved execution practical and efficient.Experiments on real-world regex benchmarks demonstrate a 19.5× geometric mean speedup over the state-of-theart GPU regex engine.

Scene understanding enables intelligent agents to interpret and comprehend their environment. While existing large vision-language models (LVLMs) for scene understanding have primarily focused on indoor household tasks, they face two significant limitations when applied to outdoor large-scale scene understanding. First, outdoor scenarios typically encompass larger-scale environments observed through various sensors from multiple viewpoints (e.g., bird view and terrestrial view), while existing indoor LVLMs mainly analyze single visual modalities within building-scale contexts from humanoid viewpoints. Second, existing LVLMs suffer from missing multidomain perception outdoor data and struggle to effectively integrate 2D and 3D visual information. To address the aforementioned limitations, we build the first multidomain perception outdoor scene understanding dataset, named SVM-City, deriving from multi-Scale scenarios with multi-View and multi-Modal instruction tuning data. It contains 420k images and 4, 811M point clouds with 567k question-answering pairs from vehicles, low-altitude drones, high-altitude aerial planes, and satellite. To effectively fuse multimodal data in the absence of one modality, we introduce incomplete multimodal learning to model outdoor scene understanding and design the LVLM named City-VLM. Multimodal fusion is realized by constructed as a joint probabilistic distribution space rather than implementing directly explicit fusion operations (e.g., concatenation). Experimental results on three typical outdoor scene understanding tasks show City-VLM achieves 18.14 % performance surpassing existing LVLMs in question-answering tasks averagely. Our method demonstrates pragmatic and generalization performance across multiple outdoor scenes.

Large Language Models (LLMs) require significant GPU memory when processing long texts, with the key value (KV) cache consuming up to 70\% of total memory during inference. Although existing compression methods reduce memory by evaluating the importance of individual tokens, they overlook critical semantic relationships between tokens, resulting in fragmented context and degraded performance. We introduce \method{}, which fundamentally reimagines KV cache compression by treating semantic chunks - rather than isolated tokens - as basic compression units. This approach preserves complete linguistic structures and contextual integrity, ensuring that essential meaning is retained even under aggressive compression. Our innovation includes a novel layer-wise index reuse technique that exploits the higher cross-layer similarity of preserved indices in \method{}, reducing computational overhead and improving throughput by 26.5\%. Comprehensive evaluations on challenging benchmarks: LongBench, Needle-In-A-HayStack, GSM8K, and JailbreakV demonstrate that \method{} outperforms state-of-the-art methods by up to 8.7\% in precision while maintaining the same compression ratio. These results confirm that semantic-aware compression significantly enhances both efficiency and performance for long-context LLM inference, providing a simple yet effective solution to the memory bottleneck problem. \emph{The code is available at \href{https://github.com/NVIDIA/kvpress}{link}.}

Cloud service providers heavily colocate high-priority, latency sensitive (LS), and low-priority, best-effort (BE) DNN inference services on the same GPU to improve resource utilization in data centers. Among the critical shared GPU resources, there has been very limited analysis on the dynamic allocation of compute units and VRAM bandwidth, mainly for two reasons: (1) The native GPU resource management solutions are either hardware-specific, or unable to dynamically allocate resources to different tenants, or both; (2) NVIDIA doesn't expose interfaces for VRAM bandwidth allocation, and the software stack and VRAM channel architectures are black-box, both of which limit the software-level resource management. These drive prior work to design either conservative sharing policies detrimental to throughput, or static resource partitioning only applicable to a few GPU models.

Private set intersection (PSI) has emerged as a key cryptographic protocol, enabling secure data sharing and facilitating collaborative computing among distributed data providers in recent years. However, it remains challenging to achieve efficient multiparty private set intersection (MPSI) for large-scale data and numerous participants in an open environment. To this end, we propose EL-MPSI, an Efficient and Lightweight MPSI scheme based on Vector Oblivious Linear Evaluation (VOLE) and Oblivious Key-Value Store (OKVS), which enables secure data sharing in settings with millions of datasets and dozens of participants. By simplifying the interaction process among multiple participants, the proposed scheme achieves constant-level round complexity and provides resistance against malicious adversaries, as well as collusion attack. Through theoretical analysis and experiments, we demonstrate that the security, efficiency and scalability of our scheme perform better than existing state-of-the-art (SOTA) works. For millions of datasets and dozens of participants, EL-MPSI achieves second-level latency while keeping client communication overhead to approximately 10 MB. Moreover, in scenarios of malicious adversary setting, the extra execution overhead is negligible, which effectively facilitates large-scale data sharing.

Infrared and visible images are captured using different sensors, resulting in various differences between the two modalities. However, current image fusion methods mainly focus on retaining global information, while neglecting to preserve the salient objects of the two source images. Additionally, existing evaluation metrics fail to measure whether the salient objects are preserved in the fused image from the two original modalities. To this end, we propose a novel image fusion method for infrared and visible images called SCFusion, which maintains salient objects consistency between the original two modalities and the fused image. Specifically, we designed a new module called the saliency decision (SD) to separate the unique and common saliency maps from the infrared and visible images for target enhancement in the final fused image. We then introduce a new metric called saliency information weight (SIW) to evaluate the preservation of salient objects by calculating the overlap between the saliency map of the fused image and those of the original modalities. To validate the practical application of our fusion algorithm, we establish a physical visible-infrared fusion system integrating SCFusion to provide real-time service, including a dual-sensor camera and an AI edge platform. Quantitative and qualitative experiments demonstrate the superiority of SCFusion over state-of-the-art methods in terms of salient objects preservation from the original two modalities.

Robotic grasping is a fundamental ability for a robot to interact with the environment. Current methods focus on how to obtain a stable and reliable grasping pose in object level, while little work has been studied on part (shape)-wise grasping which is related to fine-grained grasping and robotic affordance. Parts can be seen as atomic elements to compose an object, which contains rich semantic knowledge and a strong correlation with affordance. However, lacking a large part-wise 3D robotic dataset limits the development of part representation learning and downstream applications. In this paper, we propose a new large Language-guided SHape grAsPing datasEt (named LangSHAPE) to promote 3D part-level affordance and grasping ability learning. From the perspective of robotic cognition, we design a two-stage fine-grained robotic grasping framework (named LangPartGPD), including a novel 3D part language grounding model and a partaware grasp pose detection model, in which explicit language input from human or large language models (LLMs) could guide a robot to generate part-level 6-DoF grasping pose with textual explanation. Our method combines the advantages of humanrobot collaboration and LLMs’ planning ability using explicit language as a symbolic intermediate. To evaluate the effectiveness of our proposed method, we perform 3D part grounding and fine-grained grasp detection experiments on both simulation and physical robot settings, following language instructions across different degrees of textual complexity. Results show our method achieves competitive performance in 3D geometry fine-grained grounding, object affordance inference, and 3D part-aware grasping tasks. Our dataset and code are available on our project website https://sites.google.com/view/lang-shape.

In the realm of driving technologies, fully autonomous vehicles have not been widely adopted yet, making advanced driver assistance systems (ADAS) crucial for enhancing driving experiences. Among these, car-following behavior modeling plays a pivotal role, forming the foundation for systems that ensure safe and efficient vehicle interactions. However, current approaches often rely on fixed parameters, failing to capture the diverse social preferences and driving styles of individuals. To overcome these limitations, we propose the Editable Behavior Generation (EBG) model, a data-driven car-following model that allows for adjusting driving discourtesy levels. The framework integrates diverse courtesy calculation methods into long short-term memory (LSTM) and Transformer architectures, offering a comprehensive approach to capture nuanced driving dynamics. By integrating various discourtesy values during the training process, our model generates realistic agent trajectories with different levels of courtesy in car-following behavior. Experimental results on the naturalistic datasets showcase a reduction in Mean Squared Error (MSE) of spacing and MSE of speed compared to baselines, establishing style controllability. To the best of our knowledge, this work represents the first data-driven car-following model capable of dynamically adjusting discourtesy levels. Our model provides valuable insights for the development of ADAS that take into account drivers’ social preferences.

Transformer-based models have unlocked a plethora of powerful intelligent applications at the edge, such as voice assistant in smart home. Traditional deployment approaches offload the inference workloads to the remote cloud server, which would induce substantial pressure on the backbone network as well as raise users' privacy concerns. To address that, in-situ inference has been recently recognized for edge intelligence, but it still confronts significant challenges stemming from the conflict between intensive workloads and limited on-device computing resources. In this paper, we leverage our observation that many edge environments usually comprise a rich set of accompanying trusted edge devices with idle resources and proposeGalaxy+, a collaborative edge AI system that breaks the resource walls across heterogeneous edge devices for efficient Transformer inference acceleration.Galaxy+introduces a novel hybrid model parallelism to orchestrate collaborative inference, along with a heterogeneity and memory-aware parallelism planning for fully exploiting the resource potential. To mitigate the impact of tensor synchronizations on inference latency under bandwidth-constrained edge environments,Galaxy+devises a tile-based fine-grained overlapping of communication and computation. Furthermore, a fault-tolerant re-scheduling mechanism is developed to address device-level resource dynamics, ensuring stable and low-latency inference. Extensive evaluation based on prototype implementation demonstrates thatGalaxy+remarkably outperforms state-of-the-art approaches under various edge environment setups, achieving a$1.2\times$to$4.24\times$end-to-end latency reduction. Besides,Galaxy+can adapt to device-level resource dynamics, swiftly rescheduling and restoring inference in the presence of unexpected straggler devices.

Neural Radiance Fields have demonstrated impressive performance in novel view synthesis. However, NeRF and most of its variants still rely on traditional complex pipelines to provide extrinsic and intrinsic camera parameters, such as COLMAP. Recent works, like NeRFmm, BARF, and L2G-NeRF, directly treat camera parameters as learnable and estimate them through differential volume rendering. However, these methods work for forward-looking scenes with slight motions and fail to tackle the rotation scenario in practice. To overcome this limitation, we propose a novel camera parameter free neural radiance field (CF-NeRF), which incrementally reconstructs 3D representations and recovers the camera parameters inspired by incremental structure from motion. Given a sequence of images, CF-NeRF estimates camera parameters of images one by one and reconstructs the scene through initialization, implicit localization, and implicit optimization. To evaluate our method, we use a challenging real-world dataset, NeRFBuster, which provides 12 scenes under complex trajectories. Results demonstrate that CF-NeRF is robust to rotation and achieves state-of-the-art results without providing prior information and constraints.

The upscaling of Large Language Models (LLMs) has yielded impressive advances in natural language processing, yet it also poses significant deployment challenges.Weight quantization has emerged as a widely embraced solution to reduce memory and computational demands.This paper introduces BitDistiller, a framework that synergizes Quantization-Aware Training (QAT) with Knowledge Distillation (KD) to boost the performance of LLMs at ultra-low precisions (sub-4-bit).Specifically, BitDistiller first incorporates a tailored asymmetric quantization and clipping technique to maximally preserve the fidelity of quantized weights, and then proposes a novel Confidence-Aware Kullback-Leibler Divergence (CAKLD) objective, which is employed in a self-distillation manner to enable faster convergence and superior model performance.Empirical evaluations demonstrate that BitDistiller significantly surpasses existing methods in both 3-bit and 2-bit configurations on general language understanding and complex reasoning benchmarks.Notably, Bit-Distiller is shown to be more cost-effective, demanding fewer data and training resources.

Sparse Matrix-Matrix Multiplication (SpMM) is a building-block operation in scientific computing and machine learning applications. Recent advancements in hardware, notably Tensor Cores (TCs), have created promising opportunities for accelerating SpMM. However, harnessing these hardware accelerators to speed up general SpMM necessitates considerable effort. In this paper, we undertake a comprehensive analysis of the state-of-the-art techniques for accelerating TC-based SpMM and identify crucial performance gaps. Drawing upon these insights, we propose DTC-SpMM, a novel approach with systematic optimizations tailored for accelerating general SpMM on TCs. DTC-SpMM encapsulates diverse aspects, including efficient compression formats, reordering methods, and runtime pipeline optimizations. Our extensive experiments on modern GPUs with a diverse range of benchmark matrices demonstrate remarkable performance improvements in SpMM acceleration by TCs in conjunction with our proposed optimizations. The case study also shows that DTC-SpMM speeds up end-to-end GNN training by up to 1.91× against popular GNN frameworks.

In recent years, large-scale models can be easily scaled to trillions of parameters with sparsely activated mixture-of-experts (MoE), which significantly improves the model quality while only requiring a sub-linear increase in computational costs. However, MoE layers require the input data to be dynamically routed to a particular GPU for computing during distributed training. The highly dynamic property of data routing and high communication costs in MoE make the training system low scaling efficiency on GPU clusters. In this work, we propose an extensible and efficient MoE training system, ScheMoE, which is equipped with several features. 1) ScheMoE provides a generic scheduling framework that allows the communication and computation tasks in training MoE models to be scheduled in an optimal way. 2) ScheMoE integrates our proposed novel all-to-all collective which better utilizes intra- and inter-connect bandwidths. 3) ScheMoE supports easy extensions of customized all-to-all collectives and data compression approaches while enjoying our scheduling algorithm. Extensive experiments are conducted on a 32-GPU cluster and the results show that ScheMoE outperforms existing state-of-the-art MoE systems, Tutel and Faster-MoE, by 9%-30%.

The Artificial Intelligence-Generated Content (AIGC) technique has gained significant popularity in creating diverse content. However, the current deployment of AIGC services in a centralized framework leads to high response times. To address this issue, we propose the integration of collaborative Mobile Edge Computing (MEC) technology to decrease the processing delay of AIGC services. Nevertheless, existing collaborative MEC methods only facilitate collaborative processing among fixed Edge Servers (ESs), limiting flexibility and resource utilization across heterogeneous ESs for different computing and networking requirements associated with AIGC tasks. This poses challenges for efficient resource allocation. We present an adaptive multi-server collaborative MEC approach tailored for heterogeneous edge environments to achieve efficient AIGC by dynamically allocating task workload across multiple ESs. We formulate our problem as an online linear programming problem aiming to minimize task offloading make-span. This problem is proved to be NP-hard and we propose an online adaptive multi-server selection and allocation algorithm based on deep reinforcement learning that effectively addresses this problem. Additionally, we provide theoretical performance analysis, demonstrating that our algorithm achieves near-optimal solutions within approximate linear time complexity bounds. Finally, experimental results validate the effectiveness of our method by showcasing at least 11.04% reduction in task offloading make-span and a 44.86 % decrease in failure rate compared to state-of-the-art methods.

Federated Learning (FL) models often experience client drift caused by heterogeneous data, where the distribution of data differs across clients. To address this issue, advanced research primarily focuses on manipulating the existing gradients to achieve more consistent client models. In this paper, we present an alternative perspective on client drift and aim to mitigate it by generating improved local models. First, we analyze the generalization contribution of local training and conclude that this generalization contribution is bounded by the conditional Wasserstein distance between the data distribution of different clients. Then, we propose FedImpro, to construct similar conditional distributions for local training. Specifically, FedImpro decouples the model into high-level and low-level components, and trains the high-level portion on reconstructed feature distributions. This approach enhances the generalization contribution and reduces the dissimilarity of gradients in FL. Experimental results show that FedImpro can help FL defend against data heterogeneity and enhance the generalization performance of the model.

Despite the remarkable capabilities, Large Language Models (LLMs) face deployment challenges due to their extensive size. Pruning methods drop a subset of weights to accelerate, but many of them require retraining, which is prohibitively expensive and computationally demanding. Recently, post-training pruning approaches introduced novel metrics, enabling the pruning of LLMs without retraining. However, these metrics require the involvement of human experts and tedious trial and error. To efficiently identify superior pruning metrics, we develop an automatic framework for searching symbolic pruning metrics using genetic programming. In particular, we devise an elaborate search space encompassing the existing pruning metrics to discover the potential symbolic pruning metric. We propose an opposing operation simplification strategy to increase the diversity of the population. In this way, Pruner-Zero allows auto-generation of symbolic pruning metrics. Based on the searched results, we explore the correlation between pruning metrics and performance after pruning and summarize some principles. Extensive experiments on LLaMA and LLaMA-2 on language modeling and zero-shot tasks demonstrate that our Pruner-Zero obtains superior performance than SOTA post-training pruning methods. Code at: https://github.com/pprp/Pruner-Zero.

Current data compression methods, such as sparsification in Federated Averaging (FedAvg), effectively enhance the communication efficiency of Federated Learning (FL). However, these methods encounter challenges such as the straggler problem and diminished model performance due to heterogeneous bandwidth and non-IID (Independently and Identically Distributed) data. To address these issues, we introduce a bandwidth-aware compression framework for FL, aimed at improving communication efficiency while mitigating the problems associated with non-IID data. First, our strategy dynamically adjusts compression ratios according to bandwidth, enabling clients to upload their models at a close pace, thus exploiting the otherwise wasted time to transmit more data. Second, we identify the non-overlapped pattern of retained parameters after compression, which results in diminished client update signals due to uniformly averaged weights. Based on this finding, we propose a parameter mask to adjust the client-averaging coefficients at the parameter level, thereby more closely approximating the original updates, and improving the training convergence under heterogeneous environments. Our evaluations reveal that our method significantly boosts model accuracy, with a maximum improvement of 13% over the uncompressed FedAvg. Moreover, it achieves a 3.37 × speedup in reaching the target accuracy compared to FedAvg with a Top-K compressor, demonstrating its effectiveness in accelerating convergence with compression. The integration of common compression techniques into our framework further establishes its potential as a versatile foundation for future cross-device, communication-efficient FL research, addressing critical challenges in FL and advancing the field of distributed machine learning.

Sparsely-activated Mixture-of-Expert (MoE) layers have found practical applications in enlarging the model size of large-scale foundation models, with only a sub-linear increase in computation demands. Despite the wide adoption of hybrid parallel paradigms like model parallelism, expert parallelism, and expert-sharding parallelism (i.e., MP+EP+ESP) to support MoE model training on GPU clusters, the training efficiency is hindered by communication costs introduced by these parallel paradigms. To address this limitation, we propose Parm, a system that accelerates MP+EP+ESP training by designing two dedicated schedules for placing communication tasks. The proposed schedules eliminate redundant computations and communications and enable overlaps between intra-node and inter-node communications, ultimately reducing the overall training time. As the two schedules are not mutually exclusive, we provide comprehensive theoretical analyses and derive an automatic and accurate solution to determine which schedule should be applied in different scenarios. Experimental results on an 8-GPU server and a 32-GPU cluster demonstrate that Parm outperforms the state-of-the-art MoE training system, DeepSpeed-MoE, achieving 1.13× to 5.77× speedup on 1296 manually configured MoE layers and approximately 3× improvement on two real-world MoE models based on BERT and GPT-2.

Transformer-based models have unlocked a plethora of powerful intelligent applications at the edge, such as voice assistant in smart home. Traditional deployment approaches offload the inference workloads to the remote cloud server, which would induce substantial pressure on the backbone network as well as raise users’ privacy concerns. To address that, in-situ inference has been recently recognized for edge intelligence, but it still confronts significant challenges stemming from the conflict between intensive workloads and limited on-device computing resources. In this paper, we leverage our observation that many edge environments usually comprise a rich set of accompanying trusted edge devices with idle resources and propose Galaxy, a collaborative edge AI system that breaks the resource walls across heterogeneous edge devices for efficient Transformer inference acceleration. Galaxy introduces a novel hybrid model parallelism to orchestrate collaborative inference, along with a heterogeneity-aware parallelism planning for fully exploiting the resource potential. Furthermore, Galaxy devises a tile-based fine-grained overlapping of communication and computation to mitigate the impact of tensor synchronizations on inference latency under bandwidth-constrained edge environments. Extensive evaluation based on prototype implementation demonstrates that Galaxy remarkably outperforms state-of-the-art approaches under various edge environment setups, achieving up to 2.5× end-to-end latency reduction.

Graphics processing units (GPUs) are continually evolving to cater to the computational demands of contemporary general-purpose workloads, particularly those driven by artificial intelligence (AI) utilizing deep learning techniques. A substantial body of studies have been dedicated to dissecting the microarchitectural metrics characterizing diverse GPU generations, which helps researchers understand the hardware details and leverage them to optimize the GPU programs. However, the latest Hopper GPUs present a set of novel attributes, including new tensor cores supporting FP8, DPX, and distributed shared memory. Their details still remain mysterious in terms of performance and operational characteristics. In this research, we propose an extensive benchmarking study focused on the Hopper GPU. The objective is to unveil its microarchitectural intricacies through an examination of the new instruction-set architecture (ISA) of Nvidia GPUs and the utilization of new CUDA APIs. Our approach involves two main aspects. Firstly, we conduct conventional latency and throughput comparison benchmarks across the three most recent GPU architectures, namely Hopper, Ada, and Ampere. Secondly, we delve into a comprehensive discussion and benchmarking of the latest Hopper features, encompassing the Hopper DPX dynamic programming (DP) instruction set, distributed shared memory, and the availability of FP8 tensor cores. The microbenchmarking results we present offer a deeper understanding of the novel GPU AI function units and programming features introduced by the Hopper architecture. This newfound understanding is expected to greatly facilitate software optimization and modeling efforts for GPU architectures. To the best of our knowledge, this study makes the first attempt to demystify the tensor core performance and programming instruction sets unique to Hopper GPUs.

3D multimodal question answering (MQA) plays a crucial role in scene understanding by enabling intelligent agents to comprehend their surroundings in 3D environments. While existing research has primarily focused on indoor household tasks and outdoor roadside autonomous driving tasks, there has been limited exploration of city-level scene understanding tasks. Furthermore, existing research faces challenges in understanding city scenes, due to the absence of spatial semantic information and human-environment interaction information at the city level.To address these challenges, we investigate 3D MQA from both dataset and method perspectives. From the dataset perspective, we introduce a novel 3D MQA dataset named City-3DQA for city-level scene understanding, which is the first dataset to incorporate scene semantic and human-environment interactive tasks within the city. From the method perspective, we propose a Scene graph enhanced City-level Understanding method (Sg-CityU), which utilizes the scene graph to introduce the spatial semantic. A new benchmark is reported and our proposed Sg-CityU achieves accuracy of 63.94 % and 63.76 % in different settings of City-3DQA. Compared to indoor 3D MQA methods and zero-shot using advanced large language models (LLMs), Sg-CityU demonstrates state-of-the-art (SOTA) performance in robustness and generalization.

On-device Deep Neural Network (DNN) training has been recognized as crucial for privacy-preserving machine learning at the edge. However, the intensive training workload and limited onboard computing resources pose significant challenges to the availability and efficiency of model training. While existing works address these challenges through native resource management optimization, we instead leverage our observation that edge environments usually comprise a rich set of accompanying trusted edge devices with idle resources beyond a single terminal. We propose Asteroid, a distributed edge training system that breaks the resource walls across heterogeneous edge devices for efficient model training acceleration. Asteroid adopts a hybrid pipeline parallelism to orchestrate distributed training, along with a judicious parallelism planning for maximizing throughput under certain resource constraints. Furthermore, a fault-tolerant yet lightweight pipeline replay mechanism is developed to tame the device-level dynamics for training robustness and performance stability. We implement Asteroid on heterogeneous edge devices with both vision and language models, demonstrating up to 12.2× faster training than conventional parallelism methods and 2.1× faster than state-of-the-art hybrid parallelism methods through evaluations. Furthermore, Asteroid can recover training pipeline 14× faster than baseline methods while preserving comparable throughput despite unexpected device exiting and failure.

In this paper, we present DSA, the first automated framework for discovering sparsity allocation schemes for layer-wise pruning in Large Language Models (LLMs). LLMs have become increasingly powerful, but their large parameter counts make them computationally expensive. Existing pruning methods for compressing LLMs primarily focus on evaluating redundancies and removing element-wise weights. However, these methods fail to allocate adaptive layer-wise sparsities, leading to performance degradation in challenging tasks. We observe that per-layer importance statistics can serve as allocation indications, but their effectiveness depends on the allocation function between layers. To address this issue, we develop an expression discovery framework to explore potential allocation strategies. Our allocation functions involve two steps: reducing element-wise metrics to per-layer importance scores, and modelling layer importance to sparsity ratios. To search for the most effective allocation function, we construct a search space consisting of pre-process, reduction, transform, and post-process operations. We leverage an evolutionary algorithm to perform crossover and mutation on superior candidates within the population, guided by performance evaluation. Finally, we seamlessly integrate our discovered functions into various uniform methods, resulting in significant performance improvements. We conduct extensive experiments on multiple challenging tasks such as arithmetic, knowledge reasoning, and multimodal benchmarks spanning GSM8K, MMLU, SQA, and VQA, demonstrating that our DSA method achieves significant performance gains on the LLaMA-1|2|3, Mistral, and OPT models. Notably, the LLaMA-1|2|3 model pruned by our DSA reaches 4.73\%|6.18\%|10.65\% gain over the state-of-the-art techniques (e.g., Wanda and SparseGPT).

Model editing has become an increasingly popular alternative for efficiently updating knowledge within language models. Current methods mainly focus on reliability, generalization, and locality, with many methods excelling across these criteria. Some recent works disclose the pitfalls of these editing methods such as knowledge distortion or conflict. However, the general abilities of post-edited language models remain unexplored. In this paper, we perform a comprehensive evaluation on various editing methods and different language models, and have following findings. (1) Existing editing methods lead to inevitable performance deterioration on general benchmarks, indicating that existing editing methods maintain the general abilities of the model within only a few dozen edits. When the number of edits is slightly large, the intrinsic knowledge structure of the model is disrupted or even completely damaged. (2) Instruction-tuned models are more robust to editing, showing less performance drop on general knowledge after editing. (3) Language model with large scale is more resistant to editing compared to small model. (4) The safety of the edited model, is significantly weakened, even for those safety-aligned models. Our findings indicate that current editing methods are only suitable for small-scale knowledge updates within language models, which motivates further research on more practical and reliable editing methods.

One-shot Federated Learning (OFL) significantly reduces communication costs in FL by aggregating trained models only once. However, the performance of advanced OFL methods is far behind the normal FL. In this work, we provide a causal view to find that this performance drop of OFL methods comes from the isolation problem, which means that local isolatedly trained models in OFL may easily fit to spurious correlations due to the data heterogeneity. From the causal perspective, we observe that the spurious fitting can be alleviated by augmenting intermediate features from other clients. Built upon our observation, we propose a novel learning approach to endow OFL with superb performance and low communication and storage costs, termed as FuseFL. Specifically, FuseFL decomposes neural networks into several blocks, and progressively trains and fuses each block following a bottom-up manner for feature augmentation, introducing no additional communication costs. Comprehensive experiments demonstrate that FuseFL outperforms existing OFL and ensemble FL by a significant margin. We conduct comprehensive experiments to show that FuseFL supports high scalability of clients, heterogeneous model training, and low memory costs. Our work is the first attempt using causality to analyze and alleviate data heterogeneity of OFL.

Connected-dominating-set (CDS) is a representative technique for constructing virtual backbones of wireless networks and thus facilitates implementation of many tasks including broadcasting, routing, etc. Most of existing works on CDS aim at constructing the minimum CDS (MCDS), so as to reduce the communication overhead over the CDS. However, MCDS may not work well in cognitive radio networks (CRNs) where communication links are prone to failure due to stochastic activities of primary users (PUs). A MCDS without consideration of the stochastic activities of PUs easily becomes invalid when the PUs become active. This study addresses a new CDS construction problem by considering the PUs’ activities. Our problem is to maximize the lifetime of the CDS while minimizing the size of the CDS, where the lifetime of a CDS is defined as the expected duration that the CDS is maintained valid. We show that the problem is NP-hard and propose a three-phase centralized algorithm. Given a CRN, the centralized algorithm can compute a CDS such that the lifetime of the CDS is maximized (optimal), and the size of the CDS is upper-bounded. We further present a two-phase localized algorithm which requires 2-hop information. Extensive simulations are conducted to evaluate the proposed algorithms.

The Industrial Internet of Things (IIoT) has found extensive applications in intelligent transportation. However, as the number of vehicles increases, the issue of traffic congestion becomes more prominent, emphasizing the need for accurate congestion propagation prediction to enhance traffic conditions. Current methods for predicting congestion propagation lack consideration for the influence of communication networks and do not incorporate the path characteristics of congestion propagation. Therefore, we propose a path-based congestion propagation model, UAU_SIS_Path, employing multigrain abstraction of traffic congestion and information propagation. Specifically, UAU_SIS_Path effectively captures the propagation dynamics of congestion in IIoT by leveraging the interaction of two-layer networks and the path propagation characteristics of traffic congestion. Subsequently, we validate the effectiveness of the UAU_SIS_Path model through theoretical analysis, establishing tight upper and lower bounds of the propagation threshold and elucidating the relationship between the propagation of congestion information in the information network and the diffusion of congestion in the road network. Finally, based on theoretical analysis, we examine the impact of our model on congestion control strategies, utilizing path replanning, and traffic restriction as congestion control strategies. Experimental results in simulated road network BA and real road networks of varying sizes (GC, TA, and As) demonstrate the stability and scalability of our model. In comparison to the traditional contact-based propagation model, our model achieves a reduction in congestion propagation rates of 58.2%, 66.9%, 32.6%, and 48.6%, respectively.

One-shot neural architecture search (NAS) substantially improves the search efficiency by training one supernet to estimate the performance of every possible child architecture (i.e., subnet). However, the inconsistency of characteristics among subnets incurs serious interference in the optimization, resulting in poor performance ranking correlation of subnets. Subsequent explorations decompose supernet weights via a particular criterion, e.g., gradient matching, to reduce the interference; yet they suffer from huge computational cost and low space separability. In this work, we propose a lightweight and effective local intrinsic dimension (LID)-based method NAS-LID. NAS-LID evaluates the geometrical properties of architectures by calculating the low-cost LID features layer-by-layer, and the similarity characterized by LID enjoys better separability compared with gradients, which thus effectively reduces the interference among subnets. Extensive experiments on NASBench-201 indicate that NAS-LID achieves superior performance with better efficiency. Specifically, compared to the gradient-driven method, NAS-LID can save up to 86% of GPU memory overhead when searching on NASBench-201. We also demonstrate the effectiveness of NAS-LID on ProxylessNAS and OFA spaces. Source code:https://github.com/marsggbo/NAS-LID.

Existing learning-based multi-view stereo (MVS) methods rely on the depth range to build the 3D cost volume and may fail when the range is too large or unreliable. To address this problem, we propose a disparity-based MVS method based on the epipolar disparity flow (E-flow), called DispMVS, which infers the depth information from the pixel movement between two views. The core of DispMVS is to construct a 2D cost volume on the image plane along the epipolar line between each pair (between the reference image and several source images) for pixel matching and fuse uncountable depths triangulated from each pair by multi-view geometry to ensure multi-view consistency. To be robust, DispMVS starts from a randomly initialized depth map and iteratively refines the depth map with the help of the coarse-to-fine strategy. Experiments on DTUMVS and Tanks\&Temple datasets show that DispMVS is not sensitive to the depth range and achieves state-of-the-art results with lower GPU memory.

Communication scheduling has been shown to be effective in accelerating distributed training, which enables all-reduce communications to be overlapped with backpropagation computations. This has been commonly adopted in popular distributed deep learning frameworks. However, there exist two fundamental problems: (1) excessive startup latency proportional to the number of workers for each all-reduce operation; (2) it only achieves sub-optimal training performance due to the dependency and synchronization requirement of the feed-forward computation in the next iteration. We propose a novel scheduling algorithm, DeAR, that decouples the all-reduce primitive into two continuous operations, which overlaps with both backpropagation and feed-forward computations without extra communications. We further design a practical tensor fusion algorithm to improve the training performance. Experimental results with five popular models show that DeAR achieves up to 83% and 15% training speedup over the state-of-the-art solutions on a 64-GPU cluster with 10Gb/s Ethernet and 100Gb/s InfiniBand interconnects, respectively.

To accelerate distributed training, many gradient compression methods have been proposed to alleviate the communication bottleneck in synchronous stochastic gradient descent (S-SGD), but their efficacy in real-world applications still remains unclear. In this work, we first evaluate the efficiency of three representative compression methods (quantization with Sign-SGD, sparsification with Top-k SGD, and low-rank with Power-SGD) on a 32-GPU cluster. The results show that they cannot always outperform well-optimized S-SGD or even worse due to their incompatibility with three key system optimization techniques (all-reduce, pipelining, and tensor fusion) in S-SGD. To this end, we propose a novel gradient compression method, called alternate compressed Power-SGD (ACP-SGD), which alternately compresses and communicates low-rank matrices. ACP-SGD not only significantly reduces the communication volume, but also enjoys the three system optimizations like S-SGD. Compared with Power-SGD, the optimized ACP-SGD can largely reduce the compression and communication overheads, while achieving similar model accuracy. In our experiments, ACP-SGD achieves an average of 4.06× and 1.43× speedups over S-SGD and Power-SGD, respectively, and it consistently outperforms other baselines across different setups (from 8 GPUs to 64 GPUs and from 1Gb/s Ethernet to 100Gb/s InfiniBand).

Large models have attracted much attention in the AI area. The sparsely activated mixture-of-experts (MoE) technique pushes the model size to a trillion-level with a sub-linear increase of computations as an MoE layer can be equipped with many separate experts, but only one or two experts need to be trained for each input data. However, the feature of dynamically activating experts of MoE introduces extensive communications in distributed training. In this work, we propose PipeMoE to adaptively pipeline the communications and computations in MoE to maximally hide the communication time. Specifically, we first identify the root reason why a higher pipeline degree does not always achieve better performance in training MoE models. Then we formulate an optimization problem that aims to minimize the training iteration time. To solve this problem, we build performance models for computation and communication tasks in MoE and develop an optimal solution to determine the pipeline degree such that the iteration time is minimal. We conduct extensive experiments with 174 typical MoE layers and two real-world NLP models on a 64-GPU cluster. Experimental results show that our PipeMoE almost always chooses the best pipeline degree and outperforms state-of-the-art MoE training systems by 5%-77% in training time.

Graph Neural Networks (GNNs) are gaining huge traction recently as they achieve state-of-the-art performance on various graph-related problems. GNN training typically follows the standard Message Passing Paradigm, in which SpMM and SDDMM are the two essential sparse kernels. However, existing sparse GPU kernels are inefficient and may suffer from load imbalance, dynamics in GNN computing, poor memory efficiency, and tail effect. We propose two new kernels, Hybrid-Parallel SpMM (HP-SpMM) and Hybrid-Parallel SDDMM (HP-SDDMM), that efficiently perform SpMM and SDDMM on GPUs with a unified hybrid parallel strategy of mixing nodes and edges. In view of the emerging graph-sampling training, we design the Dynamic Task Partition (DTP) method to minimize the tail effect by exposing sufficient parallelism. We further devise the Hierarchical Vectorized Memory Access scheme to achieve aligned global memory accesses and enable vectorized instructions for improved memory efficiency. We also propose to enhance data locality by reordering the graphs with the Graph Clustering method. Experiments on extensive sparse matrices collected from real GNN applications demonstrate that our kernels achieve significant performance improvements over state-of-the-art implementations. We implement our sparse kernels in popular GNN frameworks and use them to train various GNN models, including the GCN model in full-graph mode and the GraphSAINT model in graph-sampling mode. Evaluation results show that our kernels can accelerate GNN training by up to 1.72×.

To meet the growing need of mobile traffic with Ultra-Reliable and Low Latency Communication (URLLC) requirement, 5G New Radio (NR) is extending from licensed band to unlicensed band on which Wi-Fi has already been operated, resulting in coexisting NR/Wi-Fi network. Existing works have made great efforts on throughput and latency of coexisting NR/Wi-Fi network. However, excessive NR requests offloaded from licensed band lead to unfair utilization of unlicensed band, which further causes unsatisfaction on URLLC and performance degradation of Wi-Fi. In this paper, we propose a novel Reinforcement Learning based Transmission Revoking Approach (RL-TRA) to address this problem aiming at fairer utilization of unlicensed band restrained by URLLC. Firstly, we formulate the coexistence problem of NR/Wi-Fi as integer non-linear programming and show its NP-hardness. Secondly, we decompose the problem into three sub-problems, namely redundancy determining, request scheduling, and transmission revoking. The former two sub-problems are solved with our proposed method to satisfy URLLC requirement. We further propose a novel transmission revoking mechanism when tackling transmission revoking sub-problem, aiming at maintaining fairness of coexisting NR/Wi-Fi network. Finally, simulation results verify the effectiveness of RL-TRA. By using our method, the fairness is improved by 16.5% averagely with only 1.77% loss on success rate of URLLC requests compared with baselines.

Due to the popularity of Graph Neural Networks (GNNs), various GNN-based methods have been designed to reason on knowledge graphs (KGs). An important design component of GNN-based KG reasoning methods is called the propagation path, which contains a set of involved entities in each propagation step. Existing methods use hand-designed propagation paths, ignoring the correlation between the entities and the query relation. In addition, the number of involved entities will explosively grow at larger propagation steps. In this work, we are motivated to learn an adaptive propagation path in order to filter out irrelevant entities while preserving promising targets. First, we design an incremental sampling mechanism where the nearby targets and layer-wise connections can be preserved with linear complexity. Second, we design a learning-based sampling distribution to identify the semantically related entities. Extensive experiments show that our method is powerful, efficient and semantic-aware. The code is available at https://github.com/LARS-research/AdaProp.

Industrial Internet of Things (IIoT) technology is widely used in modern industrial fields like transportation, but data security remains a major challenge. The blockchain-based access control mechanism can address the data security issue by preventing unauthorized devices from accessing limited IIoT resources. However, most existing blockchain-based access control mechanism for IIoT still has scalability and privacy issues. To deal with the above-mentioned problems, we propose a new scalable and secure strategy for the blockchain-based access control framework for IIoT via sharding, which consists of two components. First, the network sharding scheme based on the access frequency set (N2SAF) is designed to 1) improve the scalability of our proposed strategy by transaction sharding to reduce the storage pressure on nodes, and 2) increase the transaction processing speed on a three-layer architecture based on cloud-edge-device in IIoT. Second, the privacy protection scheme based on a Bloom filter (P2BF) is designed to deal with the privacy leakage problem caused by anonymous address clustering. Simulation results show that our proposed strategy improves the scalability of the system compared to existing methods while ensuring the security of the shard network, especially in large-scale IIoT environments.

IEEE 802.11ax is the standard for the new generation WiFi networks. In this paper, we formulate the problem of joint access point (AP) placement and power-channel-resource unit assignment for 802.11ax-based dense WiFi. The objective is to minimize the number of APs. Two quality-of-service (QoS) requirements are to be fulfilled: (1) a two-tier throughput requirement which ensures that the throughput of each station is good enough, and (2) a fault tolerance requirement which ensures that the stations could still use WiFi even when some APs fail. We prove that this problem is NP-hard. To tackle this problem, we first develop an analytic model to derive the throughput of each station under the OFDMA mechanism and a widely used interference model. We then design a heuristic algorithm to find high-quality solutions with polynomial time complexity. Simulation results under both fixed-user and mobile-user cases show that: (1) when the area is small (50 × 50$\rm m^2$), our algorithm gives the optimal solutions; when the area is larger (80 × 60$\rm m^2$), our algorithm can reduce the number of APs by 34.9-87.7% as compared to the Random and Greedy algorithms. (2) Our algorithm can always get feasible solutions that fulfill the QoS requirements.

Recently, federated learning (FL) techniques have enabled multiple users to train machine learning models collaboratively without data sharing. However, existing FL algorithms suffer from the communication bottleneck due to network bandwidth pressure and/or low bandwidth utilization of the participating clients in both centralized and decentralized architectures. To deal with the communication problem while preserving the convergence performance, we introduce a communication-efficient decentralized FL framework GossipFL. In GossipFL, we 1) design a novel sparsification algorithm to enable that each client only needs to communicate with one peer with a highly sparsified model, and 2) propose a new and novel gossip matrix generation algorithm that can better utilize the bandwidth resources while preserving the convergence property. We also theoretically prove that GossipFL has convergence guarantees. We conduct experiments with three convolutional neural networks on two datasets (IID and non-IID) under two distributed environments (14 clients and 100 clients) to verify the effectiveness of GossipFL. Experimental results show that GossipFL takes less communication traffic for 38.5% and less communication time for$49.8$% than state-of-the-art solutions while achieving comparative model accuracy.

The panorama image can simultaneously demonstrate complete information of the surrounding environment and has many advantages in virtual tourism, games, robotics, etc. However, the progress of panorama depth estimation cannot completely solve the problems of distortion and discontinuity caused by the commonly used projection methods. This paper proposes SphereDepth, a novel panorama depth estimation method that predicts the depth directly on the spherical mesh without projection preprocessing. The core idea is to establish the relationship between the panorama image and the spherical mesh and then use a deep neural network to extract features on the spherical domain to predict depth. To address the efficiency challenges brought by the high-resolution panorama data, we introduce two hyper-parameters for the proposed spherical mesh processing framework to balance the inference speed and accuracy. Validated on three public panorama datasets, SphereDepth achieves comparable results with the state-of-the-art methods of panorama depth estimation. Benefiting from the spherical domain setting, SphereDepth can generate a high-quality point cloud and significantly alleviate the issues of distortion and discontinuity.

In federated learning (FL), model performance typically suffers from client drift induced by data heterogeneity, and mainstream works focus on correcting client drift. We propose a different approach named virtual homogeneity learning (VHL) to directly “rectify” the data heterogeneity. In particular, VHL conducts FL with a virtual homogeneous dataset crafted to satisfy two conditions: containing no private information and being separable. The virtual dataset can be generated from pure noise shared across clients, aiming to calibrate the features from the heterogeneous clients. Theoretically, we prove that VHL can achieve provable generalization performance on the natural distribution. Empirically, we demonstrate that VHL endows FL with drastically improved convergence speed and generalization performance. VHL is the first attempt towards using a virtual dataset to address data heterogeneity, offering new and effective means to FL.

In cognitive radio networks, rendezvous is a fundamental operation by which cognitive users establish communication links. Most of existing works were devoted to shortening the time-to-rendezvous (TTR) but paid little attention to qualities of the channels on which rendezvous is achieved. In fact, qualities of channels, such as resistance to primary users' activities, have a great effect on the rendezvous operation. If users achieve a rendezvous on a low-quality channel, the communication link is unstable and the communication performance is poor. In this case, re- rendezvous is required which results in considerable communication overhead and a large latency. In this paper, we first show that actual TTRs of existing rendezvous solutions increase by 65.40-104.38% if qualities of channels are not perfect. Then we propose a Quality-Aware Rendezvous Framework (QARF) that can be applied to any existing ren-dezvous algorithms to achieve rendezvous on high-quality channels. The basic idea of QARF is to expand the set of available channels by selectively duplicating high-quality channels. We prove that QARF can reduce the expected TTR of any rendezvous algorithm when the expanded ratio$\lambda$is smaller than the threshold$(-3+\sqrt{1+4(\frac{\sigma}{\mu})^{2}}) / 2$, where$\mu$and$\sigma$, respectively, are the mean and the standard deviation of qualities of channels. We further prove that QARF can always reduce the expected TTR of Random algorithm by a factor of$1+(\frac{\sigma}{\mu})^{2}$. Extensive experiments are conducted and the results show that QARF can significantly reduce the TTRs of the existing rendezvous algorithms by 10.50-51.05 % when qualities of channels are taken into account.

We present GASS, an LLVM-based open-source compiler for NVIDIA GPU's SASS machine assembly. GASS is the first open-source compiler targeting SASS, and it provides a unified toolchain for currently fragmented low-level performance research on NVIDIA GPUs. GASS supports all recent architectures, including Volta, Turing, and Ampere.

Energy conservation of large data centers for high performance computing workloads, such as deep learning with Big Data, is of critical significance, where cutting down a few percent of electricity translates into million-dollar savings. This work studies energy conservation on emerging CPU-GPU hybrid clusters through dynamic voltage and frequency scaling (DVFS). We aim at minimizing the total energy consumption of processing a batch of offline tasks or a sequence of real-time tasks under deadline constraints. We derive a fast and accurate analytical model to compute the appropriate voltage/frequency setting for each task, and assign multiple tasks to the cluster with heuristic scheduling algorithms. In particular, our model stresses the nonlinear relationship between task execution time and processor speed for GPU-accelerated applications, for more accurately capturing real-world GPU energy consumption. In performance evaluation driven by real-world power measurement traces, our scheduling algorithm shows comparable energy savings to the theoretical upper bound. With a GPU scaling interval where analytically at most 36% of energy can be saved, we record 33-35% of energy savings. Our results are applicable to energy management on modern heterogeneous clusters.

The COVID-19 pandemic has spread globally for several months. Because its transmissibility and high pathogenicity seriously threaten people's lives, it is crucial to accurately and quickly detect COVID-19 infection. Many recent studies have shown that deep learning (DL) based solutions can help detect COVID-19 based on chest CT scans. However, most existing work focuses on 2D datasets, which may result in low quality models as the real CT scans are 3D images. Besides, the reported results span a broad spectrum on different datasets with a relatively unfair comparison. In this paper, we first use three state-of-the-art 3D models (ResNet3D101, DenseNet3D121, and MC3\_18) to establish the baseline performance on three publicly available chest CT scan datasets. Then we propose a differentiable neural architecture search (DNAS) framework to automatically search the 3D DL models for 3D chest CT scans classification and use the Gumbel Softmax technique to improve the search efficiency. We further exploit the Class Activation Mapping (CAM) technique on our models to provide the interpretability of the results. The experimental results show that our searched models (CovidNet3D) outperform the baseline human-designed models on three datasets with tens of times smaller model size and higher accuracy. Furthermore, the results also verify that CAM can be well applied in CovidNet3D for COVID-19 datasets to provide interpretability for medical diagnosis. Code: https://github.com/HKBU-HPML/CovidNet3D.

Existing state-of-the-art disparity estimation works mostly leverage the 4D concatenation volume and construct a very deep 3D convolution neural network (CNN) for disparity regression, which is inefficient due to the high memory consumption and slow inference speed. In this paper, we propose a network named EDNet for efficient disparity estimation. Firstly, we construct a combined volume which incorporates contextual information from the squeezed concatenation volume and feature similarity measurement from the correlation volume. The combined volume can be next aggregated by 2D convolutions which are faster and require less memory than 3D convolutions. Secondly, we propose an attention-based spatial residual module to generate attention-aware residual features. The attention mechanism is applied to provide intuitive spatial evidence about inaccurate regions with the help of error maps at multiple scales and thus improve the residual learning efficiency. Extensive experiments on the Scene Flow and KITTI datasets show that EDNet outperforms the previous 3D CNN based works and achieves state-of-the-art performance with significantly faster speed and less memory consumption.

It has become a common practice to train large machine learning (ML) models across a cluster of computing nodes connected by RDMA-enabled networks. However, the communication overhead caused by parameter synchronization deteriorates the performance of such distributed ML (DML), especially in a large-scale setting. This paper tackles this issue by developing a traffic management scheme to support DML traffic, called TMDML (Traffic Management for DML), which needs only a minor modification to the existing RDMA congestion control scheme DCQCN. We assume that there is only one instance of DML workload running in a network. Existing literature has shown that Fat-Tree, a predominant topology in the data center, poorly supports DML compared with BCube. With our proposed TMDML, training DML in Fat-Tree can achieve better performance than that in BCube. We first study the impact of multi-bottlenecks on DML via NS-3-based simulations. The results show that DCQCN is inefficient for DML traffic in the multi-bottlenecks scenario. To mitigate the impact of multi-bottlenecks, we propose an optimization model to minimize the maximum flow completion time (FCT) while stabilizing the queues, and then apply the Lyapunov optimization technique to solve the problem. For all the practical purposes, we present two heuristic implementations of TMDML for different deployment requirements. We evaluate the performance of our proposals by simulation, comparing it with DCQCN. We use All-Reduce parameter synchronization in Fat-Tree and BCube with traffic trace of modern deep neural network models, including AlexNet, ResNet50, and VGG-16. Our proposals can achieve up to 59% of the time reduction.

Indoor robotics applications heavily rely on scene understanding and reconstruction. Compared to monocular vision, stereo vision methods are more promising to produce accurate geometrical information, such as surface normal and depth/disparity. Besides, deep learning models have shown their superior performance in stereo vision tasks. However, existing stereo datasets rarely contain high-quality surface normal and disparity ground truth, hardly satisfying the demand of training a prospective deep model. To this end, we introduce a large-scale indoor robotics stereo (IRS) dataset with over 100K stereo images and high-quality surface normal and disparity maps. Leveraging the advanced techniques of our customized rendering engine, the dataset is considerably close to the real-world scenes. Besides, we present DTN-Net, a two-stage deep model for surface normal estimation. Extensive experiments show the advantages and effectiveness of IRS in training deep models for disparity estimation, and DTN-Net provides state-of-the-art results for normal estimation compared to existing methods.

Synchronous stochastic gradient descent (S-SGD) with data parallelism is widely used for training deep learning (DL) models in distributed systems. A pipelined schedule of the computing and communication tasks of a DL training job is an effective scheme to hide some communication costs. In such pipelined S-SGD, tensor fusion (i.e., merging some consecutive layers' gradients for a single communication) is a key ingredient to improve communication efficiency. However, existing tensor fusion techniques schedule the communication tasks sequentially, which overlooks their independence nature. In this paper, we expand the design space of scheduling by exploiting simultaneous All-Reduce communications. Through theoretical analysis and experiments, we show that simultaneous All-Reduce communications can effectively improve the communication efficiency of small tensors. We formulate an optimization problem of minimizing the training iteration time, in which both tensor fusion and simultaneous communications are allowed. We develop an efficient optimal scheduling solution and implement the distributed training algorithm ASC-WFBP with Horovod and PyTorch. We conduct real-world experiments on an 8-node GPU cluster of 32 GPUs with 10Gbps Ethernet. Experimental results on four modern DNNs show that ASC-WFBP can achieve about 1.09 × -2.48× speedup over the baseline without tensor fusion, and 1.15× -1.35× speedup over the state-of-the-art tensor fusion solution.

Many low-level optimizations for NVIDIA GPU can only be implemented in native hardware assembly (SASS). However, programming in SASS is unproductive and not portable.

The eruption of a pandemic, such as COVID-19, can cause an unprecedented global crisis. Contact tracing, as a pillar of communicable disease control in public health for decades, has shown its effectiveness on pandemic control. Despite intensive research on contact tracing, existing schemes are vulnerable to attacks and can hardly simultaneously meet the requirements of data integrity and user privacy. The design of a privacy-preserving contact tracing framework to ensure the integrity of the tracing procedure has not been sufficiently studied and remains a challenge. In this paper, we propose P2B-Trace, a privacy-preserving contact tracing initiative based on blockchain. First, we design a decentralized architecture with blockchain to record an authenticated data structure of the user's contact records, which prevents the user from intentionally modifying his local records afterward. Second, we develop a zero-knowledge proximity verification scheme to further verify the user's proximity claim while protecting user privacy. We implement P2B-Trace and conduct experiments to evaluate the cost of privacy-preserving tracing integrity verification. The evaluation results demonstrate the effectiveness of our proposed system.

Distributed synchronous stochastic gradient descent has been widely used to train deep neural networks (DNNs) on computer clusters. With the increase of computational power, network communications generally limit the system scalability. Wait-free backpropagation (WFBP) is a popular solution to overlap communications with computations during the training process. In this article, we observe that many DNNs have a large number of layers with only a small amount of data to be communicated at each layer in distributed training, which could make WFBP inefficient. Based on the fact that merging some short communication tasks into a single one can reduce the overall communication time, we formulate an optimization problem to minimize the training time in pipelining communications and computations. We derive an optimal solution that can be solved efficiently without affecting the training performance. We then apply the solution to propose a distributed training algorithm named merged-gradient WFBP (MG-WFBP) and implement it in two platforms Caffe and PyTorch. Extensive experiments in three GPU clusters are conducted to verify the effectiveness of MG-WFBP. We further exploit trace-based simulations of 4 to 2048 GPUs to explore the potential scaling efficiency of MG-WFBP. Experimental results show that MG-WFBP achieves much better scaling performance than existing methods.

Deep learning has become widely used in complex AI applications. Yet, training a deep neural network (DNNs) model requires a considerable amount of calculations, long running time, and much energy. Nowadays, many-core AI accelerators (e.g., GPUs and TPUs) are designed to improve the performance of AI training. However, processors from different vendors perform dissimilarly in terms of performance and energy consumption. To investigate the differences among several popular off-the-shelf processors (i.e., Intel CPU, NVIDIA GPU, AMD GPU, and Google TPU) in training DNNs, we carry out a comprehensive empirical study on the performance and energy efficiency of these processors1by benchmarking a representative set of deep learning workloads, including computation-intensive operations, classical convolutional neural networks (CNNs), recurrent neural networks (LSTM), Deep Speech 2, and Transformer. Different from the existing end-to-end benchmarks which only present the training time, We try to investigate the impact of hardware, vendor's software library, and deep learning framework on the performance and energy consumption of AI training. Our evaluation methods and results not only provide an informative guide for end users to select proper AI accelerators, but also expose some opportunities for the hardware vendors to improve their software library.

To reduce the long training time of large deep neural network (DNN) models, distributed synchronous stochastic gradient descent (S-SGD) is commonly used on a cluster of workers. However, the speedup brought by multiple workers is limited by the communication overhead. Two approaches, namely pipelining and gradient sparsification, have been separately proposed to alleviate the impact of communication overheads. Yet, the gradient sparsification methods can only initiate the communication after the backpropagation, and hence miss the pipelining opportunity. In this paper, we propose a new distributed optimization method named LAGS-SGD, which combines S-SGD with a novel layer-wise adaptive gradient sparsification (LAGS) scheme. In LAGS-SGD, every worker selects a small set of 'significant' gradients from each layer independently whose size can be adaptive to the communication-to-computation ratio of that layer. The layer-wise nature of LAGS-SGD opens the opportunity of overlapping communications with computations, while the adaptive nature of LAGS-SGD makes it flexible to control the communication time. We prove that LAGS-SGD has convergence guarantees and it has the same order of convergence rate as vanilla S-SGD under a weak analytical assumption. Extensive experiments are conducted to verify the analytical assumption and the convergence performance of LAGS-SGD. Experimental results on a 16-GPU cluster show that LAGS-SGD outperforms the original S-SGD and existing sparsified S-SGD without losing obvious model accuracy.

Fingerprint is one of the representative methods for wireless indoor localization. It uses a fingerprint database (measured in the offline phase) and the current received signal strengths (RSSs) (measured by the user's device in the online phase) to determine the location of this device. However, the RSSs and hence the localization accuracy would be affected by time-varying environmental factors (e.g., number of people in a shopping mall). In this paper, we propose a new method for wireless localization in time-varying indoor environments. In the offline phase, the proposed method measures extra information: it measures E fingerprint databases for E respective environmental conditions, where E is a design parameter (e.g., E=2 for the peak period and the non-peak period in a shopping mall). In the online phase, it leverages the extra information for better localization in time-varying indoor environment, even when the current environmental condition is different from the ones considered in the offline phase. The proposed method is particularly suitable for the indoor venues for which their primary concern is to provide good quality localization services while they could afford a moderate amount of extra resources for one-off measurement in the offline phase (e.g., exhibition centers, airports, shopping malls, etc.). We conduct a simulation experiment and a real-world experiment to demonstrate that the proposed method gives accurate localization.

Blockchain is essentially a distributed ledger shared by all nodes in the system. All nodes in blockchain are equal, and each node holds all transactions and blocks in the network. As the network continues to expand, the data rises linearly. Participates are about to face the problem of storage limitation. Blockchain is hard to scale.This paper introduces ICIStrategy, a multi-node collaborative storage strategy based on intra-cluster integrity. In ICIStrategy, we divide all participates into several clusters. Each cluster requires holding all data of the network, whereas a node within the cluster does not need to maintain data integrity. It aims to solve the storage pressure by reducing the amount data that each participate need to store and reduce communication overhead by collaboratively storing and verifying blocks through in-cluster nodes. Moreover, the ICIStrategy could greatly save the overhead of bootstrapping. We show the mode of operation in our strategy. We further analysis the performance of ICIStrategy and conduct simulation experiments. The results of several comparative experiments show that our strategy just needs 25% of storage space needed by Rapidchain, which indeed solve the problem of storage limitation and improve the blockchain performance.

The increasing size of machine learning models, especially deep neural network models, can improve the model generalization capability. However, large models require more training data and more computing resources (such as GPU clusters) to train. In distributed training, the communication overhead of exchanging gradients or models among workers becomes a potential system bottleneck that limits the system scalability. Recently, many research works aim to reduce communication time of two types of distributed deep learning architectures, centralized and decentralized.

Hyperledger Fabric is a popular open-source project for deploying permissioned blockchains. Many performance characteristics of the latest Hyperledger Fabric (e.g., performance characteristics of each phase, the impacts of ordering services, bottleneck and scalability) are still not well understood due to the performance complexity of distributed systems. We conducted a thorough performance evaluation on the first long term support release of Hyperledger Fabric. We studied the performance characteristics of each phase, including execute, order, and the validate phase, according to Hyperledger Fabric's new execute-order-validate architecture. We also studied the ordering services, including Solo, Kafka, and Raft. Our experimental results showed some findings as follows. 1) The execution phase exhibited a good scalability under the OR endorsement policy but not with the AND endorsement policy. 2) We were not able to find a significant performance difference between the three ordering services. 3) The validate phase was likely to be the system bottleneck due to the low validation speed of chaincode. Overall, our work helps to understand and improve Hyperledger Fabric.

Promising federated learning coupled with Mobile Edge Computing (MEC) is considered as one of the most promising solutions to the AI-driven service provision. Plenty of studies focus on federated learning from the performance and security aspects, but they neglect the incentive mechanism. In MEC, edge nodes would not like to voluntarily participate in learning, and they differ in the provision of multi-dimensional resources, both of which might deteriorate the performance of federated learning. Also, lightweight schemes appeal to edge nodes in MEC. These features require the incentive mechanism to be well designed for MEC. In this paper, we present an incentive mechanism FMore with multi-dimensional procurement auction of K winners. Our proposal FMore not only is lightweight and incentive compatible, but also encourages more high-quality edge nodes with low cost to participate in learning and eventually improve the performance of federated learning. We also present theoretical results of Nash equilibrium strategy to edge nodes and employ the expected utility theory to provide guidance to the aggregator. Both extensive simulations and real-world experiments demonstrate that the proposed scheme can effectively reduce the training rounds and drastically improve the model accuracy for challenging AI tasks.

Multiplication of a sparse matrix to a dense matrix (SpDM) is widely used in many areas like scientific computing and machine learning. However, existing work under-looks the performance optimization of SpDM on modern manycore architectures like GPUs. The storage data structures help sparse matrices store in a memory-saving format, but they bring difficulties in optimizing the performance of SpDM on modern GPUs due to irregular data access of the sparse structure, which results in lower resource utilization and poorer performance. In this paper, we refer to the roofline performance model of GPUs to design an efficient SpDM algorithm called GCOOSpDM, in which we exploit coalescent global memory access, fast shared memory reuse, and more operations per byte of global memory traffic. Experiments are evaluated on three Nvidia GPUs (i.e., GTX 980, GTX Titan X Pascal, and Tesla P100) using a large number of matrices including a public dataset and randomly generated matrices. Experimental results show that GCOOSpDM achieves 1.5-8x speedup over Nvidia's library cuSPARSE in many matrices.

Deep neural networks (DNNs) have achieved great success in the area of computer vision. The disparity estimation problem tends to be addressed by DNNs which achieve much better prediction accuracy in stereo matching than traditional hand-crafted feature based methods. On one hand, however, the designed DNNs require significant memory and computation resources to accurately predict the disparity, especially for those 3D convolution based networks, which makes it difficult for deployment in real-time applications. On the other hand, existing computation-efficient networks lack expression capability in large-scale datasets so that they cannot make an accurate prediction in many scenarios. To this end, we propose an efficient and accurate deep network for disparity estimation named FADNet with three main features: 1) It exploits efficient 2D based correlation layers with stacked blocks to preserve fast computation; 2) It combines the residual structures to make the deeper model easier to learn; 3) It contains multi-scale predictions so as to exploit a multi-scale weight scheduling training technique to improve the accuracy. We conduct experiments to demonstrate the effectiveness of FADNet on two popular datasets, Scene Flow and KITTI 2015. Experimental results show that FADNet achieves state-of-the-art prediction accuracy, and runs at a significant order of magnitude faster speed than existing 3D models. The codes of FADNet are available at https://github.com/HKBU-HPML/FADNet.

IEEE 802.11ax is a promising standard for the next-generation WiFi network, which uses orthogonal frequency division multiple access (OFDMA) to segregate the wireless spectrum into time-frequency resource units (RUs). In this paper, we aim at designing an 802.11ax-based dense WiFi network to provide WiFi services to a large number of users within a given area with the following objectives: (1) to minimize the number of access points (APs); (2) to fulfil the users' throughput requirement; and (3) to be resistant to AP failures. We formulate the above into a joint AP placement and power-channel-RU assignment optimization problem, which is NP-hard. To tackle this problem, we first derive an analytical model to estimate each user's throughput under the mechanism of OFDMA and a widely used interference model. We then design a heuristic algorithm to find high-quality solutions with polynomial time complexity. Simulation results show that our algorithm can achieve the optimal performance for a small area of 50×50 m2. For a larger area of 100×80 m2where we cannot find the optimal solution through an exhaustive search, our algorithm can reduce the number of APs by 32 ~ 55% as compared to the random and Greedy solutions.

Distributed synchronous stochastic gradient descent (SGD) algorithms are widely used in large-scale deep learning applications, while it is known that the communication bottleneck limits the scalability of the distributed system. Gradient sparsification is a promising technique to significantly reduce the communication traffic, while pipelining can further overlap the communications with computations. However, gradient sparsification introduces extra computation time, and pipelining requires many layer-wise communications which introduce significant communication startup overheads. Merging gradients from neighbor layers could reduce the startup overheads, but on the other hand it would increase the computation time of sparsification and the waiting time for the gradient computation. In this paper, we formulate the trade-off between communications and computations (including backward computation and gradient sparsification) as an optimization problem, and derive an optimal solution to the problem. We further develop the optimal merged gradient sparsification algorithm with SGD (OMGS-SGD) for distributed training of deep learning. We conduct extensive experiments to verify the convergence properties and scaling performance of OMGS-SGD. Experimental results show that OMGS-SGD achieves up to 31% end-to-end time efficiency improvement over the state-of-the-art sparsified SGD while preserving nearly consistent convergence performance with original SGD without sparsification on a 16-GPU cluster connected with 1Gbps Ethernet.

Half-precision matrix multiply has played a key role in the training of deep learning models. The newly designed Nvidia Tensor Cores offer the native instructions for half-precision small matrix multiply, based on which Half-precision General Matrix Multiply (HGEMM) routines are developed and can be accessed through high-level APIs. In this paper, we, for the first time, demystify how Tensor Cores on NVIDIA Turing architecture work in great details, including the instructions used, the registers and data layout required, as well as the throughput and latency of Tensor Core operations. We further benchmark the memory system of Turing GPUs and conduct quantitative analysis of the performance. Our analysis shows that the bandwidth of DRAM, L2 cache and shared memory is the new bottleneck for HGEMM, whose performance is previously believed to be bound by computation. Based on our newly discovered features of Tensor Cores, we apply a series of optimization techniques on the Tensor Core-based HGEMM, including blocking size optimization, data layout redesign, data prefetching, and instruction scheduling. Extensive evaluation results show that our optimized HGEMM routine achieves an average of 1.73× and 1.46× speedup over the native implementation of cuBLAS 10.1 on NVIDIA Turing RTX2070 and T4 GPUs, respectively. The code of our implementation is written in native hardware assembly (SASS).

In this paper, we present an optimized implementation for single-precision Winograd convolution on NVIDIA Volta and Turing GPUs. Compared with the state-of-the-art Winograd convolution in cuDNN 7.6.1, our implementation achieves up to 2.13X speedup on Volta V100 and up to 2.65X speedup on Turing RTX2070. On both Volta and Turing GPUs, our implementation achieves up to 93% of device peak.

Erasure codes have been used extensively in large-scale storage systems to reduce the storage overhead of triplication-based storage systems. One key performance issue introduced by erasure codes is the long time needed to recover from a single failure, which occurs constantly in large-scale storage systems. We present ESetStore, a prototype erasure-coded storage system that aims to achieve fast recovery from failures. ESetStore is novel in the following aspects. We proposed a data placement algorithm named ESet for our ESetStore that can aggregate adequate I/O resources from available storage servers to recover from each single failure. We designed and implemented efficient read and write operations on our erasure-coded storage system via effective use of available I/O and computation resources. We evaluated the performance of ESetStore with extensive experiments on a cluster with 50 storage servers. The evaluation results demonstrate that our recovery performance can obtain linear performance growth by harvesting available I/O resources. With our defined parameter recovery I/O parallelism under some mild conditions, we can achieve optimal recovery performance, in which ESet enables minimal recovery time. Rather than being an alternative to improve recovery performance, our work can be an enhancement for existing solutions, such as Partial-parallel-repair (PPR), to further improve recovery performance.

Contemporary graphics processing units (GPUs) support dynamic voltage and frequency scaling to balance computational performance and energy consumption. However, accurate and straightforward performance estimation for a given GPU kernel under different frequency settings is still lacking for real hardware, which is essential to determine the best frequency configuration for energy saving. In this article, we reveal a fine-grained analytical model to estimate the execution time of GPU kernels with both core and memory frequency scaling. Compared to the cycle-level simulators, which are too slow to apply on real hardware, our model only needs simple and one-off micro-benchmarks to extract a set of hardware parameters and kernel performance counters without any source code analysis. Our experimental results show that the proposed performance model can capture the kernel performance scaling behaviors under different frequency settings and achieve decent accuracy (average errors of 3.85, 8.6, 8.82, and 8.83 percent on a set of 20 GPU kernels with four modern Nvidia GPUs).

Skin disease is one of the most common types of human diseases, which may happen to everyone regardless of age, gender or race. Due to the high visual diversity, human diagnosis highly relies on personal experience; and there is a serious shortage of experienced dermatologists in many countries. To alleviate this problem, computer-aided diagnosis with state-of-the-art (SOTA) machine learning techniques would be a promising solution. In this paper, we aim at understanding the performance of convolutional neural network (CNN) based approaches. We first build two versions of skin disease datasets from Internet images: (a) Skin -10, which contains 10 common classes of skin disease with a total of 10,218 images; (b) Skin -100, which is a larger dataset that consists of 19,807 images of 100 skin disease classes. Based on these datasets, we benchmark several SOTA CNN models and show that the accuracy of skin -100 is much lower than the accuracy of skin -10. We then implement an ensemble method based on several CNN models and achieve the best accuracy of 79.01% for Skin -10 and 53.54% for Skin -100. We also present an object detection based approach by introducing bounding boxes into the Skin -10 dataset. Our results show that object detection can help improve the accuracy of some skin disease classes.

Distributed synchronous stochastic gradient descent (S-SGD) with data parallelism has been widely used in training large-scale deep neural networks (DNNs), but it typically requires very high communication bandwidth between computational workers (e.g., GPUs) to exchange gradients iteratively. Recently, Top-k sparsification techniques have been proposed to reduce the volume of data to be exchanged among workers and thus alleviate the network pressure. Top-k sparsification can zero-out a significant portion of gradients without impacting the model convergence. However, the sparse gradients should be transferred with their indices, and the irregular indices make the sparse gradients aggregation difficult. Current methods that use AllGather to accumulate the sparse gradients have a communication complexity of O(kP), where P is the number of workers, which is inefficient on low bandwidth networks with a large number of workers. We observe that not all top-k gradients from P workers are needed for the model update, and therefore we propose a novel global Top-k (gTop-k) sparsification mechanism to address the difficulty of aggregating sparse gradients. Specifically, we choose global top-k largest absolute values of gradients from P workers, instead of accumulating all local top-k gradients to update the model in each iteration. The gradient aggregation method based on gTop-k sparsification, namely gTopKAllReduce, reduces the communication complexity from O(kP) to O(k log P). Through extensive experiments on different DNNs, we verify that gTop-k S-SGD has nearly consistent convergence performance with S-SGD, and it has only slight degradations on generalization performance. In terms of scaling efficiency, we evaluate gTop-k on a cluster with 32 GPU machines which are interconnected with 1 Gbps Ethernet. The experimental results show that our method achieves 2.7-12× higher scaling efficiency than S-SGD with dense gradients and 1.1-1.7× improvement than the existing Top-k S-SGD.

Gradient sparsification is a promising technique to significantly reduce the communication overhead in decentralized synchronous stochastic gradient descent (S-SGD) algorithms. Yet, many existing gradient sparsification schemes (e.g., Top-k sparsification) have a communication complexity of O(kP), where k is the number of selected gradients by each worker and P is the number of workers. Recently, the gTop-k sparsification scheme has been proposed to reduce the communication complexity from O(kP) to O(k logP), which significantly boosts the system scalability. However, it remains unclear whether the gTop-k sparsification scheme can converge in theory. In this paper, we first provide theoretical proofs on the convergence of the gTop-k scheme for non-convex objective functions under certain analytic assumptions. We then derive the convergence rate of gTop-k S-SGD, which is at the same order as the vanilla mini-batch SGD. Finally, we conduct extensive experiments on different machine learning models and data sets to verify the soundness of the assumptions and theoretical results, and discuss the impact of the compression ratio on the convergence performance.

Distributed synchronous stochastic gradient descent has been widely used to train deep neural networks on computer clusters. With the increase of computational power, network communications have become one limiting factor on the system scalability. In this paper, we observe that many deep neural networks have a large number of layers with only a small amount of data to be communicated. Based on the fact that merging some short communication tasks into a single one may reduce the overall communication time, we formulate an optimization problem to minimize the training iteration time. We develop an optimal solution named merged-gradient wait-free backpropagation (MG-WFBP) and implement it in our open-source deep learning platform B-Caffe. Our experimental results on an 8-node GPU cluster with 10GbE interconnect and trace-based simulation results on a 64-node cluster both show that the MG-WFBP algorithm can achieve much better scaling efficiency than existing methods WFBP and SyncEASGD.

Calibrators and sniffers have been used in the literature to proactively update the functional relationship between the received signal strength and the distance for wireless localization in time-varying indoor venue, where calibrators and sniffers are Wi-Fi transmitters and Wi-Fi receivers respectively. To be effective, these devices should be suitably placed in the indoor venue. Let there be N calibrators and M sniffers, di,jbe the distance between calibrator i and sniffer j, and RSSi,jbe the received signal strength measured by sniffer j from calibrator i. The points (d1,1, RSS1,1), (d1,2, RSS1,2), ..., (dN,M, RSSN,M) are used to estimate the functional relationship between the received signal strength and the distance. It is desirable that d1,1, d1,2, ..., dN,Mare uniformly scattered so that the estimated functional relationship is more accurate for better localization. In this paper, we propose to minimize the discrepancy of d1,1, d1,2, ..., dN,Min order to determine the optimal locations of the N calibrators and the M sniffers. We formulate this new problem (named minimal discrepancy placement problem) and design an efficient optimization method to solve it. We conduct simulation and real-world experiments to demonstrate that minimal discrepancy placement can effectively improve localization accuracy.

With huge amounts of training data, deep learning has made great breakthroughs in many artificial intelligence (AI) applications. However, such large-scale data sets present computational challenges, requiring training to be distributed on a cluster equipped with accelerators like GPUs. With the fast increase of G PU computing power, the data communications among GPUs have become a potential bottleneck on the overall training performance. In this paper, we first propose a general directed acyclic graph (DAG) model to describe the distributed synchronous stochastic gradient descent (S-SG D) algorithm, which has been widely used in distributed deep learning frameworks. To understand the practical impact of data communications on training performance, we conduct extensive empirical studies on four state-of-the-art distributed deep learning frameworks (i.e., Caffe-MPI, CNTK, MXNet and TensorFlow) over multi-GPU and multi-node environments with different data communication techniques, including PCIe, NVLink, 10GbE, and InfiniBand. Through both analytical and experimental studies, we identify the potential bottlenecks and overheads that could be further optimized. At last, we make the data set of our experimental traces publicly available, which could be used to support simulation-based studies.

Graphics processing units (GPUs) support dynamic voltage and frequency scaling to balance computational performance and energy consumption. However, simple and accurate performance estimation for a given GPU kernel under different frequency settings is still lacking for real hardware, which is important to decide the best frequency configuration for energy saving. We reveal a fine-grained analytical model to estimate the execution time of GPU kernels with both core and memory frequency scaling. Over a 2 x range of both core and memory frequencies among 20 GPU kernels, our model achieves accurate results (4.83 % error on average) with real hardware. Compared to the cycle-level simulators, our model only needs simple micro-benchmarks to extract a set of hardware parameters and kernel performance counters to produce such high accuracy without kernel source analysis.

Many indoor localization systems rely on a set of reference anchors with known positions. A target's location is estimated from a set of distances between the target and its surrounding anchors, and hence the selection of anchors affects the localization accuracy. However, it remains a challenge to select the best set of anchors. In this paper, we study how to appropriately make use of the surrounding anchors for localizing a target. We first construct different candidate anchor clusters by selecting different number of anchors with the strongest received signals. Then for each candidate cluster, we propose a weighted min-max algorithm to provide a location estimation. Finally, we introduce a weighted geometric dilution of precision (w-GDOP) algorithm that combines the estimations from multiple clusters by quantifying their estimation accuracy. We evaluate the performance of our solution through simulations and real-world experiments. Our results show that the proposed anchor selection scheme and localization algorithm significantly improve the localization accuracy in large indoor environments.

In cognitive radio networks, rendezvous is a fundamental operation by which cognitive users establish a communication link on a commonly-available channel for communications. Most of existing rendezvous algorithms provide guaranteed rendezvous (i.e., rendezvous can be achieved within finite time) by generating channel-hopping (CH) sequences based on the whole channel set. These algorithms are inefficient when available channels account for a small proportion of the whole channel set. Some recent algorithms generate CH sequences based on the available channel set. However, these algorithms normally require additional information such as unique IDs and predefined roles of cognitive users. In this study, we design a new algorithm called ZOS based on the set of available channels without any additional requirements. ZOS uses three types of elementary sequences (namely, Zero-type, One-type, and S-type) to generate CH sequences and provides guaranteed rendezvous. The maximum time-to-rendezvous of ZOS is upper-bounded by O(m1×m2×log2M) where M is the number of all channels and m1 and m2 are the numbers of available channels of two users. Simulation results show superior performance of ZOS.

In cognitive radio networks, rendezvous is a fundamental operation by which cognitive users establish communication links. Most of existing works consider rendezvous of a pair of users. When multiple pairs of users are doing rendezvous, collisions are caused by the multiple user-pairs which significantly degrade the rendezvous performance, e.g., resulting in a long time-to-rendezvous. To address this problem, we propose a new protocol called Cooperative Rendezvous Protocol which exploits cooperation in the multiple user-pairs environment to speed up the rendezvous operation. Using this protocol, multiple user-pairs cooperate with each other to relay their channel availability information, so that they could avoid attempting rendezvous in unavailable channels. The proposed protocol serves as a general framework that can be applied in conjunction with any existing rendezvous algorithm for faster rendezvous. We theoretically derive an upper bound on the time-to-rendezvous when the proposed protocol is applied in conjunction with any rendezvous algorithm which generates channel hopping sequence based on the available channel set. In addition, we conduct extensive simulation and the results show that the proposed protocol can significantly reduce the time-to-rendezvous of the existing rendezvous algorithms by up to 80.86% in multiple user-pairs environment.

Collective motion is a fundamental operation of robot swarms by which a group of robots move from a source to a destination in a cohesive way (i.e., connectivity is preserved during these movements). However, the collective motion of robot swarms along preplanned paths has not been well studied. In this paper, we propose self-adaptive collective motion algorithms for swarm robots in 3-D space. Using the proposed collective motion algorithms, robots are able to move along a preplanned path from a source to a destination while satisfying the following requirements: 1) the robots use only one-hop neighbor information; 2) the robots maintain connectivity of the network topology for information exchange; 3) the robots maintain a desired neighboring distance; and 4) the robots are capable of bypassing obstacles without partitioning the robot swarm (i.e., member loss). Our basic idea is to introduce a guidance force and a topology force into the system. The guidance force is used to guide the robots to their destination along the preplanned path. It ensures that the robots continue to move until they reach their destination. The topology force is used to maintain a “good” topology of the robot swarm, such as maintaining connectivity of the network topology and the desired distance between neighboring robots. The resultant of the guidance and topology forces determines the movement of a robot. We develop collective motion algorithms for three cases: 1) no obstacles or leaders; 2) no obstacles with a leader; and 3) with obstacles (with and without a leader). Extensive simulations are conducted to evaluate performance of the proposed algorithms. The simulation results show that: 1) our algorithms meet all the requirements; 2) our algorithms are resistant to GPS errors and robot failures; and 3) self-adaptive control of our algorithms makes network topologies more stable and significantly saves travel time of swarm robots. Note to Practitioners-We propose self-adaptive collective motion algorithms that enable swarm robots to move along a preplanned path from a source to a destination in 3-D space. Our algorithms use only one-hop neighbor information and operate without central controllers. The algorithms are designed to be self-adaptive in the sense that robots are able to dynamically determine proper moving parameters, based on their environments and statuses. With the proposed algorithms, swarm robots are able to: 1) maintain connectivity and a desired neighboring distance during movement; 2) bypass obstacles without member loss (i.e., the robot swarm is partitioned); and 3) be resistant to GPS errors and robot failures. We address both cases of with a leader and without a leader. Simulation results show effectiveness of our algorithms which can be applied in applications of surveillance, search and rescue, mining, agricultural foraging, autonomous military units, and distributed sensing in micromachinery or human bodies.

Recently, erasure coding has been extensively deployed in large-scale storage systems to replace data replication. With the increase in disk I/O throughput and network bandwidth, the performance of erasure coding becomes a major bottleneck of erasure-coded storage systems. In this paper, we propose a graphics processing unit (GPU)-based implementation of erasure coding named G-CRS, which employs the Cauchy Reed-Solomon (CRS) code, to overcome the aforementioned bottleneck. To maximize the coding performance of G-CRS, we designed and implemented a set of optimization strategies, such as a compact structure to store thebitmatrixin GPU constant memory, efficient data access through shared memory, and decoding parallelism, to fully utilize the GPU resources. In addition, we derived a simple yet accurate performance model to demonstrate the maximum coding performance of G-CRS on GPU. We evaluated the performance of G-CRS through extensive experiments on modern GPU architectures such as Maxwell and Pascal, and compared with other state-of-the-art coding libraries. The evaluation results revealed that the throughput of G-CRS was 10 times faster than most of the other coding libraries. Moreover, G-CRS outperformed PErasure (a recently developed, well optimized CRS coding library on the GPU) by up to 3 times in the same architecture.

Cloud federation paradigm can improve cloud service providers' (CSPs) profits by renting their idle resource to other federation members. However, these CSPs have the risk that they cannot fulfill their scalability commitment when some of their customers have large short-term resource demand. To reduce this risk, we design a reinsurance-emulated collaboration mechanism in a broker-based cloud federation. Reinsurance is an insurance policy which transfers all or part of insurance business in order to scatter the risk to other insurers. Similar to insurance companies, in our proposed model, each CSP determines its resource retention for its future demand. We design an exact method to determine each CSP's retention, with the aim of maximizing its expected profit. Once the CSP's retention cannot meet its future demand, it reduces the risk by outsourcing part of the requests to others. After every CSP determines its retention, the broker will make an assignment to maximize the resource utilization so as to reduce the risk of the CSPs. We designed an algorithm to maximize the resource utilization, with a guarantee of not worse than half of the optimal solution. Simulation results show that our proposed algorithm is efficient.

Many recent deep learning platforms rely on thirdparty libraries (such as cuBLAS) to utilize the computing power of modern hardware accelerators (such as GPUs). However, we observe that they may achieve suboptimal performance because the library functions are not used appropriately. In this paper, we target at optimizing the operations of multiplying a matrix with the transpose of another matrix (referred to as NT operation hereafter), which contribute half of the training time of fully connected deep neural networks. Rather than directly calling the library function, we propose a supervised learning based algorithm selection approach named MTNN, which uses a gradient boosted decision tree to select one from two alternative NT implementations intelligently: (1) calling the cuBLAS library function; (2) calling our proposed algorithm TNN that uses an efficient out-of-place matrix transpose. We evaluate the performance of MTNN on two modern GPUs: NVIDIA GTX 1080 and NVIDIA Titan X Pascal. MTNN can achieve 96% of prediction accuracy with very low computational overhead, which results in an average of 54% performance improvement on a range of NT operations. To further evaluate the impact of MTNN on the training process of deep neural networks, we have integrated MTNN into a popular deep learning platform Caffe. Our experimental results show that the revised Caffe can outperform the original one by an average of 28%. Both MTNN and the revised Caffe are open-source.

Conserving the energy consumption of large data centers is of critical significance, where a few percent in consumption reduction translates into millions-dollar savings. This work studies energy conservation on emerging CPU-GPU hybrid clusters through dynamic voltage and frequency scaling (DVFS). We aim at minimizing the total energy consumption of processing a sequence of real-time tasks under deadline constraints. We compute the appropriate voltage/frequency setting for each task through mathematical optimization, and assign multiple tasks to the cluster with heuristic scheduling algorithms. In performance evaluation driven by real-world power measurement traces, our scheduling algorithm shows comparable energy savings to the theoretical upper bound. With a GPU scaling interval where analytically at most 38% of energy can be saved, we record 30-36% of energy savings. Our results are applicable to energy management on modern heterogeneous clusters. In particular, our model stresses the nonlinear relationship between task execution time and processor speed for GPU-accelerated applications, for more accurately capturing real-world GPU energy consumption.

Compared to general vehicular systems, bus systems have advantages including wide coverage, fixed routes, and regular service. Inspired by these unique features of the bus systems, we propose to use the bus systems as routing backbones of VANETs. In this work, we present a Community-based Bus System (CBS) which consists of two components: a community-based backbone and a routing scheme over the backbone. The backbone construction is a one-off operation which is done offline while the routing is done online in individual buses. We build a community-based backbone by applying community detection techniques and propose a twolevel routing scheme which operates over the backbone. The proposed routing scheme performs sequentially in the inter-community level and the intra-community level, and is able to support message delivery to both buses and specific locations/areas. We develop a probabilistic model to analyze the message delivery latency of CBS. The average error of the analytically-derived latency is shown to be 8.9 percent of the latency derived from the real traces. Extensive experiments are conducted on real-world traces from the Beijing bus system and the Dublin bus system and the results show that CBS can significantly lower the delivery latency and improve the delivery ratio, compared to the existing solutions. CBS is a general solution which is applicable to any bus-based VANETs.

Memory access efficiency is a key factor in fully utilizing the computational power of graphics processing units (GPUs). However, many details of the GPU memory hierarchy are not released by GPU vendors. In this paper, we propose a novel fine-grained microbenchmarking approach and apply it to three generations of NVIDIA GPUs, namely Fermi, Kepler, and Maxwell, to expose the previously unknown characteristics of their memory hierarchies. Specifically, we investigate the structures of different GPU cache systems, such as the data cache, the texture cache and the translation look-aside buffer (TLB). We also investigate the throughput and access latency of GPU global memory and shared memory. Our microbenchmark results offer a better understanding of the mysterious GPU memory hierarchy, which will facilitate the software optimization and modelling of GPU architectures. To the best of our knowledge, this is the first study to reveal the cache properties of Kepler and Maxwell GPUs, and the superiority of Maxwell in shared memory performance under bank conflict.

Virtual machine (VM) consolidation and switch/path consolidation are two typical techniques for improving energy efficiency in data centers (DCs). Most of existing work separately optimize VM consolidation and switch consolidation which results in inferiority of the optimization performance. Moreover, these work usually handle a user application as a VM flow (i.e., a source VM is connected to a destination VM). In practice, however, relation of VMs could be much more complex than the single flow and multiple VMs are connected via a network. In this work, we address a general DC energy optimization problem that enables tenants to express their applications by a general resource request graph (i.e., computation requests of VMs, bandwidth requests of VM communications, and time requests of VM execution). We propose a joint VM-switch consolidation (JVSC for short) algorithm to this problem. JVSC jointly optimizes the energy consumption of DCs in three steps: (i) it decreases the number of active PMs by VM consolidation; (ii) it decreases the number of active switches by switch consolidation at the tor tier, the aggregation tier and the core tier of the network, respectively; and (iii) it minimizes energy consumption of VM migration via an energy-aware migration strategy. Extensive experiments are conducted on both simulated applications and real Google cluster usage traces. Experimental results demonstrate that JVSC can save 60% around energy of DCs, compared to the state-of-the-art.

Mobile crowdsensing (MCS) is a promising paradigm that utilizes the mobility of people and the sensing capabilities of their mobile devices to accomplish a variety of sensing tasks. In this paper, we adopt the Signaling System No.7 (SS7) as the MCS platform since SS7 can well capture trajectories and mobility patterns of the mobile users. We collect a real-world SS7 data of 1.18 million mobile users at 3512 cell towers/sites in Xiamen, China. We first analyze this dataset and reveal important characteristics of user mobility. Then, we address a Mobile User Recruitment (MUR) problem which is crucial to all MCS systems. Given SS7 data of mobile users, a set of target cells to be sensed/covered, and recruitment cost functions of the mobile users, the MUR problem is to recruit a set of mobile users such that all the target cells are covered and the total recruitment cost is minimized. Our MUR problem is general and includes the existing problems as its special cases. We prove NP-hardness of the problem. We propose an approximation algorithm to this problem and derive the approximation ratio. Extensive experiments are conducted on the real-world SS7 dataset and results show that the proposed solution outperforms two baseline algorithms by saving 22.6% and 62.9% recruitment costs, respectively, on average.

In today's mobile devices, the battery reservoir remains severely limited in capacity, making power consumption a key concern in the design and implementation of mobile applications. In this paper, we closely examine one widely adopted approach to improve the energy efficiency of mobile applications-adaptively offloading the computation to the remote cloud. In particular, we measure the power consumption of computation offloading for two representative real-world mobile cloud applications under various wireless network conditions and identify the unique features of data transmission for computation offloading. We then formulate the power-aware scheduling problem for computation offloading and present a scheduling algorithm that makes adaptive offloading decisions according to the dynamic network conditions. Simulation results show that our proposed method can achieve better battery performance, which also reveal that computation-intensive and delay-tolerant tasks are more likely to benefit from offloading.

Technology of autonomous vehicles (AVs) is becoming mature, and many AVs will appear on roads in the near future. AVs become connected with the support of various vehicular communication technologies, and they possess a high degree of control to respond to instantaneous situations cooperatively with high efficiency and flexibility. In this paper, we propose a new public transportation system based on AVs. It manages a fleet of AVs to accommodate transportation requests, offering point-to-point services with ride sharing. We focus on the two major problems of the system: scheduling and admission control. The former is to configure the most economical schedules and routes for the AVs to satisfy the admissible requests, whereas the latter is to determine the set of admissible requests among all requests to produce maximum profit. The scheduling problem is formulated as a mixed-integer linear program, and the admission control problem is cast as a bilevel optimization, which embeds the scheduling problem as the major constraint. By utilizing the analytical properties of the problem, we develop an effective genetic-algorithm-based method to tackle the admission control problem. We validate the performance of the algorithm with real-world transportation service data.

The emerging cloud computing technologies enable a cloud platform to provide diverse cloud services to its service subscribers. By federating different services within and across cloud boundaries, cloud service developers can provision new, composite cloud services in the marketplace of apps and services on a cloud platform. Complete and accurate service QoS information is important for service recommendation and service pricing. However, measuring the entire QoS matrix for all user-service pairs incurs a tremendous overhead and is practically infeasible. This work designs efficient algorithms for recovering the complete QoS matrix from partial measurements, exploiting the low rank feature of the matrix. Our solution applies tools from differential geometry for transforming rank-constrained matrix optimization in a flat space into an unconstrained geometric optimization in a smooth manifold. Besides QoS matrix completion, future QoS matrix prediction based on manifold algorithms is also studied in this work, for the first time in the literature.

Rendezvous is a fundamental operation for cognitive users to establish communication links so as to realize data communications and network management. Most of existing rendezvous algorithms implicitly assume that each cognitive user is equipped with one radio, i.e., one wireless transceiver. As the cost of wireless transceivers is dropping, it becomes economically feasible to utilize multiple radios to significantly improve the rendezvous performance. In this paper, we propose an Adjustable Multi-Radio Rendezvous (AMRR) algorithm which exploits multiple radios for fast rendezvous based on available channels only. Suppose that a cognitive user is equipped with m radios. Our basic idea is to partition the radios into two groups: k stay radios and (m - k) hopping radios. The user stays on specific channels in the stay radios while hops on its available channels parallelly in the hopping radios. We prove that the maximum time-to-rendezvous (MTTR) of AMRR is upper-bounded by O(|C1||C2|/m1m2), where |C1| and |C2| are the numbers of available channels of two users and m1and m2are the numbers of radios of the two users. This bound meets the lower bound of MTTR of any deterministic rendezvous algorithm when two users are equipped with the same number of radios (i.e., m1= m2). AMRR is adjustable in giving its best performance on either MTTR or E(TTR) by adjusting value of k. Simulation results show that AMRR performs better than the state-of-the-art.

Abstract—In recent years, erasure coding has been adopted by large-scale cloud storage systems to replace data replication. With the increase of disk I/O throughput and network bandwidth, the speed of erasure coding becomes one of the key system bot-tlenecks. In this paper, we propose to offload the task of erasure coding to Graphics Processing Units (GPUs). Specifically, we have designed and implemented PErasure, a parallel Cauchy Reed-Solomon (CRS) coding library. We compare the performance of PErasure with that of two state-of-the-art libraries: Jerasure (for CPUs) and Gibraltar (for GPUs). Our experiments show that the raw coding speed of PErasure on a $500 Nvidia GTX780 card is about 10 times faster than that of multithreaded Jerasure on a quad-core modern CPU, and 2-4 times faster than Gibraltar on the same GPU. PErasure can achieve up to 10GB/s of overall encoding speed using just a single GPU for a large storage system that can withstand up to 8 disk failures. I.

Low delivery latency and high delivery ratio are two key goals in the design of routing schemes in Vehicular Ad Hoc Networks (VANETs). The existing routing schemes utilize real-time information (e.g., Geographical position and vehicle density) and historical information (e.g., Contacts of vehicles), which usually suffer from a long delivery latency and a low delivery ratio. Inspired by the unique features of bus systems such as wide coverage, fixed routes and regular service, we propose to use the bus systems as routing backbones of VANETs. In this work, we present a Community-based Bus System (CBS) which consists of two components: a community-based backbone and a routing scheme over the backbone. We collect real traces of 2515 buses in Beijing and build a community-based backbone by applying community detection techniques in the Beijing bus system. A two-level routing scheme is proposed to operate over the backbone. The proposed routing scheme performs sequentially in the inter-community level and the intra-community level, and is able to support message delivery to both mobile vehicles and specific locations/areas. Extensive experiments are conducted on the real trace data of the Beijing bus system and the results show that CBS can significantly lower the delivery latency and improve the delivery ratio. CBS is applicable to any bus-based VANETs.

Latest developments in cloud computing technologies have enabled a plethora of cloud based data storage services. Cloud storage service providers are facing significant bandwidth cost as the user population scales. Such bandwidth cost can be substantially slashed by exploring a hybrid cloud storage architecture that takes advantage of under-utilized storage and network resources at storage clients. A critical component in the new hybrid cloud storage architecture is an economic mechanism that incentivizes clients to contribute their local resources, while at the same time minimizes the provider's cost for pooling those resources. This work studies online procurement auction mechanisms towards these goals. The online nature of the auction is in line with asynchronous user request arrivals in practice. After carefully characterizing truthfulness conditions under the online procurement auction paradigm, we prove that truthfulness can be guaranteed by a price-based allocation rule and payment rule. Our truthfulness characterization actually converts the mechanism design problem into an online algorithm design problem, with a marginal pricing function for resources as variables set by cloud storage service providers for online procurement auction. We derive the marginal pricing function for the online algorithm. We also prove the competitive ratio of the social cost of our algorithm against that of the offline VCG mechanism and of the resource pooling cost of our algorithm against that of the offline optimal auction. Simulation studies driven by real-world traces are conducted to show the efficacy of our online auction mechanism.

The increasing complexity of computer systems and communication networks induces tremendous requirements for trust and security. This special issue includes topics on trusted computing, risk and reputation management, network security and survivable computer systems/networks. These issues have evolved into an active and important area of research and development. The past decade has witnessed a proliferation of concurrency and computation systems for practice of highly trust, security and privacy, which has become a key subject in determining future research and development activities in many academic and industrial branches. This special issue aims to present and discuss advances of current research and development in all aspects of trusted computing and network security. In addition, this special issue provides snapshots of contemporary academia work in the field of network trusted computing. We prepared and organized this special issue to record state-of-the-art research, novel development and trends for future insight in this domain. In this special issue, 14 papers have been accepted for publication, which demonstrate novel and original work in this field. A detailed overview of the selected works is given below.

Rendezvous is a fundamental operation in cognitive radio networks (CRNs) for establishing a communication link on a commonly-available channel between cognitive users. The existing work on rendezvous implicitly assumes that each cognitive user is equipped with one radio (i.e., one wireless transceiver). As the cost of wireless transceivers is dropping, this feature can be exploited to significantly improve the rendezvous performance at low cost. In this study, we investigate the rendezvous problem in CRNs where cognitive users are equipped with multiple radios and different users may have different numbers of radios. We first study how the existing rendezvous algorithms can be generalized to use multiple radios for faster rendezvous. We then propose a new rendezvous algorithm, called role-based parallel sequence (RPS), which specifically exploits multiple radios for more efficient rendezvous. Our basic idea is to let the cognitive users stay in a specific channel in one dedicated radio and hop on the available channels with parallel sequences in the remaining general radios. We prove that our algorithm provides guaranteed rendezvous (i.e., rendezvous can be completed within a finite time) and derive the upper bounds on the maximum time-to-rendezvous (TTR) and the expected TTR. The simulation results show that i) multiple radios can cost-effectively improve the rendezvous performance, and ii) the proposed RPS algorithm performs better than the ones generalized from the existing algorithms.

In a cloud market, the cloud provider provisions heterogeneous virtual machine (VM) instances from its resource pool, for allocation to cloud users. Auction-based allocations are efficient in assigning VMs to users who value them the most. Existing auction design often overlooks the heterogeneity of VMs, and does not consider dynamic, demand-driven VM provisioning. Moreover, the classic VCG auction leads to unsatisfactory seller revenues and vulnerability to a strategic bidding behavior known as shill bidding. This work presents a new type of core-selecting VM auctions, which are combinatorial auctions that always select bidder charges from the core of the price vector space, with guaranteed economic efficiency under truthful bidding. These auctions represent a comprehensive three-phase mechanism that instructs the cloud provider to judiciously assemble, allocate, and price VM bundles. They are proof against shills, can improve seller revenue over existing auction mechanisms, and can be tailored to maximize truthfulness.

Server selection is an important problem of cloud computing in which cloud service providers direct user demands to servers in one of the multiple data centers located in different geographical locations. The existing solutions usually assume homogeneity of cloud services (i.e., all users request the same type of service) and handle user demands in an individual basis which incurs high computational overhead. In this study, we propose a new and effective server selection scheme in which diversities of cloud services are taken into account. We focus on a specific cloud service, i.e., online video service, and assume that different videos have different bandwidth requirements. We group users into clusters and handle user demands on a cluster basis for faster and more efficient process. Given user demands and bandwidth capacities of servers in the data centers, our problem is to assign the user demands to the servers under the bandwidth constraint, such that the overall latency (measured by the network distance) between the user clusters and the selected servers is minimized. We design a server selection system and formulate this problem as a linear programming formulation which can be solved by existing techniques. The system periodically executes our scheme and computes an optimal solution for server selection. User demands are assigned to the servers according to the optimal solution and the minimum overall latency can be achieved. The simulation results show that our scheme is significantly better than the random algorithm and the YouTube server selection strategy.

Rendezvous is a necessary operation for cognitive users to establish communication links in cognitive radio networks (CRNs). To guarantee the rendezvous in finite time, all existing rendezvous algorithms generate CH (channel-hopping) sequences using the whole channel set and attempt rendezvous on each of the channels (i.e., both available channels and unavailable channels). In practice, the available channel set is usually a small portion of the whole channel set due to dynamics of channel availabilities and limited sensing capabilities of cognitive users. Thus, the CH sequences using the whole channel set may attempt unnecessary rendezvous in uncertain channels (e.g., unavailable channels or randomly-selected channels) which greatly degrades the performance. In this study, we propose a new rendezvous algorithm that generates channel-hopping sequences based on available channel set (CSAC) for more efficient rendezvous. We prove that CSAC gives guaranteed rendezvous and derive its upper-bound on maximum time-to-rendezvous (MTTR) which is an expression of the number of available channels instead of the number of all potential channels. To the best of our knowledge, CSAC is the first one in the literature that exploits the only available channels in designing CH sequences while providing guaranteed rendezvous. Experimental results show that CSAC can significantly improve the MTTR compared to state-of-the-art.

MOTIVATION: Since 1990, the basic local alignment search tool (BLAST) has become one of the most popular and fundamental bioinformatics tools for sequence similarity searching, receiving extensive attention from the research community. The two pioneering papers on BLAST have received over 96 000 citations. Given the huge population of BLAST users and the increasing size of sequence databases, an urgent topic of study is how to improve the speed. Recently, graphics processing units (GPUs) have been widely used as low-cost, high-performance computing platforms. The existing GPU-BLAST is a promising software tool that uses a GPU to accelerate protein sequence alignment. Unfortunately, there is still no GPU-accelerated software tool for BLAST-based nucleotide sequence alignment. RESULTS: We developed G-BLASTN, a GPU-accelerated nucleotide alignment tool based on the widely used NCBI-BLAST. G-BLASTN can produce exactly the same results as NCBI-BLAST, and it has very similar user commands. Compared with the sequential NCBI-BLAST, G-BLASTN can achieve an overall speedup of 14.80X under 'megablast' mode. More impressively, it achieves an overall speedup of 7.15X over the multithreaded NCBI-BLAST running on 4 CPU cores. When running under 'blastn' mode, the overall speedups are 4.32X (against 1-core) and 1.56X (against 4-core). G-BLASTN also supports a pipeline mode that further improves the overall performance by up to 44% when handling a batch of queries as a whole. Currently G-BLASTN is best optimized for databases with long sequences. We plan to optimize its performance on short database sequences in our future work. AVAILABILITY: http://www.comp.hkbu.edu.hk/∼chxw/software/G-BLASTN.html CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Tandem mass spectrometry-based database searching is currently the main method for protein identification in shotgun proteomics. The explosive growth of protein and peptide databases, which is a result of genome translations, enzymatic digestions, and post-translational modifications (PTMs), is making computational efficiency in database searching a serious challenge. Profile analysis shows that most search engines spend 50%-90% of their total time on the scoring module, and that the spectrum dot product (SDP) based scoring module is the most widely used. As a general purpose and high performance parallel hardware, graphics processing units (GPUs) are promising platforms for speeding up database searches in the protein identification process. RESULTS: We designed and implemented a parallel SDP-based scoring module on GPUs that exploits the efficient use of GPU registers, constant memory and shared memory. Compared with the CPU-based version, we achieved a 30 to 60 times speedup using a single GPU. We also implemented our algorithm on a GPU cluster and achieved an approximately favorable speedup. CONCLUSIONS: Our GPU-based SDP algorithm can significantly improve the speed of the scoring module in mass spectrometry-based protein identification. The algorithm can be easily implemented in many database search engines such as X!Tandem, SEQUEST, and pFind. A software tool implementing this algorithm is available at http://www.comp.hkbu.edu.hk/~youli/ProteinByGPU.html.

BitTorrent (BT) plays an important role in Internet content distribution. Because public BTs suffer from the free-rider problem, Darknets are becoming increasingly popular, which use Sharing Ratio Enforcement to increase their efficiency. We crawled and traced 17 Darknets from September 2009 to February 2011, and obtained datasets about over 5 million torrents. We conducted a broad range of measurements, including traffic, sites, torrents, and users activities. We found that some of the features of Darknets are noticeably different from public BTs. The results of our study reflect both macroscopic and microscopic aspects of the overall ecosystem of BitTorrent Darknets.

Rendezvous is a fundamental operation in cognitive radio networks (CRNs) for establishing a communication link on a commonly-available channel between cognitive users. The existing works on rendezvous implicitly assume that each cognitive user is equipped with one radio (i.e., one wireless transceiver). As the cost of wireless transceivers is dropping, this feature can be exploited to significantly improve the rendezvous performance at low cost. In this study, we investigate the rendezvous problem in CRNs where cognitive users are equipped with multiple radios and different users may have different number of radios. We first study how the existing rendezvous algorithms can be generalized to use multiple radios for faster rendezvous. We then propose a new rendezvous algorithm, called role-based parallel sequence (RPS), which specifically exploits multiple radios for more efficient rendezvous. Our basic idea is to let the cognitive users stay in a specific channel in one dedicated radio and hop on the available channels with parallel sequences in the remaining general radios. We prove that our algorithm provides guaranteed rendezvous and derive the maximum time-to-rendezvous (TTR) and upper-bounds on the expected TTR. Extensive experiments are conducted to evaluate the proposed solutions.

In sensor-target surveillance networks, sensors are typically powered by batteries with limited energy and hence it is important to manage the energy usage. In the literature, several methods have been proposed to maximize the lifetime of these networks. We observe that some surveillance applications have lifetime requirements. For example, a surveillance network is used to monitor the precious items in an exhibition and its lifetime must be at least equal to the duration of exhibition. For these surveillance applications, it is desirable to minimize the network cost while fulfilling the given lifetime requirement. In this paper, we address a new problem in which the network cost is minimized while the resulting lifetime is at least equal to a given value L. To minimize the network cost, we place the minimum number of sensors such that all the given targets can be monitored for a duration of at least L and all the sensed data can be forwarded to a given base station. We prove that this problem is NP-hard and derive a lower bound on the minimum number of sensors required. We design an efficient approximation algorithm for this problem. Theoretically, we prove that this approximation algorithm has an approximation ratio of max {2l - m + 2, 3}, where m is the number of targets and l is the number of targets in a small disk centered at the base station with a constant radius. Experimentally, we conduct computer simulation to demonstrate that this approximation algorithm gives close-to-optimal solutions.

Bi-connectivity is a basic requirement for designing fault tolerant topologies in wireless networks. In cognitive radio networks (CRNs), available channels of cognitive users dynamically change since a channel becomes unavailable whenever the channel is reclaimed by primary users. Therefore, fault tolerance of CRNs highly depends on the status of channel availability. However, traditional definition of bi-connectivity concerns only node/link failure and thus is not suitable to CRNs. In this study, we introduce a new definition of generalized-bi-connectivity (g-bi-connectivity) where a CRN is said to be g-bi-connected if the remaining network is still connected when any one of the two events occurs: i) any node fails; ii) any channel becomes unavailable. Based on this definition, our problem is to build a g-bi-connected network by assigning power and channels to the cognitive users. Our objective is to minimize the maximum transmission power of users and the number of channels required. We propose a two-stage approach which consists of the power assignment stage and the channel assignment stage. In the power assignment, we integrate a novel degree-control process which prepares a good topology for minimizing the number of channels in the next stage. We prove that the maximum transmission power of cognitive users is optimized and derive an upper- bound on the number of channels required. We present distributed topology recovery algorithms which give guaranteed g-bi-connectivity in case of node-join and node-leave. Extensive simulations are conducted to evaluate performance of our solution.

Abstract Summary: SOAP3 is the first short read alignment tool that leverages the multi-processors in a graphic processing unit (GPU) to achieve a drastic improvement in speed. We adapted the compressed full-text index (BWT) used by SOAP2 in view of the advantages and disadvantages of GPU. When tested with millions of Illumina Hiseq 2000 length-100 bp reads, SOAP3 takes < 30 s to align a million read pairs onto the human reference genome and is at least 7.5 and 20 times faster than BWA and Bowtie, respectively. For aligning reads with up to four mismatches, SOAP3 aligns slightly more reads than BWA and Bowtie; this is because SOAP3, unlike BWA and Bowtie, is not heuristic-based and always reports all answers. Availability: SOAP3 is available at: http://www.cs.hku.hk/2bwt-tools/soap3; http://soap.genomics.org.cn/soap3.html. Contact: [email protected], [email protected]

SUMMARY Homomorphic hash functions play a key role in securing distributed systems that use coding techniques such as erasure coding and network coding. The computational complexity of homomorphic hash functions remains a main challenge. In this paper, we present a massively parallel solution, named Tsunami, by exploiting the widely available many‐core graphic processing units (GPUs). Tsunami includes the following optimization techniques to achieve the highest ever hashing throughput: (1) using Montgomery multiplication and precomputation to speed up modular exponentiations; (2) using a clean implementation of Montgomery multiplication in order to decrease the demand of registers and shared memory and increase the utilization ratio of GPU processing cores; (3) using our own assembly code to implement the 32‐bit integer multiplication, which outperforms the assembly codes generated by the native compiler by 20%; and (4) exploiting memory alignment and constant memory on GPUs to improve the efficiency of memory access. Integrating the above techniques, our Tsunami achieves a significant improvement over existing results. Specifically, the hashing throughput achieved by Tsunami on a GTX295 GPU (NVIDIA, Santa Clara, CA, US) is about 33 times that of the existing solution on a quad‐core CPU. We also show that the hashing throughput grows almost linearly with the number of GPU cores. Copyright © 2011 John Wiley & Sons, Ltd.

BitTorrent is todays most influential peer-to-peer content distribution system. Currently BitTorrent has two very different operating models: (i) public trackers, and (ii) private trackers (a.k.a. PTs, Darknets). A PT can only be accessed by its registered users, and can provide ultrahigh downloading speed because of its effective share-ratio enforcement (SRE) incentive mechanism which stimulates the users to upload contents as much as possible. Although PTs are becoming more and more popular, they receive little attention from the research literature, possibly because they are operated underground. To understand the popularity of Darknets, the authors have traced 17 PT sites, 2 public tracker sites and 1 BitTorrent search engine for over a year. The authors investigate these PT sites from several aspects and try to understand why they are so successful in terms of attracting loyal users and providing high downloading speed. The authors then analyse the SRE mechanism and ratio free system which are commonly used by PTs. Our results unveil the reason of popularity and effectiveness of PTs. These understandings are essential to the sustainable development of future BitTorrent content distribution systems.

In computer networks, multicast models a class of data dissemination applications, where a common data item is routed to multiple receivers simultaneously. The routing of multicast flows across the network may incur a cost, and such a cost is to be recovered from payments by receivers who enjoy the multicast service. In reality, a group of potential multicast receivers exist at different network locations. Each receiver has a valuation for receiving the multicast service, but such valuation is private information known to itself. A multicast scheme asks each potential receiver to report her valuation, then decides which subset of potential receivers to serve, how to route the multicast flow to them, and how much to charge each of them. A multicast scheme is stragegyproof if no receiver has incentive to lie about her true valuation. It is further group strategyproof if no group of colluding receivers has incentive to lie. We study multicast schemes that target group strategyproofness, in both directed and undirected networks. Our main results reveal that under group strategyproofness, a compromise is necessary in either routing optimality or budget balance. We also design multicast schemes that pursue maximum budget balance while guaranteeing group stragetyproofness and routing optimality.

Cognitive radio networks (CRNs) have emerged as advanced and promising paradigm to exploit the existing wireless spectrum opportunistically. It is crucial for users in CRNs to search for neighbors via rendezvous process and thereby establish the communication links to exchange the information necessary for spectrum management and channel contention, etc. This paper focuses on the design of algorithms for blind rendezvous, i.e., rendezvous without using any centralized controller and common control channel (CCC). We propose a jump-stay channel-hopping (CH) algorithm for blind rendezvous. The basic idea is to generate CH sequence in rounds and each round consists of a jump-pattern and a stay-pattern. Users “jump” on available channels in the jump-pattern while “stay” on a specific channel in the stay-pattern. We prove that two users can achieve rendezvous in one of four possible pattern combinations: jump-stay, stay-jump, jump-jump, and stay-stay. Compared with the existing CH algorithms, our algorithm has the overall best performance in various scenarios and is applicable to rendezvous of multiuser and multihop scenarios. We derive upper bounds on the maximum time-to-rendezvous (TTR) and the expected TTR of our algorithm for both 2-user and multiuser scenarios (shown in Table 1). Extensive simulations are conducted to evaluate the performance of our algorithm.

In the service-oriented computing, a single transaction initiated by a client might invoke many different services in other administrative domains. Existing models for authorizing the access assume that all services involved in collaboration are managed by the central authority, which is not always a realistic premise. In this paper, we propose a novel authorization model for dynamic service collaboration. With the authorization discovery process, the client can discover the needed authorization for service access available in other autonomous domains. With extensions to SoD relationship, the conflicts of client interests can be formalized and expressed as constraints. The authorization problems are formalized to choose the optimal access path for each task. At last, the example and experiments show the practicality and the effectiveness of our scheme.

The rapid development of applications running on global information infrastructure poses the problem of securing information sharing among domain collaborations. Existing access control models are defective in dynamic authorization based on user's trustworthiness and do not take full advantages of the infrastructure in implementing access control system. In this work, we propose a trust and role based access control model and the corresponding framework in infrastructure-centric environment. With the extension to RBAC model, trust level requirements, which dictate that the roles in the privilege context must be activated by the trustworthy user, can be specified. The comprehensive trust model, which calculates the user's trust level in multiple trust contexts based on behavior histories, is proposed. Moreover, by taking advantages of the infrastructure services, our scheme is flexible and scalable in that system administrators are free to choose custom scoring functions while the infrastructure trust evaluation services are relieved of the heavy burdens of history record maintenance and trust level update.

Private P2P communities, as known as "BitTorrent Darknets" or "Private Trackers (PTs)", have received much attention in the research community recently. The downloading performance in PTs with high Seeder-to-Leecher Ratio (SLR) is much better than in public P2P communities because PTs deploy auxiliary Share Ratio Enhancement (SRE) mechanism. Nevertheless, though high SLR can benefit leechers, it will result in "Poor Downloading Motivation" problem to members who want to increase their share ratio in order to safely survive. This problem may discourage PT members' activity. To improve sustainability of PTs, we adopt Predator-Prey model in ecology to analysis high SLR phenomenon, study the optimal stable SLR range to PTs and solve the above problem. Experiments verify our model and provide insight to study PTs.

Cognitive radio networks (CRNs) have emerged as advanced and promising paradigm to exploit the existing wireless spectrum opportunistically. It is crucial for users in CRNs to search for neighbors via rendezvous process and thereby establish the communication links to exchange the information necessary for spectrum management and channel contention etc. This paper focuses on the design of algorithms for blind rendezvous, i.e., rendezvous without using any central controller and common control channel (CCC). We propose a jump-stay based channel-hopping (CH) algorithm for blind rendezvous. The basic idea is to generate CH sequence in rounds and each round consists of a jump-pattern and a stay-pattern. Users “jump” on available channels in the jump-pattern while “stay” on a specific channel in the stay-pattern. Compared with the existing CH algorithms, our algorithm achieves the following advances: i) guaranteed rendezvous without the need of time-synchronization; ii) applicability to rendezvous of multi-user and multi-hop scenarios. We derive the maximum time-to-rendezvous (TTR) and the upper-bound of expected TTR of our algorithm for both 2-user and multi-user scenarios (shown in Table I). Extensive simulations are further conducted to evaluate performance of our algorithm.

We address a new and general maximal lifetime problem in sensor-target surveillance. We assume that each sensor can watch at most k targets (k ≥ 1) and each target should be watched by h sensors (h ≥ 1) at any time. The problem is to schedule sensors to watch targets and forward the sensed data to a base station such that the lifetime of the surveillance network is maximized. This general problem includes the existing ones as its special cases (k = 1 and h = 1 in and k = 1 and h ≥ 2 in). It is also important in practice because some sensors can monitor multiple or all targets within their surveillance ranges and multisensor fusion (i.e., watching a target by multiple sensors) gives better surveillance results. The problem involves several subproblems and one of them is a new matching problem called (k, h)-matching. The (k, h)-matching problem is a generalized version of the classic bipartite matching problem (when k = h = 1, (k, h)-matching becomes bipartite matching). We design an efficient (k, h)-matching algorithm to solve the (k, h)-matching problem and then solve the general maximal lifetime problem. As a byproduct of this study, the (k, h)-matching problem and the proposed (k, h)-matching algorithm can potentially be applied to other problems in computer science and operations research.

BitTorrent is today's most influential peer-to-peer system. Currently BitTorrent has two very different operating models: (1) public trackers, and (2) private trackers (also known as Darknets). A private tracker can only be accessed by its registered users, and it can provide ultra high downloading speed due to its effective Share Ratio Enforcement (SRE) incentive mechanism which stimulates the users to upload contents as much as possible. Although private trackers are becoming more and more popular, they receive little attention from the research literature, possibly because they are operated underground. To understand the popularity of Darknets, we have traced 17 private tracker sites, 2 public tracker sites and 1 BitTorrent search engine for 6 months. We investigate these private tracker sites from several aspects and try to understand why they are so successful in terms of attracting loyal users and providing high downloading speed. We then analyze the SRE mechanism, credit/point system and ratio free system used by private trackers. Our results unveil the reason of popularity and effectiveness of private trackers. Furthermore, we point out the “poor downloading motivation” phenomenon caused by the imbalance between supply and demand in private trackers. These understandings are essential to the sustainable development of future BitTorrent content distribution systems.

Cloud computing provides a novel computing paradigm for enterprises to store programs and data in the Cloud in a transparent manner, which poses the challenge of security and privacy. In this paper, based on homomorphic cryptography and Zero-Knowledge Proof, we present a novel privacy-preserving scheme for Cloud publish/subscribe service, which achieve efficient privacy-preserving authentication, data integrity, and publish-subscribe confidentiality. The performance evaluation and security analysis demonstrate the practice and validity of the proposed scheme.

Recently, sensor data storage has gained increasing popularity for reliable access to data through redundancy spread over unreliable nodes in wireless sensor networks. In storage-centric sensor networks, several schemes have been proposed to optimize the performance of data management in terms of data availability, repair bandwidth, etc. However, few works have been undertaken to study the performance of these data management schemes from a comprehensive point of view. In this paper, we adopt a concise graphic model, i.e., Stochastic Petri Nets (SPNs), to analyze the performance of three representative data management schemes. From the steady state probability matrix of the SPNs models, we can easily get the average energy consumption, repair bandwidth, reliability and data availability. Based on numerical results, we provide guidelines for designing sensor data storage systems. The results also demonstrate that our proposed models are suitable for analyzing data management schemes in sensor data storage.

BitTorrent is currently the most prevalent peer-to-peer file sharing system. Many researchers study and modify BitTorrent protocol in order to improve its performance. A fundamental problem is the evaluation of those newly proposed protocols. The current methods of studying peer-to-peer systems, such as analytical modeling, discrete-event simulations and deployment on real networks, often are limited in scalability, reproducibility, and accuracy. Moreover, many of them are difficult to achieve complete and accurate evaluation results under a wide range of conditions. Emulation is an effective tool to tackle these problems and it is suitable to study and evaluate the behaviors of BitTorrent-like file sharing systems. Thus, we propose a lightweight emulator, Virtual BT, which is scalable, flexible, accurate and easy to deploy. It adopts a distributed network architecture whose function modules are loose-coupled and easy to be modified in order to study BitTorrent protocol design. More than 200 virtual nodes can be executed on a contemporary personal computer by using process-level virtualization; and every virtual node exchanges data without causing any disk I/O overhead. Through experiments, Virtual BT demonstrates its effectiveness and gives accurate predictions that closely match the results observed from real network measurements.

Intricate malware can result in the failure of on-line Comprehensive Protection (CP) in distributed systems, and place the system in an unsafe state which is difficult to recover from. There lacks an effective scheme to defend against this extreme attack. In this paper, based on the Two-layer Protection and Cooperative Recovery (TPCRS) mechanism, we propose an efficient survivable scheme against malware attacks in distributed systems. The basic strategy is to deploy an Emergency Response/Recovery (ER) agent at each node to recognize the state of the system whenever the CP fails, and to carry out cooperative security among multiple nodes so that the infected nodes can be rapidly recovered. Furthermore, a Preventive Maintenance (PM) model is adopted to enhance the reliability of the distributed system. Simulation results demonstrate the practicality and efficiency of the proposed schemes.

In Cloud computing, users with different service requirements often need to negotiate with service provider via Service Level Agreement (SLA). The unique pay-as-you-go billing way in Cloud computing challenges resource provisioning for service providers. In this paper, based on the Dirichlet multinomial model, we present an efficient reputation-based QoS provisioning scheme, which can minimize the cost of computing resources, while satisfying the desired QoS metrics. Unlike the previous counterparts, we consider the statistical probability of the response time as a practical metric rather than the typical mean response time. Numerical results show the efficiency and effectiveness of the proposed scheme.

BitTorrent plays a very important role in the current Internet content distribution. When BitTorrent public tracker sites are suffering from free-riding problem, private tracker sites (PTs) work very well because of Share Ratio Enforcement (SRE) which is an auxiliary effective incentive mechanism. Understanding PTs is essential to content distribution. We have crawled and traced 15 tracker sites with over 3.5 million torrents for 7 months. We first provide taxonomy of PTs, and then present measurement study on the characteristics of PTs from the user viscosity, torrents evolution, user behaviors, and content distribution. Some of the features are apparently different from public trackers. Furthermore, we analyze SRE mechanism and auxiliary credit system, and use game theory to study effectiveness of SRE mechanism. There exists “uploading starvation” phenomenon in private trackers. We model SRE mechanism and propose an improved SRE mechanism to further incent the users and enhance the performance of private trackers.

BitTorrent plays a very important role in the current Internet content distribution. The enormous impact of public and private trackers should not be overlooked. Public trackers are suffering from free-riding problem, but private trackers are becoming more and more popular and they run very well in terms of an effective Share Ratio Enforcement (SRE) which is an auxiliary incentive mechanism. In this paper, we have crawled and traced 15 trackers with 3.5 million torrents for over 6 months. We first provide taxonomy of private trackers, and then present in breadth and depth measurement from the user viscosity, torrents evolution, user behaviors, content distribution and other metrics. Some features are apparently different from public trackers. Furthermore, we analyze SRE mechanism and point/credit system, and use game theory to study the effectiveness of SRE. There exists "uploading starvation" phenomenon in private trackers. We model SRE mechanism and preliminary propose an improved SRE mechanism to further incent users and enhance the performance of private trackers.

Robotic sensor networks are more powerful than sensor networks because the sensors can be moved by the robots to adjust their sensing coverage. In robotic sensor networks, an important problem is movement control: how the robots can autonomously move to the desired locations for sensing and data collection. In this paper, we study a new movement control problem with the following essential requirements: i) an initial and possibly disconnected network is self-organized into a bi-connected network, ii) only 1-hop information is used for movement control, iii) the coverage of the network is maximized while the total moving distance in the movement process is minimized. We propose a simple movement control algorithm for this problem. This algorithm emulates the attractive force (such as the force in a stretched spring) and the repulsive force (such as the electrostatic force between electric charges) in nature, such that each robot simply follows the resultant virtual force to move. We theoretically prove that this algorithm guarantees bi-connected networks under a mild condition and derive bounds on the maximum coverage and the minimum moving distance. We conduct extensive simulation experiments to demonstrate that the proposed algorithm is effective.

Abstract In this paper, we propose a novel security scheme with key recovery capability for mobile communications. The proposed key recovery mechanism offers a “backdoor” for an authorized agency to monitor suspected communications while protecting legal users from unauthorized disclosure of their data privacy. All the features form a unitary security scheme with monitoring service. The performance analysis shows that our scheme has a low‐computational complexity and it can be practically deployed on contemporary mobile devices. Copyright © 2009 John Wiley & Sons, Ltd.

The paper addresses the maximal lifetime problem in sensor-target surveillance networks. Given a set of sensors and targets in an Euclidean plane, each sensor can watch all targets within its surveillance range and each target should be watched by at least one sensor at any time. The problem is to schedule the sensors to watch the targets and forward the sensed data to the base station, such that the lifetime of the surveillance network is maximized, where the lifetime is the duration that all targets are watched and all active sensors are connected to the base station. We propose an optimal solution to achieve the maximal lifetime. Our solution consists of three steps: 1) compute the maximal lifetime of the surveillance network and find a workload matrix and data flows by using the linear programming technique; 2) decompose the workload matrix into a sequence of schedule matrices by using the perfect matching technique; 3) determine the sensor-target surveillance trees based on the above obtained schedule matrices and data flows, which specify the active sensors and the routes to pass sensed data to the base station. The proposed optimal solution is illustrated by a numeric example.

BitTorrent is one of the most popular P2P file sharing systems. However, chunk-based file sharing mode makes it difficult to detect content pollution and prevent pollution dissemination during downloading process. In this paper, we propose an early warning scheme against pollution dissemination for BitTorrent. Our idea is to build an early cooperative warning mechanism and rapidly spread alert message among peers in the swarm when pollution is detected at the early stage, which is called "early warning, quickly reacting". The performance evaluation based on fluid model shows the necessity and effectiveness of our scheme, which effectively reduces the traffic abusement and restricts pollution dissemination in BitTorrent-like P2P networks. Another advantage of our solution is that it can handle cheating behaviors made by malicious or unconscious peers, which shows the robustness of our solution.

Homomorphic hash functions (HHFs) have been applied into peer-to-peer networks with erasure coding or network coding to defend against pollution attacks. Unfortunately HHFs are computationally expensive for contemporary CPUs, This paper to exploit the computing power of graphic processing units (GPUs) for homomorphic hashing. Specifically, we demonstrate how to use NVIDIA GPUs and the computer unified device architecture (CUDA) programming model to achieve 38 times of speedup over the CPU counterpart. We also develop a multi-precision modular arithmetic library on CUDA platform, which is not only key to our specific application, but also very useful for a large number of cryptographic applications.

The low-level disk characteristics play a vital role for the I/O performance optimization in disk storage systems. This paper presents FAXtrac, a tool for automatically and efficiently extracting the exact disk layout, i.e., the number of sectors of each disk track. FAXtrac includes three algorithms, namely SptExplore, TrackExplore, and RemoveNoise, to ensure the correctness and speediness of the extraction of disk layout. We tested FAXtrac on a number of different disk models. It took only 75 minutes to extract the detailed disk layout for a 250 GB SATA disk, which shortened the time by two orders of magnitude as compared with an existing solution. We believe that FAXtrac is a valuable tool for the hard disk storage research community.

In this paper, we address the problem of joint channel assignment, link scheduling, and routing for throughput optimization in wireless networks with multi-radios and multi-channels. We mathematically formulate this problem by taking into account the interference, the number of available radios the set of usable channels, and other resource constraints at nodes. We also consider the possible combining of several consecutive channels into one so that a network interface card (NIC) can use the channel with larger range of frequencies and thus improve the channel capacity. Furthermore, we consider several interference models and assume a general yet practical network model in which two nodes may stillnotcommunicate directly even if one is within the transmission range of the other. We designed efficient algorithm for throughput (or fairness) optimization by finding flow routing, scheduling of transmissions, and dynamic channel assignment and combining. We show that the performance, fairness and throughput, achieved by our method is within a constant factor of the optimum. Our model also can deal with the situation when each node will charge a certain amount for relaying data to a neighboring node and each flow has a budget constraint. Our extensive evaluation shows that our algorithm can effectively exploit the number of channels and radios. In addition, it shows that combining multiple channels and assigning them to a single user at some time slots indeed increases the maximum throughput of the system compared to assigning a single channel.

Realizing on-demand media streaming in a peer-to-peer (P2P) fashion is more challenging than in the case of live media streaming, since only peers with close-by media play progresses may help each other in obtaining the media content. The situation is further complicated if we wish to pursue low aggregated link cost in the transmission. In this paper, we present a new algorithmic perspective toward on-demand P2P streaming protocol design. While previous approaches employ streaming trees or passive neighbor reconciliation for media content distribution, we instead coordinate the streaming session as an auction where each peer participates locally by bidding for and selling media flows encoded with network coding. We show that this auction approach is promising in achieving low-cost on-demand streaming in a scalable fashion. It is amenable to asynchronous, distributed, and lightweight implementations, and is flexible to provide support for random-seek and pause functionalities. Through extensive simulation studies, we verify the effectiveness and performance of the proposed auction approach, focusing on the optimality in overall streaming cost, the convergence speed, and the communication overhead.

Energy efficient routing and power control techniques in wireless ad hoc networks have drawn considerable research interests recently. In this paper, we address the problem of energy efficient reliable routing for wireless ad hoc networks in the presence of unreliable communication links or devices or lossy wireless link layers by integrating the power control techniques into the energy efficient routing. We consider both the case when the link layer implements a perfect reliability and the case when the reliability is implemented through the transport layer, e.g., TCP. We study the energy efficient unicast and multicast when the links are unreliable. Subsequently, we study how to perform power control (thus, controlling the reliability of each communication link) such that the unicast routings use the least power when the communication links are unreliable, while the power used by multicast is close to optimum. Extensive simulations have been conducted to study the power consumption, the end-to-end delay, and the network throughput of our proposed protocols compared with existing protocols.

Abstract The access control model is a core aspect of trusted information systems. Based on the role based access control (RBAC) model, we put forward the concept of thehomonymous role, which extends the role control categories in RBAC, balances the control granularity and the storage space requirements, and executes the fine‐grained access control. Instead of the traditional global access control policies (GACP), we propose thehomonymous control domain(HCD) mechanism to enable the coexistence of multiple types of access control policies in a single system, thereby improving the control granularity and flexibility. The HCD mechanism facilitates the discretionary supporting of independent access control policies for its homonymous user. The HCD mechanism and the traditional access control mechanism can be linked to construct a two‐layer access control policy mechanism for a system. Notably, we also consider the temporal characteristic in HCD, which is a critical feature of modern access control models. Furthermore, we analyze the conflicts between the HCD and GACP mechanisms. Finally, we design and implement our HCD on FreeBSD to demonstrate the advantages of the two‐layer access control mechanism. Copyright © 2008 John Wiley & Sons, Ltd.

Cluster based Web servers have been widely deployed by enterprises to accommodate the ever-increasing population of Internet users. But during the period of high client loads, Web clusters may still fail to provide timely service to all the clients, and part of the clients may suffer unacceptable long delay. In order to provide better service to premium users, QoS schemes need be implemented in the Web clusters. Controlling mechanisms for stand-alone Web server have been studied in previous years, but it is still a challenging problem to design a QoS controller for Web clusters. In this paper, we apply a fuzzy Proportional Integral (PI) controller to dynamically assign system resources for guaranteeing proportional connection delay ratio. To overcome the difficulties caused by HTTP/1.1, we further propose a preemptive scheme which disconnects those idle clients with low priority if there is short of resources. We implement the controller in a real Web cluster system based on Apache, and study the performance by extensive experiments. Our results show that (1) the proposed fuzzy PI controller achieves much better performance than classic PI controller; (2) the preemptive schemes outperform non-preemptive schemes significantly.

Address allocation in Mobile Ad Hoc Network (MANET) receives significant importance recently, as a mobile device cannot participate in unicast communications until it is assigned with a conflict free IP address. All routing protocols assume nodes to be configured a priori with a unique IP address. Unlike infrastructure based networks, MANET supports autonomous and spontaneous networking and therefore, should be capable of self organization and configuration. We present a new address allocation protocol in MANET based on the concept of quadratic residue. Each node in the network is capable of assigning a unique IP address with low latency. Addresses are reclaimed automatically, as the quadratic residues lie in cycles. This saves lot of extra communication overhead and bandwidth. Our approach also has support for network merging and partitioning. The proposed scheme can be applied to large scale MANETs with low communication overhead, even distribution, and low latency.

Wireless mesh networks have attracted extensive research interests in recent years. With the maturity and pervasive deployment of IEEE 802.11a/b/g technology, 802.11 DCF protocol is considered as a promising candidate for constructing the backbone of wireless mesh networks. In a multi-channel multi-interface wireless mesh network, point-to-point 802.11 wireless link can provide the highest throughput; hence it is critical to understand the 802.11 throughput performance in a point-to-point configuration. This paper presents a simple yet precise Markov model for the analysis of point-to-point 802.11 link performance in terms of saturation throughput. Different from previously proposed analytical models, our model does not assume a constant and independent collision probability. Our analytical model is validated by computer simulations for both 802.11b and 802.11g configurations.

Network coding has recently been widely applied in various networks for system throughput improvement and/or resilience to network dynamics. However, the computational overhead introduced by the network coding operations is not negligible and has become the cornerstone for real deployment of network coding. In this paper, we exploit the computing power of contemporary Graphic Processing Units (GPUs) to accelerate the network coding operations. We proposed three parallel algorithms that maximize the parallelism of the encoding and decoding processes, i.e., the power of GPUs is fully utilized. This paper also shares our optimization design choices and our workarounds to the challenges encountered in working with GPUs. With our implementation of the algorithms, we are able to achieve up to 12 times of speedup over the highly optimized CPU counterpart, using the NVIDIA GPU and the Computer Unified Device Architecture (CUDA) programming model.

Rerouting is a viable and cost-effective approach to decrease the blocking probability in legacy circuit-switched networks. We study lightpath rerouting in optical WDM networks in this paper. We investigate two different lightpath rerouting strategies, namely, passive rerouting and intentional rerouting. Passive rerouting means rerouting established lightpaths to accommodate new lightpath requests which will otherwise be blocked. Intentional rerouting is to intentionally reroute existing lightpaths during their life period without affecting other lightpaths, so as to achieve a better load balancing. Through extensive simulation studies, we draw the following conclusions: 1) when there is wavelength conversion, passive rerouting works much better than intentional rerouting; 2) when there is no wavelength conversion, a naive-wavelength- retuning algorithm can achieve the most benefit of passive rerouting while path-adjusting does not help too much.

Overlay multicast, which performs topology construction and data relaying in the application layer, has recently emerged as a promising vehicle for data distribution. In most of the existing systems, only a single stream is assumed for each overlay, and multiple streams, if needed, are distributed separately. In addition, while the overlay node performs relay functions, they generally do not filter the content to match the heterogeneous bandwidth constraints. We consider a more general model, in which a multicast session may consist of multiple data streams, such as video and audio, which are to be delivered to the same set of nodes. The services to these steams are elastic through layer dropping, shaping, or transcoding. In this paper, we focus on an important resource allocation problem in such an adaptive multi-stream multicast framework: Assume that each stream has an associated utility function, how to maximize the total utility of all the streams in a multicast session. The problem involves optimization not only in individual nodes, but also in the global overlay structure. We show that, given a total bandwidth of the streams, there is an efficient and optimal solution for the allocation problem at a single node. The problem however can be much more complicated in a hierarchical structure like tree. Yet we show that, if the utility is concave with bandwidth, i.e., the marginal improvement diminishes with bandwidth increase, then the upstream constraint can be ignored and a local optimal solution is simply the global optimal solution.

Energy efficient routings and power control techniques in wireless networks have drawn considerable research interests recently. In this paper, we address the problem of energy efficient reliable routing in wireless networks in the presence of unreliable communication links or devices or lossy wireless link layers by integrating the power control techniques into the energy efficient routing. We study both the case when the link layer implements a perfect reliability and the case when the reliability is implemented through the transport layer, e.g., TCP. We study the energy efficient unicast when the links are unreliable. Subsequently, we study how to perform power control (thus, controlling the reliability of each communication link) such that the unicast routings use the least power when the communication links are unreliable. We presented both centralized algorithms and distributed algorithms for all the questions we studied. We conducted extensive simulations to study the power consumption, the end-to-end delay, and the network throughput of our protocols compared with existing protocols

Much research has focused on caching adaptive videos to improve system performance for heterogeneous clients with diverse access bandwidths. However, existing rate-adaptive caching systems, which are based on layered coding or transcoding, often suffer from a coarse adaptation and/or a high computation overhead. In this paper, we propose an innovative rate-adaptive caching framework that enables low-cost and fine-grained adaptation by using MPEG-4 fine-grained scalable videos. The proposed framework is both network-aware and media-adaptive; i.e., the clients can be of heterogeneous streaming rates, and the backbone bandwidth consumption can be adaptively controlled. We develop efficient cache management schemes to determine the best contents to cache and the optimal streaming rate to each client under the framework. We demonstrate via simulations that, compared to nonadaptive caching, the proposed framework with the optimal cache management not only achieves a significant reduction in the data transmission cost, but also enables a flexible utility assignment for the heterogeneous clients. Our results also show that the framework maintains a low computational overhead, which implies that it is practically deployable

Rerouting is an effective approach to decrease the blocking probability in legacy circuit-switched networks. In this paper, we consider intentional lightpath rerouting in all-optical WDM mesh networks. We propose a dynamic least congested routing (DLCR) algorithm, which dynamically switches the lightpath between the primary route and alternate route according to the network traffic distribution. Extensive simulation results show that DLCR algorithm can achieve much better blocking performance than traditional routing algorithms, including shortest path routing, fixed-alternate routing, and least congested path routing. We also find that the performance gain is more significant when wavelength conversion is available.

Blocking probability has been one of the key performance indexes in the design of wavelength-routed all-optical WDM networks. Existing research has demonstrated that an effective Routing and Wavelength Assignment (RWA) algorithm and wavelength conversion are two primary vehicles for improving the blocking performance. However, these two issues have largely been investigated separately; in particular the existing RWA algorithms have seldom considered the presence of wavelength conversion. In this paper, we firstly demonstrate that the existing dynamic RWA algorithms do not work well in the presence of wavelength conversion as they usually only take into account the current traffic, and do not explicitly consider the route lengths. We then propose a weighted least-congestion routing and first-fit wavelength assignment (WLCR-FF) algorithm that considers both the current traffic load and the route lengths jointly. We further introduce an analytical model that can evaluate the blocking performance for WLCR algorithm. We carry out extensive numerical studies over typical topologies including ring, mesh-torus, and the 14-node NSFNET; and compare the performance of WLCR-FF with a wide variety of existing routing algorithms including static routing, fixed-alternate routing and least-loaded routing. The results conclusively demonstrate that the proposed WLCR-FF algorithm can achieve much better blocking performance in the presence of sparse or/and full wavelength conversion.

Wavelength conversion has been shown as one of the key techniques to improve blocking performance in a wavelength-routed all-optical network. Given that wavelength converters nowadays remain very expensive, how to make effective use of a limited number of wavelength converters becomes an important issue. We propose sparse-partial wavelength conversion (SPWC) network architecture with the inherent flexibility that can facilitate network carriers to migrate the optical backbone to support wavelength conversion. We demonstrate that this network architecture can significantly save the number of wavelength converters, yet achieving excellent blocking performance. Theoretical and simulation results indicate that, the performance of a wavelength-routed WDM network with only 1-5%of wavelength conversion capability is very close to that with full-complete wavelength conversion capability.

Caching video objects at proxies close to clients has attracted a lot of attention in recent years. To meet diverse client bandwidth conditions, there have been research efforts to combine proxy caching with video layering or transcoding. Nevertheless, these adaptive systems suffer from either coarse adaptation granularity due to the inflexible structures of existing layered coders or high computation overhead due to the transcoding operations. In this paper, we propose a novel adaptive video caching framework that enables low-cost and fine-grained adaptation. The innovative approach employs the MPEG-4 fine-grained scalable (FGS) video with postencoding rate control. We demonstrate that the proposed framework is both network aware and media adaptive: clients can be of heterogeneous streaming rates, and the backbone bandwidth consumption can be adaptively controlled. We also examine the design and management issues in the framework, in particular, the optimal stream portions to cache and the optimal streaming rate to each client. Simulation results demonstrate that, compared to nonadaptive caching, the proposed framework with optimal cache management not only achieves significant reduction on transmission costs but also enables flexible utility assignment for the heterogeneous clients. Meanwhile, its computational overhead is kept at a low level, implying that it is practically deployable.

Existing research demonstrated that an effective routing and wavelength assignment (RWA) scheme and a wavelength converter placement algorithm are the two primary vehicles for improving the blocking performance in a wavelength-routed all-optical network. However, these issues have largely been investigated separately, in particular, the RWA has seldom considered the existence of wavelength converters. In this paper, we argue perhaps for the first time, that an effective RWA algorithm needs to take into account the presence of wavelength conversion as the latter is usually done at much earlier stage during the capacity planning. We proceed to show that existing dynamic RWA algorithms largely fail in the presence of wavelength conversion. We then propose a weighted least-congestion routing and first-fit wavelength assignment (WLCR-FF) RWA algorithm in conjunction with a simple heuristic wavelength converter placement algorithm called minimum blocking probability first (MBPF) that considers both the distribution of free wavelengths and the lengths of each route jointly. We further introduce an analytical model that can obtain the blocking performance of the proposed WLCR routing algorithm. Using both analysis and simulation, we carry out extensive numerical studies over the typical topologies including the ring, mesh-torus, and two mesh topologies, the 14-node NSFNET and the 19-node European Optical Network (EON); we compare the performance of proposed algorithm with a wide variety of existing routing algorithms including static routing, fixed-alternate routing and least-loaded routing algorithms. The results conclusively demonstrate that the proposed WLCR-FF algorithm can achieve much better blocking performance in the environment of sparse or/and full wavelength conversion.

We propose a novel integrated optical network switching architecture. The proposal offers an approach to signaling for the purpose of transport on an all-optical network of optical and nonoptical legacy network traffic. In order to provide effective end-to-end control and efficient transport services, new signaling and control techniques are required. Standard organizations such as Optical Interworking Forum (OIF) and Internet Engineering Task Force have developed interface methods between client and transport networks, as well as signaling processes for resource allocation. We propose a network controller, which implements interfaces for such integration in the intermediate future, as well as provides a feasible path for the long-term objective of all optical networking. Performance and capacity issues for these systems introduce new dimensions to the existing set of networking problems, since optical paths can now be set up in real-time. There are two main contributions in this paper: (1) functional composition of a network controller, which translates legacy signaling to optical connection signaling and path establishment and (2) determining when to issue an optical connection request based on the current network conditions such as link utilization, so that the integrated optical network can operate efficiently. Analytical approximations, as well as simulation results for call blocking performance are also presented.

Sparse wavelength conversion and appropriate routing and wavelength assignment (RWA) algorithms are the two key factors in improving the blocking performance in wavelength-routed all-optical networks. It has been shown that the optimal placement of a limited number of wavelength converters in an arbitrary mesh network is an NP-complete problem. There have been various heuristic algorithms proposed in the literature, in which most of them assume that a static routing and random-wavelength assignment RWA algorithm is employed. However, the existing work shows that fixed-alternate routing and dynamic routing RWA algorithms can achieve much better blocking performance. Our study further demonstrates that the wavelength converter placement and RWA algorithms are closely related in the sense that a well-designed wavelength converter placement mechanism for a particular RWA algorithm might not work well with a different RWA algorithm. Therefore, the wavelength converter placement and the RWA have to be considered jointly. The objective of this paper is to investigate the wavelength converter placement problem under the fixed-alternate routing (FAR) algorithm and least-loaded routing (LLR) algorithm. Under the FAR algorithm, we propose a heuristic algorithm called minimum blocking probability first for wavelength converter placement. Under the LLR algorithm, we propose another heuristic algorithm called weighted maximum segment length. The objective of the converter placement algorithms is to minimize the overall blocking probability. Extensive simulation studies have been carried out over three typical mesh networks, including the 14-node NSFNET, 19-node EON, and 38-node CTNET. We observe that the proposed algorithms not only outperform existing wavelength converter placement algorithms by a large margin, but they also can achieve almost the same performance compared with full wavelength conversion under the same RWA algorithm.

Existing research demonstrates that an effective routing and wavelength assignment (RWA) strategy and a proper wavelength converter placement algorithm are the two primary vehicles for improving the blocking performance of wavelength-routed network. However, these two issues have largely been investigated, separately in that the existing RWA algorithms seldom consider the presence of wavelength conversion. We argue in this paper that any RWA algorithm needs to take into account the underlying wavelength conversion for two reasons: (1) wavelength converter placement is usually done at a much earlier stage during capacity planning; and (2) one of the key advantages of an all-optical network is its reconfigurability in that the network topology can be changed through routing and wavelength assignment. We propose a weighted least-congestion routing and first-fit wavelength assignment (WLCR-FF) RWA algorithm in conjunction with a heuristic wavelength converter placement algorithm called minimum blocking probability first (MBPF) that considers both the distribution of free wavelengths and the lengths of each route jointly. Using both analysis and simulation, we carry out extensive studies to compare the performance of the proposed algorithms over a variety of topologies. The results demonstrate that the proposed WLCR-FF algorithm can achieve much better blocking performance than static routing, fixed-alternate routing and least-loaded routing algorithms, in the environment of sparse or/and full wavelength conversion.