Down & dirty with HW/SW co-design: Part 2 - Co-synthesis algorithms

Wayne Wolf

June 18, 2011

Wayne Wolf

Program Representations
Co-synthesis algorithms generally expect system functionality to be specified in one of two forms: a sequential/parallel program or a task graph. Programs provide operator-level detail of a program's execution. Most programming languages are also sequential, meaning that synthesis must analyze the available parallelism in a program. Some co-synthesis systems accept fairly straightforward subsets of languages such as C.

Others add constructs that allow the designer to specify operations that can be performed in parallel or must be performed in a particular order; an example is the HardwareC language used by Vulcan [Gup93].

The system of Eles et al. [Ele96] takes VHDL programs as behavioral specifications; they use VHDL processes to capture coarse-grained concurrency and use VHDL operations to describe interprocess communication.

Task graphs, as we saw in Part 1, have been used for many years to specify concurrent software. Task graphs are generally not described at the operator level, so provide a coarser-grained description of the functionality. They naturally describe the parallelism available in a system at that coarser level. However, task graph variants that allow conditional execution of processes have been developed.

For example, Eles et al. [Ele98] used a conditional task graph model. Some edges in their task graph model are designated as conditional; one is labeled with the condition, called a guard, that determines whether that edge is traversed.

A node that is the source of conditional edges is called a disjunction node and a node that is the sink of conditional edges is a conjunction node. They require that for any nodes i and j, where j is not a conjunction node, there can be an edge i -> j only if it is the case that the guard for i is true, impling that the guard for j is true.

The control dependence graph (CDG) introduced in Part 1 in this series can be used to analyze the conditions under which a node will be executed. Also, Task Graphs for Free (TGFF) [Dic98c]  is a Web tool that generates pseudorandom task graphs. The user can control the range of deadlines, graph connectivity parameters, and laxity.

A very different specification was used by Barros et al. [Bar94], who used the UNITY language to specify system behavior. UNITY was designed as an abstract language for parallel programming. The assignment portion of a UNITY program specifies the desired computations.

It consists of a set of assignments that may be performed either synchronously or asynchronously on a statement-by-statement basis. Execution starts from an initial condition, statements are fairly executed, and execution continues until the program reaches a fixed point at which the program's state does not change.

Platform Representations
In addition to representing the program to be implemented, we must also represent the hardware platform being designed. Because a platform is being created and is not given, our representation of the platform itself must be flexible. We need to describe components of the platform so that those components can be combined into a complete platform.

Some of the information about the platform is closely linked to the representation of the program. For example, processor performance is usually not captured abstractly; instead, we generally capture the speed at which various pieces of the program execute on different types of PEs. One data structure that is used with some variation in many systems is the technology table (see Figure 7-7 below).

Figure 7-7 A multiprocessor connectivity graph.
This table gives the execution time of each process for each type of processing element. (Some processes may not run on some types of PEs, particularly if the element is not programmable.)

A co-synthesis program can easily look up the execution time for a process once it knows the type of PE to which the process has been allocated.

The performance of a point-to-point communication link is generally easier to characterize since transmission time is independent of the data being sent. In these cases we can characterize the link with a data rate.