关于LUT与簇规模对深亚微米FPGA性能与密度影响的研究报告
本报告旨在向中文科研界介绍由Elias Ahmed与Jonathan Rose共同完成，并于2004年3月发表在《IEEE Transactions on Very Large Scale Integration (VLSI) Systems》期刊上的一项原创性研究。该研究隶属于计算机体系结构与电子设计自动化（EDA）领域，具体聚焦于现场可编程门阵列（Field-Programmable Gate-Array, FPGA）的底层架构设计。第一作者Elias Ahmed当时隶属于加拿大多伦多大学电气与计算机工程系，并在研究完成后加入Altera多伦多技术中心；通讯作者Jonathan Rose同样来自多伦多大学电气与计算机工程系，并兼任Altera多伦多技术中心的高级研究员。
一、 学术背景与研究目标 FPGA作为一种高度灵活的可编程逻辑器件，其基本逻辑单元——查找表（Look-Up Table, LUT）和由多个LUT组成的逻辑簇（Cluster）的规模（即LUT输入数K和每簇包含的LUT数N），是决定FPGA整体面积效率（密度）和速度性能（延迟）的关键架构参数。在本文工作之前，已有诸多研究探讨过LUT大小（K值）对FPGA面积和性能的影响。例如，早期研究（如Rose等人1990年的工作）表明，在非簇结构（即N=1）中，4输入LUT（K=4）在面积效率上最优；而另一些研究（如Singh等人1992年）则指出K=5或6能带来最佳性能。此外，也有观点认为混合使用小型LUT（如K=2和3）可能在面积上与K=4相当。然而，Ahmed和Rose认为有必要重新审视这一问题，主要基于以下四点背景：1）先前研究多集中于非簇逻辑块，而现代商用FPGA（如Altera Stratix/Cyclone系列和Xilinx Virtex系列）普遍采用簇结构，这对面积和延迟有显著影响；2）多数早期研究仅单独考察面积或延迟，而非两者兼顾；3）早期研究基于的集成电路工艺尺寸远大于当前（论文撰写时的2004年）的深亚微米工艺，未充分考虑深亚微米下的电气效应（如导线电阻电容的影响）；4）当前可用的计算机辅助设计（Computer-Aided Design, CAD）工具比十多年前更为先进，可能影响实验结果趋势。因此，本研究旨在系统性地探究在深亚微米工艺下，采用基于簇的岛式（island-style）FPGA架构时，LUT大小（K）和簇大小（N）对FPGA面积和性能的综合影响，并回答四个核心问题：1）为达到98%的逻辑单元利用率，簇所需输入数I与K、N的函数关系是什么？2）K和N对FPGA面积的影响如何？3）K和N对FPGA延迟的影响如何？4）哪些K和N值能给出最佳的面积-延迟乘积（Area-Delay Product）？
二、 详细研究流程 本研究采用了基于实验的架构评估方法，其核心是一个完全时序驱动（fully timing-driven）的CAD流程，对一组基准电路进行综合、映射、布局布线，并基于精确的晶体管级建模计算面积和延迟。
1. 实验对象与架构空间： 研究使用了28个基准电路，包括20个来自MCNC基准集的大型电路以及8个来自多伦多大学计算机视觉应用的新电路。这些电路被映射到一系列不同的FPGA逻辑块架构上。架构参数空间涵盖了LUT大小K从2到7，簇大小N从1到10，共计60种不同的架构组合。对于每种(K, N)组合，簇的输入数I并非简单设为最大值（K * N），而是通过预实验确定为能够实现98%逻辑单元利用率的最小值，以减少不必要的面积开销。
2. 实验流程与方法： 整个实验流程（如图3所示）包含以下步骤： * a. 逻辑综合与技术映射： 首先使用SIS工具进行技术无关的逻辑优化。随后，使用FlowMap和FlowPack工具进行时序驱动的技术映射，将电路转换为由K输入LUT组成的网表。 * b. 逻辑单元打包： 使用时序驱动的打包算法（T-VPack）将LUT和寄存器打包进逻辑簇中。此步骤决定了电路所需的逻辑簇总数。 * c. 布局与布线： 使用增强时序功能的VPR工具进行时序驱动的布局。布线阶段采用全路径、时序驱动的布线算法。为了获得有意义的性能评估，研究者并非在“高压”路由条件下测量延迟。他们先找到能够成功布线所需的最小通道轨道数，然后增加30%的轨道进行“低压”最终布线，并在此条件下测量关键路径延迟。这模拟了实际FPGA设计中设计师会留有余量的典型情况。 * d. 面积与延迟建模： 这是本研究方法学的关键创新与严谨之处。所有面积和延迟计算均基于一个0.18微米CMOS工艺的详细晶体管级设计。 * 面积模型： 采用Betz等人提出的方法，为FPGA中所有逻辑和路由电路（包括LUT、触发器、簇内多路复用器、簇间路由多路复用器和开关、以及相关的配置位）创建了详细的晶体管级电路设计，并进行了适当的门和缓冲器尺寸优化。面积度量为“最小宽度晶体管面积”的数量。该模型假设在多层金属工艺下，晶体管面积是决定总面积的主要因素，并得到了两家商用PLD厂商的确认。 * 延迟模型： 通过SPICE仿真考虑深亚微米下的导线电阻电容效应，精确提取了所有关键路径的延迟。这包括LUT内部延迟、簇内多路复用器延迟、以及驱动不同长度导线所需的缓冲器延迟。随着簇规模N或LUT大小K的变化，内部缓冲器尺寸会相应调整以优化延迟。路由架构参数（如线段长度、开关类型比例）参考了Betz等人对K=4, N=4架构的研究结论，并假设其适用于所有(K, N)组合，同时按逻辑块尺寸比例调整路由缓冲器尺寸。
3. 数据分析流程： 对于每个基准电路在每种(K, N)架构下的实现，记录两个主要指标：1）实现该电路所需的总面积（以最小宽度晶体管面积计）；2）关键路径延迟（纳秒）。最终结果是对28个基准电路在每种架构下所得面积和延迟的几何平均值。此外，还分解分析了总面积中的簇内（逻辑块）面积与簇间（路由）面积，以及总延迟中的簇内延迟与簇间路由延迟，以深入理解K和N的影响机制。
三、 主要研究结果 1. 簇输入数I的经验公式： 通过大量打包实验，确定了为实现98%逻辑单元利用率，簇所需输入数I与K和N的关系。结果表明，I值大约在最大可能输入数(K*N)的50%到60%之间。研究者通过观察数据拟合出一个经验公式：I = 2 * K + N。该公式与实验数据吻合良好，平均误差仅10.1%，为标准设计提供了重要指导。
2. 面积与K、N的关系： * 总面积趋势： LUT大小K为4和5时，在所有簇大小N下都表现出最佳的面积效率。K=2和3的小型LUT面积效率较差，这与早期某些认为其面积效率与K=4相当的观点相反。研究指出，早期研究可能因未使用先进的时序驱动打包和布局布线工具而高估了小型LUT的效率。 * 簇大小N的影响： 将N从1增加到3时，所有K值的总面积都有所下降，因为更多连接被吸收到簇内，减少了昂贵的簇间路由面积。然而，当N继续增大（>3）时，总面积下降非常有限甚至趋于平稳。这是因为簇规模增大会增加簇的输入/输出引脚数，导致所需的通道轨道数增加，抵消了内部化连接带来的路由面积节省，同时逻辑块自身面积也在增长。 * 面积分解分析： * 簇内面积： 随K呈指数增长（因为LUT大小为2^K），随N增大而线性增长。当K=6或7时，簇内面积成为总面积的主导部分。 * 簇间路由面积： 随K增大而线性下降。这与早期研究（Rose 1990）认为路由面积在K=4左右达到最小的结论不同。本研究解释为，K增大导致所需逻辑簇数量急剧减少（每个LUT功能更强），其速度超过了每个簇所需路由面积的增加速度，因此总路由面积下降。先进的CAD工具（能更有效地利用路由资源）和簇结构（将更多路由内部化）是导致这一新趋势的关键原因。
3. 性能（延迟）与K、N的关系： * 总延迟趋势： 关键路径延迟随K和N的增大而显著下降。例如，架构(K=2, N=1)的平均延迟为45纳秒，而(K=6, N=10)仅为14纳秒。 * 延迟分解分析： * 簇内延迟： 随K增大而下降。虽然单个基本逻辑单元（BLE）的延迟随K增大而增加（见表II），但关键路径上的BLE层级数减少得更快，因此总逻辑延迟下降。然而，对于固定的K，簇内延迟随N增大而增加，因为簇内多路复用器变大变慢。 * 簇间路由延迟： 随K和N的增大而下降。K增大减少了关键路径上的LUT总数，从而减少了所需的簇间路由跳数。N增大则将更多连接封装在簇内，减少了外部路由需求。 * 主导因素： 簇间路由延迟远大于簇内延迟，因此通过增大K或N来减少路由延迟是提升整体性能的主要途径。但研究也发现，当N超过3后，继续增大N对总延迟的改善非常有限。这是因为对于较大的N，进一步增加BLE难以保证减少关键路径上的簇层级数，特别是对于本身扇出（fanout）就较大的大型LUT（K值大）而言。
4. 面积-延迟乘积： 面积-延迟乘积综合衡量了架构的效率。结果表明，LUT大小K在4到6之间，簇大小N在3到10之间时，能获得最佳的面积-延迟乘积。K=2和3由于性能极差（延迟几乎是大型LUT的两倍）且面积并无优势，是非常糟糕的选择。K=7则因为巨大的面积开销超过了其性能增益，导致面积-延迟乘积急剧上升。
四、 研究结论与价值 本研究系统地评估了深亚微米工艺下FPGA逻辑块粒度（K和N）对面积和性能的影响，并得出了明确的设计指导结论： 1. 经验公式： 提出了簇输入数I与K、N的实用经验公式 I = 2K + N，可用于指导簇架构设计以达到高逻辑利用率。 2. 最佳架构范围： 对于追求最佳面积-延迟效率的FPGA设计，推荐使用4到6输入的LUT，并将3到10个这样的LUT组成一个逻辑簇。这为当代商用FPGA的架构选择（如广泛采用K=4, N=10或类似组合）提供了坚实的实验依据和理论解释。 3. 纠正旧有认知： 明确了小型LUT（K=2,3）在先进设计流程和簇结构下，其面积效率并不如以往认为的那样好，且性能严重不足，否定了其作为主流选择的合理性。同时发现K=5和6的面积结果比以往认知的要好。 4. 揭示内在机理： 通过将面积和延迟分解为簇内/簇间成分，深入揭示了K和N影响FPGA密度与性能的内在权衡机制：增大K和N主要通过大幅减少簇间路由（面积和延迟的大头）来提升效率，但会受到逻辑块自身面积增长和簇内多路复用器延迟增加的制约。
五、 研究亮点与创新 1. 全面性与系统性： 首次在深亚微米工艺背景下，对基于簇的FPGA架构进行了大规模、系统的参数空间探索（K=2-7, N=1-10），同时考虑了面积和性能两个维度。 2. 方法学严谨性： 采用了完全时序驱动的先进CAD流程，并基于精确的晶体管级SPICE仿真进行面积和延迟建模，充分考虑了深亚微米电气效应，使得结论更具现实指导意义。 3. 深入的分解分析： 不仅给出总体趋势，还通过将总面积分解为簇内/簇间面积，总延迟分解为簇内/簇间延迟，清晰地阐释了各种现象背后的根本原因，提供了深刻的架构洞察。 4. 提出实用设计公式： 推导出的簇输入数经验公式 I = 2K + N 对FPGA架构师具有直接的实用价值。 5. 指出未来方向： 基于结果提出了有价值的未来研究方向，例如：寻找在不付出大型LUT面积代价的前提下减少逻辑层级数的方法（暗示可能需探索异构LUT混合结构），以及如何降低簇内多路复用器的延迟。
六、 其他有价值内容 论文在最后讨论了实验结果的潜在局限性，体现了研究的科学性：1）结果依赖于所用CAD工具的质量；2）结果可能受所选基准电路类型影响；3）实验假设路由架构参数（如线段长度）对所有(K, N)组合均最优，而未对每个组合单独优化，这可能会影响不同架构间的相对评估结果，但因探索空间巨大，此简化是必要的。这些说明为正确理解和应用研究结论提供了重要背景。