SANTA CRUZ, Calif. EDA startup Bluespec Inc. this week will announce an exclusive license from the Massachusetts Institute of Technology (MIT) for synthesis technology based on term rewriting systems (TRS). The outcome, Bluespec said, will be high-level synthesis with results that match hand-coded RTL designs.
TRS-based synthesis, for which MIT received a patent in 2003, is said to dramatically reduce code size and logic errors and eliminate race conditions. Bluespec will use it to roll out a SystemVerilog "assertion-based synthesis" tool that promises to halve the time it takes to get to a netlist.
While critics say TRS-based synthesis is nothing new and offers little real improvement over RTL synthesis, its advocates insist they have a big advantage over C-language-based behavioral synthesis tools.
TRS is a computational model with many applications in computer science. TRS consists of sequences of discrete transformations in which "terms" are rewritten according to "rules." In the TRS-based synthesis developed at MIT, terms describe hardware states and rules describe behavior, capturing both state changes and the conditions in which they occur.
"You are thinking at a much higher level," said Bluespec's co-founder, Arvind, a professor of computer science and engineering at MIT. He uses only his given name. "It is an approach in which verification almost comes first," he said. "You start out with a description that you're pretty sure does the right thing, and then do transformations for area and speed without exacerbating the verification problem."
Arvind called behavioral synthesis based on C, or SystemC, a poor approach for hardware design. "It's a very difficult thing to control," he said. "The model presented to the designer is not that of an FSM [finite state machine], but when you're working with TRS, the high-level model is nothing but cooperating FSMs."
No chips have taped out using the technology, Arvind acknowledged. Sandburst Corp., a packet-switching startup he co-founded, used Bluespec for high-level modeling, he said. "We've done a fair amount of work compiling for FPGAs, and we've done lots of studies up to physical layout," Arvind said.
Thinking in assertions
To use the Bluespec compiler, designers first define state elements. In that sense it works at a lower level than C-language-based behavioral synthesis tools. But the real difference from RTL synthesis is that behavior, or action, is defined in terms of rules.
In the Bluespec compiler, this is done with design assertions in SystemVerilog, which are mapped into a TRS notation. The Bluespec compiler then outputs structural Verilog RTL that can be fed into Synopsys' Design Compiler.
Arvind said that the behavior of extremely complex systems can be completely described through the sequential execution of "atomic" actions. "Atomic means that it is completely indivisible," he said. "Single, indivisible operations that cut across module boundaries are unique to Bluespec."
The atomic semantics of TRS rules make it easier to handle complex systems with concurrent behavior, Arvind said. He also said that it eliminates race conditions. Those occur, Arvind said, when events happen in parallel unexpectedly " a consequence of a lack of atomicity.
"The notion of atomicity gives the designer a clean way to think about correctness, and the compiler is guaranteed to be consistent with that," Arvind said. This gives rise to what Bluespec calls "correct-by-compiler construction." When changes are made, Arvind said, the compiler recalculates and regenerates control logic that's guaranteed to be correct.
Rule-based descriptions don't say how long a rule takes. In essence, Arvind said, TRS-based synthesis generates synchronous digital circuits from asynchronous descriptions. In producing a synchronous circuit, the compiler identifies rules that can occur during a single clocking period. In this sense it does scheduling, but it's very different from traditional behavioral synthesis, he said.
"In a conventional system, scheduling means the compiler decides what should happen in each cycle," Arvind said. "Bluespec, on the other hand, is synthesizing a scheduler. It's a piece of combinational logic that is looking at which rules are enabled right now." Thus, he said, the scheduling is dynamic rather than static, and it can change according to data-dependent timing.
To use the Bluespec compiler, designers must first use a SystemVerilog subset identified by Bluespec. The compiler does some static checks and then converts the description into TRS notation. It allocates resources, generates the scheduler, and performs optimizations. The current output is synthesizable Verilog 1995.
Competitors are unimpressed. The Bluespec compiler "is only slightly higher than RTL," said Brett Cline, vice president of marketing at Forte Design Systems. "It still effectively causes engineers to have to work with state machines and register definitions. It's really a very small segment of the problem that needs to be covered."
Forte is preparing a SystemC-based behavioral synthesis tool, and Cline said that Arvind's critiques of behavioral synthesis are based on old information. Forte's tool, Cline insisted, can produce even better results than hand-coded RTL in many situations.
A Synopsys spokesperson said, "Rewriting is an old concept out of computer science and TRS synthesis techniques such as factoring and common-term elimination dating back to the early 1980s. Attempts to raise this technique to a higher level of abstraction are not new either."
Still, Bluespec now has an exclusive license for patented technology that, the company maintains, can reduce code size by a factor of 10 compared with conventional RTL coding. The company expects to announce a product in the first half of 2004.