A4-FPGA工艺映射算法及优化
1. 问题背景
随着芯片设计日益复杂和先进技术的不断发展，如图1所示，FPGA（现场可编程门阵列）在芯片原型验证和嵌入式系统中的应用越来越广泛。FPGA工艺映射是将逻辑电路映射到可编程逻辑查找表（LUT）的必不可少的过程，对FPGA设计的性能、功耗和面积（PPA）至关重要，图2是FPGA的基本结构。
然而，随着设计规模的增加和性能要求的提高，传统的工艺映射算法面临着挑战。这些算法在应对庞大的搜索空间、时序约束的优化、资源利用率的提升以及功耗的降低方面可能存在不足。为了提高FPGA设计的性能和资源利用率，对FPGA工艺映射算法进行优化是必要的。
2. 问题描述
2.1 描述
如图3所示是一个传统的FPGA工艺映射算法的概要图，其主要流程是对原始电路的每个节点进行CUT组的枚举，然后通过面积、深度等特性对每个节点的CUT组进行排序后，选择每个节点上最优的CUT，从而实现对整个电路面积的覆盖。从传统算法的流程来看，其还有很多可以进一步改进以及优化的地方。
如图4所示，本问题聚焦于基于智能CUT选择的工艺映射算法设计。该算法将利用智能筛选和优先割技术，以减少不必要的搜索空间并提高工艺映射的效率。通过对逻辑电路的结构和特性进行分析，算法能够智能地选择最优的割集（Cut Set）作为候选映射目标。同时，算法还将优化割集的选择顺序，以进一步减少搜索空间并提高映射效果。
该问题的目标是设计一个高效的智能筛选优先割的工艺映射算法，能够在大规模和复杂的FPGA设计中提供优秀的PPA性能。算法需要考虑多个因素，如逻辑电路的规模、时序要求、资源限制和功耗约束等。该算法的设计将充分利用智能筛选和优先割技术，结合先进的优化方法，以实现高效的工艺映射和优化。
2.2 问题case
每个案例的输入文件为AIG（And-Inverter Graph）格式的组合逻辑电路。AIG电路中的每个基本门为与门或者非门，如图5所示，与门和非门是逻辑完备组，可以表示其它所有基本门单元。
一个典型的输入文件如图5所示（本次问题只针对组合逻辑网表，所以第三项L总是 0）：
2.3 输出要求
输出文件为 LUTs 组成的网表。一个K输入的 LUT本质上是一个K位地址的单输出RAM，可以通过存储真值表的方式实现任意K输入的布尔逻辑。
一个典型的输出文件如图7所示，其中o0 = i0&i1&i2&i3&i4&i5; o1 = i0 | i2 | i4。
2.4 比赛环境
（1）运行环境
操作系统：linux系统；
硬件环境：64位x86CPU、128GB运行内存、1TB硬盘、NVIDIA-GPU；
软件环境：gcc7.5.0、g++7.5.0、glibc2.27、python3.7、cuda-驱动。
（2）参考工具
如图8所示，iMAP支持“.aig”文件的读写以及FPGA网表的写出。对于参赛队伍只需要关注FPGA工艺映射环节的算法即可。
3. 评分标准
（1）必备要求：通过等价性检查。保证输出的FPGA网表和原始输入AIG的逻辑等价，否则该题计0分。
（2）加权评分：cost=50%*runtime+30%*delay + 20%*area， cost越低表示结果质量越好，则对应case的得分就越高。