Video Large Language Models (VideoLLMs) are increasingly deployed on numerous critical applications, where users rely on auto-generated summaries while casually skimming the video stream. We show that this interaction hides a critical safety gap: if harmful content is embedded in a video, either as full-frame inserts or as small corner patches, state-of-the-art VideoLLMs rarely mention the harmful content in the output, despite its clear visibility to human viewers. A root-cause analysis reveals three compounding design flaws: (1) insufficient temporal coverage resulting from the sparse, uniformly spaced frame sampling used by most leading VideoLLMs, (2) spatial information loss introduced by aggressive token downsampling within sampled frames, and (3) encoder-decoder disconnection, whereby visual cues are only weakly utilized during text generation. Leveraging these insights, we craft three zero-query black-box attacks, aligning with these flaws in the processing pipeline. Our large-scale evaluation across five leading VideoLLMs shows that the harmfulness omission rate exceeds 90\% in most cases. Even when harmful content is clearly present in all frames, these models consistently fail to identify it. These results underscore a fundamental vulnerability in current VideoLLMs' designs and highlight the urgent need for sampling strategies, token compression, and decoding mechanisms that guarantee semantic coverage rather than speed alone.

Binary analysis plays a critical role in software comprehension and security analysis, especially when source code is unavailable or difficult to analyze. Lifting binaries to LLVM IR enables reuse of the rich LLVM toolchain for downstream binary analyses. However, existing binary lifters often fail to produce syntactically valid LLVM IR or to restore sufficient semantics, making downstream analyses unreliable or unfeasible. This paper introduces BIT, a novel binary lifter designed to ensure syntactic compliance as well as semantic adequacy BIT achieves this through a multistage approach that includes anchor variable identification, analysis context collection, and IR refinement. In the evaluation, BIT achieved excellent results across multiple downstream analyses when compared with various lifters In static analysis, the F1 score of bug detection is 0.85, which is better than Plankton’s 0.81; in symbolic execution, it outperforms McSema by 3,049× in path exploration and by 1.36× in test case generation, respectively; in reanalysis, BIT can complete all tasks and is consistent with the advanced work McSema. These results highlight BIT’s ability to bridge the gap between binary-level analysis and the LLVM toolchain.

Recent GPUs integrate specialized hardware for low-precision arithmetic (e.g., FP16, INT8), offering substantial speedups for tensor operations. However, existing methods typically rely on coarse, operator-level trial-and-error tuning, which restricts the performance–accuracy trade-off space and limits achievable gains.We present Platensor, a progressive low-precision approximation framework that expands this trade-off space through ne-grained, tile-level strategies. The key idea is to exploit the tiled computation patterns of GPUs to enable flexible precision control and richer optimization opportunities. Platensor performs a two-phase exploration: a fast rule-based pass that selects promising tile-level configurations, followed by an evolutionary search that refines them. It then automatically generates optimized kernels that combine tiles of different precisions.Experiments on GEMM operators and representative applications—including kNN, LLMs, and HPL-MxP—show that Platensor significantly broadens the attainable performance– accuracy trade-offs and more fully leverages low-precision arithmetic on modern GPUs compared to operator-level tuning.

Transformer-based language models power many cloud services, but inference on sensitive data raises confidentiality concerns. Fully Homomorphic Encryption (FHE) enables computation on encrypted inputs while preserving privacy, but at high computational cost, making Transformers difficult to deploy. This paper presents PriTran, an efficient CKKS-based library for privacy-preserving Transformer inference on CPUs. Complementing the only prior work, RoLe, which supports only Berttiny(2 encoders), PriTran introduces two novel algorithms with optimized data layouts that accelerate ciphertext–plaintext (CP) and ciphertext–ciphertext (CC) matrix multiplications (MMs) across all Bert models by reducing costly rotations and multiplications. On the MNLI dataset, RoLe fails on inputs longer than 36 tokens within a 5-hour per-token budget, while PriTran achieves average speedups of 29.3% and 22.2% for CP- and CC-MMs, respectively, and 24.1% end-to-end. We further evaluate PriTran on scaled Berttinyvariants with additional encoders and on Bertmini(4 encoders), demonstrating correctness and scalability beyond RoLe’s limits. Within current FHE limits, these gains and RoLe’s failure on longer inputs underscore PriTran’s promise as a practical approach for FHE-based Transformer inference.

Dynamic-shape DNNs are widely used in applications such as variable-resolution image processing and language modeling with variable-length sequences. Existing DL (Deep-Learning) compilers apply rule-based rewriting to either transform a subgraph into a fixed variant at compile time (leading to suboptimal performance) or generate multiple variants at runtime, incurring significant overhead. The challenge is discovering and applying shape-dependent subgraph variants that maintain high efficiency across diverse inputs with minimal runtime cost.We propose DyPARS, a dynamic-shape DL compiler approach that discovers high-performance subgraph variants at compile time and applies the best ones at runtime. Leveraging Pareto-aware MCTS, DyPARS identifies shape-aware variants, incorporating shape-dependent kernel adaptations. These variants are integrated into a prediction-enhanced computational graph, enabling efficient variant selection based on input shapes with minimal overhead. DyPARS achieves average speedups of 1.31× and 1.80× over TorchInductor (JIT) and BladeDISC (non-JIT), respectively, across five DNN models, demonstrating robust efficiency across diverse inputs.

Operator fusion is essential for accelerating FHE-based DNN inference because it reduces multiplicative depth and, in turn, lowers the cost of ciphertext operations by keeping them at lower ciphertext levels. Existing approaches either rely on manual optimizations, which miss cross-operator opportunities, or on compiler pattern matching, which lacks generality. Standard DNN graphs omit FHE-specific behaviors, while fully lowering to primitive FHE operations introduces excessive granularity and obstructs effective optimization.We present FHEFusion, a compiler framework for the CKKS scheme that enables fusion through a new IR. This IR preserves high-level DNN semantics while introducing FHE-aware operators—masking and compaction (Strided_Slice)—that are central to CKKS, thereby exposing broader fusion opportunities. Guided by algebraic rules and an FHE-aware cost model, FHEFusion reduces multiplicative depth and identifies profitable fusions. Integrated into ANT-ACE, a state-of-the-art FHE compiler, FHEFusion outperforms NGRAPH, the only framework with graph-level fusion, achieving up to 3.02× (average 1.40×) speedup across seven DNNs (13 variants from different RELU approximations) on CPUs, while maintaining inference accuracy.

Python dominates AI development and is the most widely used dynamic programming language, but synthesizing its polymorphic functions into hardware remains challenging. Existing HLS solutions support only static subsets of Python, forcing CPU offload with costly communication overhead. We present Pyls, the first framework that synthesizes dynamically polymorphic Python into monolithic hardware via Left-Child Right-Sibling (LCRS) encoding. Key to our approach is representing all Python objects as LCRS trees, enabling uniform hardware handling of dynamic types. Pyls automatically converts objects to fixed-width formats, generates XLS IR designs, and implements a tree memory architecture for efficient runtime type resolution. On FPGA platforms, Pyls demonstrates speedups of 5.19× and 3.98× over two ASIC CPUs, 303.29× over a soft-core processor, and 282.66× over a heterogeneous SoC design.

Pointer analysis for Rust faces unique challenges arising from its ownership-based memory model and layered abstractions, which complicate how heap-allocated objects flow across functions. Existing k-limited callsite abstractions - designed for earlier languages - are both imprecise and inefficient on large Rust programs. We present Rceus, a Rust-oriented pointer-analysis technique that mitigates points-to set explosion and resource exhaustion caused by cross-function pointer conflation under deep heap encapsulation, a scalability bottleneck that conventional k-limiting cannot address. Rceus performs a fast, coarse-grained pointer-flow pre-analysis to identify precision-critical functions and the essential callsites within their calling contexts. This selective context construction distinguishes parameter-derived flows while avoiding unnecessary expansion. As a result, Rceus cleanly partitions intertwined pointer flows, eliminating context explosion and improving both scalability and precision. On 16 real-world Rust applications, Rceus outperforms state-of-the-art techniques - standard k-limiting, selective k-limiting for Java, and stack-filtered k-limiting for Rust - in both precision and efficiency. The evaluation includes Wasmtime, a WebAssembly runtime with 669K lines of code, where the benefits increase with program size. Rceus also composes with existing techniques, providing a practical and extensible foundation for scalable, precise Rust pointer analysis.

IFDS taint analysis is inherently context- and flow-sensitive, allowing precise encoding of field sensitivity in access-path generation. However, preserving this level of precision in practice is difficult, leading to over-tainting - marking more data facts as tainted than necessary. The root cause is the undecidability of solving two context-free language reachability (CFL-reachability) problems along the same dataflow path, which forces k-limiting as an over-approximation of field sensitivity. Consequently, spurious access paths are introduced, increasing analysis time, memory usage, and false positives, especially in large-scale applications. To address this challenge, we present TnFix, a CFL-reachability-based technique for mitigating over-tainting in IFDS taint analysis. The key insight is that the field sequence of any candidate tainted access path can be checked by a deterministic finite automaton (DFA) that accepts feasible sequences of field accesses. TnFix builds these DFAs by first solving a lightweight field-sensitive CFL-reachability problem to construct a Field Points-to Graph (FPG) that integrates data flows from taint sources and library summaries, and then converting the FPG into per-object DFAs. During taint analysis, TnFix queries these DFAs to prune access paths whose field sequences are rejected, eliminating the spurious paths introduced by k-limiting and improving precision without sacrificing scalability. In a comparative evaluation against FlowDroid on a set of 36 widely used Android apps for taint analysis, TnFix successfully analyzes 7 apps that FlowDroid cannot complete within a three-hour time budget. For the remaining 29 apps, it improves analysis speed by an average of 2.5× and reduces false positives by an average of 12.2%. TnFix thus establishes the first CFL-based optimization framework for reducing over-tainting in IFDS taint analysis, delivering substantial gains in both efficiency and precision for practical use.

Graph pattern mining is essential for analyzing dynamic networks, where graphs evolve over time. To accommodate these changes, existing solutions update match sets incrementally, avoiding the need to re-mine the entire graph and achieving significant performance improvements. However, these methods suffer from inefficiencies due to redundant set intersection operations across subgraph instances, causing performance degradation.

Transformer-based large language models (LLMs) exhibit remarkable generative capabilities, but their inference throughput is limited by the autoregressive decoding process, which generates only one token per iteration. Speculative decoding mitigates this bottleneck by using a lightweight draft language model (DLM) to generate multiple draft tokens, which are then verified in parallel by a more accurate target language model (TLM). To accommodate the differing computational patterns of the DLM and TLM, prior work has leveraged heterogeneous systems combining xPUs and processing-in-memory (PIM) units to offload compute- and memory-intensive operators, respectively. However, existing systems often adopt a fixed draft sequence length, leading to excessive rejection of draft tokens during verification-especially under large-batch scenarios-resulting in redundant computation and reduced efficiency. This paper proposes a runtime adaptive draft length adjustment technique that dynamically tailors the draft length for each request by monitoring cumulative acceptance probabilities, thereby minimizing the generation and verification of invalid tokens. Yet, integrating adaptive draft lengths into existing PIM-enabled heterogeneous systems introduces two new challenges: (1) sequential execution of the DLM and TLM becomes inefficient due to synchronization bubbles caused by request-wise variability in draft lengths, and (2) static operator mappings become suboptimal as draft length variability alters operator arithmetic intensities dynamically. To address these issues, we introduce SADDLE, a PIM-enabled heterogeneous system designed to exploit adaptive draft lengths effectively. SADDLE incorporates two key mechanisms: (1) an asynchronous speculative decoding pipeline that decouples DLM prediction and TLM verification to reduce idle time, and (2) an arithmetic intensity-aware operator scheduler that dynamically assigns operators to the most suitable hardware units. Experimental results show that SADDLE achieves average speedups of$\mathbf{2. 8 8} \times$over a state-of-the-art GPU-only solution and$\mathbf{1. 7 1} \times$over the best-performing GPU+PIM baseline.

Taint analysis, widely used for bug and vulnerability detection, is typically formulated as a flow- and context-sensitive IFDS analysis. To achieve field sensitivity, IFDS models heap locations as k-limited access paths but suffers from cubic time and quadratic space complexity, leading to prohibitive costs under realistic memory budgets and frequent out-of-memory failures or timeouts. Existing improvements target scalability or precision under abundant memory but remain fragile under constrained resources. We present ReFine, an iterative restart-and-refinement framework that enables scalable IFDS taint analysis across diverse memory budgets. When memory is exhausted, ReFine reuses partial results from terminated runs as sound under-approximations to guide subsequent iterations. Each restart occurs at a partial-analysis point, where results are abstracted and refined by leveraging that taint propagation is monotonic under field extension—allowing longer access paths to be safely summarized by their prefixes. We formalize this process as a fixpoint computation over product semilattices and prove soundness, correctness, and termination. Evaluated on 31 real-world Android apps against a state-of-the-art IFDS taint analysis, ReFine wraps it in a restart-and-refinement framework, analyzing 5.0x more apps under 16 GB and 2.4x more under 800 GB, with up to 52.5x speedup. By turning partial analyses into progressive refinement, ReFine delivers sound, precise, and highly scalable IFDS taint analysis across diverse memory budgets.

As build systems and their scripts grow in size and complexity, detecting bugs in build configurations becomes increasingly challenging due to the rich functionality and weak typing of build scripting languages. This paper introduces CM ake S onar , the first static approach to precisely identifying semantic bugs in CMake scripts. CM ake S onar addresses this challenge by (1) designing a fine-grained type system that captures the runtime semantics of CMake values, and (2) performing a flow-sensitive analysis that detects inconsistent and ill-typed value usages by solving type constraints. Our approach identifies configuration and usage errors that can silently affect build correctness, portability, and deployment safety. In our evaluation, CM ake S onar identifies 155 bugs across 36 real-world CMake projects on GitHub, of which 23 have been accepted and fixed by developers. With a false positive rate of 4.32 % and a recall of 97.48 % , CM ake S onar demonstrates that precise static analysis can effectively uncover high-impact bugs in untyped build systems.

Rust combines high performance with strong memory safety through strict ownership and borrowing rules. However, its unsafe mode reintroduces vulnerabilities by allowing raw-pointer manipulation, a major source of memory-safety bugs. Existing whole-program analyses for Rust often suffer from low recall and high false positives. Since unsafe code is typically small and isolated, we propose a demand-driven alternative. We present Pincer , a flow-, field-, and context-sensitive dataflow analysis framework built on IFDS. Pincer performs mutually bidirectional analysis—backward to trace raw-pointer origins and forward to explore aliases—adapting this strategy to Rust’s ownership model and low-level semantics. On this foundation, Pincer performs a modular, bottom-up vulnerability-oriented typestate analysis to detect use-after-free and double-free bugs. It tracks raw-pointer aliasing and nullness, exploits strong updates at container-manipulating returns, and leverages Rust’s safety invariants to prune provably safe regions via AXM checking. The modular design enables controlled exploration, optionally under a budget, improving scalability. Controlled unsoundness further boosts efficiency while maintaining high recall and precision. We evaluate Pincer on vulnerable programs and large Rust projects. The results show that Pincer detects memory-safety errors more accurately than state-of-the-art analyses while maintaining practical efficiency.

The prevalence of dynamic tensor shapes, driven by applications like language model serving with varying sequence lengths, is a defining characteristic of modern deep neural networks. This dynamism poses a fundamental challenge: reconciling the need for intensive, offline code generation to achieve peak performance with the demand for low-latency, adaptive execution to handle unpredictable runtime tensor shapes. Consequently, mainstream strategies are ineffective. Vendor-provided libraries, while highly optimized for a subset of common shapes, suffer performance degradation on unconventional ones. Static tensor compilers are hamstrung by prohibitive just-in-time compilation overheads for each new shape. While recent dynamic-shape compilers offer an alternative, they rely on predefined shape ranges, making them brittle when inputs fall outside these bounds. To resolve this tension, we present MoonPoly , a dynamic-shape tensor compiler that introduces micro-kernel polymerization . Our approach decouples these conflicting requirements through a two-stage process. In the offline stage, it performs intensive auto-tuning to generate a set of micro-kernels and corresponding performance models. The online stage then performs adaptive execution, rapidly assembling a near-optimal tensor operator on-the-fly, guided by a lightweight cost model. Evaluated on an NVIDIA A100 GPU, MoonPoly achieves an average operator-level speedup of 1.27× over the cuBLAS library across a diverse set of operators and data types, which in turn yields end-to-end inference acceleration for a variety of models, including BERT, the Vision Transformer, and large language models.

The RNS-CKKS scheme in Fully Homomorphic Encryption (FHE) supports crucial features for privacy-preserving machine learning, such as fixed-point arithmetic and SIMD-style vectorization. Yet, managing the escalation of ciphertext scales from homomorphic multiplications, which risks capacity overflow, along with bootstrapping, presents significant challenges. These complexities are exacerbated by the need to efficiently handle scale and bootstrapping at compile time while ensuring rapid encrypted inference.

Context-sensitive pointer analysis tends to generate excessive spurious points-to relations, causing inefficiency and imprecision. We introduce stack filtering, a novel approach using Rust's stack object lifetime information to address this issue. It identifies and eliminates context-sensitive points-to relations involving variables pointing to inactive stack objects beyond their lifetimes. Stack filtering is a lightweight two-phase process. It first assesses stack object liveness based on function reachability, leveraging an efficient call graph generated by Rapid Type Analysis (RTA). Then, this filtering is applied during the main pointer analysis.

Fully Homomorphic Encryption (FHE) facilitates computations on encrypted data without requiring access to the decryption key, offering substantial privacy benefits for deploying neural network applications in sensitive sectors such as healthcare and finance. Nonetheless, programming these applications within the FHE framework is complex and demands extensive cryptographic expertise to guarantee correctness, performance, and security. In this paper, we present ANT-ACE, a production-quality, open-source FHE compiler designed to automate neural network inference on encrypted data. ANT-ACE accepts ONNX models and generates C/C++ programs, leveraging its custom open-source FHE library. We explore the design challenges encountered in the development of ANT-ACE, which is engineered to support a variety of input formats and architectures across diverse FHE schemes through a novel Intermediate Representation (IR) that facilitates multiple levels of abstraction. Comprising 44,000 lines of C/C++ code, ANT-ACE efficiently translates ONNX models into C/C++ programs for encrypted inference on CPUs, specifically utilizing the RNS-CKKS scheme. Preliminary evaluations on a single CPU indicate that ANT-ACE achieves significant speed enhancements in ResNet models, surpassing expert manual implementations and fulfilling our design goals.

Fully Homomorphic Encryption (FHE), particularly the CKKS scheme, enables computation on encrypted data, facilitating secure task offloading to untrusted servers. CKKS allows packing multiple complex values into a single ciphertext, crucial for fixed-point arithmetic in machine learning, while leveraging SIMD parallelism at the plaintext level. However, operations such as reductions can degrade performance by creating a large number of bubbles (or gaps) in intermediate ciphertexts, leading to wasted computational resources. We introduce Qiwu, a ciphertext-level vectorization approach that enhances performance by fusing multiple ciphertexts containing bubbles. Qiwu uses a DSL to specify zero bubbles in input ciphertexts and nonzero bubbles in output ciphertexts, employs data-flow analysis to track them, and formulates a fusion plan guided by a cost-benefit assessment. Implemented in an existing FHE compiler, Qiwu was evaluated on four applications (including three machine learning tasks) and three kernels. It achieves speedups of up to 18.0× on CPUs, averaging 3.4× (geometric mean), compared to the state-of-the-art compiler that exploit only plaintext-level parallelism.

We introduce VEGA, an AI-driven system aimed at easing the development of compiler backends for new targets. Our approach involves categorizing functions from existing backends into function groups, each comprising various target-specific implementations of a standard compiler interface function, abstracted as a single function template. Therefore, generating a new backend involves customizing these function templates to specific target requirements. To capitalize on AI's capabilities in code generation, VEGA maps statements in a target-specific version of a function template into feature vectors, distinguishing between target-independent and target-specific properties. Leveraging a pre-trained model, VEGA can efficiently auto-generate a version of each function template tailored to a specific target, thereby enabling the construction of a complete compiler backend for a new target based solely on its target description files. We evaluated VEGA on three distinct targets: a CPU processor (RISC-V), a customized processor with instruction extensions (RI5CY), and an IoT processor (xCORE). VEGA demonstrated high efficiency, generating compiler backends under an hour, which can substantially enhance developer productivity. Across the three targets, VEGA achieved accuracy rates of 71.5%, 73.2%, and 62.2% for all generated functions, significantly outperforming the traditional fork-flow method, which yielded less than 8% accuracy. Moreover, VEGA provides explicit confidence scores for generated functions and statements, allowing developers to easily identify areas requiring minimal manual intervention. This research has the potential to improve the effectiveness of traditional compiler backend development.

Delta debugging assumes search space monotonicity: if a program causes a failure, any supersets of that program will also induce the same failure, permitting the exclusion of subsets of non-failure-inducing programs. However, this assumption does not always hold in practice. This paper introduces Probabilistic Monotonicity Assessment (PMA), enhancing the efficiency of ddmin-style algorithms without sacrificing effectiveness. PMA dynamically models and assesses the search space’s monotonicity based on prior tests tried during the debugging process and uses a confidence function to quantify monotonicity, thereby enabling the probabilistic exclusion of subsets of non-failure-inducing programs. Our approach significantly reduces redundant tests that would otherwise be performed, without compromising the quality of the reduction.

Heterogeneous Graph Neural Networks (HGNNs) are pivotal for extracting semantic and structural information from heterogeneous graphs. Traditional HGNN implementations often grapple with the challenges of excessive metapath instances, requiring substantial storage or incurring high instance-matching overhead. These methods typically suffer from redundant instance encoding and costly semantic graph construction. Addressing these issues, we introduce an advanced Metapath Graph (MG) abstraction that encapsulates the structural information of all metapath instances within a compact representation. This approach significantly reduces storage demands, eliminates redundant instance encodings, and foregoes the need for constructing semantic graphs, thereby facilitating rapid HGNN inference. Our software-based system, MetaHG, leverages layerwise encoding and aggregation to avoid redundancies without the necessity of semantic graphs. It incorporates a fast, lightweight partitioning method to efficiently manage large graphs. Distinctively, MetaHG seamlessly integrates with both dynamic HGNNs and homogeneous GNNs, unlike conventional systems. Comparative evaluations demonstrate that MetaHG surpasses the state-of-the-art BFS- and DFS-based HGNN systems, MAGNN and the software implementation of MetaNMP, by 42.5× and 4.53×, respectively, on average.

Hypergraph Neural Networks (HGNNs) are increasingly utilized to analyze complex inter-entity relationships. Traditional HGNN systems, based on a hyperedge-centric dataflow model, independently process aggregation tasks for hyperedges and vertices, leading to significant computational redundancy. This redundancy arises from recalculating shared information across different tasks. For the first time, we identify and harness implicit dataflows (i.e., dependencies) within HGNNs, introducing the microedge concept to effectively capture and reuse intricate shared information among aggregation tasks, thereby minimizing redundant computations. We have developed a new microedge-centric dataflow model that processes shared information as fine-grained microedge aggregation tasks. This dataflow model is supported by the Read-Process-Activate-Generate execution model, which aims to optimize parallelism among these tasks. Furthermore, our newly developed MeHyper, a microedge-centric HGNN accelerator, incorporates a decoupled pipeline for improved computational parallelism and a hierarchical feature management strategy to reduce off-chip memory accesses for large volumes of intermediate feature vectors generated. Our evaluation demonstrates that MeHyper substantially outperforms the leading CPUbased system PyG-CPU and the GPU-based system HyperGef, delivering performance improvements of $1,032.23 \times$ and $10.51 \times$, and energy efficiencies of $1,169.03 \times$ and $9.96 \times$, respectively.

Decentralized Identity (DID) enhances authentication and privacy by empowering individuals to control their own digital identities, which has gained traction globally. To our knowledge, this paper presents the first end-to-end verification effort (from design to implementation) of a real-world Decentralized Identity (DID) protocol following the IIFAA DID standard, which has been deployed within the widely used super app Alipay and issued millions of DIDs in practice. We integrate formal verification into the development lifecycle of such industrial security protocol to systematically enhance its reliability from two levels: (1) At the design level, we utilized state-of-the-art protocol design verifier Tamarin to formally model the IIFAA DID standard under a realistic threat model tailored for super apps. We then formulated and performed automated verification of desired security properties using Tamarin. We identified several design flaws that could lead to a security breach. These issues were reported to the design team and have been addressed in the updated design. (2) At the implementation level, we first extract the desired specification derived from the verified symbolic model of protocol design in the form of a set of intermediate I/O specifications. Subsequently, we translate the I/O specifications into a set of functional specifications at the implementation level, which can then be verified by the automated tool VeriFast. We identified several inconsistencies between the implementation and the verified design which are fixed by the development team and led to verified implementation faithfully obeying the verified design, together offering an end-to-end verified secure DID protocol in Alipay super app. Our work showcases how an industrial security protocol development team can design and implement a practical verified secure Decentralized Identity (DID) protocol with the help of end-to-end formal verification.

We introduce VIDTOKEN, a transformer-based preinference defense against adversarial video attacks on Video Recognition Systems (VRSs). ViDToken leverages spatial and temporal encoders to tokenize video frames and select a representative frame token (RTS), effectively distinguishing adversarial from clean videos. This approach secures both CNN- and transformer-based VRSs and outperforms existing defenses by neutralizing three advanced attack types across major video classifiers, achieving high detection rates, low false positives, and manageable overhead. To counter adaptive sparse attacks that alter only one frame, we propose a frame-replication countermeasure that significantly improves performance, positioning ViDToken above nearly all defenses. Although this increases inference times, they remain under 1 second-comparable to modern facial recognition authentication systems. This study provides key insights into advancing transformer-based adversarial defenses and calls for further research.

The emerging Mixture-of-Experts (MoE) model mitigates the high compute cost of large-scale LLMs by sparsely activating a subset of experts during inference. However, MoE requires storing massive expert parameters, creating a severe memory bottleneck on resource-constrained GPUs. Existing approaches offload parameters to host memory and prefetch activated experts to GPU memory with sophisticated policies, but these solutions are tailored to single-batch inference and suffer from communication bottlenecks at larger batch sizes, limiting throughput. We identify two forms of locality in expert activation: a small set of experts are frequently invoked across inference (global locality), while others recur within short decoding bursts (temporal locality). To exploit this, we propose Diff-MoE, which introduces a differential cache hierarchy in GPU memory. Globally hot experts reside in per-layer high-priority caches, locally hot ones are dynamically managed in per-layer medium-priority caches under a priority-driven replacement policy, and the remaining cold experts are cached temporarily and evicted on demand. Moreover, Diff-MoE incorporates a lightweight predictor that prefetches experts likely needed in the next MoE layer, overlapping migration with computation to further reduce latency. Our evaluation shows that Diff-MoE improves inference throughput by 2.74 ×, 2.22 ×, and 1.55 × over DeepSpeed, Pre-gated MoE, and MoE-Infinity, respectively.

AI has been integrated into HPC across various scientific fields, significantly enhancing performance. In molecular dynamics simulations, HPC+AI facilitates the investigation of atomic-scale physical properties using machine-learning interatomic potentials (MLIPs). However, general-purpose ML tools (e.g., TensorFlow) used in MLIPs are not optimally matched, leading to missed optimization opportunities due to the higher computational complexity and greater diversity of HPC+AI applications compared to pure AI scenarios. To address this, we introduce TensorMD, an MLIP independent of existing ML tools, enabling flexible optimizations that standard ML frameworks cannot support. TensorMD outperforms a state-of-the-art MLIP—winner of the 2020 Gordon Bell Prize and built on an ML tool—by 1.88 × on NVIDIA A100 GPU. Additionally, TensorMD was evaluated on two supercomputers with different architectures, achieving significantly reduced time-to-solution and supporting molecular dynamics simulations at scales beyond 50 billion atoms.

Context-free language (CFL) reachability is a critical framework for various program analyses, widely adopted despite its computational challenges due to cubic or near-cubic time complexity. This often leads to significant performance degradation in client applications. Notably, in real-world scenarios, clients typically require reachability information only for specific source-to-sink pairs, offering opportunities for targeted optimization. We introduce MoYe, an effective regularization-based graph simplification technique designed to enhance the performance of client-driven CFL-reachability analyses by pruning non-contributing edges—those that do not participate in any specified CFL-reachable paths. MoYe employs a regular approximation to ensure exact reachability results for all designated node pairs and operates linearly with respect to the number of edges in the graph. This lightweight efficiency makes MoYe a valuable pre-processing step that substantially reduces both computational time and memory requirements for CFL-reachability analysis, outperforming a recent leading graph simplification approach. Our evaluations with two prominent CFL-reachability client applications demonstrate that MoYe can substantially improve performance and reduce resource consumption.

Practical encrypted neural network inference under the CKKS fully homomorphic encryption (FHE) scheme relies heavily on accelerating two key kernel operations: Matrix-Vector Multiplication (MVM) and Convolution (Conv). However, existing solutions—such as expert-tuned libraries and domain-specific languages—are designed in an ad hoc manner, leading to significant inefficiencies caused by excessive rotations. We introduce MKR, a novel composition-based compiler approach that optimizes MVM and Conv kernel operations for DNN models under CKKS within a unified framework. MKR decomposes each kernel into composable units, called MetaKernels , to enhance SIMD parallelism within ciphertexts (via horizontal batching) and computational parallelism across them (via vertical batching). Our approach tackles previously unaddressed challenges, including reducing rotation overhead through a rotation-aware cost model for data packing, while also ensuring high slot utilization, uniform handling of inputs with arbitrary sizes, and compatibility with the output tensor layout. Implemented in a production-quality FHE compiler, MKR achieves inference time speedups of 10.08×−185.60× for individual MVM and Conv kernels and 1.75×−11.84× for end-to-end inference compared to a state-of-the-art FHE compiler. Moreover, MKR enables homomorphic execution of large DNN models, where prior methods fail, significantly advancing the practicality of FHE compilers.

Convolutional Neural Networks (CNNs) are fundamental to advancing computer vision technologies. As CNNs become more complex and larger, optimizing model inference remains a critical challenge in both industry and academia. On modern GPU platforms, CNN operators are typically memory-bound, leading to significant performance degradation due to memory wall effects. While recent advancements have utilized operator fusion–merging multiple operators into one–to enhance inference performance, the fusion of multiple region-based operators like convolution is seldom addressed. This article introduces AFusion , a novel operator fusion technique aimed at improving inference performance, and OptiFX, an automatic optimization framework based on this approach. OptiFX employs a cost-based backtracking search to identify optimal sub-graphs for fusion and utilizes template-based code generation to create efficient kernels for these fused sub-graphs. We evaluate OptiFX across seven prominent CNN architectures–GoogLeNet, ResNet, DenseNet, MobileNet, SqueezeNet, NasNet, and UNet–on Nvidia A6000 Ada, RTX 4090, and Jetson AGX Orin platforms. Our results demonstrate that OptiFX significantly outperforms existing methods, achieving average speedups of \(2.91\times\) , \(3.30\times\) , and \(2.09\times\) in accelerating inference performance on these platforms, respectively.

Graph pattern mining is essential for deciphering complex networks. In the real world, graphs are dynamic and evolve over time, necessitating updates in mining patterns to reflect these changes. Traditional methods use fine-grained incremental computation to avoid full re-mining after each update, which improves speed but often overlooks potential gains from examining inter-update interactions holistically, thus missing out on overall efficiency improvements. In this article, we introduce Cheetah, a dynamic graph mining system that processes updates in a coarse-grained manner by leveraging exploration domains . These domains exploit the community structure of real-world graphs to uncover data reuse opportunities typically missed by existing approaches. Exploration domains, which encapsulate extensive portions of the graph relevant to updates, allow multiple updates to explore the same regions efficiently. Cheetah dynamically constructs these domains using a management module that identifies and maintains areas of redundancy as the graph changes. By grouping updates within these domains and employing a neighbor-centric expansion strategy, Cheetah minimizes redundant data accesses. Our evaluation of Cheetah across five real-world datasets shows it outperforms current leading systems by an average factor of 2.63×.

Graph processing is pivotal in deriving insights from complex data structures but faces performance limitations due to the irregular nature of graphs. Traditional general-purpose processors often struggle with low instruction-level parallelism and energy inefficiency when handling graph data. In response, modern graph accelerators have embraced an intra-edge-parallel model to enhance parallelization, significantly outperforming conventional processors. However, the indiscriminate processing of edges in existing systems results in substantial computational redundancy, negatively impacting overall efficiency. This article introduces PRAGA, an innovative graph accelerator designed to optimize efficiency by selectively processing edges that significantly contribute to final results while preserving high computational parallelism. PRAGA utilizes an intra-edge-sequential model, prioritizing edge processing to capitalize on coarse-grained vertex-level parallelism and minimize unnecessary computations. It incorporates a hot-value manager to alleviate network-on-chip congestion and a memory-aware coalescer to minimize redundant data accesses. Our experimental results, obtained using a Xilinx Alveo U280 FPGA accelerator card, demonstrate that PRAGA achieves speedups of 17.88× and 5.86× over state-of-the-art accelerators ScalaGraph and GraphDyns, respectively, and outperforms the advanced GPU-based system Gunrock by 22.52× on average. This substantial improvement underscores PRAGA’s potential to redefine performance benchmarks in graph processing.

In recent times, dynamic-shape neural networks have gained widespread usage in intelligent applications to address complex tasks, introducing challenges in optimizing tensor programs due to their dynamic nature. As the operators' shapes are determined at runtime in dynamic scenarios, the compilation process becomes expensive, limiting the practicality of existing static-shape tensor compilers. To address the need for effective and efficient optimization of dynamic-shape neural networks, this paper introduces MikPoly, a novel dynamic-shape tensor compiler based on micro-kernel polymerization. MikPoly employs a two-stage optimization approach, dynamically combining multiple statically generated micro-kernels using a lightweight cost model based on the shape of a tensor operator known at runtime. We evaluate the effectiveness of MikPoly by employing popular dynamic-shape operators and neural networks on two representative accelerators, namely GPU Tensor Cores and Ascend NPUs. Our experimental results demonstrate that MikPoly effectively optimizes dynamic-shape workloads, yielding an average performance improvement of 1.49× over state-of-the-art vendor libraries.

Existing program analysis tools for Rust lack the ability to effectively detect security vulnerabilities due to the absence of an accurate call graph and precise points-to information. We present Rupta, the first context-sensitive pointer analysis framework designed for Rust, with a particular focus on its role in constructing call graphs. Operating on Rust MIR, Rupta employs callsite-based context-sensitivity and on-the-fly call graph construction to address a range of pointer analysis challenges, including method/function calls, pointer casts, and nested structs, while preserving type information.

On behalf of the Program Committee of the International Symposium on Code Generation and Optimization (CGO), we are delighted to present the papers featured in the 2024 edition of the conference. This year marks a significant milestone in the history of CGO, as the symposium embraced a dual-round submission process for the first time. The initial round had a deadline set on May 19th, 2024, while the second round followed the traditional CGO deadline on September 1st, 2024. Although the program committee remained consistent throughout both rounds, each round had distinct program co-chairs overseeing coordination. The firstround coordinators were Jingling Xue and Michel Steuwer, while the second-round coordinators were Fernando Pereira and Guilherme Ottoni.

Abstract Rust has gained popularity as a safer alternative to C/C++ for low-level programming due to its memory-safety features and minimal runtime overhead. However, the use of the “unsafe” keyword allows developers to bypass safety guarantees, posing memory-safety risks. Bounded Model Checking (BMC) is commonly used to detect memory-safety problems, but it has limitations for large-scale programs, as it can only detect bugs within a bounded number of executions. In this paper, we introduce UnsafeCop that utilizes and enhances BMC for analyzing memory safety in real-world unsafe Rust code. Our methodology incorporates harness design, loop bound inference, and both loop and function stubbing for comprehensive analysis. We optimize verification efficiency through a strategic function verification order, leveraging both types of stubbing. We conducted a case study on TECC (Trusted-Environment-based Cryptographic Computing), a proprietary framework consisting of 30,174 lines of Rust code, including 3,019 lines of unsafe Rust code, developed by Ant Group. Experimental results demonstrate that UnsafeCop effectively detects and verifies dozens of memory safety issues, reducing verification time by 73.71% compared to the traditional non-stubbing approach, highlighting its practical effectiveness.

Personalized recommendation systems have become one of the most important Internet services nowadays. A critical challenge of training and deploying the recommendation models is their high memory capacity and bandwidth demands, with the embedding layers occupying hundreds of GBs to TBs of storage. The advent of memory disaggregation technology and Compute Express Link (CXL) provides a promising solution for memory capacity scaling. However, relocating memory-intensive embedding layers to CXL memory incurs noticeable performance degradation due to its limited transmission bandwidth, which is significantly lower than the host memory bandwidth. To address this, we introduce ReCXL, a CXL memory disaggregation system that utilizes near-memory processing for scalable, efficient recommendation model training. ReCXL features a unified, hardwareefficient NMP architecture that processes the entire embedding training within CXL memory, minimizing data transfers over the bandwidth-limited CXL and enhancing internal bandwidth. To further improve the performance, ReCXL incorporates softwarehardware co-optimizations, including sophisticated dependencyfree prefetching and fine-grained update scheduling, to maximize hardware utilization. Evaluation results show that ReCXL outperforms the CPU-GPU baseline and the naïve CXL memory by $7.1 \times \sim 10.6 \times(9.4 \times$ on average) and $12.7 \times \sim 31.3 \times(22.6 \times$ on average), respectively.

Nowadays, high-level synthesis (HLS) has gained prominence for FPGA-based architecture prototyping, enhancing productivity significantly. Despite this advancement, HLS tools are impeded by a critical drawback: they lack support for dynamic memory management (DMM), leading to static mem-ory allocation and suboptimal use of memory resources. In response, numerous efforts have been made to develop DMM solutions compatible with HLS. However, our analysis indicates that existing solutions fail to concurrently meet the desired trifecta of scalability (efficient management of memory of any size), efficiency (minimal latency in memory (de-)allocation), and robustness (low allocation failure rates). This limitation hampers their applicability in real-world scenarios. In this paper, we introduce GraDMM, a “three-birds-one- stone” solution that comprehensively enhances the scalability, efficiency, and robustness of DMM. The key insight is to formulate memory (de-)allocation as graph analytics and lever-age sophisticated FPGA-based graph processing techniques. To achieve scalability, GraDMM specializes a simplified pipeline that significantly suppresses resource utilization expansion caused by managed memory scaling. This is crucial for managing arbitrarily sized memory on resource-limited FPGA platforms. For efficiency, GraDMM implements a data-centric concurrent traversal scheme and a shortcut-assisted fast traversal policy to accelerate (de-)allocation-guided graph traversal, reducing mem-ory (de-)allocation latency. To enhance robustness, GraDMM incorporates an adaptive memory defragmenter that defragments managed memory to minimize fragmentation-induced allocation failures. GraDMM is encapsulated as a library, providing high- level interfaces for users and ensuring synthesizability with Vi- vado HLS. Experimental results demonstrate that GraDMM out-performs three state-of-the-art HLS-compatible DMM solutions by significant margins: 56.71 %-85.59% in resource consumption savings, 78.94 % -99.99 % in (de-)allocation latency improvement, and 10.71 %-65.75% in allocation failure reduction.

The IFDS algorithm is pivotal in solving field-sensitive data-flow problems. However, its conventional use of access paths for field sensitivity leads to the generation of a large number of data-flow facts. This causes scalability challenges in larger programs, limiting its practical application in extensive codebases. In response, we propose a new field-sensitive technique that reinterprets the generation of access paths as a Context-Free Language (CFL) for field-sensitivity and formulates it as an IDE problem. This approach significantly reduces the number of data-flow facts generated and handled during the analysis, which is a major factor in performance degradation. To demonstrate the effectiveness of this approach, we developed a taint analysis tool, IDEDroid, in the IFDS/IDE framework. IDEDroid outperforms FlowDroid, an established IFDS-based taint analysis tool, in the analysis of 24 major Android apps while improving its precision (guaranteed theoretically). The speed improvement ranges from 2.1 × to 2,368.4 × , averaging at 222.0 × , with precision gains reaching up to 20.0 % (in terms of false positives reduced). This performance indicates that IDEDroid is substantially more effective in detecting information-flow leaks, making it a potentially superior tool for mobile app vetting in the market.

Context-free language reachability (CFL-reachability) is a fundamental framework for implementing various static analyses. CFL-reachability utilizes context-free grammar (CFG) to extend the expressiveness of ordinary graph reachability from an unlabeled graph to an edge-labeled graph. Solving CFL-reachability requires a (sub)cubic time complexity with respect to the graph size, which limits its scalability in practice. Thus, an approach that can effectively reduce the graph size while maintaining the reachability result is highly desirable. Most of the existing graph simplification techniques for CFL-reachability work during the preprocessing stage, i.e., before the dynamic CFL-reachability solving process. However, in real-world CFL-reachability analyses, there is a large number of reducible nodes and edges that can only be discovered during dynamic solving, leaving significant room for on-the-fly improvements. This paper aims to reduce the graph size of CFL-reachability dynamically via online cycle elimination. We propose a simple yet effective approach to detect collapsible cycles in the graph based on the input context-free grammar. Our key insight is that symbols with particular forms of production rules in the grammar are the essence of transitivity of reachability relations in the graph. Specifically, in the graph, a reachability relation to a node v_i can be "transited" to another node v_j if there is a transitive relation from v_i to v_j, and cycles formed by transitive relations are collapsible. In this paper, we present an approach to identify the transitive symbols in a context-free grammar and propose an iterative-epoch framework for online cycle elimination. From the perspective of non-parallelized CFL-reachability solving, our iterative-epoch framework is well compatible with both the standard (unordered) solver and the recent ordered solver, and can significantly improve their performance. Our experiment on context-sensitive value-flow analysis for C/C++ and field-sensitive alias analysis for Java demonstrates promising performance improvement by our iterative-epoch cycle elimination technique. By collapsing cycles online, our technique accelerates the standard solver by 17.17× and 13.94× for value-flow analysis and alias analysis, respectively, with memory reductions of 48.8% and 45.0%. Besides, our technique can also accelerate the ordered solver by 14.32× and 8.36× for value-flow analysis and alias analysis, respectively, with memory reductions of 55.2% and 57.8%.

C is a dominant programming language for implementing system and low-level embedded software. Unfortunately, the unsafe nature of its low-level control of memory often leads to memory errors. Dynamic analysis has been widely used to detect memory errors at runtime. However, existing monitoring algorithms for dynamic analysis are not yet satisfactory, as they cannot deterministically and completely detect some types of errors, such as segment confusion errors, sub-object overflows, use-after-frees and memory leaks. We propose a new monitoring algorithm, namely Smatus , short for smart status , that improves memory safety by performing comprehensive dynamic analysis. The key innovation is to maintain at runtime a small status node for each memory object. A status node records the status value and reference count of an object, where the status value denotes the liveness and segment type of this object, and the reference count tracks the number of pointer variables pointing to this object. Smatus maintains at runtime a pointer metadata for each pointer variable, to record not only the base and bound of a pointer’s referent but also the address of the referent’s status node. All the pointers pointing to the same referent share the same status node in their pointer metadata. A status node is smart in the sense that it is automatically deleted when it becomes useless (indicated by its reference count reaching zero). To the best of our knowledge, Smatus represents the most comprehensive approach of its kind. We have evaluated Smatus by using a large set of programs including the NIST Software Assurance Reference Dataset, MSBench, MiBench, SPEC and stress testing benchmarks. In terms of effectiveness (detecting different types of memory errors), Smatus outperforms state-of-the-art tools, Google’s AddressSanitizer, SoftBoundCETS and Valgrind, as it is capable of detecting more errors. In terms of performance (the time and memory overheads), Smatus outperforms SoftBoundCETS and Valgrind in terms of both lower time and memory overheads incurred, and is on par with AddressSanitizer in terms of the time and memory overhead tradeoff made (with much lower memory overheads incurred).

Context-free language (CFL) reachability is a fundamental framework for formulating program analyses. CFL-reachability analysis works on top of an edge-labeled graph by deriving reachability relations and adding them as labeled edges to the graph. Existing CFL-reachability algorithms typically adopt a single-reachability relation derivation (SRD) strategy, i.e., one reachability relation is derived at a time. Unfortunately, this strategy can lead to redundancy, hindering the efficiency of the analysis. To address this problem, this paper proposesPearl, amulti-derivationapproach that reduces derivation redundancy for CFL-reachability solving, which significantly improves the efficiency of CFL-reachability analysis. Our key insight is that multiple edges can be simultaneously derived via batch propagation of reachability relations. We also tailor our multi-derivation approach to tackle transitive relations that frequently arise when solving CFL-reachability. Specifically, we present a highly efficient transitive-aware variant,PearlPG, which enhancesPearlwithpropagation graphs, a lightweight but effective graph representation, to further diminish redundant derivations. We evaluate the performance of our approach on two clients, i.e., context-sensitive value-flow analysis and field-sensitive alias analysis for C/C++. By eliminating a large amount of redundancy, our approach outperforms two baselines including the standard CFL-reachability algorithm and a state-of-the-art solverPocrspecialized for fast transitivity solving. In particular, the empirical results demonstrate that, for value-flow analysis and alias analysis respectively,PearlPGruns 3.09$\times$faster on average (up to 4.44$\times$) and 2.25$\times$faster on average (up to 3.31$\times$) thanPocr, while also consuming less memory.

SIMD extensions are widely adopted in multi-core processors to exploit data-level parallelism. However, when co-running workloads on different cores, compute-intensive workloads cannot take advantage of the underutilized SIMD lanes allocated to memoryintensive workloads, reducing the overall performance. This paper proposes Occamy, a SIMD co-processor that can be shared by multiple CPU cores, so that their co-running workloads can spatially share its SIMD lanes. The key idea is to enable elastic spatial sharing by dynamically partitioning all the SIMD lanes across different workloads based on their phase behaviors, so that each workload may execute in variable-length SIMD mode. We also introduce an Occamy compiler to support such variable-length vectorization by analyzing such phase behaviors and generating the vectorized code that works with varying vector lengths. We demonstrate that Occamy can improve SIMD utilization, and consequently, performance over three representative SIMD architectures, with negligible chip area cost.

Multi-version graph processing has been widely used to solve many real-world problems. The process of the multi-version graph processing typically includes: (1) a history graph version switching at a specific time and (2) graph processing on this history graph. Existing multi-version graph systems assume ideally that every request for a particular graph version at a particular time will have a corresponding snapshot available. However, in most cases, this is not true. Then existing solutions usually have to settle with an "approximating" version as a substitute, leading to unexpected results for the underlying graph algorithm and thus reducing the practicality of a multi-version graph system for many application scenarios significantly.In this paper, we observe that only a few graph updates have a great impact on the final results. We therefore present AFaVS, a novel multi-version graph system that can improve accuracy effectively in both time- and memory-efficient manners. The cornerstone of AFaVS lies in a novel concept "value" that characterizes the importance of graph updates. AFaVS proposes differential management of updates based on their values and achieves higher accuracy while preserving processing and memory efficiency. AFaVS is also equipped with value-guided version switching and locality-aware optimizations to boost its overall efficiency. Our results on a variety of real-world datasets show that AFaVS outperforms four state-of-the-art multi-version graph systems by 74.35%~95.72% in terms of accuracy improvement and 57.03%~90.44% in terms of memory reduction while introducing less than 2.96% extra computing time. We have deployed AFaVS in a disaster recovery system on the production cluster of Alibaba, achieving 78.8%~90.1% fewer error rates than advanced systems at a comparable efficiency.

The memory-intensive embedding layers of the personalized recommendation systems are the performance bottleneck as they demand large memory bandwidth and exhibit irregular and sparse memory access patterns. Recent studies propose near memory processing (NMP) to accelerate memory-bound embedding operations. However, due to the load imbalance caused by the skewed access frequency of the embedding data, existing NMP solutions that exploit fine-grained memory parallelism fail to translate the increasingly massive internal bandwidth to performance improvements, leading to resource underutilization and hardware overhead.

The IFDS algorithm can be both memory- and compute-intensive for large programs as it needs to store a huge amount of path edges in memory and process them until a fixed point. In general, an IFDS-based data-flow analysis, such as taint analysis, aims to discover only the data-flow facts at some program points. Maintaining a huge amount of path edges (with many visited only once) wastes memory resources, and consequently, reduces its scalability and efficiency (due to frequent re-hashings for the path-edge data structure used).

Context-sensitivity is essential for achieving good precision in inter-procedural static analysis. To be context-sensitive, top-down analysis needs to fully inline all the statements in a callee at all its callsites, leading to statement explosion. Compositional analysis, which inlines summaries of all the callees, scales up but often loses precision, as it is not strictly context-sensitive. We propose a compositional and strictly context-sensitive framework for static analysis. This framework is based on a key observation: a compositional analysis often loses precision only on some critical statements that need to be analyzed context-sensitively. Our approach hybridly inlines the critical statements and the summaries of non-critical statements of each callee, thus avoiding re-analyzing non-critical ones. In addition, our analysis lazily summarizes the critical statements, by stopping propagating the critical statements once the calling context accumulated is adequate. We have designed and implemented several analyses (including a pointer analysis) based on this framework. Our evaluation on the pointer analysis shows that it can analyze large Java programs from the DaCapo benchmark suite and industry in minutes. Compared to context-insensitive analysis, Hybrid Inlining introduces only 65% and 1% additional time overheads on DaCapo and industrial applications, respectively.

The IFDS-based taint analysis employs two mutually iterative passes: a forward pass that identifies taints and a backward pass that detects aliases. This approach ensures both flow and context sensitivity, leading to remarkable precision. To preserve flow sensitivity, the IFDS-based taint analysis enhances data abstractions with activation statements that pinpoint the moment they acquire taint. Nonetheless, this mechanism can inadvertently introduce equivalent, yet redundant, value flows. This occurs when distinct activation statements are linked with the same data abstraction, resulting in unnecessary computational and memory-intensive demands on the analysis process. We introduce MergeDroid, a novel approach to improve the efficiency of IFDS-based taint analysis by consolidating equivalent value flows. This involves merging activation statements linked to the same data abstraction from various reachable data facts that are reachable at a given program point during the backward pass. This process generates a representative symbolic activation statement applicable to all equivalent data facts, reducing them to a single symbolic data fact. During the forward pass, when this symbolic data fact returns to its point of creation, the analysis reverts to the original data facts alongside their initial activation statements. This merge-and-replay strategy eliminates redundant value flow propagation, resulting in performance gains. Furthermore, we also improve analysis efficiency and precision by leveraging context-sensitive insights from activation statements. Our evaluation on 40 Android apps demonstrates that MergeDroid significantly enhances IFDS-based taint analysis performance. On average, MergeDroid accelerates analysis by 9.0× while effectively handling 6 more apps scalably. Additionally, it reduces false positives by significantly decreasing reported leak warnings, achieving an average reduction of 19.2%.

The extensive use of libraries in modern software impedes the scalability of pointer analysis. To address this issue, library summarization can be beneficial, but only if the resulting summary-based pointer analysis is faster without sacrificing much precision in the application code. However, currently, no library summarization approaches exist that meet this design objective. This paper presents a novel approach that solves this problem by using k-object-sensitive pointer analysis, k-obj, for Java. The approach involves applying k-obj, along with a set of summary-based inference rules, to generate a k-object-sensitive library summary. By replacing the program's library with this summary and applying k-obj, the efficiency of the program can be significantly improved while maintaining nearly the same or better precision in the application code. We validate our approach with an implementation in Soot and an evaluation using representative Java programs.

Context-free language (CFL) reachability is a fundamental framework for formulating program analyses. CFL-reachability analysis works on top of an edge-labeled graph by deriving reachability relations and adding them as labeled edges to the graph. Existing CFL-reachability algorithms typically adopt a single-reachability relation derivation (SRD) strategy, i.e., one reachability relation is derived at a time. Unfortunately, this strategy can lead to redundancy, hindering the efficiency of the analysis. To address this problem, this paper proposes Pearl, a multi-derivation approach that reduces derivation redundancy for transitive relations that frequently arise when solving reachability relations, significantly improving the efficiency of CFL-reachability analysis. Our key insight is that multiple edges involving transitivity can be simultaneously derived via batch propagation of reachability relations on the transitivity-aware subgraphs that are induced from the original edge-labeled graph. We evaluate the performance of Pearl on two clients, i.e., context-sensitive value-flow analysis and field-sensitive alias analysis for C/C++. By eliminating a large amount of redundancy, Pearl achieves average speedups of 82.73x for value-flow analysis and 155.26x for alias analysis over the standard CFL-reachability algorithm. The comparison with Pocr, a state-of-the-art CFL-reachability solver, shows that Pearl runs 10.1x (up to 29.2x) and 2.37x (up to 4.22x) faster on average respectively for value-flow analysis and alias analysis with less consumed memory.

We propose a novel two-stage approach, Stir, for inferring types in incomplete programs that may be ill-formed, where whole-program syntactic analysis often fails. In the first stage, Stir predicts a type tag for each token by using neural networks, and consequently, infers all the simple types in the program. In the second stage, Stir refines the complex types for the tokens with predicted complex type tags. Unlike existing machine-learning-based approaches, which solve type inference as a classification problem, Stir reduces it to a sequence-to-graph parsing problem. According to our experimental results, Stir achieves an accuracy of 97.37 % for simple types. By representing complex types as directed graphs (type graphs), Stir achieves a type similarity score of 77.36 % and 59.61 % for complex types and zero-shot complex types, respectively.

System Management Mode (SMM) is a secure operation mode for x86 processors supported by Unified Extensible Firmware Interface (UEFI) firmware. SMM is designed to provide a secure execution environment to access highly privileged data or control low-level hardware (such as power management). The programs running in SMM are called SMM drivers and System Management Interrupt (SMI) handlers are the most important components of SMM drivers since they are the only components to receive and handle data from outside the SMM execution environment. Although SMM can serve as an extra layer of protection when the operating system is compromised, vulnerabilities in SMM drivers, especially SMI handlers, can invalidate this protection and cause severe damages to the device. Thus, early detection of SMI handler vulnerabilities is important for UEFI firmware security.To this end, researchers have proposed to use hybrid fuzzing techniques for detecting SMI handler vulnerabilities. Particularly, Intel has developed a hybrid fuzzer called Excite and uses it to secure Intel products. Although existing hybrid fuzzing techniques can detect vulnerabilities in SMI handlers, their effectiveness is limited due to two major pitfalls: 1) They can only feed input through the most common input interface to SMI handlers, lacking the ability to utilize other input interfaces. 2) They have no awareness of variables shared by multiple SMI handlers, lacking the ability to explore code segments related to such variables. By addressing the challenges faced by existing works, we propose RSFuzzer, a hybrid greybox fuzzing technique which can learn input interface and format information and detect deeply hidden vulnerabilities which are triggered by invoking multiple SMI handlers. We implemented RSFuzzer and evaluated it on 16 UEFI firmware images provided by six vendors. The experiment results show that RSFuzzer can cover 617% more basic blocks and detect 828% more vulnerabilities on average than the state-of-the-art hybrid fuzzing technique. Moreover, we found and reported 65 0-day vulnerabilities in the evaluated UEFI firmware images and 14 CVE IDs were assigned. Noticeably, 6 of the 0-day vulnerabilities were found in commercial-off-the-shelf (COTS) products from Intel, which might have been tested by Excite before releasing.

In this paper, we introduce DebloaterX, a new approach for automatically identifying context-independent objects to debloat contexts in object-sensitive pointer analysis ( k obj). Object sensitivity achieves high precision, but its context construction mechanism combines objects with their contexts indiscriminately. This leads to a combinatorial explosion of contexts in large programs, resulting in inefficiency. Previous research has proposed a context-debloating approach that inhibits a pre-selected set of context-independent objects from forming new contexts, improving the efficiency of k obj. However, this earlier context-debloating approach under-approximates the set of context-independent objects identified, limiting performance speedups. We introduce a novel context-debloating pre-analysis approach that identifies objects as context-dependent only when they are potentially precision-critical to k obj based on three general container-usage patterns. Our research finds that objects containing no fields of ”abstract” (i.e., open) types can be analyzed context-insensitively with negligible precision loss in real-world applications. We provide clear rules and efficient algorithms to recognize these patterns, selecting more context-independent objects for better debloating. We have implemented DebloaterX in the Qilin framework and will release it as an open-source tool. Our experimental results on 12 standard Java benchmarks and real-world programs show that DebloaterX selects 92.4% of objects to be context-independent on average, enabling k obj to run significantly faster (an average of 19.3x when k = 2 and 150.2x when k = 3) and scale up to 8 more programs when k = 3, with only a negligible loss of precision (less than 0.2%). Compared to state-of-the-art alternative pre-analyses in accelerating k obj, DebloaterX outperforms Zipper significantly in both precision and efficiency and outperforms Conch (the earlier context-debloating approach) in efficiency substantially while achieving nearly the same precision.

With the rapid growth of data processed by computer systems, nonvolatile memory (NVM), represented by phase change memory (PCM), is regarded as a promising next-generation storage technology as it offers superior advantages over DRAM. However, PCM suffers from a severe write durability problem, leading to an extremely short lifespan under the uneven write patterns of real-world programs. We observe that loops are one of the primary causes of uneven writes on the stack. To alleviate this problem, we present Loop2Recursion, a compiler-assisted stack wear leveling technique that automatically transforms loops into recursive functions. In addition, we propose several optimizations to reduce the stack sizes and instruction counts of the generated recursive functions, two schemes to limit recursion depth, and selective loop transformation for cache-enabled architectures. Experimental results demonstrate that Loop2Recursion outperforms state-of-the-art methods by significantly improving stack wear leveling with a greatly reduced performance overhead.

Object-sensitive pointer analysis, which separates the calling contexts of a method by its receiver objects, is known to achieve highly useful precision for object-oriented languages such as Java. Despite recent advances, all object-sensitive pointer analysis algorithms still suffer from the scalability problem due to the combinatorial explosion of contexts in large programs. In this article, we introduce a new approach, Conch , that can be applied to debloat contexts for all object-sensitive pointer analysis algorithms, thereby improving significantly their efficiency while incurring a negligible loss of precision. Our key insight is to approximate a recently proposed set of two necessary conditions for an object in a program to be context-sensitive, i.e., context-dependent (whose precise verification is undecidable) with a set of three linearly verifiable conditions in terms of the number of edges in the pointer assignment graph (PAG) representation of the program. These three linearly verifiable conditions, which turn out to be almost always necessary in practice, are synthesized from three key observations regarding context-dependability for the objects created and used in real-world object-oriented programs. To develop a practical implementation for Conch , we introduce an IFDS-based algorithm for reasoning about object reachability in the PAG of a program, which runs linearly in terms of the number of edges in the PAG. By debloating contexts for three representative object-sensitive pointer analysis algorithms, which are applied to a set of representative Java programs, Conch can speed up these three baseline algorithms substantially at only a negligible loss of precision (less than 0.1%) with respect to several commonly used precision metrics. In addition, Conch also improves their scalability by enabling them to analyze substantially more programs to completion than before (under a time budget of 12 hours). Conch has been open-sourced (http://www.cse.unsw.edu.au/~corg/tools/conch), opening up new opportunities for other researchers and practitioners to further improve this research. To demonstrate this, we introduce one extension of Conch to accelerate further the three baselines without losing any precision, providing further insights on extending Conch to make precision-efficiency tradeoffs in future research.

Low-level control makes C unsafe, resulting in memory errors that can lead to data corruption, security vulnerabilities or program crashes. Dynamic analysis tools, which have been widely used for detecting memory errors at runtime, usually perform instrumentation at the IR or binary level. However, these non-source-level instrumentation frameworks and tools suffer from two inherent drawbacks: optimization sensitivity and platform dependence. Due to optimization sensitivity, the user of these tools must trade either performance for effectiveness by compiling the program at-O0or effectiveness for performance by compiling the program at a higher optimization level, say,-O3. In this paper, we propose a new source-level instrumentation framework to overcome these two drawbacks, and implement it in a new dynamic analysis tool, calledMovec, that adopts a pointer-based monitoring algorithm. We have evaluatedMoveccomprehensively by using the NIST's SARD benchmark suite (1152 programs), a set of 126 microbenchmarks (with ground truth), a set of 20 MiBench benchmarks and 5 pure-C SPEC CPU 2017 benchmarks. In terms of effectiveness,Movecoutperforms three state-of-the-art dynamic analysis tools, AddressSanitizer, SoftBoundCETS and Valgrind, for all the standard optimization levels (from-O0to-O3). In terms of performance,Movecoutperforms SoftBoundCETS and Valgrind, and is slower than AddressSanitizer but consumes less memory.

Object-sensitive pointer analysis (denotedkobjunder$k$-limiting) for an object-oriented program can be accelerated if context-sensitivity can be selectively applied to only some precision-critical variables/objects in a program. Existing pre-analyses for making such selections, which are performed as whole-program analyses to a program, are developed based on two broad approaches. One approach preserves the precision of object-sensitive pointer analysis but achieves limited speedups by reasoning about all the possible value flows in the program conservatively, while the other approach achieves greater speedups but sacrifices precision (often unduly) by examining only some but not all the value flows in the program heuristically. In this paper, we introduce a new pre-analysis approach,Turner$^{\mathcal{m}}$(where$\mathcal {m}$stands for modularity), that represents a sweet spot between these two existing ones, as it is designed to enablekobjto run significantly faster than the former approach and achieve significantly better precision than the latter approach.Turner$^{\mathcal{m}}$is simple, lightweight yet effective due to two novel aspects in its design. First, we exploit a key observation that some precision-uncritical objects in the program can be approximated based on the object-containment relationship pre-established (from Andersen's analysis). In practice, this approximation introduces only a small degree of imprecision intokobj. Second, leveraging this initial approximation, we apply a novel object reachability analysis to the program by pre-analyzing its methods according to a reverse topological order of its call graph. When pre-analyzing each method, we make use of a simple DFA (Deterministic Finite Automaton) to reason about object reachability intra-procedurally from its entry to its exit along all the possible value flows established by its statements to identify its precision-critical variables/objects. In practice, this new modular object reachability analysis, which runs linearly in terms of the number of statements in the program, introduces again only a small loss of precision intokobj. We have validatedTurner$^{\mathcal{m}}$with an open-source implementation inSoot(already publicly available) against the state of the art by using a set of 12 widely used Java benchmarks and applications.

We present TIARA, a novel approach to recovering container classes in c++ binaries. Given a variable address in a c++ binary, TIARA first applies a new type-relevant slicing algorithm incorporated with a decay function, TSLICE, to obtain an inter-procedural forward slice of instructions expressed as a CFG to summarize how the variable is used in the binary (as our primary contribution). TIARA then makes use of a GCN (Graph Convolutional Network) to learn and predict the container type for the variable (as our secondary contribution). According to our evaluation, TIARA can advance the state of the art in inferring commonly used container types in a set of eight large real-world COTS c++ binaries efficiently (in terms of the overall analysis time) and effectively (in terms of precision, recall and F1 score).

We address the problem of finding context embeddings for faulty locations to allow a learning-based APR tool to learn and predict the repair operators used at the faulty locations. We introduce M3V, a new multi-modal multi-view context embedding approach, which represents the context of a faulty location in two modalities: (1) texts that capture its signature in a natural language using the tree-LSTM model, and (2) graphs that capture its structure with two views, data and control dependences, using the GNN model. We then fuse these two modalities to learn a probabilistic classifier from correct code that, once given a faulty location, will produce a probabilistic distribution over a set of repair operators. We have evaluated M3V against the state-of-the-art context embedding approaches in repairing two common types of bugs in Java, null pointer exceptions (NPE) and index out of bounds (OOB). Trained and tested with 75673 code samples from 20 real-world projects, a learning-based APR tool can predict repair operators more effectively with our context embeddings in repairing NPE bugs, by achieving higher accuracies (11% – 41%) and higher F1 scores (16% – 143%). For OOB bugs, these improvements are 9% – 30% and 15% – 79%, respectively.

Graph convolutional networks (GCNs) are promising to enable machine learning on graphs. GCNs exhibit mixed computational kernels, involving regular neural-network-like computing and irregular graph-analytics-like processing. Existing GCN accelerators obey a divide-and-conquer philosophy to architect two separate types of hardware to accelerate these two types of GCN kernels, respectively. This hybrid architecture improves intra-kernel efficiency but considers little inter-kernel interactions in a holistic view for improving overall efficiency.In this paper, we present a new GCN accelerator, RE-FLIP, with three key innovations in terms of architecture design, algorithm mappings, and practical implementations. First, ReFlip leverages PIM-featured crossbar architectures to build a unified architecture for supporting the two types of GCN kernels simultaneously. Second, ReFlip adopts novel algorithm mappings that can maximize potential performance gains reaped from the unified architecture by exploiting the massive crossbar-structured parallelism. Third, ReFlip assembles software/hardware co-optimizations to process real-world graphs efficiently. Compared to the state-of-the-art software frameworks running on Intel Xeon E5-2680v4 CPU and NVIDIA Tesla V100 GPU, ReFlip achieves the average speedups of 6,432× and 86.32× and the average energy savings of 9,817× and 302.44×, respectively. In addition, ReFlip also outperforms a state-of-the-art GCN hardware accelerator, AWB-GCN, by achieving an average speedup of 5.06× and an average energy saving of 15.63×.

Graph processing is promising to extract valuable insights in graphs. Nowadays, emerging 3D-stacked memories and silicon technologies can provide over terabytes per second memory bandwidth and thousands of processing elements (PEs) to meet the high hardware demand of graph applications. However, this leap in hardware capability does not result in a huge increase but even a degradation sometimes in performance for graph processing. In this paper, we discover that the centralized on-chip memory hierarchy adopted in existing graph accelerators is the villain causing poor scalability due to its quadratic increase of hardware overheads with respect to the number of PEs.We present a novel distributed on-chip memory hierarchy by leveraging the network-on-chip (NoC) to enable massively parallel graph processing. We architect ScalaGraph, a brand new graph processing accelerator, to exploit this insight. ScalaGraph adopts a software-hardware co-design to minimize NoC communication overheads via an efficient row-oriented dataflow mapping and runtime aggregation. A specialized scheduling mechanism is also proposed to improve load imbalance. Our results on a Xilinx Alveo U280 FPGA card show that ScalaGraph on a modest configuration of 512 PEs achieves 2.2× and 3.2× speedups over a state-of-theart graph accelerator GraphDyns and a GPU-based graph system Gunrock, respectively. Moreover, ScalaGraph enables supporting at least 1,024 PEs with nearly linear performance scaling while GraphDyns fails to work.

Hypergraph processing has emerged as a powerful approach for analyzing complex multilateral relationships among multiple entities. Past research on building hypergraph systems suggests that changing the scheduling order of bipartite edge tasks can improve the overlap-induced data locality in hypergraph processing. However, due to the complex intertwined connections between vertices and hyperedges, it is almost impossible to find a locality-optimal scheduling order. Thus, these task-centric hypergraph systems often suffer from substantial off-chip communications. In this paper, we first propose a novel data-centric Load-Trigger-Reduce (LTR) execution model to exploit fully the locality in hypergraph processing. Unlike a task-centric model that loads the required data along with a task, our LTR model invokes tasks as per the data used. Specifically, once the hypergraph data is loaded into the on-chip memory, all of its relevant computation tasks will be triggered simultaneously to output intermediate results, which are finally reduced to update the final results. Our LTR model enables all hypergraph data to be accessed once in each iteration. To fully exploit the LTR performance potential, we further architect an LTR-driven hypergraph accelerator, XuLin, which features with an adaptive data loading mechanism to minimize the loading cost via chunk merging at runtime. XuLin is also equipped with a priority-based differential data reduction scheme to reduce the impact of conflicting updates on performance. We have implemented XuLin both on a Xilinx Alveo U250 FPGA card and using a cycle-accurate simulator. The results show that XuLin outperforms the state-of-the-art hypergraph processing solutions Hygra and ChGraph by $20.47 \times$ and $8.77 \times$ on average, respectively.

The Unified Extensible Firmware Interface (UEFI) provides a specification of the software interface between an OS and its underlying platform firmware. The runtime services provided are seemingly secure as they reside in System Management Mode (SMM) at ring -2, assuming a higher privilege than the OS kernel at ring 0. However, their software vulnerabilities are known to be exploitable to launch ring 0 to ring -2 privilege escalation, i.e., SMM privilege escalation attacks.In this paper, we introduce an effective static analysis framework for detecting SMM privilege escalation vulnerabilities in UEFI firmware. We present a systematic study of such vulnerabilities and identify their root causes as being two types of references that can escape from the SMRAM, legacy references and unintentional references. Existing static analyses are ineffective in detecting such vulnerabilities in stripped COTS UEFI firmware images, which are developed based on a customized callback mechanism that organizes callable functions into protocols identified by GUIDs. By leveraging such a callback-based programming paradigm, we introduce SPENDER, the first static detection framework, which is founded on a novel protocol-centric analysis, for uncovering the potential SMM privilege escalation vulnerabilities in UEFI firmware efficiently and precisely. For a total of 1148 UEFI binaries collected from eight vendors, SPENDER has successfully found 36 SMM privilege escalation vulnerabilities (two 1-day and 34 0-day vulnerabilities), which can cause arbitrary code execution and arbitrary address write (and can thus enable, e.g., the attackers to install a bootkit into a flash drive). We have reported these 36 vulnerabilities to the vendors, with the two 1-day vulnerabilities confirmed as known previously but the 34 0-day vulnerabilities confirmed as new.

Control-Flow Integrity (CFI) techniques focus often on protecting forward edges and assume that backward edges are protected by shadow stacks. However, software-based shadow stacks that can provide performance, security, and compatibility are still hard to obtain, leaving an important security gap on x86-64. In this article, we introduce a simple, efficient, and effective parallel shadow stack design (based on LLVM), FlashStack , for protecting return addresses in single- and multi-threaded programs running under 64-bit Linux on x86-64, with three distinctive features. First, we introduce a novel dual-prologue approach to enable a protected function to thwart the TOCTTOU attacks, which are constructed by Microsoft’s red team and lead to the deprecation of Microsoft’s RFG. Second, we design a new mapping mechanism, Segment+Rsp-S , to allow the parallel shadow stack to be accessed efficiently while satisfying the constraints of arch_prctl() and ASLR in 64-bit Linux. Finally, we introduce a lightweight inspection mechanism, SideChannel-K , to harden FlashStack further by detecting entropy-reduction attacks efficiently and protecting the parallel shadow stack effectively with a 10-ms shuffling policy. Our evaluation on SPEC CPU2006 , Nginx, and Firefox shows that FlashStack can provide high performance, meaningful security, and reasonable compatibility for server- and client-side programs on x86-64.

Dynamic graph convolutional networks (DGCNs) have emerged as an effective approach to analyzing graph data that is constantly changing. The typical DGCNs incorporate not only graph convolutional networks (GCNs) to extract the structural information but also with recurrent neural networks (RNNs) to capture the temporal information from evolving graph data. These two alternative execution kernels of DGCNs impose unique architecture challenges for both types of kernels to be implemented efficiently. The presence of complex execution patterns of DGCNs renders existing architectures unsuitable. In this article, we present the first DGCN accelerator with an integrated architecture, named ReaDy, to accelerate DGCNs based on emerging PIM-featured ReRAM architectures. ReaDy is novel with an integrated architecture that enables running the GCN and RNN kernels of DGCNs simultaneously. Specifically, ReaDy is equipped with a redundancy-free scheduling mechanism to alleviate intrinsic dynamic irregularity for the GCN kernel, improving hardware utilization. In addition, ReaDy also includes a locality-aware dataflow strategy to exploit the inherent intervertex data locality for the RNN kernel, reducing superfluous data accesses to vertices and weight parameters. In a holistic view, ReaDy further enhances the entire system via an interkernel pipeline to reduce the off-chip accesses of intermediate results, boosting the overall efficiency of DGCNs significantly. Compared to the state-of-the-art software framework, PyGT, running on Intel Xeon E5-2680v4 CPU and NVIDIA Ampere A100 GPU, ReaDy achieves the average speedups of$955\times $and$27.33\times $, and the average energy savings of 1$093\times $and$80.21\times $, respectively. In addition, ReaDy outperforms ReFlip-ERA, which is obtained by combining a state-of-the-art GCN accelerator ReFlip and RNN accelerator ERA-LSTM, by an average speedup of$8.30\times $and an average energy saving of$7.29\times $.

Pruning deep neural networks (DNNs) can reduce the model size and thus save hardware resources of a resistive-random-access-memory (ReRAM)-based DNN accelerator. For the tightly coupled crossbar structure, existing ReRAM-based pruning techniques prune the weights of a DNN in a structured manner, thereby attaining low pruning ratios. This article presents a novel pruning technique, SegPrune, for pruning the weights of a DNN flexibly on crossbar architectures in order to maximize the pruning ratio achieved while preserving crossbar efficiency. We observe that different filters of a weight matrix share a large number of matrix subcolumns (in the same rows), called segments, that can be pruned by using the same segment shape in the sense that the weights at the same column position of these segments are either simultaneously accuracy-sensitive (and should thus be reserved) or simultaneously accuracy-insensitive (and can thus be pruned). Due to the bit-line exchangeability in the crossbar, segments with the same pruning shape can be assembled together into the same crossbar to ensure crossbar execution efficiency. We propose a projection-based shape voting algorithm to select suitable segment shapes to drive the weight pruning process. Accordingly, we also introduce a low-overhead data path that can be easily integrated into any existing ReRAM-based DNN accelerator, achieving a high pruning ratio and a high execution efficiency. Our evaluation shows that SegPrune outperforms the state-of-the-art, Hybrid-P, and FORMAS, by up to$14.6\times $and$3.6\times $in pruning ratio,$13.9\times $and$3.4\times $in inference speedup, and$12.5\times $and$3.1\times $in energy reduction, respectively, while achieving an even higher accuracy at the cost of less than 0.27% extra hardware area overhead.

Shadow stacks play an important role in protecting return addresses to mitigate ROP attacks. Parallel shadow stacks, which shadow the call stack of each thread at the same constant offset for all threads, are known not to support multi-threading well. On the other hand, compact shadow stacks must maintain a separate shadow stack pointer in thread-local storage (TLS) , which can be implemented in terms of a register or the per-thread Thread-Control-Block (TCB) , suffering from poor compatibility in the former or high performance overhead in the latter. In addition, shadow stacks are vulnerable to information disclosure attacks. In this paper, we propose to mitigate ROP attacks for single- and multi-threaded server programs running on general-purpose computing systems by using a novel stack layout, called a buddy stack (referred to as Bustk ), that is highly performant, compatible with existing code, and provides meaningful security. These goals are met due to three novel design aspects in Bustk . First, Bustk places a parallel shadow stack just below a thread’s call stack (as each other’s buddies allocated together), avoiding the need to maintain a separate shadow stack pointer and making it now well-suited for multi-threading. Second, Bustk uses an efficient stack-based thread-local storage mechanism, denoted STK-TLS , to store thread-specific metadata in two TLS sections just below the shadow stack in dual redundancy (as each other’s buddies), so that both can be accessed and updated in a lightweight manner from the call stack pointer rsp alone. Finally, Bustk re-randomizes continuously (on the order of milliseconds) the return addresses on the shadow stack by using a new microsecond-level runtime re-randomization technique, denoted STK-MSR . This mechanism aims to obsolete leaked information, making it extremely unlikely for the attacker to hijack return addresses, particularly against a server program that sits often tens of milliseconds away from the attacker. Our evaluation using web servers, Nginx and Apache Httpd , shows that Bustk works well in terms of performance, compatibility, and security provided, with its parallel shadow stacks incurring acceptable memory overhead for real-world applications and its STK-TLS mechanism costing only two pages per thread. In particular, Bustk can protect the Nginx and Apache servers with an adaptive 1-ms re-randomization policy (without observable overheads when IO is intensive, with about 17,000 requests per second). In addition, we have also evaluated Bustk using other non-server applications, Firefox , Python , LLVM , JDK and SPEC CPU2006 , to demonstrate further the same degree of performance and compatibility provided, but the protection provided for, say, browsers, is weaker (since network-access delays can no longer be assumed).

Cloud systems suffer from distributed concurrency bugs, which often lead to data loss and service outage. This paper presentsCloudRaid, a new automatical tool for finding distributed concurrency bugs efficiently and effectively. Distributed concurrency bugs are notoriously difficult to find as they are triggered by untimely interaction among nodes, i.e., unexpected message orderings. To detect concurrency bugs in cloud systems efficiently and effectively,CloudRaidanalyzes and tests automatically only the message orderings that are likely to expose errors. Specifically,CloudRaidmines the logs from previous executions to uncover the message orderings that are feasible but inadequately tested. In addition, we also propose a log enhancing technique to introduce new logs automatically in the system being tested. These extra logs added improve further the effectiveness ofCloudRaidwithout introducing any noticeable performance overhead. Our log-based approach makes it well-suited for live systems. We have appliedCloudRaidto analyze six representative distributed systems: Hadoop2/Yarn, HBase, HDFS, Cassandra, Zookeeper, and Flink.CloudRaidhas succeeded in testing 60 different versions of these six systems (10 versions per system) in 35 hours, uncovering 31 concurrency bugs, including nine new bugs that have never been reported before. For these nine new bugs detected, which have all been confirmed by their original developers, three are critical and have already been fixed.

Tensor-specialized hardware for supporting low-precision arithmetic has become an inevitable trend due to the ever-increasing demand on computational capability and energy efficiency in intelligent applications. The main challenge faced when accelerating a tensor program on tensor-specialized hardware is how to achieve the best performance possible in reduced precision by fully utilizing its computational resources while keeping the precision loss in a controlled manner. In this paper, we address this challenge by proposing QUANTENSOR, a new approach for accelerating general-purpose tensor programs by replacing its tensor computations with low-precision quantized tensor computations on NVIDIA Tensor Cores. The key novelty is a new residual-based precision refinement technique for controlling the quantization errors, allowing tradeoffs between performance and precision to be made. Evaluation with GEMM, deep neural networks, and linear algebra applications shows that QUANTENSOR can achieve remarkable performance improvements while reducing the precision loss incurred significantly at acceptable overheads.

Go, a fast growing programming language, is often considered as “the programming language of the cloud”. The language provides a rich set of synchronization primitives, making it easy to write concurrent programs with great parallelism. However. the rich set of primitives also introduces many bugs. We build Gobench, the first benchmark suite for Go concurrency bugs. Currently, Gobench consists of 82 real bugs from 9 popular open source applications and 103 bug kernels. The bug kernels are carefully extracted and simplified from 67 out of these 82 bugs and 36 additional bugs reported in a recent study to preserve their bug-inducing complexities as much as possible. These bugs cover a variety of concurrency issues, both traditional and Go-specific. We believe Gobench will be instrumental in helping researchers understand concurrency bugs in Go and develop effective tools for their detection. We have therefore evaluated a range of representative concurrency error detection tools using Gobench. Our evaluation has revealed their limitations and provided insights for making further improvements.

Object-sensitive pointer analysis for an object-oriented program can be accelerated if context-sensitivity can be selectively applied to some precision-critical variables/objects in the program. Existing pre-analyses, which are performed to make such selections, either preserve precision but achieve limited speedups by reasoning about all the possible value flows in the program conservatively or achieve greater speedups but sacrifice precision (often unduly) by examining only some but not all the value flows in the program heuristically. In this paper, we introduce a new approach, named Turner, that represents a sweet spot between the two existing ones, as it is designed to enable object-sensitive pointer analysis to run significantly faster than the former approach and achieve significantly better precision than the latter approach. Turner is simple, lightweight yet effective due to two novel aspects in its design. First, we exploit a key observation that some precision-uncritical objects can be approximated based on the object-containment relationship pre-established (by applying Andersen’s analysis). This approximation introduces a small degree yet the only source of imprecision into Turner. Second, leveraging this initial approximation, we introduce a simple DFA to reason about object reachability for a method intra-procedurally from its entry to its exit along all the possible value flows established by its statements to finalize its precision-critical variables/objects identified. We have validated Turner with an implementation in Soot against the state of the art using a set of 12 popular Java benchmarks and applications.

C is a dominant language for implementing system software. Unfortunately, its support for low-level control of memory often leads to memory errors. Dynamic analysis tools, which have been widely used for detecting memory errors at runtime, are not yet satisfactory as they cannot deterministically and completely detect some types of memory errors, e.g., segment confusion errors, sub-object overflows, use-after-frees, and memory leaks.

We Introduce a new approach, Conch, for debloating contexts for all the object-sensitive pointer analysis algorithms developed for object-oriented languages, where the calling contexts of a method are distinguished by its receiver objects. Our key insight is to approximate a recently proposed set of two necessary conditions for an object to be context-sensitive, i.e., context-dependent (whose precise verification is undecidable) with a set of three linearly verifiable conditions (in terms of the number of statements in the program) that are almost always necessary for real-world object-oriented applications, based on three key observations regarding context-dependability for their objects used. To create a practical implementation, we introduce a new IFDS-based algorithm for reasoning about object reachability in a program. By debloating contexts for two representative object-sensitive pointer analyses applied to a set of 12 representative Java programs, Conch can speed up the two baselines together substantially (3.1x on average with a maximum of 15.9x) and analyze 7 more programs scalably, but at only a negligible loss of precision (less than 0.1%).

Deep learning has been widely adopted in industry and has achieved great success in a wide range of application areas. Bugs in deep learning programs can cause catastrophic failures, in addition to a serious waste of resources and time.This paper aims at detecting industrial TensorFlow program bugs. We report an extensive empirical study on 12,289 failed TensorFlow jobs, showing that existing static tools can effectively detect 72.55% of the top three types of Python bugs in industrial TensorFlow programs. In addition, we propose (for the first time) a constraint-based approach for detecting TensorFlow shape-related errors (one of the most common TensorFlow-specific bugs), together with an associated tool, ShapeTracer. Our evaluation on a set of 60 industrial TensorFlow programs shows that ShapeTracer is efficient and effective: it analyzes each program in at most 3 seconds and detects effectively 40 out of 60 industrial TensorFlow program bugs, with no false positives. ShapeTracer has been deployed in the platform-X platform and will be released soon.

Object sensitivity is widely used as a context abstraction for computing the points-to information context-sensitively for object-oriented programming languages such as Java. Due to the combinatorial explosion of contexts in large object-oriented programs, k -object-sensitive pointer analysis (under k -limiting), denoted k -obj , is often inefficient even when it is scalable for small values of k , where k ⩽ 2 holds typically. A recent popular approach for accelerating k -obj trades precision for efficiency by instructing k -obj to analyze only some methods in a program context-sensitively, determined heuristically by a pre-analysis. In this article, we investigate how to develop a fundamentally different approach, Eagle , for designing a pre-analysis that can make k -obj run significantly faster while maintaining its precision. The novelty of Eagle is to enable k -obj to analyze a method with partial context sensitivity (i.e., context-sensitively for only some of its selected variables/allocation sites) by solving a context-free-language (CFL) reachability problem based on a new CFL-reachability formulation of k -obj . By regularizing one CFL for specifying field accesses and using another CFL for specifying method calls, we have formulated Eagle as a fully context-sensitive taint analysis (without k -limiting) that is both effective (by selecting the variables/allocation sites to be analyzed by k -obj context-insensitively so as to reduce the number of context-sensitive facts inferred by k -obj in the program) and efficient (by running linearly in terms of the number of pointer assignment edges in the program). As Eagle represents the first precision-preserving pre-analysis, our evaluation focuses on demonstrating its significant performance benefits in accelerating k -obj for a set of popular Java benchmarks and applications, with call graph construction, may-fail-casting, and polymorphic call detection as three important client analyses.

Scratchpad Memory (SPM) is widely used in emerging domain-specific architectures and accelerators for improving energy efficiency and time predictability. Typically, SPM-based architectures use DMA for fetching data from off-chip memory and global load instructions for loading fine-grained data directly into registers. For such architectures, neither capacity-only nor bandwidth-only loop tiling can efficiently use the bandwidth and SPM. This paper introduces a bandwidth-aware loop tiling approach that enables a tradeoff between SPM space utilization and bandwidth utilization to be made, by leveraging a runtime tiling framework and a cross-host-kernel IPA. Experimental results demonstrate that our approach can achieve the performance improvement of up to 4x, with a geometric average of 26%.

Tensors are a popular programming interface for developing AI algorithms. Representative AI programming frameworks require developers to be always aware of tensor layouts, thereby reducing their productivity in integrating an existing operation with a new library and/or writing a new operation. We propose VTensor, a layout-oblivious virtual tensor programming interface, together with a global layout inference mechanism to resolve the layout required by virtual tensors. Furthermore, VTensor leverages a layout-oriented optimization to globally minimize the number of layout conversion operations, together with a straggler-ware scheduling algorithm and a pool-based memory allocation scheme to globally allocate resources. VTensor yields significant speedup and LOC (Lines of Codes) reduction compared to TensorFlow.

Non-Volatile Memory (NVM) technologies, such as Phase Change Memory (PCM), herald the next generation of main memory as they offer superior features compared with DRAM. Unfortunately, NVM's limited write endurance hinders its adoption as its lifetime can be extremely short under skew writes. This paper observes that the loops in programs are one of the primary causes of uneven writes as they introduce the hot data and cause a large number of stack frames to be allocated to the same locations. To alleviate this problem, we present Loop2Recursion, a compile-time wear leveling technique for transforming loops into recursions automatically. Our approach is flexible as it can avoid a substantial memory overhead by limiting the depth of recursion. Experimental results demonstrate that Loop2Recursion can significantly improve the wear leveling over stack area compared to the state-of-the-art methods, while incurring only negligible performance overhead.

Return-oriented programming (ROP) is an effective code-reuse attack in which short code sequences (i.e., gadgets) ending in a ret instruction are found within existing binaries and then executed by taking control of the call stack. The shadow stack, control flow integrity (CFI) and code (re)randomization are three popular techniques for protecting programs against return address overwrites. However, existing runtime rerandomization techniques operate on concrete return addresses, requiring expensive pointer tracking.

Many fault localization (FL) techniques have been proposed to facilitate software debugging. Due to being lightweight, spectrum-based fault localization (SBFL) is one of the most popular FL families and widely deployed in program repair tools. SBFL ranks program elements by recording the program coverage under a test suite and calculates the suspiciousness score of each element with a ranking formula. Despite numerous formulae proposed, SBFL still suffers from providing no new sources of information other than program coverage. Mutation-based fault localization (MBFL) iteratively mutates a faulty program and suggests fault locations through mutants that overturn failed test cases. However, due to its explosive search space, MBFL has been adopted by only few program repair tools.In this paper, we aim at exploiting the advantages of MBFL and boosting SBFL with low overhead by building a practical FL tool. We propose Flip, an FL technique with inferences from mutated predicates. Based on SBFL, we leverage and extend the predicate switching technique to infer fault locations no matter whether the mutated predicate can overturn a failed test case or not. Finally, we compute a new ranking list with a joint inference that combines program coverage and mutation inferences.We use Defects4j (version 1.5.0), containing 438 real-world faults from six projects to evaluate Flip. All the seven stateof-the-art SBFL techniques benefit from Flip (e.g., by ranking up to 46.4% more faults in top-1) with low overhead (e.g., by incurring less than 2-minute average overhead for each fault). We also offer some insights on how to further improve FL on real-world faults based on the empirical results.

Resistive random access memory (ReRAM) addresses the high memory bandwidth requirement challenge of graph analytics by integrating the computing logic in the memory. Due to the matrix-structured crossbar architecture, existing ReRAM-based accelerators, when handling real-world graphs that often have the skewed degree distribution, suffer from the severe sparsity problem arising from zero fillings and activation nondeterminism, incurring substantial ineffectual computations.In this paper, we observe that the sparsity sources lie in the consecutive mapping of source and destination vertex index onto the wordline and bitline of a crossbar. Although exhaustive graph reordering improves the sparsity-induced inefficiency, its totally-random (source and destination) vertex mapping leads to expensive overheads. This work exploits the insight in a mid-point vertex mapping with the random wordlines and consecutive bitlines. A cost-effective preprocessing is proposed to exploit the insight by rapidly exploring the crossbar-fit vertex reorderings but ignores the sparsity arising from activation dynamics. We present a novel ReRAM-based graph analytics accelerator, named Spara, which can maximize the workload density of crossbars dynamically by using a tightly-coupled bank parallel architecture further proposed. Results on real-world and synthesized graphs show that Spara outperforms GraphR and GraphSAR by 8.21 × and 5.01 × in terms of performance, and by 8.97 × and 5.68× in terms of energy savings (on average), while incurring a reasonable (<; 9.98%) pre-processing overhead.

Processing-In-Memory (PIM) is an emerging technology that addresses the memory bottleneck of graph processing. In general, analog memristor-based PIM promises high parallelism provided that the underlying matrix-structured crossbar can be fully utilized while digital CMOS-based PIM has a faster single-edge execution but its parallelism can be low. In this paper, we observe that there is no absolute winner between these two representative PIM technologies for graph applications, which often exhibit irregular workloads. To reap the best of both worlds, we introduce a new heterogeneous PIM hardware, called Hetraph, to facilitate energy-efficient graph processing. Hetraph incorporates memristor-based analog computation units (for high-parallelism computing) and CMOS-based digital computation cores (for efficient computing) on the same logic layer of a 3D die-stacked memory device. To maximize the hardware utilization, our software design offers a hardware heterogeneity-aware execution model and a workload offloading mechanism. For performance speedups, such a hardware-software co-design outperforms the state-of-the-art by 7.54 ×(CPU), 1.56 ×(GPU), 4.13× (memristor-based PIM) and 3.05× (CMOS-based PIM), on average. For energy savings, Hetraph reduces the energy consumption by 57.58× (CPU), 19.93× (GPU), 14.02 ×(memristor-based PIM) and 10.48 ×(CMOS-based PIM), on average.

The Android framework provides sensitive APIs for Android apps to access the user's private information, e.g., SMS, call logs and locations. Whether a sensitive API call in an app is legitimate or not depends on whether the app has provided enough natural-language semantics to reflect the need for the permission. The prior efforts on analyzing description-to-permission fidelity in an app are all static. Some check whether the permissions requested (or sensitive APIs used) by the app are consistent with the functionalities described by the app. These app-level techniques are too coarse-grained, as they cannot tell if a sensitive API call under a certain runtime context, such as a UI state, is legitimate or not. Others attempt to establish this connection by performing a data-flow analysis, but such fine-grained API-level static analyses are too imprecise to handle a variety of dynamic language features used in Android apps, including dynamic class loading, reflection and code obfuscation. We introduce APICOG, an automated fine-grained API-level approach, representing the first dynamic description-to-permission fidelity analysis for an Android app that can check if a sensitive API call is legitimate or not under a given runtime context. APICOGrelates each sensitive API call with a UI state, called its UI context, under which the call is made via dynamic analysis and then extracts the text-based semantics for each UI context from its associated text- and image-typed attributes by applying a natural language processing (NLP) technique. Finally, APICOGrelies on machine-learning to deduce if a sensitive API call under a UI context is legitimate or not. We have evaluated APICOGwith thousands of Android apps drawn from a third-party market and a malware dataset, achieving an accuracy of 97.7%, a precision of 94.1% and a recall of 92.8% overall, outperforming the prior art in all the three metrics.

Android supports an event dispatching system that reacts to system and user actions by generating events. However, lack of synchronization between events can lead to event-based races in Android apps. Such event-based races are difficult to detect dynamically due to the challenges faced in generating the right events to satisfy the right event-dependent conditional branches, so that their guarded racy statements can be reached. As a result, existing dynamic tools, which try to find and reschedule some race-triggering events heuristically, are often ineffective.We introduce SIEVE, a tool for exposing event-based races in Android apps dynamically by leveraging a new selective branch instrumentation technique. For the conditionals potentially affecting a race (detected, say, by a static tool), SIEVE fixes the true/false outcomes of some of these conditionals based on a systematic branch analysis, which analyzes the satisfiability of all the conditionals guarding the given racy statements and their safeness for instrumentation. By instrumenting certain branches selectively this way, we can not only expose effectively event-based races but also reduce substantially the negative ramifications of instrumentation (e.g., reporting non-existent races and introducing unexpected crashes during dynamic execution). An evaluation of SIEVE with 25 Android apps shows that our tool can expose event-based races more effectively than the state of the art.

Graph mining is becoming increasingly important due to the ever-increasing demands on analyzing complex structures in graphs. Existing graph accelerators typically hold most of the randomly-accessed data in an on-chip memory to avoid off-chip communications. However, graph mining exhibits substantial random accesses from not only vertex dimension but also edge dimension (with the latter being excessively more complex than the former), leading to significant degradations in terms of both performance and energy efficiency.We observe that the most random memory requests arising in graph mining come from accessing a small fraction of valuable (vertex and edge) data when handling real-world graphs. To exploit this extension locality with maximum parallelism, we architect GRAMER, the first graph mining accelerator. GRAMER contains a specialized memory hierarchy, where the valuable data (precisely identified through a cost-efficient heuristic) is permanently resident in a high-priority memory while others are maintained in a cache-like memory under a lightweight replacement policy. The specific pipelined processing units are carefully designed to maximize computational parallelism. GRAMER is also equipped with a work-stealing mechanism to reduce load imbalance. We have implemented GRAMER on a Xilinx Alveo U250 accelerator card. Compared with two state-of-the-art CPU-based graph mining systems, Fractal and RStream, running on a 14-core Intel E5-2680 v4 processor, GRAMER achieves not only considerable speedups (1.11 × ~ 129.95 ) but also significant energy savings (5.79 × ~ 678.34×)

FPGA-based graph processing accelerators are nowadays equipped with multiple pipelines for hardware acceleration of graph computations. However, their multi-pipeline efficiency can suffer greatly from the considerable overheads caused by the read/write conflicts in their on-chip BRAM from different pipelines, leading to significant performance degradation and poor scalability. In this article, we investigate the underlying causes behind such inter-pipeline read/write conflicts by focusing on multi-pipeline FPGAs for accelerating Sparse Matrix Vector Multiplication (SpMV) arising in graph processing. We exploit our key insight that the problem of eliminating inter-pipeline read/write conflicts for SpMV can be formulated as one of solving a row- and column-wise tiling problem for its associated adjacency matrix. However, how to partition a sparse adjacency matrix obtained from any graph with respect to a set of pipelines by both eliminating all the inter-pipeline read/write conflicts and keeping all the pipelines reasonably load-balanced is challenging. We present a conflict-free scheduler, WaveScheduler, that can dispatch different sub-matrix tiles to different pipelines without any read/write conflict. We also introduce two optimizations that are specifically tailored for graph processing, “degree-aware vertex index renaming” for improving load balancing and “data re-organization” for enabling sequential off-chip memory access, for all the pipelines. Our evaluation on Xilinx®Alveo™ U250 accelerator card with 16 pipelines shows that WaveScheduler can achieve up to 3.57 GTEPS, running much faster than native scheduling and two state-of-the-art FPGA-based graph accelerators (by 6.48× for “native,” 2.54× for HEGP, and 2.11× for ForeGraph), on average. In particular, these performance gains also scale up significantly as the number of pipelines increases.

Deep Neural Networks (DNNs) are now increasingly adopted in a variety of Artificial Intelligence (AI) applications. Meantime, more and more DNNs are moving from cloud to the mobile devices, as emerging AI chips are integrated into mobiles. Therefore, the DNN models can be deployed in the cloud, on the mobile devices, or even mobile-cloud coordinate processing, making it a big challenge to select an optimal deployment strategy under specific objectives. This article proposes a DNN tuning framework, i.e., DNNTune, that can provide layer-wise behavior analysis across a number of platforms. Using DNNTune, this article further selects 13 representative DNN models, including CNN, LSTM, and MLP, and three mobile devices ranging from low-end to high-end, and two AI accelerator chips to characterize the DNN models on these devices to further assist users finding opportunities for mobile-cloud coordinate computing. Our experimental results demonstrate that DNNTune can find a coordinated deployment achieving up to 1.66× speedup and 15× energy saving comparing with mobile-only and cloud-only deployment.

The increasing computational cost of deep neural network models limits the applicability of intelligent applications on resource-constrained edge devices. While a number of neural network pruning methods have been proposed to compress the models, prevailing approaches focus only on parametric operators (e.g., convolution), which may miss optimization opportunities. In this article, we present a novel fusion-catalyzed pruning approach, called FuPruner, which simultaneously optimizes the parametric and nonparametric operators for accelerating neural networks. We introduce an aggressive fusion method to equivalently transform a model, which extends the optimization space of pruning and enables nonparametric operators to be pruned in a similar manner as parametric operators, and a dynamic filter pruning method is applied to decrease the computational cost of models while retaining the accuracy requirement. Moreover, FuPruner provides configurable optimization options for controlling fusion and pruning, allowing much more flexible performance-accuracy tradeoffs to be made. Evaluation with state-of-the-art residual neural networks on five representative intelligent edge platforms, Jetson TX2, Jetson Nano, Edge tensor processing unit, neural compute stick, and neural compute stick 2, demonstrates the effectiveness of our approach, which can accelerate the inference of models on CIFAR-10 and ImageNet datasets.

We present Supa, a value-flow-based demand-driven flow- and context-sensitive pointer analysis with strong updates for C and C++ programs. Supa enables computing points-to information via value-flow refinement, in environments with small time and memory budgets. We formulate Supa by solving a graph-reachability problem on an inter-procedural value-flow graph representing a program's def-use chains, which are pre-computed efficiently but over-approximately. To answer a client query (a request for a variable's points-to set), Supa reasons about the flow of values along the pre-computed def-use chains sparsely (rather than across all program points), by performing only the work necessary for the query (rather than analyzing the whole program). In particular, strong updates are performed to filter out spurious def-use chains through value-flow refinement as long as the total budget is not exhausted. We have implemented Supa on top of LLVM (4.0.0) together with a comprehensive micro-benchmark suite after a years-long effort (consisting of around 400 test cases, including hand-written ones and the ones extracted from real programs). We have evaluated Supa by choosing uninitialized pointer detection and C++ virtual table resolution as two major clients, using 24 real-world programs including 18 open-source C programs and 6 large CPU2000/2006 C++ benchmarks. For uninitialized pointer client, Supa achieves improved precision as the analysis budget increases, with its flow-sensitive (context-insensitive) analysis reaching 97.4 percent of that achieved by whole-program Sparse Flow-Sensitive analysis (SFS) by consuming about 0.18 seconds and 65 KB of memory per query, on average (with a budget of at most 10,000 value-flow edges per query). With context-sensitivity also considered, Supa becomes more precise for some programs but also incurs more analysis times. To further demonstrate the effectiveness of Supa, we have also evaluated Supa in resolving C++ virtual tables by querying the function pointers at every virtual callsite. Compared to analysis without strong updates for heap objects, Supa's demand-driven context-sensitive strong update analysis reduces 7.35 percent spurious virtual table targets with only 0.4 secs per query, on average.

OpenCL offers code portability but no performance portability. Given an OpenCL program X specifically written for one platform P, existing OpenCL compilers, which usually optimize its host and kernel codes individually, often yield poor performance for another platform Q. Instead of obtaining a performance-improved version of X for Q via manual tuning, we aim to achieve this automatically by a source-to-source OpenCL compiler framework, PPOpenCL. By fusing X's host and kernel thread codes (with the operations in different work-items in the same work-group represented explicitly), we are able to apply data flow analyses, and subsequently, performance-enhancing optimizations on a fused control flow graph specifically for platform Q. Validation against OpenCL benchmarks shows that PPOpenCL (implemented in Clang 3.9.1) can achieve significantly improved portable performance on seven platforms considered.

Fuzzing is a promising technique for detecting security vulnerabilities. Newly developed fuzzers are typically evaluated in terms of the number of bugs found on vulnerable programs/binaries. However, existing corpora usually do not capture the features that prevent fuzzers from finding bugs, leading to ambiguous conclusions on the pros and cons of the fuzzers evaluated. In this paper, we propose to address the above problem by generating corpora based on search-hampering features. As a proof-of-concept, we designed FEData, a prototype corpus that currently focuses on three search-hampering features to generate vulnerable programs for fuzz testing. Unlike existing corpora that can only answer "how", FEData can also further answer "why" by exposing (or understanding) the reasons for the identified weaknesses in a fuzzer. The "why" information serves as the key to the improvement of fuzzers. Based on the "why" information, our FEData programs enabled us to identify the weakness of AFLFast, called cycle explosion, behind. We further developed an improved version of AFLFast, called AFLFast+, which has overcome the cycle explosion problem. AFLFast+ retains the efficiency of AFLFast in path search while maintaining or even surpassing the bug-finding capability of AFL for the corpus evaluated.

Automated Program Repair (APR) faces a key challenge in efficiently generating correct patches from a potentially infinite solution space. Existing approaches, which attempt to reason about the entire solution space, can be ineffective (by often producing no plausible patches at all) and imprecise (by often producing plausible but incorrect patches). We present VFIX, a new value-flow-guided APR approach, to fix null pointer exception (NPE) bugs by considering a substantially reduced solution space in order to greatly increase the number of correct patches generated. By reasoning about the data and control dependences in the program, VFIX can identify bug-relevant repair statements more accurately and generate more correct repairs than before. VFIX outperforms a set of 8 state-of-the-art APR tools in fixing the NPE bugs in Defects4j in terms of both precision (by correctly fixing 3 times as many bugs as the most precise one and 50% more than all the bugs correctly fixed by these 8 tools altogether) and efficiency (by producing a correct patch in minutes instead of hours).

Unlike Java, Android provides a rich set of APIs to support a hybrid concurrency system, which consists of both Java threads and an event queue mechanism for dispatching asynchronous events. In this model, concurrency errors often manifest themselves in the form of order violations. An order violation occurs when two events access the same shared object in an incorrect order, causing unexpected program behaviors (e.g., null pointer dereferences). This paper presents SARD, a static analysis tool for detecting both intra-and inter-thread use-after-free (UAF) order violations, when a pointer is dereferenced (used) after it no longer points to any valid object, through systematic modeling of Android's concurrency mechanism. We propose a new flow-and context-sensitive static happens-before (HB) analysis to reason about the interleavings between two events to effectively identify precise HB relations and eliminate spurious event interleavings. We have evaluated SARD by comparing with NADROID, a state-of-the-art static order violation detection tool for Android. SARD outperforms NADROID in terms of both precision (by reporting three times fewer false alarms than NADROID given the same set of apps used by NADROID) and efficiency (by running two orders of magnitude faster than NADROID).

For performance reasons, C++, albeit unsafe, is often the programming language of choice for developing software infrastructures. A serious type of security vulnerability in C++ programs is type confusion, which may lead to program crashes and control flow hijack attacks. While existing mitigation solutions almost exclusively rely on dynamic analysis techniques, which suffer from low code coverage and high overhead, static analysis has rarely been investigated. This paper presents TCD, a static type confusion detector built on top of a precise demand-driven field-, context-and flow-sensitive pointer analysis. Unlike existing pointer analyses, TCD is type-aware as it not only preserves the type information in the pointed-to objects but also handles complex language features of C++ such as multiple inheritance and placement new, making it therefore possible to reason about type casting in C++ programs. We have implemented TCD in LLVM and evaluated it using seven C++ applications (totaling 526,385 lines of C++ code) from Qt, a widely-adopted C++ toolkit for creating GUIs and cross-platform software. TCD has found five type confusion bugs, including one reported previously in prior work and four new ones, in under 7.3 hours, with a low false positive rate of 28.2%.

The unsafe language features of C, such as low-level control of memory, often lead to memory errors, which can result in silent data corruption, security vulnerabilities, and program crashes. Dynamic analysis tools, which have been widely used for detecting memory errors at runtime, usually perform instrumentation at the IR-level or binary-level. However, their underlying non-source-level instrumentation techniques have three inherent limitations: optimization sensitivity, platform dependence and DO-178C non-compliance. Due to optimization sensitivity, these tools are used to trade either performance for effectiveness by compiling the program at -O0 or effectiveness for performance by compiling the program at a higher optimization level, say, -O3.

COTS software products are developed extensively on top of OSS projects, resulting in OSS reuse vulnerabilities. To detect such vulnerabilities, finding OSS reuses in COTS software has become imperative. While scalable to tens of thousands of OSS projects, existing binary-to-source matching approaches are severely imprecise in analyzing COTS software products, since they support only a limited number of code features, compute matching scores only approximately in measuring OSS reuses, and neglect the code structures in OSS projects. We introduce a novel binary-to-source matching approach, called B2SFINDER1, to address these limitations. First of all, B2SFINDER can reason about seven kinds of code features that are traceable in both binary and source code. In order to compute matching scores precisely, B2SFINDER employs a weighted feature matching algorithm that combines three matching methods (for dealing with different code features) with two importance-weighting methods (for computing the weight of an instance of a code feature in a given COTS software application based on its specificity and occurrence frequency). Finally, B2SFINDER identifies different types of code reuses based on matching scores and code structures of OSS projects. We have implemented B2SFINDER using an optimized data structure. We have evaluated B2SFINDER using 21991 binaries from 1000 popular COTS software products and 2189 candidate OSS projects. Our experimental results show that B2SFINDER is not only precise but also scalable. Compared with the state ofthe art, B2SFINDER has successfully found up to 2.15× as many reuse cases in 53.85 seconds per binary file on average. We also discuss how B2SFINDER can be leveraged in detecting OSS reuse vulnerabilities in practice.

The IFDS algorithm can be compute-and memoryintensive for some large programs, often running for a long time (more than expected) or terminating prematurely after some time and/or memory budgets have been exhausted. In the latter case, the corresponding IFDS data-flow analyses may suffer from false negatives and/or false positives. To improve this, we introduce a sparse alternative to the traditional IFDS algorithm. Instead of propagating the data-flow facts across all the program points along the program’s (interprocedural) control flow graph, we propagate every data-flow fact directly to its next possible use points along its own sparse control flow graph constructed on the fly, thus reducing significantly both the time and memory requirements incurred by the traditional IFDS algorithm. In our evaluation, we compare FLOWDROID, a taint analysis performed by using the traditional IFDS algorithm, with our sparse incarnation, SPARSEDROID, on a set of 40 Android apps selected. For the time budget (5 hours) and memory budget (220GB) allocated per app, SPARSEDROID can run every app to completion but FLOWDROID terminates prematurely for 9 apps, resulting in an average speedup of 22.0x. This implies that when used as a market-level vetting tool, SPARSEDROID can finish analyzing these 40 apps in 2.13 hours (by issuing 228 leak warnings) while FLOWDROID manages to analyze only 30 apps in the same time period (by issuing only 147 leak warnings).

Hyper-blocks can significantly improve instruction level parallelism on a wide range of super-scalar and VLIW processors. However, most hyper-block construction approaches aim at minimizing the average-case execution time of a program. In real-time embedded systems, minimizing the worst-case execution time (WCET) of a program is the primary goal of an optimizing compiler. We investigate the hyper-block construction problem for a program executed on a clustered VLIW processor such that the WCET of the program is minimized, and propose a novel heuristic approach considering tail duplications. Our approach is underpinned by a novel priority scheme and a precise tail duplication cost model for computing the WCET of a program. We have implemented our approach in Trimaran 4.0, and compared it with the state-of-the-art approach by using a set of 8 benchmark suites. The experimental results show that our approach achieves the maximum WCET improvement of 20.37% and the average WCET improvement of 11.59%, respectively.

We present ISymb an incremental symbolic inference framework for probabilistic programs in situations when some loop-manipulated array data, upon which their probabilistic models are conditioned, undergoes small changes. To tackle the path explosion challenge, ISymb is intra-procedurally path-sensitive except that it conducts a “meet-over-all-paths” analysis within an iteration of a loop (conditioned on some observed array data). By recomputing only the probability distributions for the paths affected, ISymb avoids expensive symbolic inference from scratch while also being precision-preserving. Our evaluation with a set of existing benchmarks shows that ISymb can lead to orders of magnitude performance improvements compared to its non-incremental counterpart (under small changes in observed array data).

Existing Android testing tools, such as Monkey, generate a large quantity and a wide variety of user events to expose latent GUI bugs in Android apps. However, even if a bug is found, a majority of the events thus generated are often redundant and bug-irrelevant. In addition, it is also time-consuming for developers to localize and replay the bug given a long and tedious event sequence (trace).

Object-sensitivity is widely used as a context abstraction for computing the points-to information context-sensitively for object-oriented languages like Java. Due to the combinatorial explosion of contexts in large programs, k -object-sensitive pointer analysis (under k -limiting), denoted k -obj, is scalable only for small values of k , where k ⩽2 typically. A few recent solutions attempt to improve its efficiency by instructing k -obj to analyze only some methods in the program context-sensitively, determined heuristically by a pre-analysis. While already effective, these heuristics-based pre-analyses do not provide precision guarantees, and consequently, are limited in the efficiency gains achieved. We introduce a radically different approach, Eagle, that makes k -obj run significantly faster than the prior art while maintaining its precision. The novelty of Eagle is to enable k -obj to analyze a method with partial context-sensitivity, i.e., context-sensitively for only some of its selected variables/allocation sites. Eagle makes these selections during a lightweight pre-analysis by reasoning about context-free-language (CFL) reachability at the level of variables/objects in the program, based on a new CFL-reachability formulation of k -obj. We demonstrate the advances made by Eagle by comparing it with the prior art in terms of a set of popular Java benchmarks and applications.

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

We introduce P oker , a permutation-based approach for vectorizing multiple queries over B + -trees. Our key insight is to combine vector loads and path-encoding-based permutations to alleviate memory latency while keeping the number of key comparisons needed for a query to a minimum. Implemented as a C++ template library, P oker represents a general-purpose solution for vectorizing the queries over indexing trees on multi-core processors equipped with SIMD units. For a set of five representative benchmarks evaluated with 24 configurations each, P oker outperforms the state of the art by 2.11x with one single thread and 2.28x with eight threads on an Intel Broadwell processor that supports 256-bit AVX2, on average. In addition, strip-mining queries will further improve P oker ’s performance by 1.21x (with one single thread) and 1.31x (with eight threads), on average.

Java reflection has been widely used in a variety of applications and frameworks. It allows a software system to inspect and change the behaviour of its classes, interfaces, methods, and fields at runtime, enabling the software to adapt to dynamically changing runtime environments. However, this dynamic language feature imposes significant challenges to static analysis, because the behaviour of reflection-rich software is logically complex and statically hard to predict. As a result, existing static analysis tools either ignore reflection or handle it partially, resulting in missed, important behaviours, i.e., unsound results. Therefore, improving or even achieving soundness in static reflection analysis—an analysis that infers statically the behaviour of reflective code—will provide significant benefits to many analysis clients, such as bug detectors, security analyzers, and program verifiers. In this article, we provide a comprehensive understanding of Java reflection through examining its underlying concept, API, and real-world usage, and, building on this, we introduce a new static approach to resolving Java reflection effectively in practice. We have implemented our reflection analysis in an open-source tool, called S OLAR , and evaluated its effectiveness extensively with large Java programs and libraries. Our experimental results demonstrate that S OLAR is able to (1) resolve reflection more soundly than the state-of-the-art reflection analyses; (2) automatically and accurately identify the parts of the program where reflection is resolved unsoundly or imprecisely; and (3) guide users to iteratively refine the analysis results by using lightweight annotations until their specific requirements are satisfied.

Existing data race detectors can witness race conditions for their occurrence but few can also identify the fundamental reasons for their understanding. In this paper, we present a new debugging framework for providing a concise schedule that can help not only witness but also understand data race. The key innovation of this work is to integrate dynamic slicing into constraint solving technique. We propose to use race manifestation (a fraction of memory accesses) to characterize buggy behaviors arising from data races. By encoding race manifestation constraints, existing constraint solving system is enabled to generate the buggy-behavior-exposing schedule, which is further simplified to a minimum as root cause via a tailored data race slicing technique further proposed.

We propose POKER, a permutation-based vectorization approach for vectorizing multiple queries over B+-trees. Our key insight is to combine vector loads and path-encoding-based permutations to alleviate memory latency while keeping the number of key comparisons needed for a query to a minimum. Implemented as a C++ template library, POKER represents a general-purpose solution for vectorizing the queries over indexing trees on multi-core processors equipped with SIMD units. For a set of five representative benchmarks evaluated with 24 configurations each, POKER outperforms the state-of-the-art by 2.11x with one single thread and 2.28x with eight threads on an Intel Broadwell processor that supports 256-bit AVX2, on average.

May-Happen-in-Parallel (MHP) analysis computes whether two statements in a multi-threaded program may execute concurrently or not. It works as a basis for many analyses and optimization techniques of concurrent programs. This paper proposes a novel approach for MHP analysis, by statically computing vector clocks. Static vector clocks extend the classic vector clocks algorithm to handle the complex control flow structures in static analysis, and we have developed an efficient context-sensitive algorithm to compute them. To the best of our knowledge, this is the first attempt to compute vector clocks statically. Using static vector clocks, we can drastically improve the efficiency of existing MHP analyses, without loss of precision: the performance speedup can be up to 1828X, with a much smaller memory footprint (reduced by up to 150X). We have implemented our analysis in a static data race detector, and experimental results show that our MHP analysis can help remove up to 88% of spurious data race pairs.

As DNNs gain popularity in modern datacenters, it becomes imperative to revisit compiler optimizations for DNNs in a colocation scenario. Loop tiling turns out to be the most significant compiler optimization, since DNNs typically apply a series of matrix computations iteratively to a massive amount of data.

Zero-day Use-After-Free (UAF) vulnerabilities are increasingly popular and highly dangerous, but few mitigations exist. We introduce a new pointer-analysis-based static analysis, CRed, for finding UAF bugs in multi-MLOC C source code efficiently and effectively. CRed achieves this by making three advances: (i) a spatio-temporal context reduction technique for scaling down soundly and precisely the exponential number of contexts that would otherwise be considered at a pair of free and use sites, (ii) a multi-stage analysis for filtering out false alarms efficiently, and (iii) a path-sensitive demand-driven approach for finding the points-to information required.

Existing static analyses model activity transitions in Android apps context-insensitively, making it impossible to distinguish different activity launch modes, reducing the pointer analysis precision for an activity's callbacks, and potentially resulting in infeasible activity transition paths. In this paper, we introduce Chime, a launch-mode-aware context-sensitive activity transition analysis that models different instances of an activity class according to its launch mode and the transitions between activities context-sensitively, by working together with an object-sensitive pointer analysis.

The frequent release of Android OS and its various versions bring many compatibility issues to Android Apps. This paper studies and addresses such evolution-induced compatibility problems. We conduct an extensive empirical study over 11 different Android versions and 4,936 Android Apps. Our study shows that there are drastic API changes between adjacent Android versions, with averagely 140.8 new types, 1,505.6 new methods, and 979.2 new fields being introduced in each release. However, the Android Support Library (provided by the Android OS) only supports less than 23% of the newly added methods, with much less support for new types and fields. As a result, 91.84% of Android Apps write additional code to support different OS versions. Furthermore, 88.65% of the supporting codes share a common pattern, which directly compares variable android.os.Build.VERSION.SDK_INT with a constant version number, to use an API of particular versions.

The Android multitasking mechanism can be plagued with app switching attacks, in which a malicious app replaces the legitimate top activity of the focused app with one of its own, thus mounting, e.g., phishing and denial-of-service attacks. Existing market-level defenses are still ineffective, as static analysis is fundamentally unable to reason about the intention of an app and dynamic analysis has low coverage.

Summary Reflection poses grave problems for static security analysis, despite its widespread use in Android apps. In general, string inference has been mainly used to handle reflection, resulting in significantly missed security vulnerabilities. In this work, we bring forward the ubiquity of incomplete information environments (IIEs) for Android apps, where some critical dataflows are missing during static analysis and the need for resolving reflective calls under IIEs. We present Ripple, the first IIE‐aware static reflection analysis for Android apps that resolves reflective calls more soundly than string inference. Validation with 17 popular Android apps from Google Play demonstrates the effectiveness of Ripple in discovering reflective targets with a low false positive rate (due to its trade‐off made among soundness, precision, and scalability). As a result, Ripple enables FlowDroid, a taint analysis for Android apps, to find hundreds of sensitive data leakages that would otherwise be missed. As a fundamental analysis, Ripple will be valuable for many security analysis clients, since more program behaviors can now be analyzed under IIEs.

Compiler-based vectorization represents a promising solution to automatically generate code that makes efficient use of modern CPUs with SIMD extensions. Two main auto-vectorization techniques, superword-level parallelism vectorization (SLP) and loop-level vectorization (LLV), require precise dependence analysis on arrays and structs to vectorize isomorphic scalar instructions (in the case of SLP) and reduce dynamic dependence checks at runtime (in the case of LLV). The alias analyses used in modern vectorizing compilers are either intra-procedural (without tracking inter-procedural data-flows) or inter-procedural (by using field-sensitive models, which are too imprecise in handling arrays and structs). This article proposes an inter-procedural L oop-oriented P ointer A nalysis for C, called L pa , for analyzing arrays and structs to support aggressive SLP and LLV optimizations effectively. Unlike field-insensitive solutions that pre-allocate objects for each memory allocation site, our approach uses a lazy memory model to generate access-based location sets based on how structs and arrays are accessed. L pa can precisely analyze arrays and nested aggregate structures to enable SIMD optimizations for large programs. By separating the location set generation as an independent concern from the rest of the pointer analysis, L pa is designed so that existing points-to resolution algorithms (e.g., flow-insensitive and flow-sensitive pointer analysis) can be reused easily. We have implemented L pa fully in the LLVM compiler infrastructure (version 3.8.0). We evaluate L pa by considering SLP and LLV, the two classic vectorization techniques, on a set of 20 C and Fortran CPU2000/2006 benchmarks. For SLP, L pa outperforms LLVM’s BasicAA and ScevAA by discovering 139 and 273 more vectorizable basic blocks, respectively, resulting in the best speedup of 2.95% for 173.applu. For LLV, LLVM introduces totally 551 and 652 static bound checks under BasicAA and ScevAA, respectively. In contrast, L pa has reduced these static checks to 220, with an average of 15.7 checks per benchmark, resulting in the best speedup of 7.23% for 177.mesa.

Typestate analysis relies on pointer analysis for detecting temporal memory safety errors, such as use-after-free (UAF). For large programs, scalable pointer analysis is usually imprecise in analyzing their hard "corner cases", such as infeasible paths, recursion cycles, loops, arrays, and linked lists. Due to a sound over-approximation of the points-to information, a large number of spurious aliases will be reported conservatively, causing the corresponding typestate analysis to report a large number of false alarms. Thus, the usefulness of typestate analysis for heap-intensive clients, like UAF detection, becomes rather limited, in practice.

Despite its widespread use in Android apps, reflection poses graving problems for static security analysis. Currently, string inference is applied to handle reflection, resulting in significantly missed security vulnerabilities. In this paper, we bring forward the ubiquity of incomplete information environments (IIEs) for Android apps, where some critical data-flows are missing during static analysis, and the need for resolving reflective calls under IIEs. We present Ripple, the first IIE-aware static reflection analysis for Android apps that resolves reflective calls more soundly than string inference. Validation with 17 popular Android apps from Google Play demonstrates the effectiveness of Ripple in discovering reflective targets with a low false positive rate. As a result, Ripple enables FlowDroid to find hundreds of sensitive data leakages that would otherwise be missed.

Reflection, which is widely used in practice and abused by many security exploits, poses a significant obstacle to program analysis. Reflective calls can be analyzed statically or dynamically. Static analysis is more sound but also more imprecise (by introducing many false reflective targets and thus affecting its scalability). Dynamic analysis can be precise but often miss many true reflective targets due to low code coverage.We introduce MIRROR, the first automatic reflection analysis for Java that increases significantly the code coverage of dynamic analysis while keeping false reflective targets low. In its static analysis, a novel reflection-oriented slicing technique is applied to identify a small number of small path-based slices for a reflective call so that different reflective targets are likely exercised along these different paths. This preserves the soundness of pure static reflection analysis as much as possible, improves its scalability, and reduces substantially its false positive rate. In its dynamic analysis, these slices are executed with automatically generated test cases to report the reflective targets accessed. This significantly improves the code coverage of pure dynamic analysis. We evaluate MIRROR against a state-of-the-art dynamic reflection analysis tool, TAMIFLEX, by using 10 large real-world Java applications. MIRROR detects 12.5% - 933.3% more reflective targets efficiently (in 362.8 seconds on average) without producing any false positives. These new targets enable 5 - 174949 callgraph edges to be reachable in the application code.

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

Mainstream points-to analysis techniques for object-oriented languages rely predominantly on the allocation-site abstraction to model heap objects. We present MAHJONG, a novel heap abstraction that is specifically developed to address the needs of an important class of type-dependent clients, such as call graph construction, devirtualization and may-fail casting. By merging equivalent automata representing type-consistent objects that are created by the allocation-site abstraction, MAHJONG enables an allocation-site-based points-to analysis to run significantly faster while achieving nearly the same precision for type-dependent clients.

In real-time embedded system design, one major goal is to construct a feasible schedule. Whether a feasible schedule exists depends on the Worst-Case Execution Time (WCET) of each task. Consequently, it is important to minimize the WCET of each task. We investigate the problem of instruction scheduling and register allocation for a program executed on a clustered Very Long Instruction Word (VLIW) processor such that the WCET of the program is minimized, and propose a novel, unified instruction scheduling and register allocation heuristic approach. Our heuristic approach is underpinned by a set of novel techniques, including spanning graph-based WCET-aware live range splitting, WCET-aware dynamic register pressure control, WCET-aware basic block prioritization for performing integrated instruction scheduling and register allocation, and WCET-aware spill code handling. We have implemented our approach in Trimaran 4.0, and compared it with the state-of-the-art approach by using a set of 20 benchmarks. The experimental results show that our approach achieves the maximum WCET improvement of 29.61% and the average WCET improvement of 10.23%, respectively.

Phase change memory (PCM) is a promising DRAM alternative because of its non-volatility, high density, low standby power and close-to-DRAM performance. These features make PCM an attractive solution to optimize the management of NAND flash memory in embedded systems. However, PCM's limited write endurance hinders its application in embedded systems. Therefore, how to manage flash memory with PCM-particularly guarantee PCM a reasonable lifetime-becomes a challenging issue. In this paper, we propose to partially replace DRAM using PCM to optimize the management of flash memory metadata for better system reliability in the presence of power failure and system crash. To prolong PCM's lifetime, we present a write-activity-aware PCM-assisted flash memory management scheme, called PCM-FTL. By differentiating sequential and random I/O behaviors, a novel two-level mapping mechanism and a customized wear-leveling scheme are developed to reduce writes to PCM and extend its lifetime. We evaluate PCM-FTL with a variety of general-purpose and mobile I/O workloads. Experimental results show that PCM-FTL can significantly reduce write activities and achieve an even distribution of writes in PCM with very low overhead.

Due to continuous improvements in the VLSI technologies, the dependability of computing, caused by soft errors, has become increasingly a design challenge. Current protection techniques usually incur significant economic costs, performance degradation or resource consumption. This paper introduces a lightweight software approach for mitigating soft errors. By exploiting the facts that many data values have narrow width or constant bits, indicating that a large fraction of binary bits are unused or constant, we can predict these data values before program execution. First of all, invariants concerning bit-level data widths and values are identified by performing two bitwise data-flow analyses. Based on the bitwise analysis results, the masking operations are inserted to clear the possible errors in the known-value bits for reducing the window of vulnerability. Then the program reliability is improved with minimum penalty. To improve the effectiveness, the covered mask analysis can remove the non-vital masking operations without affecting the dependability. We have implemented our approach in the LLVM compiler. The fault injection experimental results for the MiBench benchmarks indicate that our approach improves the reliability of programs by 8.03% while incurring only 1.61% performance overhead.

This paper presents SVF, a tool that enables scalable and precise interprocedural Static Value-Flow analysis for C programs by leveraging recent advances in sparse analysis. SVF, which is fully implemented in LLVM, allows value-flow construction and pointer analysis to be performed in an iterative manner, thereby providing increasingly improved precision for both. SVF accepts points- to information generated by any pointer analysis (e.g., Andersen’s analysis) and constructs an interprocedural memory SSA form, in which the def-use chains of both top-level and address-taken variables are captured. Such value-flows can be subsequently exploited to support various forms of program analysis or enable more precise pointer analysis (e.g., flow-sensitive analysis) to be performed sparsely. By dividing a pointer analysis into three loosely coupled components: Graph, Rules and Solver, SVF provides an extensible interface for users to write their own solutions easily. SVF is publicly available at http://unsw-corg.github.io/SVF.

For C programs, flow-sensitivity is important to enable pointer analysis to achieve highly usable precision. Despite significant recent advances in scaling flow-sensitive pointer analysis sparsely for sequential C programs, relatively little progress has been made for multithreaded C programs. In this paper, we present FSAM, a new Flow-Sensitive pointer Analysis that achieves its scalability for large Multithreaded C programs by performing sparse analysis on top of a series of thread interference analysis phases. We evaluate FSAM with 10 multithreaded C programs (with more than 100K lines of code for the largest) from Phoenix-2.0, Parsec-3.0 and open-source applications. For two programs, raytrace and x264, the traditional data-flow-based flow-sensitive pointer analysis is un- scalable (under two hours) but our analysis spends just under 5 minutes on raytrace and 9 minutes on x264. For the rest, our analysis is 12x faster and uses 28x less memory.

Existing loop vectorization techniques can exploit either intra- or inter-iteration SIMD parallelism alone in a code region if one part of the region vectorized for one type of parallelism has data dependences (called mixed-parallelism-inhibiting dependences) on the other part of the region vectorized for the other type of parallelism. In this paper, we consider a class of loops that exhibit both types of parallelism (i.e., mixed SIMD parallelism) in its code regions that contain mixed-parallelism-inhibiting data dependences. We present a new compiler approach for exploiting such mixed SIMD parallelism effectively by reducing the data reorganization overhead incurred when one type of parallelism is switched to the other. Our auto-vectorizer is simple and has been implemented in LLVM (3.5.0). We evaluate it on seven benchmarks with mixed SIMD parallelism selected from SPEC and NAS benchmark suites and demonstrate its performance advantages over the state-of-the-art.

Protocol and typestate analyses often report some sequences of statements ending at a program point P that needs to be scrutinized, since P may be erroneous or imprecisely analyzed. Program slicing focuses only on the behavior at P by computing a slice of the program affecting the values at P. In this paper, we propose to restrict our attention to the subset of that behavior at P affected by one or several statement sequences, called a sequential criterion (SC). By leveraging the ordering information in a SC, e.g., the temporal order in a few valid/invalid API method invocation sequences, we introduce a new technique, program tailoring, to compute a tailored program that comprises the statements in all possible execution paths passing through at least one sequence in SC in the given order. With a prototyping implementation, Tailor, we show why tailoring is practically useful by conducting two case studies on seven large real-world Java applications. For program debugging and understanding, Tailor can complement program slicing by removing SC-irrelevant statements. For program analysis, Tailor can enable a pointer analysis, which is unscalable to a program, to perform a more focused and therefore potentially scalable analysis to its specific parts containing hard language features such as reflection.

Energy consumption is increasingly becoming a critical issue in HPC. There is a broad consensus that future exascale-computing will be strongly constrained by energy consumption. Heterogeneous systems usually feature higher energy efficiency than homogeneous ones since the former employ coprocessors that provide higher GFlops/Watt than CPUs. Thus, it is of great importance to better utilize the coprocessors from an energy-efficiency standpoint. Dense LU factorization (LU) is a critical kernel that is widely used to solve dense linear algebra problems. However, existingheterogeneous implementations are typically designed to be CPU-centered, which rely highly on CPUs and thus suffer from large data transfer overheads via PCIe, hurting the energy efficiency of the entire computer system. We present a coprocessor-resident implementation of LU for a heterogeneous platform to improve energy efficiency without impeding performance by relieving the CPUs from performing unnecessary computations and reducing excessive data transfers via PCIe. In addition, several optimizations are judiciously employed to overlap the computation and communication between the CPUs and coprocessors. Validation on the Tianhe-2 supercomputer shows that our LU implementation gains higher performance, achieves higher energy efficiency, and features a better scalability than Intel MKL.

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

Compiler-based auto-vectorization is a promising solution to automatically generate code that makes efficient use of SIMD processors in high performance platforms and embedded systems. Two main auto-vectorization techniques, superword-level parallelism vectorization (SLP) and loop-level vectorization (LLV), re- quire precise dependence analysis on arrays and structs in order to vectorize isomorphic scalar instructions and/or reduce dynamic dependence checks incurred at runtime. The alias analyses used in modern vectorizing compilers are either intra-procedural (without tracking inter-procedural data-flows) or inter-procedural (by using field-insensitive models, which are too imprecise in handling arrays and structs). This paper pro- poses an inter-procedural Loop-oriented Pointer Analysis, called LPA, for analyzing arrays and structs to support aggressive SLP and LLV optimizations. Unlike field-insensitive solutions that pre- allocate objects for each memory allocation site, our approach uses a fine-grained memory model to generate location sets based on how structs and arrays are accessed. LPA can precisely analyze ar- rays and nested aggregate structures to enable SIMD optimizations for large programs. By separating the location set generation as an independent concern from the rest of the pointer analysis, LPA is designed to reuse easily existing points-to resolution algorithms. We evaluate LPA using SLP and LLV, the two classic vectorization techniques on a set of 20 CPU2000/2006 benchmarks. For SLP, LPA enables it to vectorize a total of 133 more basic blocks, with an average of 12.09 per benchmark, resulting in the best speedup of 2.95% for 173.applu. For LLV, LPA has reduced a total of 319 static bound checks, with an average of 22.79 per benchmark, resulting in the best speedup of 7.18% for 177.mesa.

We present a new Strong UPdate Analysis for C programs, called Supa, that enables computing points-to information on-demand via value-flow refinement, in environments with small time and memory budgets such as IDEs. We formulate Supa by solving a graph-reachability problem on a value- flow graph representation of the program, so that strong updates are performed where needed, as long as the total analysis budget is not exhausted. Supa facilitates efficiency and precision tradeoffs by allowing different pointer analyses to be applied in a hybrid multi-stage analysis framework.

Existing vectorization techniques are ineffective for loops that exhibit little loop-level parallelism but some limited superword-level parallelism (SLP). We show that effectively vectorizing such loops requires partial vector operations to be executed correctly and efficiently, where the degree of partial SIMD parallelism is smaller than the SIMD datapath width. We present a simple yet effective SLP compiler technique called P aver (PArtial VEctorizeR), formulated and implemented in LLVM as a generalization of the traditional SLP algorithm, to optimize such partially vectorizable loops. The key idea is to maximize SIMD utilization by widening vector instructions used while minimizing the overheads caused by memory access, packing/unpacking, and/or masking operations, without introducing new memory errors or new numeric exceptions. For a set of 9 C/C++/Fortran applications with partial SIMD parallelism, P aver achieves significantly better kernel and whole-program speedups than LLVM on both Intel’s AVX and ARM’s NEON.

The key to reducing static energy in supercomputers is switching off their unused components. Routers are the major components of a supercomputer. Whether routers can be effectively switched off or not has become the key to static energy management for supercomputers. For many typical applications, the routers in a supercomputer exhibit low utilization. However, there is no effective method to switch the routers off when they are idle. By analyzing the router occupancy in time and space, for the first time, we present a routing-policy guided topology partitioning methodology to solve this problem. We propose topology partitioning methods for three kinds of commonly used topologies (mesh, torus and fat-tree) equipped with the three most popular routing policies (deterministic routing, directionally adaptive routing and fully adaptive routing). Based on the above methods, we propose the key techniques required in this topology partitioning based static energy management in supercomputer interconnection networks to switch off unused routers in both time and space dimensions. Three topology-aware resource allocation algorithms have been developed to handle effectively different job-mixes running on a supercomputer. We validate the effectiveness of our methodology by using Tianhe-2 and a simulator for the aforementioned topologies and routing policies. The energy savings achieved on a subsystem of Tianhe-2 range from 3.8 to 79.7 percent. This translates into a yearly energy cost reduction of up to half a million US dollars for Tianhe-2.

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

Despite their widespread adoption in cloud computing, multicore processors are heavily under-utilized in terms of computing resources. To avoid the potential for negative and unpredictable interference, co-location of a latency-sensitive application with others on the same multicore processor is disallowed, leaving many cores idle and causing low machine utilization. To enable co-location while providing QoS guarantees, it is challenging but important to predict performance interference between co-located applications. We observed that the performance degradation of an application can be represented as a piecewise predictor function of the aggregate pressures on shared resources from all cores. Based on this observation, we propose to adopt regression analysis to build a predictor function for an application. Furthermore, the prediction model thus obtained for an application is able to characterize its contentiousness and sensitivity. Validation using a large number of single-threaded and multi-threaded benchmarks and nine real-world datacenter applications on two different platforms shows that our approach is also precise, with an average error not exceeding 0.4 percent.

Spatial errors (e.g., buffer overflows) continue to be one of the dominant threats to software reliability and security in C/C++ programs. Presently, the software industry typically enforces spatial memory safety by instrumentation. Due to high overheads incurred in bounds checking at runtime, many program inputs cannot be exercised, causing some input-specific spatial errors to go undetected in today's commercial software. This paper introduces a new compile-time approach for reducing bounds checking overheads based on the notion of weakest precondition (WP). The basic idea is to guard a bounds check at a pointer dereference inside a loop, where the WP-based guard is hoisted outside the loop, so that its falsehood implies the absence of out-of-bounds errors at the dereference, thereby avoiding the corresponding bounds check inside the loop. This WP-based approach is applicable to any spatial-error detection approach (in software or hardware or both). To evaluate the effectiveness of our approach, we take SoftBound, a compile-time tool with an open-source implementation in low-level virtual machine (LLVM), as our baseline. SoftBound adopts a pointer-based checking scheme with disjoint metadata, making it a state-of-the-art tool in providing compatible and complete spatial safety for C. Our new tool, called WPBound, is a refined version of SoftBound, also implemented in LLVM, by incorporating our WP-based compiler approach comprising both intra and interprocedural optimizations. For a set of 20 C benchmarks selected from SPEC and MiBench,WPBound reduces the average runtime overhead of SoftB ound from 77% to 47% (by a reduction of 39%), with small code size increases.

Asymmetric multicore processors (AMPs) have been proposed as an energy-efficient alternative to symmetric mul-ticore processors (SMPs). However, AMPs derive their performance from core specialization, which requires co-running applications to be scheduled to run on their most appropriate core types. Despite extensive research on AMP scheduling, developing an effective scheduling algorithm remains challenging. Contention for shared resources is a key performance-limiting factor, which often renders existing contention-free scheduling algorithms ineffective. We introduce a contention-aware scheduling algorithm for ARM's big.LITTLE, a commercial AMP platform. Our algorithm comprises an offline stage and an online stage. The offline stage builds a performance interference model for an application by training it with a set of co-running applications. Guided by this model, the online stage schedules a workload by assigning its applications to their most appropriate core types in order to minimize the performance degradation caused by contention for shared resources. Our model can accurately predict the performance degradation of an application when co-running with other applications with an average prediction error of 9.60%. Compared with the default scheduler provided for ARM's big.LITTLE and the speedup-factor-driven scheduler, our contention-aware scheduler can improve overall system performance by up to 28.32% and 28.51%, respectively.

The C programming language continues to play an essential role in the development of system software. May-Happen-in-Parallel (MHP) analysis is the basis of many other analyses and optimisations for concurrent programs. Existing MHP analyses that work well for programming languages such as X10 are often not effective for C (with Pthreads). This paper presents a new MHP algorithm for C that operates at the granularity of code regions rather than individual statements in a program. A flow-sensitive Happens-Before (HB) analysis is performed to account for fork-join semantics of pthreads on an interprocedural thread-sensitive control flow graph representation of a program, enabling the HB relations among its statements to be discovered. All the statements that share the same HB properties are then grouped into one region. As a result, computing the MHP information for all pairs of statements in a program is reduced to one of inferring the HB relations from among its regions. We have implemented our algorithm in LLVM-3.5.0 and evaluated it using 14 programs from the SPLASH2 and PARSEC benchmark suites. Our preliminary results show that our approach is more precise than two existing MHP analyses yet computationally comparable with the fastest MHP analysis.

This paper presents the design and implementation of a highly efficient Double-precision General Matrix Multiplication (DGEMM) based on Open BLAS for 64-bit ARMv8 eight-core processors. We adopt a theory-guided approach by first developing a performance model for this architecture and then using it to guide our exploration. The key enabler for a highly efficient DGEMM is a highly-optimized inner kernel GEBP developed in assembly language. We have obtained GEBP by (1) maximizing its compute-to-memory access ratios across all levels of the memory hierarchy in the ARMv8 architecture with its performance-critical block sizes being determined analytically, and (2) optimizing its computations through exploiting loop unrolling, instruction scheduling and software-implemented register rotation and taking advantage of A64 instructions to support efficient FMA operations, data transfers and prefetching. We have compared our DGEMM implemented in Open BLAS with another implemented in ATLAS (also in terms of a highly-optimized GEBP in assembly). Our implementation outperforms the one in ALTAS by improving the peak performance (efficiency) of DGEMM from 3.88 Gflops (80.9%) to 4.19 Gflops (87.2%) on one core and from 30.4 Gflops (79.2%) to 32.7 Gflops (85.3%) on eight cores. These results translate into substantial performance (efficiency) improvements by 7.79% on one core and 7.70% on eight cores. In addition, the efficiency of our implementation on one core is very close to the theoretical upper bound 91.5% obtained from micro-benchmarking. Our parallel implementation achieves good performance and scalability under varying thread counts across a range of matrix sizes evaluated.

Despite the widespread adoption of heterogeneous clusters in modern data centers, modeling heterogeneity is still a big challenge, especially for large-scale MapReduce applications. In a CPU/GPU hybrid heterogeneous cluster, allocating more computing resources to a MapReduce application does not always mean better performance, since simultaneously running CPU and GPU tasks will contend for shared resources.

This paper presents an on-the-fly register allocator which dynamically detects and utilises lifetime holes for clustered VLIW processors. A lifetime hole is an interval in which a variable does not contain a valid value. A register holding a lifetime hole can be allocated to another variable whose live range fits in the lifetime hole, leading to more efficient utilisation of registers. We propose efficient techniques for dynamically utilising lifetime holes and incorporate these techniques into our on-the-fly register allocator. We have simulated our register allocator and a linear scan register allocator without considering lifetime holes by using the MediaBench II benchmark suite. Our simulation results show that our register allocator reduces the number of spills by 12.5%, 11.7%, 12.7%, for three different processor models, respectively.

This paper presents the first parallel implementation of pointer analysis with Context-Free Language (CFL) reachability, an important foundation for supporting demand queries in compiler optimisation and software engineering. Formulated as a graph traversal problem (often with context- and field-sensitivity for desired precision) and driven by queries (issued often in batch mode), this analysis is non-trivial to parallelise. We introduce a parallel solution to the CFL-reachability-based pointer analysis, with context- and field-sensitivity. We exploit its inherent parallelism by avoiding redundant graph traversals with two novel techniques, data sharing and query scheduling. With data sharing, paths discovered in answering a query are recorded as shortcuts so that subsequent queries will take the shortcuts instead of re-traversing its associated paths. With query scheduling, queries are prioritised according to their statically estimated dependences so that more redundant traversals can be further avoided. Evaluated using a set of 20 Java programs, our parallel implementation of CFL-reachability-based pointer analysis achieves an average speedup of 16.2X over a state-of-the-art sequential implementation on 16 CPU cores.

Spatial errors (e.g., Buffer overflows) continue to be one of the dominant threats to software reliability and security in C/C++ programs. Presently, the software industry typically enforces spatial memory safety by instrumentation. Due to high overheads incurred in bounds checking at runtime, many program inputs cannot be exercised, causing some input-specific spatial errors to go undetected in today's commercial software. This paper introduces a new compile-time optimisation for reducing bounds checking overheads based on the notion of Weakest Precondition (WP). The basic idea is to guard a bounds check at a pointer dereference inside a loop, where the WP-based guard is hoisted outside the loop, so that its falsehood implies the absence of out-of-bounds errors at the dereference, thereby avoiding the corresponding bounds check inside the loop. This WP-based optimisation is applicable to any spatial-error detection approach (in software or hardware or both). To evaluate the effectiveness of our optimisation, we take SOFTBOUND, a compile-time tool with an open-source implementation in LLVM, as our baseline. SOFTBOUND adopts a pointer-based checking approach with disjoint metadata, making it a state-of-the-art tool in providing compatible and complete spatial safety for C. Our new tool, called WPBOUND, is a refined version of SOFTBOUND, also implemented in LLVM, by incorporating our WP-based optimisation. For a set of 12 SPEC C benchmarks evaluated, WPBOUND reduces the average (geometric mean) slowdown of SOFTBOUND from 71% to 45% (by a reduction of 37%), with small code size increases.

Because of its high precision as a flow-insensitive pointer analysis, Andersen's analysis has been deployed in some modern optimising compilers. To obtain improved precision, we describe how to add context sensitivity on top of Andersen's analysis. The resulting analysis, called ICON, is efficient to analyse large programs while being sufficiently precise to drive compiler optimisations. Its novelty lies in summarising the side effects of a procedure by using one transfer function on virtual variables that represent fully parameterised locations accessed via its formal parameters. As a result, a good balance between efficiency and precision is made, resulting in ICON that is more powerful than a 1-callsite-sensitive analysis and less so than a call-path-sensitive analysis (when the recursion cycles in a program are collapsed in all cases). We have compared ICON with FULCRA, a state of the art Andersen's analysis that is context sensitive by acyclic call paths, in Open64 (with recursion cycles collapsed in both cases) using the 16 C/C++ benchmarks in SPEC2000 (totalling 600 KLOC) and 5 C applications (totalling 2.1 MLOC). Our results demonstrate scalability of ICON and lack of scalability of FULCRA. FULCRA spends over 2 h in analysing SPEC2000 and fails to run to completion within 5 h for two of the five applications tested. In contrast, ICON spends just under 7 min on the 16 benchmarks in SPEC2000 and just under 26 min on the same two applications. For the 19 benchmarks analysable by FULCRA, ICON is nearly as accurate as FULCRA in terms of the quality of the built Static Single Assignment (SSA) form and the precision of the discovered alias information. Copyright © 2013 John Wiley & Sons, Ltd.

We introduce a static detector, Saber, for detecting memory leaks in C programs. Leveraging recent advances on sparse pointer analysis, Saber is the first to use a full-sparse value-flow analysis for detecting memory leaks statically. Saber tracks the flow of values from allocation to free sites using a sparse value-flow graph (SVFG) that captures def-use chains and value flows via assignments for all memory locations represented by both top-level and address-taken pointers. By exploiting field-, flow- and context-sensitivity during different phases of the analysis, Saber detects memory leaks in a program by solving a graph reachability problem on its SVFG. Saber, which is fully implemented in Open64, is effective at detecting 254 leaks in the 15 SPEC2000 C programs and seven applications, while keeping the false positive rate at 18.3 percent. Saber compares favorably with several static leak detectors in terms of accuracy (leaks and false alarms reported) and scalability (LOC analyzed per second). In particular, compared with Fastcheck (which analyzes allocated objects flowing only into top-level pointers) using the 15 SPEC2000 C programs, Saber detects 44.1 percent more leaks at a slightly higher false positive rate but is only a few times slower.

Despite their widespread adoption in cloud computing, multicore processors are heavily under-utilized in terms of computing resources. To avoid the potential for negative and unpredictable interference, co-location of a latency-sensitive application with others on the same multicore processor is disallowed, leaving many cores idle and causing low machine utilization. To enable co-location while providing QoS guarantees, it is challenging but important to predict performance interference between co-located applications. This research is driven by two key insights. First, the performance degradation of an application can be represented as a predictor function of the aggregate pressures on shared resources from all cores, regardless of which applications are co-running and what their individual pressures are. Second, a predictor function is piecewise rather than non-piecewise as in prior work, thereby enabling different types of dominant contention factors to be more accurately captured by different subfunctions in its different subdomains. Based on these insights, we propose to adopt a two-phase regression approach to efficiently building a predictor function. Validation using a large number of benchmarks and nine real-world datacenter applications on three different platforms shows that our approach is also precise, with an average error not exceeding 0.4%. When applied to the nine datacenter applications, our approach improves overall resource utilization from 50% to 88% at the cost of 10% QoS degradation.

We propose a unified approach to the problem of scheduling a set of tasks with individual release times, deadlines and precedence constraints, and allocating the data of each task to the SPM (Scratchpad Memory) on a single processor system. Our approach consists of a task scheduling algorithm and an SPM allocation algorithm. The former constructs a feasible schedule incrementally, aiming to minimize the number of preemptions in the feasible schedule. The latter allocates a portion of the SPM to each task in an efficient way by employing a novel data structure, namely, the preemption graph. We have evaluated our approach and a previous approach by using six task sets. The results show that our approach achieves up to 20.31% on WCRT (Worst-Case Response Time) reduction over the previous approach.

Andersen's pointer analysis becomes more precise when applied with full heap cloning but unscalable for large, heap-intensive programs. In contrast, k-callsite-sensitive heap cloning can be faster but less precise for some programs. In this paper, we make one step forward by enhancing Andersen's analysis with QUery-Directed Adaptive (QUDA) heap cloning for optimizing compilers. The novelty of our analysis, called QUDA, lies in performing k-callsite-sensitive heap cloning iteratively, starting with k = 0 (without heap cloning), so that an abstract heap object is cloned at iteration k = i + 1 only if some mayalias queries that are not answered positively at iteration k = i may now be answered more precisely. QUDA, which is implemented in Open64, has the same precision as the state-of-the-art, FULCRA, a version of QUDA with exhaustive heap cloning, but is significantly more scalable. For 10 SPEC2000 C benchmarks and 5 C applications (totalling 840 KLOC) evaluated, QUDA takes only 4+ minutes but exhaustive heap cloning takes 42+ minutes to complete. QUDA takes only 75.1 % of the time that Open64 takes on average to compile these 15 programs under “-O2”.

This paper describes the first implementation of Andersen's inclusion-based pointer analysis for C programs on a heterogeneous CPU-GPU system, where both its CPU and GPU cores are used. As an important graph algorithm, Andersen's analysis is difficult to parallelise because it makes extensive modifications to the structure of the underlying graph, in a way that is highly input-dependent and statically hard to analyse. Existing parallel solutions run on either the CPU or GPU but not both, rendering the underlying computational resources underutilised and the ratios of CPU-only over GPU-only speedups for certain programs (i.e., graphs) unpredictable. We observe that a naive parallel solution of Andersen's analysis on a CPU-GPU system suffers from poor performance due to workload imbalance. We introduce a solution that is centered around a new dynamic workload distribution scheme. The novelty lies in prioritising the distribution of different types of workloads, i.e., graph-rewriting rules in Andersen's analysis to CPU or GPU according to the degrees of the processing unit's suitability for processing them. This scheme is effective when combined with synchronisation-free execution of tasks (i.e., graph-rewriting rules) and difference propagation of points-to information between the CPU and GPU. For a set of seven C benchmarks evaluated, our CPU-GPU solution outperforms (on average) (1) the CPU-only solution by 50.6%, (2) the GPU-only solution by 78.5%, and (3) an oracle solution that behaves as the faster of (1) and (2) on every benchmark by 34.6%.

SUMMARY This paper introduces a new dynamic data race detector, ACCULOCK, to detect data races in Java programs. ACCULOCK is the first hybrid detector that combines lockset and epoch‐based happens‐before for race detection. ACCULOCK analyzes a program execution by reasoning about the subset of the happens‐before relation observed with lock acquires and releases excluded, thereby making it less sensitive to thread interleaving than pure happens‐before detectors. When this relaxed happens‐before relation is violated, ACCULOCK applies a new lockset algorithm to verify the locking discipline by distinguishing reads and writes, thereby making it more immune to false positives than pure lockset detectors. In addition, ACCULOCK is designed to achieve these design objectives by maintaining comparable instrumentation overheads (in both time and space) to that of FASTTRACK, the fastest happens‐before detector available (at least for Java programs). All these properties of ACCULOCK have been validated and confirmed by comparing it against FASTTRACK and five other (pure happens‐before, pure lockset, or hybrid) detectors, which are implemented in the Jikes Research Virtual Machine using a collection of large benchmark programs from a variety of applications. Furthermore, porting ACCULOCK and FASTTRACK to a different platform, RoadRunner, and repeating our experiments yield similar observations in terms of their effectiveness in race detection and instrumentation overheads. Copyright © 2012 John Wiley & Sons, Ltd.

Most scientific computations serve to apply mathematical operations to a set of preconceived data structures, e.g., matrices, vectors, and grids. In this article, we use a number of widely used matrix computations from the LINPACK library to demonstrate that complex internal organizations of data structures can severely degrade the effectiveness of compiler optimizations. We then present a data-layout-oblivious optimization methodology, where by isolating an abstract representation of the computations from complex implementation details of their data, we enable these computations to be much more accurately analyzed and optimized through varying state-of-the-art compiler technologies. We evaluated our approach on an Intel 8-core platform using two source-to-source compiler infrastructures, Pluto and EPOD. Our results show that while the efficiency of a computational kernel differs when using different data layouts, the alternative implementations typically benefit from a common set of optimizations on the operations. Therefore separately optimizing the operations and the data layout of a computation could dramatically enhance the effectiveness of compiler optimizations compared with the conventional approaches of using a unified representation.

Research on compiler techniques for thread-level loop speculation has so far remained on studying its performance limits: loop candidates that are worthy of parallelization are manually selected by the researchers or based on extensive profiling and preexecution. It is therefore difficult to include them in a production compiler for speculative multithreaded multicore processors. In a way, existing techniques are statically adaptive ("realized"; by the researchers for different inputs) yet dynamically greedy (since all iterations of all selected loop candidates are always parallelized at run time). This paper introduces a Statically GrEEdy and Dynamically Adaptive (SEED) approach for thread-level speculation on loops that is quite different from most other existing techniques. SEED relies on the compiler to select and optimize loop candidates greedily (possibly in an input-independent way) and provides a runtime scheduler to schedule loop iterations adaptively. To select loops for parallelization at runtime (subject to program inputs), loop iterations are prioritized in terms of their potential benefits rather than their degree of speculation as in many prior studies. In our current implementation, the benefits of speculative threads are estimated by a simple yet effective cost model. It comprises a mechanism for efficiently tracing the loop nesting structures of the program and a mechanism for predicting the outcome of speculative threads. We have evaluated SEED using a set of SPECint2000 and Olden benchmarks. Compared to existing techniques with a program's loop candidates being ideally selected a priori, SEED can achieve comparable or better performance while aututomating the entire loop candidate selection process.

Most scientific computations serve to apply mathematical operations to a set of preconceived data structures, e.g., matrices, vectors, and grids. In this paper, we use a number of widely used matrix computations from the LINPACK library to demonstrate that complex internal organizations of data structures can severely degrade the effectiveness of compilers optimizations. We then present a data layout oblivious optimization methodology, where by isolating an abstract representation of computations from complex implementation details of their data, we enable these computations to be much more accurately analyzed and optimized through varying state-of-the-art compiler technologies.

Static analyses can be typically accelerated by reducing redundancies. Modern demand-driven points-to or alias analysis techniques rest on the foundation of Context-Free Language (CFL) reachability. These techniques achieve high precision efficiently for a small number of queries raised in small programs but may still be too slow in answering many queries for large programs in a context-sensitive manner.

Automatically parallelizing loop nests into CUDA kernels must exploit the full potential of GPUs to obtain high performance. One state-of-the-art approach makes use of the polyhedral model to extract parallelism from a loop nest by applying a sequence of affine transformations to the loop nest. However, how to automate this process to exploit both intra and inter-SM parallelism for GPUs remains a challenging problem. Presently, compilers may generate code significantly slower than hand-optimized code for certain applications. This paper describes a compiler framework for tiling and parallelizing loop nests with uniform dependences into CUDA code. We aim to improve two levels of wave front parallelism. We find tiling hyper planes by embedding parallelism enhancing constraints in the polyhedral model to maximize intra-tile, i.e., intra-SM parallelism. This improves the load balance among the SPs in an SM executing a wave front of loop iterations within a tile. We eliminate parallelism-hindering false dependences to maximize inter-tile, i.e., inter-SM parallelism. This improves the load balance among the SMs executing a wave front of tiles. Our approach has been implemented in PLUTO and validated using eight benchmarks on two different NVIDIA GPUs (C1060 and C2050). Compared to PLUTO, our approach achieves 2 - 5.5X speedups across the benchmarks. Compared to highly hand-optimized 1-D Jacobi (3 points), 2-D Jacobi (5 points), 3-D Jacobi (7 points) and 3-D Jacobi (27 points), our speedups, 1.17X, 1.41X, 0.97X and 0.87X with an average of 1.10X on C1060 and 1.24X, 1.20X, 0.86X and 0.95X with an average of 1.06X on C2050, are competitive.

Reuse distance analysis is a runtime approach that has been widely used to accurately model the memory system behavior of applications. However, traditional reuse distance analysis algorithms use tree-based data structures and are hard to parallelize, missing the tremendous computing power of modern architectures such as the emerging GPUs. This paper presents a highly-parallel reuse distance analysis algorithm (HP-RDA) to speedup the process using the SPMD execution model of GPUs. In particular, we propose a hybrid data structure of hash table and local arrays to flatten the traditional tree representation of memory access traces. Further, we use a probabilistic model to correct any loss of precision from a straightforward parallelization of the original sequential algorithm. Our experimental results show that using an NVIDIA GPU, our algorithm achieves a factor of 20 speedup over the traditional sequential algorithm with less than 1% loss in precision.

Almost every computer user has encountered an un-responsive system failure or system hang, which leaves the user no choice but to power off the computer. In this paper, the causes of such failures are analyzed in detail and one empirical hypothesis for detecting system hang is proposed. This hypothesis exploits a small set of system performance metrics provided by the OS itself, thereby avoiding modifying the OS kernel and introducing additional cost (e.g., hardware modules). Under this hypothesis, we propose SHFH, a self-healing framework to handle system hang, which can be deployed on OS dynamically. One unique feature of SHFH is that its "light-heavy" detection strategy is designed to make intelligent tradeoffs between the performance overhead and the false positive rate induced by system hang detection. Another feature is that its diagnosis-based recovery strategy offers a better granularity to recover from system hang. Our experimental results show that SHFH can cover 95.34% of system hang scenarios, with a false positive rate of 0.58% and 0.6% performance overhead, validating the effectiveness of our empirical hypothesis.

We introduce a static detector, Saber, for detecting memory leaks in C programs. Leveraging recent advances on sparse pointer analysis, Saber is the first to use a full-sparse value-flow analysis for leak detection. Saber tracks the flow of values from allocation to free sites using a sparse value-flow graph (SVFG) that captures def-use chains and value flows via assignments for all memory locations represented by both top-level and address-taken pointers. By exploiting field-, flow- and context-sensitivity during different phases of the analysis, Saber detects leaks in a program by solving a graph reachability problem on its SVFG. Saber, which is fully implemented in Open64, is effective at detecting 211 leaks in the 15 SPEC2000 C programs and five applications, while keeping the false positive rate at 18.5%. We have also compared Saber with Fastcheck (which analyzes allocated objects flowing only into top-level pointers) and Sparrow (which handles all allocated objects using abstract interpretation) using the 15 SPEC2000 C programs. Saber is as accurate as Sparrow but is 14.2X faster and reports 40.7% more bugs than Fastcheck at a slightly higher false positive rate but is only 3.7X slower.

We describe our preliminary experience in the design and implementation of a points-to analysis for Java, called EMU, that enables developers to perform pointer-related queries in programs undergoing constant changes in IDEs. EMU achieves fast response times by adopting a modular approach to incrementally updating method summaries upon small code changes: the points-to information in a method is summarised indirectly by CFL reachability rather than directly by points-to sets. Thus, the impact of a small code change made in a method is localised, requiring only its affected part to be re-summarised just to reflect the change. EMU achieves precision by being context-sensitive (for both method invocation and heap abstraction) and field-sensitive. Our evaluation shows that EMU can be promisingly deployed in IDEs where the changes are small.

In embedded systems, SPM (scratchpad memory) is an attractive alternative to cache memory due to its lower energy consumption and higher predictability of program execution. This paper studies the problem of placing variables of a program into an SPM such that its WCET (worst-case execution time) is minimized. We propose an efficient dynamic approach that comprises two novel heuristics. The first heuristic iteratively selects a most beneficial variable as an SPM resident candidate based on its impact on the k longest paths of the program. The second heuristic incrementally allocates each SPM resident candidate to the SPM based on graph coloring and acyclic graph orientation. We have evaluated our approach by comparing with an ILP-based approach and a longest-path-based greedy approach using the eight benchmarks selected from Powerstone and Mälardalen WCET Benchmark suites under three different SPM configurations. Our approach achieves up to 21% and 43% improvements in WCET reduction over the ILP-based approach and the greedy approach, respectively.

Algorithm-specific, that is, semantic-specific optimizations have been observed to bring significant performance gains, especially for a diverse set of multi/many-core architectures. However, current programming models and compiler technologies for the state-of-the-art architectures do not exploit well these performance opportunities. In this article, we propose a pattern-making methodology that enables algorithm-specific optimizations to be encapsulated into “optimization patterns”. Such optimization patterns are expressed in terms of preprocessor directives so that simple annotations can result in significant performance improvements. To validate this new methodology, a framework, named EPOD, is developed to map these directives into the underlying optimization schemes for a particular architecture. It is difficult to create an exact performance model to determine an optimal or near-optimal optimization scheme (including which optimizations to apply and in which order) for a specific application, due to the complexity of applications and architectures. However, it is trackable to build individual optimization components and let compiler developers synthesize an optimization scheme from these components. Therefore, our EPOD framework provides an Optimization Programming Interface (OPI) for compiler developers to define new optimization schemes. Thus, new patterns can be integrated into EPOD in a flexible manner. We have identified and implemented a number of optimization patterns for three representative computer platforms. Our experimental results show that a pattern-guided compiler can outperform the state-of-the-art compilers and even achieve performance as competitive as hand-tuned code. Therefore, such a pattern-making methodology represents an encouraging direction for domain experts' experience and knowledge to be integrated into general-purpose compilers.

The stream processors represent a promising alternative to traditional cache-based general-purpose processors in achieving high performance in stream applications (media and some scientific applications). In a stream programming model for stream processors, an application is decomposed into a sequence of kernels operating on streams of data. During the execution of a kernel on a stream processor, all streams accessed must be communicated through a nonbypassing software-managed on-chip memory, the SRF (Stream Register File). Optimizing utilization of the scarce on-chip memory is crucial for good performance. The key insight is that the interference graphs (IGs) formed by the streams in stream applications tend to be comparability graphs or decomposable into a set of comparability graphs. We present a compiler algorithm for finding optimal or near-optimal colorings, that is, SRF allocations in stream IGs, by computing a maximum spanning forest of the sub-IG formed by long live ranges, if necessary. Our experimental results validate the optimality and near-optimality of our algorithm by comparing it with an ILP solver, and show that our algorithm yields improved SRF utilization over the First-Fit bin-packing algorithm, the best in the literature.

Reliability is a key challenge to be understood to turn the vision of exascale supercomputing into reality. Inevitably, large-scale supercomputing systems, especially those at the peta/exascale levels, must tolerate failures, by incorporating fault-tolerance mechanisms to improve their reliability and availability. As the benefits of fault-tolerance mechanisms rarely come without associated time and/or capital costs, reliability will limit the scalability of parallel applications. This paper introduces for the first time the concept of "Reliability Wall” to highlight the significance of achieving scalable performance in peta/exascale supercomputing with fault tolerance. We quantify the effects of reliability on scalability, by proposing a reliability speedup, defining quantitatively the reliability wall, giving an existence theorem for the reliability wall, and categorizing a given system according to the time overhead incurred by fault tolerance. We also generalize these results into a general reliability speedup/wall framework by considering not only speedup but also costup. We analyze and extrapolate the existence of the reliability wall using two representative supercomputers, Intrepid and ASCI White, both employing checkpointing for fault tolerance, and have also studied the general reliability wall using Intrepid. These case studies provide insights on how to mitigate reliability-wall effects in system design and through hardware/software optimizations in peta/exascale supercomputing.

Loops are the main source of parallelism in many applications. This paper solves the open problem of extracting the maximal number of iterations from a loop to run parallel on chip multiprocessors. Our algorithm solves it optimally by migrating the weights of parallelism-inhibiting dependences on dependence cycles in two phases. First, we model dependence migration with retiming and formulate this classic loop parallelization into a graph optimization problem, i.e., one of finding retiming values for its nodes so that the minimum nonzero edge weight in the graph is maximized. We present our algorithm in three stages with each being built incrementally on the preceding one. Second, the optimal code for a loop is generated from the retimed graph of the loop found in the first phase. We demonstrate the effectiveness of our optimal algorithm by comparing with a number of representative nonoptimal algorithms using a set of benchmarks frequently used in prior work and a set of graphs generated by TGFF.

Clustering is a well-known technique for improving the scalability of classical VLIW processors. A clustered VLIW processor consists of multiple clusters, each of which has its own register file and functional units. This paper presents a novel phase coupled priority-based heuristic for scheduling a set of instructions in a basic block on a clustered VLIW processor. Our heuristic converts the instruction scheduling problem into the problem of scheduling a set of instructions with a common deadline. The priority of each instruction vi is the lmax(vi)-successor-tree-consistent deadline which is the upper bound on the latest completion time of vi in any feasible schedule for a relaxed problem where the precedence-latency constraints between vi and all its successors, as well as the resource constraints are considered. We have simulated our heuristic, UAS heuristic and Integrated heuristic on the 808 basic blocks taken from the MediaBench II benchmark suite using six processor models. On average, for the six processor models, our heuristic improves 25%, 25%, 33%, 23%, 26%, 27% over UAS heuristic, respectively, and 15%, 16%, 15%, 9%, 20%, 8% over Integrated heuristic, respectively.

Current programming models and compiler technologies for multi-core processors do not exploit well the performance benefits obtainable by applying algorithm-specific, i.e., semantic-specific optimizations to a particular application. In this work, we propose a pattern-making methodology that allows algorithm-specific optimizations to be encapsulated into “optimization patterns” that are expressed in terms of pre-processor directives so that simple annotations can result in significant performance improvements. To validate this new methodology, a framework, named EPOD, is developed to map such directives to the underlying optimization schemes. We have identified and implemented a number of optimization patterns for three representative computer platforms. Our experimental results show that a pattern-guided compiler can outperform the state-of-the-art compilers and even achieve performance as competitive as hand-tuned code. Thus, such a pattern-making methodology represents an encouraging direction for domain experts' experience and knowledge to be integrated into general-purpose compilers.

Happens-before detectors are precise but can be too conservative to detect certain data races in repeated test runs as they are sensitive to thread interleaving. By making the opposite tradeoffs, lockset detectors can detect more races but are not precise (by reporting false positives). For both types of detectors, happens-before detectors run more slowly as they use expensive vector clocks. Existing hybrid race detectors (combining lockset and happens-before) alleviate some of the limitations in both analysis techniques at the cost of additional analysis overhead. Recently, due to FastTrack, epoch-based happens-before and lockset detectors now exhibit comparable performance. It is the time to rethink how to design a hybrid race detector to balance precision and coverage, by leveraging the lightweightness of epoch clocks. Acculock is the first such a solution. Acculock analyzes a program by reasoning about the subset of the happens-before relation observed with lock acquires and releases excluded, thereby reducing its sensitivity to thread interleaving. When such a weaker happens-before relation is violated, Acculock applies a new efficient lockset algorithm to enforce a lock-based synchronization discipline by distinguishing the locks protecting reads and writes. The key motivation behind is to ensure that Acculock can improve happens-before detectors by discovering also data races in alternate thread interleavings when analyzing one program execution while limiting false warnings thus incurred in a controlled manner. In addition, Acculock achieves these objectives by maintaining comparable performance as FastTrack, the fastest happens-before detector. All these properties of Acculock are validated and confirmed by comparing it against six other detectors, all implemented in Jikes RVM using 11 benchmark programs.

High-performance libraries, the performance-critical building blocks for high-level applications, will assume greater importance on modern processors as they become more complex and diverse. However, automatic library generators are still immature, forcing library developers to manually tune library to meet their performance objectives. We are developing a new script-controlled compilation framework to help domain experts reduce much of the tedious and error-prone nature of manual tuning, by enabling them to leverage their expertise and reuse past optimization experiences. We focus on demonstrating improved performance and productivity obtained through using our framework to tune BLAS3 routines on three GPU platforms: up to 5.4x speedups over the CUBLAS achieved on NVIDIA GeForce 9800, 2.8x on GTX285, and 3.4x on Fermi Tesla C2050. Our results highlight the potential benefits of exploiting domain expertise and the relations between different routines (in terms of their algorithms and data structures).

Reducing memory accesses is particularly important for digital signal processing (DSP) applications since they are widely used in embedded systems and need to be executed with high performance and low power consumption. In this paper, we propose a machine-independent loop memory access optimization technique, redundant load exploration and migration (REALM), to explore hidden redundant load operations and migrate them outside loops based on loop-carried data dependence analysis. We implement REALM into IMPACT and Trimaran. To the best of our knowledge, this is the first work to implement the memory access reduction with loop-carried data reuse in real world compilers. We conduct experiments using a set of benchmarks from DSPstone and MiBench on the cycle-accurate VLIW simulator of Trimaran. The experimental results show that our technique significantly reduces the number of memory accesses.

Existing scratchpad memory (SPM) allocation algorithms for arrays, whether they rely on well-crafted heuristics or resort to integer linear programming (ILP) techniques, typically assume that every array is small enough to fit directly into the SPM. As a result, some arrays have to be spilled entirely to the off-chip memory in order to make room for other arrays to stay in the SPM, resulting in sometimes poor SPM utilization.

We present a practical and scalable method for flow- and context-sensitive (FSCS) pointer analysis for C programs. Our method analyzes the pointers in a program level by level in terms of their points-to levels, allowing the points-to relations of the pointers at a particular level to be discovered based on the points-to relations of the pointers at this level and higher levels. This level-by-level strategy can enhance the scalability of the FSCS pointer analysis in two fundamental ways, by enabling (1) fast and accurate flow-sensitive analysis on full sparse SSA form using a flow-insensitive algorithm and (2) fast and accurate context-sensitive analysis using a full transfer function and a meet function for each procedure.

This paper presents reuse-aware modulo scheduling to maximizing stream reuse and improving concurrency for stream-level loops running on stream processors. The novelty lies in the development of a new representation for an unrolled and software-pipelined stream-level loop using a set of reuse equations, resulting in simultaneous optimization of two performance objectives for the loop, reuse and concurrency, in a unified framework. We have implemented this work in the compiler developed for our 64-bit FT64 stream processor. Our experimental results obtained on FT64 and by simulation using nine representative stream applications demonstrate the effectiveness of the proposed approach.

We propose the first polynomial-time code selection algorithm for minimising the worst-case execution time of a non-nested loop executed on a fully pipelined processor that uses scratchpad memory to replace the instruction cache. The time complexity of our algorithm is O(m(ne+n2 log n)), where n and e are the number of basic blocks and the number of edges in the control flow graph of the loop, and m is the size of the scratchpad memory. Furthermore, we propose the first dynamic code selection heuristic for minimising the worst-case execution time of a task by using our algorithm for a non-nested loop. Our simulation results show that our heuristic significantly outperforms a previously known heuristic

To exploit the full potential of GPGPUs for general purpose computing, DOACR parallelism abundant in scientific and engineering applications must be harnessed. However, the presence of cross-iteration data dependences in DOACR loops poses an obstacle to execute their computations concurrently using a massive number of fine-grained threads. This work focuses on iterative PDE solvers rich in DOACR parallelism to identify optimization principles and strategies that allow their efficient mapping to GPGPUs. Our main finding is that certain DOACR loops can be accelerated further on GPGPUs if they are algorithmically restructured (by a domain expert) to be more amendable to GPGPU parallelization, judiciously optimized (by the compiler), and carefully tuned by a performance-tuning tool. We substantiate this finding with a case study by presenting a new parallel SSOR method that admits more efficient data-parallel SIMD execution than red-black SOR on GPGPUs. Our solution is obtained non-conventionally, by starting from a K-layer SSOR method and then parallelizing it by applying a non-dependence-preserving scheme consisting of a new domain decomposition technique followed by a generalized loop tiling. Despite its relatively slower convergence, our new method outperforms red-black SOR by making a better balance between data reuse and parallelism and by trading off convergence rate for SIMD parallelism. Our experimental results highlight the importance of synergy between domain experts, compiler optimizations and performance tuning in maximizing the performance of applications, particularly PDE-based DOACR loops, on GPGPUs.

Abstract Inter‐iteration dependences in loops can hinder loop‐level parallelism. For some loops, existing thread‐level speculation techniques fail to expose their inherent loop‐level parallelism, because some inter‐iteration dependences are too costly to synchronize, predict, pre‐compute and isolate. This paper presents a compiler technique called loop recreation to change the nature of some dependences (by turning some inter‐iteration dependences into intra‐iteration ones and vice versa) in a loop so that the inter‐iteration dependences in the transformed loop are less costly to enforce at runtime than those in the original loop. We present an algorithm for finding an optimal loop recreation transformation with respect to a simple misspeculation cost model and demonstrate the performance advantages of loop recreation over two recent techniques for multicore systems running nine representative irregular applications. Copyright © 2009 John Wiley & Sons, Ltd.

Memory accesses limit the performance of stream processors. By exploiting the reuse of data held in the Stream Register File (SRF), an on-chip, software controlled storage, the number of memory accesses can be reduced. In current stream compilers, reuse exploitation is only attempted for simple stream references, those whose start and end are known. Compiler analysis, from outside of stream processors, does not directly enable the consideration of other more complex stream references. In this article, we propose a transformation to automatically optimize stream programs to exploit the reuse supplied by loop-dependent stream references. The transformation is based on three results: lemmas identifying the reuse supplied by stream references, a new abstract representation called the Stream Reuse Graph (SRG) depicting the identified reuse, and the optimization of the SRG for our transformation. Both the reuse between the whole sequences accessed by stream references and between partial sequences is exploited in the article. In particular, partial reuse and its treatment are quite new and have never, to the best of our knowledge, appeared in scalar and vector processing. At the same time, reusing streams increases the pressure on the SRF, and this presents a problem of which reuse should be exploited within limited SRF capacity. We extend our analysis to achieve this objective. Finally, we implement our techniques based on the StreamC/KernelC compiler that has been optimized with the best existing compilation techniques for stream processors. Experimental results show a resultant speed-up of 1.14 to 2.54 times using a range of benchmarks.

Existing methods place data or code in scratchpad memory (SPM) by relying on heuristics or resorting to integer programming or mapping it to a graph-coloring problem. In this article, the SPM allocation problem for arrays is formulated as an interval coloring problem. The key observation is that in many embedded C programs, two arrays can be modeled such that either their live ranges do not interfere or one contains the other (with good accuracy). As a result, array interference graphs often form a special class of superperfect graphs (known as comparability graphs), and their optimal interval colorings become efficiently solvable. This insight has led to the development of an SPM allocation algorithm that places arrays in an interference graph in SPM by examining its maximal cliques. If the SPM is no smaller than the clique number of an interference graph, then all arrays in the graph can be placed in SPM optimally. Otherwise, we rely on containment-motivated heuristics to split or spill array live ranges until the resulting graph is optimally colorable. We have implemented our algorithm in SUIF/machSUIF and evaluated it using a set of embedded C benchmarks from MediaBench and MiBench. Compared to a graph-coloring algorithm and an optimal ILP algorithm (when it runs to completion), our algorithm achieves close-to-optimal results and is superior to graph coloring for the benchmarks tested.

This paper solves the open problem of extracting the maximal number of iterations from a loop that can be executed in parallel on chip multiprocessors. Our algorithm solves it optimally by migrating the weights of parallelism-inhibiting dependences on dependence cycles in two phases. First, we model dependence migration with retiming and formulate this classic loop parallelization into a graph optimization problem, i.e., one of finding retiming values for its nodes so that the minimum non-zero edge weight in the graph is maximized. We present our algorithm in three stages with each being built incrementally on the preceding one. Second, the optimal code for a loop is generated from the retimed graph of the loop found in the first phase. We demonstrate the effectiveness of our optimal algorithm by comparing with a number of representative non-optimal algorithms using a set of benchmarks frequently used in prior work.

We present a new cache-efficient parallel multilayer Gauss-Seidel algorithm to solve 2D diffusion equations on distributed memory machines, by focusing on improving its cache behaviour and parallelism simultaneously. The novelty of our parallel multi-layer algorithm lies in performing Gauss-Seidel in two alternating sweeping directions (with multiple layers, i.e., iterations per direction) and applying alternating tiling strategies in two opposite sweeping directions to the subdomain allocated to every processor. As a result, its efficiency comes from a significant reduction in two sources of overhead: data cache misses and communication costs. In comparison with two commonly used parallel Gauss-Seidel algorithms, our algorithm has good performance and scalability in a cluster computing environment.

A stream processor executes an application that has been decomposed into a sequence of kernels that operate on streams of data elements. During the execution of a kernel, all streams accessed must be communicated through the SRF (Stream Register File), a non-bypassing software-managed on-chip memory. Therefore, optimizing utilization of the SRF is crucial for good performance. The key insight is that the interference graphs formed by the streams in stream applications tend to be comparability graphs or decomposable into a set of multiple comparability graphs. We present a compiler algorithm that can find optimal or near-optimal colorings in stream IGs, thereby improving SRF utilization than the First-Fit

Scratchpad memory (SPM), a fast on-chip SRAM managed by software, is widely used in embedded systems. This article introduces a general-purpose compiler approach, called memory coloring, to assign static data aggregates, such as arrays and structs, in a program to an SPM. The novelty of this approach lies in partitioning the SPM into a pseudo--register file (with interchangeable and aliased registers), splitting the live ranges of data aggregates to create potential data transfer statements between SPM and off-chip memory, and finally, adapting an existing graph coloring algorithm for register allocation to assign the data aggregates to the pseudo--register file. Our experimental results using a set of 10 C benchmarks from MediaBench and MiBench show that our methodology is capable of managing SPMs efficiently and effectively for large embedded applications. In addition, our SPM allocator can obtain close to optimal solutions when evaluated and compared against an existing heuristics-based SPM allocator and an ILP-based SPM allocator.

The memory access limits the performance of stream processors. By exploiting the reuse of data held in the Stream Register File (SRF), an on-chip storage, the number of memory accesses can be reduced. In current stream compilers reuse is only attempted for simple stream references, those whose start and end are known. Compiler analysis from outside of stream processors does not directly enable the consideration of other complex stream references. In this paper we propose a transformation to automatically optimize stream programs to exploit the reuse supplied by loop-dependent stream references. The transformation is based on three results: algorithms to recognize the reuse supplied by stream references, a new abstract expression called the Stream Reuse Graph (SRG) to depict the reuse and the optimization of the SRG for the transformation. Both the reuse between whole sequences accessed by stream references and that between partial sequences are exploited in the paper. In particular, the problem of exploiting partial stream reuse does not have its parallel in the traditional data reuse exploitation setting (for scalars and arrays). Finally, we have implemented our techniques using the StreamC/KernelC compiler for Imagine. Experimental results show a resultant speedup of 1.14 to 2.54 times using a range of typical stream processing application kernels.

Sparse matrix vector multiplication (SpMxV) is a core operation in many engineering, scientific and financial applications. Due to the sparse nature of the underlying matrices, irregular memory access patterns and short row lengths often slow down the performance significantly. Past implementations of SpMxV have been reported to be run at 10% or less of the machine's peak capability. In this paper we present a novel hardware support called distTree for efficient SpMxV. It is shown that replacing the column indices of sparse matrices with extra hardware is achievable and yields an average speedup by a factor of two for the suite of benchmarks used. The matrix data set for the distTree is approximately 30% less than that for conventional CSR algorithms so that distTree is beneficial in terms of not only performance but also memory usage. Thorough analysis is done by looking at the correlation between the performance speedups and various matrices properties.

This paper presents a complete design of a reconfigurable architecture support system, called ACS (an Addressless Configuration Support), which provides efficient access to non-contiguous reconfigurable locations in reconfigurable systems. ACS reduces the amount of partial reconfiguration information required by removing a large amount of addressing information and padding as found in Virtex-4 bitstreams. ACS improves significantly on the distTree architecture previously proposed by us. ACS introduces the selector block which connects the leaf nodes to a consecutive block of reconfiguration locations called a frame set. The system allows any number of leaf nodes customised to the size of the device, thereby providing much more flexibility. The hardware costs have also been reduced significantly over the distTree design. Together with the new marker loading mechanism, ACS is readily applicable to SRAM-based FPGAs. This new ACS system is benchmarked using eight real-world applications against a Virtex-4 device and the results show 6.83%–15.07% speedups when the reconfiguration granularity is set to a Virtex-4 frame.

This paper describes a generalisation of modulo scheduling to parallelize loops for SpMT processors that exploits simultaneously both instruction-level parallelism and thread-level parallelism while preserving the simplicity and effectiveness of modulo scheduling. Our generalisation is simple, drops easily into traditional modulo scheduling algorithms such as Swing in GCC 4.1.1 and produces good speedups for SPECfp2000 benchmarks, particularly in terms of its ability in parallelising DOACROSS loops.

This paper describes a graph coloring compiler framework to allocate on-chip SRF(Stream Register File) storage for optimizing scientific applications on stream processors. Our framework consists of first applying enabling optimizations such as loop unrolling to expose stream reuse and opportunities for maximizing parallelism, i.e., overlapping kernel execution and memory transfers.Then the three SRF management tasks are solved in a unified manner via graph coloring: (1) placing streams in the SRF, (2) exploiting stream use, and (3) maximizing parallelism. We evaluate the performance of our compiler framework by actually running nine representative scientific computing kernels on our FT64 stream processor. Our preliminary results show that compiler management achieves an average speedup of 2.3x compared to First-Fit allocation. In comparison with the performance results obtained from running these benchmarks on Itanium 2, an average speedup of 2.1x is observed.

We have devised an algorithm for minimal placement of bank selections in partitioned memory architectures. This algorithm is parameterizable for a chosen metric, such as speed, space, or energy. Bank switching is a technique that increases the code and data memory in microcontrollers without extending the address buses. Given a program in which variables have been assigned to data banks, we present a novel optimization technique that minimizes the overhead of bank switching through cost-effective placement of bank selection instructions. The placement is controlled by a number of different objectives, such as runtime, low power, small code size or a combination of these parameters. We have formulated the minimal placement of bank selection instructions as a discrete optimization problem that is mapped to a partitioned boolean quadratic programming (PBQP) problem. We implemented the optimization as part of a PIC Microchip backend and evaluated the approach for several optimization objectives. Our benchmark suite comprises programs from MiBench and DSPStone plus a microcontroller real-time kernel and drivers for microcontroller hardware devices. Our optimization achieved a reduction in program memory space of between 2.7 and 18.2%, and an overall improvement with respect to instruction cycles between 5.0 and 28.8%. Our optimization achieved the minimal solution for all benchmark programs. We investigated the scalability of our approach toward the requirements of future generations of microcontrollers. This study was conducted as a worst-case analysis on the entire MiBench suite. Our results show that our optimization (1) scales well to larger numbers of memory banks, (2) scales well to the larger problem sizes that will become feasible with future microcontrollers, and (3) achieves minimal placement for more than 72% of all functions from MiBench.

For some sequential loops, existing techniques that form speculative threads only at their loop boundaries do not adequately expose the speculative parallelism inherent in them. This is because some inter-iteration dependences, which translate into inter-thread dependences at run time, are too costly to synchronize or speculate. This paper presents a novel compiler technique, called loop recreation, to transform a loop into a prologue, a kernel loop - formed with instructions from two adjacent iterations, and an epilogue so that the inter-iteration dependences in the kernel are less costly to enforce at run time than those in the original loop. We prove the concept by giving an algorithm for finding an optimal loop recreation with respect to a simple misspeculation cost model and by demonstrating performance advantages of loop recreation over two recent techniques for speculative multi-core systems running four irregular applications with indirect array accesses.

Program parallelization requires mapping computation and data to processing elements. Navigational Programming (NavP), based on the principle of migrating computations, offers a different approach than the conventional solutions that use a SPMD model. This paper focuses on data distribution for NavP. We introduce the Navigational Trace Graph (NTG), a mathematical structure that captures the alignment and distribution preferences of a sequential program. Graph partitioning is applied to NTGs to obtain data distribution solutions. The major advantage is that our methodology can focus exclusively on reducing communication overhead first and later determine the actual computation partition and parallelization, because NavP computations migrate freely across partitions. This is in stark contrast to SPMD, where the data partitioning imposes hard constraints on the threads because they are stationary. We present experimental results to demonstrate the effectiveness of our approach.

Existing methods place data or code in scratchpad memory, i.e., SPM by either relying on heuristics or resorting to integer programming or mapping it to a graph coloring problem.

Caches have become increasingly important with the widening gap between main memory and processor speeds. Small and fast cache memories are designed to bridge this discrepancy. However, they are only effective when programs exhibit sufficient data locality. In addition, caches are a source of unpredictability, resulting in programs sometimes behaving in a different way than expected. Detailed information about the number of cache misses and their causes allows us to predict cache behavior and to detect bottlenecks. Small modifications in the source code may change memory patterns, thereby altering the cache behavior. Code transformations, which take the cache behavior into account, might result in a high cache performance improvement. However, cache memory behavior is very hard to predict, thus making the task of optimizing and timing cache behavior very difficult. This article proposes and evaluates a new compiler framework that times cache behavior for multitasking systems. Our method explores the use of cache partitioning and dynamic cache locking to provide worst-case performance estimates in a safe and tight way for multitasking systems. We use cache partitioning, which divides the cache among tasks to eliminate intertask cache interferences. We combine static cache analysis and cache-locking mechanisms to ensure that all intratask conflicts, and consequently, memory access times, are exactly predictable. The results of our experiments demonstrate the capability of our framework to describe cache behavior at compile time. We compare our timing approach with a system equipped with a nonpartitioned, but statically, locked data cache. Our method outperforms static cache locking for all analyzed task sets under various cache architectures, demonstrating that our fully predictable scheme does not compromise the performance of the transformed programs.

Bank switching is a technique that increases the code and data memory in microcontrollers without extending the address buses. Given a program in which variables have been assigned to data banks, we present a novel optimization technique that minimizes the overhead of bank switching through cost-effective placement of bank selection instructions. The optimal placement is controlled by a variety of different objectives, such as runtime, low power, small code size or a combination of these parameters. We have formulated the problem as a form of Partitioned Boolean Quadratic Programming (PBQP).We implemented the optimization as part of a PIC Micro-chip backend and evaluated the approach for several optimization objectives. Our benchmark suite comprises programs from MiBench and DSPStone plus a microcontroller real-time kernel and drivers for microcontroller hardware devices. Our optimization achieved a reduction of program memory space between 2.7% and 18.2%, and an overall improvement with respect to instruction cycles between 5.1% and 28.8%. Our optimization achieved an optimal solution for all benchmark programs.

Recently, we have witnessed a tremendous growth of interests in streaming continuous media such as video data over the Internet. However, how to provide true on-demand streaming services with VCR functionality is still a challenging task, especially when their scalability is required. In this paper, we propose CoopStream, a novel streaming scheme, to address this challenge in the context of overlay networks. At the client side, we propose to use a dual-channel cache management mechanism to dynamically adjust the cache contents based on its current playing state, so as to support VCR operations locally. On the server side, we exploit the temporal relationship among asynchronous streaming requests to schedule streams. This enables us to reduce significantly the server load by redirecting streaming requests to the clients that can serve those requests. Simulation results show that, CoopStream is capable of providing continuous streaming services that are scalable in terms of the server bandwidth consumed

ILP (instruction level parallelism) processors are being increasingly used in embedded systems. In embedded systems, instructions may be subject to timing constraints. An optimising compiler for ILP processors needs to find a feasible schedule for a set of time-constrained instructions. In this paper, we present a fast algorithm for scheduling instructions with precedence-latency constraints, individual integer release times and deadlines on an ILP processor with multiple functional units. The time complexity of our algorithm is O(n2logd)+min{O(de), O(ne)}+min{O(ne), O(n2.376)}, where n is the number of instructions, e is the number of edges in the precedence graph and d is the maximum latency. Our algorithm is guaranteed to find a feasible schedule whenever one exists in the following special cases: 1) one functional unit, arbitrary precedence constraints, latencies in {0,1}, integer release times and deadlines; 2) two identical functional units, arbitrary precedence constraints, latencies of 0, integer release times and deadlines; 3) multiple identical functional units or multiple functional units of different types, monotone interval-ordered graph, integer release times and deadlines; 4) multiple identical functional units, in-forest, equal latencies, integer release times and deadlines. In case 1) our algorithm improves the existing fastest algorithm from O(n2logn)+min{O(ne), O(n2.376)} to min{O(ne), O(n2.376)}. In case 2) our algorithm improves the existing fastest algorithm from O(ne+n2logn) to min{O(ne), O(n2.376)}. In case 3) no polynomial time algorithm for multiple functional units of different types was known before

This paper presents the design, implementation and experimental evaluation of a practical region-based partial dead code elimination (PDE) algorithm on predicated code in the Open Research Compiler framework. Existing PDE algorithms are not applicable on predicated code due to the existence of if-converted branches in the program. The proposed algorithm processes all PDE candidates in a worklist and considers their partial deadness using predicate partition graphs. Our algorithm operates uniformly on individual hyperblocks as well as regions comprising of basic blocks and hyperblocks. The result of applying our algorithm to a single-entry multiple-exit (SEME) region is optimal: partially dead code cannot be removed without changing the branching structure of the program or potentially introducing new predicate defining instructions. We present statistical evidence about the PDE opportunities in the 17 SPEC95 and SPEC00 integer benchmarks. Our algorithm achieves performance improvements in 12 out of the 17 benchmarks on an Itanium machine at small compilation overheads. Our results indicate that our algorithm can be used as a practical pass before instruction scheduling. Copyright © 2006 John Wiley & Sons, Ltd.

A lifetime optimal algorithm, called MC-PRE, is presented for the first time that performs speculative PRE based on edge profiles. In addition to being computationally optimal in the sense that the total number of dynamic computations for an expression in the transformed code is minimized, MC-PRE is also lifetime optimal since the lifetimes of introduced temporaries are also minimized. The key in achieving lifetime optimality lies not only in finding a unique minimum cut on a transformed graph of a given CFG, but also in performing a data-flow analysis directly on the CFG to avoid making unnecessary code insertions and deletions. The lifetime optimal results are rigorously proved. We evaluate our algorithm in GCC against three previously published PRE algorithms, namely, MC-PRE copt (Qiong and Xue's computationally optimal version of MC-PRE), LCM (Knoop, Rüthing, and Steffen's lifetime optimal algorithm for performing nonspeculative classic PRE), and CMP-PRE (Bodik, Gupta, and Soffa's PRE algorithm based on code-motion preventing (CMP) regions, which is speculative but not computationally optimal). We report and analyze our experimental results, obtained from both actual program execution and instrumentation, for all 22 C, C++ and FORTRAN 77 benchmarks from SPECcpu2000 on an Itanium 2 computer system. Our results show that MC-PRE (or MC-PRE copt ) is capable of eliminating more partial redundancies than both LCM and CMP-PRE (especially in functions with complex control flow), and, in addition, MC-PRE inserts temporaries with shorter lifetimes than MC-PRE copt . Each of both benefits has contributed to the performance improvements in benchmark programs at the costs of only small compile-time and code-size increases in some benchmarks.

This paper presents a new approach to enabling loop fusion and tiling for arbitrary affine loop nests. Given a set of multiple loop nests, we present techniques that automatically eliminate all the fusion-preventing dependences by means of loop tiling and array copying. Applying our techniques iteratively to multiple loop nests yields a single loop nest that can be tiled for cache locality. Our approach handles LU, QR, Cholesky and Jacobi in a unified framework. Our experimental evaluation on an SGI Octane2 system shows that the benefit from the significantly reduced L1 and L2 cache misses has far more than offset the branching and loop control overhead introduced by our approach.

Energy-aware compilers are becoming increasingly important for embedded systems due to the need to meet conflicting constraints on time, code size and power consumption. We introduce a trace-based, offline compiler framework on binaries and demonstrate its benefits in supporting energy optimisations. The key innovation lies in identifying frequently executed paths in a binary program and duplicating them as single-entry traces. Separating frequently from infrequently executed paths enables the compiler to focus both performance and energy optimisations on the hot traces.Traces constructed at the level of binaries are inherently inter-procedural, spanning both application and library code. Such a framework allows an embedded application developer to exploit optimisation opportunities made possible due to the information that is available only at link time.We describe the implementation of our trace-based framework in alto, a link-time optimiser for the Alpha architecture. We present a new algorithm for constructing the hot traces from binaries. This algorithm is both effective (since the execution cycles are mostly spent on traces) and practical (due to small code size increases caused). We have developed and implemented a new optimisation to reduce the functional unit leakage energy. We show how the traces facilitate the development of such an optimisation, which results in significant leakage energy savings for benchmark programs at the cost of small performance penalties.

Data caches are a key hardware means to bridge the gap between processor and memory speeds, but only for programs that exhibit sufficient data locality in their memory accesses. Thus, a method for evaluating cache performance is required to both determine quantitatively cache misses and to guide data cache optimizations. Existing analytical models for data cache optimizations target mainly isolated perfect loop nests. We present an analytical model that is capable of statically analyzing not only loop nest fragments, but also complete numerical programs with regular and compile-time predictable memory accesses. Central to the whole-program approach are abstract call inlining, memory access vectors, and parametric reuse analysis, which allow the reuse and interference both within and across loop nests to be quantified precisely in a unified framework. Based on the framework, the cache misses of a program are specified using mathematical formulas and the miss ratio is predicted from these formulas based on statistical sampling techniques. Our experimental results using kernels and whole programs indicate accurate cache miss estimates in a substantially shorter amount of time (typically, several orders of magnitude faster) than simulation.

Existing profile-guided partial redundancy elimination (PRE) methods use speculation to enable the removal of partial redundancies along more frequently executed paths at the expense of introducing additional expression evaluations along less frequently executed paths. While being capable of minimizing the number of expression evaluations in some cases, they are, in general, not computationally optimal in achieving this objective. In addition, the experimental results for their effectiveness are mostly missing. This work addresses the following three problems: (1) Is the computational optimality of speculative PRE solvable in polynomial time? (2) Is edge profiling - less costly than path profiling - sufficient to guarantee the computational optimality? (3) Is the optimal algorithm (if one exists) lightweight enough to be used efficiently in a dynamic compiler? In this paper, we provide positive answers to the first two problems and promising results to the third. We present an algorithm that analyzes edge insertion points based on an edge profile. Our algorithm guarantees optimally that the total number of computations for an expression in the transformed code is always minimized with respect to the edge profile given. This implies that edge profiling, which is less costly than path profiling, is sufficient to guarantee this optimality. The key in the development of our algorithm lies in the removal of some non-essential edges (and consequently, all resulting non-essential nodes) from a flow graph so that the problem of finding an optimal code motion is reduced to one of finding a minimal cut in the reduced (flow) graph thus obtained. We have implemented our algorithm in Intel's Open Runtime Platform (ORP). Our preliminary results over a number of Java benchmarks show that our algorithm is lightweight and can be potentially a practical component in a dynamic compiler. As a result, our algorithm can also be profitably employed in a profile-guided static compiler in which compilation cost can often be sacrificed for code efficiency.

For SOR-like PDE solvers, loop tiling either helps little in improving data locality or hurts their performance. We present a novel compiler technique called code tiling for generating fast tiled codes for these solvers on uniprocessors with a memory hierarchy. Code tiling combines loop tiling with a new array layout transformation called data tiling in such a way that a significant amount of cache misses that would otherwise be present in tiled codes are eliminated. Compared to nine existing loop tiling algorithms, our technique delivers impressive performance speedups (faster by factors of 1.55-2.62) and smooth performance curves across a range of problem sizes on representative machine architectures. The synergy of loop tiling and data tiling allows us to find a problem-size-independent tile size that minimises a cache miss objective function independently of the problem size parameters. This "one-size-fits-all" scheme makes our approach attractive for designing fast SOR solvers without having to generate a multitude of versions specialised for different problem sizes.

Data caches are essential in modern processors, bridging the widening gap between main memory and processor speeds. However, they yield very complex performance models, which make it hard to bound execution times tightly. This paper contributes a new technique to obtain predictability in preemptive multitasking systems in the presence of data caches. We explore the use of cache partitioning, dynamic cache locking, and static cache analysis to provide worst-case performance estimates in a safe and tight way. Cache partitioning divides the cache among tasks to eliminate inter-task cache interferences. We combine static cache analysis and cache locking mechanisms to ensure that all intra-task conflicts, and consequently, memory access times, are exactly predictable. To minimize the performance degradation due to cache partitioning and locking, two strategies are employed. First, the cache is loaded with data likely to be accessed so that their cache utilization is maximized. Second, compiler optimizations such as tiling and padding are applied in order to reduce cache replacement misses. Experimental results show that this scheme is fully predictable, without compromising the performance of the transformed programs. Our method outperforms static cache locking for all analyzed task sets under various cache architectures, with a CPU utilization reduction ranging between 3.8 and 20.0 times for a high performance system.

Caches have become increasingly important with the widening gap between main memory and processor speeds. However, they are a source of unpredictability due to their characteristics, resulting in programs behaving in a different way than expected.Cache locking mechanisms adapt caches to the needs of real-time systems. Locking the cache is a solution that trades performance for predictability: at a cost of generally lower performance, the time of accessing the memory becomes predictable.This paper combines compile-time cache analysis with data cache locking to estimate the worst-case memory performance (WCMP) in a safe, tight and fast way. In order to get predictable cache behavior, we first lock the cache for those parts of the code where the static analysis fails. To minimize the performance degradation, our method loads the cache, if necessary, with data likely to be accessed.Experimental results show that this scheme is fully predictable, without compromising the performance of the transformed program. When compared to an algorithm that assumes compulsory misses when the state of the cache is unknown, our approach eliminates all overestimation for the set of benchmarks, giving an exact WCMP of the transformed program without any significant decrease in performance.

Based on a new characterisation of data reuse across multiple loop nests, we preset a method, a prototyping implementation and some experimental results for analysing the cache behaviour of whole programs with regular computations. Validation against cache simulation using real codes shows the efficiency and accuracy of our method. The largest program, we have analysed, Applu from SPECfP95, has 3868 lines, 16 subroutines and 2565 references. In the case of a 32KB cache with a 32B line size, our method obtains the miss ratio with an absolute error of about 0.80% in about 128 seconds while the simulator used runs for nearly 5 hours on a 933MHz Pentium. III PC. Our method can be used to guide compiler locality optimisations and improve cache simulation performance.

This paper describes a unified approach to checking data link and computational conflicts in mapping algorithms to lower-dimensional processor arrays. Based primarily on the notion of Hermite normal form, we propose a range of necessary and sufficient conditions to identify mappings without data link and computational conflicts. These conditions are then used to find optimal time mappings of a transitive closure algorithm to linear processor arrays.

The authors present a new formulation for mapping algorithms into linear systolic arrays. The closed-form necessary and sufficient mapping conditions are derived to identify mappings without computation conflicts and data link collisions. These mapping conditions are easy to check because their constituent variables are the space-time mapping matrix and the problem size parameters. The design of optimal arrays is a mathematical programming problem, which can be solved by a systematic enumeration of its search space.>