Synthesis and Optimisation of Designs Based on Novel Canonical Algebraic Structures

行为综合是电子系统级设计的重要组成部分，它使设计人员能够集中精力进行最高层次的设计抽象，即行为级和算法级，从而为优化设计提供了最有效的手段。行为综合无疑对使用CAD工具设计的复杂集成电路（IC）和片上系统（SoC）的质量影响最大。尽管在过去的二十年里，行为综合取得了许多进展，但现有的综合系统在将初始设计规范转化为硬件方面仍然是无效的。特别是，现有的工具依赖于从设计规范中提取的单个固定数据流图（DFG），并映射到硬件上。本研究提出了一种基于功能的行为综合的系统方法，（而不是结构化的）计算表示。特别地，本文提出了一种新的方法，利用两种新的规范代数结构：1）Taylor展开图（TED）和2）Galois域决策图（GPDD），对算法设计描述中的多项式表达式进行有效的因式分解和分解，作为规范表示，这些结构可以捕获整个结构解类，而不是现有方法所能获得的单个DFG。通过本研究提出的一套新颖的功能分解程序，可以将初始功能表征转换为一组结构表征（数据流图，DFG），从中可以选择一个最佳的一个特定的设计目标，如芯片面积，延迟，功率，或性能，从而实现高效的硬件实现。所提出的方法将为设计人员提供一种工具来执行架构解决方案的有效探索，而不需要重写和重新合成原始规范以寻找最佳解决方案。

Behavioral synthesis, an important part of Electronic System Level (ESL)design, provides the most effective means to optimize the design by allowingthe designer to concentrate on the highest level of design abstraction, namely behavioral and algorithmic levels. Behavioral synthesis has unquestionably the greatest impact on the quality of complex Integrated Circuits (ICs) and systems on chip (SoC) designed with CAD tools. Despite many advances in behavioral synthesis over the past two decades, existing synthesis systems are still ineffective in translating the initial design specification into hardware.In particular, existing tools rely on a single, fixed data flow graph (DFG), extracted from the design specification, and mapped onto hardware.This research proposes a systematic approach to behavioral synthesis based on functional (rather than structural) representation of the computation. In particular, a new method is proposed to perform efficient factorization and decomposition for polynomial expressions derived from algorithmic design descriptions using two novel, canonical algebraic structures:1) Taylor Expansion Diagram (TED), and2) Galois Field Decision Diagrams (GPDD).As canonical representations, these structures can capture an entire class of structural solutions, rather than a single DFG obtainable with current methods. Through a set of novel functional decomposition procedures proposed in this research, the initial functional representation can be converted into a set of structural representations (data flow graphs, DFG), from which an optimum one can be chosen for a particular design objective, such as thecircuit area, latency, power, or performance, leading to efficient hardware implementations.The proposed method will equip the designers with a tool to perform efficient exploration of architectural solutions, without a need to rewrite and re-synthesize the original specification in search for the best solution.