Selecting Long Atomic Traces for High Coverage

Abstract

This paper performs a comprehensive investigation of dynamic selection for long atomic traces. It introduces a classification of trace selection methods and discusses existing and novel dynamic selection approaches - including loop unrolling, procedure in-lining and incremental merging of traces based on dynamic bias. The paper empirically analyzes a number of selection schemes in an idealized framework. Observations based on the SPEC-CPU2000 benchmarks show that: (a) selection based on dynamic bias is necessary to achieve the best performance across all benchmarks, (b) the best selection scheme is benchmark and maximum trace-length specific, (c) simple selection, based on program structure information only, is sufficient to achieve the best performance for several benchmarks. Consequently, two alternatives for the trace selection mechanism are established: (a) a "best performance" approach relying on complex dynamic criteria

(b) a "value" approach that provides the best performance (and potentially the best power consumption) based on simpler static criteria. Another emerging alternative advocates adaptive based mechanisms to adjust selection criteria.