最大流算法应用于二次线性规划布局合法化过程  

Max-Flow Algorithm Applied to Legalization Process in Force-Directed Quadratic Placement

作　　者：王新晨 周洋洋 虞健 惠锋 WANG Xinchen;ZHOU Yangyang;YU Jian;HUI Feng(East Technology,Inc.,Wuxi 214072,China)

机构地区：[1]无锡中微亿芯有限公司,江苏无锡214072

出　　处：《电子与封装》2021年第4期46-49,共4页Electronics & Packaging

摘　　要：以力导向为基础的解析型算法如今越来越多地被应用到FPGA布局问题当中去,二次线性规划算法便是其中一种,其使用数学的方法求解拉力模型矩阵,以得到理论的最优解。但在实际的算法实现当中,二次线性规划虽体现出了其较快求解的特性,其解却存有重叠的问题,尚需进一步合法化以解决重叠问题。现有的合法化过程一般较为随意,并无系统性算法,导致最终解质量下降。文章将合法化过程加以抽象,转化为最大流算法的问题,以求得最优合法的解。Nowadays,force-directed analytic algorithms are often applied to solve FPGA placement problems.Quadratic placement is one of them which using mathematical methods to solve matrices derived from force model,to get the theoretical optimal solution.The solutions usually contain overlapped instances,and a legalization step is required to remove the overlap.Legalization is usually based on greedy approach that reduced the quality of the placement solutions.In this paper,the placement legalization process is modeled as a network flow problem and the max-flow algorithm is used to improve the quality of the final placement solution.

关 键 词：FPGA 布局 二次线性规划 最大流 

分 类 号：TN402[电子电信—微电子学与固体电子学]