Publications | Zheng (Eddy) Zhang

2023

ASPLOS
Exploiting the Regular Structure of Modern Quantum Architectures for Compiling and Optimizing Programs with Permutable Operators

Yuwei Jin, Fei Hua, Yanhao Chen, and 3 more authors

In Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 4, 2023

Abs Bib PDF

A critical feature in today’s quantum circuit is that they have permutable two-qubit operators. The flexibility in ordering the permutable two-qubit gates leads to more compiler optimization opportunities. However, it also imposes significant challenges due to the additional degree of freedom. Our Contributions are two-fold. We first propose a general methodology that can find structured solutions for scalable quantum hardware. It breaks down the complex compilation problem into two sub-problems that can be solved at small scale. Second, we show how such a structured method can be adapted to practical cases that handle sparsity of the input problem graphs and the noise variability in real hardware. Our evaluation evaluates our method on IBM and Google architecture coupling graphs for up to 1,024 qubits and demonstrate better result in both depth and gate count - by up to 72% reduction in depth, and 66% reduction in gate count. Our real experiments on IBM Mumbai show that we can find better expected minimal energy than the state-of-the-art baseline.
@inproceedings{asplos23qaoa, author = {Jin, Yuwei and Hua, Fei and Chen, Yanhao and Hayes, Ari and Zhang, Chi and Zhang, Eddy Z.}, title = {Exploiting the Regular Structure of Modern Quantum Architectures for Compiling and Optimizing Programs with Permutable Operators}, year = {2023}, isbn = {9798400703942}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3623278.3624751}, doi = {10.1145/3623278.3624751}, booktitle = {Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 4}, pages = {108–124}, numpages = {17}, keywords = {quantum circuit compilation, QAOA, circuit fidelity}, location = {, Vancouver, BC, Canada, }, series = {ASPLOS '23}, }

HPCA

A Pulse Generation Framework with Augmented Program-aware Basis Gates and Criticality Analysis

Yanhao Chen, Yuwei Jin, Fei Hua, and 4 more authors

In 2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA), 2023

@inproceedings{chenetalhpca23,
  author = {Chen, Yanhao and Jin, Yuwei and Hua, Fei and Hayes, Ari and Li, Ang and Shi, Yunong and Zhang, Eddy Z.},
  booktitle = {2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA)},
  title = {A Pulse Generation Framework with Augmented Program-aware Basis Gates and Criticality Analysis},
  year = {2023},
  volume = {},
  number = {},
  pages = {773-786},
  doi = {10.1109/HPCA56546.2023.10070990}
}

ASPLOS
CaQR: A Compiler-Assisted Approach for Qubit Reuse through Dynamic Circuit

Fei Hua, Yuwei Jin, Yanhao Chen, and 6 more authors

In Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3, 2023

Abs Bib HTML PDF

Quantum measurement is important to quantum computing as it extracts out the outcome of the circuit at the end of the computation. Previously, all measurements have to be done at the end of the circuit. Otherwise, it will incur significant errors. But it is not the case now. Recently IBM starts supporting dynamic circuit through hardware (instead of software by simulator). With mid-circuit hardware measurement, we can improve circuit efficacy and fidelity from three aspects: (a) reduced qubit usage, (b) reduced swap insertion, and (c) improved fidelity. We demonstrate this using real-world applications Bernstein Verizani on real hardware and show that circuit resource usage can be improved by 60%, and circuit fidelity can be improved by 15%. We design a compiler-assisted tool that can find and exploit the tradeoff between qubit reuse, fidelity, gate count, and circuit duration. We also developed a method for identifying whether qubit reuse will be beneficial for a given application. We evaluated our method on a representative set of important applications. We can reduce resource usage by up to 80% and improve circuit fidelity by up to 20%.
@inproceedings{huaetalasplos23, author = {Hua, Fei and Jin, Yuwei and Chen, Yanhao and Vittal, Suhas and Krsulich, Kevin and Bishop, Lev S. and Lapeyre, John and Javadi-Abhari, Ali and Zhang, Eddy Z.}, title = {CaQR: A Compiler-Assisted Approach for Qubit Reuse through Dynamic Circuit}, year = {2023}, isbn = {9781450399180}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, doi = {10.1145/3582016.3582030}, booktitle = {Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3}, pages = {59–71}, numpages = {13}, keywords = {qubit reuse, circuit fidelity, qubit usage, mid-circuit measurement}, location = {Vancouver, BC, Canada}, series = {ASPLOS 2023} }

2021

ASPLOS
Time-Optimal Qubit Mapping

Chi Zhang, Ari B. Hayes, Longfei Qiu, and 3 more authors

In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, 2021

Abs Bib HTML PDF

Rapid progress in the physical implementation of quantum computers gave birth to multiple recent quantum machines implemented with superconducting technology. In these NISQ machines, each qubit is physically connected to a bounded number of neighbors. This limitation prevents most quantum programs from being directly executed on quantum devices. A compiler is required for converting a quantum program to a hardware-compliant circuit, in particular, making each two-qubit gate executable by mapping the two logical qubits to two physical qubits with a link between them. To solve this problem, existing studies focus on inserting SWAP gates to dynamically remap logical qubits to physical qubits. However, most of the schemes lack the consideration of time-optimality of generated quantum circuits, or are achieving time-optimality with certain constraints. In this work, we propose a theoretically time-optimal SWAP insertion scheme for the qubit mapping problem. Our model can also be extended to practical heuristic algorithms. We present exact analysis results by using our model for quantum programs with recurring execution patterns. We have for the first time discovered an optimal qubit mapping pattern for quantum fourier transformation (QFT) on 2D nearest neighbor architecture. We also present a scalable extension of our theoretical model that can be used to solve qubit mapping for large quantum circuits.
@inproceedings{zhangetalasplos21, author = {Zhang, Chi and Hayes, Ari B. and Qiu, Longfei and Jin, Yuwei and Chen, Yanhao and Zhang, Eddy Z.}, title = {Time-Optimal Qubit Mapping}, year = {2021}, isbn = {9781450383172}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, doi = {10.1145/3445814.3446706}, booktitle = {Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems}, pages = {360–374}, numpages = {15}, keywords = {Qubit Mapping, Quantum Fourier Transformation, Noisy Intermediate Quantum Computers, NISQ, Quantum Computing, QFT}, location = {Virtual, USA}, series = {ASPLOS '21}, }
ICPP
BGPQ: A Heap-Based Priority Queue Design for GPUs

Yanhao Chen, Fei Hua, Yuwei Jin, and 1 more author

In Proceedings of the 50th International Conference on Parallel Processing, 2021

Abs Bib HTML PDF

Programming today’s many-core processor is challenging. Due to the enormous amount of parallelism, synchronization is expensive. We need efficient data structures for providing automatic and scalable synchronization methods. In this paper, we focus on the priority queue data structure. We develop a heap-based priority queue implementation called BGPQ. BGPQ uses batched key nodes as the internal data representation, exploits both task parallelism and data parallelism, and is linearizable. We show that BGPQ achieves up to 88X speedup compared with four state-of-the-art CPU parallel priority queue implementations and up to 11.2X speedup over an existing GPU implementation. We also apply BGPQ to search problems, including 0-1 Knapsack and A* search. We achieve 45X-100X and 12X-46X speedup respectively over best known concurrent CPU priority queues.
@inproceedings{chen+:icpp21, author = {Chen, Yanhao and Hua, Fei and Jin, Yuwei and Zhang, Eddy Z.}, title = {BGPQ: A Heap-Based Priority Queue Design for GPUs}, year = {2021}, isbn = {9781450390682}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, doi = {10.1145/3472456.3472463}, booktitle = {Proceedings of the 50th International Conference on Parallel Processing}, articleno = {9}, numpages = {10}, keywords = {GPUs, Priority Queue, Batched Heap}, location = {Lemont, IL, USA}, series = {ICPP '21} }
MICRO
AutoBraid: A Framework for Enabling Efficient Surface Code Communication in Quantum Computing

Fei Hua, Yanhao Chen, Yuwei Jin, and 4 more authors

In MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture, 2021

Abs Bib HTML PDF

Quantum computers can solve problems that are intractable using the most powerful classical computer. However, qubits are fickle and error prone. It is necessary to actively correct errors in the execution of a quantum circuit. Quantum error correction (QEC) codes are developed to enable fault-tolerant quantum computing. With QEC, one logical circuit is converted into an encoded circuit. Most studies on quantum circuit compilation focus on NISQ devices which have 10-100 qubits and are not fault-tolerant. In this paper, we focus on the compilation for fault-tolerant quantum hardware. In particular, we focus on optimizing communication parallelism for the surface code based QEC. The execution of surface code circuits involves non-trivial geometric manipulation of a large lattice of entangled physical qubits. A two-qubit gate in surface code is implemented as a virtual “pipe” in space-time called a braiding path. The braiding paths should be carefully routed to avoid congestion. Communication between qubits is considered the major bottleneck as it involves scheduling and searching for simultaneous paths between qubits. We provide a framework for efficiently scheduling braiding paths. We discover that for quantum programs with a local parallelism pattern, our framework guarantees an optimal solution, while the previous greedy-heuristic-based solution cannot. Moreover, we propose an extension to the local parallelism analysis framework to address the communication bottleneck. Our framework achieves orders of magnitude improvement after addressing the communication bottleneck.
@inproceedings{huaetalmicro21, author = {Hua, Fei and Chen, Yanhao and Jin, Yuwei and Zhang, Chi and Hayes, Ari and Zhang, Youtao and Zhang, Eddy Z.}, title = {AutoBraid: A Framework for Enabling Efficient Surface Code Communication in Quantum Computing}, year = {2021}, isbn = {9781450385572}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, doi = {10.1145/3466752.3480072}, booktitle = {MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture}, pages = {925–936}, numpages = {12}, location = {Virtual Event, Greece}, series = {MICRO '21} }

2019

CGO

Decoding CUDA Binary

Ari B. Hayes, Fei Hua, Jin Huang, and 2 more authors

In 2019 IEEE/ACM International Symposium on Code Generation and Optimization (CGO), 2019

Bib PDF

@inproceedings{hayesetalcgo19,
  author = {Hayes, Ari B. and Hua, Fei and Huang, Jin and Chen, Yanhao and Zhang, Eddy Z.},
  booktitle = {2019 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)},
  title = {Decoding CUDA Binary},
  year = {2019},
  volume = {},
  number = {},
  pages = {229-241},
  doi = {10.1109/CGO.2019.8661186}
}

2018

USENIX ATC
Locality-Aware Software Throttling for Sparse Matrix Operation on GPUs

Yanhao Chen, Ari B. Hayes, Chi Zhang, and 2 more authors

In Proceedings of the 2018 USENIX Conference on Usenix Annual Technical Conference, 2018

Abs Bib PDF

This paper tackles the cache thrashing problem caused by the non-deterministic scheduling feature of bulk synchronous parallel (BSP) execution in GPUs. In the BSP model, threads can be executed and interleaved in any order before reaching a barrier synchronization point, which requires the entire working set to be in cache for maximum data reuse over time. However, it is not always possible to fit all the data in cache at once. Thus, we propose a locality-aware software throttling framework that throttles the number of active execution tasks, prevents cache thrashing, and enhances data reuse over time. Our locality-aware software throttling framework focuses on an important class of applications that operate on sparse matrices (graphs). These applications come from the domains of linear algebra, graph processing, machine learning and scientific simulation. Evaluated on over 200 real sparse matrices and graphs that suffer from cache thrashing in the Florida sparse matrix collection, our technique achieves an average of 2.01X speedup, a maximum of 6.45X speedup, and a maximum performance loss ≤5%.
@inproceedings{chenetalatc18, author = {Chen, Yanhao and Hayes, Ari B. and Zhang, Chi and Salmon, Timothy and Zhang, Eddy Z.}, title = {Locality-Aware Software Throttling for Sparse Matrix Operation on GPUs}, year = {2018}, isbn = {9781931971447}, publisher = {USENIX Association}, address = {USA}, booktitle = {Proceedings of the 2018 USENIX Conference on Usenix Annual Technical Conference}, pages = {413–425}, numpages = {13}, location = {Boston, MA, USA}, series = {USENIX ATC '18} }

2017

TACO
LD: Low-Overhead GPU Race Detection Without Access Monitoring

Pengcheng Li, Xiaoyu Hu, Dong Chen, and 4 more authors

ACM Trans. Archit. Code Optim., Mar 2017

Abs Bib HTML PDF

Data race detection has become an important problem in GPU programming. Previous designs of CPU race-checking tools are mainly task parallel and incur high overhead on GPUs due to access instrumentation, especially when monitoring many thousands of threads routinely used by GPU programs.This article presents a novel data-parallel solution designed and optimized for the GPU architecture. It includes compiler support and a set of runtime techniques. It uses value-based checking, which detects the races reported in previous work, finds new races, and supports race-free deterministic GPU execution. More important, race checking is massively data parallel and does not introduce divergent branching or atomic synchronization. Its slowdown is less than 5 \texttimes for over half of the tests and 10 \texttimes on average, which is orders of magnitude more efficient than the cuda-memcheck tool by Nvidia and the methods that use fine-grained access instrumentation.
@article{li+:taco17, author = {Li, Pengcheng and Hu, Xiaoyu and Chen, Dong and Brock, Jacob and Luo, Hao and Zhang, Eddy Z. and Ding, Chen}, title = {LD: Low-Overhead GPU Race Detection Without Access Monitoring}, year = {2017}, issue_date = {March 2017}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, volume = {14}, number = {1}, issn = {1544-3566}, doi = {10.1145/3046678}, journal = {ACM Trans. Archit. Code Optim.}, month = mar, articleno = {9}, numpages = {25}, keywords = {low overhead, value-based checking, GPU race detection, instrumentation-free} }
POMACS
A Simple Yet Effective Balanced Edge Partition Model for Parallel Computing

Lingda Li, Robel Geda, Ari B. Hayes, and 4 more authors

Proc. ACM Meas. Anal. Comput. Syst., Jun 2017

Abs Bib HTML PDF

Graph edge partition models have recently become an appealing alternative to graph vertex partition models for distributed computing due to their flexibility in balancing loads and their performance in reducing communication cost [6, 16]. In this paper, we propose a simple yet effective graph edge partitioning algorithm. In practice, our algorithm provides good partition quality (and better than similar state-of-the-art edge partition approaches, at least for power-law graphs) while maintaining low partition overhead. In theory, previous work [6] showed that an approximation guarantee of O(dmax√ log n log k) apply to the graphs with m=Ω(k2) edges (k is the number of partitions). We further rigorously proved that this approximation guarantee hold for all graphs.We show how our edge partition model can be applied to parallel computing. We draw our example from GPU program locality enhancement and demonstrate that the graph edge partition model does not only apply to distributed computing with many computer nodes, but also to parallel computing in a single computer node with a many-core processor.
@article{lietalpomacs17, author = {Li, Lingda and Geda, Robel and Hayes, Ari B. and Chen, Yanhao and Chaudhari, Pranav and Zhang, Eddy Z. and Szegedy, Mario}, title = {A Simple Yet Effective Balanced Edge Partition Model for Parallel Computing}, year = {2017}, issue_date = {June 2017}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, volume = {1}, number = {1}, doi = {10.1145/3084451}, journal = {Proc. ACM Meas. Anal. Comput. Syst.}, month = jun, articleno = {14}, numpages = {21}, keywords = {gpu, data sharing, program locality, graph model, edge partition} }
SIGMETRICS
A Simple Yet Effective Balanced Edge Partition Model for Parallel Computing

Lingda Li, Robel Geda, Ari B. Hayes, and 4 more authors

In Proceedings of the 2017 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, Jun 2017

Abs Bib HTML PDF

Graph edge partition models have recently become an appealing alternative to graph vertex partition models for distributed computing due to both their flexibility in balancing loads and their performance in reducing communication cost.In this paper, we propose a simple yet effective graph edge partitioning algorithm. In practice, our algorithm provides good partition quality while maintaining low partition overhead. It also outperforms similar state-of-the-art edge partition approaches, especially for power-law graphs. In theory, previous work showed that an approximation guarantee of O(dmax√(log n log k)) apply to the graphs with m=Ω(k2) edges (n is the number of vertices, and k is the number of partitions). We further rigorously proved that this approximation guarantee hold for all graphs.We also demonstrate the applicability of the proposed edge partition algorithm in real parallel computing systems. We draw our example from GPU program locality enhancement and demonstrate that the graph edge partition model does not only apply to distributed computing with many computer nodes, but also to parallel computing in a single computer node with a many-core processor.
@inproceedings{lietalsigmetrics17, author = {Li, Lingda and Geda, Robel and Hayes, Ari B. and Chen, Yanhao and Chaudhari, Pranav and Zhang, Eddy Z. and Szegedy, Mario}, title = {A Simple Yet Effective Balanced Edge Partition Model for Parallel Computing}, year = {2017}, isbn = {9781450350327}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, doi = {10.1145/3078505.3078520}, booktitle = {Proceedings of the 2017 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems}, pages = {6}, numpages = {1}, keywords = {edge partition, GPU, program locality, graph model, data sharing}, location = {Urbana-Champaign, Illinois, USA}, series = {SIGMETRICS '17 Abstracts} }
USENIX ATC
GPU Taint Tracking

Ari B. Hayes, Lingda Li, Mohammad Hedayati, and 3 more authors

In Proceedings of the 2017 USENIX Conference on Usenix Annual Technical Conference, Jun 2017

Abs Bib PDF

Dynamic tainting tracks the influence of certain inputs (taint sources) through execution and it is a powerful tool for information flow analysis and security. Taint tracking has primarily targeted CPU program executions. Motivated by recent recognition of information leaking in GPU memory and GPU-resident malware, this paper presents the first design and prototype implementation of a taint tracking system on GPUs. Our design combines a static binary instrumentation with dynamic tainting at runtime. We present new performance optimizations by exploiting unique GPU characteristics–a large portion of instructions on GPU runtime parameters and constant memory can be safely eliminated from taint tracking; large GPU register file allows fast maintenance of a hot portion of the taint map. Experiments show that these techniques improved the GPU taint tracking performance by 5 to 20 times for a range of image processing, data encryption, and deep learning applications. We further demonstrate that GPU taint tracking can enable zeroing sensitive data to minimize information leaking as well as identifying and countering GPU-resident malware.
@inproceedings{hayesetalatc17, author = {Hayes, Ari B. and Li, Lingda and Hedayati, Mohammad and He, Jiahuan and Zhang, Eddy Z. and Shen, Kai}, title = {GPU Taint Tracking}, year = {2017}, isbn = {9781931971386}, publisher = {USENIX Association}, address = {USA}, booktitle = {Proceedings of the 2017 USENIX Conference on Usenix Annual Technical Conference}, pages = {209–220}, numpages = {12}, location = {Santa Clara, CA, USA}, series = {USENIX ATC '17} }

2016

Middleware
Orion: A Framework for GPU Occupancy Tuning

Ari B. Hayes, Lingda Li, Daniel Chavarrı́a-Miranda, and 2 more authors

In Proceedings of the 17th International Middleware Conference, Jun 2016

Abs Bib PDF

An important feature of modern GPU architectures is variable occupancy. Occupancy measures the ratio between the actual number of threads actively running on a GPU and the maximum number of threads that can be scheduled on a GPU. High-occupancy execution enables a large number of threads to run simultaneously and to hide memory latency, but may increase resource contention. Low-occupancy execution leads to less resource contention, but is less capable of hiding memory latency. Occupancy tuning is an important and challenging problem. A program running at two different occupancy levels can have three to four times difference in performance.We introduce Orion, the first GPU program occupancy tuning framework. The Orion framework automatically generates and chooses occupancy-adaptive code for any given GPU program. It is capable of finding the (near-)optimal occupancy level by combining static and dynamic tuning techniques. We demonstrate the efficiency of Orion with twelve representative benchmarks from the Rodinia benchmark suite and CUDA SDK evaluated on two different GPU architectures, obtaining up to 1.61 times speedup, 62.5% memory resource saving, and 6.7% energy saving compared to the baseline of optimized code compiled by nvcc.
@inproceedings{hayesetalmiddleware16, author = {Hayes, Ari B. and Li, Lingda and Chavarr\'{\i}a-Miranda, Daniel and Song, Shuaiwen Leon and Zhang, Eddy Z.}, title = {Orion: A Framework for GPU Occupancy Tuning}, year = {2016}, isbn = {9781450343008}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/2988336.2988355}, doi = {10.1145/2988336.2988355}, booktitle = {Proceedings of the 17th International Middleware Conference}, articleno = {18}, numpages = {13}, keywords = {Shared Memory Allocation, GPU Compiler, Concurrent Program Compilation, Register Allocation, Occupancy Tuning}, location = {Trento, Italy}, series = {Middleware '16} }

DATE

Critical points based register-concurrency autotuning for GPUs

Ang Li, Shuaiwen Leon Song, Akash Kumar, and 3 more authors

In 2016 Design, Automation & Test in Europe Conference & Exhibition (DATE), Jun 2016

Bib PDF

@inproceedings{li+:date16,
  author = {Li, Ang and Song, Shuaiwen Leon and Kumar, Akash and Zhang, Eddy Z. and Chavarría-Miranda, Daniel and Corporaal, Henk},
  booktitle = {2016 Design, Automation & Test in Europe Conference & Exhibition (DATE)},
  title = {Critical points based register-concurrency autotuning for GPUs},
  year = {2016},
  volume = {},
  number = {},
  pages = {1273-1278},
  doi = {}
}

HPDC
New-Sum: A Novel Online ABFT Scheme For General Iterative Methods

Dingwen Tao, Shuaiwen Leon Song, Sriram Krishnamoorthy, and 5 more authors

In Proceedings of the 25th ACM International Symposium on High-Performance Parallel and Distributed Computing, Jun 2016

Abs Bib HTML PDF

Emerging high-performance computing platforms, with large component counts and lower power margins, are anticipated to be more susceptible to soft errors in both logic circuits and memory subsystems. We present an online algorithm-based fault tolerance (ABFT) approach to efficiently detect and recover soft errors for general iterative methods. We design a novel checksum-based encoding scheme for matrix-vector multiplication that is resilient to both arithmetic and memory errors. Our design decouples the checksum updating process from the actual computation, and allows adaptive checksum overhead control. Building on this new encoding mechanism, we propose two online ABFT designs that can effectively recover from errors when combined with a checkpoint/rollback scheme. These designs are capable of addressing scenarios under different error rates. Our ABFT approaches apply to a wide range of iterative solvers that primarily rely on matrix-vector multiplication and vector linear operations. We evaluate our designs through comprehensive analytical and empirical analysis. Experimental evaluation on the Stampede supercomputer demonstrates the low performance overheads incurred by our two ABFT schemes for preconditioned CG (0.4% and 2.2%) and preconditioned BiCGSTAB (1.0% and 4.0%) for the largest SPD matrix from UFL Sparse Matrix Collection. The evaluation also demonstrates the flexibility and effectiveness of our proposed designs for detecting and recovering various types of soft errors in general iterative methods.
@inproceedings{tao+:hpdc16, author = {Tao, Dingwen and Song, Shuaiwen Leon and Krishnamoorthy, Sriram and Wu, Panruo and Liang, Xin and Zhang, Eddy Z. and Kerbyson, Darren and Chen, Zizhong}, title = {New-Sum: A Novel Online ABFT Scheme For General Iterative Methods}, year = {2016}, isbn = {9781450343145}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, doi = {10.1145/2907294.2907306}, booktitle = {Proceedings of the 25th ACM International Symposium on High-Performance Parallel and Distributed Computing}, pages = {43–55}, numpages = {13}, keywords = {checksum, rollback recovery, resilience, algorithm-based fault tolerance (abft), online error detection, iterative methods, silent data corruption (sdc), checkpoint}, location = {Kyoto, Japan}, series = {HPDC '16} }
ICS
Tag-Split Cache for Efficient GPGPU Cache Utilization

Lingda Li, Ari B. Hayes, Shuaiwen Leon Song, and 1 more author

In Proceedings of the 2016 International Conference on Supercomputing, Jun 2016

Abs Bib HTML PDF

Modern GPUs employ cache to improve memory system efficiency. However, large amount of cache space is underutilized due to irregular memory accesses and poor spatial locality which exhibited commonly in GPU applications. Our experiments show that using smaller cache lines could improve cache space utilization, but it also frequently suffers from significant performance loss by introducing large amount of extra cache requests. In this work, we propose a novel cache design named tag-split cache (TSC) that enables fine-grained cache storage to address the problem of cache space underutilization while keeping memory request number unchanged. TSC divides tag into two parts to reduce storage overhead, and it supports multiple cache line replacement in one cycle. TSC can also automatically adjust cache storage granularity to avoid performance loss for applications with good spatial locality. Our evaluation shows that TSC improves the baseline cache performance by 17.2% on average across a wide range of applications. It also out-performs other previous techniques significantly.
@inproceedings{li+:ics16, author = {Li, Lingda and Hayes, Ari B. and Song, Shuaiwen Leon and Zhang, Eddy Z.}, title = {Tag-Split Cache for Efficient GPGPU Cache Utilization}, year = {2016}, isbn = {9781450343619}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, doi = {10.1145/2925426.2926253}, booktitle = {Proceedings of the 2016 International Conference on Supercomputing}, articleno = {43}, numpages = {12}, keywords = {GPGPU, Spatial Locality, Cache Organization}, location = {Istanbul, Turkey}, series = {ICS '16} }

2014

ICS
Unified On-Chip Memory Allocation for SIMT Architecture

Ari B. Hayes, and Eddy Z. Zhang

In Proceedings of the 28th ACM International Conference on Supercomputing, Jun 2014

Abs Bib HTML PDF

The popularity of general purpose Graphic Processing Unit (GPU) is largely attributed to the tremendous concurrency enabled by its underlying architecture – single instruction multiple thread (SIMT) architecture. It keeps the context of a significant number of threads in registers to enable fast “context switches" when the processor is stalled due to execution dependence, memory requests and etc. The SIMT architecture has a large register file evenly partitioned among all concurrent threads. Per-thread register usage determines the number of concurrent threads, which strongly affects the whole program performance. Existing register allocation techniques, extensively studied in the past several decades, are oblivious to the register contention due to the concurrent execution of many threads. They are prone to making optimization decisions that benefit single thread but degrade the whole application performance.Is it possible for compilers to make register allocation decisions that can maximize the whole GPU application performance? We tackle this important question from two different aspects in this paper. We first propose an unified on-chip memory allocation framework that uses scratch-pad memory to help: (1) alleviate single-thread register pressure; (2) increase whole application throughput. Secondly, we propose a characterization model for the SIMT execution model in order to achieve a desired on-chip memory partition given the register pressure of a program. Overall, we discovered that it is possible to automatically determine an on-chip memory resource allocation that maximizes concurrency while ensuring good single-thread performance at compile-time. We evaluated our techniques on a representative set of GPU benchmarks with non-trivial register pressure. We are able to achieve up to 1.70 times speedup over the baseline of the traditional register allocation scheme that maximizes single thread performance.
@inproceedings{hayesetalics14, author = {Hayes, Ari B. and Zhang, Eddy Z.}, title = {Unified On-Chip Memory Allocation for SIMT Architecture}, year = {2014}, isbn = {9781450326421}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, doi = {10.1145/2597652.2597685}, booktitle = {Proceedings of the 28th ACM International Conference on Supercomputing}, pages = {293–302}, numpages = {10}, keywords = {concurrency, register allocation, compiler optimization, gpu, shared memory allocation}, location = {Munich, Germany}, series = {ICS '14} }
ISMM
Massive Atomics for Massive Parallelism on GPUs

Ian J. Egielski, Jesse Huang, and Eddy Z. Zhang

In Proceedings of the 2014 International Symposium on Memory Management, Jun 2014

Abs Bib HTML PDF

One important type of parallelism exploited in many applications is reduction type parallelism. In these applications, the order of the read-modify-write updates to one shared data object can be arbitrary as long as there is an imposed order for the read-modify-write updates. The typical way to parallelize these types of applications is to first let every individual thread perform local computation and save the results in thread-private data objects, and then merge the results from all worker threads in the reduction stage. All applications that fit into the map reduce framework belong to this category. Additionally, the machine learning, data mining, numerical analysis and scientific simulation applications may also benefit from reduction type parallelism. However, the parallelization scheme via the usage of thread-private data objects may not be vi- able in massively parallel GPU applications. Because the number of concurrent threads is extremely large (at least tens of thousands of), thread-private data object creation may lead to memory space explosion problems.In this paper, we propose a novel approach to deal with shared data object management for reduction type parallelism on GPUs. Our approach exploits fine-grained parallelism while at the same time maintaining good programmability. It is based on the usage of intrinsic hardware atomic instructions. Atomic operation may appear to be expensive since it causes thread serialization when multiple threads atomically update the same memory object at the same time. However, we discovered that, with appropriate atomic collision reduction techniques, the atomic implementation can out- perform the non-atomics implementation, even for benchmarks known to have high performance non-atomics GPU implementations. In the meantime, the usage of atomics can greatly reduce coding complexity as neither thread-private object management or explicit thread-communication (for the shared data objects protected by atomic operations) is necessary.
@inproceedings{egielski+:ismm14, author = {Egielski, Ian J. and Huang, Jesse and Zhang, Eddy Z.}, title = {Massive Atomics for Massive Parallelism on GPUs}, year = {2014}, isbn = {9781450329217}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, doi = {10.1145/2602988.2602993}, booktitle = {Proceedings of the 2014 International Symposium on Memory Management}, pages = {93–103}, numpages = {11}, keywords = {concurrency, parallelism, atomics, gpu}, location = {Edinburgh, United Kingdom}, series = {ISMM '14} }

2013

JParallel
An Infrastructure for Tackling Input-Sensitivity of GPU Program Optimizations

Xipeng Shen, Yixun Liu, Eddy Z. Zhang, and 1 more author

Int. J. Parallel Program., Dec 2013

Abs Bib HTML PDF

Graphic processing units (GPU) have become increasingly adopted for the enhancement of computing throughput. However, the development of a high-quality GPU application is challenging, due to the large optimization space and complex unpredictable effects of optimizations on GPU program performance. Many recent efforts have been employing empirical search-based auto-tuners to tackle the problem, but few of them have concentrated on the influence of program inputs on the optimizations. In this paper, based on a set of CUDA and OpenCL kernels, we report some evidences on the importance for auto-tuners to adapt to program input changes, and present a framework, G-ADAPT+, to address the influence by constructing cross-input predictive models for automatically predicting the (near-)optimal configurations for an arbitrary input to a GPU program. G-ADAPT+ is based on source-to-source compilers, specifically, Cetus and ROSE. It supports the optimizations of both CUDA and OpenCL programs.
@article{shen+:jpp13, author = {Shen, Xipeng and Liu, Yixun and Zhang, Eddy Z. and Bhamidipati, Poornima}, title = {An Infrastructure for Tackling Input-Sensitivity of GPU Program Optimizations}, year = {2013}, issue_date = {December 2013}, publisher = {Kluwer Academic Publishers}, address = {USA}, volume = {41}, number = {6}, issn = {0885-7458}, doi = {10.1007/s10766-012-0236-3}, journal = {Int. J. Parallel Program.}, month = dec, pages = {855–869}, numpages = {15}, keywords = {Cross-input Adaptation, CUDA, GPU, Program Optimizations, Empirical Search, G-ADAPT} }
PPoPP
Complexity Analysis and Algorithm Design for Reorganizing Data to Minimize Non-Coalesced Memory Accesses on GPU

Bo Wu, Zhijia Zhao, Eddy Zheng Zhang, and 2 more authors

In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Dec 2013

Abs Bib HTML PDF

The performance of Graphic Processing Units (GPU) is sensitive to irregular memory references. Some recent work shows the promise of data reorganization for eliminating non-coalesced memory accesses that are caused by irregular references. However, all previous studies have employed simple, heuristic methods to determine the new data layouts to create. As a result, they either do not provide any performance guarantee or are effective to only some limited scenarios. This paper contributes a fundamental study to the problem. It systematically analyzes the inherent complexity of the problem in various settings, and for the first time, proves that the problem is NP-complete. It then points out the limitations of existing techniques and reveals that in practice, the essence for designing an appropriate data reorganization algorithm can be reduced to a tradeoff among space, time, and complexity. Based on that insight, it develops two new data reorganization algorithms to overcome the limitations of previous methods. Experiments show that an assembly composed of the new algorithms and a previous algorithm can circumvent the inherent complexity in finding optimal data layouts, making it feasible to minimize non-coalesced memory accesses for a variety of irregular applications and settings that are beyond the reach of existing techniques.
@inproceedings{wu+:ppopp13, author = {Wu, Bo and Zhao, Zhijia and Zhang, Eddy Zheng and Jiang, Yunlian and Shen, Xipeng}, title = {Complexity Analysis and Algorithm Design for Reorganizing Data to Minimize Non-Coalesced Memory Accesses on GPU}, year = {2013}, isbn = {9781450319225}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, doi = {10.1145/2442516.2442523}, booktitle = {Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming}, pages = {57–68}, numpages = {12}, keywords = {gpgpu, memory coalescing, computational complexity, data transformation, runtime optimizations, thread-data remapping}, location = {Shenzhen, China}, series = {PPoPP '13} }

2012

TPDS

The Significance of CMP Cache Sharing on Contemporary Multithreaded Applications

Eddy Z. Zhang, Yunlian Jiang, and Xipeng Shen

IEEE Transactions on Parallel and Distributed Systems, Dec 2012

Bib PDF

@article{zhang+:tpds12,
  author = {Zhang, Eddy Z. and Jiang, Yunlian and Shen, Xipeng},
  journal = {IEEE Transactions on Parallel and Distributed Systems},
  title = {The Significance of CMP Cache Sharing on Contemporary Multithreaded Applications},
  year = {2012},
  volume = {23},
  number = {2},
  pages = {367-374},
  doi = {10.1109/TPDS.2011.130}
}

2011

ASPLOS
On-the-Fly Elimination of Dynamic Irregularities for GPU Computing

Eddy Z. Zhang, Yunlian Jiang, Ziyu Guo, and 2 more authors

In Proceedings of the Sixteenth International Conference on Architectural Support for Programming Languages and Operating Systems, Dec 2011

Abs Bib HTML PDF

The power-efficient massively parallel Graphics Processing Units (GPUs) have become increasingly influential for general-purpose computing over the past few years. However, their efficiency is sensitive to dynamic irregular memory references and control flows in an application. Experiments have shown great performance gains when these irregularities are removed. But it remains an open question how to achieve those gains through software approaches on modern GPUs.This paper presents a systematic exploration to tackle dynamic irregularities in both control flows and memory references. It reveals some properties of dynamic irregularities in both control flows and memory references, their interactions, and their relations with program data and threads. It describes several heuristics-based algorithms and runtime adaptation techniques for effectively removing dynamic irregularities through data reordering and job swapping. It presents a framework, G-Streamline, as a unified software solution to dynamic irregularities in GPU computing. G-Streamline has several distinctive properties. It is a pure software solution and works on the fly, requiring no hardware extensions or offline profiling. It treats both types of irregularities at the same time in a holistic fashion, maximizing the whole-program performance by resolving conflicts among optimizations. Its optimization overhead is largely transparent to GPU kernel executions, jeopardizing no basic efficiency of the GPU application. Finally, it is robust to the presence of various complexities in GPU applications. Experiments show that G-Streamline is effective in reducing dynamic irregularities in GPU computing, producing speedups between 1.07 and 2.5 for a variety of applications.
@inproceedings{zhangetalasplos11, author = {Zhang, Eddy Z. and Jiang, Yunlian and Guo, Ziyu and Tian, Kai and Shen, Xipeng}, title = {On-the-Fly Elimination of Dynamic Irregularities for GPU Computing}, year = {2011}, isbn = {9781450302661}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, doi = {10.1145/1950365.1950408}, booktitle = {Proceedings of the Sixteenth International Conference on Architectural Support for Programming Languages and Operating Systems}, pages = {369–380}, numpages = {12}, keywords = {thread divergence, thread data remapping, gpgpu, cpu-gpu pipelining, data transformation, memory coalescing}, location = {Newport Beach, California, USA}, series = {ASPLOS XVI} }
OOPSLA
A Step towards Transparent Integration of Input-Consciousness into Dynamic Program Optimizations

Kai Tian, Eddy Zhang, and Xipeng Shen

In Proceedings of the 2011 ACM International Conference on Object Oriented Programming Systems Languages and Applications, Dec 2011

Abs Bib HTML PDF

Dynamic program optimizations are critical for the efficiency of applications in managed programming languages and scripting languages. Recent studies have shown that exploitation of program inputs may enhance the effectiveness of dynamic optimizations significantly. However, current solutions for enabling the exploitation require either programmers’ annotations or intensive offline profiling, impairing the practical adoption of the techniques.This current work examines the basic feasibility of transparent integration of input-consciousness into dynamic program optimizations, particularly in managed execution environments. It uses transparent learning across production runs as the basic vehicle, and investigates the implications of cross-run learning on each main component of input-conscious dynamic optimizations. It proposes several techniques to address some key challenges for the transparent integration, including randomized inspection-instrumentation for cross-user data collection, a sparsity-tolerant algorithm for input characterization, and selective prediction for efficiency protection. These techniques make it possible to automatically recognize the relations between the inputs to a program and the appropriate ways to optimize it. The whole process happens transparently across production runs; no need for offline profiling or programmer intervention. Experiments on a number of Java programs demonstrate the effectiveness of the techniques in enabling input-consciousness for dynamic optimizations, revealing the feasibility and potential benefits of the new optimization paradigm in some basic settings.
@inproceedings{tian+:oopsla11, author = {Tian, Kai and Zhang, Eddy and Shen, Xipeng}, title = {A Step towards Transparent Integration of Input-Consciousness into Dynamic Program Optimizations}, year = {2011}, isbn = {9781450309400}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, doi = {10.1145/2048066.2048103}, booktitle = {Proceedings of the 2011 ACM International Conference on Object Oriented Programming Systems Languages and Applications}, pages = {445–462}, numpages = {18}, keywords = {dynamic version selection, just-in-time compilation, java virtual machine, program inputs, proactivity, seminal behaviors, dynamic optimizations}, location = {Portland, Oregon, USA}, series = {OOPSLA '11} }

PACT

Correctly Treating Synchronizations in Compiling Fine-Grained SPMD-Threaded Programs for CPU

Ziyu Guo, Eddy Zheng Zhang, and Xipeng Shen

In 2011 International Conference on Parallel Architectures and Compilation Techniques, Dec 2011

Bib PDF

@inproceedings{guo+:pact11,
  author = {Guo, Ziyu and Zhang, Eddy Zheng and Shen, Xipeng},
  booktitle = {2011 International Conference on Parallel Architectures and Compilation Techniques},
  title = {Correctly Treating Synchronizations in Compiling Fine-Grained SPMD-Threaded Programs for CPU},
  year = {2011},
  volume = {},
  number = {},
  pages = {310-319},
  doi = {10.1109/PACT.2011.62}
}

PACT

Enhancing Data Locality for Dynamic Simulations through Asynchronous Data Transformations and Adaptive Control

Bo Wu, Eddy Z. Zhang, and Xipeng Shen

In 2011 International Conference on Parallel Architectures and Compilation Techniques, Dec 2011

Bib PDF

@inproceedings{wu+:pact11,
  author = {Wu, Bo and Zhang, Eddy Z. and Shen, Xipeng},
  booktitle = {2011 International Conference on Parallel Architectures and Compilation Techniques},
  title = {Enhancing Data Locality for Dynamic Simulations through Asynchronous Data Transformations and Adaptive Control},
  year = {2011},
  volume = {},
  number = {},
  pages = {243-252},
  doi = {10.1109/PACT.2011.56}
}

2010

JPEVA
Trace data characterization and fitting for Markov modeling

Giuliano Casale, Eddy Z. Zhang, and Evgenia Smirni

Performance Evaluation, Dec 2010

Abs Bib HTML PDF

We propose a trace fitting algorithm for Markovian Arrival Processes (MAPs) that can capture statistics of any order of interarrival times between measured events. By studying real traffic and workload traces often used in performance evaluation studies, we show that matching higher order statistical properties, in addition to first and second order descriptors, results in increased queueing prediction accuracy with respect to algorithms that only match the mean, the coefficient of variation, and the autocorrelations of the trace. This result supports the approach of modeling traces by the interarrival time process instead of the counting process that is more frequently used in the literature. We proceed by first characterizing the general properties of MAPs using a spectral approach. Based on this result, we show how different MAPs can be combined together using Kronecker products to define a larger MAP with predefined properties of interarrival times. We then devise an algorithm that is based on this Kronecker composition and can accurately fit data traces. This MAP fitting algorithm uses nonlinear optimization that can be customized to fit an arbitrary number of moments and to meet the desired cost-accuracy tradeoff. Numerical results of the fitting algorithm on real data, such as the Bellcore Aug89 trace and a Seagate disk drive trace, indicate that the proposed fitting technique achieves increased prediction accuracy with respect to other state-of-the-art fitting methods.
@article{casaleetaljpeva10, title = {Trace data characterization and fitting for Markov modeling}, journal = {Performance Evaluation}, volume = {67}, number = {2}, pages = {61-79}, year = {2010}, issn = {0166-5316}, doi = {https://doi.org/10.1016/j.peva.2009.09.003}, author = {Casale, Giuliano and Zhang, Eddy Z. and Smirni, Evgenia}, keywords = {Markovian arrival process, Fitting algorithm, Time series modeling, Temporal dependence, Correlations} }
JPEVA
KPC-Toolbox: Best Recipes for Automatic Trace Fitting Using Markovian Arrival Processes

Giuliano Casale, Eddy Z. Zhang, and Evgenia Smirni

Perform. Eval., Sep 2010

Abs Bib HTML PDF

We present the KPC-Toolbox, a library of MATLAB scripts for fitting workload traces into Markovian Arrival Processes (MAPs) in an automatic way based on the recently proposed Kronecker Product Composition (KPC) method. We first present detailed sensitivity analysis that builds intuition on which trace descriptors are the most important for queueing performance, stressing the advantages of matching higher-order correlations of the process rather than higher-order moments of the distribution. Given that the MAP parameterization space can be very large, we focus on first determining the order of the smallest MAP that can fit the trace well using the Bayesian Information Criterion (BIC). The KPC-Toolbox then automatically derives a MAP that captures accurately the most essential features of the trace. Extensive experimentation illustrates the effectiveness of the KPC-Toolbox in fitting traces that are well documented in the literature as very challenging to fit, showing that the KPC-Toolbox offers a simple and powerful solution to fitting accurately trace data into MAPs. We provide a characterization of moments and correlations that can be fitted exactly by KPC, thus showing the wider applicability of the method compared to small order MAPs. We also consider the fitting of phase-type (PH-type) distributions, which are an important specialization of MAPs that are useful for describing traces without correlations in their time series. We illustrate that the KPC methodology can be easily adapted to PH-type fitting and present experimental results on networking and disk drive traces showing that the KPC-Toolbox can also match accurately higher-order moments of the inter-arrival times in place of correlations.
@article{casale+:jpeva10, author = {Casale, Giuliano and Zhang, Eddy Z. and Smirni, Evgenia}, title = {KPC-Toolbox: Best Recipes for Automatic Trace Fitting Using Markovian Arrival Processes}, year = {2010}, issue_date = {September, 2010}, publisher = {Elsevier Science Publishers B. V.}, address = {NLD}, volume = {67}, number = {9}, issn = {0166-5316}, doi = {10.1016/j.peva.2009.12.003}, journal = {Perform. Eval.}, month = sep, pages = {873–896}, numpages = {24}, keywords = {MAP characterization, Phase-type distribution, Automatic fitting, Time series modeling, Markovian Arrival Process, Temporal dependence} }
PPoPP
Does Cache Sharing on Modern CMP Matter to the Performance of Contemporary Multithreaded Programs?

Eddy Z. Zhang, Yunlian Jiang, and Xipeng Shen

In Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Sep 2010

Abs Bib HTML PDF

Most modern Chip Multiprocessors (CMP) feature shared cache on chip. For multithreaded applications, the sharing reduces communication latency among co-running threads, but also results in cache contention.A number of studies have examined the influence of cache sharing on multithreaded applications, but most of them have concentrated on the design or management of shared cache, rather than a systematic measurement of the influence. Consequently, prior measurements have been constrained by the reliance on simulators, the use of out-of-date benchmarks, and the limited coverage of deciding factors. The influence of CMP cache sharing on contemporary multithreaded applications remains preliminarily understood.In this work, we conduct a systematic measurement of the influence on two kinds of commodity CMP machines, using a recently released CMP benchmark suite, PARSEC, with a number of potentially important factors on program, OS, and architecture levels considered. The measurement shows some surprising results. Contrary to commonly perceived importance of cache sharing, neither positive nor negative effects from the cache sharing are significant for most of the program executions, regardless of the types of parallelism, input datasets, architectures, numbers of threads, and assignments of threads to cores. After a detailed analysis, we find that the main reason is the mismatch of current development and compilation of multithreaded applications and CMP architectures. By transforming the programs in a cache-sharing-aware manner, we observe up to 36% performance increase when the threads are placed on cores appropriately.
@inproceedings{zhangetalppopp10, author = {Zhang, Eddy Z. and Jiang, Yunlian and Shen, Xipeng}, title = {Does Cache Sharing on Modern CMP Matter to the Performance of Contemporary Multithreaded Programs?}, year = {2010}, isbn = {9781605588773}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, doi = {10.1145/1693453.1693482}, booktitle = {Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming}, pages = {203–212}, numpages = {10}, keywords = {shared cache, thread scheduling, chip multiprocessors, parallel program optimizations}, location = {Bangalore, India}, series = {PPoPP '10} }
CGO
Exploiting Statistical Correlations for Proactive Prediction of Program Behaviors

Yunlian Jiang, Eddy Z. Zhang, Kai Tian, and 4 more authors

In Proceedings of the 8th Annual IEEE/ACM International Symposium on Code Generation and Optimization, Sep 2010

Abs Bib HTML PDF

This paper presents a finding and a technique on program behavior prediction. The finding is that surprisingly strong statistical correlations exist among the behaviors of different program components (e.g., loops) and among different types of program level behaviors (e.g., loop trip-counts versus data values). Furthermore, the correlations can be beneficially exploited: They help resolve the proactivity-adaptivity dilemma faced by existing program behavior predictions, making it possible to gain the strengths of both approaches–the large scope and earliness of offline-profiling–based predictions, and the cross-input adaptivity of runtime sampling-based predictions.The main technique contributed by this paper centers on a new concept, seminal behaviors. Enlightened by the existence of strong correlations among program behaviors, we propose a regression based framework to automatically identify a small set of behaviors that can lead to accurate prediction of other behaviors in a program. We call these seminal behaviors. By applying statistical learning techniques, the framework constructs predictive models that map from seminal behaviors to other behaviors, enabling proactive and cross-input adaptive prediction of program behaviors. The prediction helps a commercial compiler, the IBM XL C compiler, generate code that runs up to 45% faster (5%-13% on average), demonstrating the large potential of correlation-based techniques for program optimizations.
@inproceedings{jiang+:cgo10, author = {Jiang, Yunlian and Zhang, Eddy Z. and Tian, Kai and Mao, Feng and Gethers, Malcom and Shen, Xipeng and Gao, Yaoqing}, title = {Exploiting Statistical Correlations for Proactive Prediction of Program Behaviors}, year = {2010}, isbn = {9781605586359}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, doi = {10.1145/1772954.1772989}, booktitle = {Proceedings of the 8th Annual IEEE/ACM International Symposium on Code Generation and Optimization}, pages = {248–256}, numpages = {9}, keywords = {program behavior, correlation}, location = {Toronto, Ontario, Canada}, series = {CGO '10} }

Is Reuse Distance Applicable to Data Locality Analysis on Chip Multiprocessors?

Yunlian Jiang, Eddy Z. Zhang, Kai Tian, and 1 more author

In Compiler Construction, Sep 2010

Abs Bib PDF

@inproceedings{jiang+:cc10,
  author = {Jiang, Yunlian and Zhang, Eddy Z. and Tian, Kai and Shen, Xipeng},
  editor = {Gupta, Rajiv},
  title = {Is Reuse Distance Applicable to Data Locality Analysis on Chip Multiprocessors?},
  booktitle = {Compiler Construction},
  year = {2010},
  publisher = {Springer Berlin Heidelberg},
  address = {Berlin, Heidelberg},
  pages = {264--282},
  isbn = {978-3-642-11970-5}
}

ICS
Streamlining GPU Applications on the Fly: Thread Divergence Elimination through Runtime Thread-Data Remapping

Eddy Z. Zhang, Yunlian Jiang, Ziyu Guo, and 1 more author

In Proceedings of the 24th ACM International Conference on Supercomputing, Sep 2010

Abs Bib HTML PDF

Because of their tremendous computing power and remarkable cost efficiency, GPUs (graphic processing unit) have quickly emerged as a kind of influential platform for high performance computing. However, as GPUs are designed for massive data-parallel computing, their performance is subject to the presence of condition statements in a GPU application. On a conditional branch where threads diverge in which path to take, the threads taking different paths have to run serially. Such divergences often cause serious performance degradations, impairing the adoption of GPU for many applications that contain non-trivial branches or certain types of loops.This paper presents a systematic investigation in the employment of runtime thread-data remapping for solving that problem. It introduces an abstract form of GPU applications, based on which, it describes the use of reference redirection and data layout transformation for remapping data and threads to minimize thread divergences. It discusses the major challenges for practical deployment of the remapping techniques, most notably, the conflict between the large remapping overhead and the need for the remapping to happen on the fly because of the dependence of thread divergences on runtime values. It offers a solution to the challenge by proposing a CPU-GPU pipelining scheme and a label-assign-move (LAM) algorithm to virtually hide all the remapping overhead. At the end, it reports significant performance improvement produced by the remapping for a set of GPU applications, demonstrating the potential of the techniques for streamlining GPU applications on the fly.
@inproceedings{zhangetalics10, author = {Zhang, Eddy Z. and Jiang, Yunlian and Guo, Ziyu and Shen, Xipeng}, title = {Streamlining GPU Applications on the Fly: Thread Divergence Elimination through Runtime Thread-Data Remapping}, year = {2010}, isbn = {9781450300186}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, doi = {10.1145/1810085.1810104}, booktitle = {Proceedings of the 24th ACM International Conference on Supercomputing}, pages = {115–126}, numpages = {12}, keywords = {thread divergence, GPGPU, thread-data remapping, data transformation, CPU-GPU pipelining}, location = {Tsukuba, Ibaraki, Japan}, series = {ICS '10} }
OOPSLA
An Input-Centric Paradigm for Program Dynamic Optimizations

Kai Tian, Yunlian Jiang, Eddy Z. Zhang, and 1 more author

In Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications, Sep 2010

Abs Bib HTML PDF

Accurately predicting program behaviors (e.g., locality, dependency, method calling frequency) is fundamental for program optimizations and runtime adaptations. Despite decades of remarkable progress, prior studies have not systematically exploited program inputs, a deciding factor for program behaviors.Triggered by the strong and predictive correlations between program inputs and behaviors that recent studies have uncovered, this work proposes to include program inputs into the focus of program behavior analysis, cultivating a new paradigm named input-centric program behavior analysis. This new approach consists of three components, forming a three-layer pyramid. At the base is program input characterization, a component for resolving the complexity in program raw inputs and the extraction of important features. In the middle is input-behavior modeling, a component for recognizing and modeling the correlations between characterized input features and program behaviors. These two components constitute input-centric program behavior analysis, which (ideally) is able to predict the large-scope behaviors of a program’s execution as soon as the execution starts. The top layer of the pyramid is input-centric adaptation, which capitalizes on the novel opportunities that the first two components create to facilitate proactive adaptation for program optimizations.By centering on program inputs, the new approach resolves a proactivity-adaptivity dilemma inherent in previous techniques. Its benefits are demonstrated through proactive dynamic optimizations and version selection, yielding significant performance improvement on a set of Java and C programs.
@inproceedings{tian+:oopsla10, author = {Tian, Kai and Jiang, Yunlian and Zhang, Eddy Z. and Shen, Xipeng}, title = {An Input-Centric Paradigm for Program Dynamic Optimizations}, year = {2010}, isbn = {9781450302036}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, doi = {10.1145/1869459.1869471}, booktitle = {Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications}, pages = {125–139}, numpages = {15}, keywords = {proactivity, just-in-time compilation, program inputs, dynamic optimizations, seminal behaviors, dynamic version selection, java virtual machine}, location = {Reno/Tahoe, Nevada, USA}, series = {OOPSLA '10} }

2009

SIGOPSOSR
The Study and Handling of Program Inputs in the Selection of Garbage Collectors

Xipeng Shen, Feng Mao, Kai Tian, and 1 more author

SIGOPS Oper. Syst. Rev., Jul 2009

Abs Bib HTML PDF

Many studies have shown that the best performer among a set of garbage collectors tends to be different for different applications. Researchers have proposed applicationspecific selection of garbage collectors. In this work, we concentrate on a second dimension of the problem: the influence of program inputs on the selection of garbage collectors. We collect tens to hundreds of inputs for a set of Java benchmarks, and measure their performance on Jikes RVM with different heap sizes and garbage collectors. A rigorous statistical analysis produces four-fold insights. First, inputs influence the relative performance of garbage collectors significantly, causing large variations to the top set of garbage collectors across inputs. Profiling one or few runs is thus inadequate for selecting the garbage collector that works well for most inputs. Second, when the heap size ratio is fixed, one or two types of garbage collectors are enough to stimulate the top performance of the program on all inputs. Third, for some programs, the heap size ratio significantly affects the relative performance of different types of garbage collectors. For the selection of garbage collectors on those programs, it is necessary to have a cross-input predictive model that predicts the minimum possible heap size of the execution on an arbitrary input. Finally, by adoptingstatistical learning techniques, we investigate the cross-input predictability of the influence. Experimental results demonstrate that with regression and classification techniques, it is possible to predict the best garbage collector (along with the minimum possible heap size) with reasonable accuracy given an arbitrary input to an application. The exploration opens the opportunities for tailoring the selection of garbage collectors to not only applications but also their inputs.
@article{shen+:sigopsosr09, author = {Shen, Xipeng and Mao, Feng and Tian, Kai and Zhang, Eddy Zheng}, title = {The Study and Handling of Program Inputs in the Selection of Garbage Collectors}, year = {2009}, issue_date = {July 2009}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, volume = {43}, number = {3}, issn = {0163-5980}, doi = {10.1145/1618525.1618531}, journal = {SIGOPS Oper. Syst. Rev.}, month = jul, pages = {48–61}, numpages = {14}, keywords = {profiling, minimum possible heap size, cross-input program analysis, selection of garbage collectors, input-specific selection} }

IPDPS

A cross-input adaptive framework for GPU program optimizations

Yixun Liu, Eddy Z. Zhang, and Xipeng Shen

In 2009 IEEE International Symposium on Parallel & Distributed Processing, Jul 2009

Bib PDF

@inproceedings{liu+:ipdps09,
  author = {Liu, Yixun and Zhang, Eddy Z. and Shen, Xipeng},
  booktitle = {2009 IEEE International Symposium on Parallel & Distributed Processing},
  title = {A cross-input adaptive framework for GPU program optimizations},
  year = {2009},
  volume = {},
  number = {},
  pages = {1-10},
  doi = {10.1109/IPDPS.2009.5160988}
}

VEE
Influence of Program Inputs on the Selection of Garbage Collectors

Feng Mao, Eddy Z. Zhang, and Xipeng Shen

In Proceedings of the 2009 ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments, Jul 2009

Abs Bib HTML PDF

Many studies have shown that the best performer among a set of garbage collectors tends to be different for different applications. Researchers have proposed application-specific selection of garbage collectors. In this work, we concentrate on a second dimension of the problem: the influence of program inputs on the selection of garbage collectors.We collect tens to hundreds of inputs for a set of Java benchmarks, and measure their performance on Jikes RVM with different heap sizes and garbage collectors. A rigorous statistical analysis produces four-fold insights. First, inputs influence the relative performance of garbage collectors significantly, causing large variations to the top set of garbage collectors across inputs. Profiling one or few runs is thus inadequate for selecting the garbage collector that works well for most inputs. Second, when the heap size ratio is fixed, one or two types of garbage collectors are enough to stimulate the top performance of the program on all inputs. Third, for some programs, the heap size ratio significantly affects the relative performance of different types of garbage collectors. For the selection of garbage collectors on those programs, it is necessary to have a cross-input predictive model that predicts the minimum possible heap size of the execution on an arbitrary input. Finally, based on regression techniques, we demonstrate the predictability of the minimum possible heap size, indicating the potential feasibility of the input-specific selection of garbage collectors.
@inproceedings{mao+:vee09, author = {Mao, Feng and Zhang, Eddy Z. and Shen, Xipeng}, title = {Influence of Program Inputs on the Selection of Garbage Collectors}, year = {2009}, isbn = {9781605583754}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, doi = {10.1145/1508293.1508307}, booktitle = {Proceedings of the 2009 ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments}, pages = {91–100}, numpages = {10}, keywords = {cross-input program analysis, input-specific selection, minimum possible heap size, profiling, selection of garbage collectors}, location = {Washington, DC, USA}, series = {VEE '09} }

2008

QEST

KPC-Toolbox: Simple Yet Effective Trace Fitting Using Markovian Arrival Processes

Giuliano Casale, Eddy Z. Zhang, and Evgenia Smirni

In 2008 Fifth International Conference on Quantitative Evaluation of Systems, Jul 2008

Bib PDF

@inproceedings{casaleetalqest08,
  author = {Casale, Giuliano and Zhang, Eddy Z. and Smirni, Evgenia},
  booktitle = {2008 Fifth International Conference on Quantitative Evaluation of Systems},
  title = {KPC-Toolbox: Simple Yet Effective Trace Fitting Using Markovian Arrival Processes},
  year = {2008},
  volume = {},
  number = {},
  pages = {83-92},
  doi = {10.1109/QEST.2008.33}
}