VLIW: The "Impossible" Computer

TL;DR

VLIW architecture promised 10–30x speedups by shifting all scheduling complexity from hardware to a radical trace-scheduling compiler, but its company Multiflow collapsed before the market could validate it.

Key Points

• 1.Josh Fisher invented trace scheduling at NYU's Courant Institute in the late 1970s. Working on the PUMA CDC-6600 emulator, he noticed that chip layout and code scheduling were conceptually identical — both transform 1D lists into 2D grids — inspiring a compiler that treats an entire program as one block and predicts execution paths.
• 2.A 1970 paper had concluded parallelism could only yield ~2 simultaneous operations. Trace scheduling demolished this assumption by ignoring conditional branch boundaries, allowing the compiler to aggressively bundle independent instructions into a single Very Long Instruction Word for massive parallel execution.
• 3.Fisher's 1982 ISCA paper introduced VLIW and the ELI-512 architecture. The compiler, named Bulldog, was the true innovation — targeting 10–30 RISC-level operations per cycle — but audiences were drawn to the provocative hardware claims, which Fisher considered the easy part.
• 4.Multiflow was founded in April 1984 after a $500,000 Apollo Computer loan and later $33 million in VC funding. Fisher left Yale with grad student John Ruttenberg and systems manager John O'Donnell; the Apollo deal collapsed six months in, forcing cofounders to personally borrow money to keep paying staff.
• 5.The TRACE 7/200 computer bundled 7 instructions into a 256-bit word; later models scaled to 28 instructions at 1024 bits. The hardware was deliberately simple — multiple arithmetic, logic, floating-point, memory, and branch units — while the compiler handled all scheduling, bus coordination, and memory conflict resolution.
• 6.The Multiflow compiler operated in three phases and created six intermediate representations, sometimes taking up to 3 days to compile. It outperformed RISC-based MIPS machines on LINPACK benchmarks by 2–10x, and the 7/300 series' fourfold speed gains in 1989 came almost entirely from software improvements alone.
• 7.Multiflow debuted the TRACE at the World Trade Center in April 1987, selling ~100 machines to 75 customers by end of 1989. Customers included the NSA's Supercomputer Research Center, P&G, HP, and Motorola; a Cray cost ~$5 million versus the TRACE's $300,000.
• 8.The minisuper market imploded starting in 1988, killed by "Killer Micros" — RISC-based UNIX workstations like SPARC, RS/6000, and the Intel i860. The i860 ran at 25 MHz on a few watts for ~$100,000, while the TRACE ran at 8 MHz requiring multiple kilowatts; Moore's Law scaling favored integrated single-chip designs Multiflow's discrete cluster architecture couldn't match.
• 9.Multiflow voluntarily liquidated in March 1990 after a DEC acquisition fell through, but its ~160 employees — "Multifloids" — spread VLIW ideas to HP, Intel, and DEC. Fisher won the Eckert-Mauchly Award; Bob Colwell joined Intel and became chief architect of the Pentium Pro through Pentium 4, ensuring VLIW's influence on modern computing.