You Never Know

Grad-school work on worst-case execution time — and how the same method jumped to energy, then got dwarfed by scale. You never know.

A look back — long before any of the tools we argue about now.

The topic I was handed as a small first-year master’s student in the late 1990s was WCET — Worst Case Execution Time — analysis. Wikipedia dates the term to around 2008, but I’d inherited the project from the lab’s seniors and started studying it back in 1995, so there’s a gap in the timeline somewhere. A slightly hard story first, then two “you never know” turns.

Roughly: in an RTOS world where many tasks each run as functions, if you can know a well-predicted execution time before running, you can schedule efficiently. You build a “program” using a simulator and cache emulation of the machine, solve it with theoretical methods, take a benchmark’s source and its compiled code as input, construct the worst-case scenario, and predict it. The final comparison ran on a MIPS workstation.

Safer, Tighter, at Reasonable Cost

A prediction method has to satisfy those three virtues. My seniors’ research moved from judging by code path alone to emulating instruction and data caches, then the varied pipelines of a superscalar processor, tightening the bound. What I added was a claim that feeding in loop bounds and the conditions inside loops made a few benchmarks a little tighter. After me, the professors and the others extended it toward NAND flash and beyond.

I don’t remember exactly, but it was something like reducing an insertion sort’s N² over-bound — useful on a handful of benchmarks, a suitably modest ending. To get there I tore a compiler apart across several phases and built up MIPS cross-compiling know-how. It could be genuinely useful scheduling once MIPS chips came down into real controllers, though university research also does things a long way from reality. My master’s was a struggle for lack of depth, but those goals still sit well in memory. Isn’t that engineering, though?

You Never Know (1): Into Energy

The heart of the method was binary-code-level analysis of each instruction’s behavior through simulation and emulation, with final units in nanoseconds and clock counts. Since every different CPU meant reimplementing things, I built an abstract machine layer and spent a lot of time laying out and comparing systems — and hit limits handling the new instructions of complex systems, plus the difficulty of CPUs that wouldn’t cross-compile cleanly.

Around the late 1990s, heat and energy consumption suddenly became the topic. Energy had always been an issue, but as things went mobile and embedded it rose again — and as a kind of pre-flight check, you’d measure how much battery an app would drain before running it, and plan around that. Nearly the same concept. You’d account for each instruction’s energy and rewrite multiplications as additions, or accept a little slowness for lower draw. That timing could be swapped for energy so easily told me there’s a lot to learn from how the masters understand a thing.

You Never Know (2): Scaling

Later, working at a company, I drifted away from the academic world — but that was also a time of explosive information and a paradigm shift, and I met plenty more realizations, and plenty more pointlessness. Where the approaches above were efforts to lift a prediction by five or ten percent and raise utilization by that much, the surrounding world changed in brute, overwhelming ways. If you’re short on memory, add more — you could call that scaling too.

Until it broke recently, Moore’s law kept driving usage up, all kinds of parallelism became possible, and now anyone — if they can bear the cost — can train on the world’s documents; batteries with new lithium-ion materials jumped past ten times the old capacity in no time, and the gleaning of a few percent here and there came to look faintly embarrassing. I’m still in the middle of the change, which is fascinating and, honestly, not purely fun — but in another sense, you never know. Let’s look back again in ten years or so.

Part of 90s Computer Science Stories — first-person notes on growing up with computers and studying CS in Korea in the 1980s and ’90s. See the full series →

Adapted from my Korean essay on Brunch: brunch.co.kr/@chaesang/47