一种基于顶点位置树的可重构软硬件迭代协同算法

可重构计算分时复用有限的面积资源,实现更多的任务硬件加速运行,同时也给传统的软硬件协同设计带来了新的挑战.为此设计了一种基于顶点位置树的迭代协同ICS-VPT算法针对离线型、集中共享式可重构计算平台,综合软硬件划分、硬件布局和任务调度,提升系统性能:首次提出顶点位置树的数据结构,以较小的存储空间快速查找布局位置;迭代协同算法根据数据依赖图分组任务,结合通信代价获取软/硬件任务的优先级,进行合理划分和调度.实验结果表明,ICS-VPT算法在高效管理可重构资源和灵活处理通信代价的同时,保持了较低的系统运行时间.     

支持可重构计算的满二叉树中序存储策略及快速遍历算法

通过对满二叉树顺序存储序列与中序序列之间解析关系的研究,推导与证明了完全二叉树的一些重要性质,给出了一种可快速访问的满二叉树中序序列存储方法并设计出相应的遍历算法。基于该方法,一颗具有N个结点的满二叉树中序序列仅需要线性时间复杂度O(N)即可遍历,相关计算过程可嵌入在可重构系统中形成可重构计算单元。还给出了算法的C++实现过程及可重构系统的设计方案。     

一种基于后缀数组的多重复模式匹配算法

要在海量的信息中进行多重复模式的查找,应用一般的查找方法所需O(n2)的复杂度.为了提高模式查找算法的效率,提出了算法Epattern searcher H.该算法是采用能节省空间占用的后缀数组数据结构来实现,同时又运用过滤算法的思想而设计,从而提高算法的运行速度.这里针对英文小说高频词的查找对算法进行测试,可得到时间复杂度为O(n)实验结果.     

无线传感器网络中免于测距的声音定位算法

为在无线传感器网络中实现声音定位,从降低计算复杂度和减小噪声干扰的角度提出了一种基于中垂线分割的免于测距的声音定位算法.该算法采用免于测距的中垂线分割法确定声源所在定位区间,时间复杂度为O(N2),低于时间复杂度为O(N3)的基于测距的传统定位算法.通过对测量噪声的深入研究,提出了噪声敏感区概念.该算法在针对噪声敏感区...     

一种求解图着色的单亲遗传算法

给出了一种求解图着色问题的新算法,即单个个体的单亲遗传算法.算法采用顶点序号的聚类编码将个体的某个子串随机分配到其他子串中的变异方法.并对该算法的时间复杂度进行了分析比较,结果表明该算法具有较好的运行效率与收敛速度.     

利用超奇异椭圆曲线进行素性检验(英文)

根据超奇异椭圆曲线有理点个数与素数的关系,提出一个具有多项式时间复杂度的素性检验的概率型算法.对于给定的整数N,如果N≡3(mod4)或者N≡1(mod3),该算法具有多项式时间O(log8N).在广义黎曼假设成立的情况下,对于所有整数都具有这一时间复杂度.     

并行层压缩树包分类算法

在层压缩树路由算法思想基础上提出了一种新的硬件包分类算法--并行层压缩树包分类算法.该算法是基于独立存储单元和多域并行处理并在FPGA内部实现的高速网络包分类算法,主要包括单通道并行搜索和多通道综合比较两大部分.仿真结果表明在40 MHz的搜索时钟频率下,该算法能够达到每秒2 M包头的处理速度,其空间性能明显优于其他算法,具有O（d）的时间复杂度（d为域的个数）和O（dN）的空间复杂度（N为规则数）.     

一种用于可重构计算系统的离线布局算法

为在编译过程中估计程序在可重构器件上的执行时间,进而进行软硬件代码划分,需要将程序中所有基本块映射到可重构器件上,然后使用逻辑综合或其他方法计算其硬件执行时间,为此提出一个离线布局算法完成基本块的映射工作,同时使用基于IP核的代码转换机制完成从基本块数据流图到布局算法所需任务图的转换.实验结果表明,虽然布局算法的结果是局部最优解,同Xilinx ISE中的布局器相比,生成电路的最大工作频率平均低6.891%,面积大4.016%,但布局过程所需时间缩短了5个数量级,从而极大地减少了整个编译过程所需时间.     

一种新型的单芯片级可进化硬件系统

针对可进化硬件（EHW）系统的需求,设计实现了FDP-2-SOPC芯片,芯片中嵌入了CPU和FPGA两种IP核,可实现硬件电路的重构和进化;以该芯片为系统核心建立了一种新型的软硬件结合的单芯片级EHW系统.为了提高电路重构速度,设计了针对EHW需求的快速局部重配置技术;为提高遗传算法的执行速度,设计了专用的随机数产生器...     

基于总体性能优化的矩阵乘法器设计与实现

针对矩阵算法的优化,且兼顾系统的总体性能,采用Ripple运算模式,提出了一种基于多处理单元的矩阵并行乘法器设计方案,并将其于FPGA上实现.最后,将其FPGA资源利用报告与移位累加算法做比较,表明该设计方案可使得系统在矩阵复杂度相同的情况下,大大缩短运算时间,提高系统的时钟频率,且芯片布局得以优化.     

用于IC版图运算的O(N)排序算法

扫描线算法是集成电路版图运算的主流算法,排序在其中占有相当大的工作量．针对集成电路版图的特点,提出一种线性的排序算法,其时间复杂度为Ｏ（Ｎ）,比通常的快速排序算法时间复杂度（Ｏ（ＮｌｏｇＮ）低,适用于基于扫描线算法的集成电路版图运算．对于层次式设计的版图,该算法更具优越性     

一种短波通信中基于DSP的低速率语音编码技术

介绍了一种应用在短波通信中的码率为1．5Kbps低速率语音编码算法，此算法基于MELP（mixed excitation linearp rediction）混合激励线性预测语音编码算法的声码器模型，并对算法进行改进，降低复杂度和速率，在DSP芯片的硬件系统中实时运行了该算法，最后给出了算法测试仿真结果。     

可编程语音压缩专用处理器设计

为了提高通信系统的保密性,降低制造成本,需要进行专用处理器的设计。基于正弦激励线性预测(SELP)算法模型,设计了一款多速率语音专用处理器。芯片使用可重构体系结构和超长指令字(VLIW),优化了高复杂度函数。仿真结果表明:该处理器对0.6kb/s速率SELP算法的执行效率明显优于通用数字信号处理器(DSP)。处理器内部程序数据外部不可见,指令并行度显著提高,常用函数可被修改,从而达到高保密性、低复杂度、易开发性。     

二叉树CreateBTree算法的改进

在分析二叉树的CreateBTree算法的基础上，利用线性探测再散列方法对CreateBTree算法的中序遍历序列进行预处理来改进CreateBTree算法，使得改进后的CreateBTree算法在最差情况下，时间复杂度由O(N^2)降为O(N)。     

多序列比对问题的并行近似算法

基于中心方法的思想,采用分治策略,在SIMD-CREW模型上设计了一个使用O(k2m)个处理器(其中k为序列个数,m为最长的序列长度),时间复杂度为O(m logk)的并行近似算法.在实际情况中,由于logk远远小于m,相对于时间复杂度为O(m2k2)的串行中心方法,该算法在理论上达到线性加速.与现有的并行算法相比,它可以适用于任意情况,且易于分析时间复杂度.利用LARPBS模型的特点和并行求前缀和的方法,调用LARPBS模型上求和与最大(小)值的并行算法,首次给出了在LARPBS模型上的多序列比对问题的并行近似算法.该算法使用O(k2m)个处理器,时间复杂度为O(m log log D),其中D为序列两两比对的代价值的最大值.该算法同样适用于任何情况,由于log log D通常远小于m,所以它在理论上也是线性加速的.     

Dynamically Reconfigurable Encryption System of the AES

Reconfigurable computing has grown to become an important and large field of research, it offers advantages over traditional hardware and software implementations of computational algorithms. The Advanced Encryption Standard （AES） algorithm is widely applied in government department and commerce. This paper analyzed the AES algorithms with different cipher keys, adopted a novel key scheduler that generated the round key real-time, proposed a dynamically reconfigurable encryption system which supported the AES algorithm with different cipher keys, and designed the architecture of the reconfigurable system. The dynamically reconfigurable AES system had been realized on FPGA. The result proves that the reconfigurable AES system is flexible, lower cost and high security level.     

任意无向图的R点连通扩充

为研究以最少边集扩充一个任意无向图为R点连通图这一尚未解决的优化问题，通过将无向图点连通问题转化为有向图边连通问题，采用增广扩充的方法，提出了一个复杂度为O（｜V｜^5）的算法．利用该算法可最优地将给定无向图中任意2点达到所要求的点连通度．它发展了K点连通最优扩充的研究，从而使图的点连通扩充的研究在应用于网络设计的可靠性设计方面更具有实际意义．     

基于遗传算法的代理服务器位置优化研究

针对传统方法难以快速求得Web服务器代理部署问题的满意解,提出了一种基于遗传算法的求解策略.以图论为基础,构建了代理服务器位置优化模型,从Web服务器到客户构成一个树型结构.遗传算法采用二进制编码表示代理的位置,使用单亲交叉算子和单亲变异算子来提高算法的执行速度和进化效率.算法在时间复杂度方面优于传统方法.仿真结果表明,基于遗传算法的求解方案能快速地求出代理服务器位置优化问题的全局近似最优解,并满足实际Web应用的精度要求.