芯片级布图规划中的缓冲器规划算法

文中对纳米技术下, 互连驱动的芯片级布图规划问题中的缓冲器规划问题进行了研究, 提出了基于空白区重分布(redistribution)的缓冲器规划算法; 布局中的空白区是指在布局中不被任何电路模块占用的闲置区域; 该算法充分利用布局中的空白区插入缓冲器. 在基于拓扑的布图规划表示中, 可以把电路模块和空白区相关联, 在相应区域内移动一些电路模块就可以达到重分布空白区的目的. 在进行空白区重分布的过程中, 给定布局的总面积和拓扑结构将维持不变. 通过重分布布局中的空白区, 可以增加满足时延约束的线网数目; 实验证实, 满足时延约束的线网数的增长率平均达到9%.     

优化时延和可布性的标准单元布局算法

分析了时延和可布性的关系, 提出了一个多步的布局算法来优化这两个目标. 首先, 时延驱动的布局算法找到一个全局最优解. 在第二步中, 本算法在保证不破坏时延特性的基础上提高芯片的可布性. 这个算法已经实现, 并且对若干实际电路进行了测试. 结果表明应用本布局算法最大时延值能够下降30%, 并且第二步中在保证时延值不变的情况下, 最大拥挤度下降10%.     

吸气式空空导弹FADS系统设计

分析了吸气式空空导弹FADS系统设计面临的关键技术难点及设计流程.针对吸气式空空导弹大长细比布局、高机动、大攻角和低成本控制等特点,提出了一种高精度、多点故障诊断、容错和可抗大过载的FADS系统设计方法.主要包括基于压力模型、分层诊断和多模型重构容错策略的求解算法设计、系统误差模型设计、高精度和抗大过载压力测量模块设计、以及解算机模块设计等.针对某典型吸气式空空导弹外形设计了9个测压点布局、飞行马赫数2.0~4.5的FADS系统原理样机,在1.2 m×1.2 m超声速风洞完成原理样机的实时解算试验,试验结果表明:静压测量相对误差≤6.9%,马赫数测量误差0.1,攻角和侧滑角的测量误差均1°.重构模型的测量误差接近基准模型的误差;算法诊断故障点数≤3,故障诊断的范围是P1点的偏差≤-20%或≥40%,P2~P9点的偏差≤-30%或≥30%,算法具有≤2故障点的容错能力.系统的测量误差水平、故障诊断和容错能力均能满足工程要求.     

基于置换图的便笺存储器分配

在当今的嵌入式系统中,广泛地将片上存储器组织为软件管理的便笺存储器(SPM).Li等研究发现,对于很多嵌入式应用,其相干图中的数组生存期满足包含性.他们证明了满足生存期包含性的数组相干图为超完美图,并提出了一个基于超完美图的SPM分配算法.他们的算法在面向嵌入式应用的SPM分配上获得了当前最好的性能.本文进一步证明满足生存期包含性的数组相干图为置换图.置换图是超完美图的一个子类.在现有技术的情况下,置换图在判定及区间着色方面比超完美图有优势,如存在线性时间的识别算法,存在线性时间的最优区间着色算法.基于此理论结果,我们将Li等的算法在保留原算法逻辑的基础上,改进为基于置换图.实验表明,改进后的算法在很多不满足生存期包含性的相干图上仍能取得最优SPM分配,获得比基于超完美图的分配算法更好的分配结果.     

用合成孔径雷达(SAR)单次飞行全极化图像数据进行地面数字高程(DEM)反演

在合成孔径雷达(SAR)空对地观测中, 倾斜地表面的同极化回波极大值所对应的入射波极化的取向角ψ≠0. 由ψ≠0迁移, 通过二次相干飞行SAR或干涉SAR(INSAR)图像可确定地表面坡度与反演地面数字高程(DEM). 用全极化散射Mueller矩阵解, 将ψ≠0的迁移表示为SAR测量的散射Stokes参数I_vs, I_hs, U_s的函数. 通过Euler角变换, 把ψ迁移与倾斜地表面的水平方位角、射程角以及SAR观测的几何结构联系起来. 在只能获得单次飞行SAR数据的情况下, 提出用倾斜地表水平方位排列产生的图像纹理作形态学细化算法来确定水平方位角. 这样用一次飞行的SAR图像数据, 可确定水平方位角和射程角及其坡度分布, 用完整多重网格算法数值求解地面高程的Poisson方程, 得到地形DEM的反演.     

一种实用的互联网络拓扑结构RP(k)及路由算法

提出了一种基于Petersen图的互联网络RP(k), 研究了该互联网络的性质, 它具有良好的连接度、短的直径和简单的拓扑结构. 在节点小于300的情况下, RP(k)的直径低于Torus的直径, 其最优分组的距离小于Torus最优分组的距离, 特别是当分组节点数m满足6≤m≤100时,RP(k)最优分组的距离近似等于Torus最优分组距离的一半. 基于Petersen 图结构, 设计了点点通信、置换路由、广播路由和多对多路由算法, 它们的通信效率分别为[ k /2]+2,k+5,[k/2]+2和k+5.     

基于搜索空间缩减策略的供水管网抗震设计参数优化

供水管网抗震优化设计模型以用户节点的抗震安全能力为设计目标,包含管网拓扑布局及管段结构抗震能力两个设计参数,寻找最优设计参数是离散变量组合优化问题.提出了一种基于两阶段搜索空间缩减策略的管网抗震优化设计模型求解方法,第一阶段利用度约束连通图生成初始种群,缩小优化初始搜索空间;第二阶段采用违约个体修补策略转换优化进行过程中不满足约束条件个体所处的搜索空间,实现了优化过程中搜索空间的动态缩减,提高了优化搜索的效率.此方法在供水管网抗震优化设计中有较高的效率,也可为其他有约束离散变量优化问题提供参考.     

基于图论的多尺度特征点匹配

文中针对在视觉测量系统中双目立体视觉特征点同名点匹配问题,提出基于图论的稀疏特征点全局匹配算法.首先,提出多尺度特征点提取算法来获得特征点的准确位置.算法引入多尺度小波变换,利用变换后的系数构建自相关矩阵从而进一步确定特征点的位置.然后,根据图理论将提取的稀疏特征点构建一个图,从而使特征点匹配问题转化为可用能量最小化方法解决的图的标记问题.此多尺度特征点全局匹配算法利用多尺度分析来提高匹配精度,并且利用特征点构建图降低了图的规模,同时根据极线约束选择潜在视差值进行计算,降低了计算量.实验结果表明此算法可获得精确的匹配结果.     

非合作Internet用户行为特征和约束机制的研究

基于一次博弈模型的流速与拥塞控制方法虽然能解释用户的非合作行为,但是由于最终的均衡解的效率不高,影响了其应用价值.文中在讨论了一次博弈模型和流速均衡的解析解的基础上,对基于无限重复博弈模型的流速与拥塞控制行为进行了深入研究.提出了重复和无限重复流速与拥塞控制博弈模型,论证了重复博弈NEP的存在性和最优性,并讨论了重复博弈中贴现因子的意义.接着研究了N个用户的无限重复流速控制博弈中用户不合理行为的惩罚威胁策略,设计了无限和有限博弈中用户行为的惩罚约束方法.最后利用重复博弈模型中的结论,提出了一种基于重复博弈模型的流速率控制算法FCAR.仿真实验表明,FCAR算法能够较为有效地规范和约束用户不合理行为,促使理性的非合作用户达成合作,以实现整个流速与拥塞控制系统效用的最优.     

求解几何约束问题的几何变换法

提出两种基于图表示求解几何约束问题的方法. 第1种方法能线性地处理无循环约束的几何约束问题. 第2种方法可以解决含循环约束问题. 这一算法的复杂度与Owen, Hoffmann的三角分解法一样是二次，但解题范围有所扩大. 实际上这一算法可以解决所有关于简单多边形的约束问题. 这一算法的核心是将几何变换引入基于关系图的约束求解算法.     

球面三角区域四叉树L空间填充曲线

球面三角四叉树中面片和结点的排列顺序直接关系到球面三角四分剖分模型组织和管理数据的效率. 在Lee编码模型基础上设计了L面片和结点空间填充曲线, 给出了面片寻址、结点L曲线生成、以及面片结点访问等主要算法. 同时, 基于位码运算提出了面片类型判别恒定算法时间优化算子, 可利用硬件来实现. 结点L曲线中大多数面片结点间距离分布在较低值范围内, 为数据高效存取提供了保证. 但是堂兄弟面片位置相邻, 结点地址却不连续, 少数面片结点间距离异常大, 导致平均结点间距离和遍历总距离的增大. 为解决该问题, 采用了m簇完备结点集作为n剖分簇结点存储基本单元, 每个m簇完备结点集重复存储公共结点, 从而避免了面片结点距离过大, 提高了节点访问效率.     

基于子图同构的前驱三维工序模型向二维工序图映射匹配算法

为满足企业对三维工序模型的迫切需求,解决前驱三维工序模型与工序图的映射匹配问题,提出一种基于子图同构的前驱三维工序模型向二维工序图的映射匹配算法．该方法首先对三维工序模型进行投影,获取其投影图;然后分别提取工序图与投影图中的图元信息,将其表示为以图元作为节点的属性邻接图．在映射匹配过程中,将投影图表示成“大图”,工序图表示成“子图”;将前驱三维工序模型向二维工序图的映射匹配问题转化为“大图”中寻找“子图”的问题．为提高匹配效率,对属性邻接图进行分割,并且充分利用图的顶点属性对图顶点进行有效细分．实验结果表明,该算法能够实现精确的匹配,并且匹配效率能满足实际应用要求．     

一种新型全姿态飞行仿真转台的运动学分析

针对三轴转台无法避免运动学奇异的缺陷,提出了一种四轴型全姿态飞行仿真转台,利用冗余自由度机构的特点,使机构始终保持提供三个自由度的运动.针对所提出的四轴转台的运动学正解问题,采用双欧拉法计算负载的姿态角,解决了全姿态欧拉角计算的奇异问题.针对四轴转台的运动学反解问题,采用基于伪逆的梯度投影法给出了带有性能指标优化的转轴角速度的最优解,然后用基于动态控制的方法获得转轴的角位置.提出的运动学反解算法能保证在获得期望姿态的同时,避免接近奇异位置和各轴的极限角位置.仿真结果表明,四轴型全姿态飞行仿真转台运动学性能明显优于三轴转台.     

移动进程的空间逻辑

提出了一个用于描述异步π-演算中移动进程的时态和空间性质的模态逻辑. 该逻辑具有基于谓词变量的递归构造. 建立了这一逻辑的语义理论, 并证明了语义的单调性, 从而保证了不动点的存在. 还设计了一个算法来自动地检测移动进程是否具有用该逻辑公式所描述的性质, 并证明了该算法的正确性.     

资源约束下的活动网络时差算法及实现技术

提出一种特定的修正两阶段调度算法计算资源约束下活动的总时差和自由时差。第一阶段为正向调度过程,获得基准调度计划并确定各活动在优先关系和资源约束都可行条件下的最早时间参数;第二阶段基于第一阶段获得的时间参数,采用逆向混合调度生成策略,计算出每个活动在满足两个约束条件下的最晚时间参数,然后基于最晚时间参数和最早时间参数计算出资源约束下活动的两种时差。在得到计算公式后,基于面向对象的程序设计技术,开发了Visual C++代码实现所提出的算法,并采用一个实例说明了算法的求解过程。研究结果表明,本文算法是有效的,可用面向对象技术实现。     

IDEA算法高速密钥生成模块的FPGA实现

提出了一种基于FPGA的高速IDEA算法密钥生成方案.详细介绍了IDEA密钥生成模块的子模块的功能划分、设计实现及性能分析,对直接影响速度性能的模乘和模乘逆运算,提出改进的硬件实现结构.在此基础上,设计了新的IDEA密钥生成模块FPGA实现方案以克服其常用结构所存在的缺陷.仿真结果表明,其速度性能有了较大的提高,且该结构能在速度与资源消耗之间取得一个较好的平衡.     

一种求解带有时间调度的四维长方体装填问题的启发式算法

长方体的Packing问题被证明是NP-hard问题。对于低维度Packing问题,国内外学者给出了模拟退火算法、遗传算法、分枝限界算法、拟人算法等求解算法。文中针对带有时间调度的三维长方体的Packing问题,引入封装级别、空间距离和周边生成序数等评判标准,提出了一种基于贪心策略的启发式算法。该算法对每个长方体每一占角位置进行评判,依据空间利用率选择给定格局下的最佳放置长方体及其放置方式,并进行填放。算法的运算复杂度是一个与容器参数A,B,C,T以及长方体数目n有关的多项式O(A~2B~2C~2T~2n~5)。利用该算法对非闸断模式和闸断模式测试样例进行实验,算法求解得到非闸断模式测试样例的平均空间利用率为98.81%,闸断模式测试样例的空间平均利用率为99.87%。并且,对于一半以上样例,该算法能够求出最优解。实验说明该算法对于求解带有时间调度的三维长方体Packing问题十分有效。     

宽频段空间信号频率、二维到达角和极化联合估计

在宽频段情况下,利用两个非均匀线阵组成的L型阵列,提出了一种基于ESPRIT和整数搜索解模糊算法的多个独立空间信号频率、二维到达角和极化的联合估计算法. L型阵列由与坐标轴方向平行的偶极子对组成. 数值模拟结果证实了这种方法的有效性.     

卫星位置误差条件下基于约束Taylor级数迭代的地面目标定位理论性能分析

基于卫星平台的地球表面目标定位系统受到卫星位置误差的影响较大,为此,该文在卫星位置存在误差的条件下,系统给出一种推导约束Taylor级数迭代公式及其理论定位性能的数学分析框架.为了便于讨论,文中以时差观测量为范例,并在三种情形下分别推导各种用于地面目标辐射源定位的约束Taylor级数迭代公式及其相应的理论定位性能,并将该理论性能与三种情形下的约束Cram′er-Rao界进行定量比较,从而得到若干定量结论.文中讨论的三种情形包括:(I)没有卫星位置误差且没有校正源的情况;(II)卫星位置存在误差且没有校正源的情况;(III)卫星位置存在误差且存在校正源(位置精确已知)的情况.最后,文中设计若干基于时差的卫星定位实验场景用以验证算法推导和理论分析的有效性.     

环、mesh 嵌入RP(k)网络

基于RP(k)互连网络, 首先讨论了该网络的拓扑性质, 证明了RP(k)网络是一个Hamilton 图. 然后, 重点研究了将环和二维mesh 嵌入该互连网络的算法. 构造性的证明了10*k的环可以嵌入RP(k)网络, 且四个性能参数都为1. 考虑到网络的容错情况, 当RP(k)网络中每个片有一个节点出现故障时, 去掉故障节点和相应的边, 得到互连网络RP-1(k), 该网络也是Hamilton 图. 然后讨论了将二维 mesh 嵌入RP(k)网络的方法, 定义了顺序列嵌入、迂回列嵌入和最短路径映射, 并设计了嵌入算法. 该嵌入算法的性能如下, 若a是二维mesh 最小一维的长度, 按照迂回列嵌入方式, 当a =1, 2, 3, 4, 5时, 其延伸分别为1,2,3,3,2, 拥挤度分别为1、3、4、5、3; 当5<a<10时, 按照顺序列嵌入方式, 延伸=3, 拥挤度≤6; 当a>10时, 其延伸=^┌ a/10^┐ +2, 拥挤度= max{^┌a/10^┐, 6}; 当a=10 时, 四个参数都为1. 研究结果表明, RP(k)网络具有简单的拓扑性质, 很强的容错能力, 并且环和2-D mesh可以高效地嵌入该网络.