An instruction scheduler for Elbrus: why the LLM lost to a greedy algorithm

On ordinary processors the hardware picks the execution order. On VLIW, the basis of Elbrus, one wide instruction carries several operations, and the compiler decides which goes to which channel and cycle. A bad schedule does not break the program, it slows it down: channels idle, dependent operations wait.

The e2k-v6 constraints are strict: multiplication on four channels with a 4-cycle latency, division on one channel with 11 cycles, loads on four channels with 5 cycles, stores on two. The author measured them three ways: querying the port matrix of the lcc assembler, timing dependency chains and measuring throughput with independent streams.

A standard scheduler makes greedy, irreversible decisions: it takes a ready operation and places it in the first free channel. On simple graphs of 6–14 nodes it is almost flawless: 298–300 of 300 schedules optimal. On a hard set of 300 graphs the average gap to optimum was 1.03 cycles, with no exact solutions at all. The gap is measurable and provable, so there is room to improve.

The first attempt handed the whole schedule to Qwen2.5-3B. Result: 30 seconds per task instead of 3 milliseconds and only 17 % valid schedules on hard graphs. The model drowned in bookkeeping: checking channels, latencies and conflicts.

The second attempt changed the roles. The model outputs only the order of operations, a deterministic algorithm places them into channels and guarantees correctness. On the hard set this combination reached a gap of 0.82 instead of 1.03 and 59–62 exact solutions out of 300, roughly a 20 % improvement where greedy had hit its ceiling.

The lesson goes beyond compilers. A language model handles tasks with many simultaneous formal constraints poorly, but suggests priorities and order well. Give the model the heuristic and leave checking and execution to code with guarantees. Reliable AI agents in business processes are built the same way: the model proposes, rules decide.

The LLM did not replace the Elbrus scheduler, but improved it by a fifth once it was left only with ordering. An honest result: neither 'AI solved everything' nor 'AI is useless'.