Quantifying the Common Computational Problems in Contemporary Applications (Extended version)

The workloads of computing systems have traditionally been characterized in terms of the behavior of algorithms and their embodiments in applications, executing on a variety of hardware architectures. Algorithms are however only a means to the end goal of the solution of computational problems. A quantitative characterization of the constituent computational problems in contemporary applications is thus of great interest, given the recent advent of programming languages and system software platforms which enable performance and energy-efficiency trade-offs through the exploitation of algorithmic alternatives for a given compute problem. This article quantifies the potential for the exploitation of algorithmic choice as a means by which applications may gain performance improvements in return for architectural or programmer investment. This argument is made through the quantitative characterization of the dominant computational problems contained in a suite of 21 applications, representative of a diverse collection of general-purpose real-world software. It is demonstrated that almost 40% of the aggregate execution time of the applications studied is spent in a set of 16 problems that can be defined in terms of notation for describing computational problems independent of algorithms for their solution. The properties of compute problems which would make them amenable to representation in the proposed notation are discussed, and quantified through hardware performance counter measurements. Based on the insights obtained from the work presented, a tentative hardware microarchitecture for exploiting algorithmic choice is introduced.