非默认规则线技术下基于多策略的时延驱动层分配算法

层分配作为超大规模集成电路物理设计中的关键环节,在决定布线方案的时延起到非常重要作用.为了优化集成电路的时延性能,现有的层分配工作通常注重优化互连时延和通孔数量,但要么未考虑到对线网中时序关键段的分配问题,要么对线网段的时序关键性的表示不够合理,最终使得算法的时延优化不够理想.为此,本文提出一种非默认规则线技术下基于多策略的时延驱动层分配算法,主要包含4种关键策略:(1)提出轨道数感知的层选择策略,增强层分配器为线网段选择合适布线层的能力;(2)提出多指标驱动的初始线网排序策略,综合考虑线长、信号接收器数和可布线轨道资源等多个指标为线网确定层分配优先级,从而获得高质量的初始层分配结果;(3)提出线网段调整策略,通过重绕线网,将时序关键段调整至上层布线层,优化线网时延;(4)提出线网段时延优化策略,对存在溢出线网进行拆线重绕,从而可同时优化时延和溢出数.实验结果表明,本文提出的算法相比于现有的层分配算法能够在时延和通孔数两个指标上均取得最佳,并且保证不产生溢出.     

考虑通孔电阻和耦合电容的时延驱动的层分配算法

针对集成电路设计的多层布线问题,提出了以直接优化互连时延为目标、同时考虑通孔电阻与耦合电容的层分配算法.通过基于路径的时延分析寻找电路的关键路径,以通孔的时延模型和概率耦合电容模型作为层分配模型计算资源分配的代价,利用基于启发式的贪婪算法进行层分配.实验结果表明:该算法比只控制通孔和耦合电容数量的层分配策略具有更大的优势.     

DrPlace:基于深度学习的可布线性驱动布局算法

在集成电路物理设计的布局阶段,针对基于深度学习的布局算法结果可布线性较差的问题,在开源的DREAMPlace算法的基础上提出并实现了一种基于深度学习的可布线性驱动布局算法DrPlace.算法模型在总体上设计并实现了布局器的整体框架,集成了基于深度学习的可布线性驱动总体布局、可布线性驱动的合法化和详细布局.总体布局过程中,在目标函数中加入了引脚密度函数,并实现了基于GPU的引脚密度的关键内核.在ISPD2011和DAC 2012布局实例上的实验结果表明,该算法与DREAMPlace相比在可布线性上获得了提升,且在运行时间、线长和可布线性方面均优于传统的可布线性驱动布局算法.     

一种减少重复搜索的FPGA快速布线算法

为了提高FPGA布线的运行速度,提出一种减少重复搜索的快速布线算法,该算法分为布通驱动布线算法和时序驱动布线算法.在布通驱动布线算法中,通过把线网的布线路径转换成连接的布线路径来判断每条连接的路径中是否存在拥塞节点,如果存在,保留其布线路径,否则重新进行搜索;时序驱动布线算法采用临界度判定机制来平衡运行速度和时序性能之间的比重.实验结果表明,与公认的VPR布线算法相比,布通驱动布线算法和时序驱动布线算法的运行时间分别平均减少了95.19%和28.98%,且时序驱动布线算法的关键路径延时减少了4.80%.     

矩形Steiner最小树布线灵活度

矩形Steiner最小树(RSMT)的布线灵活度影响其结构变形能力,直接影响芯片布线的收敛性.文中从树边形态、结构固有变形和拓扑变形3方面对线网的RSMT的布线灵活度进行刻画,给出了更能反映RSMT结构变形能力的计算模型.针对布线灵活度的"瓶颈"问题,提出了拥挤驱动的RSMT布线灵活度挖掘算法:根据树形的最短布线路径布线可能情况,定义了树边的布线灵活度;进而考虑RSMT结构中所有树边布线灵活度的组合情况和RSMT拓扑的变形性,得到RSMT布线灵活度.实验结果表明:将计算模型应用到拥挤驱动的RSMT布线灵活度挖掘算法,良好地改善了布线拥挤;将该挖掘算法应用到FastRoute4.1总体布线算法中,能够缩短14%的运行时间.     

预先指定单元位置的时延驱动布局优化方法

为了在时延驱动的布局算法中减少关键路径的数量,提出一种预先指定单元位置的基于线性规划优化时延驱动的布局方法.在全局布局每次迭代优化后提取关键子电路,建立子电路的时延模型;应用线性规划优化并移动子电路上各单元位置形成新的初始布局,进行下一次布局迭代.将该方法嵌入到力指向的布局器Kraftwerk中的实验结果表明,最小负时延裕量提高了21 ps,负时延裕量总和平均提高了483 ps,同时线长仅增加了0.83%.     

一种时延驱动的跨层路由方法

针对武器协同数据链对低时延数据传输的特殊需求,提出了一种基于时延驱动的跨层路由模型和路由方法（Delay-Driven Cross-Layer Routing,DDCR）。在该模型中,利用临近节点反馈信息以及层间的信息交互,使节点能够选择具有最小时延的下一跳。仿真验证表明,与Bellman-Ford最短路径路由算法相比,提出的方法显著降低了网络端到端时延,从而满足了武器协同级别的路由需求。     

基于VPR的FPGA布局算法时延改进

基于模拟退火的现场可编程门阵列(FPGA)布局算法在计算关键度时存在一定的偏差。为此,提出一种FPGA布局时延改进算法。利用不同的模拟退火温度和交换接收率,以及前后2次布局的时延代价差,对FPGA布局的时延代价进行补偿。通过增加时延补偿模块来调整布局的代价函数,达到重新寻找布局过程中被遗弃的较优解的目的。实验结果表明,在MCNC基准电路上使用改进算法,布局的时延代价和线网代价分别比改进前的算法减少19.2%和0.5%。此外,电路的关键路径时延也得到了不同程度的改善,使得布局质量在各个方面都明显优于优化前的通用布局布线算法。     

计数器驱动的IEEE 802.16e休眠模式研究

为了降低移动终端的能量消耗以及对基站空口资源的占用,IEEE 802.16e标准定义了休眠模式。针对计数器驱动的休眠工作模式与IEEE 802.16e标准不能较好兼容的局限,提出了改进的计数器驱动休眠算法,建立马尔可夫链模型分析其性能,推导出平均时延、平均功耗与计数器门限值等参数之间的内在关系,在此基础上给出了不同QoS要求的连接所对应的参数设置方案。     

DiffServ中基于优先级的队列调度算法

为了提高DWRR算法的时延性能及应对突发流的能力,文中结合比例时延区分服务模型,在DWRR算法的基础上提出了一种能够体现优先级的队列调度算法-PDDRR。该算法的控制目标是保证各业务流的平均排队时延在无突发业务流时维持在给定的比率,而在应对突发流时忽略时延的比例公平原则,根据网络实时负载动态地调整各队列的权值,合理地分配资源。仿真结果表明,算法不仅能实现不同优先级业务的时延区分,而且在业务流突发时为各等级业务提供服务质量保证。     

基于非hanan点的时延约束最小斯坦那树生成方法

介绍了一个基于非hanan点的时延约束最小斯坦那树生成方法,该方法引入非hanan点的概念,可以得到长度费用优化较好的布线树.     

基于延迟敏感的组播路由遗传算法的研究

1 引言为了保证多媒体实时业务流的QoS传输,所采用的路由技术之一是通过组播路由(multicast routing)为实时应用寻找最佳路径。以往,人们对非受限组播路由问题研究较多,但由于它们都未考虑QoS的延迟标准,因此,对多媒体实时传输的要求显得束手无策。Widyono阐述了受限Bellman-Ford(CBF)算法,它的性能较优,但其计算时间随着网络规模的增大而呈指     

机会网络典型路由算法性能分析

通过对真实城市场景中行人移动行为的仿真,定量分析First Contact、Direct Delivery、Epidemic、Spray and Wait、Prophet和MaxProp6种机会网络典型路由算法在不同场景下的性能。在仿真过程中,以不同节点密度、不同节点移动模型和不同节点缓存大小设置多种场景,从传输能力、传输效率、网络资源开销和节点能耗4个方面对路由算法进行分析和比较。实验结果表明,节点移动模型、节点密度等因素会对路由算法产生显著影响,各路由算法在不同的场景下性能差距较大,每种算法都有其适用的特定场景。     

一种线长和时延双重驱动的布局算法

针对标准单元模式的超大规模集成电路布局问题,本文提了一种新的基于线长和时延双重优化目标的布局算法。在以优化线长为目标函数的布局结果基础上,进一步优化了芯片的时延特性,并通过算法设计较好地解决了二者优化方向的一致性。通过标准单元测试电路的实验结果比对,该算法在线长及时延优化方面综合性能良好。     

基于Boole过程的考虑互连延迟的逻辑电路波形模拟中的关键问题

论文运用Boole过程论中对逻辑电路进行描述和计算的基本思想,较好地解决了逻辑电路波形模拟中的冒险检测与消除、反馈环路处理、伪路径识别和惯性延迟冲突等关键问题。在此基础上,面向详细布线提出RC延迟与动态加载串扰相结合的互连线延迟计算方法,并将其融入到基于Boole过程的波形模拟算法中。论文充实和完善了基于Boole过程的波形模拟算法,改进了其中的不足之处,扩展了Boole过程的应用。     

一种基于带宽和时延的流量工程动态路由选择算法

在流量工程的路由选择模式中动态路由选择算法最重要。本文研究了多种动态路由选择算法后，提出了一种基于带宽和时延的流量工程动态路由选择算法，并通过实际仿真，验证了该算法的有效性和便利性。     

基于强化学习的SDN路由优化算法

针对SDN控制器中网络路由的优化问题,基于强化学习中的PPO模型设计了一种路由优化算法。该算法可以针对不同的优化目标调整奖励函数来动态更新路由策略,并且不依赖于任何特定的网络状态,具有较强的泛化性能。由于采用了强化学习中策略方法,该算法对路由策略的控制相比各类基于Q-learning的算法更为精细。基于Omnet++仿真软件通过实验评估了该算法的性能,相比传统最短路径路由算法,路由优化算法在Sprint结构网络上的平均延迟和端到端最大延迟分别降低了29.3%和17.4%,吞吐率提高了31.77%,实验结果说明了基于PPO的SDN路由控制算法不仅具有良好的收敛性,而且相比静态最短路径路由算法与基于Q-learning的QAR路由算法具有更好的性能和稳定性。     

无线移动自组织网路由协议性能研究

路由是无线移动自组织网的关键技术之一。目前已经提出的MANET路由协议有很多种，因此如何针对一定应用场景选择一个最佳的路由协议，是人们十分关心的一个问题。该文对已经通过IETF认可的三种MANET路由协议：DSR、AODV和OLSR进行了仿真对比分析。设计了大量的场景，通过对路由协议的分组传送率、端到端时延和所选路径长度等指标的比较，得出了在不同的网络环境下MANET最佳路由协议选择方案。仿真中发现同是采用按需的路由发现策略的DSR和AODV在高移动、高负荷的网络环境下的性能存在较大差异，对此原因进行了深入分析，并根据分析对DSR提出了改进方案。     

不规则网络中基于拐弯模型的路由算法的设计

由虫孔路由交换器连接而成的不规则拓扑网络，越来越多地用于构建工作站机群系统（NOWs），以实现高性能价格比的并行处理．采用虫孔路由技术，网络中容易发生死锁．交换器之间连接的不规则性，使路由避免死锁问题变得更加复杂．本文给出了在不规则网络中，设计基于拐弯模型的无死锁路由算法的一般方法，并采用扩展链路方向的方法得到多种路由策略，确定了up-first与down-last两种性能较优的路由算法．最后通过模拟实验，评价了算法的性能．     

基于群组移动模型的OLSR协议性能仿真与评估

在研究移动自组网移动模型和无线路由协议的基础上,选取移动自组网中具有代表性的参考点群移动模型,基于ns2网络模拟平台,以参考点群组移动模型生成移动场景文件,应用层使用cbr数据流量,对OLSR无线路由协议在不同参数条件下的性能进行了模拟测试。通过对测试结果数据的详细分析,总结得出了OLSR无线路由协议在参考点群移动模型下端到端时延、报文交付率和路由负载三个方面的特点。为进一步研究移动自组网下基于OLSR协议的各种应用提供参考。