（无锡中微亿芯有限公司，江苏无锡 214072）

1 引言

现场可编程逻辑门阵列（Field-Programmable Gate Array,FPGA）是一种在日用家电、大型机械乃至航空航天领域都有广泛应用的芯片。而FPGA 的设计离不开电子设计自动化（Electronic Design Automation,EDA）工具。布局则是EDA 工具中重要的一环，其对EDA 工具本身运行速度、所处理电路的最终质量有着很大影响。

近年来，FPGA 芯片电路的规模快速增长，使其功能更加强大，但同时也给相应的EDA 工具带来了挑战。解析型的算法以其可以使用数学方法快速求得全局最优解的特性成为当今布局算法的主流方向之一。二次线性规划算法[1-2]是解析型算法的一种，其在具体应用于解决布局问题的时候体现出了快速求解的特性，但在求解完成后，依然存在不合法的布局，需要再次进行合法化操作。原始的合法化操作仅是在不合法布局的周围寻找一个最近的合法位置，这样的操作不具备任何导向性，往往导致最终的解不尽如人意。业界有使用综合型算法[3]来弥补这一缺点，本文则将最大流算法应用于二次线性规划算法求解后的合法化操作，以求提高最终解的质量。

2 原始合法化流程概述

图1 曼哈顿距离示意图

3 最大流算法原理

如图2 所示是最大流算法中一个经典问题——两方匹配问题。每个节点有自己可以放入的位置，位置个数有限，要使尽量多的节点可以放入。将布局合法化问题抽象成图，将不合法节点与空置位置抽象为图中节点，将不合法节点与空置位置间的关系抽象为边。……