VLST-CAD中图形处理算法及其固化技术研究项目摘要

本课题研究版图验证（以DRC为例）的一些主要算法的固化。包括数据排队算法和图形的各种逻辑操作算法。主要创新是这些算法用硬件实现（即所谓固化），这类专用硬件作为主机的协处理器工作，本课题所用的硬件是FPGA实际的结果表明算法固化后的运算速度对数据排队算法比软件实现快25倍，对于逻辑操作算法（用线扫描法）固化后的速度比软件实现快50倍，其结果使版图验证速度大提高，也即可以验证规模更大的VLS版图。此外本课题尚做了连机DRC的系统开发，该系统做到版图输入后能即时进行DRC检查。 2100433B

DFSA算法可采用各种方法预测待识别的标签数量，然后动态调整最优帧长，与FSA相比，系统效率有明显改善，接近36．8%。但是，当标签数量较多（特别是标签数量大于500）时，采用由预测标签数量设置最优帧长的方案会使系统效率急剧下降。因此，在标签数量较多的情况下，为了使系统效率得到提高，EPCClass1Gen2标准中采用了Q值算法，该算法可以实时自适应地调整帧长 。

Q值算法

在Q值算法中，阅读器首先发送Query命令，该命令中含有一个参数Q（取值范围0～15），接收到命令的标签可在[0，2Q－1]范围内（称为帧长）随机选择时隙，并将选择的值存入标签的时隙计数器中，只有计数器为0的标签才能响应，其余标签保持沉默状态。当标签接收到阅读器发送的QueryRep命令时，将其时隙计数器减1，若减为0，则给阅读器发送一个应答信号。标签被成功识别后，退出这轮盘存。当有两个以上标签的计数器都为0时，它们会同时对阅读器进行应答，造成碰撞。阅读器检测到碰撞后，发出指令将产生碰撞的标签时隙计数器设为最大值（2Q－1），继续留在这一轮盘存周期中，系统继续盘存直到所有标签都被查询过，然后阅读器发送重置命令，使碰撞过的标签生成新的随机数 。

根据上一轮识别的情况，阅读器发送Query－Adjust命令来调整Q的值，当标签接收到Query－Adjust命令时，先更新Q值，然后在[0，2Q－1]范围内选择随机值。EPCClass1Gen2标准中提供了一种参考算法来确定Q值的范围.其中：Qfp为浮点数，其初值一般设为4．0，对Qfp四舍五入取整后得到的值即为Q；C为调整步长，其典型取值范围是0．1

该算法在参数C的辅助下对Q值进行动态调整，但是C太大会造成Q值变化过于频繁，导致帧长调整过于频繁，C太小又不能快速地实现最优帧长的选择。因此，研究者们对Q值的调整进行了各种优化 。

基于最大吞吐量调整Q值的算法

文献提出一种基于最大吞吐量对Q值进行调整的算法，其中定义了以下变量：Nt为已识别的标签个数；N为识别标签所需的总时隙数；NC为冲突时隙的个数；nu为上一轮未识别的标签个数；e为冲突时隙中的平均标签个数；PC为冲突时隙所占的比例 。

这些参数之间的关系为PC=NC/N，e=nu/Nc，吞吐量=Nt/N。由于Aloha类算法的最大吞吐量为0．368（e－1）[5]，该算法以此作为调整Q值的依据。当系统吞吐量达到或接近0．368时，阅读器仅需调用2Q－1次QueryRep命令，而不需要在接下来的盘存周期中调整Q值。当吞吐量小于0．368时，根据未识别的标签个数nu来调整Q值 .

基于分组的位隙Aloha算法

文献提出一种基于分组的位隙Aloha算法，该算法采用位隙Aloha算法中的128位预定序列，代表128个位隙。若某个标签选择了第i个位隙，则将第i位置1，其余各位都置0。当标签数量为15时，位隙Aloha算法可获得最大吞吐率88．38%，但随着标签数量的增加，算法性能急剧下降 。

因此，基于分组的位隙Aloha算法通过对标签进行分组来提高算法的性能。该算法在查询命令中设置了一个位隙计数器的参数Q（Q为整数，且0≤Q≤15），当标签收到阅读器发送的查询命令后，在[0，2Q－1]范围内生成一个随机数，即代表选择了相应的位隙，只有选择了0的标签才会立即响应。同时，该算法根据冲突位隙数动态地对Q值进行调整：当冲突位隙数小于11时，Q减1且最小为0；当冲突位隙数在11～20之间时，Q保持不变；当冲突位隙数大于20时，Q加1且最大不超过15 。

综上所述，基于Aloha的防碰撞算法原理简单、容易实现，对新到达的标签具有较好的适应性，尤其对于标签持续到达的情况有较好的解决方案，但该类算法存在几个明显的缺点：①响应时间不确定，即同一批标签在不同时刻进行识别所需要消耗的时间相差很大；②个别标签可能永远无法被识别；③Aloha算法达到最佳吞吐率的条件是其帧长等于标签数量，当需要识别的标签数量较多或选择的帧长与实际待识别标签数量不符时，系统性能将明显下降。而基于树的算法则很好地解决了这些问题 。

《智能控制算法及其应用》主要介绍各种典型智能控制算法的基本内容、设计与实现方法及其在函数优化、电力系统中的应用。《智能控制算法及其应用》首先阐述智能、智能控制的基本概念，介绍智能控制与传统的经典控制理论、现代控制理论的联系和区别。然后从四种典型智能控制算法（专家系统、模糊控制、神经网络和进化计算）入手分别阐述它们的发展历史、基本内容、实现方法及其应用。最后介绍混沌模拟退火动态烟花优化算法，并将其用于优化离散时间微分平坦自抗扰控制律的参数，通过计算机仿真和基于智能优化算法试验平台开展试验以验证该算法的有效性；介绍递减步长果蝇优化算法，并将其应用于风电机组齿轮箱的故障诊断；介绍云粒子群布谷鸟融合算法，通过联合循环发电机组典型热工过程模型参数辨识实例验证该算法的有效性。

《分布并行图形绘制技术及其应用》系统深入地介绍了分布并行图形绘制的基础知识、体系结构和多种绘制加速算法以及典型的应用系统，分为基础篇、技术篇和应用篇，共15章的内容。《分布并行图形绘制技术及其应用》可作为并行图形绘制、分布式虚拟现实、高性能图形绘制等方向的研究生教材以及技术参考书，同时可供研究并行绘制技术和分布式虚拟现实技术的师生和从事高性能图形绘制技术的研发人员参考。