[Route] FLUTE:基于直线的快速查找表 超大规模集成电路设计中的Steiner最小树算法

斯坦纳树概念

斯坦纳树斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小

一、背景

斯坦纳最小树RSMT是NP 完全 问题，之前使用RMST代替使用，误差可以容忍，后期需要更好的无线长度，RSMT结构是必要的。其他算法计算过于昂贵或者其他原因。

本文提出基于查找表的RSMT算法——FLUTE

二、低度网的查找表法

基于哈曼网格，斯坦纳树的线长可以写成网格边长的线性组合。

大多数向量都是冗余的，所以每个低度网络只有几个powv。哪个是最优取决于每个网格边长实际的值。

三、查找表的生成

提出基于边界压缩技术的算法

四、缩小查找表的大小

五、最小长度计算的加速

总结

提示：这里对文章进行总结：