Heads and Tails:
Efficient Variable-Length Instruction Encoding

Heidi Pan and Krste Asanovic

Existing variable-length instruction formats provide higher code densities than fixed-length formats, but are ill-suited to pipelined or parallel instruction fetch and decode. Heads-and-Tails is a new variable-length instruction format that supports parallel fetch and decode of multiple instructions per cycle, allowing both high code density and rapid execution for high-performance embedded processors. The Head-and-Tails format splits each instruction into a fixed-length head and a variable-length tail, and packs heads and tails in separate sections within a larger fixed-length instruction bundle. The heads can be easily fetched and decoded in parallel as they are a fixed distance apart in the instruction stream, while the variable-length tails provide improved code density.


[1] "Heads and Tails: A Variable-Length Instruction Format Supporting Parallel Fetch and Decode", Heidi Pan and Krste Asanovic, International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES 2001), Atlanta, GA, November 2001. (PDF paper, PDF slides, PPT slides)
[2] "High-Performance Variable-Length Instruction Encodings", Heidi Pan, M.Eng. Thesis, Massachusetts Institute of Technology, June 2002. (PDF)


We gratefully thank the sponsors for this work, including NSF, DARPA, and HP.