CS Paper Radar

Energy-optimal scheduling for clocked reversible computing

Michael C. Thumann, David Soloveichik

cs.CC cond-mat.stat-mechcs.ET ·submitted 2026-10-17 03:52 UTC · v1
theory

Abstract

Computational dissipation may arise from both information erasure and finite-time operation, although both contributions can in principle be avoided in the absence of space and time constraints. Logically reversible computation can replace erasure with ancilla cleanup, and slow adiabatic protocols can eliminate any excess finite-time dissipation. Under limited memory and in finite time, however, choosing reversible cleanup over erasure requires additional dissipative operations, creating a semi-reversible energy--memory--time tradeoff. We formulate this tradeoff at a fixed operating point of an externally clocked thermally coupled computer, where reversible checkpoint moves and local irreversible erasures have specified effective prices $ε_R$ and $ε_I$. Their ratio $λ=ε_I/ε_R$ selects an energy-optimal semi-reversible schedule under a checkpoint-memory bound by trading reversible moves against erasures. For a sequential computation whose dependency graph is a line, we derive an exact separator recurrence and prove that an asymptotically optimal schedule repeats a strictly reversible block followed by one local erasure. Coupling this scheduling theorem to a stochastic-thermodynamic constitutive model shows how temperature, primitive duration, memory, and device-dependent operation costs determine whether the optimal schedule uses reversible cleanup, elective erasures, or erasure at every disposal.

Comment
12 pages, 5 figures

Closest papers

Nearest neighbours by meaning across the whole index.

RENESIS: Energy-Aware Synthesis of Adiabatic Logic from Irreversible Netlists

cs.AR cs.ET ·2026-08-17 ·Mitchell A. Thornton
benchmarkcode/data similarity 0.66
Abstract · v1: 33pp., 13 figs; v2: 34 pp., 13 figs, 11 tables, added optimality gap results and cost remark for affine-detection test

We describe Renesis, an automated synthesis tool that accepts an ordinary irreversible netlist and produces a verified, technology-mapped energy-recovery (adiabatic) circuit, using energy rather than area or delay as the optimization criterion. Renesis models the netlist with a vector-space formulation that expresses simulation and justification sweeps as forward and reverse traversals whose cost is linear in the number of circuit components. The traversals populate ledgers with data tags that characterize switching, erasure, and observability information at their natural Rényi orders. The output is a logically reversible circuit mapped to one of eight energy-recovery families, with the associated parameters reported. Reversibility is treated here as a circuit-level requirement rather than a thermodynamic one. When an adiabatic gate erases information the penalty is not $k_B T \ln 2$ but a full non-adiabatic $CV^2$ discharge, which is comparable to the switching energy the circuit style exists to recover. Every synthesis transformation is equivalence-checked, and it must improve one of two reported cost tables, one uncapped and one after a series-realizability bound, while worsening neither before it is accepted. Across a twenty-circuit development set, optional re-synthesis passes improve fourteen circuits. On a held-out set of twenty circuits, fifteen of nineteen are improved, with a best-arm median of $0.91$ of the default energy. A certified optimality-gap program computes the distance between the synthesized circuits and the provable floor of the tool's own search space. A device-level SPICE deck reproduces the tool's per-cycle energy figures on the reference family. The tool, the benchmark netlists, the validation procedure, and the run records behind every reported number are released as open source.

0.37

Beyond Reachability: When Edit Order Preserves Couplings in Graph Flow Matching

cs.IT cs.LG ·2026-10-28 ·Zilin Li, Zixing Song
similarity 0.58
Abstract · 14 pages. Theoretical preprint

Shortest-path optimality does not guarantee that a memoryless graph generator preserves a prescribed source-target correspondence. We study whether reordering legal shortest edits can retain this correspondence without changing the pairing, mandatory edits, or sampling budget. Under a common Poisson clock, we establish an exact criterion for endpoint coupling recoverability: the source-blind Markov projection attains the unavoidable clock-error floor if and only if routes to distinct targets do not share graph states. Routes to the same target may merge without sacrificing endpoint fidelity. This characterization leads to an exact finite-state routing formulation and a legality-preserving scheduling procedure with recovery certificates. A marker-free construction demonstrates how shared edge structure can retain source distinctions, while a capacity-constrained family exhibits a sharp separation in paired error between edit orders with identical marginal error. Finally, a target-conditioned aliasing bound connects structural route design to the terminal fidelity of a learned graph-only generator. These results characterize when legal edit ordering can preserve a prescribed coupling under fixed operational costs.

0.33

Asymmetric Weighted Earliness-Tardiness: Scheduling with a Nonrestrictive Common Due Date

cs.CC math.OCcs.DMmath.CO ·2026-09-12 ·Nicholas G. Hall, Hans Kellerer, Miao Song
similarity 0.57
Abstract · 268 pages, 12 figures, 29 tables

Single-machine asymmetric weighted earliness--tardiness (AWET) scheduling asks how to sequence jobs around a common synchronization date when early and late completion incur unrelated job-dependent penalties. At the boundary nonrestrictive date $d=\sum_jp_j$, a compact V-shaped schedule reduces the continuous-time problem to a quadratic choice of a nonempty early set. We establish four complementary results for this model. First, the positive-integer problem is strongly NP-complete by a unary-polynomial reduction from Restricted Exact Cover by 3-Sets. Second, unrestricted AWET admits a polynomial-time $(3+2\sqrt2+\varepsilon)$-approximation based on an anchored semidefinite relaxation and deterministic marginal thresholding. Third, when the earliness and tardiness ratio orders are strict reversals, the problem is weakly NP-complete but has an exact two-resource pseudopolynomial dynamic program. Fourth, for fixed total refinements whose ratio permutation is separable, an exact separating-tree recurrence and coordinated geometric trimming yield an FPTAS. The proofs use different manifestations of the same canonical objective: scale-separated prefix penalties, positive-semidefinite minimum-kernel covariance, a dominant completed load square, and a bounded four-coordinate decomposition interface. Together, the results show that the decisive issue is not merely whether the two ratio orders agree, but whether their interaction can be controlled by a global certificate or compressed into a bounded constructive interface.

0.21

Self-stabilising approximate clock synchronisation requires linear time

cs.DC ·2026-11-03 ·Joel Rybicki
theory similarity 0.56
Abstract

Synchronising the clocks of processes is a fundamental problem in distributed computing. We consider message-passing systems in which processes start in an arbitrary initial state (self-stabilisation) and up to $f$ processes may be non-transiently faulty. It is well known that synchronising clocks \emph{exactly} is at least as hard as consensus and requires $Θ(f)$ time. In contrast, without self-stabilisation, clocks can be synchronised \emph{approximately} much faster, in time independent of the number of non-transient faults [Srikanth and Toueg, JACM 1987; Welch and Lynch, Inf. Comput. 1988]. In this work, we show that deterministic self-stabilising approximate clock synchronisation tasks require $Ω(f)$ time to stabilise. This gives the first non-trivial time lower bound for these tasks, whose time complexity has remained open for over two decades [Dolev and Welch, JACM 2004; Dolev, Függer, Schmid and Lenzen, JACM 2014]. In particular, this answers the open question whether self-stabilising approximate clock synchronisation tasks are as hard as consensus or as easy as approximate agreement [Lenzen and Rybicki, JACM 2019]. The results show that guaranteeing \emph{both} transient and non-transient fault-tolerance simultaneously is expensive even for approximate synchronisation tasks. The lower bounds hold in a very strong model: the faulty processes can only crash, the local clocks of processes have no clock drift, and the message delay is bounded and known to all processes. The proof is based on a combinatorial topological argument showing that no fast finite-state protocol can ensure that the clocks behave consistently across all executions. To our knowledge, this is the first use of topological arguments to prove time lower bounds in the self-stabilising setting.

0.14

Bao: Automatic Region Placement and Memory Allocation for Intermittent Computing

cs.PL ·2026-10-02 ·Byeongjee Kang, Jan Hoffmann, Limin Jia, Brandon Lucia, Feras A. Saad
top venuetheory similarity 0.55
Abstract · Accepted to ASPLOS '27. 28 pages, 12 figures, 10 tables

Intermittent computing enables batteryless embedded devices to operate in harsh environment, but frequent power failures interrupt program execution and require careful management of state across power cycles. The core challenge is to guarantee both memory consistency and forward progress while minimizing the energy overhead of checkpointing. Recent compile-time approaches identify regions that fit in the energy buffer. At runtime, the device waits and recharges between the regions. However, they still rely on greedy or path-local heuristics that commit to local decisions and can miss globally lower-overhead boundary placements. To address this limitation, we present Bao, a system that jointly finds optimal energy-aware region formation and memory allocation decisions with formal correctness guarantees, by formulating it as a mixed-integer linear program. We prove that any feasible solution guarantees energy safety and implement our approach in LLVM. Our evaluation on 13 benchmarks across 3 capacitor sizes shows that Bao outperforms existing baselines, achieving 10% faster execution and 52% fewer region boundary hits on average compared to the best baseline.

0.38

Approximation Algorithms for Dual-Memory Request Scheduling in Disaggregated LLM Inference

cs.DS ·2026-10-11 ·Xin Wang, Hong Shen, Hui Tian, Ye Tao
similarity 0.55
Abstract · 30 pages, 15 figures

Disaggregated LLM inference executes the prefill and decode phases on separate resource pools, reducing interference between the two phases. However, this architecture introduces a coupled scheduling problem because a request that completes prefill retains its prompt KV cache in prefill memory until it is admitted to the decode pool. Prefill and decode admission decisions therefore jointly determine memory occupancy and request completion times. To the best of our knowledge, this problem lacks a formal formulation, and no approximation guarantees are known for request scheduling in disaggregated LLM inference. We formalize this setting as the dual-memory request scheduling (DMRS) problem, whose objective is to minimize the sum of request completion times, and prove that it is strongly NP-hard. We develop two deterministic polynomial-time approximation algorithms. The first applies to instances satisfying $α<1$ and $β<1$ and achieves an approximation ratio of $8+\frac{4}{1-α}+\frac{8}{1-β}$, where $α$ and $β$ are the maximum normalized prefill and peak decode memory demands among all requests, respectively. In particular, it yields a $32$-approximation when $α,β\leq 1/2$. The second algorithm applies to all feasible instances and achieves a uniform $36$-approximation. Finally, evaluations on two H100 GPUs using trace-derived offline workloads show that the proposed algorithms reduce the sum of request completion times relative to multiple vLLM deployment baselines.

0.14

The Price of Remembering: A Calibrated Energy Law for Computation

cs.PF cs.ARcs.LO ·2026-09-01 ·Mohamed Amine Bergach
theory similarity 0.55
Abstract

Where does a computer's energy go? Mostly into keeping, not into computing. A bit held in fast storage draws power for every second it stays there, and it costs energy again each time it moves between storage levels. We call the first cost \emph{rent} and the second \emph{fare}, and we state one law: the energy of a computation is at least its operations, plus rent on every live bit for as long as it lives, plus fare on every bit moved. The model under the law prices control as well as data. There is no free clock, and any unpriced register would make the theorems false. One lemma does most of the work: every use of a value is paid for by rent, by fare, or by computing the value again. Three things follow. Exact attention brings every past token back for every new one, so its energy grows with the square of the context length, while a recurrent model with a fixed state grows linearly. The square is a theorem for machines that never re-read past tokens. Under a stated serving hypothesis it is the fare on every past token, which passes the model's own arithmetic near ten thousand tokens, the point where long-context serving becomes bandwidth-bound today. Known bounds on memory over time become joule floors: on any sequential machine with volatile working storage, sorting $n$ items pays rent proportional to $n^2/\log n$ bit-steps on most inputs, and the bound for scrypt makes every password guess cost joules that no amount of parallel hardware reduces.

0.47

Online Resource Allocation with an Endogenous Markov State: Fewer LP Solves Earn More

cs.LG ·2026-10-07 ·Zhaohua Chen
benchmark similarity 0.54
Abstract

We study finite-horizon online resource allocation with i.i.d. requests and an endogenous Markov state on a finite state space: each action affects the transition of the state that governs future rewards and resource consumption. In this problem, a transient fluid LP benchmark upper bounds the expected reward of every nonanticipating policy, while a stationary LP supplies randomized state-dependent controls. We assume that the stationary LP has a unique optimum and identify primal nondegeneracy and irreducibility of the optimal induced kernel as important regularity conditions in this framework. With a known request prior, we show that, under nondegeneracy and irreducibility, both frequent and infrequent re-solving attain $O(1)$ regret. However, under a degenerate optimum, irreducibility yields the sharp worst-case $Θ(\sqrt{T})$ rate for infrequent re-solving, while frequent re-solving can incur $Ω(T)$ regret. Thus, more frequent optimization can perform asymptotically worse. With an unknown request prior, we develop a three-phase U-shaped infrequent re-solving policy that coordinates learning and inventory correction with $O(\log\log T)$ LP solves. When the optimal induced kernel is irreducible and the algorithm is given the optimal target state class and a constant-cost entrance policy, it attains $O(1)$ regret under nondegeneracy and $O(\sqrt{T})$ regret under degeneracy. Without the target-class information, linear minimax regret is unavoidable. Numerical experiments further illustrate the instability of round-by-round re-solving relative to epoch-wise infrequent re-solving, show that thresholding greatly mitigates its loss, and find that infrequent schemes remain dominant under both known and estimated priors.

0.19