Dissertation/Thesis Abstract

Dynamic Trace Analysis with Zero-Suppressed BDDs
by Price, Graham David, Ph.D., University of Colorado at Boulder, 2011, 224; 3468482
Abstract (Summary)

Instruction level parallelism (ILP) limitations have forced processor manufacturers to develop multi-core platforms with the expectation that programs will be able to exploit thread level parallelism (TLP). Multi-core programming shifts the burden of locating additional performance away from computer hardware to the software developers, who often attempt high-level redesigns focused on exposing thread level parallelism, as well as explore aggressive optimizations for sequential codes.

Precise dynamic analysis can provide useful guidance for program optimization efforts, including efforts to find and extract thread level parallelism. Unfortunately, finding regions of code amenable to further optimization efforts requires analyzing traces that can quickly grow in size. Analysis of large dynamic traces (e.g. one billion instructions or more) is often impractical for commodity hardware.

An ideal representation for dynamic trace data would provide compression. However, decompressing large software traces, even if decompressed data is never permanently stored, would make many analysis impractical. A better solution would allow analysis of the compressed data, without a costly decompression step. Prior works have developed trace compressors that generate an analyzable representation, but often limit the precision or scope of analyses.

Zero-suppressed binary decision diagram (ZDDs) exhibit many of the desired properties of an ideal trace representation. This thesis shows: (1) dynamic trace data may be represented by zero-suppressed binary decision diagrams (ZDDs); (2) ZDDs allow many analyses to scale; (3) encoding traces as ZDDs can be performed in a reasonable amount of time; and, (4) ZDD-based analyses, such as irrelevant instruction detection and potential coarse-grained thread level parallelism extraction, can reveal a number of performance opportunities in sequential programs.

Indexing (document details)
Advisor: Vachharajani, Manish
Commitee: Chang, Bor-Yuh Evan, Moseley, Tipp, Siek, Jeremy G., Somenzi, Fabio
School: University of Colorado at Boulder
Department: Electrical Engineering
School Location: United States -- Colorado
Source: DAI-B 72/11, Dissertation Abstracts International
Subjects: Electrical engineering, Computer science
Keywords: Aggressive optimizations, Dynamic program analysis, Multicore programming, Parallelism, Sequential codes, Zero-suppressed BDDs
Publication Number: 3468482
ISBN: 978-1-124-82471-0
Copyright © 2020 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy