Research Abstracts - 2007

Bluespec is a high-level hardware description language used for architectural exploration, hardware modeling and synthesis of semiconductor chips. In Bluespec, one views hardware as a collection of stateful elements (e.g., registers, memories) and describes its behavior using rules, or Guarded Atomic Actions which modify these elements. All legal behaviors of a Bluespec program can be explained in terms of a sequence of rules being applied. Scheduling is the process of selecting which rules to execute in parallel while maintaining this semantic invariant. The scheduling decision can have a large impact on critical design properties such as pipeline concurrency and clock frequency.

Previously, it was thought that the scheduling of a design was the compiler's responsibility. Much work has gone into generating efficient scheduler circuits for designs which provide good throughput[1]. However, experience has shown that too often even clever schedulers, do not match the designer's intent[2]. As a result, scheduling pragmas were added to express these requirements. This approach proved to be relatively cumbersome and required too much knowledge of the compiler's scheduling algorithm.

We propose a new approach to this problem: place the scheduling responsibility back into the hand of the designer. To do this, we need a language by which we can precisely express a schedule.

Scheduling as Rule Composition

Rule composition is taking two smaller rules and composing into a larger rule. This derived rule's behavior can always be expressed as some deterministic sequence of the rules from which it is composed. This definition is very similiar to the scheduled system. In fact, we can express all schedulers for a system as a rule compositions on the rules in a design. We have defined a concise set of 3 primitive rule compositions from which all other schedulers can be described. We've also implemented some interesting examples in Bluespec using these composistions.

Future Work

Next, we want to reexpress these composition-based schedulers reflect the modular context. Additionally, this work provides a basis for reasoning not just at the rules, level but also at the scheduler level which may provide some interesting avenues for verification formalisms and strategies.

References:

[1] Thomas Esposito, Mieszko Lis, Ravi Nanavati, Joseph Stoy, and Jacob Schwartz. System and method for scheduling TRS rules. United States Patent US 133051-0001, February 2005.

[2] Nirav Dave. Designing a Processor in Bluespec. Master's thesis, Electrical Engineering and Computer Science Department, MIT, Cambridge, MA, Jan 2005.