Compiling to Programmable Logic

Dennis Allison
Stanford University
10 May 1995

The Problem

The Concept

* Use traditional compilation techniques
* Examine the compiled program to discover complex primitives
* Compile program using the discovered primitives

Deja Vu: User Microprogramming

What Source Language To Use?

* Lots of candidates (C, Verilog, VHDL, CSP, Occam, Lisp, etc.)
* Most tend to hide concurrency
* Most languages look a lot like other languages
* Front-end issues (Parsing, Semantic Checks, etc) are well understood

The Altera Flex 8000 PLD

* Lots of usable "gates" (2500 to 24,000)
* Reasonable performance
* Interesting architecture
* RIP-10 and RIP-20 boards
* Configurable
* Not really a gate array ...

Block Diagram

Logic Element

Logic Array Block

Traditional PLD Approach

* Targets gates (logic)
* Uses standard logic design tools
* Separates design from layout from timing verification
* Gates tend to be standard logic
* Tendency to use standard PLD cells for many functions
* LEGO building block approach

"Michelangelo" Model

* Target PLD directly
* Discover complex gates and interconnections in specification
* Treat synthesis as a compilation problem
* Find the right instruction set

Tradition Vs. PLD Compilers

* Lexical and Syntax Analysis
* Control and Data Flow Analysis and Optimization
* Target Machine Dependent Optimization
* Code Generation

What's Understood

* Conversion of control flow to data flow
* Direct mapping of some functions
* Some program transformations
* How to compute dependencies, etc.
* How to discover some parallelism in a sequential program
* Protocols for communication between independent processes

What's Not Understood

* How to manage timing and control
* How to discover the best "instruction mapping" from problem onto PLD
* How to manage topological layout constraints
* How to manage parallelism and latency

Who Should Be Responsible?

* The programmer should be responsible for producing the algorithm for the function
* Should the programmer also be responsible for managing parallelism within the algorithm explicitly?
* Should the programmer be responsible for topological issues?
* Should the programmer be responsible for timing issues?

Is the Flex 8000 Architcture Right?

* Design is driven by bottom-up constraints
* Resources are sparse and have hard limits

* Bird in the hand

Genetic Algorithms

* Create a population of LABs
* Evolve them (mate with selection, genetic crossover, mutation) until suitable solution is found
* Continue until a suitable LAB is found