基于最小自由度优先原则的任意多边形模块布局算法

给出了直角多边形模块自由度的定义和公式,扩展了最小自由度优先原则,使算法能够处理任意直角多边形模块以及有相对约束的模块.实验结果说明该方法在布局效果和效率上都有良好的表现.     

利用公共子序列求解固定边框布图问题

提出一种新的固定边框的布图算法．该算法采用SP表示方法，以公共子序列为基础，在随机搜索过程中限定布图宽度的变化，从而使减小芯片面积的目标与固定边框的目标在一定程度上取得一致．与现有的固定边框布图算法相比，文中算法在边框更紧凑、宽长比更大的条件下具有更高的成功率和更短的运行时间．此外，文中算法在布图初始阶段就可以对固定边框的合理性进行评估，避免了因给定的边框不合理而带来的时间上的浪费．     

Deterministic VLSI block placement algorithm using Less Flexibility First principle

In this paper,a simple while effective deterministic algorithm for solving the VLSI block placement problem is proposed considering the packing area and interconnect wiring simultaneously.The algorithm is based on a principle inspired by observations of ancient professionals in solving their similar problems.Using the so-called Less Flexibility First principle,it is tried to pack blocks with the least packing flexibility on its shape and interconnect requirement to the empty space with the least packing flexibility in a greedy manner.Experimental results demonstrate that the algorithm,though simple,is quite effective in solving the problem.The same philosophy could also be used in designing efficient heuristics for other hard problems,such as placement with preplaced modules,placement with L/T shape modules,etc.     

力驱动三维FPGA布局算法

三维FPGA布局问题的复杂度与二维情况相比成指数倍增长,布局算法需要花费大量时间,影响了FPGA物理设计效率.为了在保证布局质量的前提下缩短布局时间,提出以线长为优化目标基于力驱动的三维FPGA布局算法——3D-WFP.该算法由整体布局、坐标合法化和层划分、布局优化3个阶段组成,通过力驱动算法快速形成整体布局,为后续2个子过程提供更精确的逻辑单元位置和时延信息.提出三维空间填充曲线,根据位置和时延信息依次对逻辑单元按照三维空间填充曲线进行坐标合法化和层划分;修正了低温模拟退火进行布局优化的解空间,大大加快了低温模拟退火的收敛速度.与已有的三维FPGA布局算法比较,3D-WFP在保证运行时间和时延性能的前提下,有效地缩短了最终布局结果,缩短的总线长达7.38%.     

专用实时系统的系统级设计方法

1 系统级设计复杂的计算机应用,如嵌入控制、信号处理、自动化、计算机实时图象生成等,所要求的系统往往是专用实时系统,且具有分布、复杂、并发等特点。一个专用实时系统通常包含了通用硬件、软件,专用硬件、软件,并通过一系列传感器,执行机构与环境发生交互作用。在系统设计之初根据设计需求为这种系统建立一个概念模型是至关重要的。作为文档它不但要被来自不同的工程领域的设计参与者所理解,而且应成为专用实时系统硬件和软件设计的良好起点。系统的概念模型最终将转换成系统设计方案并付诸实施。为了获得对系统行为的深入了解并确认系统的设计和实现满足了系统的设计需求,应能对系统的概念模型及由概念模型得到的系统实现进行分析。     

基于角模块布图表示的增量式布图规划算法

提出了一种基于CBL布图表示的新的增量式布图规划算法.该算法能很好地解决包括不可二划分结构在内的布图规划问题.针对现有增量式的一些需求,算法给出了相应的高速解决方案.在已有的初始布局的基础上,基于CBL表示方法建立水平约束和垂直约束图,利用图中关键路径和各模块之间的累加的距离松弛量进行增量式操作.对于新模块的插入,在力求面积最小,线长最短和移动模块数目最少的目标指引下能快速地找到最佳位置作为插入点,高效地完成相关操作,算法的时间复杂性仅为O(n).通过对一组来自工业界的设计实例的测试结果表明,该算法在保证芯片的面积、线长等性能不降低甚至有所改善的情况下,运行速度相当快,仅在μs量级,满足了工业界对增量式布图规划算法在速度上的首要要求,同时保证了基本性能的稳定.     

面向应用的片上网络的网络拓扑生成算法

针对面向应用的片上网络,提出了一种三阶段的低功耗网络拓扑生成算法.首先基于内核通信量和物理坐标信息做划分驱动的布图规划,以确定内核的摆放位置以及内核和转换器之间的映射关系;其次考虑转换器和网络接口的面积消耗,并把它们的同时插入问题抽象成整数线性规划模型,通过求解此优化模型确定其最佳插入位置,生成互连网络;最后通过路由分配策略确定互连网络上的通信量分布,进一步优化功耗.实验结果表明,该算法平均能节省35.2%的功耗开销以及5.7%的中转转换器数目.