Fully Homomorphic Encryption (FHE) enables privacy-preserving computation on encrypted data. However, it incurs massive computation and DRAM traffic overheads, making hardware acceleration essential. Existing FPGA-based solutions offer limited exploration of bandwidth utilization and memory optimizations, leaving room for further performance improvements.

Vision models fail both under tiny pixel attacks and under real-world shifts in style or background because they latch onto spurious features. We propose a two-step, label-free method. (1) Spurious-Invariant Self-Supervised Pre-training (SISSP) trains an encoder to collapse representations of the same object despite randomized styles and backgrounds, pruning shortcut signals. (2) Semantic-Alignment Adversarial Refinement (SAAR) takes any attack and projects it back into a small ball within SISSP feature space, yielding adversaries that look natural yet still fool the classifier. Fine-tuning with SISSP features and SAAR images produces a ResNet-50 that retains 64% ImageNet accuracy, 46% PGD robustness without environment labels or specialized augmentations. Together, SISSP provides a semantics-aware metric and SAAR generates on-manifold adversaries, achieving the first ImageNet-scale model robust to both pixel-level noise and semantic shifts.

Matrix transposition is a classic operation in machine learning and scientific applications. HBM-enabled FPGAs, with their high-bandwidth capabilities, are increasingly deployed in the data centers. However, achieving high bandwidth utilization on HBM is challenging due to the large strided access patterns in matrix transposition, which significantly degrade bandwidth utilization. Additionally, saturating HBM bandwidth requires a large number of parallel accesses, further complicating the design. In this paper, we present a high throughput matrix transposition design for HBM-enabled FPGAs. Our design performs small strided accesses to HBM, ensuring optimized bandwidth utilization. We use on-chip SRAMs to reorganize data from HBM into the access pattern needed for matrix transposition. Inspired by Latin Squares, we propose a novel data layout for storing the matrix tiles in SRAM. This data layout is paired with a customized scheduling strategy to eliminate SRAM bank conflicts. We develop a fully pipelined architecture with multiple Processing Elements (PEs) to enable parallel HBM accesses. Our design is highly scalable, supporting various configurations of HBM channels and arbitrary matrix dimensions. We implement the proposed design on the AMD Alveo U280 FPGA. Experimental results show that our design achieves a matrix transposition throughput of up to 415 GB/s, more than 90% of the peak HBM bandwidth of the target FPGA platform. Our design outperforms state-of-the-art GPU implementations, delivering up to 1.44 × higher HBM memory bandwidth utilization.

Homomorphic Encryption (HE) is a promising technique for protecting user privacy in cloud-based Machine Learning (ML) inference. However, homomorphically encrypted operations are orders of magnitude slower than the corresponding unencrypted operations due to high computation and memory bandwidth requirements. FPGAs are attractive platforms for designing domain-specific accelerators. Manually programming FPGAs for HE ML inference is challenging, as different HE parameters and operations require different mapping strategies. We propose OLA, the first FPGA-based overlay accelerator for low latency computation on homomorphically encrypted data. OLA eliminates the need for manual and time consuming FPGA programming by providing a Python-based interface and a compiler that efficiently maps OLA programs to hardware instructions for execution. The hardware architecture and instruction set are co-designed to accelerate common HE primitives, while the compiler maps all the required HE operations to these primitives for efficient execution. OLA features two optimizations to address memory bandwidth challenges in HE computation. First, we propose an asynchronous dataflow execution model where the compiler manages data processing order and the architecture enforces it at run time. This approach enables guaranteed data reuse via on-chip SRAMs. Second, we design latency-aware instruction scheduling in the compiler to reduce data reuse distance. We implement the overlay accelerator on the AMD Alveo U280 FPGA. We evaluate the effectiveness of the proposed overlay accelerator by executing various HE operations, HE linear algebra benchmarks, and end-to-end ML inference. Experimental results show that OLA reduces the latency of HE operations by up to 683× (4.4×) compared with State-Of-The-Art (SOTA) CPU (GPU) implementations. It achieves up to 3212× speedup in latency compared with the SOTA CPU implementations for HE ML inference.

Bootstrapping is a critical operation in Fully Homomorphic Encryption (FHE) for privacy-preserving computation. Due to its significant computational overhead, accelerating bootstrapping is crucial for practical FHE applications involving deep evaluation circuits. In this paper, we introduce FAST, an FPGA-based accelerator for efficient FHE bootstrapping. We propose novel datapath optimizations for two key operations in bootstrapping: homomorphic linear transformation (HLT) and polynomial evaluation. Our memory-efficient datapath designed for HLT significantly reduces off-chip ciphertext access. We also speed up the polynomial evaluation process by reducing the number of required HE operations. We conduct an in-depth analysis of the Advanced Bootstrapping Algorithm (ABA) and highlight its computational advantages. FAST is the first accelerator to support ABA, demonstrating significant speedup for bootstrapping. In addition, we develop a novel versatile permutation circuit to handle diverse permutation patterns in FHE, achieving high throughput and efficient resource utilization. Compared with the state-of-the-art (SOTA) GPU and FPGA designs, FAST achieves 8.84× and 5.89× speedups for bootstrapping, respectively. As illustrative examples of deep FHE applications, we show that FAST delivers over 20× speedup for logistic regression training compared with the SOTA GPU implementation and outperforms the SOTA FPGA design by 1.43× for ResNet-20 inference.

Homomorphic Encryption (HE) enables secure computation on encrypted data, addressing privacy concerns in cloud computing. However, the high computational cost of HE operations, particularly matrix multiplication (MM), remains a major barrier to its practical deployment. Accelerating Homomorphic Encrypted MM (HE MM) is crucial for applications such as privacy-preserving machine learning. In this paper, we present a bandwidth-efficient FPGA implementation of HE MM. We first develop a cost model to evaluate the on-chip memory requirement for a given set of HE parameters and input matrix sizes. Our analysis shows that optimizing on-chip memory usage is critical for scalable and efficient HE MM. To this end, we design a novel datapath for Homomorphic Linear Transformation (HLT), the major bottleneck in HE MM. Our datapath significantly reduces off-chip memory traffic and on-chip memory demand by enabling fine-grained data reuse. Leveraging the proposed datapath, we introduce FAME, the first FPGA-based accelerator specifically tailored for HE MM. FAME supports arbitrary matrix shapes and is configurable for a wide range of HE parameter sets. We implement FAME on Alveo U280 and evaluate its performance over diverse matrix sizes and shapes. Experimental results show that FAME achieves an average of$221 \times$speedup over state-of-the-art CPU-based implementations, demonstrating its scalability and practicality for large-scale consecutive HE MM and real-world workloads.

Matricized Tensor Times Khatri-Rao Product (MTTKRP) is the computational bottleneck in sparse tensor decomposition. As real-world sparse tensors grow to billions of nonzeros, they increasingly demand higher memory capacity and compute throughput from hardware accelerators. In this work, we present AMPED, a multi-GPU parallel algorithm designed to accelerate MTTKRP on billion-scale sparse tensors. AMPED scales beyond the limits of a single GPU, meeting both the memory and performance requirements of large-scale workloads. We introduce a partitioning strategy combined with a dynamic load balancing scheme to distribute computation and minimize GPU idle time. On real-world billion-scale tensors, AMPED achieves a 5.1 × geometric mean speedup in total execution time over state-of-the-art GPU baselines using 4 GPUs on a single CPU node.

Heterophilous graphs, where dissimilar nodes tend to connect, pose a challenge for graph neural networks (GNNs). Increasing the GNN depth can expand the scope (i.e., receptive field), potentially finding homophily from the higher-order neighborhoods. However, GNNs suffer from performance degradation as depth increases. Despite having better expressivity, state-of-the-art deeper GNNs achieve only marginal improvements compared to their shallow variants. Through theoretical and empirical analysis, we systematically demonstrate a shift in GNN generalization preferences across nodes with different homophily levels as depth increases. This creates a disparity in generalization patterns between GNN models with varying depth. Based on these findings, we propose to improve deeper GNN generalization while maintaining high expressivity by Mixture of scope experts at test (Moscat). Experimental results show that Moscat works flexibly with various GNN architectures across a wide range of datasets while significantly improving accuracy.

Uncertainty quantification is essential for reliable federated graph learning, yet existing methods struggle with decentralized and heterogeneous data. In this work, we first extend Conformal Prediction (CP), a well-established method for uncertainty quantification, to federated graph learning, formalizing conditions for CP validity under partial exchangeability across distributed subgraphs. We prove that our approach maintains rigorous coverage guarantees even with client-specific data distributions. Building on this foundation, we address a key challenge in federated graph learning: missing neighbor information, which inflates CP set sizes and reduces efficiency. To mitigate this, we propose a variational autoencoder (VAE)-based architecture that reconstructs missing neighbors while preserving data privacy. Empirical evaluations on real-world datasets demonstrate the effectiveness of our method: our theoretically grounded federated training strategy reduces CP set sizes by 15.4%, with the VAE-based reconstruction providing an additional 4.9% improvement, all while maintaining rigorous coverage guarantees.

We examine an uplink cell-free (CF) massive multiple-input multiple-output (MIMO) system in which multiple-antenna access points (APs) are connected to a central processing unit (CPU) via unlimited capacity front-haul links, and each user equipment (UE) is equipped with a single antenna. In such a system, optimizing AP selection to maximize the sum spectral efficiency (SE) while meeting real-time communication requirements is challenging. To address this, we develop a novel approach using a heterogeneous graph neural network (HetGNN), which effectively captures the complex relationships between AP and UE nodes. Given the difficulty in obtaining ground truth for optimal AP selection, we employ an unsupervised HetGNN model that directly optimizes AP selection through its loss function. Simulation results demonstrate that our approach achieves an average improvement of at least 8% compared to existing methods and surpasses an offline approach using the Simulated Annealing method. Our approach also results in high fairness scores on Jain's Fairness Index; averaging greater than 0.845 per UE and exceeding 0.9 as the system scales. Our computation time analysis shows that the average inference time remains low and within acceptable limits for communication systems.

Synthetic Aperture Radar (SAR) Automatic Target Recognition (ATR) is a crucial technology in remote sensing. SAR devices, such as those on satellites like Sentinel-1A, collect SAR data for various applications. However, state-of-the-art CNN-based approaches for SAR ATR have high computational complexity. This makes them unsuitable for deployment on resource-limited platforms. In this paper, we present a novel model-architecture co-design for SAR ATR on Field Programmable Gate Arrays (FPGAs). Our proposed co-design consists of: (1) A novel multi-layer Graph Neural Network (GNN) model for SAR ATR with low computational complexity and a small number of parameters. (2) An optimized hardware architecture on FPGAs, ensuring low-latency, high-throughput, and energy-efficient execution of the GNN model. For model design, we leverage attention mechanisms to enhance classification accuracy. We then use knowledge distillation to train a simplified GNN model. This reduces computational cost while maintaining nearly the same accuracy. Additionally, we apply model pruning to further reduce computational complexity without compromising performance. To maximize computational parallelism, we introduce a customized hardware accelerator on FPGA. This accelerator uses the Scatter-Gather paradigm to efficiently manage the irregular computation and memory access patterns inherent to GNNs. For productivity, we develop parameterized hardware templates using High-level Synthesis (HLS) and create user-friendly Application Programming Interfaces (APIs). We deploy our accelerator design on both datacenter and embedded FPGAs. Specifically, we test it on Alveo U280, AMD/Xilinx PYNQ-Z1, and ZCU104, which are comparable to state-of-the-art space-grade FPGAs. We evaluate the proposed model on multiple datasets, including MSTAR, SynthWakeSAR, and GBSAR. Compared with the state-of-the-art models, the proposed GNN model achieves higher or comparable accuracy with substantially less computational complexity. Furthermore, compared with CPU and GPU implementations, our FPGA-based accelerators consistently deliver lower latency, improved throughput, and higher energy efficiency.

Memory performance bottlenecks the execution of graph applications, from traditional graph analytics (GA) to rapidly evolving graph neural networks (GNNs), due to the large size and complexity of graphs. While machine learning (ML) algorithms have shown potential in data prefetching to hide memory access latency, existing approaches face challenges with phase transitions and irregular memory access patterns in graph applications. To address these challenges, we introduce GraFetch, a specialized prefetching system for accelerating graph applications. GraFetch comprises of 1) a novel Hierarchical Hybrid Prefetching (HHP) framework that supports the cooperation of phase-specific ML predictors for high-complexity pattern prefetching and rule-based prefetchers for low-complexity pattern prefetching; and 2) Domain Specific Machine Learning (DSML) models integrated in the framework, which incorporate domain knowledge of graph applications to detect phases, recognize patterns, and predict memory accesses. We evaluate our approach using popular GA frameworks GPOP and X-Stream, and state-of-the-art GNN frameworks PyG and DGL. Our domain specific attention-based memory access predictors achieve 7.4% higher F1-score for delta (consecutive address jump) prediction and 15.35% higher accuracy@10 for page prediction compared with basic attention models. GraFetch achieves an average IPC improvement of 12.47% for GA and 4.18% for GNNs over a system with no prefetcher. This outperforms state-of-the-art rule-based prefetchers BO (7.12% for GA, 1.10% for GNNs), ISB (3.82% for GA, 1.60% for GNNs), and IMP (8.47% for GA, 2.20% for GNNs), as well as ML-based prefetchers Voyager (9.61% for GA, 3.14% for GNNs) and TransFetch (10.98% for GA, 2.48% for GNNs).

Temporal Graph Neural Networks (TGNNs) are powerful models to capture temporal, structural, and contextual information on temporal graphs, outperforming other methods in many high-impact downstream tasks. However, achieving high-performance TGNN inference in production environments is challenging because TGNN models suffer from high computation complexity and intrinsic temporal data dependency that hinders data parallelism. In addition, real-world TGNN applications have different latency and throughput requirements. This work presents ViTeGNN, a versatile TGNN inference solution for memory-based TGNNs on FPGAs. ViTeGNN performs algorithm-model-architecture co-design to meet the latency and throughput requirements of real-world TGNN applications. Besides the vanilla inference mode ViTeGNN-bal that updates embeddings for nodes interacting with others, we propose ViTeGNN-lat and ViTeGNN-thpt, optimized for latency and throughput. Our model optimizations include a lightweight method to compute attention scores and a related temporal neighbor pruning strategy to reduce computation and memory accesses. These are holistically coupled with key hardware optimizations that leverage the FPGA hardware. We propose a novel hardware module to execute the complex neighbor update process efficiently. To ensure similar accuracy vis-á-vis the original model, the simplified models are trained using the knowledge distillation technique. We propose a unified hardware design that supports all of these three inference modes without FPGA reconfiguration. Enabled by our flexible hardware architecture, we further propose ViTeGNN-auto, which automatically selects the best inference mode at runtime based on latency and throughput requirements, guided by our accurate performance model. We evaluate the performance of the proposed hardware accelerator on five real-world datasets. ViTeGNN-bal reduces the computation complexity by an average of 62% and memory accesses by an average of 36% with only 0.0042 accuracy loss. Compared with state-of-the-art implementations on CPU and GPU, our FPGA implementation achieves$53.9/26.0/16.1\times$speedup and$8.2/4.0/2.5\times$speedup for ViTeGNN-lat/-bal/-thpt, respectively.

Homomorphic Encryption (HE) is a promising technique for preserving user data privacy in cloud computing. Nevertheless, HE operations are magnitudes slower than un-encrypted computations due to their high computational complexity. FPGAs are attractive platforms for designing domain-specific accelerators. However, manually programming FPGAs for HE applications is nontrivial because of the vastly different parameter settings and latency requirements. To close the gap, we propose a framework to generate low latency FPGA accelerators for all the operations supported by HE, enabling users to utilize FPGA-accelerated HE processing without requiring knowledge of FPGA implementation details. The framework takes HE parameters and hardware resource constraints as input, uses design space exploration to automatically determine the design parameters that minimize HE computation latency, and produce synthesizable Verilog code. We propose a layered approach that decomposes HE operations into basic HE primitives, coupled with a parameterized HE domain-specific architecture that can efficiently execute the HE primitives. This approach avoids allocating dedicated FPGA resources to different subroutines within HE operations and improves compute utilization. Our evaluation shows that the generated accelerators significantly reduce latency in various HE operations, achieving up to$215\times$improvement over state-of-the-art CPU implementations. We demonstrate our framework's capability to compose end-to-end HE applications using HE CNN inference. Our designs outperform state-of-the-art CPU designs in latency by up to$60\times$.

Sparse Matricized Tensor Times Khatri-Rao Product (spMTTKRP) is the bottleneck kernel of sparse tensor decomposition. In this work, we propose a GPU-based algorithm design to address the key challenges in accelerating spMTTKRP computation, including (1) eliminating global atomic operations across GPU thread blocks, (2) avoiding the intermediate values being communicated between GPU thread blocks and GPU global memory, and (3) ensuring a balanced distribution of workloads across GPU thread blocks. Our approach also supports dynamic tensor remapping, enabling the above optimizations in all the modes of the input tensor. Our approach achieves a geometric mean speedup of 1.5×, 2.0×, and 21.7× in total execution time across widely used datasets compared with the state-of-the-art GPU implementations. Our work is the only GPU implementation that can support tensors with modes greater than 4 since the state-of-the-art works have implementation constraints for tensors with a large number of modes.

Vision Transformers (ViTs) have achieved state-of-the-art accuracy on various computer vision tasks. However, their high computational complexity prevents them from being applied to many real-world applications. Weight and token pruning methods are well-known in reducing ViT model complexity. However, naively combining and integrating both the methods results in irregular computation patterns leading to accuracy drops and difficulties in hardware acceleration. This limits the net complexity reduction offered by integrating such pruning methods. To address the above challenges, we propose a comprehensive algorithm-hardware codesign for accelerating ViT on FPGA through simultaneous pruning - combining static weight pruning and dynamic token pruning. For algorithm design, we systematically combine a hardware-aware structured block-pruning method for pruning model parameters and a dynamic token pruning method for removing unimportant token vectors. Moreover, we design a novel training algorithm to reduce the accuracy drop due to such simultaneous pruning. For hardware design, we develop a novel hardware accelerator for executing the pruned model. The proposed hardware design employs multi-level parallelism with a load-balancing strategy to efficiently deal with the irregular computation pattern presented by the two pruning approaches. Moreover, we develop an efficient hardware mechanism for executing the on-the-fly token pruning. We apply our codesign approach to the widely used DeiT-Small model. We implement the proposed accelerator on a state-of-the-art FPGA. The evaluation results show that the proposed algorithm reduces computation complexity by up to 3.4× with ≈ 3% accuracy drop and a model compression ratio of up to 1.6×. Compared with state-of-the-art implementation on CPU, GPU, and FPGA, our codesign on FPGA achieves an average latency reduction of 12.8×, 3.2×, and 0.7 – 2.1×, respectively.

Fully Homomorphic Encryption (FHE) plays an important role in privacy-preserving computation on the cloud. It allows computations on encrypted data without decryption. Bootstrapping is a fundamental operation in FHE, enabling an unlimited number of homomorphic encrypted computations, but at a significant time cost. A major bootstrapping component, the Homomorphic Encrypted Discrete Fourier Transform (HE DFT), is particularly time-consuming and requires the transfer of a large amount of data from external memory. In this paper, we propose a bandwidth-efficient FPGA implementation of HE DFT. We design a cost model to evaluate the on-chip memory requirement and the off-chip data transfer overhead for HE DFT. Our analysis shows that prior approaches can lead to significant off-chip data transfers, which process the entire ciphertext between subroutines. To address DRAM transfer overhead, we propose LimbFlow, an optimized dataflow approach for HE DFT that enhances fine-grained data reuse by rearranging the processing order of ciphertext and merging several subroutines. Leveraging the LimbFlow, we develop an FPGA-based accelerator tailored for HE DFT. We evaluate the accelerator on AMD U280 FPGA across various sets of security parameters. Our accelerator achieves up to 4.90 × and 1.98 × speedup compared with the State-Of-The-Art (SOTA) GPU and FPGA implementations.

Graph neural networks (GNNs) have recently em-powered various novel computer vision (CV) tasks. In GNN-based CV tasks, a combination of CNN layers and GNN layers or only GNN layers are employed. This paper introduces GCV-Turbo, a domain-specific accelerator on FPGA for end-to-end acceleration of GNN-based CV tasks. GCV-Turbo consists of two key components: (1) a novel hardware architecture optimized for the computation kernels in both CNNs and GNNs using the same set of computation resources. (2) a compiler that takes a user-defined model as input, performs end-to-end optimization for the computation graph of a given GNN-based CV task, and produces optimized code for hardware execution. The hardware architecture and the compiler work synergistically to support a variety of GNN-based CV tasks. We implement GCV-Turbo on a state-of-the-art FPGA and evaluate its performance across six representative GNN-based CV tasks with diverse input data modalities (e.g., image, human skeleton, point cloud). Compared with state-of-the-art CPU (GPU) implementations, GCV-Turbo achieves an average latency reduction of 68.4× (4.1x) on these six GNN-based CV tasks. Moreover, GCV-Turbo supports the execution of the standalone CNNs or GNNs, achieving performance comparable to that of state-of-the-art CNN (GNN) accelerators for widely used CNN-only (GNN-only) models.

Image classifiers for domain-specific tasks like Synthetic Aperture Radar Automatic Target Recognition (SAR ATR) and chest X-ray classification often rely on convolutional neural networks (CNNs). These networks, while powerful, experience high latency due to the number of operations they perform, which can be problematic in real-time applications. Many image classification models are designed to work with both RGB and grayscale datasets, but classifiers that operate solely on grayscale images are less common. Grayscale image classification has critical applications in fields such as medical imaging and SAR ATR. In response, we present a novel grayscale image classification approach using a vectorized view of images. By leveraging the lightweight nature of Multi-Layer Perceptrons (MLPs), we treat images as vectors, simplifying the problem to grayscale image classification. Our approach incorporates a single graph convolutional layer in a batch-wise manner, enhancing accuracy and reducing performance variance. Additionally, we develop a customized accelerator on FPGA for our model, incorporating several optimizations to improve performance. Experimental results on benchmark grayscale image datasets demonstrate the effectiveness of our approach, achieving significantly lower latency (up to $16 \times$ less on MSTAR) and competitive or superior performance compared to state-of-the-art models for SAR ATR and medical image classification.

Recently, Temporal Graph Neural Networks (TGNNs) have demonstrated state-of-the-art performance in various high-impact applications, including fraud detection and content recommendation. Despite the success of TGNNs, they are prone to the prevalent noise found in real-world dynamic graphs like time-deprecated links and skewed interaction distribution. The noise causes two critical issues that significantly compromise the accuracy of TGNNs: (1) models are supervised by inferior interactions, and (2) noisy input induces high variance in the aggregated messages. However, current TGNN denoising techniques do not consider the diverse and dynamic noise pattern of each node. In addition, they also suffer from the excessive mini-batch generation overheads caused by traversing more neighbors. We believe the remedy for fast and accurate TGNNs lies in temporal adaptive sampling. In this work, we propose TASER, the first adaptive sampling method for TGNNs optimized for accuracy, efficiency, and scalability. TASER adapts its mini-batch selection based on training dynamics and temporal neighbor selection based on the contextual, structural, and temporal properties of past interactions. To alleviate the bottleneck in mini-batch generation, TASER implements a pure GPU-based temporal neighbor finder and a dedicated GPU feature cache. We evaluate the performance of TASER using two state-of-the-art backbone TGNNs. On five popular datasets, TASER outperforms the corresponding baselines by an average of 2.3% in Mean Reciprocal Rank (MRR) while achieving an average of 5.1× speedup in training time.

Attention-based Neural Networks (NN) have demonstrated their effectiveness in accurate memory access prediction, an essential step in data prefetching. However, the substantial computational overheads associated with these models result in high inference latency, limiting their feasibility as practical prefetchers. To close the gap, we propose a new approach based on tabularization that significantly reduces model complexity and inference latency without sacrificing prediction accuracy. Our novel tabularization methodology takes input as a distilled, yet highly accurate attention-based model for memory access prediction and efficiently converts its expensive matrix multiplications into a hierarchy of fast table lookups. As an exemplar of the above approach, we develop DART, a prefetcher comprised of a simple hierarchy of tables. With a modest 0.09 drop in F1-score, DART reduces 99.99% of arithmetic operations from the original attention-based model and 91.83% from the distilled model. DART accelerates the large model inference by 170× and the distilled model by 9.4×. DART has comparable latency and storage costs as state-of-the-art rule-based prefetcher BO but surpasses it by 6.1% in IPC improvement. DART outperforms state-of-the-art NN-based prefetchers TransFetch by 33.1% and Voyager by 37.2% in terms of IPC improvement, primarily due to its low prefetching latency.

Temporal Graph Neural Networks (TGNNs) have emerged as powerful tools for modeling dynamic interactions across various domains. The design space of TGNNs is notably complex, given the unique challenges in runtime efficiency and scalability raised by the evolving nature of temporal graphs. We contend that many of the existing works on TGNN modeling inadequately explore the design space, leading to suboptimal designs. Viewing TGNN models through a performance-focused lens often obstructs a deeper understanding of the advantages and disadvantages of each technique. Specifically, benchmarking efforts inherently evaluate models in their original designs and implementations, resulting in unclear accuracy comparisons and misleading runtime. To address these shortcomings, we propose a practical comparative evaluation framework that performs a design space search across well-known TGNN modules based on a unified, optimized code implementation. Using our framework, we make the first efforts towards addressing three critical questions in TGNN design, spending over 10,000 GPU hours: (1) investigating the efficiency of TGNN module designs, (2) analyzing how the effectiveness of these modules correlates with dataset patterns, and (3) exploring the interplay between multiple modules. Key outcomes of this directed investigative approach include demonstrating that the most recent neighbor sampling and attention aggregator outperform uniform neighbor sampling and MLP-Mixer aggregator; Assessing static node memory as an effective node memory alternative, and showing that the choice between static or dynamic node memory should be based on the repetition patterns in the dataset. Our in-depth analysis of the interplay between TGNN modules and dataset patterns should provide a deeper insight into TGNN performance along with potential research directions for designing more general and effective TGNNs.

The emergence of diverse machine learning (ML) models has led to groundbreaking revolutions in computer vision (CV). These ML models include convolutional neural networks (CNNs), graph neural networks (GNNs), and vision transformers (ViTs). However, existing hardware accelerators designed for CV lack the versatility to support various ML models, potentially limiting their applicability to real-world scenarios. To address this limitation, we introduce VisionAGILE, a domain-specific accelerator designed to be versatile and capable of accommodating a range of ML models, including CNNs, GNNs, and ViTs. VisionAGILE comprises a compiler, a runtime system, and a hardware accelerator. For the hardware accelerator, we develop a novel unified architecture with a flexible data path and memory organization to support the computation primitives in various ML models. Regarding the compiler design, we develop a unified compilation workflow that maps various ML models to the proposed hardware accelerator. The runtime system executes dynamic sparsity exploitation to reduce inference latency and dynamic task scheduling for workload balance. The compiler, the runtime system, and the hardware accelerator work synergistically to support a variety of ML models in CV, enabling low-latency inference. We deploy the hardware accelerator on a state-of-the-art data center FPGA (Xilinx Alveo U250). We evaluate VisionAGILE on diverse ML models for CV, including CNNs, GNNs, hybrid models (comprising both CNN and GNN), and ViTs. The experimental results indicate that, compared with state-of-the-art CPU (GPU) implementations, VisionAGILE achieves a speedup of$81.7\times$($4.8\times$) in terms of latency. Evaluated on standalone CNNs, GNNs, and ViTs, VisionAGILE demonstrates comparable or higher performance with state-of-the-art CNN accelerators, GNN accelerators, and ViT accelerators, respectively.

Graph neural networks (GNNs) have gained significant attention across diverse areas due to their superior performance in learning graph representations. While GNNs exhibit superior performance compared to other methods, they are primarily designed for homogeneous graphs, where all nodes and edges are of the same type. Training a GNN model for large-scale graphs incurs high computation and storage costs, especially when considering the heterogeneous structural information of each node. To address the demand for efficient GNN training, various sampling methods have been proposed. In this paper, we propose a sampling method based on bandit sampling, an online learning algorithm with provable convergence under weak assumptions on the learning objective. To the best of our knowledge, this is the first bandit-based sampling method applied to heterogeneous GNNs with a theoretical guarantee. The main idea is to prioritize node types with more informative connections with respect to the learning objective. Compared with existing techniques for GNN training on heterogeneous graphs, extensive experiments using the Open Academic Graph (OAG) dataset demonstrate that our proposed method outperforms the state-of-the-art in terms of the runtime across various tasks with a speed-up of 1.5-2x, while achieving similar accuracy.

Multi-Agent Reinforcement Learning (MARL) has achieved significant success in large-scale AI systems and big-data applications such as smart grids, surveillance, etc. Existing advancements in MARL algorithms focus on improving the rewards obtained by introducing various mechanisms for inter-agent cooperation. However, these optimizations are usually compute- and memory-intensive, thus leading to suboptimal speed performance in end-to-end training time. In this work, we analyze the speed performance (i.e., latency-bounded throughput) as the key metric in MARL implementations. Specifically, we first introduce a taxonomy of MARL algorithms from an acceleration perspective categorized by (1) training scheme and (2) communication method. Using our taxonomy, we identify three state-of-the-art MARL algorithms - Multi-Agent Deep Deterministic Policy Gradient (MADDPG), Target-oriented Multi-agent Communication and Cooperation (ToM2C), and Networked Multi-Agent RL (NeurComm) - as target benchmark algorithms, and provide a systematic analysis of their performance bottlenecks on a homogeneous multi-core CPU platform. We justify the need for MARL latency-bounded throughput to be a key performance metric in future literature while also addressing opportunities for parallelization and acceleration.

Monte Carlo Tree Search (MCTS) is a widely used search technique in Artificial Intelligence (AI) applications. MCTS manages a dynamically evolving decision tree (i.e., one whose depth and height evolve at run-time) to guide an AI agent toward an optimal policy. In-tree operations are memory-bound leading to a critical performance bottleneck for large-scale parallel MCTS on general-purpose processors. CPU-FPGA accelerators can alleviate the memory bottleneck of in-tree operations. However, a major challenge for existing FPGA accelerators is the lack of dynamic memory management due to which they cannot efficiently support dynamically evolving MCTS trees. In this work, we address this challenge by proposing an MCTS acceleration framework that (1) incorporates an algorithm-hardware co-optimized accelerator design that supports in-tree operations on dynamically evolving trees without expensive hardware reconfiguration; (2) adopts a hybrid parallel execution model to fully exploit the compute power in a CPU-FPGA heterogeneous system; (3) supports Python-based programming API for easy integration of the proposed accelerator with RL domain-specific bench-marking libraries at run-time. We show that by using our framework, we achieve up to 6.8× speedup and superior scalability of parallel workers than state-of-the-art parallel MCTS on multi-core systems.

Sparse Matricized Tensor Times Khatri-Rao Product (spMTTKRP) is the most computationally intensive kernel in sparse tensor decomposition. In this paper, we propose a hardware-algorithm co-design on FPGA to minimize the execution time of spMTTKRP along all modes of an input tensor. We introduce FLYCOO, a novel tensor format that eliminates the communication of intermediate values to the FPGA external memory during the computation of spMTTKRP along all the modes. Our remapping of the tensor using FLYCOO also balances the workload among multiple Processing Engines (PEs). We propose a parallel algorithm that can concurrently process multiple partitions of the input tensor independent of each other. The proposed algorithm also orders the tensor dynamically during runtime to increase the data locality of the external memory accesses. We develop a custom FPGA accelerator design with (1) PEs consisting of a collection of pipelines that can concurrently process multiple elements of the input tensor and (2) memory controllers to exploit the spatial and temporal locality of the external memory accesses of the computation. Our work achieves a geometric mean of 8.8X and 3.8X speedup in execution time compared with the state-of-the-art CPU and GPU implementations on widely-used real-world sparse tensor datasets.

Homomorphic Encryption (HE) is a promising technique to guarantee the security and privacy of Machine Learning (ML) applications in the cloud. Rotation is a key operation in HE ML; however, the high computational complexity and memory bandwidth requirements severely limit its performance. This work proposes a low-latency HE rotation accelerator targeting HBM-enabled FPGAs. First, we identify memory inefficiencies due to the access patterns of various sub-routines in rotation. We propose a dynamic data layout technique that converts large stride memory accesses to unit stride accesses to improve the bandwidth utilization. We leverage this technique to develop an FPGA accelerator that supports rotation for various HE parameter settings. The accelerator utilizes an optimized dataflow and an architecture specially designed to perform the dynamic data layout. We evaluate the accelerator using AMD U280 FPGA. Our design achieves up to 2.1 x speedup compared with two commonly used static layout approaches and up to 1.47x speedup compared with state-of-the-art GPU implementation across various rotation benchmarks.

Sparse Matricized Tensor Times Khatri-Rao Prod-uct (spMTTKRP) is the most time-consuming compute kernel in sparse tensor decomposition. In this paper, we introduce a novel algorithm to minimize the execution time of spMTTKRP across all modes of an input tensor on multi-core CPU plat-form. The proposed algorithm leverages the FLYCOO tensor format to exploit data locality in external memory accesses. It effectively utilizes computational resources by enabling lock-free concurrent processing of independent partitions of the input tensor. The proposed partitioning ensures load balancing among CPU threads. Our dynamic tensor remapping technique leads to reduced communication overhead along all the modes. On widely used real-world tensors, our work achieves 2.12x - 9.01x speedup in total execution time across all modes compared with the state-of-the-art CPU implementations.

Memory performance is a key bottleneck in accelerating graph analytics. Existing Machine Learning (ML) prefetchers encounter challenges with phase transitions and irregular memory accesses in graph processing. We propose MPGraph, an ML-based Prefetcher for Graph analytics using domain specific models. MPGraph introduces three novel optimizations: soft detection of phase transitions, phase-specific multi-modality models for access delta and page predictions, and chain spatio-temporal prefetching (CSTP) for prefetch control.

An enhanced label propagation (LP) method called GraphHop was proposed recently. It outperforms graph convolutional networks (GCNs) in the semi-supervised node classification task on various networks. Although the performance of GraphHop was explained intuitively with joint node attribute and label signal smoothening, its rigorous mathematical treatment is lacking. In this paper, we propose a label efficient regularization and propagation (LERP) framework for graph node classification, and present an alternate optimization procedure for its solution. Furthermore, we show that GraphHop only offers an approximate solution to this framework and has two drawbacks. First, it includes all nodes in the classifier training without taking the reliability of pseudo-labeled nodes into account in the label update step. Second, it provides a rough approximation to the optimum of a subproblem in the label aggregation step. Based on the LERP framework, we propose a new method, named the LERP method, to solve these two shortcomings. LERP determines reliable pseudo-labels adaptively during the alternate optimization and provides a better approximation to the optimum with computational efficiency. Theoretical convergence of LERP is guaranteed. Extensive experiments are conducted to demonstrate the effectiveness and efficiency of LERP. That is, LERP outperforms all benchmarking methods, including GraphHop, consistently on five common test datasets, two large-scale networks, and an object recognition task at extremely low label rates (i.e., 1, 2, 4, 8, 16, and 20 labeled samples per class).

The increasing penetration of solar PhotoVoltaic (PV) panels in residential markets is leading to increasing solar generation hidden behind metering instruments of utility companies. Current metering infrastructure only measures the net load (sum of consumption and solar generation signals) from customers. However, it is desirable to observe solar generation separate from load consumption for grid optimizations. To enable that, we propose an unsupervised Behind-the-Meter (BTM) disaggregation model that utilizes a novel Consumer Mixture Model (CMM) for the modelling of consumption load in the disaggregation model. CMM uses consumption patterns of neighboring customers without PVs installed as features for modelling. We evaluate our model on an Australia dataset and use a load regression model and a state-of-the-art disaggregation model as baselines. We show that our model outperforms the baselines – the Mean Average Error of disaggregation results of our model was 28.37% lower than the state-of-the-art model. Additionally, we show that our model is agnostic to aggregation levels. This enables the utilities to focus on specific grid portions as needed.

Homomorphic encryption (HE) is a promising technique to ensure the security and privacy of applications in the cloud. Number Theoretic Transform (NTT) is a key operation in HE-based applications. HE requires vastly different NTT parameters to meet the performance and security requirements of applications. The increasing compute capabilities and flexibility of FPGAs make them attractive to accelerate NTT. However, programming FPGA still involves hardware design expertise and significant development effort. To close the gap, we propose NTTGen, a framework to automatically generate low latency NTT designs targeting HE-based applications. NTTGen takes application parameters, latency and hardware resource constraints as input, determines the design parameters, and produces synthesizable Verilog code as output. Low latency NTT implementations are obtained by varying the data, pipeline and batch parallelism. NTTGen utilizes streaming permutation network to reduce the interconnect complexity between stages in the NTT computation. The framework supports two types of NTT cores to perform modular arithmetic, the key computation in NTT: a low latency and resource efficient NTT core for a specific class of prime moduli and a general purpose NTT core for other primes. We further develop a design space exploration flow to identify the hardware design parameters of an optimal design. We evaluate NTTGen by generating designs for various NTT parameters. The designs result in up to 2.9X improvement in latency over the state-of-the-art FPGA implementations.

Machine learning algorithms have shown potential to improve prefetching performance by accurately predicting future memory accesses. Existing approaches are based on the modeling of text prediction, considering prefetching as a classification problem for sequence prediction. However, the vast and sparse memory address space leads to large vocabulary, which makes this modeling impractical. The number and order of outputs for multiple cache line prefetching are also fundamentally different from text prediction.

Homomorphic Encryption (HE) is a promising solution to the increasing concerns of privacy in machine learning. But HE-based CNN inference remains impractically slow. Pruning can significantly reduce the compute and memory footprint of CNNs. However, homomorphic encrypted Sparse Convolutional Neural Networks (SCNN) have vastly different compute and memory characteristics compared with unencrypted SCNN. Simply extending the design principles of existing SCNN accelerators may offset the potential acceleration offered by sparsity. To realize fast execution, we propose an FPGA accelerator to speedup the computation of linear layers, the main computational bottleneck in HE SCNN batch inference. First, we analyze the memory requirements of various linear layers in HE SCNN and discuss the unique challenges. Motivated by the analysis, we present a novel dataflow specially designed to optimize HE SCNN data reuse coupled with an efficient scheduling policy that minimizes on-chip SRAM access conflicts. Leveraging the proposed dataflow and scheduling algorithm, we demonstrate the first end-to-end acceleration of HE SCNN batch inference targeting CPU-FPGA heterogeneous platforms. For a batch of 8K images, our design achieves up to 5.6× speedup in inference latency compared with the CPU-only solution for widely studied 6-layer and 11-layer HE CNNs.

Homomorphic Encryption is a promising approach to perform secure inference on Machine Learning models such as CNNs by allowing cloud servers to perform computations on encrypted data directly. However, CNN inference over encrypted images has high computational complexity. Prior works propose accelerators for individual HE primitives on FPGAs. In this work, we focus on an integrated design for end-to-end acceleration of inference on encrypted data. We develop parameterized IP cores for HE primitives and CNN layers. To understand the tradeoffs between various parameters such as hardware resources and performance and optimize the overall performance, we develop a parameterized performance model to evaluate the resource consumption and latency of the complete design. The performance model allows design space exploration to identify the optimal architectural parameters of the accelerator for a given FPGA, CNN model, and security requirements. We implement our design on a Xilinx VU13P FPGA and compare its performance with software implementation on a state-of-the-art server with a multi-core CPU. Our implementation for a widely studied 8-layer CNN inference for a batch of 8K images achieves average inference time of 38.8 ms per image, which is 4.1× improvement over the software baseline on the state-of-the-art server.

Monte Carlo Tree Search (MCTS) methods have achieved great success in many Artificial Intelligence (AI) benchmarks. The in-tree operations become a critical performance bottleneck in realizing parallel MCTS on CPUs. In this work, we develop a scalable CPU-FPGA system for Tree-Parallel MCTS. We propose a novel decomposition and mapping of MCTS data structure and computation onto CPU and FPGA to reduce communication and coordination. High scalability of our system is achieved by encapsulating in-tree operations in an SRAM-based FPGA accelerator. To lower the high data access latency and inter-worker synchronization overheads, we develop several hardware optimizations. We show that by using our accelerator, we obtain up to 35× speedup for in-tree operations, and 3× higher overall system throughput. Our CPU-FPGA system also achieves superior scalability wrt number of parallel workers than state-of-the-art parallel MCTS implementations on CPU.

Synthetic aperture radar (SAR) automatic target recognition (ATR) is the key technique for remote-sensing image recognition. The state-of-the-art convolutional neural networks (CNNs) for SAR ATR suffer from high computation cost and large memory footprint, making them unsuitable to be deployed on resource-limited platforms, such as small/micro satellites. In this paper, we propose a comprehensive GNN-based model-architecture co-design on FPGA to address the above issues. Model design: we design a novel graph neural network (GNN) for SAR ATR. The proposed GNN model incorporates GraphSAGE layer operators and attention mechanism, achieving comparable accuracy as the state-of-the-art work with near 1/100 computation cost. Then, we propose a pruning approach including weight pruning and input pruning. While weight pruning through lasso regression reduces most parameters without accuracy drop, input pruning eliminates most input pixels with negligible accuracy drop. Architecture design: to fully unleash the computation parallelism within the proposed model, we develop a novel unified hardware architecture that can execute various computation kernels (feature aggregation, feature transformation, graph pooling). The proposed hardware design adopts the Scatter-Gather paradigm to efficiently handle the irregular computation patterns of various computation kernels. We deploy the proposed design on an embedded FPGA (AMD Xilinx ZCU104) and evaluate the performance using MSTAR dataset. Compared with the state-of-the-art CNNs, the proposed GNN achieves comparable accuracy with 1/3258 computation cost and 1/83 model size. Compared with the state-of-the-art CPU/GPU, our FPGA accelerator achieves 14.8×/2.5× speedup (latency) and is 62×/39× more energy efficient.

Homomorphic Encryption (HE) is a promising solution to the increasing concerns of privacy in Machine Learning (ML) as it enables computations directly on encrypted data. However, it imposes significant overhead on the compute system and remains impractically slow. Prior works have proposed efficient FPGA implementations of basic HE primitives such as number theoretic transform (NTT), key switching, etc. Composing the primitives together to realize higher level ML computation is still a challenge due to the large data transfer overhead. In this work, we propose an efficient FPGA implementation of HE Matrix Vector Multiplication$(\mathbf{M}\times \mathbf{V})$, a key kernel in HE-based Machine Learning applications. By analyzing the data reuse characteristics and the encryption overhead of HE$\mathbf{M}\times \mathbf{V}$, we show that simply using the principles of unencrypted$\mathbf{M}\times \mathbf{V}$to design accelerators for HE$\mathbf{M}\times \mathbf{V}$can lead to a significant amount of DRAM data transfers. We tackle the computation and data transfer challenges by proposing a bandwidth efficient dataflow that is specially optimized for HE$\mathbf{M}\times \mathbf{V}$. We identify highly reused data entities in HE$\mathbf{M}\times \mathbf{V}$and efficiently utilize the on-chip SRAM to reduce the DRAM data transfers. To speed up the computation of HE$\mathbf{M}\times \mathbf{V}$, we exploit three types of parallelism: partial sum parallelism, residual polynomial parallelism and coefficient parallelism. Leveraging these innovations, we demonstrate the first FPGA accelerator for HE matrix vector multiplication. Evaluation on 7 HE$\mathbf{M}\times \mathbf{V}$benchmarks shows that our FPGA accelerator is up to$3.8\times$(GeoMean$2.8\times$) faster compared to the 64-thread CPU implementation.

Prefix Scan is a versatile collective used in several classes of algorithms including sorting, lexical analysis, graph analytics, and regex matching. It is also a powerful tool to perform tree operations and load balancing. However, host-based Prefix Scan implementations incur high latency, large network traffic and poor scalability on large distributed systems.We explore in-network computation to accelerate Prefix Scan, using switches with data aggregation capabilities. We discuss the fundamental challenges associated with offloading Prefix Scan onto a network, and resolve them with innovations in dataflow topology and embedding methodology. We implement the proposed approach on the Intel PIUMA system. To the best of our knowledge, this is the first realization of a Prefix Scan offloading onto network switches.Our in-network Prefix Scan is highly scalable with less than 5μs latency on 16K PIUMA nodes and 6× lower latency than the host-based Prefix Scan. The performance benefits directly translate to improved workload scalability, as we demonstrate using a key bioinformatics application called Sequence Alignment.

Temporal Graph Neural Networks (TGNNs) are powerful models to capture temporal, structural, and contextual information on temporal graphs. The generated temporal node embeddings outperform other methods in many downstream tasks. Real-world applications require high performance inference on real-time streaming dynamic graphs. However, these models usually rely on complex attention mechanisms to capture relationships between temporal neighbors. In addition, maintaining vertex memory suffers from intrinsic temporal data dependency that hinders task-level parallelism, making it inefficient on general-purpose processors. In this work, we present a novel model-architecture co-design for inference in memory-based TGNNs on FPGAs. The key modeling optimizations we propose include a light-weight method to compute attention scores and a related temporal neighbor pruning strategy to further reduce computation and memory accesses. These are holistically coupled with key hardware optimizations that leverage FPGA hardware. We replace the temporal sampler with an on-chip FIFO based hardware sampler and the time encoder with a look-up-table. We train our simplified models using knowledge distillation to ensure similar accuracy vis-á-vis the original model. Taking advantage of the model optimizations, we propose a principled hardware architecture using batching, pipelining, and prefetching techniques to further improve the performance. We also propose a hardware mechanism to ensure the chronological vertex updating without sacrificing the computation parallelism. We evaluate the performance of the proposed hardware accelerator on three real-world datasets. The proposed model reduces the computation complexity by 84% and memory accesses by 67% with less than 0.33% accuracy loss. Compared with CPU/GPU, our FPGA accelerator achieves 16.4/2.3× speedup in latency and 0.27% improvement in accuracy compared with the state-of-the-art inference algorithm. To the best of our knowledge, this is the first work that performs model-architecture co-design on memory-based Temporal Graph Neural Networks.

Extreme scale graph analytics is imperative for several real-world Big Data applications with the underlying graph structure containing millions or billions of vertices and edges. Since such huge graphs cannot fit into the memory of a single computer, distributed processing of the graph is required. Several frameworks have been developed for performing graph processing on distributed systems. The frameworks focus primarily on choosing the right computation model and the partitioning scheme under the assumption that such design choices will automatically reduce the communication overheads. For any computational model and partitioning scheme, communication schemes — the data to be communicated and the virtual interconnection network among the nodes — have significant impact on the performance. To analyze this impact, in this work, we identify widely used communication schemes and estimate their performance. Analyzing the trade-offs between the number of compute nodes and communication costs of various schemes on a distributed platform by brute force experimentation can be prohibitively expensive. Thus, our performance estimation models provide an economic way to perform the analyses given the partitions and the communication scheme as input. We validate our model on a local HPC cluster as well as the cloud hosted NSF Chameleon cluster. Using our estimates as well as the actual measurements, we compare the communication schemes and provide conditions under which one scheme should be preferred over the others.

Data prefetching hides memory latency by predicting and loading necessary data into cache beforehand. Most prefetchers in the literature are efficient for specific memory address patterns thereby restricting their utility to specialized applications-they do not perform well on hybrid applications with multifarious access patterns. Therefore we propose ReSem-ble: a Reinforcement Learning (RL) based adaptive enSemble framework that enables multiple prefetchers to complement each other on hybrid applications. Our RL trained ensemble controller takes prefetch suggestions from all prefetchers as input, selects the best suggestion dynamically, and learns online toward getting higher cumulative rewards, which are collected from prefetch hits/misses. Our ensemble framework using a simple multilayer perceptron as the controller achieves on the average 85.27 % (accuracy) and 44.22 % (coverage), leading to 31.02 % IPC improvement, which outperforms state-of-the-art individual prefetchers by 8.35%-26.11 %, while also outperforming SBP, a state-of-the-art (non-RL) ensemble prefetcher by 5.69%.

Reinforcement Learning (RL) is a major branch of AI that enables agents to learn optimal decision making via interaction with the environment. Proximal Policy Optimization (PPO) is the state-of-the-art policy optimization based RL algorithm which achieves superior overall performance on various benchmarks. A PPO agent iteratively optimizes its policy - a function which chooses optimal actions approximated by a DNN, with each iteration consisting of two computationally intensive phases: Sample Generation - where agents inference on its policy and interact with the environment to collect data, and Model Update - where the policy is trained using the collected data. In this paper, we develop the first high-throughput PPO accelerator on CPU-FPGA heterogeneous platform. Our unified systolic-array based design accelerates both the inference and the training of the deep neural network used in a RL algorithm, and is generalizable to various MLP and CNN models across a wide range of RL applications. We develop novel optimizations to simultaneously reduce data access and computation latencies, specifically: (a) optimal data flow mapping to systolic array, (b) novel memory-blocked data layout to enable streaming stall-free data access in both forward and backward propagations, and, (c) a systolic array compute sharing technique to mitigate load imbalance in the training of two networks. We evaluate our design on widely used robotics and gaming benchmarks, achieving 1.4×–26× and 1.3×–2.7× improvements in throughput, respectively, when compared with state-of-the-art CPU/CPU-GPU implementations.

Temporal Knowledge Graphs store events in the form of subjects, relations, objects, and timestamps which are often represented by dynamic heterogeneous graphs. Event forecasting is a critical and challenging task in Temporal Knowledge Graph reasoning that predicts the subject or object of an event in the future. To obtain temporal embeddings multi-step away in the future, existing methods learn generative models that capture the joint distribution of the observed events. To reduce the high computation costs, these methods rely on unrealistic assumptions of independence and approximations in training and inference. In this work, we propose SeDyT, a discriminative framework that performs sequence modeling on the dynamic entity embeddings to solve the multi-step event forecasting problem. SeDyT consists of two components: a Temporal Graph Neural Network that generates dynamic entity embeddings in the past and a sequence model that predicts the entity embeddings in the future. Compared with the generative models, SeDyT does not rely on any heuristic-based probability model and has low computation complexity in both training and inference. SeDyT is compatible with most Temporal Graph Neural Networks and sequence models. We also design an efficient training method that trains the two components in one gradient descent propagation. We evaluate the performance of SeDyT on five popular datasets. By combining temporal Graph Neural Network models and sequence models, SeDyT achieves an average of 2.4% MRR improvement when not using the validation set and more than 10% MRR improvement when using the validation set.

Graph convolutional networks (GCNs) have revolutionized many big data applications, such as recommendation systems, traffic prediction, etc. However, accelerating GCN inference is challenging due to (1) massive external memory traffic and irregular memory access, (2) workload imbalance due to skewed degree distribution, and (3) intra-stage load imbalance caused by two heterogeneous computation phases of the algorithm. To address the above challenges, we propose a framework named BoostGCN to optimize GCN inference on FPGA. First, we develop a novel hardware-aware Partition-Centric Feature Aggregation (PCFA) scheme that leverages 3-D partitioning with the vertex-centric computing paradigm. This increases on-chip data reuse and reduces the total data communication volume with external memory. Second, we design a novel hardware architecture to enable pipelined execution of the two heterogeneous computation phases. We develop a low-overhead task scheduling strategy to reduce the pipeline stalls caused by the two computation phases. Third, we provide a complete GCN acceleration framework on FPGA with optimized RTL templates. It can generate hardware designs based on the customized configuration and is adaptable to various GCN models. Using our framework, we generate accelerators for various GCN models on a state-of-the-art FPGA platform and evaluate our designs using widely used datasets. Experimental results show that the accelerators produced by our framework achieve significant speedup compared with state-of-the-art implementations on CPU (≈ 100×), GPU (≈ 30×), prior FPGA accelerator (3-45)×.

Most of the existing work on FPGA acceleration of Convolutional Neural Network (CNN) focuses on employing a single strategy (algorithm, dataflow, etc.) across all the layers. Such an approach does not achieve optimal latency on complex and deep CNNs. Emerging CNNs have diverse per-layer computation characteristics including parallelism, arithmetic intensity, locality, and memory footprint. Per-layer strategy selection and fine-grained tuning are required to achieve low end-to-end latency. However, specialized hardware modules dedicated to each layer limit the per-layer utilization and adversely affect end-to-end latency. In this paper, we address these problems by an algorithm-architecture co-optimization framework, DYNAMAP, consisting of (1) a unified hardware overlay that can be reused across layers, supporting dynamic mapping of all three families of popular convolution algorithms, and further allowing flexible dataflow switching to maximize hardware utilization for each layer; (2) a novel software Design Space Exploration (DSE) flow that customizes the hardware overlay and chooses optimal strategy mapping. We show that the algorithm mapping space increases exponentially with network depth, and while the optimal algorithm selection problem is NP-hard in general, by exploiting the series-parallel structure of CNN models, we demonstrate a polynomial-time solution for optimal algorithm mapping. DYNAMAP is optimized for any CNN, including those having diverse computation and memory requirements across the layers. We demonstrate DYNAMAP using two state-of-the-art CNNs - GoogleNet and Inception-V4. The generated accelerators achieve up to 2.8x and 1.4x speedups, respectively, wrt inference latency compared with the state-of-the-art FPGA implementations.

Graph convolutional networks (GCNs) have revolutionized many big data applications. However, accelerating GCN inference is still challenging due to (1) massive external memory traffic and irregular memory access, (2) workload imbalance because of the skewed degree distribution, and (3) intra-stage load imbalance between feature aggregation and feature transformation steps. To address the above challenges, we propose a framework to optimize GCN inference on FPGA. First, we propose a novel Partition-Centric Feature Aggregation (PCFA) scheme to increase the data locality and reduce the number of random memory accesses in feature aggregation step. Second, we propose a novel hardware architecture to enable pipelined execution of the two heterogeneous computation steps. Then, a low-overhead task scheduling strategy is proposed to achieve stall-free execution of the two computation steps. Third, we provide a complete GCN acceleration framework on FPGA, and define key parameters for users to fine-tune the throughput. The model-specific operators can be customized to support a wide-range of GCN models. Using our framework, we design accelerators on a state-of-the-art FPGA. We evaluate our work using widely used datasets and. Experimental results show the accelerators produced by our framework achieve significant speedup compared with state-of-the-art implementations on CPU (≈100x), GPU (≈30x), and FPGA (4.5-32x).

Privacy of data is a critical concern when applying Machine Learning (ML) techniques to domains with sensitive data. Homomorphic Encryption (HE), by enabling computations on encrypted data, has emerged as a promising approach to perform inference on ML models such as Convolution Neural Network (CNN) in a privacy preserving manner. A significant portion of the total inference latency is in performing convolution over homomorphic encrypted data (HE-Convolution). For performing convolution over plaintext data, low latency accelerator designs have been proposed using algorithms such as im2col, frequency domain convolution, etc. However, developing accelerators for the HE versions of these algorithms is non-trivial. In this work, we develop a unified FPGA design that enables low latency execution of both im2col and frequency domain HE-Convolution. To enable selection of the efficient algorithm for each convolution layer of a CNN, we develop a performance model that takes the parameters about the encryption and convolution layer as input and outputs the computation and resource requirements of the two algorithms for that layer. We use the performance model to select convolution algorithm for each layer of ResNet-50 and obtain the first low latency batch-1 inference accelerator for CNN inference with HE-Convolution targeting FPGAs using HLS. We compare our design against prior techniques on CPUs and show that our accelerator achieves speedups in the range of $3.4\times\sim 6.7\times$ in latency.

Fractionally Strided Convolution (FSC) is a key operation in popular image-based Deep Learning models, for example, back propagation in CNN training, the decoding stage of convolutional auto-encoders and generative CNNs (GAN), etc. FSC typically performs up-convolution on a 2-D grid image, i.e., expands it to a larger one, as compared to conventional (down)-convolution, resulting in more complex computation patterns. Specifically, it introduces additional interleaved zero-spacing (i.e. insertion and padding of zeros) in feature maps that impose excessive computation and memory access overheads on traditional convolution methods such as im2col. The resulting hardware under-utilization is especially severe in layers with large kernels and large strides, commonly seen in typical CNNs and Generative CNNs. In this paper, we propose a methodology to address this challenge using a multi-channel-multi-kernel parallel algorithm, kn2row, to eliminate zero-computations in FSC. We further develop a unified accelerator for kn2row-based convolution and FSC operations in High-Level Synthesis (HLS). Benefiting from the compute-reduction of kn2row, we achieve up to 14.6x improvement in effective resource utilization in typical convolutional auto-decoding layers, GAN layers and backward pass of Nature-CNN, a reinforcement learning bench-marking model. These lead to overall speedup of up to 3.8x in the complete forward or backward propagation phases of the above benchmarks. Our methodology leads up to 8x speedup and 11x better power efficiency than general-purpose processors. Compared with existing GAN accelerators, our methodology achieves higher normalized throughput with high portability.

Task mapping is critical for the effective utilization of high performance computing systems. Recently, heterogeneous platforms consisting of CPUs, GPUs, FPGAs, and hardware accelerators have become popular. While there have been extensive studies to optimize task mapping, existing approaches have primarily focused on homogeneous platforms and rely on heuristics like greedy algorithms and do not effectively explore the search space. In this paper, we focus on a class of task mapping problems that captures heterogeneity in the application as well as in the target platform. We consider task mapping under a generalized computational setting where heterogeneous applications consisting of interdependent tasks with platform-dependent execution and communication parameters are to be mapped onto heterogeneous resource-limited execution platforms including CPUs, GPUs, FPGAs, and accelerators. This abstracts modern scientific workflows where computations proceed in an iterative fashion. We propose Pick-Best-Pair with Running Best (PRB) - a Monte Carlo Tree Search (MCTS) based approach to identify a task-hardware mapping for an input application. We formulate the task mapping problem as an integer linear programming problem and solve it using our PRB approach that conducts a series of LP relaxations with randomized rounding by leveraging exploration of long-term cumulative reward in terms of the total completion time, instead of a local optimal solution. We evaluate our approach by varying the number of stages, number of tasks per stage, and types of tasks, as well as resources with mixed types. Experimental results show that our proposed algorithm is effective in finding efficient mapping compared with classic approaches, such as the greedy heuristic and the randomized LP rounding. PRB achieves up to 20% improvement over greedy algorithm and 15% over LP relaxation with randomized rounding.

The use of massively parallel systems for application scaling has pushed the performance bottleneck towards data communication on the network. This is especially critical for allreduce collective that exhibits an all-to-all communication pattern. In this paper, we present an approach for developing performance optimized in-network allreduce on a multi-dimensional HyperX network. Specifically, we describe (a) novel architectural features to support network embeddings of logical topologies for in-network collective computation, and (b) a scalable methodology to realize a low latency allreduce embedding on a HyperX network equipped with the aforementioned hardware support. The proposed architecture further allows pipelined computation in network embeddings for high throughput allreduce. Our approach is employed in the Intel PIUMA system which features a HyperX interconnection network between the nodes. Since there is no physical installation of PIUMA yet, we use simulations to evaluate the performance of our in-network allreduce. It demonstrates excellent scalability with less than 1µ s latency for a single element allreduce on 16K nodes, and up to 40× reduction in latency compared to software implementation. In terms of throughput, in-network allreduce achieves 98% of the ideal bandwidth on a 16 node cluster, outperforming state-of-the-art software allreduce by 3.6×.

Even with generational improvements in DRAM technology, memory access latency still remains the major bottleneck for application accelerators, primarily due to limitations in memory interface IPs which cannot fully account for variations in target applications, the algorithms used, and accelerator architectures. Since developing memory controllers for different applications is time-consuming, this paper introduces a modular and programmable memory controller that can be configured for different target applications on available hardware resources. The proposed memory controller efficiently supports cache-line accesses along with bulk memory transfers. The user can configure the controller depending on the available logic resources on the FPGA, memory access pattern, and external memory specifications. The modular design supports various memory access optimization techniques including, request scheduling, internal caching, and direct memory access. These techniques contribute to reducing the overall latency while maintaining high sustained bandwidth. We implement the system on a state-of-the-art FPGA and evaluate its performance using two widely studied domains: graph analytics and deep learning workloads. We show improved overall memory access time up to 58% on CNN and GCN workloads compared with commercial memory controller IPs.

State-of-the-art Graph Neural Networks (GNNs) have limited scalability with respect to the graph and model sizes. On large graphs, increasing the model depth often means exponential expansion of the scope (i.e., receptive field). Beyond just a few layers, two fundamental challenges emerge: 1. degraded expressivity due to oversmoothing, and 2. expensive computation due to neighborhood explosion. We propose a design principle to decouple the depth and scope of GNNs – to generate representation of a target entity (i.e., a node or an edge), we first extract a localized subgraph as the bounded-size scope, and then apply a GNN of arbitrary depth on top of the subgraph. A properly extracted subgraph consists of a small number of critical neighbors, while excluding irrelevant ones. The GNN, no matter how deep it is, smooths the local neighborhood into informative representation rather than oversmoothing the global graph into “white noise”. Theoretically, decoupling improves the GNN expressive power from the perspectives of graph signal processing (GCN), function approximation (GraphSAGE) and topological learning (GIN). Empirically, on seven graphs (with up to 110M nodes) and six backbone GNN architectures, our design achieves significant accuracy improvement with orders of magnitude reduction in computation and hardware cost.

Graph Neural Networks (GNNs) are proven to be powerful models to generate node embedding for downstream applications. However, due to the high computation complexity of GNN inference, it is hard to deploy GNNs for large-scale or real-time applications. In this paper, we propose to accelerate GNN inference by pruning the dimensions in each layer with negligible accuracy loss. Our pruning framework uses a novel LASSO regression formulation for GNNs to identify feature dimensions (channels) that have high influence on the output activation. We identify two inference scenarios and design pruning schemes based on their computation and memory usage for each. To further reduce the inference complexity, we effectively store and reuse hidden features of visited nodes, which significantly reduces the number of supporting nodes needed to compute the target embedding. We evaluate the proposed method with the node classification problem on five popular datasets and a real-time spam detection application. We demonstrate that the pruned GNN models greatly reduce computation and memory usage with little accuracy loss. For full inference, the proposed method achieves an average of 3.27X speedup with only 0.002 drop in F1-Micro on GPU. For batched inference, the proposed method achieves an average of 6.67X speedup with only 0.003 drop in F1-Micro on CPU. To the best of our knowledge, we are the first to accelerate large scale real-time GNN inference through channel pruning.

Spectral-domain CNNs have been shown to be more efficient than traditional spatial CNNs in terms of reducing computation complexity. However they come with a 'kernel explosion' problem that, even after compression (pruning), imposes a high memory burden and off-chip bandwidth requirement for kernel access. This creates a performance gap between the potential acceleration offered by compression and actual FPGA implementation performance, especially for low-latency CNN inference. In this paper, we develop a principled approach to overcoming this performance gap and designing a low-latency, low-bandwidth, spectral sparse CNN accelerator on FPGAs. First, we analyze the bandwidth-storage tradeoff of sparse convolutional layers and locate communication bottlenecks. We then develop a dataflow for flexibly optimizing data reuse in different layers to minimize off-chip communication. Finally, we propose a novel scheduling algorithm to optimally schedule the on-chip memory access of multiple sparse kernels and minimize read conflicts. On a state-of-the-art FPGA platform, our design reduces data transfers by 42% with DSP utilization up to 90% and achieves inference latency of 9 ms for VGG16, compared to the baseline state-of-the-art latency of 68 ms.

Q-Table based Reinforcement Learning (QRL) is a class of widely used algorithms in AI that work by successively improving the estimates of Q values -- quality of state-action pairs, stored in a table. They significantly outperform Neural Network based techniques when the state space is tractable. Fast learning for AI applications in several domains (e.g. robotics), with tractable 'mid-sized' Q-tables, still necessitates performing substantial rapid updates. State-of-the-art FPGA implementations of QRL do not scale with the increasing Q-Table state space, thus are not efficient for such applications. In this work, we develop a novel FPGA implementation of QRL, scalable to large state spaces and facilitating a large class of AI applications. Our pipelined architecture provides higher throughput while using significantly fewer on-chip resources and thereby supports a variety of action selection policies that covers Q-Learning and variations of bandit algorithms. Possible dependencies caused by consecutive Q value updates are handled, allowing the design to process one Q-sample every clock cycle. Additionally, we provide the first known FPGA implementation of the SARSA (State-Action-Reward-State-Action) algorithm. We evaluate our architecture for Q-Learning and SARSA algorithms and show that our designs achieve a high throughput of up to 180 million Q samples per second.

Writing high-performance code requires significant expertise in the programming language, compiler optimizations, and hardware knowledge. This often leads to poor productivity and portability and is inconvenient for a non-programmer domain-specialist such as a Physicist. More desirable is a high-level language where the domain-specialist simply specifies the workload in terms of high-level operations (e.g., matrix-multiply(A, B)), and the compiler identifies the best implementation fully utilizing the heterogeneous platform. For creating a compiler that supports productivity, portability, and performance simultaneously, it is crucial to predict the performance of various available implementations (variants) of the dominant operations (kernels) contained in the workload on various hardware to decide (a) which variant should be chosen for each kernel in the workload, and (b) on which hardware resource the variant should run. To enable the performance prediction, we propose lightweight augmented neural networks for arbitrary combinations of kernel-variant-hardware. A key innovation is utilizing the mathematical complexity of the kernels as a feature to achieve higher accuracy. These models are compact to reduce training time and allow fast inference during compile-time and run-time. Using models with less than 75 parameters, and only 250 training data instances, we are able to obtain accurate performance predictions, significantly outperforming traditional feed-forward neural networks on 48 kernel-variant-hardware combinations. We further demonstrate that our variant-selection approach can be used in Halide implementations to obtain up to 1.7x speedup over Halide auto-scheduler.

Tip decomposition is a crucial kernel for mining dense subgraphs in bipartite networks, with applications in spam detection, analysis of affiliation networks etc. It creates a hierarchy of vertex-induced subgraphs with varying densities determined by the participation of vertices in butterflies (2, 2-bicliques). To build the hierarchy, existing algorithms iteratively follow a delete-update (peeling) process: deleting vertices with the minimum number of butterflies and correspondingly updating the butterfly count of their 2-hop neighbors. The need to explore 2-hop neighborhood renders tip-decomposition computationally very expensive. Furthermore, the inherent sequentiality in peeling only minimum butterfly vertices makes derived parallel algorithms prone to heavy synchronization. In this paper, we propose a novel parallel tip-decomposition algorithm - REfine CoarsE-grained Independent Tasks (RECEIPT) that relaxes the peeling order restrictions by partitioning the vertices into multiple independent subsets that can be concurrently peeled. This enables RECEIPT to simultaneously achieve a high degree of parallelism and dramatic reduction in synchronizations. Further, RECEIPT employs a hybrid peeling strategy along with other optimizations that drastically reduce the amount of wedge exploration and execution time. We perform detailed experimental evaluation of RECEIPT on a shared-memory multicore server. It can process some of the largest publicly available bipartite datasets orders of magnitude faster than the state-of-the-art algorithms - achieving up to 1100× and 64× reduction in the number of thread synchronizations and traversed wedges, respectively. Using 36 threads, RECEIPT can provide up to 17.1× self-relative speedup.

Matrix Factorization (MF) based on Stochastic Gradient Descent (SGD) is a powerful machine learning technique to derive hidden features of objects from observations. In this article, we design a highly parallel architecture based on Field-Programmable Gate Array (FPGA) to accelerate the training process of the SGD-based MF algorithm. We identify the challenges for the acceleration and propose novel algorithmic optimizations to overcome them. By transforming the SGD-based MF algorithm into a bipartite graph processing problem, we propose a 3-level hierarchical partitioning scheme that enables conflict-minimizing scheduling and processing of edges to achieve significant speedup. First, we develop a fast heuristic graph partitioning approach to partition the bipartite graph into induced subgraphs; this enables to efficiently use the on-chip memory resources of FPGA for data reuse and completely hide the data communication between FPGA and external memory. Second, we partition all the edges of each subgraph into non-overlapping matchings to extract the maximum parallelism. Third, we propose a batching algorithm to schedule the execution of the edges inside each matching to reduce the memory access conflicts to the on-chip RAMs of FPGA. Compared with non-optimized FPGA-based baseline designs, the proposed optimizations result in up to 60× data dependency reduction, 4.2× bank conflict reduction, and 15.4× speedup. We evaluate the performance of our design using a state-of-the-art FPGA device. Experimental results show that our FPGA accelerator sustains a high computing throughput of up to 217 billion floating-point operations per second (GFLOPS) for training very large real-life sparse matrices. Compared with highly-optimized GPU-based accelerators, our FPGA accelerator achieves up to 12.7× speedup. Based on our optimization methodology, we also implement a software-based design on a multi-core platform, which demonstrates 1.3× speedup compared with the state-of-the-art multi-core implementation.

To improve the reliability of content shared on social media, effective strategies for mitigating the diffusion of fake news are increasingly necessary. Traditionally, to counter false belief a competing cascade approach is used. This approach assumes that the opposite belief is already known, and thus, not applicable to newly spreading fake news. Another approach is to block nodes and links of the network to impede the flow of fake news (rumor/influence blocking). However, a more active way to battle the dissemination of fake news is to propagate the corresponding real news, since people who receive the real news in tandem with the fake news are less likely to believe in fake news. Such a setting is especially useful on a messaging platform such as WhatsApp, where the news item flows as a private message and the correction of fake news and its propagation must be performed by the users within the network as they receive it. To achieve this goal, we propose network-based recruitment for active fake news correction (RecANt) to find a set of individuals of a pre-defined size to be incentivized for actively fact-checking and passing on the real news so as to reach the maximum number of nodes in the network. These individuals should be such that they are likely to receive the fake news so that they can test its credibility, and when they propagate the corresponding real news, it reaches a large number of individuals. We prove that RecANt is NP-Hard with a monotone and submodular objective, leading to a polynomial time greedy algorithm (AFC) which provides a (1 - 1/e - ε)-approximation. We further optimize the runtime of AFC by developing a fast graph-pruning heuristic (RAFC) that performs as well as AFC in checking the spread of fake news while reducing the runtime significantly. Simulations on several networks demonstrate that our approach outperforms popular social network centrality measures and state-of-the-art information diffusion algorithm.

Graph sampling is an important tool to obtain small and manageable subgraphs from large real-world graphs. Prior research has shown that Induced Edge Sampling (IES) outperforms other sampling methods in terms of the quality of subgraph obtained. Even though fast sampling is crucial for several workflows, there has been little work on parallel sampling algorithms in the past.

Accurate prediction of crime incidents can assist the police in better planning of prevention strategies and scheduling deployment. The problem is often studied as a spatio-temporal regression problem approached by dividing the area of interest into a grid of uniform cells, and performing regression on timeseries of each cell. We propose that changing the method of division of the area can significantly improve crime prediction. We demonstrate this using a heterogeneous division of the area obtained by our partitioning algorithm that takes into account the density of crime. We further show that existing measures do not provide a fair comparison of two methods that partition the area in two different ways. To address this severe drawback in crime prediction evaluation, we propose a novel measure which is based on optimal allocation of resources relying on the prediction and then checking the actual number of crimes that would have been avoided by the allocation. Essentially, our measure answers the question of which model would have assisted in preventing most number of actual crimes if allocation were to be done using the predicted crimes. We also prove that a greedy algorithm results in the optimal allocation resources, thus making our evaluation computationally lightweight. Experiments on real-world datasets demonstrate that heterogeneous division of the area results in improved crime prediction while drastically decreasing the number of models to be trained compared to uniform grid division.

To accelerate inference of Convolutional Neural Networks (CNNs), various techniques have been proposed to reduce computation redundancy. Converting convolutional layers into frequency domain significantly reduces the computation complexity of the sliding window operations in space domain. On the other hand, weight pruning techniques address the redundancy in model parameters by converting dense convolutional kernels into sparse ones. To obtain high-throughput FPGA implementation, we propose spec - the first work to prune and accelerate spectral CNNs. First, we propose a systematic pruning algorithm based on Alternative Direction Method of Multipliers (ADMM). The offline pruning iteratively sets the majority of spectral weights to zero, without using any handcrafted heuristics. Then, we design an optimized pipeline architecture on FPGA that has efficient random access into the sparse kernels and exploits various dimensions of parallelism in convolutional layers. Overall, achieves high inference throughput with extremely low computation complexity and negligible accuracy degradation. We demonstrate by pruning and implementing LeNet and VGG16 on the Xilinx Virtex platform. After pruning 75% of the spectral weights, achieves 0% accuracy loss for LeNet, and <; 1% accuracy loss for VGG16. The resulting accelerators achieve up to 24× higher throughput, compared with the state-of-the-art FPGA implementations for VGG16.

The Graph Convolutional Network (GCN) model and its variants are powerful graph embedding tools for facilitating classification and clustering on graphs. However, a major challenge is to reduce the complexity of layered GCNs and make them parallelizable and scalable on very large graphs - state-of the art techniques are unable to achieve scalability without losing accuracy and efficiency. In this paper, we propose novel parallelization techniques for graph sampling-based GCNs that achieve superior scalable performance on very large graphs without compromising accuracy. Specifically, our GCN guarantees work-efficient training and produces order of magnitude savings in computation and communication. To scale GCN training on tightly-coupled shared memory systems, we develop parallelization strategies for the key steps in training: For the graph sampling step, we exploit parallelism within and across multiple sampling instances, and devise an efficient data structure for concurrent accesses that provides theoretical guarantee of near-linear speedup with number of processing units. For the feature propagation step within the sampled graph, we improve cache utilization and reduce DRAM communication by data partitioning. We prove that our partitioning strategy is a 2-approximation for minimizing the communication time compared to the optimal strategy. We demonstrate that our parallel graph embedding outperforms state-of-the-art methods in scalability (with respect to number of processors, graph size and GCN model size), efficiency and accuracy on several large datasets. On a 40-core Xeon platform, our parallel training achieves 64× speedup (with AVX) in the sampling step and 25× speedup in the feature propagation step, compared to the serial implementation, resulting in a net speedup of 21×. Our scalable algorithm enables deeper GCN, as demonstrated by 1306× speedup on a 3-layer GCN compared to Tensorflow implementation of state-of-the-art.

Graph analytics frameworks, typically based on Vertex-centric or Edge-centric paradigms suffer from poor cache utilization, irregular memory accesses, heavy use of synchronization primitives or theoretical inefficiency, that deteriorate overall performance and scalability. In this paper, we generalize the partition-centric PageRank computation approach [1] to develop a novel Graph Processing Over Partitions (GPOP) framework that enables cache-efficient, work-efficient and scalable implementations of several graph algorithms. For large graphs, we observe that GPOP is upto 19× and 6.1× faster than Ligra and GraphMat, respectively.

Hub labeling is widely used to improve the latency and throughput of Point-to-Point Shortest Distance (PPSD) queries in graph databases. However, constructing hub labeling, even via the state-of-the-art Pruned Landmark Labeling (PLL) algorithm is computationally intensive. PLL further has a sequential root order label dependency that makes it challenging to parallelize. Hence, the existing parallel approaches are often plagued by label size increase, poor scalability and inability to process large weighted graphs. In this paper, we develop novel algorithms that construct the minimal (guaranteed) Canonical Hub Labeling on shared and distributed-memory parallel systems in a scalable and efficient manner. Our key contribution, the PLaNT algorithm, provides an embarrassingly parallel approach for label construction that scales well beyond the limits of current practice. Our approach is the first to employ a collaborative label partitioning scheme across multiple nodes of a cluster, for completely in-memory labeling and parallel querying on massive graphs whose labels cannot fit on a single node. On a single node with 72-threads, our shared-memory algorithm is up to 47.4X faster than sequential PLL. While our labeling time is comparable to the state-of-the-art shared-memory paraPLL, our label size is 17% smaller on average. PLaNT demonstrates superior parallel scalability. It can process significantly larger graphs and construct labeling orders of magnitude faster than the state-of-the-art distributed paraPLL. Compared to the best shared-memory parallel algorithm, it achieves up to 9.5X speedup on a 64 node cluster.

This paper presents, HitGraph, an FPGA framework to accelerate graph processing based on the edge-centric paradigm. HitGraph takes in an edge-centric graph algorithm and hardware resource constraints, determines design parameters and then generates a Register Transfer Level (RTL) FPGA design. This makes accelerator design for various graph analytics transparent and user-friendly by masking internal details of the accelerator design process. HitGraph enables increased data reuse and parallelism through novel algorithmic optimizations, including (1) an optimized data layout that reduces non-sequential external memory accesses, (2) an efficient update merging and filtering scheme to reduce the data communication between the FPGA and external memory, and (3) a partition skipping scheme to reduce redundant edge traversals for non-stationary graph algorithms. Based on our design methodology, we accelerate Sparse Matrix Vector Multiplication (SpMV), PageRank (PR), Single Source Shortest Path (SSSP), and Weakly Connected Component (WCC). Experimental results show that HitGraph sustains a high throughput of 2076 Million Traversed Edges Per Second (MTEPS) for SpMV, 2225 MTEPS for PR, 2916 MTEPS for SSSP, and 3493 MTEPS for WCC, respectively. Compared with highly-optimized multi-core implementations, HitGraph achieves up to 37.9× speedup. Compared with state-of-the-art FPGA frameworks, HitGraph achieves up to 50.7× throughput improvement.

Interventions to reduce violence among homeless youth are difficult to implement due to the complex nature of violence. However, a peer-based intervention approach would likely be a worthy approach as it has been shown that individuals who interact with more violent individuals are more likely to be violent, suggesting a contagious nature of violence. We propose Uncertain Voter Model to represent the complex process of diffusion of violence over a social network, that captures uncertainties in links and time over which the diffusion of violence takes place. Assuming this model, we define Violence Minimization problem where the task is to select a predefined number of individuals for intervention so that the expected number of violent individuals in the network is minimized over a given time-frame. We extend the problem to a probabilistic setting, where the success probability of converting an individual into non-violent is a function of the number of “units” of intervention performed on them. We provide algorithms for finding the optimal intervention strategies for both scenarios. We demonstrate that our algorithms perform significantly better than interventions based on popular centrality measures in terms of reducing violence.

Many emerging real-world applications require fast processing of large-scale data represented in the form of graphs. In this paper, we design a Field-Programmable Gate Array (FPGA) framework to accelerate graph algorithms based on the edge-centric paradigm. Our design is flexible for accelerating general graph algorithms with various vertex attributes and update propagation functions, such as Sparse Matrix Vector Multiplication (SpMV), PageRank (PR), Single Source Shortest Path (SSSP), and Weakly Connected Component (WCC). The target platform consists of large external memory to store the graph data and FPGA to accelerate the processing. By taking an edge-centric graph algorithm and hardware resource constraints as inputs, our framework can determine the optimal design parameters and produce an optimized Register-Transfer Level (RTL) FPGA accelerator design. To improve data locality and increase parallelism, we partition the input graph into non-overlapping partitions. This enables our framework to efficiently buffer vertex data in the on-chip memory of FPGA and exploit both inter-partition and intra-partition parallelism. Further, we propose an optimized data layout to improve external memory performance and reduce data communication between FPGA and external memory. Based on our design methodology, we accelerate two fundamental graph algorithms for performance evaluation: Sparse Matrix Vector Multiplication (SpMV) and PageRank (PR). Experimental results show that our accelerators sustain a high throughput of up to 2250 Million Traversed Edges Per Second (MTEPS) and 2487 MTEPS for SpMV and PR, respectively. Compared with several highly-optimized multi-core designs, our FPGA framework achieves up to 20.5× speedup for SpMV, and 17.7× speedup for PR, respectively; compared with two state-of-the-art FPGA frameworks, our designs demonstrate up to 5.3× and 1.8× throughput improvement for SpMV and PR, respectively.

Sparse matrix factorization using Stochastic Gradient Descent (SGD) is a popular technique for deriving latent features from observations. SGD is widely used for Collaborative Filtering (CF), itself a well-known machine learning technique for recommender systems. In this paper, we develop an FPGA-based accelerator, FASTCF, to accelerate the SGD-based CF algorithm. FASTCF consists of parallel, pipelined processing units which concurrently process distinct user ratings by accessing a shared on-chip buffer. We design FASTCF through a holistic analysis of the specific design challenges for the acceleration of SGD-based CF on FPGA. Based on our analysis of these design challenges, we develop a bipartite graph processing approach with a novel 3-level hierarchical partitioning scheme that enables conflict-minimizing scheduling and processing of on-chip feature vector data to significantly accelerate the processing of this bipartite graph. First, we develop a fast heuristic to partition the input graph into induced subgraphs; this enables FASTCF to efficiently buffer vertex data for reuse and completely hide communication overhead. Second, we partition all the edges of each subgraph into matchings to extract the maximum parallelism. Third, we schedule the execution of the edges inside each matching to reduce concurrent memory access conflicts to the shared on-chip buffer. Compared with non-optimized baseline designs, the hierarchical partitioning approach results in up to 60x data dependency reduction, 4.2x bank conflict reduction, and 15.4x speedup. We implement FASTCF based on state-of-the-art FPGA and evaluate its performance using three large real-life datasets. Experimental results show that FASTCF sustains a high throughput of up to 217 billion floating-point operations per second (GFLOPS). Compared with state-of-the-art multi-core and GPU implementations, FASTCF demonstrates 13.3x and 12.7x speedup, respectively.

We consider bottleneck congestion games in an arbitrary graph G where player strategies are flows in G . The player's objective is to select a flow that minimizes the maximum load on any edge, that is, minimize the bottleneck congestion. We consider splittable and unsplittable games with pure strategies. It has been an open problem for many years to determine whether it is possible to compute in polynomial time Nash equilibriums for bottleneck congestion games in arbitrary graphs. For splittable games we provide a polynomial time algorithm to compute a Nash equilibrium which is also a global optimum. The unsplittable game problem is known to be PLS-complete, and so we focus on approximate Nash equilibria where players are approximately stable. For uniform player demands we give an algorithm to compute a O(łog m)-approximate unsplittable equilibrium in polynomial time, where m is the number of edges. For non-uniform player demands we give an algorithm to compute a O(ζ łog(ζ m))-approximate unsplittable equilibrium in polynomial time, where ζ = O(1 + łog (dmax /dmin)) and dmax, dmin are the respective maximum and minimum player demands. To our knowledge, these are the first general results for efficiently computing equilibria of pure bottleneck congestion games in arbitrary graphs, both for the splittable and unsplittable cases.

Mitigating supply-demand mismatch is critical for smooth power grid operation. Traditionally, load curtailment techniques such as demand response have been used for this purpose. However, these cannot be the only component of a net-load balancing framework for smart grids with high PV penetration. These grids sometimes exhibit supply surplus, causing overvoltages. Currently, these are mitigated using voltage manipulation techniques such as Volt-Var Optimizations, which are computationally expensive, thereby increasing the complexity of grid operations. Taking advantage of recent technological developments that enable rapid selective connection of PV modules of an installation to the grid, we develop a unified net-load balancing framework that performs both load and solar curtailment. We show that when the available curtailment values are discrete, this problem is NP-hard and we develop bounded approximation algorithms. Our algorithms produce fast solutions, given the tight timing constraints required for grid operation, while ensuring that practical constraints such as fairness, network capacity limits, and so forth are satisfied. We also develop an online algorithm that performs net-load balancing using only data available for the current interval. Using both theoretical analysis and practical evaluations, we show that our net-load balancing algorithms provide solutions that are close to optimal in a small amount of time.

Sparse graph processing generates highly irregular Memory Access Patterns (MAP) which lack locality and result in poor cache performance. In this paper, we propose a novel graph ordering algorithm that addresses this problem. We observe that existing reordering algorithms primarily try to improve cache line utilization by enhancing spatial locality. They are oblivious to cache data reuse which reflects the temporal locality that MAP can possess. Our premise is that peak efficiency can be achieved by a graph order for which the resulting MAP exhibit both spatial and temporal locality. Therefore, we first introduce a new metric Profit, that quantifies cache data reuse leading to a heuristic pH that enhances temporal locality in the MAP of graph algorithms. Then we define a notion of dynamically matching MAP with cache contents in a way that jointly maximizes both cache data reuse and cache line utilization. To perform this joint optimization, we develop a Block Reordering algorithm which utilizes pH to rearrange blocks of consecutive nodes with high spatial locality. We evaluate our algorithm using 8 real world datasets and 4 representative graph algorithms. Experimental results show that graphs obtained by Block Reordering can achieve upto 2.3× speedup over the original graph order and consistently outperform the existing state of the art reordering technique by 20% to 25% reduction in cache misses.

Subgraph isomorphism is a fundamental graph problem with many applications. Due to its NP-Hard nature, subgraph isomorphism in large dynamic graphs is considered as a challenging problem. In this paper, we present a distributed graph pruning algorithm (D-IDS) for dynamic graphs to enable efficient subgraph isomorphism. D-IDS continuously maintains the maximum dual simulation match in a dynamic graph. We develop D-ISI, a distributed incremental algorithm for subgraph isomorphism that utilizes D-IDS. We evaluated our algorithms on a commodity cluster in Amazon EC2 using real world graph datasets. Our evaluation results show that the graph pruning technique is highly effective on graphs with small diameter where it achieves over 60% reduction in graph size.

A classic optimization problem in network routing is to minimize C + D, where C is the maximum edge congestion and D is the maximum path length (also known as dilation). The problem of computing the optimal C* + D* is NP-complete even when either C* or D* is a small constant. We study routing games in general networks where each player i selfishly selects a path that minimizes Ci+ Dithe sum of congestion and dilation of the player's path. We first show that there are instances of this game without Nash equilibria. We then turn to the related quality of routing (QoR) games which always have Nash equilibria. QoR games represent networks with a small number of service classes where paths in different classes do not interfere with each other (with frequency or time division multiplexing). QoR games have O(log4n) price of anarchy when either C* or D* is a constant. Thus, Nash equilibria of QoR games give poly-log approximations to hard optimization problems.

Consider a parallel channel with M independent flat-fading subchannels. There exists a smart jammer which has possession of a copy of perfect channel state information (CSI) measured and sent back by a receiver to its transmitter. Under this model, a class of two-person zero-sum games is investigated where either achievable mutual information rate or Chernoff bound is taken as the underlying pay-off function with the strategy space of each player determined by respective power control and hopping functions. More specifically, we have tackled and answered the following three fundamental questions. The first one is about whether the transmitter and jammer should hop or fully use all degrees of freedom over the entire parallel channels given the full CSI available to both of them, i.e. to hop or not to hop. The second question is about the impact of sending back CSI on system performance considering that the smart jammer can exploit CSI to further enhance its interference effects, i.e. to feedback or not to feedback. The last question is about whether the amount of feedback information can be reduced given the mutual restrictions between transmitter and jammer, i.e. when to feedback and when not to.

In this paper, we provide a fundamental channel model to characterize the interference effect inherent in cognitive radio systems. Mutual information rates of our proposed probabilistic block interference channels for both primary and secondary users are derived without assuming that receivers have knowledge on channel interference states. Novel constrained optimization problems are then put forward with a constraint on the performance loss margin tolerated by the primary user. Furthermore, we investigate some special cases where conditions are provided to justify the optimality of adopting Neyman-Pearson rule. Also presented are some scenarios in which randomized decision without using sensing measurement is needed to balance the rateloss for PU and throughput gain for SD.

The high-frequency segment (10-66 GHz) of the IEEE 802.16 standard seems promising for the implementation of wireless backhaul networks carrying large volumes of Internet traffic. In contrast to wireline backbone networks, where channel errors seldom occur, the TCP protocol in IEEE 802.16 Worldwide Interoperability for Microwave Access networks is conditioned exclusively by wireless channel impairments rather than by congestion. This renders a cross-layer design approach between the transport and physical layers more appropriate during fading periods. In this paper, an adaptive coding and modulation (ACM) scheme for TCP throughput maximization is presented. In the current approach, Internet traffic is modulated and coded employing an adaptive scheme that is mathematically equivalent to the replicator dynamics model. The stability of the proposed ACM scheme is proven, and the dependence of the speed of convergence on various physical-layer parameters is investigated. It is also shown that convergence to the strategy that maximizes TCP throughput may be further accelerated by increasing the amount of information from the physical layer.

The 13 papers in this special issue focus on game theory. The aim of this issue is to bring together the state-of-the-art research contributions that address the fundamentals and sound theoretical models of game theory, and the major opportunities and challenges of applying game theory to solving real problems in industry, biology, medicine, communications, and other disciplines.

Failure detection (FD) is an important issue for supporting dependability in distributed healthcare systems to guarantee continuous, safe, secure, and dependable operation, and often is an important performance bottleneck in the event of node failure. FD can be used to manage the health status of communication for delivering telemedicine services, and then to help distributed healthcare system reduce fatal accident rate and increase the reliability and safety of systems. Ensuring acceptable quality of service (QoS) is made difficult by the relative unpredictability of the network environment. In this paper, first, we compare QoS metrics of several adaptive FDs, discuss their properties and their relation, and then propose one optimization over the existing methods, called tuning adaptive margin failure detector (TAM FD), which significantly improves QoS, especially in the aggressive range and when the network is unstable. Second, we address the problem of most adaptive schemes, namely their need for a large window of samples. So we also analyze the impact of memory size on the performance of FDs, and then prove that the presented scheme is designed to use a fixed and very limited amount of memory for the distributed system. Our experimental results over several kinds of networks (Cluster, WiFi, LAN, Intercontinental WAN) show that the properties of the existing adaptive failure detectors, and demonstrate that the optimization is reasonable and acceptable. Furthermore, the extensive experimental results show what is the effect of memory size on the overall QoS of each adaptive failure detector. For our TAM FD, the effect of window size on their QoS is very small and can be negligible.

Recent studies suggest that spectrum congestion is primarily due to inefficient spectrum usage rather than spectrum availability. Dynamic spectrum access (DSA) and cognitive radio (CR) are two techniques being considered to improve spectrum efficiency and utilization. The advent of CR has created a paradigm shift in wireless communications and instigated a change in FCC policy towards spectrum regulations. Within the hierarchical DSA model, spectrum overlay and underlay techniques are employed to enable primary and secondary users to coexist while improving overall spectrum efficiency. As employed here, spectrum overlay exploits unused (white) spectral regions while spectrum underlay exploits underused (gray) spectral regions. In general, underlay approaches use more spectrum than overlay approaches and operate below the noise floor of primary users. Spectrally modulated, spectrally encoded (SMSE) signals, to include orthogonal frequency domain multiplexing (OFDM) and multi-carrier code division multiple access (MC-CDMA), are candidate CR waveforms. The SMSE structure supports and is well suited for CR-based software defined radio (SDR) applications. This paper provides a general soft decision SMSE (SDSMSE) framework that extends the original SMSE framework to achieve synergistic CR benefits of overlay and underlay techniques. This extended framework provides considerable flexibility to design overlay, underlay and hybrid overlay/underlay waveforms that are scenario dependent. Overlay/underlay framework flexibility is demonstrated herein for a family of SMSE signals, including OFDM and MC-CDMA. Analytic derivation of CR error probability for overlay and underlay applications is presented. Simulated performance analysis of overlay, underlay and hybrid overlay/underlay waveforms is also presented and benefits discussed, to include improved spectrum efficiency and channel capacity maximization. Performance analysis of overlay/underlay CR waveform in fading channels will be discussed in Part II of the paper.

In this paper, we first provide a joint source and channel coding (JSCC) approach in estimating Gaussian sources over Gaussian MAC channels, as well as its sufficient and necessary condition in restoring Gaussian sources with a prescribed distortion value. An interesting relationship between our proposed joint approach with a more straightforward separate source and channel coding (SSCC) scheme is further established. We then formulate constrained power minimization problems to minimize total transmission power consumption under a distortion constraint for arbitrary in-homogeneous networks under JSCC, SSCC and uncoded scheme (UC). They are transformed to relaxed convex geometric programming problems. Our numerical results exhibit that none of the three schemes is consistently most energy efficient. The proposed JSCC could be more energy efficient than either the uncoded scheme, or SCCC, but not both. In addition, we prove that the optimal decoding order to minimize the total transmission powers for both source and channel coding parts is solely subject to the ordering of MAC channel qualities, and has nothing to do with the ranking of measurement qualities across measuring nodes.

The high frequency segment (10-66 GHz) of the IEEE 802.16 standard seems promising for the implementation of wireless backhaul networks carrying large volumes of Internet traffic. In contrast to wireline backbone networks, where channel errors seldom occur, routing decisions in IEEE 802.16 networks are conditioned by wireless channel impairments rather than by congestion, exclusively. This renders a cross-layer routing approach between the routing and the physical layers more appropriate during fading periods. In this paper, an adaptive cross-layer routing scheme is presented based on the selection of the most reliable path in terms of packet error ratio (unipath routing). The paper argues that routing Internet traffic through wireless backhaul networks is modeled more realistically employing evolutionary rather than conventional game theory. The stability of the proposed routing algorithm is proven and the dependence of the speed of convergence on various physical layer parameters is investigated. Is is also shown that convergence may be further accelerated by increasing the amount of information from the physical layer, specifically the physical separation between the alternative paths provided to the routing layer.

Relaying is often advocated for improving system performance by enhancing spatial diversity in wireless networks. In this paper, we address the issue of energy tradeoff made by relay nodes between transmitting their own data and forwarding other nodes' information in fading channels. We first propose a power control policy in a two-node relay network under which total energy consumption across both nodes is minimized while meeting both outage probability requirements. Based on this power control algorithm, we consider the problem of forming optimal partial coalitions of relays in an N node system subject to selfish constraints: A node participates in a relay pair (or chain) if and only if the energy cost of relaying is lower than the cost of direct transmission by the node to the destination itself. We develop a simple (1,2)-polynomial time bi-criteria approximation for this NP-hard problem. The energy cost provided by the approximation is at most that of the optimal relay pairing, while the constraints are violated by at most a factor of two. The running time of the approximation algorithm is polynomial, as it requires the solution of a relaxed linear programming instance of the original integer programming problem.

We formulate a Gaussian uncorrelated jamming problem in block fading channels under long term power constraints. Source aims at minimizing the outage probability of its transmission under the presence of a malicious jammer, while the jammer attempts to maximize the corresponding outage probability under its average power constraint. Optimal power control strategies for both source and jammer are obtained for minimax and maxmin problems, respectively, for any arbitrary finite number of blocks in block fading channels. Our results demonstrate the non-existence of Nash-equilibria of this two- person zero-sum game.

Relaying is often advocated for improving system performance by enhancing spatial diversity in wireless networks. Relay nodes make contributions to improving the source-destination link quality by sacrificing their own energy. In this paper, we address the issue of energy tradeoff made by relay nodes between transmitting their own data and forwarding other nodes' information in fading channels. Assuming channel state information (CSI) on fading amplitudes is perfectly known to both transmitters and receivers, we propose two power control and relaying policies. One is based on a strategic motivation, where each node functions as a relay and minimizes its own energy expenditure while meeting the outage probability requirement of all nodes. The second approach is based on complete collaboration, where the total energy consumption across all nodes is minimized. Numerical results demonstrate a significant impact of CSI on energy saving in relaying as compared with the relaying scheme without power control. In most cases, collaborative relaying dominates over the non-cooperative strategic one in the sense that the former not only minimizes total energy but also reduces individual energy expenditure of all nodes. This implies once forwarding and relaying is adopted across various nodes, exchanging of CSI becomes crucial, and collaborative energy minimization rather than the non-cooperative strategic approach should be pursued

Sensor nodes having limited and unreplenishable power resources. However the density of deployment is very high leading to a lot of redundancy. A lot of resources are wasted without the design of efficient algorithms. One of the approaches to saving energy is to turn off redundant nodes. In this paper, we propose an optimization problem which minimizes the total energy consumption by turning off redundant nodes while satisfying the condition that every point in the target area is covered. Then we prove that the optimization problem is NP-complete. We further propose three distributed greedy algorithms which utilize local energy and deployment information to turn off redundant nodes while still covering the whole sensing area. We test the effectiveness of our protocols by comparing our schemes with a random scheme proposed in earlier work [T. Yan et al, 2003]. Our schemes achieve significant gains in energy savings and also improve the half-life of the network. Inspite of the extra overhead associated with our schemes our proposed protocols have significantly better performance.

Sensor networks usually operate under very severe energy restrictions. Therefore, sensor communications should consume the minimum possible amount of energy. White broadcasting is a very energy-expensive protocol, it is also widely used as a building block for a variety of other network layer protocols. Therefore, reducing the energy consumption by optimizing broadcasting is a major improvement in sensor networking. In this paper, we propose an optimized broadcast protocol for sensor networks (BPS). The major novelty of BPS is its adaptive-geometric approach that enables considerable reduction of retransmissions by maximizing each hop length. BPS adapts itself and gets the best out of existing radio conditions. In BPS, nodes do not need any neighborhood information, which leads to low communication and memory overhead. We analyze the worst-case scenario for BPS and show that the number of transmissions in such a scenario is a constant multiple of those required in the ideal case. Our simulation results show that BPS is very scalable with respect to network density. BPS is also resilient to transmission errors.

The Benes network has been used as a rearrangeable network for over 40 years, yet the uniform N(2 log N-1) control complexity of the N/spl times/N Benes is not optimal for many permutations. In this paper, we present a novel O(log N) depth rearrangeable network, called KR-Benes, that is permutation-specific control-optimal The KR-Benes routes every permutation with the minimal control complexity specific to that permutation and its worst-case complexity for arbitrary permutations is bounded by the Benes; thus, it replaces the Benes when considering control complexity/latency. We design the KR-Benes by first constructing a restricted 2log K+2 depth rearrangeable network called K-Benes for routing K-bounded permutations with control 2N log K, 0/spl les/K/spl les/N/4. We then show that the N/spl times/N Benes network itself (with one additional stage) contains every KR-Benes network as a subgraph and use this property to construct the KR-Benes network. With regard to the control-optimality of the KR-Benes, we show that any optimal network for rearrangeably routing K-bounded permutations must have depth 2log K+2 and, therefore, the K-Benes (and, hence, the KR-Benes) is optimal.

The design of the IP protocol makes it difficult to reliably identify the originator of an IP packet making the defense against distributed denial of service attacks one of the hardest problems on the Internet today. Previous solutions for this problem try to traceback to the exact origin of the attack by requiring every router's participation. For many reasons this requirement is impractical and the victim ends up with an approximate location of the attacker. Reconstruction of the whole path is also very difficult owing to the sheer size of the Internet. This paper presents lightweight schemes for tracing back to the attack-originating AS instead to the exact origin itself. Once the attack-originating AS is determined, all further routers in the path to the attacker are within that AS and under the control of a single entity; which can presumably monitor local traffic in a more direct way than a generalized, Internet scale, packet marking scheme can. We also provide a scheme to prevent compromised routers from forging markings.

This paper presents a random asynchronous wakeup (RAW), a power saving technique for sensor networks that reduces energy consumption without significantly affecting the latency or connectivity of the network. RAW builds on the observation that when a region of a shared-channel wireless network has a sufficient density of nodes, only a small number of them need be active at any time to forward the traffic for active connections. RAW is a distributed, randomized algorithm where nodes make local decisions on whether to sleep, or to be active. Each node is awake for a randomly chosen fixed interval per time frame. High node density results in existence of several paths between two given nodes whose path length and delay characteristics are similar to the shortest path. Thus, a packet can be forwarded to any of several nodes in order to be delivered to the destination without affecting much the path length and delay experienced by the packet as compared to forwarding the packet through the shortest path. The improvement in system lifetime, due to RAW, increases as the ratio of idle-to-sleep energy consumption increases, and as the density of the network increases. Through analytical and experimental evaluations, we show that RAW improves communication latency and system lifetime compared to current schemes.

Path length, path reliability, and sensor energy-consumption are three major constraints affecting routing in resource constrained, unreliable wireless sensor networks. By considering the implicit collaborative imperative for sensors to achieve overall network objectives subject to individual resource consumption, we develop a game-theoretic model of reliable, length and energy-constrained, sensor-centric information routing in sensor networks. We define two distinct payoff (benefit) functions and show that computing optimally reliable energy-constrained paths is NP-Hard under both models for arbitrary sensor networks. We then show that optimal length-constrained paths can be computed in polynomial time in a distributed manner (using O(E) messages) for popular sensor network implementations using geographic routing. We also develop sensor-centric metrics called path weakness to measure the qualitative performance of different routing schemes and provide theoretical limits on the inapproximability of computing paths with bounded weakness. Heuristics for computing optimal paths in arbitrary sensor networks are described along with simulation results comparing performance with other routing algorithms.

Any reliable multicast protocol requires some recovery mechanism. A generic description of a recovery mechanism consists of a prioritized list of recovery servers/receivers (clients), hierarchically and/or geographically and/or randomly organized. Recovery requests are sent to the recovery clients on the list one-by-one until the recovery effort is successful. There are many recovery strategies available in literature fitting the generic description. We propose a polynomial time algorithm for choosing the recovery strategy with law recovery latency without sacrificing much bandwidth. We compared our method with two existing recovery methods, SRM (scalable reliable multicast) and RMA (reliable multicast architecture), by simulation and found that our method performs better. Although our theoretical analyses are based on a reliable network, our simulation results show that our strategy performs as well with the per link loss probability in a network up to 20% or more

Standard embedded sensor network models emphasize energy efficiency and distributed decision-making by considering untethered and unattended sensors. To this we add two constraints - the possibility of sensor failure and the fact that each sensor must tradeoff its own resource consumption with overall network objectives. In this paper, we develop an analytical model of data-centric information routing in sensor networks under all the above constraints. Unlike existing techniques, we use game theory to model intelligent sensors thereby making our approach sensor-centric. Sensors behave as rational players in an N-player routing game, where they tradeoff individual communication and other costs with network wide benefits. The outcome of the sensor behavior is a sequence of communication link establishments, resulting in routing paths from reporting to querying sensors. We show that the optimal routing architecture is the Nash equilibrium of the N-player routing game and that computing the optimal paths (which maximizes payoffs of the individual sensors) is NP-hard with and without data-aggregation. We develop a game-theoretic metric called path weakness to measure the qualitative performance of different routing mechanisms. This sensor-centric concept which is based on the contribution of individual sensors to the overall routing objective is used to define the quality of routing (QoR) paths. Simulation results are used to compare the QoR of different routing paths derived using various energy-constrained routing algorithms.

In this paper, we consider the problem of multicasting large files over a reliable network. In a reliable network, errors are transient and any change in the multicast tree is a rare occurrence. Further, the loss of a packet is correlated in the sense that a packet lost at a link will result in a loss to all downstream recipients. We propose to partition the recipients into static subgroups during the construction of the multicast tree. Whenever a NACK is received, the source retransmits the packet to all members of the subgroup from which the NACK came. This recovery method eliminates the overhead of joining/leaving subgroups associated with dynamic recovery schemes. This scheme reduces the NACK implosion by allowing all NACK from a subgroup to be merged in one NACK. We proposed an objective function to judge the merits of static subgroup-based recovery schemes. Further, we proved that computing the optimal subgroups is NP-hard. We provide an heuristic for computing subgroups with low cost of recovery and study its performance by simulation.

Given the increasing importance of optimal sensor deployment for battlefield strategists, the converse problem of reacting to a particular deployment by an enemy is equally significant and not yet addressed in a quantifiable manner in the literature. We address this issue by modeling a two stage game in which the opponent deploys sensors to cover a sensor field and we attempt to maximally reduce his coverage at minimal cost. In this context, we introduce the concept of minimal sensor integrity which measures Me vulnerability of any sensor deployment. We find the best response by quantifying the merits of each response. While the problem of optimally deploying sensors subject to coverage constraints is NP-complete, in this paper we show that the best response (i.e. the maximum vulnerability) can be computed in polynomial time for sensors with arbitrary coverage capabilities deployed over points in any dimensional space. In the special case when sensor coverages form an interval graph (as in a linear grid), we describe a better O(Min(M/sup 2/, NM)) dynamic programming algorithm.

In this paper we propose a deflection routing based N/spl times/N ATM multicast switch. The switch consists of a copy network, a routing network and a novel mechanism to reduce memory requirements. We analyze the switch performance and show that the switch requires only O(log N) stages for low packet loss rates. Our theoretical results are backed by simulations of the switch. The switch is output queued and allows the delivery of multiple packets to the same destination during a time slot.

We propose an efficient low cost multicast ATM switch which is fair to all inputs. The switch consists of a novel copy network followed by a routing network which ensures sequencing. Both the copy and routing networks are based on deflection routing. The switch requires O(log N) stages and can be designed for any arbitrarily low level of packet loss. Switching elements in both the copying and routing networks have O(1) bit complexity, making the overall bit level hardware complexity of the network O(N log N). The latency of the switch is proportional to the number of stages O(log N). Unlike other existing copy networks, our copy network drops packets in a fair manner and hence can provide QoS support. The switch is output queued and allows the delivery of multiple packets to the same destination during a time slot.

We propose and analyze the architecture for a large-scale high-speed multicast switch called MSXmin. The hardware complexity of MSXmin is O(N log/sup 2/ N) which compares favorably with existing architectures. Further, the internal latency of the MSXmin is O(log/sup 2/ N) bits. While it is superior to the existing architectures in terms of the hardware complexity and the internal latency, it is comparable to other multicast switches in terms of the header overhead and translation table complexity. MSXmin is output buffered and based on the group knockout principle. Moreover, MSXmin is a dual-bit-controlled tree-based switch.

We propose a pipelined optical sorting network to sort N w-bit inputs using O(wNlogN) single bit-controlled 2/spl times/2 switching elements. The network is compared to the standard Batcher (1968) sorter which requires (O(Nlog/sup 2/N)) two-input comparators for sorting N log N-bit words. However each comparator in the Batcher sorter has to perform a word comparison between two log N bit inputs, as opposed to single-bit controlled switching elements in the proposed scheme. An alternative implementation of the proposed network maintains the same hardware complexity while showing an O(loglogN) improvement in latency over the Batcher sorter. The proposed network is based on binary radix sort and utilizes a pair of self-routing reverse banyan networks to implement each step of the radix-sort algorithm. A distributed single-bit control scheme due to a particular non-blocking property of the reverse banyan network is used to route packets through each reverse banyan. Given the high cost of optical switches, the low hardware and control complexity of the network makes it easy to replace electronic switching elements with 2/spl times/2 lithium niobate directional couplers, thus making the network attractive for high-speed optical applications.

We propose STWnet, a self-routing high bandwidth optical network architecture for interconnecting users, grouped together as g groups with w users per group. STWnet uses the three dimensions of space, time, and wavelength by combining the advantages of space and temporal switching with the benefits of wavelength parallel data transmissions. Technologically difficult switching of individual wavelengths is avoided by prearranging transmissions in a way that they can be switched in a wavelength insensitive manner. Wavelengths are reused within the network thus allowing for a larger switching fabric. The proposed architecture can be internally expanded either in the spatial or temporal dimension to allow for multiple packets to be delivered to the same destination group. The expansion factor is determined based on the group knockout principle and given typical traffic patterns is a small number. STWnet allows easy group to group multicasting and broadcasting while system-wide multicasts and broadcasts can be achieved through repetitive group-to-group transmissions. The network uses readily available components such as opto-electronic directional couplers, fixed wavelength transmitters, and diffraction based parallel receivers while avoiding the use of relatively slow and expensive tunable components.

We propose SXmin: a self-routing, group-knockout principle based asynchronous transfer mode (ATM) packet switch which provides comparable delay-throughput performance and packet loss probabilities at significantly reduced hardware requirements compared to earlier switches. The M/spl times/N SXmin consists of an N/spl times/N Batcher sorter followed by log/sub 2/N-1 stages of sort-expander (SX) modules arranged in the form of a complete binary tree. Each SX module consists of a column of 2/spl times/2 switches with a wraparound-unshuffle input-output interconnection. This enables the hierarchical utilization of the group-knockout principle to expand the number of inputs by a small factor at each stage, resulting in a significant reduction in overall hardware complexity. Routing at each switch is controlled by a single bit. However, in case of contention, a dual bit resolution algorithm is used locally which drops excess packets in a predetermined manner while ensuring global randomness of packet loss over the entire switching network. There are no internal buffers at the individual stages and therefore the internal delay is constant and proportional to the number of stages. The use of simple hardware components and regular interconnections in the SX modules makes the network suitable for optical implementation.

The general time-space-time switching problem in telecommunications requires the use of multichannel time slot interchangers. We propose two multichannel time slot sorters which sort N/sup 2/ time-division multiplexed (TDM) optical inputs, arranged as N frames with N time slots per frame using O(Nlog/sup 2/N) optical switch elements. The TDM optical inputs are sorted in place without expanding the space-time fabric into a space-division switch. The hardware components used are 2/spl times/2 optical switches (LiNbO/sub 3/ directional couplers) and optical delay lines connected in a feedforward fashion. Two space-time variants of the spatial odd-even merge algorithm are used to design the sorters. By maintaining the number of shift-exchange operations invariant at each stage, the proposed sorters use fewer switches than previously proposed sorters using switches with feedback line delays. The use of local control at each 2/spl times/2 switch makes the proposed sorters more practical for high-speed optical inputs than Benes-based time slot permuters with global control and high latency, which affects interframe distance. Both time slot sorters support pipelining of input frames and sorted outputs are available at each time slot after an initial frame delay. The proposed sorters find practical application in the time-domain equivalents of space-division, nonblocking, self-routing packet switches using the sort-banyan architecture, such as the Starlite switch, Sunshine switch, etc.