1.Mixed-Cell-Height Legalizer是什么？
在VLSI设计流程中，合法化（Legalization）是布局（Placement）的一个重要环节，用于在全局布局阶段之后消除所有单元之间的重叠，并确保元件被放置在指定的格点上，以确保设计的正确性和可制造性。
随着现代设计的复杂性不断增加，混合单元高度现代设计（Mixed-Cell-Height Modern Design）变得越来越流行，这使得合法化问题更具挑战性。
2.Open NBLG是什么？
Open NBLG是我们提出的一种基于协商（Negotiation-Based）的混合多倍高度单元的布局合法化算法 ，以全局布局后的标准单元布局坐标（def文件）和工艺库（lef文件）作为输入、能快速地产生一个合法且高质量的布局结果（def文件）。它可以在考虑栅栏区域（fence regions）和技术约束（tech constraints）的情况下减少混合单元高度电路的在合法化过程中的平均位移和最大位移。
Open NBLG基于ICCAD-2017 CAD Contest in Multi-Deck Standard Cell Legalization and Benchmarks数据集进行测试，使用C++代码实现，支持多线程协商来达到加速收敛的目标，并且使用开源的lefdef-toolkit库解析lef/def文件，可以很容易拓展到新的布局布线框架上。
3.OpenNBLG 有哪些特性？
算法将布局合法化问题创新地转化为布局格点资源分配问题，通过使用基于协商的方法，将标准单元对应的格点映射为协商中的所产生的成本，单元之间互相竞争格点资源，最终有效解决大规模资源分配问题，从而实现高质量合法化。
算法在合法化过程中采用隔离点和自适应惩罚函数来加速算法并减少位移，同时限制每个单元的可搜索空间在周围的窗口内，避免局部最优解。
算法利用多线程技术完成负载均衡，加速协商方法的收敛，提高合法化过程的效率和速度。
4.OpenNBLG 核心算法是什么？
算法核心流程主要包括三个部分：预处理（Preprocessing）、解决资源分配任务（Solving the resource allocation task）和后优化（Post-optimization）。如下图所示：
在预处理阶段，首先对单元进行排序，然后进行行位置对齐，最后将单元移出非法区域。
在解决资源分配任务阶段，所有单元竞争格点资源，最终消除彼此之间的重叠。在这个阶段，算法通过两种技术，即隔离点和自适应惩罚函数，加速算法的收敛过程并减少单元的位移。此外，每个单元的可搜索空间被限制在周围的窗口内，而不是固定的空间，以确保单元的移动可以逐步积累以走出局部窗口。
最后，在后优化阶段，采用贪心方法和二部图匹配算法进一步减少单元的位移，以提高合法化解决方案的质量。
详细算法见文末参考文献
5.结语
随着我们对合法化算法的不断深入和扩展，未来的科研工作将致力于进一步细化和提升该算法，以更好地适应和领先于快速发展的技术潮流。我们计划的主要研究方向包括：
考虑更实际的设计约束：未来的工作将更多地考虑实际设计中的约束，如进一步降低pin short/pin access和edge spacing的数量，提高其在实际设计中的适用性和有效性。
考虑CPU与GPU并行计算的可能，进一步加快算法的收敛速度，这将涉及算法的优化、计算效率的提升。
……
项目由西南交通大学集成电路学院邸志雄老师课题组陈锦炜、超松等同学完成，欢迎试用，期待能收到来自大家的反馈。
本算法的FPGA版本荣获2020年第二届“集成电路EDA设计精英挑战赛”布局合法化问题全国第一名。
参考文献
https://github.com/recurme/Mixed-Cell-Height_legalizer
J. Chen, Z. Di, J. Shi, et.al, "NBLG: A Robust Legalizer for Mixed-Cell-Height Modern Design," in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 41, no. 11, pp. 4681-4693, Nov. 2022.
