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

When designing a distributed embedded system, software AND hardware developers need to deal with several design problems:

Problem #1: We must schedule operations in time, including communication on the network and computations on the processing elements. Clearly, the scheduling of operations on the PEs and the communications between the processing element are linked.

If one PE finishes its computations too late, it may interfere with another communication on the network as it tries to send its result to the processing elements that needs it. This is bad for both the processing elements that needs the result and the other PEs whose communication is interfered with.

Problem #2: we must allocate computations to the processing elements. The allocation of computations to the PEs determines which communications are required-if a value computed on one PE is needed on another, it must be transmitted over the network.

Problem #3: we must partition the functional description into computational units. Partitioning in this sense is different from hardware/software partitioning, in which we divide a function between the CPU and the accelerator. The granularity with which we describe the function to be implemented affects our choice of search algorithm and our methods for performance and energy analysis.

Problem #4: we need to map processing elements and communication links ***a*** onto specific components. Some algorithms allocate functions to abstract PEs and links that do not model the behavior of a particular component in detail. This allows the synthesis algorithm to explore a larger design space using simple estimates. Mapping selects specific components that can be associated with more precise cost, performance, and power models.

In short, co-synthesis design systems need to satisfy objective functions and meet constraints. The traditional co-synthesis problem is to minimize hardware cost while satisfying deadlines. Power consumption was added to objective functions as low-power design became more important. Several groups have developed algorithms that try to satisfy multiple objective functions simultaneously

Following on the overview in Part 1 in this series, the discussion here in Part 2, will consider various design representations including 1) methods used to specify the programs that describe the desired system behavior; 2) ways to describe the characteristics of the hardware and 3) techniques to synthesize based on a hardware architecture template.

Part 3 looks at co-synthesis algorithms for general multiprocessors that generate arbitrary hardware topologies without the use of templates. Finally in Part 4, we study 1) multi-objective algorithms for co-synthesis, 2) co-synthesis for control and I/O systems; 3) co-synthesis techniques designed for memory-intense systems; and 4) co-synthesis algorithms for reconfigurable systems.