On the limitations of analysing worst-case dynamic energy of processing.

This paper examines dynamic energy consumption caused by data during softwareexecution on deeply embedded microprocessors, which can be significant on somedevices. In worst-case energy consumption analysis, energy models are used tofind the most costly execution path. Taking each instruction's worst caseenergy produces a safe but overly pessimistic upper bound. Algorithms for safeand tight bounds would be desirable. We show that finding exact worst-caseenergy is NP-hard, and that tight bounds cannot be approximated with guaranteedsafety. We conclude that any energy model targeting tightness must eithersacrifice safety or accept overapproximation proportional to data-dependentenergy.