arXiv CSopen access

Energy Calculus: A Compositional Algebra of Energy in Computational Systems

The ML.ENERGY Initiative

Energy Calculus A Compositional Algebra of Energy in Computational Systems Mosharaf Chowdhury∗ , Jae-Won Chung∗ , Jeff J. Ma, Nishil Talati, Ruofan Wu

arXiv:2607.11087v1 [cs.DC] 13 Jul 2026

Energy is a binding constraint for AI scaling, yet it lacks the formal treatment that computation, communication, and learning have long enjoyed. Recent systems demonstrate large energy savings, but each targets a specific granularity and structure; one cannot combine frequency scaling from one system with critical-path analysis from another and reason about their joint effect on total energy. Energy remains a monolithic scalar that is measured after the fact and optimized with point solutions that do not generalize. We propose energy calculus, a compositional algebra that treats energy as a first-class primitive. It builds on energy elements, units of computation whose energy we can reliably measure, each carrying an energy signature that comprises its time, its static and dynamic energy, the hardware operating point and execution context under which we measured it, and the associated measurement uncertainty. Three operators (sequential, same-device parallel, and cross-device parallel) compose signatures along the same structure as the computation itself, covering arbitrary DAG-structured executions. The algebra rests on seven axioms that capture how hardware consumes energy, and it exhibits two properties distinctive to energy among computing resources: sequential composition commutes only when elements are mutually contextinsensitive, and sequential composition does not distribute over parallel composition. We also present a Reduction Theorem that recovers simple context-independent algebra whenever interactions fall below measurement uncertainty, so practitioners pay for context dependence only where the physics demands it. Uncertainty propagates through every composition, so each prediction carries an error bound. Finally, we show that the same operators extend from energy totals to time–energy Pareto frontiers, so reasoning about tradeoffs composes with the same algebra.

Authors listed alphabetically.

∗ Equal contribution.

Correspondence: [email protected]

Contents 1 Introduction

4

2 Background 2.1 Energy in Computational Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Computation as Structured Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Measurement Uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Composing the Energy of a Transformer Attention Layer . . . . . . . . . . . . . . . . . . . . . . .

5 5 6 6 6

3 Energy Calculus: Foundations 3.1 Energy Elements and Context Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Energy Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Composing Energy Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Interaction Mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 8 8 10 12

4 Reduction to Context-Independence 4.1 Context-Insensitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 The Reduction Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 The Context-Independent Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 The Interaction Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Axioms and Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13 13 15 16 16 17

5 Properties of Energy Calculus 5.1 Algebraic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Uncertainty and Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18 18 21

6 Application: Operating Frontiers Under Context-Independence 6.1 Operating Set and Frontier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Frontier Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22 23 23

7 Discussion 7.1 What the Framework Covers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 What the Framework Does Not Cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Open Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25 25 25 26

8 Related Work 8.1 Energy Measurement and Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 ML Energy Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Performance and Power Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4 Compositional Reasoning in Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28 28 28 28 28

9 Conclusion

29

A Interaction Mechanism Details A.1 Thermal Coupling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Cache and Memory State . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Power Delivery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.4 Resource Contention . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30 30 30 30 30

B Insensitivity Expansion

30

2

C Reduction Theorem C.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.2 Sequential Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.3 Parallel Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.4 Tightness and Breakdown . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31 31 31 32 32

D Bias Accumulation

32

E Energy Calculus Algebraic Property Proofs E.1 Commutativity (Property 5.1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E.2 Associativity (Property 5.2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E.3 Closure (Property 5.3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E.4 Distributivity (Property 5.4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E.5 Monotonicity (Property 5.5) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33 33 34 34 35 36

F Variance Propagation Details F.1 Sequential Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . F.2 Parallel Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . F.3 Closed Forms and Limits for the Makespan Variance . . . . . . . . . . . . . . . . . . . . . . . . . F.4 Distributional Treatment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36 36 36 37 37

G Refinement–Coarsening Consistency

37

H Frontier Composition Under Context-Independence H.1 Sequential Frontier Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . H.2 Parallel Frontier Coupling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38 38 38

3

1 Introduction Energy is a binding constraint for AI scaling [5, 11, 16]. While the demand for energy to power millions of accelerators keeps growing, energy procurement at scale remains slow: it takes around three years for natural gas sources and five to ten years for nuclear [18]. As such, energy has become a computing resource that deserves the same level of attention and analysis as time, memory, and network bandwidth. Recent work has advanced our understanding of energy as a quantifiable computing resource and derived large energy savings through optimization. For instance, Zeus [21] leverages the fact that GPUs are not powerproportional and jointly tunes the batch size of training and the GPU’s power limit to cut energy consumption by 24%–75%. Perseus [6] identifies “energy bloat” in large model training, where viewing training as a Directed Acyclic Graph (DAG) and analyzing the critical path allows up to 30% reduction in training energy consumption with no slowdown. Kareus [20] decomposes energy into static and dynamic components and jointly optimizes GPU streaming multiprocessor (SM) allocation, computation/communication scheduling, and frequency, reducing training energy by up to 28% at the same training time. However, such systems target specific computation granularities and structures, and do not automatically compose or generalize. One cannot trivially take frequency scaling from Zeus, critical-path analysis from Perseus, and launch timing from Kareus and reason about their combined effect on total energy. Further, their optimization algorithms are tied to the specific structures they were designed for (e.g., recurring training jobs [21], the DAG of training forward and backward computations [6], repeating partitions of computation and communication kernels [20]). This calls for a general formalism for reasoning about energy in computational systems. Mature formalisms for reasoning about computation (complexity theory), communication (information theory), and learning and generalization (statistical learning theory) exist, but energy has yet to be treated as a composable quantity grounded in how hardware consumes it. It is treated as a monolithic scalar, measured after the fact, and optimized by point solutions that do not generalize across granularity, computation structure, or hardware. The formalism must decompose energy into algebraically composable components, propagate measurement-induced uncertainty1 through composition, and apply at arbitrary granularity on any hardware. We propose energy calculus to fill this gap. Energy calculus treats energy as a first-class primitive, a structured quantity decomposed into static and dynamic components that compose along the same structure as the computation itself. The basic unit of analysis is an energy element, defined as any unit of computation for which energy can be reliably measured. Each element carries an energy signature: its measured time and energy, the static– dynamic breakdown, the hardware operating point and execution context under which it was measured, and the associated measurement uncertainty. By composing per-element energy signatures with explicit algebraic operators, energy calculus produces end-to-end energy predictions with bounded uncertainty, reusing previously characterized signatures rather than profiling each computation in full. Energy calculus is built on the following principles. First, the framework captures the physical nature of how computing consumes energy. The static–dynamic decomposition reflects how hardware actually consumes energy, and we treat direct measurement as ground truth. Second, measurement reliability sets the finest admissible granularity; above that floor [20], an energy element can be a kernel, layer, block, model, pipeline stage, or an entire job, and we operate at whichever granularity the analysis demands.2 Third, we compose elements hierarchically so that elements combine into larger elements using the same operators. A composition is itself an element with a well-defined energy signature. Fourth, we make measurement uncertainty intrinsic to the calculus. Every signature carries the variances of its measured quantities—execution time and total energy—and these variances propagate through every composition, so each prediction comes with an error bound. Fifth, we admit context dependence: signatures are functions of the physical state in which elements run (thermal, cache, power delivery, etc.), and composition propagates that state from one element to the next. Sections 3 and 4 formalize these principles as seven axioms (five physical, two methodological). Furthermore, a Reduction Theorem recovers simple context-independent algebra in the common case where interactions fall below measurement uncertainty, so practitioners pay the cost of context dependence only where it is physically required. Energy calculus makes energy something practitioners can reason about. A system designer can ask whether a 1 Software-reported energy measurements can deviate from hardware ground truth by ±5% [1].

2 Note that finer decomposition does not reduce profiling time and can increase the number of elements to characterize; the saving comes instead from amortization. An element characterized once on a target accelerator is composed into many computations without re-profiling, so a signature library amortizes its characterization cost across everything that reuses it.

4

frequency-scaling decision at the kernel level composes with a critical-path optimization at the pipeline level, and the calculus answers algebraically rather than by re-profiling the combination. Once signatures are characterized on a target accelerator, predicting energy for a new computation composes existing signatures algebraically with propagated uncertainty, instead of requiring a full optimization sweep. The same algebra extends from energy totals to time–energy Pareto frontiers, so reasoning about tradeoffs at any granularity uses the same operators as reasoning about totals. Energy becomes a resource that can be budgeted across stages of a pipeline, allocated to subsystems, and traded against time at a chosen granularity. Scope. This work establishes foundations rather than presenting an evaluation. We define the algebra, ground it physically, state and prove its core properties, and identify the mechanisms that drive context dependence. Empirical validation at scale, optimization layers built on the algebra, and energy-aware compilation are the subject of subsequent work; Section 7.3 catalogs these and other open directions. Contributions. We make the following contributions: • We introduce energy calculus, a compositional framework that treats energy as a first-class primitive with static and dynamic components, parameterized by hardware operating point and execution context, and applicable at any granularity from kernel to job. We ground it in seven axioms (five physical, two methodological). • We define three composition operators (sequential, same-device parallel, and cross-device parallel), show that they compose arbitrary DAG-structured schedules, and establish their algebraic properties. Two of these properties are distinctive to energy: conditional commutativity of sequential composition under context propagation, and non-distributivity of sequential over parallel composition. • We prove a Reduction Theorem that recovers context-independent algebra whenever interacting elements are mutually context-insensitive within measurement uncertainty. • We identify the physical mechanisms behind context dependence (thermal, cache and memory, contention, power delivery) and present an interaction-graph workflow for characterizing non-negligible element pairs and prefixes. The inventory is open-ended and extensible without algebraic modification. • We extend the algebra from energy totals to time–energy Pareto frontiers, showing that the three operators induce composition rules on operating frontiers. Parallel composition further admits slack-to-energy conversion: an element that finishes earlier than the others can be slowed down to reduce energy consumption, and the calculus provides an analytical framework for reasoning about this.

2 Background Our primary setting is AI datacenters, where GPUs dominate the energy of training and inference workloads. Energy calculus only assumes that device power divides into static and dynamic components, and applies to any accelerator with that structure.

2.1 Energy in Computational Systems A GPU’s power consumption has two components. Dynamic power tracks computation and memory activity: 𝑃dynamic ∝ 𝑉 2 𝑓,3 dropping to zero when no work occurs. Static power flows continuously whenever the device is powered. It includes leakage current, memory refresh, clock distribution, and other baseline costs. For instance, an NVIDIA A100 at idle draws 40–60 W; at full load, it can reach 300–400 W depending on SKU and power cap [14]. The static–dynamic split determines how energy composes. Two computations running in parallel on one device share static power, drawn once over the makespan. When the two do not slow each other down by competing for shared resources, their dynamic energies add. Two computations running sequentially on one device each draw static power for their own duration. GPUs are not power-proportional: a GPU at 10% utilization does not consume 10% of peak power, because static power creates a high floor. How sub-computations share or serialize on hardware therefore determines whether static power amortizes or goes to waste. 3 𝑉 is the supply voltage and 𝑓 is the clock frequency.

5

Hardware further shapes these components through runtime controls. Dynamic voltage and frequency scaling (DVFS) varies 𝑓 and 𝑉 at runtime, while a power cap 𝑃cap enforces an upper bound on instantaneous power draw. Both static power and dynamic energy depend on (𝑓, 𝑉, 𝑃cap ): the same computation at different settings consumes different energy in different amounts of time. We collect these settings into an operating point 𝜔 = (𝑓, 𝑉, 𝑃cap , …) that parameterizes the energy of every element. These settings are device-wide; an element additionally carries per-element settings such as its SM allocation. Section 3.1 splits 𝜔 into device-wide and perelement components accordingly.

2.2 Computation as Structured Composition A computation arranges units of any granularity (kernel invocations, fused operator groups, layers, model blocks, pipeline stages, entire jobs) under execution and data dependencies. That arrangement determines how the units’ energies combine into total energy. The parallelism strategies used in large model training illustrate the typical composition patterns: • Data parallelism replicates the model across devices. Each replica processes a shard of the minibatch (parallel across devices), followed by gradient synchronization (communication overlapping with or following computation). • Tensor parallelism partitions individual operators across devices within a layer. A single layer’s forward pass interleaves local computation with collective communication, creating fine-grained same-device overlap, with cross-device synchronization at the communication boundary. • Pipeline parallelism partitions layers across devices into stages. A minibatch is split further into microbatches that flow through the pipeline, creating sequential processing within each stage, parallel execution of different microbatches across stages, and idle “bubble” time at the boundaries due to pipeline fill and drain, and workload imbalance. In practice these strategies compose: a training job may use tensor parallelism within a node, pipeline parallelism across nodes, and data parallelism across node groups. The resulting execution is a DAG of computational units connected by sequential, same-device parallel, and cross-device parallel relationships. Newer regimes such as expert parallelism (for Mixture-of-Experts models) and context/sequence parallelism (for long-context training/inference) decompose into the same sequential and parallel relationships. The same compositional structure appears beyond training: inference serving, data-processing frameworks, and scientific simulations all arrange sub-computations in time and across hardware through the same sequential and parallel relationships.

2.3 Measurement Uncertainty Energy measurement is inherently noisy. Internal and external instruments measure different quantities at different timescales, and software-reported energy can deviate from hardware ground truth by ±5% [1]. Device temperature drifts during measurement, creating run-to-run variance especially for short-duration kernels. Samplinginterval limits inflate uncertainty for fine-grained measurements. Different hardware platforms expose different baseline behaviors, complicating cross-hardware comparison further. Three design requirements follow. Every measured element must carry a variance term, uncertainty must propagate through every composition, and divergence between a composed prediction and a direct measurement (beyond propagated uncertainty) must flag a composition or characterization failure (Section 5.2).

2.4 Composing the Energy of a Transformer Attention Layer We illustrate the core mechanism on a concrete workload before developing the formalism. The workload is an attention layer from Llama 3.2 3B training on two A100 GPUs with tensor parallelism and computation– communication overlap. The attention layer consists of a sequential prefix (RMS Norm → Linear 1) followed by a parallel region where the compute path (RoPE → Attention → Linear 2) overlaps with AllReduce communication (Figure 1). The compute kernels use 105 streaming multiprocessors (SMs) while AllReduce uses 3 SMs.

6

Energy signatures. Each element has a measurCompute-bound Memory-bound AllReduce able energy signature: a static power 𝑠 (W), execution Total Energy: 3.32 J time 𝑇 (s), and dynamic energy 𝑑 (J), so that total energy is 𝐸 = 𝑠⋅𝑇+𝑑. For this layer, the sequential prefix Ro takes 𝑇seq = 1.55 ms with dynamic energy 𝑑seq ; the RMS Attention Linear 2 Linear 1 PE subsequent compute path takes 𝑇compute = 2.77 ms Norm with dynamic energy 𝑑compute ; and the AllReduce in AllReduce parallel takes 𝑇ar = 2.77 ms with dynamic energy 𝑑ar . Time (ms) 1.55 0.00 4.32 Each A100 draws 60 W of static power at this operating point, so 𝑠 = 120 W summed across both GPUs; dyFigure 1: AllReduce overlaps with compute kernels durnamic energies similarly aggregate across the pair. Being attention layer execution on 2×A100 GPUs. cause the two GPUs execute identical per-GPU timelines in lockstep, the cross-device parallelism between them collapses into this combined static power, leaving the within-GPU compute–AllReduce overlap as the only operator structure visible in the formula below. Composition. Given these signatures, the layer’s total energy follows from how its parts are arranged in time. In the parallel region, compute and AllReduce overlap on the same device, so static power is drawn once over the region’s makespan while dynamic energies add: 𝐸parallel = 𝑠 ⋅ max(𝑇compute , 𝑇ar ) + 𝑑compute + 𝑑ar

(1)

The full layer composes the prefix and the parallel region sequentially, where each part draws static power for its own duration: 𝐸layer = 𝑠 ⋅ 𝑇seq + 𝑑seq + 𝑠 ⋅ max(𝑇compute , 𝑇ar ) + 𝑑compute + 𝑑ar (2) The total time is 𝑇layer = 1.55 + max(2.77, 2.77) = 4.32 ms. Static energy accounting. Compositional reasoning matters for the static term even when the execution is fixed. Because the compute path and AllReduce run concurrently, the layer occupies the device for 𝑇layer = 4.32 ms and the correct static energy is 𝑠 ⋅ 𝑇layer = 120 × 4.32 ms = 518 mJ. Treating the two as if they were serialized would sum their durations to 1.55 + 2.77 + 2.77 = 7.09 ms and give 120 × 7.09 ms = 851 mJ, overstating static energy by 333 mJ (64% of the correct value) by double-counting the overlap period. Dynamic energy is unchanged in both cases because the same computations execute either way. Direct measurement of the full layer yields 3.32 J, of which the composed static term accounts for 518 mJ; the rest is the three dynamic terms. This example rests on two simplifying assumptions. Each element consumes the same time and energy whether measured alone or as part of the layer, so a single measurement characterizes it once and for all. The overlapping kernels do not slow each other down by competing for shared resources, so each keeps the duration and energy it has on its own. Later sections show when these assumptions hold and how to handle the cases where they fail.

3 Energy Calculus: Foundations This section develops the foundational layer of energy calculus. We define energy elements and the context variables that carry physical state and co-execution structure (Section 3.1), build energy signatures over them (Section 3.2), and give the composition operators in their general context-dependent form, showing that they compose arbitrary DAG-structured schedules (Section 3.3). Finally, we ground the context variables physically, identifying the interaction mechanisms through which one element’s execution changes the energy another consumes (Section 3.4). Based on the foundations established in this section, Section 4 establishes when context dependence can be dropped, and Section 5 derives properties and rules of the composition algebra.

7

3.1 Energy Elements and Context Variables Definition 3.1 (Energy Element). An energy element 𝑒 is a unit of computation that admits an energy measurement (or estimate) and composes with other elements into larger ones. Each element is associated with workload parameters 𝜃 describing the computation it performs, is realized by an implementation 𝜅 chosen among those computing its operation, and executes at an operating point 𝜔 = (𝜔dev , 𝜔elem ) of the hardware, split into a devicewide part 𝜔dev shared by everything on the device and a per-element part 𝜔elem partitioning device capacity among elements.4 Each element has a trace: a record of the actions it issues, e.g., the cache lines it touches or the memory transactions it requests. A GPU kernel, a layer, a Transformer block, a training step, or an entire job are all energy elements; the calculus prescribes no fixed granularity. The contents of 𝜃 likewise depend on granularity: tensor dimensions for a kernel, batch size and sequence length for a layer, the full configuration for a training run. The implementation 𝜅 selects among the realizations of the element’s mathematical operation. For instance, the attention operation is one element, and cuDNN, FlexAttention, and FlashAttention are values of 𝜅, each with its own trace, time, and dynamic energy. Beyond what an element mathematically computes (𝜃), how it is realized (𝜅), and how the hardware is set (𝜔), the energy consumption of an energy element depends on the physical environment of its execution, which we capture with three Context Variables. Definition 3.2 (Context Variables). The entry context 𝜙 of an element is the vector of physical state variables it inherits from prior execution, e.g., device temperature, cache occupancy, memory fragmentation, power delivery state. The runtime context 𝜌 of an element is the set of elements, including itself, that run concurrently and potentially interfere with each other. Because each element executes on a specific device, 𝜌 determines the hardware resources the elements share and hence the mechanisms through which they can interfere. The exit context of an element is the physical state it leaves behind; whatever runs next inherits that as its entry context. All context variables must be measurable or controllable, as state that can be neither observed nor set cannot be used to explain energy. Entry and exit contexts are state handed across time, whereas the runtime context is company kept across space. Elements interact when one’s execution impacts another’s energy, and the context variables are the complete interface for capturing that influence; a preceding element influences its successors through entry and exit contexts, and concurrently running elements influence each other through the runtime context they share. Physical mechanisms (e.g., cache, memory, heat) define how interactions via each mechanism translate to actual context variable values. What ties together the context variables is the element’s trace. The trace itself is fixed given the element, its workload parameters, and its implementation: context changes not what an element does but how long it takes and how much energy it consumes. The trace records issued actions, not their hardware realization. Whether a touched cache line hits or misses depends on context, and that difference lands in time and dynamic energy, not in the trace. Thermal interaction, for example, takes the current the element drew—which, at the device’s operating voltage, delivers energy that all ends up as heat released over its execution time—and computes the device temperature left behind. We survey physical mechanisms and their context update rules in Section 3.4. Energy elements compose in their execution in many ways. In the simplest case where two elements execute back to back on the same device and each runs in isolation (its runtime context contains only itself), the first element’s exit context is exactly the entry context the second inherits. Elements can also overlap in time and share a runtime context 𝜌: on one device they take the same entry context and contend for its shared resources (e.g., memory bandwidth), while across devices they each take the entry context of their own device and contend for shared resources (e.g., a common interconnect, node-level power budget). The traces of all elements in the runtime context contribute influence to the exit context of the whole overlapped execution.

3.2 Energy Signatures The energy signature is the atom of the calculus: every energy element has an energy signature, and composition consumes its operands’ energy signatures and produces the composed element’s energy signature. Throughout 4 Which components are device-wide is hardware-dependent: on current GPUs, frequency, voltage, and the power cap are device-wide, 𝜔dev = (𝑓, 𝑉, 𝑃cap ), while software knobs that partition the GPU’s resources (e.g., SM allocation) are per-element.

8

Sections 3 and 4 we will introduce seven axioms that the calculus rests on, starting from the physical distinction between power that flows regardless of computation and energy that scales with the work performed. Axiom 3.1 (P1: Energy Decomposition). Energy over an execution period is the time integral of power; therefore, energy over disjoint periods is additive. For any energy element 𝑒 with workload parameters 𝜃 and implementation 𝜅 at operating point 𝜔 (device-wide part 𝜔dev ), in entry context 𝜙 and runtime context 𝜌, the energy consumed decomposes as: 𝐸𝑒 (𝜃, 𝜅, 𝜔, 𝜙, 𝜌) = 𝑠𝑒 (𝜔dev , 𝜙, 𝜌) ⋅ 𝑇𝑒 (𝜃, 𝜅, 𝜔, 𝜙, 𝜌) + 𝑑𝑒 (𝜃, 𝜅, 𝜔, 𝜙, 𝜌) (3) where 𝑠𝑒 ≥ 0 is the static power of the device 𝑒 executes on, 𝑇𝑒 ≥ 0 is execution time, and 𝑑𝑒 ≥ 0 is dynamic energy.

In the special case of isolation (𝜌 = {𝑒}), we suppress 𝜌 and write 𝐸𝑒 (𝜃, 𝜅, 𝜔, 𝜙) = 𝑠𝑒 (𝜔dev , 𝜙) 𝑇𝑒 (𝜃, 𝜅, 𝜔, 𝜙) + 𝑑𝑒 (𝜃, 𝜅, 𝜔, 𝜙). Values with a non-singleton 𝜌 are whole-run values, absorbing the arrivals and departures of other peer elements running together. In this case, both who the peers are and when they overlap matter to these values. The values therefore depend on the co-scheduled configuration: the runtime context 𝜌 together with the overlap windows, which the composition supplies since it sets every element’s start and end times. Two schedules that overlap the same elements differently have different characterized values. Static power5 does not depend on 𝜃 or 𝜅 as it is the baseline draw independent of the workload running on the device, and it depends on the operating point only through its device-wide part 𝜔dev , since the per-element part 𝜔elem is tied to each element’s execution decision which is orthogonal to the device’s static power draw. Static power is also a function of the runtime context 𝜌. For instance, two elements that execute together may increase instant power draw or thermal load that newly or more severely trigger frequency throttling, which affects the device’s static power. Dynamic energy is the derived quantity (𝑑𝑒 ∶= 𝐸𝑒 − 𝑠𝑒 𝑇𝑒 ), and the axiom asserts 𝑑𝑒 ≥ 0. Definition 3.3 (Energy Signature). The energy signature of an energy element 𝑒 is ( ) 𝑆𝑒 = 𝑒, 𝜃, 𝜅, 𝜔, Φ, 𝒫, 𝑠𝑒 (⋅), 𝑇𝑒 (⋅), 𝑑𝑒 (⋅), 𝜎𝑇2 , 𝜎𝐸2 , 𝑀 𝑒

𝑒

(4)

where Φ is the set of entry contexts and 𝒫 the set of co-scheduled configurations (runtime contexts with their schedule windows) over which the element was characterized.6 Additionally, 𝑠𝑒 , 𝑇𝑒 , and 𝑑𝑒 are the components of Axiom P1 characterized over Φ and 𝒫; 𝜎𝑇2 and 𝜎𝐸2 are the variances of the element’s execution time and total energy; and 𝑀 is 𝑒 𝑒 metadata (measurement method, hardware platform identity, conditions under which the signature was obtained). Composing energy elements (Section 3.3) is the core operation of energy calculus, and the energy signature is defined to contain every piece of information of the element needed to carry out the composition. Hardware identity enters through the metadata 𝑀: the achievable ranges of 𝜔 and 𝜙, and the signature functions themselves, are hardware-specific, so the same abstract computation has different signatures on different hardware, and predicting on other hardware means composing that hardware’s own characterized signatures with the same operators. Axiom 3.2 (M1: Intrinsic Uncertainty). Error in every measured signature component is summarized by its mean and variance. For an element measured directly, static power is a calibration constant, exact at each characterized (𝜔dev , 𝜙, 𝜌), and the errors of its execution time and dynamic energy are uncorrelated. Uncertainty propagates through every composition. Uncertainty is part of the signature because a reported energy value without an uncertainty estimate is incomplete. The signature carries the variances of the two measured quantities, execution time and total energy, and the variance of the derived dynamic energy follows from them. For an element measured directly, Axiom M1 gives that static power is exact and the errors of time and dynamic energy are uncorrelated, so Axiom P1 yields: 𝜎𝐸2 = 𝑠𝑒2 𝜎𝑇2 + 𝜎𝑑2 . 𝑒

𝑒

(5)

𝑒

A composed element carries its energy variance directly, propagated from its parts. The variances carry the random error: instrument noise and run-to-run jitter. Heavier-tailed or multimodal error structure falls outside the model. The three components are not measured symmetrically: execution time carries run-to-run variability, static power is a calibration constant and contributes no variance, and dynamic energy, derived per run as 𝐸𝑒 − 𝑠𝑒 𝑇𝑒 (Axiom P1), inherits the energy instrument’s noise.7 If a run that happens to take ∆𝑇 longer con5 We define static power to be not the deep idle/sleep power of the device, but rather the power draw of a ready device at the same operating point and context as the element’s execution. For instance, it would correspond to the NVIDIA GPU Performance state P0. 6 One can think of the individual entries in Φ and 𝒫 as different environments where 𝑒 was characterized. 7 Time can often be measured with higher precision than energy in modern hardware, so 𝜎 2 would be dominated by energy variability. 𝐸 𝑒

9

tributes 𝑠𝑒 ∆𝑇 more to its energy fluctuation, the subtraction 𝑑𝑒 = 𝐸𝑒 − 𝑠𝑒 𝑇𝑒 cancels that component. This leaves dynamic-energy error largely orthogonal to time, supporting Axiom M1’s uncorrelated assumption.

3.3 Composing Energy Elements We define three composition operators that combine energy elements: sequential (⊗), same-device parallel (⊕), and cross-device parallel (⊕multi ). The operators accept energy signatures as input and produce the energy signature of the composite element. For each operator, we derive the composite’s energy consumption 𝐸𝑒1 op 𝑒2 , abbreviated 𝐸1 op 𝐸2 ; Property 5.3 later proves the operators closed, deriving the composite’s own signature components. For notational convenience, 𝜔 and each element’s 𝜃 and 𝜅 are suppressed. Idle elements and energy accounting. We write 𝒟𝑒 for the set of devices hosting element 𝑒: a singleton for an element on one device, and larger for composites spanning several. When multiple elements compose, all participating devices across the composing elements are held for the full makespan of the composition. Any period in which a participating device runs nothing is viewed as running a special idle element: an energy element with an empty trace, whose device stays ready at its element’s device-wide operating point, drawing that device’s static power at the idle period’s own entry context and zero dynamic energy. Thus, each participating device consumes static power for the full makespan of the composition (either via an element or an idle element), and the dynamic energy consumption of all elements adds on top of that static energy consumption. We note that idle elements appear in runtime contexts like any other element, since an idle device still draws power and dissipates heat on shared rails and cooling paths, coupling it and concurrent elements in both directions. 3.3.1 Sequential Composition (⊗) For two elements executing one after the other on the same device, the composite’s energy is the sum of the two executions’ energies (Axiom P1), each evaluated at its own entry and runtime contexts: 𝐸1 ⊗ 𝐸2 = 𝐸𝑒1 ⊗𝑒2 (𝜙0 ) = 𝑠1 (𝜙0 , 𝜌1 ) 𝑇1 (𝜙0 , 𝜌1 ) + 𝑑1 (𝜙0 , 𝜌1 ) + 𝑠2 (𝜙1 , 𝜌2 ) 𝑇2 (𝜙1 , 𝜌2 ) + 𝑑2 (𝜙1 , 𝜌2 ),

(6)

where 𝜙0 is the entry context of the first element and the composite, 𝜙1 is 𝑒1 ’s exit context, inherited by 𝑒2 as its entry context, and 𝜌𝑖 is the runtime context the surrounding composition places 𝑒𝑖 in—the two elements run back to back, so neither appears in the other’s. For 𝑛 operands, the composite’s energy is still the sum of the 𝑛 elements’ total energy consumption, each evaluated at its own entry context, which is the exit context of its predecessor, and its own runtime context. 3.3.2 Same-Device Parallel Composition (⊕) Working out the energy consumption of elements that start together and overlap inside one device starts from a physical fact: however many elements run, the device draws its static power once. Axiom 3.3 (P2: Per-Device Static Power). A device has a single static power, reflecting components that draw power regardless of the workload (e.g., leakage, clock distribution, memory refresh), so however many elements run concurrently in the device, the device draws static power once. Following Axiom P2, the composite’s total energy consumption is: ( ) 𝐸1 ⊕ 𝐸2 = 𝐸𝑒1 ⊕𝑒2 (𝜙0 ) = 𝑠(𝜙0 , 𝜌) ⋅ max 𝑇1 (𝜙0 , 𝜌), 𝑇2 (𝜙0 , 𝜌) + 𝑑1 (𝜙0 , 𝜌) + 𝑑2 (𝜙0 , 𝜌)

(7)

where 𝜙0 is the shared entry context of both elements, 𝜌 is the runtime context the surrounding composition places the pair in ({𝑒1 , 𝑒2 } when the pair runs alone), and 𝑠 is the device’s static power (𝑠 = 𝑠1 = 𝑠2 as they run on the same device). Following the same energy accounting principle, the device draws its static power over the whole makespan of the composition (max(𝑇1 , 𝑇2 )), and that static power is drawn once per device (Axiom P2). Compared with each element executing in isolation, concurrently running elements can interact with each other (Section 3.4), slowing each other down and perturbing each other’s dynamic energy—this is what the runtime context 𝜌 captures. For 𝑛 elements running on the same device together, the makespan is max 𝑖 𝑇𝑖 over which the device’s static power is consumed, and dynamic energies add. 10

Serialization (same device) Data/sync dependency (cross device)

GPU 0 GPU 1

F1

F2 F1

B1

B1 F2

B2 B2

AR

GPU 0

EF1 EF2

Eι

AR

GPU 1

Eι EF1

EB1

(a) The execution plan as a DAG.

EB1

Eι EB2 E

EF2 EB2 EAR

AR

Eι

(b) The plan reduced to per-GPU sequences with idle elements.

Figure 2: Composing energy of a DAG-structured schedule with the three operators. (a) A two-stage 1F1B pipeline-parallel execution of two microbatches, running as one replica of a data-parallel job; 𝐴𝑅 is the gradient AllReduce with the peer replica (not shown). (b) Idle elements cover every gap and pad the later-starting 𝐴𝑅, which ⊕ merges with 𝐵2 . Each blue box is the element ⊗ composes within its GPU, and the purple box around all GPUs is the final ⊕multi element. The same-device parallel operator ⊕ is for all elements that start executing at the same time. Cases where elements start at different times are captured by sequential composition with idle elements. That is, such a schedule’s energy consumption can be computed by explicitly introducing idle elements in front of the later-starting elements, sequentially composing them with ⊗, and then composing the resulting elements with ⊕. 3.3.3 Cross-Device Parallel Composition (⊕multi ) For two elements executing concurrently on different devices for the same duration, each device draws its own static power: 𝐸1 ⊕multi 𝐸2 = 𝐸𝑒1 ⊕multi 𝑒2 (𝜙0 ) = 𝑠1 (𝜙0 , 𝜌) 𝑇1 (𝜙0 , 𝜌) + 𝑑1 (𝜙0 , 𝜌) + 𝑠2 (𝜙0 , 𝜌) 𝑇2 (𝜙0 , 𝜌) + 𝑑2 (𝜙0 , 𝜌),

(8)

where 𝜙0 is the composite entry context each device starts from, 𝜌 is the runtime context the surrounding composition places the pair in ({𝑒1 , 𝑒2 } when the pair runs alone), and 𝑇1 = 𝑇2 by the operator’s equal-duration requirement. Runtime context 𝜌 matters across devices too: concurrent elements running on different devices can still interfere (e.g., PCIe switch, NVLink/NVSwitch/NVL72 domain, a network link, node- or rack-level power budgets) if they share and saturate a resource. For 𝑛 elements of equal duration, each device’s static power is drawn over the common duration, and dynamic energies add. The cross-device parallel operator ⊕multi is for all elements that start executing at the same time and run for the same duration. Cases where the start and end times differ across elements are captured by sequential composition with idle elements, similarly to the same-device parallel case. Specifically, such a schedule’s energy consumption can be computed by explicitly introducing idle elements in front of the later-starting elements and after the earlierending elements, sequentially composing them with ⊗, and then composing the resulting elements with ⊕multi . 3.3.4 Composition Over a DAG of Elements So far, we have introduced each operator over exactly two elements, with one device in the world for ⊗ and ⊕ and two for ⊕multi . The key challenge is to determine how entry contexts, runtime contexts, and schedules are derived for each element under arbitrary compositions. Real execution schedules (e.g., pipeline parallelism, data parallelism, complex overlap patterns) form DAGs of elements, and this section composes any such schedule with the three operators. We take a DAG to be a fully scheduled execution plan, not a bare dependency specification: each element carries its placement 𝒟𝑒 , and the edges are the data and synchronization dependencies plus the serialization edges between elements executing on the same device. The schedule determines the contexts given to every element. Only data and synchronization dependencies cross the device boundary, not hardware state, so an element’s entry context is its own device’s state when it starts. Any such plan can be expressed as a term over the three operators, with Figure 2 providing an example. The general procedure is as follows. First, merge the elements that overlap on one device into a single element via 11

⊕, prepending idle elements to later-starting ones if needed. Second, insert an idle element into every period in which a device runs nothing, including the gaps before a device’s first execution and after its last, so that every device is covered for the full makespan. Finally, compose each device’s elements with ⊗ in execution order; the resulting per-device elements all span the same makespan, the length of the critical path through the plan, so ⊕multi ’s equal-duration requirement is met by construction and composes them across devices. In Figure 2, the gradient AllReduce starts partway through 𝐵2 on each GPU, so the first step pads it with an idle element and ⊕ merges the pair; the full plan becomes: ( ( ) ( )) ( ) 𝐸 = 𝐸𝐹1 ⊗𝐸𝐹2 ⊗𝐸𝜄 ⊗𝐸𝐵1 ⊗𝐸𝜄 ⊗ 𝐸𝐵2 ⊕(𝐸𝜄 ⊗𝐸𝐴𝑅 ) ⊕multi 𝐸𝜄 ⊗𝐸𝐹1 ⊗𝐸𝐵1 ⊗𝐸𝐹2 ⊗ 𝐸𝐵2 ⊕(𝐸𝜄 ⊗𝐸𝐴𝑅 ) ⊗𝐸𝜄 . (9) This process is exact: every instant on every participating device belongs to exactly one execution—an element, a same-device parallel group, or an idle element—and energy over disjoint periods adds. The term is thus the execution schedule in operator form, designating the entry and runtime contexts for every element for the purpose of evaluating the energy signature of composites at each level.

3.4 Interaction Mechanisms Energy elements can interact with each other and influence each other’s energy through physical mechanisms. Axiom 3.4 (P3: Interaction Structure). Interaction effects decompose into a finite set of physical mechanisms, each summarizable by a small number of effective state variables. Axiom P3 is an assumption about the structure of interactions: the channels through which one element’s execution can influence another’s energy are finite and well-defined, which allows us to characterize them and compose them in the calculus, exactly within this model. Thermal coupling, cache and memory state, and power delivery act through the entry context: they are state accumulated from prior execution, and their effective state variables constitute 𝜙. Resource contention acts through the runtime context: it exists only during overlapped execution, is a property of concurrent execution rather than of any entry state, and is characterized at the pair or composite level. The contended resource can be device-local for ⊕ (memory bandwidth, cache capacity) or shared across devices for ⊕multi (PCIe switch, NVLink/NVSwitch/NVL72 domain, TCP/RDMA link, node- or rack-level power budgets). A mechanism acting through the entry context additionally carries a context update rule that advances its effective state variables under the traces present. Temperature responses add approximately under a linear thermal model; cache occupancy follows a displacement model, traces evicting entry-state residency and one another under the capacity constraint; power-delivery state decays to the trace’s ending draw within microseconds. Exit contexts assemble by these rules: a successor’s entry context follows from its predecessor’s entry context and trace. A few effective state variables suffice per mechanism, even when the underlying physical state (e.g., cache contents) is high-dimensional. Characterization is performed via measurement, and measurement needs a starting state that every run can reproduce: the null context 𝜙null , the reference entry context the characterization protocol realizes (Axiom M2), in which no mechanism carries appreciable state from prior execution. Axiom 3.5 (M2: Interaction Measurability). Signatures are characterized by direct measurement of the element under multiple representative entry contexts spanning the operating range, with other variables fixed. Characterization starts from the null context 𝜙null , measures the signature components at each context and the element’s trace once, and requires a protocol that isolates 𝜙 from other sources of variation (thermal stability, consistent initial cache state, controlled concurrency). The runtime context is covered the same way, by co-executing the element with representative runtime contexts. Table 1 identifies the current inventory and how each mechanism is characterized, and is open to extension. To add a mechanism, one must specify its physical cause, its characteristic timescale, a measurement protocol that isolates it from other mechanisms, a set of effective state variables, and rules for taking the element’s trace and contexts and producing the exit context. Adding a new mechanism does not change the structure of the calculus: it adds a new entry context variable or a new shared resource acting through the runtime context, and the composition operators remain unchanged. Appendix A details current protocols. 12

Table 1: Current interaction mechanism inventory, grouped by the context channel through which each mechanism acts. Full characterization protocols appear in Appendix A. Mechanism

Physical cause

Timescale

Characterization

Mechanisms acting through the entry context 𝜙 Thermal coupling

Heating increases leakage and can trigger throttling

Seconds

Measure 𝐸 at multiple device temperatures

Cache/memory state

Cache warming or pollution by preceding elements

Intervening traffic

Measure 𝐸 with cold vs. warm cache

Power delivery

Voltage droops from current-draw transitions

Nanoseconds to microseconds

High-resolution power measurement at boundaries

Instantaneous

Measure 𝐸 in isolation vs. concurrently with the interferer

Mechanisms acting through the runtime context 𝜌 Resource contention

Shared resources (bandwidth, cache, fabrics, power budgets) degraded under concurrency

4 Reduction to Context-Independence The generic framework of Section 3 is complete but can become unwieldy: every signature value is a function of the entry and runtime contexts, and characterizing that dependence mechanism by mechanism becomes less tractable as the number of elements grows. However, in practice, the full generality may not always be necessary. Elements that do not share an interaction mechanism’s hardware channel do not interact through it at all. Furthermore, interaction would be limited between elements that are far apart, where distance is mechanism-specific: elapsed time for thermal state and power-delivery transients, and intervening memory traffic for cache state. In this section, we formalize these observations (Section 4.1), present the Reduction Theorem which unlocks a simplified context-independent algebra (Section 4.2), and present the interaction graph, which records characterized interactions between context-dependent elements and lets everything else compose context-independently (Section 4.4). Finally, we summarize the foundational axioms and notation of contextdependent and context-independent energy calculus (Section 4.5).

4.1 Context-Insensitivity 4.1.1 Sensitivity to Entry Context Certain pairs of elements may interact negligibly. For entry context dependence, Axiom P4 provides an analytical model for interactions between elements and the decay thereof. Axiom 4.1 (P4: Interaction Locality). Entry context effects decay with separation between elements. Separation is mechanism-specific. For energy elements 𝑒1 and 𝑒2 , each mechanism 𝑘 carries its own separation measure 𝓁𝑘 (𝑒1 , 𝑒2 ): a mechanism couples the two only when they share the hardware it acts through (𝓁𝑘 (𝑒1 , 𝑒2 ) = ∞ otherwise), and, given shared hardware, 𝓁𝑘 (𝑒1 , 𝑒2 ) measures their separation in the mechanism’s own metric. Then, for each signature component 𝑥 ∈ {𝑠, 𝑇, 𝑑}: || | (10) || 𝑥2 (𝜙1 ) − 𝑥2 (𝜙¬1 ) ||| → 0 as 𝓁𝑘 (𝑒1 , 𝑒2 ) → ∞ for all 𝑘 where 𝜙1 is the entry context 𝑒2 sees following 𝑒1 ’s execution from 𝜙0 , and 𝜙¬1 the entry context 𝑒2 would see had 𝑒1 not executed, all else unchanged.

The two contexts differ only in the state 𝑒1 left behind, which decays mechanism by mechanism as the separation grows, and the interaction effect of 𝑒1 on each of 𝑒2 ’s signature components—hence on its energy consumption—vanishes in the limit. How 𝓁𝑘 is defined depends on the interaction mechanism 𝑘. For the current inventory (Table 1), thermal state couples elements that share a die and cooling path, with 𝓁𝑘 the elapsed time between them; cache state 13

couples elements that share a cache hierarchy, with 𝓁𝑘 the memory transactions between the two executions; and power-delivery transients couple elements on the same delivery rail, with 𝓁𝑘 the elapsed time since the current transition. The rate of decay as 𝓁𝑘 → ∞ is mechanism-specific as well, e.g., thermal effects would be slow, whereas with sufficient memory transactions, cache state interactions would decay quickly. Now, we define when we can treat an element to be insensitive to different entry contexts it executes under, which relieves the costly characterization of the element under every possible context. Definition 4.1 (History-Insensitivity). An element 𝑒 is history-insensitive with respect to a set of entry contexts (i.e., history) within measurement uncertainty if, for all 𝜙, 𝜙′ in the set, ∆𝑠 𝑇𝑒 (𝜙′ ) + ∆𝑇 𝑠𝑒 (𝜙′ ) + ∆𝑠 ∆𝑇 + ∆𝑑 ≤ 𝑐𝛼 ⋅ 𝜎𝐸𝑒 ,

(11)

where ∆𝑠 = |𝑠𝑒 (𝜙)−𝑠𝑒 (𝜙′ )|, ∆𝑇 = |𝑇𝑒 (𝜙)−𝑇𝑒 (𝜙′ )|, and ∆𝑑 = |𝑑𝑒 (𝜙)−𝑑𝑒 (𝜙′ )|, for the desired confidence level (1−𝛼), with 𝑐𝛼 the two-sided Gaussian multiplier, the (1 − 𝛼∕2) quantile of the standard normal distribution. The left-hand side comes from expanding the absolute total energy difference |𝐸𝑒 (𝜙) − 𝐸𝑒 (𝜙′ )| into static power, time, and dynamic energy components per Axiom P1 and extracting a worst-case bound containing each component’s absolute difference (derivation in Appendix B). Each difference is measurable: time per run, static power as the ready device’s draw at each context, and dynamic energy derived per run as 𝐸𝑒 − 𝑠𝑒 𝑇𝑒 (Axiom P1). When this worst-case bound is satisfied, each component’s contribution is bounded separately, and total energy difference is bounded by 𝑐𝛼 ⋅ 𝜎𝐸𝑒 as well.8 Definition 4.2 (Mutual History-Insensitivity). Two elements are mutually history-insensitive when each is historyinsensitive with respect to the contexts the other can produce. History-insensitivity is a property of an element paired with a set of entry contexts, not an intrinsic property of the element. An element may be history-insensitive with respect to thermal variation within a narrow band and history-sensitive with respect to cache state. It is relative to measurement uncertainty as well: the threshold 𝑐𝛼 ⋅ 𝜎𝐸𝑒 treats shifts smaller than a chosen multiple of the element’s run-to-run variation, which includes mainly measurement instrument uncertainty (Axiom M1), as negligible. As instruments improve, the instrument uncertainty component of 𝜎𝐸𝑒 shrinks. Thus, with higher fidelity measurement instruments, the insensitivity check is able to detect interactions for characterization that coarser measurement could not separate from noise. 4.1.2 Sensitivity to Runtime Context Locality and history-insensitivity covers the entry context: it bounds how an element responds to the state its predecessors leave behind. Concurrent composition needs a second condition, for the runtime context. For runtime context dependence, Axiom P5 states the physical regularity: unlike entry-context effects, which decay with separation, interference is thresholded. Axiom 4.2 (P5: Interference Thresholding). Runtime context effects are thresholded by shared-resource capacity. Concurrent elements interfere only through the hardware resources they share, each with finite capacity. While the elements’ combined demand on every shared resource stays within its capacity, the interference effect on each element’s static power, execution time, and dynamic energy remains negligible; once any shared resource saturates, the effect grows abruptly with the excess demand. Axiom P5 allows us to formalize when elements that run together are insensitive to each other’s presence. Definition 4.3 (Interference-Insensitivity). An element 𝑒 is interference-insensitive with respect to a set of runtime contexts containing it and a set of entry contexts, within measurement uncertainty, if for every 𝜌 and every 𝜙 in the two sets, ∆𝑠 𝑇𝑒 + ∆𝑇 𝑠𝑒 + ∆𝑠 ∆𝑇 + ∆𝑑 ≤ 𝑐𝛼 ⋅ 𝜎𝐸𝑒 , (12)

where ∆𝑥 = |𝑥𝑒 (𝜙, 𝜌) − 𝑥𝑒 (𝜙, {𝑒})| for 𝑥 ∈ {𝑠, 𝑇, 𝑑}, and the multipliers 𝑇𝑒 , 𝑠𝑒 are the isolation values 𝑇𝑒 (𝜙, {𝑒}), 𝑠𝑒 (𝜙, {𝑒}).

8 Directly bounding the total energy difference is not what we want. For instance, an element may have the same total energy under entry contexts 𝜙 and 𝜙′ , but 𝜙′ may lead to longer execution time and lower dynamic energy than 𝜙 by the compensating amount. In this case, a total-energy-only bound test would indicate history-insensitivity, but wherever time stands alone in composition (e.g., in the makespan and the static power it multiplies), the composite’s energy under 𝜙 and 𝜙′ would differ significantly. This contradicts history-insensitivity.

14

The left-hand side mirrors Equation (11): it is the same Axiom P1 expansion applied to the co-run and isolation runs, |𝐸𝑒 (𝜙, 𝜌) − 𝐸𝑒 (𝜙, {𝑒})|, so satisfying it bounds each component’s co-run perturbation separately and the total energy difference as well (Appendix B). Definition 4.4 (Mutual Interference-Insensitivity). Two elements are mutually interference-insensitive when both are interference-insensitive with respect to their shared runtime context {𝑒1 , 𝑒2 } and the entry contexts they execute under. Interference-insensitivity is the runtime counterpart of history-insensitivity. When elements that run together collectively exceed a shared resource’s capacity (Axiom P5), they ought to be characterized as a composite element, which the interference-insensitivity test detects. 4.1.3 Putting the Two Together A composition realizes both kinds of context, so we put them together in a single definition. Definition 4.5 (Mutual Context-Insensitivity). Two composed elements are mutually context-insensitive when each is history-insensitive with respect to the null context and the entry contexts the composition realizes for it, and interference-insensitive with respect to the runtime contexts the composition places it in, at those same entry contexts. The definition covers idle elements like any other element: an idle element’s duration is set by the schedule and its dynamic energy is zero, so both conditions reduce to their ∆𝑠 terms, with its energy variance inherited from the durations that set its gap (Section 3.3). When a composition is purely sequential and runs alone, every runtime context is a singleton, the differences in Equation (12) vanish, and the condition reduces to mutual history-insensitivity; the interference half constrains compositions that co-run elements.

4.2 The Reduction Theorem Pairs of elements can be mutually context-insensitive, as formalized by Section 4.1. This allows us to reduce the generic, context-dependent algebra of Section 3 to a simpler, context-independent form. Proposition 4.1 (Reduction Theorem). Let 𝑒1 and 𝑒2 be composed by an operator op ∈ {⊗, ⊕, ⊕multi }, with the pair mutually context-insensitive at confidence level (1 − 𝛼). Write op(0) for the same composition computed with every signature value evaluated at the null context in isolation. Then, whatever entry context the composition itself starts at, 𝐸1 op 𝐸2 and 𝐸1 op(0) 𝐸2 agree within operator-specific multiples of the elements’ bias tolerances 𝑐𝛼 ⋅ 𝜎𝐸𝑒 : 𝑖

| || ||𝐸1 op 𝐸2 − 𝐸1 op(0) 𝐸2 ||| ≤ 𝑚1 𝑐𝛼 𝜎𝐸𝑒1 + 𝑚2 𝑐𝛼 𝜎𝐸𝑒2 ,

op

𝑚1 𝑚2

⊗ ⊕ ⊕multi

1 2 2

1 2 2

(13)

The ⊕multi row covers its equal-duration domain; unequal durations compose through idle padding, whose added terms Appendix D derives. Proof sketch. Reduction replaces each element’s realized values with null-context isolation values through two kinds of substitution, each shifting the element’s static power, time, and dynamic energy by at most one bias tolerance. Entry-state substitution evaluates the element at the null context instead of its realized entry context, bounded by history-insensitivity; isolation substitution evaluates it in isolation instead of at the shared runtime context, bounded by interference-insensitivity. The multipliers count the substitutions each element needs: sequential composition runs alone, so each element carries only its entry-state substitution, and the parallel operators co-run their elements, so each carries both. Appendix C proves each case. When the composition itself starts at the null context, elements that start with it skip the entry-state substitution and drop one tolerance each, e.g., 𝑚1 = 0 under ⊗. The Reduction Theorem allows us to compose signatures at the null context in isolation, without characterizing every possible entry and runtime context, significantly reducing the characterization burden. Section 5 derives properties and rules of composition in both the general algebra and the resulting context-independent algebra. 15

Reduction is widely applicable in practice. Elapsed time or elements in between separate most pairs enough that their mutual entry context effects fall below measurement uncertainty. Concurrently running elements are often scheduled carefully to avoid bottlenecking on shared resources (lest they risk little gain or even slowdown), so their interference is often negligible as well (Axiom P5). Finally, many workloads run in steady-state thermal and cache regimes where signatures characterized once apply across many compositions; the set of entry and runtime contexts that introduces perturbation larger than the bias tolerance is not large, and the theorem would be applicable to many pairs. Where these conditions fail (cold-start transients, adjacent thermally-coupled kernels, shared-cache contention), the reduction does not apply, and more exact characterization is needed (Section 4.4). Composing elements at the null context in isolation (i.e., using the context-independent op(0) operators) accumulates the bias term: each element’s contribution to the composite’s energy may be off by up to 𝑚𝑖 times its bias tolerance (Equation (13)). Moreover, for a given composition, the offset is the same on every run, unlike measurement noise which varies run to run.9 Thus, over an 𝑛-element composition, each element contributes its own bias, growing the worst case total bias linearly with 𝑛.10 The worst case bound is computable in advance by summing every element’s 𝑚𝑖 𝑐𝛼 𝜎𝐸𝑒 bounds, and this can be checked against what the application tolerates 𝑖 at the planned composition depth (more details in Appendix D). When the bound exceeds that, the remedy is to characterize at a coarser granularity. Directly measuring a larger composite as a single element replaces every bias term accumulated inside it with one measured signature, at its own measured uncertainty. However, the tradeoff of coarser grained composition is reduced reusability: the composite’s signature is only valid for the contexts it was characterized under, whereas the individual elements’ signatures are valid for any composition that does not violate their mutual context-insensitivity.

4.3 The Context-Independent Form When the Reduction Theorem (Proposition 4.1) applies, we opt into context-independent algebra, where every signature value is evaluated in isolation at the null context 𝜙null , both 𝜙 and 𝜌 are dropped, and the bounded bias (Equation (13)) is accepted. The signature reduces to point values, 𝑆𝑒 = (𝑒, 𝜃, 𝜅, 𝜔, 𝜙null , 𝑠𝑒 , 𝑇𝑒 , 𝑑𝑒 , 𝜎𝑇2 , 𝜎𝐸2 , 𝑀). 𝑒 𝑒 The semantics of the operators themselves do not change: the accounting of Section 3.3 applies verbatim over the context-independent signatures.

4.4 The Interaction Graph Pairs that fail mutual context-insensitivity fall outside the Reduction Theorem, and their interaction must be characterized. Locality keeps this set sparse for separated pairs (Axiom P4), and capacity headroom for concurrent ones (Axiom P5). However, a failing pair does not force the whole composition into context-dependent treatment. Once characterized, the pair composes with its signature evaluated at the contexts the composition realizes; every other pair composes at the null context, and only the latter contribute bias terms. The characterized pair must in turn be interference-insensitive with respect to the remaining co-runners, with its co-run values in place of the isolation values in Equation (12). The interaction graph. Characterized interactions are recorded in the interaction graph. Nodes are element types rather than instances; for example, an attention layer that runs thousands of times per training step is one node, not thousands. Edges connect pairs of types whose interaction has been characterized. There are two kinds of edges, corresponding to the entry and runtime contexts. • Directed edge (𝐴 → 𝐵): an entry context interaction, where the state 𝐴 leaves behind perturbs 𝐵’s signature. • Undirected edge (𝐴 ↔ 𝐵): a runtime context interaction under co-execution. The edge carries each endpoint’s perturbation separately, since interference can affect one element of a pair and not the other. Because nodes are types, one edge covers all instances of the two types it connects, and characterization scales with the number of distinct types rather than the length of the execution. Every edge carries the responsible mechanisms from Table 1 and the workload parameters and contexts over which the interaction was characterized, analogous to Φ and 𝒫 in the signature. The edge also references the characterization outcome of step 4 9 The bias has a physical cause that the composition reproduces on every run. For instance, if element 𝑒 always runs right after a high2 power element 𝑒1 , 𝑒2 enters at the same elevated temperature on every run and consumes the same extra energy relative to its signature values at the null context. Averaging repeated runs therefore shrinks measurement noise but leaves the bias untouched. 10 Reaching that worst case requires every element’s bias to point in the same direction, i.e., sustained context drift like monotonic heating.

16

Table 2: The seven axioms of energy calculus: physical (P) and methodological (M). Label

No.

Name

Statement (short form)

P1 P2

3.1 3.3

Energy Decomposition Per-Device Static Power

P3

3.4

Interaction Structure

P4

4.1

Interaction Locality

P5

4.2

Interference Thresholding

𝐸𝑒 = 𝑠𝑒 𝑇𝑒 + 𝑑𝑒 ; all components non-negative. A device has a single static power; same-device concurrent execution draws it once over the makespan. Interaction effects decompose into a finite set of characterizable physical mechanisms. Entry-context effects decay with separation between elements. Runtime-context effects are negligible below shared-resource capacity and grow abruptly past saturation.

M1

3.2

Intrinsic Uncertainty

M2

3.5

Interaction Measurability

Error is summarized by mean and variance; for elements measured directly, static power is exact and component errors uncorrelated; uncertainty propagates through every composition. Signatures are characterized by measurement under multiple contexts, with other variables fixed.

below, which is either the signature extended over the realized contexts or the composite pair’s signature. The measured deviation that triggered characterization is kept as edge metadata, but composition never consumes it. Composition consumes only signatures, and the interaction graph is a sparse index into them. Pairwise edges do not by themselves justify the reduction for a whole composition. Individually negligible effects can accumulate. Kernels in a long prefix can each heat the device by less than the pairwise bias tolerance while their aggregate shifts a later element past throttling, and any two of three concurrent elements can fit within a shared bandwidth that all three together exceed. The applicability condition is therefore stated at the level of whole prefixes and sub-DAGs: for every element, its actual entry context under the composed schedule must lie in a characterized set over which it is history-insensitive, and its runtime context must lie in a characterized set over which it is interference-insensitive. When either fails, the offending prefix becomes a composite element with its own signature and trace, and cumulative effects surface when the composite’s measured energy deviates from its composed prediction (Section 5.2); the detected cause is then recorded in the interaction graph. Building the interaction graph. The interaction graph starts empty and grows only as measured deviations justify characterization. 1. Context-independent composition. Compose signatures with every value at the null context in isolation, correct within the Reduction Theorem’s tolerances for pairs satisfying its condition. 2. Deviation detection. Compare composed predictions against direct measurement (Section 5.2). Pairs with consistent deviation are candidates for the interaction graph. 3. Mechanism identification. For each candidate pair, identify the dominant mechanism from Table 1 and measure the interaction effect via the mechanism’s characterization protocol. 4. Signature update. Either characterize the element as a function of 𝜙 or 𝜌 (for reusable dependence) or characterize the composite pair as a single element (for pair-specific dependence). Either result composes further with the same operators. 5. Reuse. The characterized signature (or composite) is reusable across any composition whose contexts fall within the characterized sets.

4.5 Axioms and Notation This concludes the development of foundational axioms and notation. Table 2 summarizes them, and Table 3 collects the core notation used in the remainder of the paper. 17

Table 3: Core notation. Symbol

Meaning

Symbol

Meaning

𝑒 𝜃 𝜅 𝜔 𝜔dev 𝜔elem 𝜙 Φ 𝜙null 𝜌 𝒫 𝑠𝑒

Energy element Workload parameters Implementation realizing the element’s operation Operating point Device-wide part of 𝜔 Per-element part of 𝜔 Entry context (state from prior execution) Set of characterized entry contexts Null context (no state from prior execution) Runtime context Set of characterized runtime contexts Static power of the device hosting 𝑒 (W)

𝑇𝑒 𝑑𝑒 𝐸𝑒 𝑆𝑒 𝜎𝑇2 𝑒 , 𝜎𝐸2 𝑒 𝜎𝑑2𝑒 ⊗ ⊕ ⊕multi 𝑐𝛼 𝒟𝑒

Execution time (s) Dynamic energy (J) Total energy 𝑠𝑒 𝑇𝑒 + 𝑑𝑒 (J) Energy signature Variances of measured time and total energy Variance of dynamic energy Sequential composition Same-device parallel composition Cross-device parallel composition Two-sided Gaussian multiplier at confidence 1 − 𝛼 Set of devices hosting the element

Table 4: Properties and corollaries of the composition algebra (short form). Full statements appear in the body; proofs in appendices. No.

Name

Statement (short form)

Property 5.1

Commutativity

Property 5.2

Associativity

Property 5.3

Closure

Property 5.4

Non-Distributivity

Property 5.5

Monotonicity

⊕ and ⊕multi commute unconditionally; ⊗ does not commute in general. Under the Reduction Theorem, ⊗ commutes in the context-independent algebra (Corollary 5.1). All three operators are associative; groupings are equivalent, orderings are not. Every composition is itself an energy element with a well-defined signature. ⊗ does not distribute over parallel composition; the sides differ by the duplicated dynamic energy. Component-wise no-smaller signatures can decrease a composition under context dependence. Under the Reduction Theorem, they never decrease any composition in the context-independent algebra (Corollary 5.2).

5 Properties of Energy Calculus Section 3 developed the general context-dependent algebra, and the Reduction Theorem (Proposition 4.1) established when it reduces to the simpler context-independent algebra. This section derives useful properties and rules for both.

5.1 Algebraic Properties In this section, we establish the algebraic properties of the composition operators. All three operators are associative and closed, the parallel operators commute, and sequential composition does not distribute over parallel; these hold in the general context-dependent algebra and therefore in the context-independent algebra as well.11 Additionally, in the context-independent algebra, sequential composition commutes and monotonicity holds. The properties and their corollaries are summarized in Table 4. 11 A context-independent evaluation is a context-dependent evaluation with every signature value taken at the null context in isolation, so identities that hold over all contexts instantiate to the context-independent algebra. Non-distributivity, a negative result, transfers through its counterexample, which is built from null-context point values.

18

5.1.1 Commutativity Consider a high-power element that leaves the device hot, followed by a thermally sensitive element that throttles when hot (Section 3.4). Also consider the same two elements executed in the opposite order—if the thermally sensitive element runs first on a cooler device, it may avoid throttling and consume different energy. Therefore, swapping the order of sequential composition can in general change the total energy, unlike parallel compositions that are structurally symmetric. Property 5.1 (Commutativity). Parallel operators ⊕ and ⊕multi are unconditionally commutative, in both the context-dependent and context-independent algebras: 𝐸1 ⊕ 𝐸2 = 𝐸2 ⊕ 𝐸1

𝐸1 ⊕multi 𝐸2 = 𝐸2 ⊕multi 𝐸1

(14) (15)

Sequential composition does not commute in general: 𝐸1 ⊗ 𝐸2 ≠ 𝐸2 ⊗ 𝐸1 .

(16)

Proof sketch. Parallel commutativity follows from symmetry of max and +: both elements evaluate at the shared entry context 𝜙0 and the shared runtime context 𝜌 = {𝑒1 , 𝑒2 }, leaving no label-dependent term. For the sequential case, let 𝜙0 be the shared entry context, with the composition running alone so that runtime contexts are singletons and suppressed. Then 𝐸1 ⊗ 𝐸2 = 𝑠1 (𝜙0 )𝑇1 (𝜙0 ) + 𝑑1 (𝜙0 ) + 𝑠2 (𝜙1 )𝑇2 (𝜙1 ) + 𝑑2 (𝜙1 ) with 𝜙1 the exit context of 𝑒1 ’s execution from 𝜙0 , and 𝐸2 ⊗ 𝐸1 = 𝑠2 (𝜙0 )𝑇2 (𝜙0 ) + 𝑑2 (𝜙0 ) + 𝑠1 (𝜙2 )𝑇1 (𝜙2 ) + 𝑑1 (𝜙2 ) with 𝜙2 the exit context of 𝑒2 ’s execution from 𝜙0 . In general 𝜙1 ≠ 𝜙2 , and the two sums differ. The full proof appears in Appendix E.1. Non-commutativity reflects context propagation: execution order changes what each element inherits from its predecessor. When the elements are mutually context-insensitive, however, the Reduction Theorem removes the order dependence. Corollary 5.1. When 𝑒1 and 𝑒2 are mutually context-insensitive under both orderings, the Reduction Theorem (Proposition 4.1) reduces both orderings to the same context-independent value: sequential composition commutes in the context-independent algebra. The physical orderings themselves agree within their summed reduction bounds, 𝑐𝛼 (𝜎𝐸𝑒 + 𝜎𝐸𝑒 ) when the composition starts at the null context. 1

2

Note that the corollary’s equality is for total-energy values, not for full composite signatures: two orderings can consume the same energy while leaving different exit contexts, so one ordering substitutes for the other inside a larger composition only when their exit contexts are equivalent over the downstream admissible context set. Reordering is also available only where the schedule’s dependencies permit both orders. 5.1.2 Associativity Whether a three-stage pipeline is modeled as the first two stages followed by the third, or the first followed by the latter two, is bookkeeping: the stages execute in the same order either way, and the total energy is the same. Property 5.2 (Associativity). All three operators are associative, in both context-dependent and context-independent algebras: (𝐸1 ⊗ 𝐸2 ) ⊗ 𝐸3 = 𝐸1 ⊗ (𝐸2 ⊗ 𝐸3 ) (𝐸1 ⊕ 𝐸2 ) ⊕ 𝐸3 = 𝐸1 ⊕ (𝐸2 ⊕ 𝐸3 )

(17)

(𝐸1 ⊕multi 𝐸2 ) ⊕multi 𝐸3 = 𝐸1 ⊕multi (𝐸2 ⊕multi 𝐸3 ) Associativity of ⊗ preserves the order of execution: it is the equivalence of groupings of one composition, not of orderings. Proof sketch. Associativity of ⊕ and ⊕multi follows because grouping changes no element’s contexts—the same elements co-start and co-run either way—and their energy formulas (Equations (7) and (8)) are built from addition and maximum, both associative. For ⊗, context propagates forward with execution order regardless of grouping, so each element inherits the same context in either grouping. Appendix E.2 provides the full proof. 19

5.1.3 Closure Composition operators take signatures as operands, and they produce a well-defined signature as output. Property 5.3 (Closure). A composition of energy elements via any operator is itself an energy element with a welldefined energy signature, in both the context-dependent and context-independent algebras. Proof sketch. Most signature entries are trivially well-defined: the composite inherits its workload parameters, implementation, and operating point from the operands, and its duration 𝑇 ′ , dynamic energy 𝑑′ , and duration variance follow the operator’s time and dynamic accounting. The proof shows that the remaining three—static power, energy variance, and the composite’s contexts—are also well-defined. Axiom P1 fixes static power to the non-negative summary 𝑠′ = (𝐸1 op 𝐸2 − 𝑑′ )∕𝑇 ′ , a derived quantity rather than a device’s baseline draw. The variance propagated by Property 5.6 is carried in the signature directly. The composite’s entry and exit contexts follow from its parts, and each operand’s runtime context is recovered from the composite’s schedule and the operand’s position in it. Appendix E.3 writes out the precise formulas and completes the proof. Closure enables hierarchical composition. An element composed within the calculus keeps its term: an enclosing composition still sees its parts, and evaluation derives each constituent’s contexts, as the proof sketch describes. An element measured directly has no parts to see; its signature stands on its own over the contexts it was characterized under (Φ and 𝒫). Either way, the same operators apply at every level of the hierarchy, and context propagation is handled uniformly. Within a single composition, some elements may be composed and others directly measured, some fine-grained and others coarse. 5.1.4 Distributivity Applying distributivity to a sequential composition (⊗) over a parallel composition (⊕ or ⊕multi ) would duplicate the first element, which is not equivalent to what the original composition executes. Property 5.4 (Non-Distributivity). Sequential composition does not distribute over parallel composition, in both the context-dependent and context-independent algebras: 𝐸1 ⊗ (𝐸2 ⊕ 𝐸3 ) ≠ (𝐸1 ⊗ 𝐸2 ) ⊕ (𝐸1 ⊗ 𝐸3 )

𝐸1 ⊗ (𝐸2 ⊕multi 𝐸3 ) ≠ (𝐸1 ⊗ 𝐸2 ) ⊕multi (𝐸1 ⊗ 𝐸3 )

(18) (19)

Proof sketch. On the right-hand side, both branches contain 𝑒1 , so 𝑒1 executes twice. Expanding both sides in the context-independent algebra, the static terms coincide—the makespan is the same under either structure— and the two sides differ by exactly 𝑑1 , the dynamic energy of the duplicated execution. The full proof appears in Appendix E.4. 5.1.5 Monotonicity When two elements run back to back, the first element’s exit context can make the second element cheaper or more expensive than it would be in isolation. This creates cases that break monotonicity: replacing the earlier element with one that consumes more energy but leaves a context that makes the later element much cheaper (e.g., more cache-friendly output or a cooler device) can lower the total energy of the composition. Property 5.5 (Non-Monotonicity). In the context-dependent algebra, total energy is not monotone in a composition’s sub-elements: it is possible that replacing a sub-element with one that is no cheaper in any signature component— static power, execution time, and dynamic energy—can decrease the composition’s total energy. The failure comes from replacement changing the exit context the rest of the composition inherits: replacing 𝑒1 with a more expensive 𝑒1′ lowers the total of 𝑒1′ ⊗ 𝑒2 below that of 𝑒1 ⊗ 𝑒2 whenever 𝑒1′ leaves a context that makes 𝑒2 sufficiently cheaper. Appendix E.5 constructs an explicit instance. In the context-independent algebra, however, every signature value is evaluated at the null context, so a replacement cannot change what the rest of the composition evaluates at.

20

Corollary 5.2. In the context-independent algebra, replacing a sub-element with one whose signature has no smaller static power, execution time, and dynamic energy never decreases the energy of any composition that contains it. Here, replacing means swapping that element’s signature alone, with the schedule still feasible, shared operating parameters fixed, and every other signature unchanged. Proof sketch. Each operator’s energy formula is monotone in (𝑠𝑖 , 𝑇𝑖 , 𝑑𝑖 ), since addition and maximum are both monotone, and monotonicity carries over to hierarchies because an enclosing composition consumes a subcomposite only through its duration, dynamic energy, and total energy (Property 5.3), all weakly increased by such a replacement. The full proof appears in Appendix E.5. Corollary 5.2 makes conservative bounds useful: replacing uncertain signatures with upper bounds yields a valid upper bound on the composed energy in the context-independent algebra.

5.2 Uncertainty and Measurement Every measured signature component carries noise, and a composed prediction inherits the noise of every element it combines. Physical measurement of energy is authoritative, and divergence between composed predictions and direct measurement signals a composition assumption violation, an incomplete characterization, or a measurement limitation. This subsection first derives how uncertain a composed prediction is, and then lays out three places where the propagated uncertainty is useful. 5.2.1 Propagating Uncertainty A composed prediction’s variance combines the variances of its elements. This needs the elements’ distributions to stay fixed and their measurement errors to be independent. The first is the context-independent algebra’s standing assumption: under mutual context-insensitivity, every execution of an element is a draw from its nullcontext characterization.12 The second is an assumption we add; it holds largely in practice because run-torun time jitter and per-run dynamic-energy noise belong to each element, and characterization protocols keep measurement conditions (e.g., ambient temperature) fixed across runs (Axiom M2). Property 5.6 (Variance Propagation). The total energy variance of a single directly measured element is given by Equation (5). In the context-independent algebra, with measurement errors independent between the two elements and the times (𝑇1 , 𝑇2 ) jointly independent of the dynamic energies (𝑑1 , 𝑑2 ): 𝜎𝐸2 ⊗𝐸 = 𝜎𝐸2 + 𝜎𝐸2 1

2

1

2

(

𝜎𝐸2 ⊕𝐸 = 𝜎𝑑2 + 𝜎𝑑2 + 𝑠2 Var max(𝑇1 , 𝑇2 ) 1 2 1 2

𝜎𝐸2 ⊕ 1

)

( ) 2 2 2 𝐸 = 𝜎𝑑 + 𝜎𝑑 + (𝑠1 + 𝑠2 ) Var max(𝑇1 , 𝑇2 )

multi 2

1

2

(20) (21) (22)

For ⊕, 𝑠 is the shared static power of the device (i.e., 𝑠 = 𝑠1 = 𝑠2 ). The sequential rule adds the operands’ carried energy variances and takes any operands. The parallel rules split each operand into its time and dynamic variances, because static power converts time noise into energy noise: when a duration fluctuates by ∆𝑇, energy fluctuates by ∆𝑇 times the static power that keeps flowing through those seconds, and a scale factor on a fluctuation enters its variance squared. For ⊕multi the weight is (𝑠1 + 𝑠2 )2 , because a makespan fluctuation holds both devices longer and their combined static draw flows through it. This split is why parallel operands must each draw one constant static power, as elements measured directly and constant-baseline composites do (Property 5.3). Appendices F.1 and F.2 derive the three equations, and Appendix F.3 gives closed forms and limit cases for Var(max(𝑇1 , 𝑇2 )). Under the context-dependent algebra, the fluctuation of elements can couple through shared contexts (e.g., a run where 𝑒1 runs hot or long shifts the context 𝑒2 inherits), and independence fails. In this case, a contiguous segment containing the coupled elements should be characterized as a single composite (Section 4.4). The composite’s variances are measured directly, independence holds at its boundary, and propagation via Property 5.6 proceeds between insensitive units as before. 12 Each execution of an element is a draw from a distribution, and in the general context-dependent case, the distribution itself shifts with the element’s entry and runtime contexts (i.e., not fixed). However, under mutual context-insensitivity, the distribution is characterized at the null context in isolation and fixed, so every execution is, within the bias tolerance, a draw from that fixed distribution.

21

5.2.2 Using Propagated Uncertainty The machinery below consumes a composed prediction 𝐸̂ and its propagated standard deviation 𝜎𝐸̂ from Property 5.6, and applies under either algebra. Prediction intervals and comparison. From the propagated variance, we can more reliably compare the energy consumption of different configurations based on intervals rather than points. A composed prediction carries the interval 𝐸̂ ± 𝑐𝛼 ⋅ 𝜎𝐸̂ , covering a single run of the composition at confidence (1 − 𝛼) (if it’s the average √ over 𝑛 repeated runs tightens to 𝐸̂ ± 𝑐𝛼 𝜎𝐸̂ ∕ 𝑛).13 We can confidently say that one configuration consumes less energy than another only when its interval’s upper bound lies below the other’s lower bound; comparing point predictions alone would let run-to-run noise decide. Deviation detection. Propagated uncertainty also serves as a diagnostic. We compose signatures to predict a composition’s energy, then measure the composition directly. The two disagree when √ , (23) + 𝜎𝐸2 |𝐸predicted − 𝐸measured | > 𝑐𝛼 ⋅ 𝜎𝐸2 measured

predicted

where 𝜎𝐸2 is the prediction’s propagated variance and 𝜎𝐸2 the direct measurement’s own variance. The predicted measured variance of the difference is the sum of the two variances because the two are independent: the measurement is a fresh run, while the prediction inherits its error from characterization. Agreement within propagated uncertainty means the composition model is consistent with measurement at the current precision. Disagreement means an assumption failed: an interaction the composition does not capture, a measurement that needs recalibration, or a signature applied outside its characterized range. Even under a correct model, the test triggers with probability 𝛼, and testing many pairs multiplies such false triggers; recharacterization should follow persistent triggers, not single ones. The workflow of Section 4.4 then localizes and characterizes the cause. The right-hand side of Equation (23) carries random error only. On∑top of this random error, the bias accepted by the Reduction Theorem accumulates across composed elements ( 𝑖 𝑚𝑖 𝑐𝛼 𝜎𝐸𝑒 , Appendix D), and over deep 𝑖 compositions can exceed the propagated interval. This composite-level check is what catches it. Refinement and coarsening. The deviation test (Equation (23)) also governs granularity changes. We refine an element by decomposing it into sub-elements and composing their signatures, and coarsen a set of composed elements into a single element with an aggregate signature; the two are inverses up to measurement error. Property 5.7 (Refinement–Coarsening Consistency). Let element 𝑒 have directly measured signature 𝑆𝑒 , and let 𝑒 be refined into sub-elements 𝑒1 , … , 𝑒𝑛 composed via the appropriate operators, yielding composed signature 𝑆̂𝑒 . If the sub-elements are mutually context-insensitive, then at confidence level (1 − 𝛼), √ ∑ |𝐸𝑒 − 𝐸̂ 𝑒 | ≤ 𝑚𝑖 𝑐𝛼 𝜎𝐸𝑒 + 𝑐𝛼 ⋅ 𝜎𝐸2 + 𝜎2̂ , (24) 𝑖

𝑖

𝑒

𝐸𝑒

where the first term is the composition’s accumulated bias bound (Equation (13)); it drops to zero when each 𝑒𝑖 ’s signature is instead correctly characterized at every entry and runtime context the refinement realizes. When the hypothesis fails, the deviation test triggers, meaning the diagnostic is working as intended. This gives consistency checks across granularities; the full statement and proof appear in Appendix G.

6 Application: Operating Frontiers Under Context-Independence We extend energy calculus from composing energy totals to composing time–energy Pareto frontiers. This section operates under the context-independent algebra, where composed elements are mutually context-insensitive at every implementation and operating point. Elements that are not mutually context-insensitive are instead characterized together as a single composite (Section 4.4), which this section treats as one element. 13 Note that the Gaussian shape behind 𝑐 is still an approximation: sums of many weakly dependent errors approach Gaussian by the 𝛼

central limit theorem, but the maxima of parallel composition do not.

22

6.1 Operating Set and Frontier The operating set Ω𝑒 of element 𝑒 is the set of operating points at which 𝑒 can execute. An element may also have multiple implementations 𝜅 of its operation (Section 3.1). At a fixed workload parameter (thus suppressed from the argument), sweeping the pairs (𝜅, 𝜔) over the element’s implementations and operating points maps each pair to a point on the time–energy plane: (𝑇𝑒 (𝜅, 𝜔), 𝐸𝑒 (𝜅, 𝜔)) where 𝐸𝑒 (𝜅, 𝜔) = 𝑠𝑒 (𝜔dev ) 𝑇𝑒 (𝜅, 𝜔) + 𝑑𝑒 (𝜅, 𝜔) (Axiom P1).14 The achievable set of 𝑒 is the set of these swept points, and from the achievable set, we can extract the operating frontier ℱ𝑒 of 𝑒 by removing Pareto-dominated points. Frontiers of this form arise at every granularity, from a single GPU kernel to model layers [20], training iterations [6], and entire training jobs [21]. Composing per-element operating-point schedules assumes that switching between operating points takes negligible time and energy compared to the elements’ time and energy. When switching time is non-negligible, that influences the granularity at which operating-point switching can be applied. Non-trivial switching time and energy can be accounted for by a transition element 𝑒𝜔→𝜔′ , with its own signature composing like any other element.

6.2 Frontier Composition With each element carrying its own operating set and frontier, we now discuss how the frontiers of composed elements are obtained. We begin with the three composition operators of Section 3.3, and then discuss general composition. 6.2.1 Sequential Composition Consider two elements that run back to back on one device, each free to pick its own implementation and operating point. Durations add and energies add, so each choice of implementations and operating points lands at the component-wise sum of two swept points. The set of all pairwise sums of two point sets is therefore their Minkowski sum, written: ℱ𝑒1 ⊞ ℱ𝑒2 = {(𝑇1 + 𝑇2 , 𝐸1 + 𝐸2 ) ∶ (𝑇1 , 𝐸1 ) ∈ ℱ𝑒1 , (𝑇2 , 𝐸2 ) ∈ ℱ𝑒2 }.

(25)

Property 6.1 (Sequential Frontier Composition). Let 𝑒1 and 𝑒2 be mutually context-insensitive at every choice of implementations and operating points. Under ⊗, ( ) ℱ𝑒1 ⊗𝑒2 = Pareto-min ℱ𝑒1 ⊞ ℱ𝑒2 . (26) Proof sketch. Each choice of implementations and operating points sums the two elements’ durations and energies, so the achievable set is exactly the pairwise-sum set. Replacing either element’s swept point with a frontier point that dominates it improves the composite in at least one coordinate without worsening the other, so restricting the sweep to the elements’ own frontiers loses no composite-optimal point. The full proof appears in Appendix H.1. 6.2.2 Parallel Composition Now let the two elements run concurrently, on one device or on two. Whichever element finishes first, every participating device is held until the later one finishes (Section 3.3), so static power is drawn for the shared makespan no matter how fast either element runs. Under ⊕, a sweep chooses implementations and operating points, with the operating points sharing the device-wide part 𝜔dev . Across devices, ⊕multi itself requires equal durations, so wherever a sweep leaves them unequal, an idle element pads the earlier-finishing device to the makespan before ⊕multi applies (Section 3.3.3); each device then draws its own static power, with no shared-𝜔dev constraint. At each pair of implementations, each operating-point pair evaluates to 𝐸𝑒1 ⊕𝑒2 (𝜔1 , 𝜔2 ) = 𝑠(𝜔dev ) ⋅ 𝑇max + 𝑑1 (𝜔1 ) + 𝑑2 (𝜔2 ) ( ) 𝐸𝑒1 ⊕multi 𝑒2 (𝜔1 , 𝜔2 ) = 𝑠1 (𝜔1 ) + 𝑠2 (𝜔2 ) ⋅ 𝑇max + 𝑑1 (𝜔1 ) + 𝑑2 (𝜔2 )

( ) 𝑇max = max 𝑇1 (𝜔1 ), 𝑇2 (𝜔2 ) .

(27)

14 Static power moves with the device-wide operating point 𝜔 dev . DVFS, for instance, changes a device’s ready-state static power draw.

23

For ⊕, 𝑠 is the shared static power of the device (𝑠 = 𝑠1 = 𝑠2 ). For ⊕multi , the display takes each padded device’s idle draw equal to its active draw; Appendix H.2 keeps the two distinct. The makespan term couples the two sweeps, so unlike the sequential case, the composite frontier is not a Minkowski sum. Instead, it is obtained by sweeping the elements’ implementations and operating points in full and keeping the Pareto-optimal points. The makespan term also gives the composite frontier its right end. Slowing the longer-running element typically saves its dynamic energy but stretches the makespan, over which every participating device keeps drawing static power. Once further slowdown saves less dynamic energy than the added static energy over the extra time, total energy turns back upward, and the slower points are Pareto-dominated. The composite frontier therefore terminates at the energy-minimizing makespan. Empirically, Perseus [6] observes this right-end upturn in its measured iteration-level time–energy curve. One interesting observation is that when sweeping the two elements’ implementations and operating points to obtain points on the composite’s time–energy plane, restricting the sweep to the elements’ own Pareto-optimal points is unsound: a swept point that is Pareto-suboptimal for an element may be part of a Pareto-optimal point for the composite. When one element finishes before the other, the window from its finish to the makespan is its slack. Suppose that the earlier-finishing element’s device draws the same static power at every swept operating point. That static power is then drawn for the full makespan no matter what the element does, so the element affects the composite total only through its dynamic energy, not total energy. However, the element’s own frontier is about Pareto-optimal time and total energy, not dynamic energy. The result is that swept points past the element’s minimum total energy point can be Pareto-optimal in terms of time and dynamic energy, and therefore part of the composite’s Pareto-optimal frontier. This generalizes to an operational rule: Property 6.2 (Slack-to-Energy Conversion). Let 𝑒1 and 𝑒2 be parallel composed elements with durations 𝑇1 < 𝑇2 , so that the makespan is 𝑇max = 𝑇2 and 𝑒1 has slack. Suppose 𝑒1 can be slowed, moving its signature components from (𝑠1 , 𝑇1 , 𝑑1 ) to (𝑠1′ , 𝑇1′ , 𝑑1′ ) with 𝑇1 ≤ 𝑇1′ ≤ 𝑇max . On a shared device, suppose further that the move changes only 𝑒1 ’s implementation or the per-element part of its operating point, leaving the device-wide part, and with it the device’s static power and 𝑒2 ’s signature, unchanged. The move then does not increase composite energy at unchanged makespan whenever: (i) 𝑑1′ ≤ 𝑑1 . On separate devices, the move does not increase composite energy at unchanged makespan whenever the following hold in addition to (i): (ii) 𝑠1′ ≤ 𝑠1 ; and (iii) 𝑠1′ does not exceed the draw of the state 𝑒1 ’s device idles in.

Proof sketch. On a shared device, the hypothesis fixes the device’s static power and 𝑒2 ’s signature, and the makespan is unchanged since 𝑇1′ ≤ 𝑇max , so the composite’s energy changes by 𝑑1′ −𝑑1 , non-positive under condition (i). On separate devices, the energy change decomposes into three terms: the change in dynamic energy, the change in static energy over the element’s execution, and the exchange of idle time for computation over the added duration. Conditions (i)–(iii) make the corresponding terms non-positive. The full proof appears in Appendix H.2.

Condition (iii) is the race-to-idle decision. Filling the slack window with slowed computation wins when idling draws more static power than the slowed computation does. Hardware with a deep low-power idle state instead makes racing to finish and idling the cheaper schedule. The actual method for slowing an element depends on how elements are composed and how their operating points are defined. On a shared device, changing 𝑒1 ’s implementation or the per-element part of its operating point can control its time and dynamic energy; the device-wide part couples both elements’ time, dynamic energy, and static power, requiring joint consideration. On separate devices, device-wide operating points can control elements independently (e.g., DVFS on each device). 6.2.3 General Composition The rules above apply one operator at a time, with the composition term fixed. Deriving the optimal frontier of a DAG-composed element is a significantly harder problem due to a global property: changing the implementation or operating point of one element (and therefore its duration) potentially affects every other element’s schedule and amount of slack. This problem, in fact, contains as a special case the discrete time–cost tradeoff problem of project planning, which is strongly NP-hard [8] and even APX-hard assuming standard conjectures [17]. Perseus addresses this by solving a continuous relaxation of the problem exactly [6]. 24

7 Discussion This section examines what the framework covers, what lies outside its scope, and what remains open.

7.1 What the Framework Covers Energy calculus applies to any computational system that meets four conditions: (i) elements admit a static– dynamic decomposition whose first-order error is acceptable at the chosen granularity (Axiom P1); (ii) interactions belong to a finite mechanism inventory, each summarizable by a small number of effective state variables (Axiom P3); (iii) entry-context effects decay with separation (Axiom P4) and interference stays below sharedresource capacity (Axiom P5), so that the interaction graph can remain sparse; and (iv) measurement instrumentation resolves the chosen granularity, so that the insensitivity tests are informative rather than vacuous (Axiom M1, Axiom M2). Conditions (i) through (iii) ask that the axioms’ idealizations hold to acceptable accuracy, and (iv) asks that measurement can detect when they do not (Axiom P2 holds by construction, since device boundaries are drawn where static power is drawn once). We expect most modern ML workloads (training, inference, fine-tuning), data-processing workloads, and scientific simulations on GPU and CPU hardware to satisfy these conditions, with direct verification discussed in Section 7.3. Under them, the calculus supports five capabilities, subject to empirical validation in subsequent work. 1. Compositional prediction. Characterized signatures compose algebraically, so the calculus can predict total energy and propagated uncertainty for workload variations (schedule changes, parallelism adjustments, element substitution) without re-running the workload. 2. Reordering as a first-class energy lever. Conditional commutativity (Property 5.1) exposes execution order as an energy lever, since two orderings of the same elements can consume different energy when a driving mechanism is active. Characterizing the thermal, cache, and power-delivery mechanisms (Section 3.4) turns reordering from an informal heuristic into a quantity the calculus can predict and bound. Because equal totals do not imply equal exit contexts, substituting one ordering for another inside a larger composition additionally requires the exit contexts to be equivalent over the downstream admissible set (Property 5.1). 3. Cross-hardware transfer. The compositional structure is hardware-independent, since signatures characterized as functions of implementation 𝜅, operating point 𝜔, and context 𝜙 on a target accelerator compose under the same operators as those on the reference platform. Migration reduces to re-characterizing individual elements on the target, over the target’s own implementation set; the algebra does not change. 4. Anomaly localization. Deviation detection (Equation (23)) is designed to surface the pair whose predicted energy diverges from measurement. The sparsity of the interaction graph, which locality (Axiom P4) and capacity headroom (Axiom P5) make possible, restricts the search because a workload-level anomaly reduces in principle to a pair-level or prefix-level diagnosis (Section 4.4). 5. Principled coarsening and refinement. Refinement–coarsening consistency (Property 5.7) lets a practitioner trade characterization cost against prediction resolution without changing the algebra.

7.2 What the Framework Does Not Cover Non-time tradeoffs. The calculus reasons in the time–energy plane parameterized by (𝜃, 𝜔). Tradeoffs that replace the time axis with a non-time objective (accuracy, throughput, model quality) are obtained by composing such objective functions with calculus-computed energy. A curve in (𝐴, 𝐸) space, for example, is {(𝐴(𝜃), 𝐸 ⋆ (𝜃)) ∶ 𝜃 ∈ Θ}, with 𝐴(𝜃) supplied by the application domain and 𝐸 ⋆ (𝜃) the minimum energy over the element’s implementations and operating points, read off the operating frontier (Section 6). The framework supplies the energy axis of any such tradeoff but does not define the other axes. Attribution of held-device static power. The composition operators attribute every participating device’s static power over the full makespan to the composition, with idle elements covering the gaps (Section 3.3). This is an accounting convention rather than a physical necessity. It is the appropriate accounting for dedicated allocations but debatable for shared clusters, where an idle device may serve other work. Alternative attribution policies change how consumed energy is divided among compositions; the calculus computes the consumption itself and leaves the division to the deployment context. 25

Context driven from outside the composition. The general calculus assumes that context evolves under the traces of the composed elements, with exit contexts assembling by the mechanisms’ update rules from the composition’s own execution (Section 3.4). When context is instead driven by execution outside the composition, this assumption fails. For example, in a virtualized multi-tenant datacenter, co-located tenants share caches, memory bandwidth, and cooling with the composition, yet their elements are invisible to it, perturbing both the entry context an element inherits and the runtime context it executes in. The mechanisms themselves are in the inventory and the signature’s context dependence is characterizable (Axiom M2), but the drivers of the realized context are neither measurable nor controllable from within the composition (Definition 3.2), so the calculus cannot say which characterized context applies. Runtime adaptation. Signatures characterized at a fixed operating point and context do not account for runtime changes (closed-loop thermal throttling that interacts with workload dynamics, autotuning that changes kernel variants within a run, or changes to workload parameters of a subset of elements across iterations). Such elements also lack a fixed trace (Definition 3.1), since their actions depend on what they observe at runtime. Implementation choice fixed ahead of execution, by contrast, is the signature’s implementation entry 𝜅 (Section 3.1); what falls outside the framework is switching driven by runtime observation. Adaptive regimes require online signature updates; the framework admits this extension but does not specify it. Uncharacterized elements. The framework predicts only for elements with characterized signatures on the target hardware. We cannot predict a workload whose elements remain unmeasured; extrapolation from nothing is outside scope. Sub-first-order physical effects. The static–dynamic decomposition is a first-order approximation. Secondorder effects (voltage regulator efficiency curves, temperature-dependent leakage beyond the exponential model, current-draw harmonics) are not resolved by the algebra: their run-varying part folds into 𝜎2 , and their repeatable part is bias. These effects inflate the elements’ variances and hence the bias tolerances the Reduction Theorem carries; when the inflated tolerances exceed what the application requires, we must refine characterization.

7.3 Open Problems Axiom minimality. The seven axioms split into physical (Axiom P1–Axiom P5) and methodological (Axiom M1, Axiom M2) commitments. Their independence is open: an independence proof would confirm minimality, whereas a derivation of one axiom from the others would simplify the set. Axiom P2 is a candidate for demotion, as it is satisfiable by construction whenever device boundaries are drawn at power-domain boundaries, which makes it closer to a definitional commitment than a physical one. Algebraic placement. Conditional commutativity and non-distributivity together place energy calculus in a specific algebraic neighborhood (Section 8). Whether that neighborhood corresponds to a known structure or to a new one remains open. Worst-case energy bounds. The current uncertainty treatment carries mean and variance, with conservative operator-level bounds. Carrying full distributions, using convolution for sums and order statistics for max, would yield worst-case energy bounds for safety-critical or SLA-bound systems and tighten uncertainty propagation through general DAGs. Although Appendix F.4 sketches the building blocks, the full integration with the algebra remains open. Power-aware composition. Energy calculus already considers power partially, with static power 𝑠 a primitive and time-averaged dynamic power within an element recoverable as 𝑑∕𝑇. However, it does not carry the instantaneous power profile within an element or, derivatively, the peak power composed across elements. Operationally, peak power matters because it triggers thermal events and power caps, and datacenter supply constrains concurrent draw across devices.

26

A peak-power axis composed under the same three operators is plausible, but each operator carries a different rule. Under ⊗, the elements are disjoint in time on their device, so the device peak is the max of individual peaks. Under ⊕, the two elements’ dynamic power draws overlap in time on the same device, so the composite’s dynamic peak is bounded by the sum of the individual dynamic peaks on top of the single static draw (Axiom P2), attained when the peaks align in time, subject to the device’s delivery capacity. Once the capacity is exceeded, the resulting throttling feedback falls outside the framework (runtime adaptation above). Under ⊕multi , each device hosts only its own element and keeps its own peak; what composes is the aggregate draw across devices, whose peak is bounded by the sum of the per-device peaks and attained when they align in time. The saturation side of this aggregate constraint is already a runtime-context mechanism (Axiom P5), and what is missing is the composed power profile that determines when it triggers. Whether these rules compose cleanly into a second algebra alongside the energy one, or whether the device-capacity bound forces a reformulation, is open. Interaction-graph sparsity at scale. The practical reach of the Reduction Theorem leans on the empirical claim that most element pairs are mutually context-insensitive within uncertainty. Measuring the interaction graph on diverse training or inference workloads would test the claim directly and quantify how much of a real composition composes context-independently. Predictive context analysis. We populate the interaction graph empirically, admitting pairs only after measured deviation. Predicting context dependencies from workload structure, without first measuring deviation, would cut characterization cost but requires a physical model of each mechanism. Operating point interpolation. Continuous models 𝑠𝑒 (𝜔) and 𝑑𝑒 (𝜃, 𝜅, 𝜔) that predict signatures at uncharacterized operating points would cut characterization cost but shift uncertainty from measurement to interpolation. The same machinery would support cross-hardware transfer when the target device admits only sparse probes. Energy-aware compilation. Embedding energy calculus into ML compilers, so that code generation optimizes composed energy under latency constraints, would close the loop between characterization and deployment. A type system whose types carry resource budgets (a graded or quantitative type system) would let static analysis track composed energy and uncertainty alongside time complexity. Reach beyond GPUs. TPUs, NPUs, dataflow accelerators, and analog or in-memory compute may have powerstate structures unlike those that motivated the static–dynamic split. Whether energy calculus applies to these domains, and if so how the axioms and mechanisms adapt, remains open. Non-ML computational domains, including signal processing and scientific computing on FPGAs, raise the same questions. Hardware design and architecture exploration. Architecture exploration evaluates design choices against performance targets for a set of workloads, using kernel-level modeling and simulation to predict whether a proposed design will hit those targets once built. As energy becomes a primary bottleneck for ML infrastructure, a design is increasingly likely to carry an energy target alongside its performance target. Energy calculus supplies the composed energy prediction for such a target, since per-kernel signatures characterized on candidate designs compose under the same operators; a design-space sweep then predicts total energy per workload without re-profiling each candidate end to end. Operating-point domains are one such design dimension, as CPUs already scale voltage and frequency per core or per core group [3, 9], which makes per-SM or per-SM-group DVFS on GPUs a design potentially worth building. Energy calculus already provides the generality to explore its gains, since the device-wide versus per-element split of Section 3.1 is hardware-dependent; finer frequency domains then move 𝑓 and 𝑉 from 𝜔dev into 𝜔elem and compose with the same operators, with transition latency, itself hardware-dependent, bounding the granularity. Whether the axioms and mechanisms transfer to pre-silicon models, where signatures come from simulation rather than measurement, is open.

27

8 Related Work 8.1 Energy Measurement and Estimation Hardware instrumentation (NVIDIA NVML, RAPL, vendor APIs) offers direct energy measurement, with known limitations and biases. Software such as Zeus [2], ML.ENERGY [7], and other tools based on NVML [1] provide measurements at varying granularities. These tools share a common gap: they report totals but provide no algebra for reasoning about how parts contribute to the whole. Energy calculus takes their measurements as inputs (characterized signatures) and adds the compositional machinery they lack.

8.2 ML Energy Optimization Zeus [21] tunes batch size and GPU power limit jointly to navigate the time–energy tradeoff during training. Perseus [6] reduces dynamic energy via GPU frequency scaling on off-critical-path computations in pipelineparallel training. Kareus [20] jointly optimizes SM allocation, kernel launch timing, and GPU frequency for execution-aware energy optimization. Many efficiency-focused works further reduce static energy by overlapping computation, communication, and memory operations [22]. Each of these optimizes a slice of the problem without a unifying algebraic framework. Energy calculus provides that framework. Each system’s lever maps onto a signature parameter or composition choice (batch size and power limit into 𝜃 and 𝜔, frequency and SM allocation into 𝜔, scheduling and overlap into the composition structure), so the calculus combines their effects in a single algebraic prediction.

8.3 Performance and Power Modeling Performance and power modeling supplies the inputs that energy calculus composes. Roofline models [19] and operational intensity analysis characterize compute–memory tradeoffs. Analytical and learned GPU performance models predict execution time from workload parameters [13]. Power modeling approaches range from counter-based regressions to detailed microarchitectural models [10]. These predict 𝑇, 𝑑, or 𝑠 in isolation at specific operating points; energy calculus consumes them as signature components and composes them across elements.

8.4 Compositional Reasoning in Systems Network calculus. Network calculus [12] is the closest compositional neighbor. It uses min-plus algebra to derive deterministic bounds on traffic and delay through networks of service elements, with compact parameterized representations (arrival curves, service curves) that compose. Energy calculus pursues the analogous goal for a different physical resource, energy rather than delay, and consequently uses a non-distributive algebra whose sequential operator commutes only conditionally (Property 5.1), rather than min-plus. Context propagation is the deeper structural difference: energy calculus hands physical state from element to element through exit and entry contexts, which has no counterpart in network calculus. Tropical/max-plus algebras. Max-plus (tropical) algebras [4] replace + with max and × with +, which yields formulations of scheduling and critical-path analysis with both operations commutative and addition distributing over maximum. Energy calculus is distinct on both counts: commutativity of sequential composition is conditional rather than unconditional (Property 5.1), and sequential composition does not distribute over parallel (Property 5.4). The static–dynamic decomposition further couples max (on time in same-device parallel composition) with + (on dynamic energy), so the same parallel operation simultaneously uses both max and +, a structure outside the reach of max-plus, which collapses the two operations into one. Category theory. Monoidal categories [15] abstract any system with sequential and parallel composition, so energy calculus fits their shape. The abstraction deliberately leaves open which additional laws hold between the two operators. For energy, measurement answers that question, as sequential composition does not distribute over parallel (Property 5.4) and commutes only conditionally (Property 5.1).

28

9 Conclusion We propose energy calculus, a compositional framework that makes energy a first-class primitive of computational systems. Energy elements carrying measured signatures compose under three operators and an accompanying algebra, grounded in seven axioms about static and dynamic power. Two properties distinguish energy calculus from familiar structures, and both follow from physics rather than algebraic choice. First, sequential composition does not distribute over parallel, because restructuring a schedule duplicates dynamic energy while static energy follows the makespan. Second, sequential composition commutes only conditionally, because context propagates between elements through thermal, cache, and power-delivery state. We also provide a Reduction Theorem that recovers a simple context-independent algebra whenever composed elements are mutually contextinsensitive. Practitioners thus pay the cost of context dependence only where the physics demands it. Energy calculus is borne of years of building energy optimization systems. Our systems Zeus, Perseus, and Kareus each exploited a piece of the algebra without naming it, whether the smooth response of energy to workload parameters and operating points, static power drawn over a schedule’s full makespan, or the static–dynamic decomposition itself. The calculus codifies these observations, so that what each system rediscovered in its own corner is stated once, for all of them. Just as complexity theory and information theory grew from the recognition that time and data admit formal structure, we hope energy calculus is a starting point for an equivalent research direction on energy. This direction spans empirical validation of the axioms, optimization layers built on the algebra, and the design of hardware whose energy behavior is compositional by construction. We expect that arrow to reverse, so that where systems once taught us the algebra piece by piece, the algebra can now tell us which systems to build.

29

A Interaction Mechanism Details This appendix provides detailed characterization protocols for each mechanism in Table 1.

A.1 Thermal Coupling • Mechanism: An element heats the device; elevated temperature increases leakage current (raising static power) and may trigger dynamic thermal throttling (reducing clock frequency, increasing execution time). • Timescale: Thermal time constants of modern GPUs are on the order of seconds, so thermal interactions matter between elements within a few seconds of each other. • Characterization: Measure 𝐸𝑒 at multiple device temperatures, set by varying the duration of a prior thermal load, and fit 𝐸𝑒 (𝜙) as a function of entry temperature. Thermally stable profiling, with cooldown intervals between measurements, isolates this effect.

A.2 Cache and Memory State • Mechanism: Preceding elements populate (warm) or pollute (evict) cache lines that subsequent elements use. Cache warming decreases memory traffic and dynamic energy (negative interaction effect); pollution increases it (positive). • Timescale: Microseconds; a few intervening memory-intensive operations overwrite cache state. • Characterization: Measure 𝐸𝑒 with a cold cache (after a cache-flushing preamble) and with a warm cache (after a representative preceding element runs). The difference is the interaction effect.

A.3 Power Delivery • Mechanism: A sudden change in current draw (e.g., transition between elements with very different power profiles) causes voltage droops in the power delivery network, which may trigger brief frequency reductions or unreliable execution that changes timing. • Timescale: Nanoseconds to microseconds for the electrical transient; the effect on execution may persist for tens of microseconds. • Characterization: Requires high-resolution power measurement; typically visible as a brief execution time anomaly at the boundary between elements.

A.4 Resource Contention • Mechanism: Concurrent elements contend for shared resources, and the contention degrades each element’s performance and energy. On the same device, the contested resources are memory bandwidth, interconnect bandwidth, and shared cache capacity. Across devices, the contested resources are shared fabrics (NVLink, PCIe, or network interconnect) and node- or rack-level power budgets. • Timescale: Instantaneous; contention exists only during concurrent execution. • Characterization: Measure 𝐸𝑒 in isolation and concurrently with a representative interferer; the difference is the contention effect. Same-device contention is characterized through ⊕; cross-device interconnect contention is characterized through ⊕multi with a co-running peer that exercises the shared fabric. Per-element time under co-execution is directly measurable; per-element dynamic energy can only be measured jointly, since device power is shared, so attributing it across the pair requires time-windowed measurement, counter-based apportioning, or regression across varied peers—when attribution is impractical, characterize the pair as a composite.

B Insensitivity Expansion This appendix derives the left-hand side of the history-insensitivity condition (Equation (11)) from Axiom P1. Fix an element 𝑒 at workload parameters 𝜃, implementation 𝜅, and operating point 𝜔, all suppressed below, and

30

let 𝜙, 𝜙′ be two entry contexts. Subtracting Axiom P1’s decomposition at the two contexts and expanding the static-energy product around 𝜙′ : 𝐸𝑒 (𝜙) − 𝐸𝑒 (𝜙′ ) = 𝑠𝑒 (𝜙) 𝑇𝑒 (𝜙) − 𝑠𝑒 (𝜙′ ) 𝑇𝑒 (𝜙′ ) + 𝑑𝑒 (𝜙) − 𝑑𝑒 (𝜙′ ) ( )( ) = 𝑠𝑒 (𝜙′ ) + 𝑠𝑒 (𝜙) − 𝑠𝑒 (𝜙′ ) 𝑇𝑒 (𝜙′ ) + 𝑇𝑒 (𝜙) − 𝑇𝑒 (𝜙′ ) − 𝑠𝑒 (𝜙′ ) 𝑇𝑒 (𝜙′ ) + 𝑑𝑒 (𝜙) − 𝑑𝑒 (𝜙′ ) ( )( ) = 𝑠𝑒 (𝜙′ ) + 𝛿𝑠 𝑇𝑒 (𝜙′ ) + 𝛿𝑇 − 𝑠𝑒 (𝜙′ ) 𝑇𝑒 (𝜙′ ) + 𝛿𝑑 = 𝛿𝑠 𝑇𝑒 (𝜙′ ) + 𝛿𝑇 𝑠𝑒 (𝜙′ ) + 𝛿𝑠 𝛿𝑇 + 𝛿𝑑,

(28)

where 𝛿𝑠 ∶= 𝑠𝑒 (𝜙) − 𝑠𝑒 (𝜙′ ), 𝛿𝑇 ∶= 𝑇𝑒 (𝜙) − 𝑇𝑒 (𝜙′ ), and 𝛿𝑑 ∶= 𝑑𝑒 (𝜙) − 𝑑𝑒 (𝜙′ ) are the signed shifts. Taking magnitudes, with ∆𝑠 = |𝛿𝑠|, ∆𝑇 = |𝛿𝑇|, and ∆𝑑 = |𝛿𝑑| as in Definition 4.1: || | ||𝐸𝑒 (𝜙) − 𝐸𝑒 (𝜙′ )||| ≤ ∆𝑠 𝑇𝑒 (𝜙′ ) + ∆𝑇 𝑠𝑒 (𝜙′ ) + ∆𝑠 ∆𝑇 + ∆𝑑

(29)

by the triangle inequality, with equality when every shift is non-negative. The right-hand side is the left-hand side of Equation (11): the worst-case energy shift the component deviations can produce. Bounding it by 𝑐𝛼 ⋅ 𝜎𝐸𝑒 therefore bounds the total energy difference, and, every term being non-negative, each component’s contribution separately, e.g., ∆𝑇 𝑠𝑒 (𝜙′ ) ≤ 𝑐𝛼 ⋅ 𝜎𝐸𝑒 . The same expansion yields the left-hand side of the interference-insensitivity condition (Equation (12)): replace (𝜙, 𝜙′ ) with the co-run and isolation runs (𝜙, 𝜌) and (𝜙, {𝑒}), at each entry context 𝜙 in the definition’s set, giving the isolation values as the multipliers.

C Reduction Theorem This appendix proves the Reduction Theorem (Proposition 4.1). When two elements are mutually context-insensitive within measurement uncertainty, compositions agree with their context-independent evaluations within the theorem’s bias tolerances.

C.1 Setup Fix operating point 𝜔, workload parameters 𝜃1 , 𝜃2 , and implementations 𝜅1 , 𝜅2 . Let 𝜙0 = 𝜙null be the null context at which signatures are characterized (Axiom M2), and let Φ1 , Φ2 be the sets of entry contexts the composition realizes for elements 1 and 2. Definition 4.5 includes the null context, so 𝜙0 ∈ Φ𝑖 . Write 𝜙𝑐 for the composite’s own entry context, which lies in Φ𝑖 for every element that starts with the composite. The Reduction Theorem (Proposition 4.1) assumes mutual context-insensitivity (Definition 4.5); its history-insensitivity requirement (Definition 4.2) with confidence level (1 − 𝛼) reads: ∆𝑠𝑖 𝑇𝑖 (𝜙0 ) + ∆𝑇𝑖 𝑠𝑖 (𝜙0 ) + ∆𝑠𝑖 ∆𝑇𝑖 + ∆𝑑𝑖 ≤ 𝑐𝛼 ⋅ 𝜎𝐸𝑖

∀𝜙 ∈ Φ𝑖 , 𝑖 ∈ {1, 2},

(30)

where ∆𝑠𝑖 = |𝑠𝑖 (𝜙0 ) − 𝑠𝑖 (𝜙)|, ∆𝑇𝑖 = |𝑇𝑖 (𝜙0 ) − 𝑇𝑖 (𝜙)|, and ∆𝑑𝑖 = |𝑑𝑖 (𝜙0 ) − 𝑑𝑖 (𝜙)|, writing 𝜎𝐸𝑖 for 𝜎𝐸𝑒 . This bounds 𝑖 the perturbation of 𝑠𝑖 , 𝑇𝑖 , and 𝑑𝑖 separately, which is what the proofs below require. It implies the total-energy bound || | ∀𝜙 ∈ Φ𝑖 , 𝑖 ∈ {1, 2} (31) ||𝐸𝑖 (𝜃𝑖 , 𝜅𝑖 , 𝜔, 𝜙) − 𝐸𝑖 (𝜃𝑖 , 𝜅𝑖 , 𝜔, 𝜙0 )||| ≤ 𝑐𝛼 ⋅ 𝜎𝐸𝑖

by the expansion of Appendix B. When measurement uncertainty is dominated by a single component, the two bounds coincide; otherwise the component-wise bound is the stronger condition that the theorem states.

C.2 Sequential Case Proof. The context-dependent sequential composition (Equation (6)) from the composite’s entry context 𝜙𝑐 is 𝐸1 ⊗ 𝐸2 = 𝑠1 (𝜙𝑐 )𝑇1 (𝜙𝑐 ) + 𝑑1 (𝜙𝑐 ) + 𝑠2 (𝜙1 )𝑇2 (𝜙1 ) + 𝑑2 (𝜙1 )

(32)

with 𝜙1 ∈ Φ2 the entry context the second element sees, the exit context of 𝑒1 ’s execution from 𝜙𝑐 ; the composition runs alone, so runtime contexts are singletons and suppressed. The context-independent composition evaluates every value at 𝜙0 : 𝐸1 ⊗(0) 𝐸2 = 𝑠1 (𝜙0 )𝑇1 (𝜙0 ) + 𝑑1 (𝜙0 ) + 𝑠2 (𝜙0 )𝑇2 (𝜙0 ) + 𝑑2 (𝜙0 ). (33) 31

Element 2’s block shifts by at most one tolerance, |𝑠2 (𝜙1 )𝑇2 (𝜙1 ) − 𝑠2 (𝜙0 )𝑇2 (𝜙0 )| + |𝑑2 (𝜙1 ) − 𝑑2 (𝜙0 )| ≤ 𝑐𝛼 ⋅ 𝜎𝐸2 ,

(34)

by Equation (30) applied to 𝑒2 at 𝜙1 ∈ Φ2 , via the expansion of Appendix B. Element 1’s block shifts by at most its own tolerance by the same bound applied at 𝜙𝑐 ∈ Φ1 , giving 𝑚1 = 𝑚2 = 1; when the composition starts at the null context, 𝜙𝑐 = 𝜙0 , element 1’s block is exact, and 𝑚1 = 0.

C.3 Parallel Cases Proof. Under ⊕ and ⊕multi , both elements start at the composite’s entry context 𝜙𝑐 and share the runtime context, so two substitutions arise: entry-state substitution (evaluating at 𝜙0 rather than 𝜙𝑐 ) and isolation substitution (evaluating each element in isolation rather than at the composition’s shared runtime context). Mutual historyinsensitivity (Equation (30)) bounds the first and mutual interference-insensitivity (Definition 4.4) the second, each perturbing an element’s static power, time, and dynamic energy by at most one tolerance. Superscript (0) marks null-context isolation values; unmarked values are realized ones. (0) (0) Under ⊕, the composite is 𝑠⋅max(𝑇1 , 𝑇2 )+𝑑1 +𝑑2 , and its shift is at most ∆𝑠⋅max(𝑇1 , 𝑇2 )+𝑠(0) |∆ max(𝑇1 , 𝑇2 )|+ ∆𝑑1 + ∆𝑑2 . The first term is the longer element’s ∆𝑠 summand, the second at most the shifted element’s ∆𝑇 summand (|∆ max | ≤ max 𝑖 |∆𝑇𝑖 |), so each element contributes at most one tolerance per substitution: 𝑚1 = 𝑚2 = 2, dropping to one each when the composition starts at the null context and the entry-state substitution is unneeded. Under ⊕multi , the durations are equal, the composite is 𝑠1 𝑇1 + 𝑑1 + 𝑠2 𝑇2 + 𝑑2 , and each element’s block carries at most one tolerance per substitution exactly as under ⊕.

C.4 Tightness and Breakdown The bound is tight when both elements are maximally sensitive within the admitted uncertainty envelope; in practice the deviation is smaller. Thermal example. Static power depends on device temperature 𝑇dev through leakage current, which rises with temperature. Across the operating range of typical GPU workloads (∼50–85◦ C for an A100 under sustained load), the dependence is well approximated by the linear form ( ) 𝑠(𝑇dev ) ≈ 𝑠0 ⋅ 1 + 𝛽(𝑇dev − 𝑇ref ) , (35) where 𝑇ref is the reference temperature at which we measured 𝑠0 and 𝛽 is a device-specific leakage coefficient on the order of 0.5–1% per ◦ C for current-generation datacenter GPUs. Elements that run in a narrow thermal band (e.g., within a few ◦ C of 𝑇ref ) perturb 𝑠 by less than typical measurement uncertainty across Φ1 , Φ2 , so the Reduction Theorem applies. Elements that span a wide thermal range (e.g., a cold-start kernel followed by a sustained compute burst spanning 20–30◦ C, producing a 10–30% swing in static power) violate the bound and require 𝜙-parameterized characterization.

D Bias Accumulation The Reduction Theorem’s pairwise bounds (Equation (13)) add over composition, one term per element. For a shared-device chain 𝑒1 ⊗ ⋯ ⊗ 𝑒𝑛 run alone from the null context, with every element history-insensitive over the entry contexts the chain realizes together with the null context, applying the sequential case of Appendix C to each element in turn gives 𝑛 ∑ || (0) || ≤ 𝐸 − 𝐸 𝑐𝛼 𝜎𝐸𝑖 , (36) || 𝑒1 ⊗⋯⊗𝑒𝑛 || 𝑖=2

where 𝐸 (0) is the context-independent value; element 1 executes at 𝜙0 and contributes no term. Parallel operands contribute their operator’s multiplied tolerances (Equation (13)). Multipliers do not compound: composing a composite with a further element adds the new element’s multiplied tolerance and leaves the accumulated bias untouched, so the total is a sum over elements, not a product over levels. 32

The composition (𝑒1 ⊗ 𝜄) ⊕multi 𝑒2 , with 𝜄 the idle element restoring equal durations (Section 3.3.3), is the accumulation’s canonical instance beyond chains. Superscript (0) marks null-context isolation values. Write 𝜙𝜄 for the idle element’s entry context, the exit context of 𝑒1 ’s execution; Equations (6) and (8) give the two elements’ terms plus the idle energy 𝑠1 (𝜙𝜄 , {𝑒2 }) (𝑇2 −𝑇1 ). Device 1 is held for the makespan whatever 𝑇1 is, so its static energy (0) (0) forms one ledger: with 𝛿𝑎 = 𝑠1 (𝜙0 , 𝜌) − 𝑠1 and 𝛿𝜄 = 𝑠1 (𝜙𝜄 , {𝑒2 }) − 𝑠1 the draw deviations during 𝑒1 ’s execution and during the idle window, (0)

𝑠1 (𝜙0 , 𝜌) 𝑇1 + 𝑠1 (𝜙𝜄 , {𝑒2 }) (𝑇2 − 𝑇1 ) = 𝑠1 𝑇2 + 𝛿𝑎 𝑇1 + 𝛿𝜄 (𝑇2 − 𝑇1 ),

(37)

and 𝑇1 survives only against the deviations: a 𝑇1 shift moves the boundary between two draws that already agree within tolerance, a second-order effect. Subtracting the context-independent value 𝐸 (0) from the composition’s energy 𝐸 and collecting the first-order terms, ) ( |||𝐸 − 𝐸 (0) ||| ≤ |𝛿𝑎 | 𝑇 (0) + |∆𝑑1 | + |||𝑠2 𝑇2 + 𝑑2 − 𝑠(0) 𝑇 (0) − 𝑑(0) ||| + 𝑠(0) |∆𝑇2 | + |𝛿𝜄 | ⋅ 𝑇 (0) − 𝑇 (0) . (38) 1 2 1 2 2 2 | 1 | | | The first two terms are 𝑒1 ’s ∆𝑠 and ∆𝑑 summands, at most one tolerance per substitution, contributing 2𝑐𝛼 𝜎𝐸1 . (0)

(0)

(0)

Element 2’s block is at most 2𝑐𝛼 𝜎𝐸2 by the expansion of Appendix B, and 𝑠1 |∆𝑇2 | ≤ (𝑠1 ∕𝑠2 ) ⋅ 2𝑐𝛼 𝜎𝐸2 , since device 1 keeps drawing while 𝑇2 stretches. The idle element’s own conditions (Definitions 4.1 and 4.3) bound the last term: its duration is schedule-set and its dynamic energy zero, so Equations (11) and (12) reduce to their ∆𝑠 (0) (0) (0) 2 terms and give |𝛿𝜄 | ⋅ (𝑇2 − 𝑇1 ) ≤ 2𝑐𝛼 𝜎𝐸𝜄 across the entry and isolation substitutions, with 𝜎𝐸2 = 𝑠1 (𝜎𝑇2 + 𝜎𝑇2 ) 𝜄 1 2 inherited from the independent durations that set the gap (Section 3.3). The composition therefore accumulates, to first order, 2 𝑐𝛼 𝜎𝐸1 + 2 (1 + 𝑠1 ∕𝑠2 ) 𝑐𝛼 𝜎𝐸2 + 2 𝑐𝛼 𝜎𝐸𝜄 at null-context values: the idle element contributes twice its own tolerance, and 𝑒2 , whose time gates the idle window, carries the idle device’s draw as the power ratio. Products of deviations with time shifts are second order and dropped, as is a realized ordering flip, possible only when the null-context idle window is itself within time noise. √ The bias grows linearly in 𝑛 while propagated uncertainty grows as 𝑛: on a shared device with independent √ √∑ 2 ∑ ∑ errors, 𝜎2 (0) = 𝑖 𝜎𝐸2 (Equation (20)), and by Cauchy–Schwarz 𝑖 𝜎𝐸𝑖 ≤ 𝑛 ⋅ 𝜎 , with equality at equal 𝑖 𝐸 𝐸

𝑖

𝑖

variances. The reported interval therefore does not cover the worst-case accumulated bias at depth; an interval that does must add the accumulated bias bound to the noise quantile, 𝑛

∑ | || 𝑐𝛼 𝜎𝐸𝑖 + 𝑐𝛼 𝜎𝐸 (0) ||𝐸 − 𝐸 (0) ||| ≤ 𝑖=2

(39)

at confidence (1 − 𝛼), with 𝐸 the physical energy of the chain. Attaining the linear worst case requires per-element deviations of aligned sign. Deviations that are independent and zero-mean across elements add in quadrature and are absorbed by the propagated interval; aligned signs mean systematic context drift, and sustained drift moves entry contexts out of their characterized sets, so the regime that realizes the worst case is also the regime the applicability condition (Section 4.4) excludes and deviation detection (Equation (23)) flags at composite granularity. Finally, the idle window’s power ratio mirrors the amplification that propagated variance itself carries (the 𝑠1 + 𝑠2 weight in Equation (22)), so measured in multiples of the composite’s own propagated deviation, each element’s bias contribution stays 𝑂(1) regardless of the participating devices’ static powers. Depth, not device configuration, is what loosens the guarantee, with idle windows contributing like elements, at their own tolerances.

E Energy Calculus Algebraic Property Proofs We provide full proofs for the algebraic properties stated in Section 5.1.

E.1 Commutativity (Property 5.1) Proof. We prove the parallel case first, then the sequential case. Same-device parallel (⊕): 𝐸1 ⊕ 𝐸2 = 𝑠 ⋅ max(𝑇1 , 𝑇2 ) + 𝑑1 + 𝑑2 = 𝑠 ⋅ max(𝑇2 , 𝑇1 ) + 𝑑2 + 𝑑1 = 𝐸2 ⊕ 𝐸1 by commutativity of max and addition. Both elements evaluate at the shared entry context 𝜙0 and the shared 33

runtime context 𝜌 = {𝑒1 , 𝑒2 }, both symmetric in the two elements, so no label-dependent term arises. Hence parallel commutativity holds unconditionally. Cross-device parallel (⊕multi ): 𝐸1 ⊕multi 𝐸2 = 𝑠1 𝑇1 +𝑑1 +𝑠2 𝑇2 +𝑑2 = 𝐸2 ⊕multi 𝐸1 by commutativity of addition, the expression being symmetric in the two elements, with the same shared-𝜙0 argument. Sequential (⊗): Let 𝜙0 be the entry context of the composite; the composition runs alone, so runtime contexts are singletons and suppressed. Then 𝐸1 ⊗ 𝐸2 = 𝑠1 (𝜙0 )𝑇1 (𝜙0 ) + 𝑑1 (𝜙0 ) + 𝑠2 (𝜙1 )𝑇2 (𝜙1 ) + 𝑑2 (𝜙1 )

(40)

where 𝜙1 is the exit context of 𝑒1 ’s execution from 𝜙0 , and similarly 𝐸2 ⊗ 𝐸1 = 𝑠2 (𝜙0 )𝑇2 (𝜙0 ) + 𝑑2 (𝜙0 ) + 𝑠1 (𝜙2 )𝑇1 (𝜙2 ) + 𝑑1 (𝜙2 )

(41)

with 𝜙2 the exit context of 𝑒2 ’s execution from 𝜙0 . In general 𝜙1 ≠ 𝜙2 , and the two sums differ; the thermal example preceding Property 5.1 provides an explicit instance. Equality between orderings can also hold outside the context-insensitive case when the context-dependent perturbations of 𝑒1 and 𝑒2 cancel. Proof of Corollary 5.1. Assume 𝑒1 and 𝑒2 are mutually context-insensitive under both orderings (Definition 4.5), with the composition starting at the null context (𝜙0 = 𝜙null ): each element’s history set contains 𝜙0 , seen when it runs first, and the context the other produces, seen when it runs second. By Definition 4.1, substituting 𝜙0 for 𝜙1 (respectively 𝜙2 ) perturbs each element’s total contribution by at most 𝑐𝛼 ⋅ 𝜎𝐸𝑖 . Substituting 𝜙0 for 𝜙1 and 𝜙2 in both expressions reduces both orderings to the same context-independent value, 𝐸1 ⊗(0) 𝐸2 = 𝑠1 (𝜙0 )𝑇1 (𝜙0 ) + 𝑠2 (𝜙0 )𝑇2 (𝜙0 ) + 𝑑1 (𝜙0 ) + 𝑑2 (𝜙0 ) = 𝐸2 ⊗(0) 𝐸1 ,

(42)

so the reduced evaluation is exactly commutative. The physical orderings are each within one element’s tolerance of this common value (𝑒2 ’s in the order 𝑒1 ⊗𝑒2 , 𝑒1 ’s in the other), so |𝐸1 ⊗𝐸2 −𝐸2 ⊗𝐸1 | ≤ 𝑐𝛼 (𝜎𝐸1 +𝜎𝐸2 ), establishing the corollary.

E.2 Associativity (Property 5.2) ) ∑3 ( Proof. Sequential (⊗): (𝐸1 ⊗𝐸2 )⊗𝐸3 = 𝑖=1 𝑠𝑖 (𝜙𝑖−1 )𝑇𝑖 (𝜙𝑖−1 )+𝑑𝑖 (𝜙𝑖−1 ) where 𝜙0 is the composite entry context and 𝜙𝑖 the exit context of 𝑒𝑖 ’s execution from 𝜙𝑖−1 , with the composition running alone so that runtime contexts are singletons and suppressed. The same sum arises from 𝐸1 ⊗ (𝐸2 ⊗ 𝐸3 ) for two reasons: (i) context propagation follows execution order, which grouping does not change, so the context entering 𝑒3 in the grouping (12)3 equals the context entering 𝑒3 in 1(23); and (ii) total energy is a sum of per-element contributions that depend only on each element’s individual entry context, with no grouping-dependent term. Both reductions therefore produce the same ordered sequence of context arguments and the same total energy. Same-device parallel (⊕): All three elements co-start and co-run under either grouping, so every value evaluates at the shared entry context 𝜙0 and the same runtime context 𝜌, and (𝐸1 ⊕ 𝐸2 ) ⊕ 𝐸3 = 𝑠 ⋅ max(𝑇1 , 𝑇2 , 𝑇3 ) + 𝑑1 + 𝑑2 + 𝑑3 = 𝐸1 ⊕ (𝐸2 ⊕ 𝐸3 ) by associativity of max and addition. Cross-device parallel (⊕multi ): Likewise with every value at the shared entry context and runtime context, and all durations equal by the operator’s requirement, (𝐸1 ⊕multi 𝐸2 ) ⊕multi 𝐸3 = (𝑠1 + 𝑠2 + 𝑠3 ) ⋅ 𝑇1 + 𝑑1 + 𝑑2 + 𝑑3 = 𝐸1 ⊕multi (𝐸2 ⊕multi 𝐸3 ) by associativity of +.

E.3 Closure (Property 5.3) Proof. For each operator, we exhibit composite components (𝑠′ , 𝑇 ′ , 𝑑′ ) that are non-negative, satisfy Axiom P1 (𝐸 ′ = 𝑠′ ⋅ 𝑇 ′ + 𝑑′ ), and carry the context bookkeeping the composite needs to participate in further compositions. Sequential (⊗): With every value evaluated as in Equation (6), 𝑇 ′ = 𝑇1 (𝜙0 , 𝜌1 ) + 𝑇2 (𝜙1 , 𝜌2 ),

𝑑′ = 𝑑1 (𝜙0 , 𝜌1 ) + 𝑑2 (𝜙1 , 𝜌2 ),

(43)

𝑠1 (𝜙0 , 𝜌1 ) 𝑇1 (𝜙0 , 𝜌1 ) + 𝑠2 (𝜙1 , 𝜌2 ) 𝑇2 (𝜙1 , 𝜌2 ) 𝐸 ′ − 𝑑′ = , 𝑇′ 𝑇1 (𝜙0 , 𝜌1 ) + 𝑇2 (𝜙1 , 𝜌2 )

(44)

and Axiom P1 then fixes the static power to 𝑠′ =

34

the time-averaged static power, reducing to the device’s single 𝑠 when both elements draw it. Given 𝑇 ′ as the physical makespan and 𝑑′ as the summed dynamic energy, this is the unique decomposition preserving total static energy 𝑠′ ⋅ 𝑇 ′ and total dynamic energy 𝑑′ . The summary 𝑠′ is a derived quantity, computed once from the operands’ signature values; when 𝑠1 ≠ 𝑠2 , it varies with the operands’ durations and hence with their workload parameters, unlike the baseline draw of a device (Axiom P1). Every operator consumes an operand’s static power only as static energy, so the summary stays exact in further composition: ⊗ multiplies 𝑠′ by the composite’s own duration 𝑇 ′ ; ⊕multi requires equal durations, so its makespan window equals 𝑇 ′ ; and ⊕ requires its operands to run on one device at a shared device-wide operating point, drawing a single 𝑠. Same-device parallel (⊕): With both elements evaluated at the shared (𝜙0 , 𝜌) of Equation (7), ( ) 𝑠′ = 𝑠(𝜙0 , 𝜌), 𝑇 ′ = max 𝑇1 (𝜙0 , 𝜌), 𝑇2 (𝜙0 , 𝜌) , 𝑑′ = 𝑑1 (𝜙0 , 𝜌) + 𝑑2 (𝜙0 , 𝜌), (45) where 𝑠 is the device’s static power (Axiom P2), and 𝑠′ ⋅ 𝑇 ′ + 𝑑′ is Equation (7) itself. Cross-device parallel (⊕multi ): With both elements evaluated at the shared (𝜙0 , 𝜌) of Equation (8) and durations equal by the operator’s requirement, 𝑠′ = 𝑠1 (𝜙0 , 𝜌) + 𝑠2 (𝜙0 , 𝜌),

𝑇 ′ = 𝑇1 (𝜙0 , 𝜌) = 𝑇2 (𝜙0 , 𝜌),

𝑑′ = 𝑑1 (𝜙0 , 𝜌) + 𝑑2 (𝜙0 , 𝜌),

(46)

and 𝑠′ ⋅ 𝑇 ′ + 𝑑′ is Equation (8) itself; the composite’s device set is the union 𝒟𝑒1 ∪ 𝒟𝑒2 . In all cases 𝑠′ , 𝑇 ′ , 𝑑′ ≥ 0, since each combines non-negative values by addition, maximum, and time-averaging. The composite’s entry context is that of its first element (sequential) or of its shared start (parallel), tracked per participating device; its exit context is the state its internal dynamics leave behind; its runtime context tracks the composite’s internal timing, with peers entering with the windows they overlap, so each constituent’s 𝜌𝑖 is recovered by interval overlap against the composite’s internal boundaries. The composite’s uncertainty is likewise carried directly; its energy variance is the propagated 𝜎𝐸2 ′ of Property 5.6, alongside the duration variance the operator’s time accounting yields (e.g., 𝜎𝑇2 ′ = 𝜎𝑇2 + 𝜎𝑇2 under ⊗ with independent errors). Where that prop1 2 erty’s independence assumptions fail, the covariance form (Equation (47)) or direct measurement of the coupled composite supplies the energy variance (Section 5.2). When the operands draw one shared static power, the composite has a constant baseline and Equation (5) applies to it like an element measured directly. When their static powers differ, it does not: subtracting 𝑠′2 𝜎𝑇2 ′ from 𝜎𝐸2 ′ would weight every operand’s time noise by the average 𝑠′ , whereas each operand’s time noise converts into energy noise through that operand’s own static power. Further composition consumes the carried variances the same way it consumes a measured element’s; under ⊗ with independent errors, the operands’ energy variances add (Appendix F.1). The result extends to arbitrary compositions by induction on composition depth, each level composing the previous level’s components by the same rules.

E.4 Distributivity (Property 5.4) Proof. Same device (⊕): Expand both sides under 𝐸𝑋 ⊕ 𝐸𝑌 = 𝑠 ⋅ max(𝑇𝑋 , 𝑇𝑌 ) + 𝑑𝑋 + 𝑑𝑌 , with all signatures evaluated at the null context and elements sharing the device’s static power 𝑠. The left-hand side composes 𝑒1 sequentially with the parallel pair (𝑒2 , 𝑒3 ): 𝐸1 ⊗ (𝐸2 ⊕ 𝐸3 ) = 𝑠(𝑇1 + max(𝑇2 , 𝑇3 )) + 𝑑1 + 𝑑2 + 𝑑3 . The right-hand side composes 𝑒1 sequentially with each of 𝑒2 and 𝑒3 before the parallel join: (𝐸1 ⊗ 𝐸2 ) ⊕ (𝐸1 ⊗ 𝐸3 ) = 𝑠 ⋅ max(𝑇1 + 𝑇2 , 𝑇1 + 𝑇3 ) + 2𝑑1 + 𝑑2 + 𝑑3 . Since max(𝑇1 + 𝑇2 , 𝑇1 + 𝑇3 ) = 𝑇1 + max(𝑇2 , 𝑇3 ), the static terms coincide, and the two sides differ by exactly 𝑑1 , the dynamic energy of the duplicated execution of 𝑒1 ; whenever 𝑑1 > 0, the equality fails. Cross device (⊕multi ): Place 𝑒2 on device 𝛽 and 𝑒3 on device 𝛾, with 𝑇2 = 𝑇3 per ⊕multi ’s equal-duration requirement. For the left-hand side, one copy of 𝑒1 runs on 𝛽 while 𝛾 hosts an idle element, so both devices draw static power for the full makespan: ( ) 𝐸1 ⊗ (𝐸2 ⊕multi 𝐸3 ) = (𝑠𝛽 + 𝑠𝛾 ) 𝑇1 + 𝑇2 + 𝑑1 + 𝑑2 + 𝑑3 . 35

On the right-hand side both branches contain 𝑒1 , and ⊕multi places the branches on different devices, so the expression is well-typed only under replication, a device-indexed copy of 𝑒1 executing on each device; with the copies sharing (𝑇1 , 𝑑1 ) on identical devices, ) ( (𝐸1 ⊗ 𝐸2 ) ⊕multi (𝐸1 ⊗ 𝐸3 ) = (𝑠𝛽 + 𝑠𝛾 ) 𝑇1 + 𝑇2 + 2𝑑1 + 𝑑2 + 𝑑3 , and the two sides again differ by exactly 𝑑1 , the dynamic energy of the additional copy. On heterogeneous devices, the copies’ signatures differ, and the gap is the additional copy’s own dynamic energy.

E.5 Monotonicity (Property 5.5) Proof. Let 𝑒1 ⊗ 𝑒2 run alone from entry context 𝜙0 , with 𝜙1 the exit context of 𝑒1 ’s execution. Take 𝑒1′ matching 𝑒1 ’s static power and execution time but consuming 𝛿 > 0 more dynamic energy, whose exit context 𝜙1′ lowers the successor’s energy by more: 𝐸2 (𝜙1′ ) ≤ 𝐸2 (𝜙1 ) − 2𝛿, e.g., through a more cache-friendly output layout. Replacing 𝑒1 with the component-wise no-smaller 𝑒1′ then decreases the total: (𝐸1 + 𝛿) + 𝐸2 (𝜙1′ ) ≤ 𝐸1 + 𝐸2 (𝜙1 ) − 𝛿. Proof of Corollary 5.2. In the context-independent form (Section 4.3), signature values are fixed point values across the substitution, independent of the contexts the composition produces. Replacing means swapping 𝑒𝑖 ’s signature alone, with the schedule still feasible, shared operating parameters fixed, and every other signature unchanged; a replacement that changes the shared device-wide operating point is treated separately below. We show that if element 𝑒𝑖′ has 𝑠𝑖′ ≥ 𝑠𝑖 , 𝑇𝑖′ ≥ 𝑇𝑖 , and 𝑑𝑖′ ≥ 𝑑𝑖 , then replacing 𝑒𝑖 with 𝑒𝑖′ in any composition weakly increases total energy. Sequential (⊗): 𝐸(𝑒1′ , 𝑒2 ) = 𝑠1′ 𝑇1′ + 𝑠2 𝑇2 + 𝑑1′ + 𝑑2 ≥ 𝑠1 𝑇1 + 𝑠2 𝑇2 + 𝑑1 + 𝑑2 because 𝑠1′ 𝑇1′ ≥ 𝑠1 𝑇1 (product of non-negative numbers, both factors weakly larger) and 𝑑1′ ≥ 𝑑1 . Same-device parallel (⊕): 𝐸(𝑒1′ , 𝑒2 ) = 𝑠 ⋅ max(𝑇1′ , 𝑇2 ) + 𝑑1′ + 𝑑2 ≥ 𝑠 ⋅ max(𝑇1 , 𝑇2 ) + 𝑑1 + 𝑑2 because max is monotone in each argument. A replacement that raises the shared operating state also raises 𝑠 for the whole composite, which again weakly increases the total. Cross-device parallel (⊕multi ): 𝐸(𝑒1′ , 𝑒2 ) = (𝑠1′ + 𝑠2 ) ⋅ max(𝑇1′ , 𝑇2 ) + 𝑑1′ + 𝑑2 , with an idle element at its device’s draw restoring equal durations on the shorter side; the static-energy term is weakly larger because it is a product of weakly larger non-negative factors. The result extends to arbitrary compositions by induction on composition depth: an enclosing composition consumes a sub-composite only through its duration, dynamic energy, and total energy, each of which the replacement weakly increases.

F Variance Propagation Details This appendix develops the variance propagation results summarized in Section 5.2. Throughout, operands are elements measured directly or constant-baseline composites, so per Axiom M1, static powers, including those of idling devices, are exact and each element’s time and dynamic-energy errors are uncorrelated.

F.1 Sequential Composition Under ⊗, total energy is the sum of the operands’ energies, so the variance of the sum yields ( ) 𝜎𝐸2 ⊗𝐸 = 𝜎𝐸2 + 𝜎𝐸2 + 2 Cov 𝐸1 , 𝐸2 , 1

2

1

2

(47)

which reduces under independent errors to Equation (20); for operands within Equation (5)’s scope, each term expands as 𝜎𝐸2 = 𝑠𝑖2 𝜎𝑇2 + 𝜎𝑑2 , with 𝑠𝑖 the device’s draw at element 𝑖’s operating state. 𝑖

𝑖

𝑖

F.2 Parallel Composition Under ⊕, 𝐸12 = 𝑠 ⋅ max(𝑇1 , 𝑇2 ) + 𝑑1 + 𝑑2 . Writing 𝜎𝐸2 = 𝑠2 Var(𝑇𝑖 ) + Var(𝑑𝑖 ) for each element and expanding 𝑖 Var(𝐸12 ) under measurement errors independent between the two elements replaces the per-element 𝑠2 Var(𝑇𝑖 ) terms with 𝑠2 Var(max(𝑇1 , 𝑇2 )): ( ) ( ) 𝜎𝐸2 ⊕𝐸 = 𝜎𝐸2 + 𝜎𝐸2 + 𝑠2 ⋅ Var max(𝑇1 , 𝑇2 ) − 𝑠2 ⋅ Var(𝑇1 ) + Var(𝑇2 ) + 2𝑠 ⋅ 𝐶max , (48) 1

2

1

2

36

where 𝐶max is the covariance between max(𝑇1 , 𝑇2 ) and 𝑑1 + 𝑑2 ; when the times (𝑇1 , 𝑇2 ) are jointly independent of the dynamic energies (𝑑1 , 𝑑2 ), 𝐶max = 0, and Equation (48) reduces to Property 5.6’s form. Under ⊕multi , the same expansion gives 𝜎𝐸2 ⊕ 𝐸 = 𝜎𝐸2 + 𝜎𝐸2 + (𝑠1 + 𝑠2 )2 Var(max(𝑇1 , 𝑇2 )) − 𝑠12 Var(𝑇1 ) − 1

1

multi 2

2

𝑠22 Var(𝑇2 )+2 (𝑠1 +𝑠2 ) 𝐶max : the makespan term carries the combined weight (𝑠1 +𝑠2 )2 , while each subtracted perelement term keeps its own 𝑠𝑖2 . The cross-device form takes each held device to keep drawing its active static power through the makespan. The exact expression involves the distribution of max(𝑇1 , 𝑇2 ), which depends on the marginal distributions of 𝑇1 and 𝑇2 . For known distributions (e.g., Gaussian execution times), we can compute Var(max(𝑇1 , 𝑇2 )) analytically or via simulation. When the measurement noise on 𝐸1 and 𝐸2 is correlated (e.g., shared instrumentation, shared thermal history), an additional 2 Cov(𝐸1 , 𝐸2 ) term enters the right-hand side, which matches the sequential covariance form (Equation (47)).

F.3 Closed Forms and Limits for the Makespan Variance Two cases of Var(max(𝑇1 , 𝑇2 )) admit a quick treatment. First, when 𝑇1 and 𝑇2 are independent Gaussian with means 𝜇𝑖 and variances 𝜎𝑇2 , Var(max(𝑇1 , 𝑇2 )) has a known closed form in terms of the standard normal CDF 𝑖 and PDF. Second, when the runtimes are well separated, |𝜇1 − 𝜇2 | ≫ 𝜎𝑇1 + 𝜎𝑇2 , the longer element dominates the maximum and Var(max(𝑇1 , 𝑇2 )) ≈ 𝜎𝑇2 ⋆ where 𝑖 ⋆ = arg max 𝑖 𝜇𝑖 . Under ⊕, the parallel variance in this 𝑖

regime simplifies to 𝜎𝐸2 ⋆ + 𝜎𝑑2 , where 𝑗 is the index of the shorter element: the longer element’s energy variance 𝑖

𝑗

is propagated in full, and only the shorter element’s dynamic-energy uncertainty contributes. Under ⊕multi , the makespan fluctuation holds both devices, so the regime instead gives (𝑠1 + 𝑠2 )2 𝜎𝑇2 ⋆ + 𝜎𝑑2 ⋆ + 𝜎𝑑2 . This is the 𝑖

𝑖

𝑗

common regime in pipeline-parallel training and in compute-overlapping-communication patterns, where one path is reliably longer than the other.

F.4 Distributional Treatment If full distributions (not just mean and variance) are available, we compute the composition via convolution (for sums under sequential composition) or order statistics (for max under parallel composition), both exact for independent components; dependent components require their joint distribution. This yields the exact composed distribution, from which we can extract any quantile. The mean-and-variance treatment in the main text is the default; the distributional treatment is a refinement for cases where tail behavior matters (e.g., worst-case energy bounds for safety-critical systems).

G Refinement–Coarsening Consistency Property G.1 (Refinement–Coarsening Consistency, full statement). Let element 𝑒 have directly measured reduced signature 𝑆𝑒 = (𝑒, 𝜃, 𝜅, 𝜔, 𝜙null , 𝑠𝑒 , 𝑇𝑒 , 𝑑𝑒 , 𝜎𝑇2 , 𝜎𝐸2 , 𝑀) (Proposition 4.1). Let 𝑒 be refined into sub-elements 𝑒 𝑒 ̂ ̂ 𝑑, ̂ 𝑇, 𝑒1 , … , 𝑒𝑛 composed via operators op , … , op , yielding a composed reduced signature 𝑆̂𝑒 with components (𝑠, 1

𝑛−1

𝜎̂ 𝑇2 , 𝜎̂ 𝐸2 , 𝑀 ′ ). Then, assuming mutual context-insensitivity within uncertainty: |𝐸𝑒 − 𝐸̂ 𝑒 | ≤

∑ 𝑖

𝑚𝑖 𝑐𝛼 𝜎𝐸𝑒 + 𝑐𝛼 ⋅ 𝑖

√ 𝜎𝐸2 + 𝜎̂ 𝐸2 𝑒

(49)

at confidence level (1 − 𝛼), with the bias term dropping to zero when each 𝑒𝑖 ’s signature is instead correctly characterized at every entry and runtime context the refinement realizes. Proof sketch. 𝐸𝑒 and 𝐸̂ 𝑒 are two estimates of the same physical quantity. The direct ∑estimate is unbiased up to measurement error; the composed estimate carries the reduction bias, bounded by 𝑖 𝑚𝑖 𝑐𝛼 𝜎𝐸𝑒 (Appendix D) under 𝑖 mutual context-insensitivity, and zero under correct characterization at every realized context. After subtracting that bias, the difference is a zero-mean random variable with variance bounded by 𝜎𝐸2 + 𝜎̂ 𝐸2 when the two esti𝑒 mates share no measurements; shared measurements add a covariance term. The Gaussian approximation with 𝑐𝛼 the two-sided Gaussian multiplier, consistent with Definition 4.1, then √ yields the stated bound; it also holds distribution-free via Chebyshev’s inequality at the cost of a larger 𝑐𝛼 = 1∕ 𝛼. A violation of this bound indicates 37

an incorrect measurement, an element refinement that omits a material interaction (mutual context-sensitivity not absorbed by characterization), or both. Refinement and coarsening are inverses in the following sense. Refinement decomposes 𝑒 into sub-elements and produces 𝑆̂𝑒 ; coarsening takes a collection of composed sub-elements and produces a composite signature. Iterated refinement followed by coarsening at the same granularity yields a signature that agrees with the original within propagated uncertainty, by the same argument.

H Frontier Composition Under Context-Independence This appendix proves the frontier composition results of Section 6. Fix workload parameters 𝜃1 , 𝜃2 and entry context 𝜙0 , and let each element 𝑒𝑖 carry its implementations 𝜅, operating set Ω𝑒𝑖 , and time–energy map per Section 6.1. Both subsections assume mutual context-insensitivity at every choice of implementations and operating points (Definition 4.5), and the Reduction Theorem (Proposition 4.1) evaluates signatures at 𝜙0 throughout. All frontier identities are therefore exact in the model; physically, every swept composite point carries its propagated uncertainty interval, and a point is discarded as dominated only when intervals separate, per the comparison rule of Section 5.2. Same-device parallel sweeps are constrained to pairs sharing the device-wide components 𝜔dev (Section 3.3); per-element components and implementations vary freely. We assume Pareto-minimal points are attained, e.g., the swept sets finite or compact with continuous time–energy maps.

H.1 Sequential Frontier Composition This subsection proves Property 6.1. Proof of Property 6.1. Under ⊗, durations add and 𝐸𝑒1 ⊗𝑒2 = 𝐸1 (𝜅1 , 𝜔1 ) + 𝐸2 (𝜅2 , 𝜔2 ), with each element’s values independent of the other’s choice by mutual context-insensitivity, so each choice of implementations and operating points lands at the coordinate-wise sum of the two elements’ swept points. The standard domination argument applies: if an element’s point lies off ℱ𝑒𝑖 , replacing it with a dominating point improves the composite in at least one coordinate and worsens neither, contradicting Pareto-minimality; hence Pareto-minimal composite points arise from points of ℱ𝑒1 and ℱ𝑒2 , and the composite’s achievable set is ℱ𝑒1 ⊞ ℱ𝑒2 up to discarding ( ) Pareto-dominated points. Discarding them yields ℱ𝑒1 ⊗𝑒2 = Pareto-min ℱ𝑒1 ⊞ ℱ𝑒2 . Associativity of frontier composition under ⊗ follows from associativity of ⊞, with Pareto-dominated points discarded early or late to the same effect; the result extends to any finite number of mutually context-insensitive elements by induction.

H.2 Parallel Frontier Coupling Under both parallel operators the two frontiers couple through the shared makespan 𝑇max = max(𝑇1 , 𝑇2 ). Samedevice composition draws the device’s static power once (Axiom P2), so, at each pair of implementations, 𝐸𝑒1 ⊕𝑒2 (𝜔1 , 𝜔2 ) = 𝑠(𝜔dev ) ⋅ 𝑇max + 𝑑1 (𝜔1 ) + 𝑑2 (𝜔2 ),

𝜔1 , 𝜔2 sharing 𝜔dev ;

(50)

across devices, ⊕multi requires equal durations, so an idle element pads the earlier-finishing device (Section 3.3.3); the same ( makespan rule ) follows with each device drawing its own static power and no shared-𝜔dev constraint, 𝐸 = 𝑠1 (𝜔1 ) + 𝑠2 (𝜔2 ) 𝑇max + 𝑑1 (𝜔1 ) + 𝑑2 (𝜔2 ), taking each device’s idle draw 𝑠̄𝑖 , its static power in the ready state it idles in, equal to the active draw (𝑠̄𝑖 = 𝑠𝑖 ); the slack proof below keeps the two draws distinct. In both cases the composite frontier is obtained by sweeping the elements’ implementations and operating points and keeping the Pareto-optimal points; the shared makespan couples the two sweeps, so unlike the sequential case the composition is not a Minkowski sum. Proof of Property 6.2. On a shared device, the composite is 𝑠 ⋅ 𝑇max + 𝑑1 + 𝑑2 with 𝑠 the device’s static power (Axiom P2); the move leaves the device-wide operating point, hence 𝑠 and 𝑒2 ’s signature, unchanged, and the makespan unchanged since 𝑇1′ ≤ 𝑇max , so ∆𝐸 = 𝑑1′ − 𝑑1 ≤ 0 by condition (i). On separate devices, per the accounting of Section 3.3, each device draws its element’s static power over the element’s duration and 𝑠̄𝑖 through 38

its idle element over the remainder of the makespan; the idle element’s operating point is schedule-chosen, so the move leaves 𝑠̄𝑖 unchanged. This regroups as 𝐸 = 𝐸̃ 1 + 𝐸̃ 2 + (𝑠̄1 + 𝑠̄2 ) ⋅ 𝑇max with 𝐸̃ 𝑖 = 𝑑𝑖 + (𝑠𝑖 − 𝑠̄𝑖 ) 𝑇𝑖 element 𝑖’s energy above what its device would draw idling over the same period, the decomposition of Perseus [6]. The move changes only 𝐸̃ 1 at unchanged 𝑇max , and with 𝛿 = 𝑇1′ − 𝑇1 , ∆𝐸 =

𝑑1′ − 𝑑1 ⏟⏟⏟

(i) dynamic saving

+

(𝑠1′ − 𝑠1 ) 𝑇1 ⏟⎴⎴⏟⎴⎴⏟

(ii) static saving, active period

+

(𝑠1′ − 𝑠̄1 ) 𝛿 ⏟⎴⏟⎴⏟

,

(iii) window exchange

each term non-positive under its condition; the window exchange fills time formerly idling at 𝑠̄1 with computation drawing 𝑠1′ . The sign of (iii) is the race-to-idle decision: on hardware whose idle state draws less than the slowed active state, racing to finish and idling is the cheaper schedule and slack filling costs energy.

39

References [1] NVIDIA Management Library (NVML). https://developer.nvidia.com/nvidia-management-library-nvml. [2] Zeus. https://github.com/ml-energy/zeus. [3] Advanced Micro Devices, Inc. Processor programming reference (PPR) for AMD family 17h model 20h, revision A1 processors. https://docs.amd.com/v/u/en-US/55772-A1-PUB_3.08, 2021. [4] François Baccelli, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat. Synchronization and Linearity: An Algebra for Discrete Event Systems. Wiley New York, 1992. [5] CBRE. Global data center trends 2025. https://www.cbre.com/insights/reports/global-data-center-trend s-2025, 2025. [6] Jae-Won Chung, Yile Gu, Insu Jang, Luoxi Meng, Nikhil Bansal, and Mosharaf Chowdhury. Reducing energy bloat in large model training. In SOSP, 2024. [7] Jae-Won Chung, Jeff J. Ma, Ruofan Wu, Jiachen Liu, Oh Jun Kweon, Yuxuan Xia, Zhiyu Wu, and Mosharaf Chowdhury. The ML.ENERGY benchmark: Toward automated inference energy measurement and optimization. In NeurIPS D&B, 2025. [8] Prabuddha De, E. James Dunne, Jay B. Ghosh, and Charles E. Wells. Complexity of the discrete time-cost tradeoff problem for project networks. Operations Research, 45(2):302–306, 1997. [9] Intel Corporation. Intel 64 and IA-32 architectures software developer’s manual, volume 3B: System programming guide, part 2. https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html, 2026. [10] Vijay Kandiah, Scott Peverelle, Mahmoud Khairy, Junrui Pan, Amogh Manjunath, Timothy G Rogers, Tor M Aamodt, and Nikos Hardavellas. AccelWattch: A power modeling framework for modern gpus. In MICRO, 2021. [11] Helen Kou. Power for AI: Easier said than built. https://about.bnef.com/insights/commodities/power-for-a i-easier-said-than-built/, 2025. [12] Jean-Yves Le Boudec and Patrick Thiran. Network Calculus: A Theory of Deterministic Queuing Systems for the Internet. Springer Berlin Heidelberg, 2002. [13] Seonho Lee, Amar Phanishayee, and Divya Mahajan. Forecasting GPU performance for deep learning training and inference. In ASPLOS, 2025. [14] NVIDIA. NVIDIA A100 Tensor Core GPU datasheet, 2021. [15] Peter Selinger. A survey of graphical languages for monoidal categories. In Bob Coecke, editor, New Structures for Physics, volume 813 of Lecture Notes in Physics, pages 289–355. Springer, 2010. [16] SemiAnalysis. InferenceMAX: Open source inference benchmarking. https://newsletter.semianalysis.com/p/ inferencemax-open-source-inference, 2025. [17] Ola Svensson. Hardness of vertex deletion and project scheduling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 301–312, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. [18] U.S. Energy Information Administration (EIA). Capital cost and performance characteristics for utility-scale electric power generating technologies. https://www.eia.gov/analysis/studies/powerplants/capitalcost/pdf/cap ital_cost_AEO2025.pdf, 2024. [19] Samuel Williams, Andrew Waterman, and David Patterson. Roofline: an insightful visual performance model for multicore architectures. Communications of the ACM, 52(4):65–76, 2009. [20] Ruofan Wu, Jae-Won Chung, and Mosharaf Chowdhury. Kareus: Joint reduction of dynamic and static energy in large model training. In OSDI, 2026. [21] Jie You, Jae-Won Chung, and Mosharaf Chowdhury. Zeus: Understanding and optimizing GPU energy consumption of DNN training. In USENIX NSDI, 2023. [22] Kan Zhu, Yufei Gao, Yilong Zhao, Liangyu Zhao, Gefei Zuo, Yile Gu, Dedong Xie, Tian Tang, Qinyu Xu, Zihao Ye, Keisuke Kamahori, Chien-Yu Lin, Ziren Wang, Stephanie Wang, Arvind Krishnamurthy, and Baris Kasikci. NanoFlow: Towards optimal large language model serving throughput. In OSDI, 2025.

40