Orangepath/HPRLS Project: Hardware and Embedded Software Synthesis from Executable Specifications.
Direct Synthesis of Protocols

Automated Design of Data Transfer Protocols

Many detailed aspects of system implementation are similar in process to designing external protocols for system interaction. So we can concentrate on protocol design to perform system design.

Sections, Interfaces, Busses and other Terminology

Let us define some terminology.

We use the term code to refer to both declarative and behavioural source code.

A protocol operates over an interface. Interfaces occur where sections touch each other. Any particular section has one or more interfaces. There can be more than one interface between any given pair of sections. Each interface operates its protocol without reference to the other interfaces. Source and sink sections are used frequently in system testbenches: these have a single interface and just generate or soak up data respectively.

Inside our HPRLS tool, the above terms, interface, protocol and section, are implemented in a user-extendable libraries and built-up from a single lower-level construct called a unit.

A hierarchic design approach is useful, where a parent section may instantiate child sections, configure wiring between certain of the child section interfaces and present the remaining interfaces as the interfaces to the parent. The internal interfaces are hidden interfaces.

Certain interfaces are peer-to-peer and others are busses, meaning respectively that exactly two and more than two sections connect to the nodes of the interface. Many peer-to-peer interfaces are asymmetic, requiring one client section and server sides (sometimes called master and slave). Most interfaces have an explicit or implict idle state and conduct exactly one transaction between (nominal) visits to the idle state. The side that initiates a transaction is the master or client side. Other interfaces are hermapharodite.

In summary, a design is made up of sections. Each section has a number of external interfaces. It may have instantiated lower sections with hidden interfaces between them. Interfaces must be defined before they are used in section definitions. Each interface has its own class name in a class namespace. For each interface there is an associated protocol. A section definition describes a structured arrangement of interfaces by making reference to the interfaces, using class and instance name, and also contains local code for that section, that implements the internal operation of the section.

Scheduling and Nodeslots

Design of a protocol normally involves scheduling operations against time where there are detailed limits on the number or set of concurrent operations. At the lowest level, an operation is a wire having a data value on it. Let us call the wires that form part of an interface `nodes'. The most simple node is a single bit wire, which is a one or a zero at each clock cycle. More complex nodes can take on a scalar value. In transactional-level modelling, nodes can range over a instance of a data structure or object. Nodes are visible to both the sender and receiver of the data. For instance, a USB interface is a two-wire bus, and hence has two, one-bit nodes. In USB, the nodes are bidirectional and can be thought of as shared variables.

We are considering digital, synchronous interfaces only, whereby each node takes on exactly one value per clock cycle. If there is no explicit clock net at the interface, we require that other wiring or clock recovery techniques are used to explicitly define the relevant clock domain. (Indeed, a frequently occuring protocol constraint is the presence of sufficient transitions for clock recovery, even when idle.) We use the term nodeslot to refer to the value of a node during one clock cycle.

When generating a circuit, the nodes become ports or contacts of a Verilog or VHDL module. When generating software, the nodes become shared variables in a RAM or the formal parameters and return value to a function. Indeed, there is no clear distinction between hardware and software because we are refering to data representation rather than control flow. In either case, the direction of transfer of data over the node must generally be expressed. However, since we wish to use the same design source code for both sides of an interface, and the interface is frequently asymmetric, we must generally specify whether to generate the client or server side, which in turn dictates the directions of the nodes. Rather than use loaded terms such as client and server, or master and slave, we use the terms forward and reverse. We split the specification of an interface into three separate syntactic definitions, containing the neutral declarations, the forward declarations and the reverse declarations. It is intended that as much as possible of the design is specified in the neutral definition. However, information about node directions must be included in forward definition. The forward definition is then used to largely infer the contents of the reverse definition. The reverse defintion should just contain material that cannot be infered by our tool by reversing the contents of the forward definition. Behavioural source code is frequently polarity sensitive (i.e. needs to be different between the two directions) and so, where used, a pair of versions of it generally must be placed in the forward and reverse definitions. Again, the intention is that behavioural specification should be used sparingly, leaving as much of the specification as possible to neutral declarations.

Example Protocol Constraints

Protocols implement restrictions on the sequences of values on nodes. For instance, in the MFM protocol used for floppy-disk data transfer, there is one node, which is the read head. The restrictions are that ... also HDB3. RS232. B3ZS.

Example restrictions arising in practice:

  • Number of simultaneously switching nodes.

  • Polarity insensitivity.

  • Finite error propagation.

  • Disparity restriction.

  • One's density restriction.

  • Error detection.

  • Flow control.

    Our Approach

    Protocols are generally designed to transfer opaque data bits. Design of a protocol amounts to a data conservation exercise, where a number of source bits must be transfered to the same number of destination locations using the interface nodes [ Data Conservation Primitives]. There are many possible orderings of the data over the nodes, and many of these may violate the constraints imposed by the physical properties of the interface.

    Each interface node will take on the value of an expression at each time slot. The values will be invertible functions of the data to be transferred. When there are no constraints, one solution is for each node to be the identity function of a given bit.

    A backtracking approach to protocol design can be considered, where we attempt to map data to nodeslots, and backtrack where violations are encountered. The algorithm can be phrased easily in prolog. We can then use a SAT solver to do the backtracking, which helps with large problems and allows the contraints to be more-easily expressed as formal predicates.

    Adding Data Processing Operations

    To allow the system to do more than move data, we must introduce computation elements. We chose to place (many of the) computation elements at the nodes of hidden interfaces. Therefore we can statically allocate their number and their use can be planned on a cycle-by-cycle basis by the HPRLS system. dot dot

    Concrete Syntax

    We have defined a simple concrete syntax for our language and written a yacc parser to generate an ML structure for our examples. In the future, other tools can generate the same abstract syntax.

    Example interface definitions

       interface bunny
    	   protocol hopper;
    	   assert always dvalid->ack;   // 
    	   always ~dvalid -> terms == X; //
    	   node out [2:0] terms;
    	   node out ack;
    	   node in dvalid;
    	   // The nodes are implicitly defined here
    	   // but with the reverse direction.

    Example section definitions. We do not optimise over section boundaries at the moment, but will add support and control for that.

       section mysource
         interface bunny a;
       section mytranscoder
         interface bunny b;
         interface bunny c;
       section mysink
         interface bunny d;
       // Top-level section for simulation
       section system
          interface bunny x, y;
          mysource s1(.a(x));
          mytranscoder tc1(.b(x), .c(y));
          mysink s2(.d(y);


    Please see Two Rail Signalling.

    Please see GPIB to Centronix Example.

  • (C) January 2003 DJ Greaves. Home.