Synthesis Algorithms

Research in synthesis algorithms is typically focused on the quality of the synthesis results. In most cases this goes along with increasing memory and performance requirements. Thus, synthesis algorithms are typically not feasible for an execution inside of embedded systems.

Rationale of new Algorithms

The aim of this research is to find new synthesis algorithms that are feasible for an execution inside of embedded systems. Thus, it would be possible to autonomously synthesize functional units for the adaptive processor to accelerate the running application (factors of 10-1000 depending on the nature of the application can be expected). Even if the result of the synthesis is not optimal compared to up-to-date algorithms, the speedup can still be significant enough. The general motto for this research will be: forfeit 10% of the quality and gain a factor of 10 in memory/performance requirements.

Approach

In general we will follow two branches:

• revisit CAD algorithms that have been developed recently. We will try to reduce their space and computing complexity by simplifying/neglecting design restrictions. Obviously, this will degrade the quality of the results. Thus, we have to find a balance between quality and complexity.
• revisit algorithms that have been replaced by better ones, but still may be of interest due to their complexity.

Current Work

Two areas of CSoC design algorithms shall be researched:

• Placement of cells. Current algorithms use either genetic programming or simulated annealing to find optimal placements. Due to the relatively small area that has to be considered in CSoCs other algorithms may also be relevant (min-cut or even greedy approaches).
• Technology mapping. Current algorithms often use binary decision diagrams (BDD) to find optimal mappings. Time and space complexity can be reduced by breaking down large functions into smaller ones before BDD mapping. Also, we can avoid finding the optimal structure of the BDD, which reduces time complexity.