• black-box
• performance
• prediction
• profiling
• software
• computational complexity
• energy model
• characterization
• hardware
• energy
• completion time
• Benchmarking

Lilja (2005) states that “In the field of computer science and engineering there is surprisingly little agreement on how to measure something as fun- damental as the performance of a computer system.”. The field lacks of the most fundamental element for sharing measures and results: an appropriate metric to express performance.

Since the introduction of laptops and mobile devices, there has been a strong research focus towards the energy efficiency of hardware. Many papers, both from academia and industrial research labs, focus on methods and ideas to lower power consumption in order to lengthen the battery life of portable device components. Much less effort has been spent on defining the responsibility of software in the overall computational system energy consumption. Some attempts have been made to describe the energy behaviour of software, but none of them abstract from the physical machine where the measurements were taken. In our opinion this is a strong drawback because results can not be generalized.

In this work we attempt to bridge the gap between characterization and prediction, of both hardware and software, of performance and energy, in a single unified model. We propose a model designed to be as simple as possible, generic enough to be abstract from the specific resource being described or predicted (applying to both time, memory and energy), but also concrete and practical, allowing useful and precise performance and energy predictions. The model applies to the broadest set of resource possible. We focus mainly on time and memory (hence bridging hardware benchmarking and classical algorithms time complexity), and energy consumption. To ensure a wide applicability of the model in real world scenario, the model is completely black-box, it does not require any information about the source code of the program, and only relies on external metrics, like completion time, energy consumption, or performance counters.

Extending the benchmarking model, we define the notion of experimental computational complexity, as the characterization of how the resource usage changes as the input size grows.
Finally, we define a high-level energy model capable of characterizing the power consumption of computers and clusters, in terms of the usage of resources as defined by our benchmarking model.

We tested our model in four experiments:
Expressiveness: we show the close relationship between energy and clas- sical theoretical complexity, also showing that our experimental com- putational complexity is expressive enough to capture interesting be- haviour of programs simply analysing their resource usage.
Performance prediction we use the large database of performance mea- sures available on the CPU SPEC website to train our model and predict the performance of the CPU SPEC suite on randomly selected computers.
Energy profiling: we tested our model to characterize and predict the power usage of a cluster running OpenFOAM, changing the number of active nodes and cores.
Scheduling: on heterogeneous systems applying our performance pre- diction model to features of programs extracted at runtime, we predict the device where is most convenient to execute the programs, in an heterogeneous system.