恒达娱乐 > SEO算法 > 恒达注册登录以下五个FPGA布局布线算法领域的重要工作几乎奠定了现代

恒达注册登录以下五个FPGA布局布线算法领域的重要工作几乎奠定了现代

admin SEO算法 2020年04月12日

  很多世界顶尖的“建筑师”可能是你从未听说过的人,他们设计并创造出了很多你可能从未见过的神奇结构,比如在芯片内部的复杂体系。芯片的基本材料源于沙子,但芯片本身已经成为人们当代生活不可或缺的东西。如果你使用手机、电脑,或者通过互联网收发信息,那么你就无时无刻不在受益于这些建筑师们的伟大工作。

  FPGA是芯片的其中一种,从上世纪八十年代诞生起,FPGA 已经从简单的可编程门阵列,发展成为了有着大量可编程逻辑的复杂片上系统。除了硬件结构之外,FPGA 的开发工具和应用场景也都取得了长足的进步和扩展,FPGA 在整个半导体行业的重要性也在不断增强。FPGA 芯片的演进,离不开这些“建筑师”的不断发明创造。

  几年前,这些 FPGA 的顶级建筑师们选出了自上世纪九十年代起的 20 年以来 FPGA 领域最有影响力的 25 个研究成果。通过这些重要的成果,我们会理解 FPGA 是如何发展至今,并且知道 FPGA 技术未来将会发展向何处。

  这 25 个研究成果按研究领域分为架构、EDA工具、电路、应用等大类,每项成果都由一名该领域的顶级学者做推介。接下来,我将在几篇文章里,分别介绍这这些改变了 FPGA 发展进程的重要研究成果。本文是布局布线算法篇。关于 FPGA 架构领域的重要创新,请参见这两篇:《系统架构篇》和《微架构篇》。

  这项工作可以算是过去二十年中影响 FPGA 技术发展的最重要的成果之一。这项成果对工业界和学术界都产生了极其深远的影响。最重要的是,这个工作将 FPGA 的布线研究,从一个结果波动极大的问题,转化为一个能够很好控制的优化问题。时至今日,几乎所有的 FPGA 厂商都在使用这项工作提出的协商拥塞(NegoTIated CongesTIon)的布线算法,或者是由这个算法引申出来的其他布线方法。此外,学术界最为广泛使用的 FPGA 架构设计和分析工具 VPR,就是基于这项成果而开发的。

  通常来说,有些研究成果会立刻对学术界带来启发,而有些则会首先被低估一段时间,然后才会被人们完全理解。这项成果就属于后者。很多研究 FPGA 设计工具的工作都是提出一些新的想法,使用基准测试对这些想法进行实验,然后比当时的其他工作取得 5%到 10%的提升,诸如此类。并不是说这些工作不够优秀,但大多数的工作所取得的成就和影响都是暂时的,因为会不断出现新的 CAD 工作取得更好的结果。

  在 1995 年,大多数 FPGA 研究者都认为这项工作也只不过是又一个取得了 10%性能提升的成果,和其他研究并无二致。只有很少的人认识到,这项成果带来的是改变整个游戏规则的根本性创新,它将在今后的几十年里经受住其他工作的挑战,而且不会被其他布线算法所超越。幸运的是,在随后的几年里,学术界和工业界都渐渐认识到,这项成果所提出的理念已经达到了前所未有的高度。

  这项工作首先阐述了协商的基本思想,以及处理一阶拥塞的方法。然后分析了二阶拥塞,见下图,并引入了对“历史成本(history cost)”的需求。之后将这个概念进行了推广,并将布线延时引入考量。最后给出了这个算法的伪代码,以及一些实验结果。相比于当时的其他商用工具,这个方法能取得 11%的效果提升。

  客观的说,尽管这是一项出色的工作,但它在表述时的清晰程度并非完美。当你每次审视这项工作时,都能体会出一些细微的差别。

  时至今日,我们已经能够广泛而成功的使用协商拥堵算法来处理 FPGA 的布线问题了。尽管如此,这个方法为何如此有效,学术界在理论层面上仍然莫衷一是。例如,我们能完全理解和分析退火算法是如何工作和收敛的,但对于协商拥堵算法的理解还远远达不到这个层次。也就是说,人们还没有对这个思想构建起足够严谨的理论体系。因此,这项工作仍将继续激发研究者们对这一课题的进一步研究。

  这项工作在 VPR 中加入了对时序优先布线算法的支持,并对延时进行了精确估计。恒达注册登录这使得 VPR 可以对 FPGA 互联网络结构进行更加深入的研究。通常来说,FPGA 上 90%的面积都是用来进行可编程布线的,而关键路径延时里有 80%都是布线延时。因此,如何构建正确的 FPGA 互联网络,对于性能和资源消耗来说都是至关重要的。随着 FPGA 面积的不断增加,这一点更为明显,因为根据 Rent 法则,电路中导线数量的增长必须快于逻辑单元数量的增长。

  然而,架构师经常习惯于根据直觉和以往的经验做出决策,而不是根据基准测试和理论分析。CAD 工具通常针对单一架构进行优化,因此如果架构进行了变更,工具的性能和有效性就会不可避免的下降。此外,如果要量化互联对性能的影响,就需要有基于时序驱动的综合、布局和布线算法。

  这项工作在 VPR 中引入了一种用来精确估计延时的 Elmore 模型,并阐述了一种使用 VPR 对 FPGA 布线架构进行分析和评估的方法。这使得 FPGA 架构师可以通过一种架构描述语言(architecture description language),对 FPGA 架构进行建模和分析,然后工具就可以自动对这种架构进行适配。

  这项成果首先假设了一个传统的岛型 FPGA 架构,然后尝试使用最优的方法对连线进行分段,并将这些分段连接起来。通过使用 VPR,可以自动对大部分的参数空间进行探索,从而得到对于给定的参数的最优布线结果。

  这项成果最大的贡献在于它所使用的方法论和工具。仅仅在几年之后,Altera在构建 Stratix 架构时就采用了相似的设计方法,以及基于 VPR 的工具包。这进一步表明,创新既需要跳出固有的思维模式,也要使用先进的工具来评估这些新的想法,两者缺一不可。

  一句话总结:通过自动处理 FPGA 布线架构研究中繁琐的部分,推进了整个研究领域的跨越式发展。

  FPGA 的架构研究是非常复杂的,有的时候即使是为了回答最简单的问题,都需要付出相当程度的努力。在很多情况下,FPGA 架构师会认为他们的一些新想法,诸如更大的逻辑块、新型的进位链等等,理应会极大的提升系统的功耗、性能、面积、稳定性等指标。然而,为了证明这些想法的可行性,就需要设计工具和实际应用来对这些想法进行验证。同时,也需要结合很多和这些想法无关的 FPGA 架构细节,以组成一个完整的系统。在工具层面,大名鼎鼎的 Pathfinder 和 VPR 的出现,已经为大多数逻辑映射工作提供了一个稳定而高效的后端平台。

  然而,对于 FPGA 互联架构来说,仍然有着很多细节问题需要注意。例如,连线长度、互联方法、逻辑块结构,等等。这些问题往往与希望研究的主要问题无关,但都是必须统筹考虑的问题。尽管单向导线(unidirectional wires)也许是个好的想法,但如果我们将其用于所有的互联节点,那么面积和容抗的增加将迅速掩盖这个想法带来的优点和好处。那么,如果我们只将其用于 50%的互联节点,然后将所有的逻辑块输出连接到奇数号导线、将所有逻辑块输入连接到偶数号导线呢?如果我们又想到了其他的互联架构和方式呢?在这项成果面世之前,这些问题都是无法求解的。

  因此,解决这类问题的重点,是这项成果所展示的架构描述语言,以及 VPR 中的架构生成器。简单来说,这项成果专注于处理那些布线架构中没人关心、但却非常重要的细节问题,比如:逻辑块是如何连接的?如何保证连线之间的交互不会对系统产生不确定影响?交换架构是如何组织排列的?当设计中存在长导线时,如何保证这条穿过芯片多个区域的连线以合理的方式进行分段?……等等等等。而这项成果就是用来解决这些在 FPGA 架构研究中的细微问题。

  正是如此,尽管这项工作并没有专注于架构研究的重点和流行的部分,但它极大的帮助了这个领域向前推进了一大步。通过提供更加高效的工具,这项工作使研究人员更有生产力,从而在另外一个角度帮助 FPGA 架构研究带来了大量创新。

  众所周知,VPR 是 FPGA 学术界最流行的开源 CAD 软件,几乎每个新的 FPGA 架构研究都使用了 VPR。而这项成果就详细阐述了在 VPR 中使用的时序驱动的布局算法。在这项成果中介绍的 T-VPlace 算法,除了广受好评和广泛使用之外,它还对 FPGA 的布局算法有着三个重要的贡献。

  第一,在 T-VPlace 算法中,时序优化的过程是通过最小化延时与导线长度的加权和实现的。这个计算过程通过一个基于模拟退火(simulated annealing)的优化引擎完成。其中,每个节点的权值是该节点时序临界性的多项式函数。这项工作的结果表明,这种权值函数能够得到很好的时序收敛。此外,导线长度和时序都可以根据前一次的迭代进行自主归一化,这使得算法有着很好的稳定性。

  第二,这项工作表明,每个节点的时序裕量(timing slack)不需要随着逻辑单元的移动而不断更新。只需要在对每个温度进行的迭代完成之后,再进行精确的基于路径的时序分析即可。使用未更新的时序裕量通常并不会对时序优化造成影响,反而会大幅提升 T-VPlace 算法的性能和效率。不过,后来的工作也表明,在高度流水线化的设计中,如果使用未更新的时序裕量会对性能造成负面影响。

  第三,在一个给定的分段可编程互联架构中,在源 - 汇节点间的延时不能简单的通过其曼哈顿距离来估计。然而,恒达娱乐如果在布局期间使用一个布线器来计算每个源 - 汇节点之间的延时也是非常不现实的。因此,通过利用 FPGA 架构中的对称性,T-VPlace 算法使用了一个预先计算的延时查找表,根据水平和垂直方向的距离作为索引,从而实现对延时的快速查找。

  通过以上三种技术,使得 T-VPlace 可以高效的产生高质量的时序优化结果。事实上,前两种技术同样可以被应用于集成电路设计中的标准单元布局。可以说,T-VPlace 算法是现代 FPGA 布局布线算法的基石。作者所在的 RightTrack 公司在 2000 年被 Altera 收购后,T-VPlace 及其优化技术就被整合进 Altera 的Quartus设计软件中,并被世界上成千上万的 FPGA 设计者所使用至今。

  FPGA 业界当前面临的最关键的问题之一是设计工具编译的时间过长,这一方面是由于计算机处理器的性能并没有质的飞跃,另外一方面是由于 FPGA 的大小随着半导体制造工艺的发展而不断增加。为了应对这个问题,一个有效的方法是使用多个处理器核心进行并行编译。

  这项成果旨在应对 FPGA CAD 流程中最慢的部分之一,即布局的并行化问题。在这个工作中,采用了几项非常独特而重要的方法。例如,这是目前首个,也是唯一一个尝试对工业级布局软件进行并行化的工作,并最终将成果转化为成功的商用软件。在此之前,尽管有很多工作试图对布局算法做并行化处理,它们其实都是基于学术版本的算法,也就是说,这些工作并不需要应对海量的器件数据库、复杂的时序分析、以及在商业版软件中会遇到的各种细节问题。

  此外,这项工作对算法的确定性(determinism)做了重要阐述。算法的确定性指,不管使用多少个处理器运行算法,它的结果都会是完全相同的。尽管在学术界中存在争议,但在商业软件中确定性对于复现结果以及调试都是不可或缺的。这项成果表明,需要做一系列细致的工作以保证算法的确定性。此外,这项成果也证明了这些工作对性能的损失很小。

  这个工作还就内存架构对并行算法性能的影响进行了深入分析。值得注意的是,它表明不同的内存结构对算法性能的影响很大。

  总体来说,这项成果对算法性能取得了很大的提升:在布局阶段,使用 4 个处理器内核可以得到 2.2 倍的性能提升。对于大型设计,这样的性能提升会节省好几个小时的运行时间。在一个完整的 FPGA 编译流程中,还存在着很多耗时的阶段,这也意味着需要做更多的工作,才能最终将 FPGA 项目的编译时间进一步缩短。但是,这个成果为实现这一目标做出了巨大的贡献,也是其他后续工作值得参考的典范。

  这五个 FPGA 布局布线算法领域的重要工作,有的奠定了几乎所有现代商用 FPGA 的布线算法基础,有的大幅改进了 FPGA 布局、布线、时序优化等环节的算法性能,有的则对 FPGA CAD 软件进行了跨越式提升。更重要的是,这些工作所采用的方法论、思维方式、前瞻性与实用性的统一、以及严谨的治学态度,都为之后的学术和工业研究树立了最高的典范。

  感谢大家对Mil往期FPGA直播的支持!最后一期,大家要继续加油哟!关于直播中,Mill老师有提到的FPGA众筹,为大家

  FPGA中乘法器是很稀缺的资源,但也是我们做算法必不可少的资源。7系列及之前的FPGA都是25x18....

  做深度学习加速器已经两年了,从RTL设计到仿真验证,以及相应的去了解了Linux驱动,深度学习压缩方....

  之前最主流的是GoogLeNet,1年半到2年后是ResNet,现在ResNet是最尖端的技术,但是....

  几年前,这些 FPGA 的顶级建筑师们选出了自上世纪九十年代起的 20 年以来 FPGA 领域最有影....

  如题。 补充几个图//----------------------------------------- 这个目录上Static Timing的图标都和其它的不一...

  比较器将网线传输过来的差分信号转为单端信号,该信号时钟频率为100M,电平标准能满足FPGA的输入电平标准,波形质...

  MathWorks宣布,HDLVerifier从现已上市的Release2019b开始提供对Univ....

  平台计算机采用FPGA+S698IP核的方案(简称SOC),以欧比特公司的S698IP核做为主CPU....

  目前,图片处理的需求正在快速成长,即源于用户生成内容,视频图片抓取等方式的图片缩略图生成,像素处理,....

  我有一块带有Spartan 6 FPGA和SPI闪存的电路板。 当我在GUI模式下编程闪存时,它工作正常。 但是当我使用...

  [tr])写了这样的一个乒乓操作: while(pingpong_buffer_num UPID0 = (U...

  LED大屏幕显示系统由上位机(PC机)、单片机系统、FPGA控制器、LED显示屏的行列驱动电路等模块....

  2020全网首发《60天FPGA工程师入门就业项目实战特训营》 FPGA就业培训班带你深入全面掌握FPGA。让理论与...

  FPGA(Field-Program mable Gate Array),即现场可编程门阵列,它是在....

  近年来,随着可编程逻辑器件(CPLD/FPGA)的迅猛发展,可编程逻辑器件在数据采集、逻辑接口设计、电平接口转换...

  用FPGA做的MCU内核的汇编指令集完全解析,FPGA使用VHDL编写MCU内核,使用PHP编写汇编器,使用vc...

  同时发布符合开放计算项目 3.0 ( OCP3.0)尺寸规格的以太网适配器,以及世界首款基于FPGA....

  市场渗透率如此之高,全球对大电流低压数字IC的需求激增也就不足为奇了。当前全球市场规模预估超过18亿....

  在数字通信、卫星通信等系统中,不同程度的存在回波现象,影响了通信质量。为了消除回波可以采用回波抵消器....

  IIR数字滤波器在很多领域中有着广阔的应用。与FIR数字滤波器相比,它可以用较低的阶数获得高选择性,....

  FPGA是一种高密度的可编程逻辑器件。经过20多年的发展,FPGA的逻辑规模已经从最初的1000个可....

  运动估计主要是针对帧间预测,去除视频帧在空间域和时间域的冗余度。块匹配方法是目前编码效率较高,普遍采....

  DPA的主要缺点是每个电源“砖”都包含隔离,这会降低效率,并增加尺寸、成本和复杂性。随着大多数DPA....

  目前,无线产品的广泛应用使无线音频和视频的高质量传输成为可能。蓝牙、无限局域网等无线传输设备比较复杂....

  传统的正交下变频是通过对模拟I、Q输出直接采样数字化来实现的,由于I、Q两路模拟乘法器、低通模拟器本....

  据了解,FPGA芯片的技术门槛非常高,一直处于美国公司的垄断之下。处于领跑地位的赛灵思在该领域深耕了....

  我刚刚涉及到FPGA,导师让做“基于zigbee的智能宿舍”课题,不知道怎么选择FPGA开发板,求大佬推荐!!!...

  MLP全称Machine Learning Processing单元,是由一组至多32个乘法器的阵列....

  所谓中频,顾名思义,是指一种中间频率的信号形式。中频是相对于基带信号和射频信号来讲的,中频可以有一级....

  异步串行数据接口要求接收器恢复数据,方式是对比特流进行检查,并在所发送数据未附带时钟时确定每个位的采....

  图2列出了和传统的4输入LUT结构的FPGA相比较,采用ALM的StratixⅡFPGA器件例化3输....

  在较长的一段时间内,脉冲重复频率跟踪器技术都是基于ISA总线且建立在分立式IC器件架构之上,存在着元....

  低密度奇偶校验(Low Density Parity Check Code,LDPC)码是一类具有稀....

  上次提出了一个处于异步时钟域的MCU与FPGA直接通信的实现方式,其实在这之前,特权同学想列举一个异....

  随着测控技术及数字图像处理技术的高速发展,基于三角法线结构光的三维测量具有高精度、非接触、实时性和强....

  Wilson Research Group 的一项最近研究发现,48% 的 FPGA 设计项目和 7....

  引言 Internet 的快速发展和成功促进了以太网(Ethernet)技术的发展和应用的扩展,所涉....

  对于工程师而言,设计、评估和调试带有模拟输入/输出(I/O)接口的混合信号电路始终面临巨大挑战。

  波形相位频率可调DDS信号发生器(设计分享) --作者:造就狂野青春 本文为明德扬原创及录用文章,转载请注明出...

  关于锁存器问题的讨论 很多同学提问到锁存器的相关问题,说明大家对这方面知识还不是很了解,今天我们就...

  2020 年 2 月 27 日– MathWorks 宣布,随着 2019b 发行版的 MATLAB....

  当我们谈论物联网 (IoT) 的时候,不夸张地说,它可以将我们所使用的智能设备互相连接,彼此分享大量....

  人们很难预测哪些新技术会带来机器视觉发展的下一个突破,它可能来自多年学术研究的结果,或仅仅来自一个简....

  Achronix 最新基于台积电(TSMC)的7nm FinFET工艺的Speedster7t FP....

  近段时间微信工作群最火的接龙莫过于“体温接龙”,一场来势汹汹的疫情让“测温”成为日常生活的一部分,更....

  AI芯片设计大厂莱迪思半导体(Lattice Semiconductor),基于本身Nexus技术平....

  Vision HDL Toolbox 自动生成经过 FPGA 验证的代码,适用于高达 8k 分辨率的....

  2020年伊始,新型冠状病毒肺炎突然爆发并迅速蔓延,严格的防控措施成了这场战“疫”的关键。

  广东高云半导体科技股份有限公司(以下简称“高云半导体”)将于2月25日至27日在德国纽伦堡参加Emb....

  自动驾驶域控制器,要具备多传感器融合、导航定位、路径规划、计算决策、V2X无线通讯、运动控制的能力。

  呼吸机是可以完全替代病人的呼吸或实现辅助呼吸功能的仪器,适用于呼吸衰竭,甚至停止呼吸的病人,它能帮助....

  将GDDR6的优势从图形计算扩展至高性能网络应用?下文主要介绍Achronix Speedster7....

  最近几年,FPGA这个概念越来越多地出现。例如,比特币挖矿,就有使用基于FPGA的矿机。还有,之前微....

  从业者认为,5G 时代和工业领域最相关的技术就是边缘计算。其实,得益于技术本身拥有的及时处理和分析功....

  AI芯片设计大厂莱迪思半导体(Lattice Semiconductor),基于本身Nexus技术平....

  创龙结合TI KeyStone系列多核架构TMS320C6678及Xilinx Kintex-7系列....

  现场可编程门阵列(FPGA)技术不断呈现增长势头。 1984年Xilinx刚刚创造出FPGA时,它还....

  近日,赛灵思VP(副总裁)DanGibbons一行到访北京深维科技,在CEO樊平及深维核心团队成员的....

  随着互联网的发展,人类进入了网络化、数字化的时代。在三网融合的政策背景下,数字电视信号的网络传输得到....

  在GTC19大会期间,NVIDIA 加速计算产品管理总监Paresh Kharya对关于GPU相比F....

  一直以来,FPGA 的主要应用领域是电子工程。但当英特尔完成对 Altera(Altera 是最大的....

  本文在研究航空全双工交换式以太网(Avionics Full Duplex Switched Eth....

标签: 现代优化算法