Improved heuristics for finite word-length polynomial datapath optimization
Improved heuristics for finite word-length polynomial datapath optimization
复制标题
改进了有限字长多项式数据路径优化的启发式方法
DOI：
10.1145/1687399.1687536
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
M. Fujita
中科院分区：
文献类型：
--
作者：
B. Alizadeh;M. Fujita
传统的高级综合技术不能有效地处理多项式表达式，这是因为缺乏合适的优化技术来消除Z2n上的冗余.本文通过比较，提出了1)基于单变量单项式而不是检查所有子多项式的改进的划分启发式，2)能够补偿单项式和系数的改进的补偿启发式，3)结合面积延迟优化的因式分解方法，从Z2n上的多个输出多项式中提取最常用的子表达式。实验结果表明，与现有技术相比，该方法在逻辑门数和关键路径延迟方面分别平均节省32%和27.2%。与相比，门数和延时分别提高了14.3%和13.9%。实验结果表明，面积-时延联合优化可以使平均时延降低26.4%。
Conventional high-level synthesis techniques are not able to manipulate polynomial expressions efficiently due to the lack of suitable optimization techniques for redundancy elimination over Z2 n. This paper, in comparison with, presents 1) an improved partitioning heuristic based on single-variable monomials instead of checking all sub-polynomials, 2) an improved compensation heuristic which is able to compensate monomials as well as coefficients, and 3) a combined area-delay-optimized factorization approach to extract the most frequently used sub-expressions from multi-output polynomials over Z2 n. Experimental results have shown an average saving of 32% and 27.2% in the number of logic gates and critical path delay respectively compared to the state-of-the-art techniques. Regarding the comparison with, the number of gates and delay are improved by 14.3% and 13.9% respectively. Furthermore, the results show that the combined area-delay optimization can reduce the average delay by 26.4%.