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

Abstract

The workloads of computing systems have tradition-
ally 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 quanti-
tative 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 prob-
lems 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.

Cite as:

R. Jongerius, P. Stanley-Marbell, and H. Corporaal. "Quantifying the Common Computational Problems in Contemporary Applications (Extended Version)". IBM Research Report RZ 3885, 2014.

BibTeX:

@misc{6114199_extended,
url={https://dominoweb.draco.res.ibm.com/reports/rz3885.pdf}, 
title={Quantifying the common computational problems in contemporary applications},
author={Jongerius, Rik and Stanley-Marbell, Phillip and Corporaal, Henk},  
journal={IBM Research Reports}, 
year={2014}, 
moth={nov}
}