程序执行的时空测量方法研究

程序执行时所花费的时间和内存空间是评价一个程序性能优劣的一个重要指标。理论上,可以借助于数学这个强有力的工具估算出程序的时间复杂度和空间复杂度,然后用这两个标准来度量程序的效率;实际上,在源代码在线评测系统这样的实际系统中无法使用。文章对程序执行时所花费的时间和内存空间的测量方法进行大量深入的研究,基于DOS平台,提出了计时法。利用clock和coreleft测量程序执行的时间和空间;基于Windows平台,利用Get Process Times和Get Process MemoryInfo测量程序执行的时间和空间,在四川理工ACM中得到应用,实践证明这些方法正确、有效。     

一种改进的实时系统可达性分析算法

首先简介了时间自动机、时钟区域、区域等价、时钟带的概念.利用时钟带,可以将时间自动机的无穷状态空间转化为有穷.实时系统的绝大多数安全性和部分活性可以通过可达性分析算法来验证.然而,当系统时钟个数较多时,用DBM存储时钟带,会造成内存空间的很大耗费.该文提出了用邻接表存储时钟带,给出了改进的算法,并对算法的空间复杂度作了分析.实验表明,当时钟个数大于5时能节约很大的内存空间,从而在一定程度上缓解了状态爆炸.     

计算流体力学程序单核指令级优化方法

针对目前大多数计算流体力学程序对系统的单核计算能力利用不足,提出一种针对计算流体力学程序的单核指令级优化方法。该方法首先分析程序的性能指标存在潜在的性能不足,根据分析结果进行优化;依据容器的存储特性和系统的访存特性,对程序的存储结构和访存顺序进行调整,以优化空间开销和访存性能;对CPU的流水机制进行分析,在循环和分支中消除指令的控制相关和数据相关从而达到减少流水中断率的目的;分析编译器对高级语言的处理特点并结合系统中的运行时栈在指令级作出分析,优化指令结构从而减少指令冗余和降低指令复杂度。实验结果表明,在TIANHE-1A超级计算机系统上进行测试,与优化前程序相比,优化后的程序执行时间约减少68.34%,空间消耗约减少55.43%。通过对程序性能各项指标进行分析的结果表明,程序在流水中断率、缓存命中率及机器指令数等性能指标上均有大幅地提升,该方法优化覆盖范围多于目前其他优化方法,有较好的优化效果,在计算流体力学程序优化研究中具有一定的借鉴价值。     

股票数据流的相关性计算方法

相关性分析在股票投资、监测、预测中起着非常重要的作用．为定量计算各股票间的相关性，文中提出了一种股票数据流的相关性计算方法，它基于高效的单遍数据集扫描算法，能在有限的内存空间中计算出各股票间的相关性．与传统的计算方法相比，不管是在空间复杂度还是在时间复杂度上，所提出的方法都只需付出更小的代价．实验证明，这种相关性计算方法在同步股票报价中是有效的．     

内存推移理论及其实验

双空间存储器是2013年发明的新型存储系统,其核心是内存空间在巨大的双空间存储器上的映射理论——内存推移理论.介绍了所构建的第一个双空间存储器实物系统,并在该系统上首次实施了内存推移理论.完成了对双空间存储器和推移锁存器组的实物设计及实现,并在实物实验系统上成功实施了内存推移操作,从而证实了将内存空间在双空间存储器上推移的理论的正确性,成功解决了内存空间与巨大的双空间存储器随机访问空间的对接问题,奠定了构造双空间存储器和实施内存推移理论的实践基础.所构造的实物系统包含一块TQ2440Core 2.0核心板、1 GB双空间存储器和由8个12位推移锁存器组成的推移锁存器组.将该核心板对其2 MB内存空间的随机访问自动落实为对1 GB双空间存储器字空间上指定位置的随机访问,并利用推移指令在双空间存储器的字空间上实现了窗框移动操作.     

典型"稳定婚姻问题"的简明矩阵算法实现

对于典型“稳定婚姻问题”，借助矩阵（二维数组）给出了一种简明的实现方法．在本算法中，所采用的存储结构和实现方法灵活巧妙，通俗易懂，方便实现；而且用于存储所要处理数据的内存空间相对于其它一些算法节省了一半，空间复杂度为O（1）；由于存储结构的巧妙性，算法的时间复杂度在最好的情况下为线性时间N，在最坏的情况下为O（N^2）．     

内存空间在双空间存储器上的推移技术实验

详细介绍双空间存储器理论和其核心技术——内存空间推移技术的仿真实验.证实了用非易失性随机存储器(non-volatile random access memory,NVRAM)构建双空间存储器的可行性,同时通过对8086CPU系统的仿真实验,证实了将内存空间在双空间存储器上推移之技术的正确性.实验设置的目标系统包含一个8086CPU,16 MB的双空间存储器和16个8位的推移锁存器.目标系统中设置了2个不可闭窗和14个可推移的窗框,在不可闭的255号窗壁中设置了8086CPU的首指令和初始化程序,在不可闭的254号窗壁设置了8086CPU的中断向量表和双空间存储器的推移向量表.实验完成了8086CPU的上电过程、自动执行初始化程序、正确执行中断命令、正确执行数据读写命令等操作,并将CPU对其1 MB内存空间的随机读写访问自动落实为对16 MB双空间存储器指定位置的实时随机访问;实验还完成了随时修改推移锁存器的操作,并以此将对应的窗框推移到了双空间存储器的任意位置.实验结果为双空间存储器理论和内存空间推移技术奠定了基础.     

排序算法的分析与比较实现

本文论述了内部排序的几种算法,在思想、时间复杂度、空间复杂度及稳定性方面进行了比较。最后用C#语言比较了几种算法在大量数据中进行排序的比较次数和花费的时间。     

一种用于可重构计算系统的软硬件划分算法

在编译过程中,为了对运行于可重构计算系统上的应用程序自动地进行软硬件划分,提出一种基于模拟退火和链式调度的划分算法,该算法将程序的划分和调度结合起来,采用软硬件协同工作的方式,利用系统中微处理器核与可重构硬件之间的并行性加速程序的执行,同时在调度过程中,通过配置预取减少系统的重构开销.实验结果表明,相对于现有软硬件自动划分方法,该算法可以平均减少25%左右的程序执行时间.     

可任意花费的可传递电子现金系统

针对现有的可传递电子现金系统在传递协议中传递花费顺序固定以及传递次数受限制的问题,利用Groth-Sahai证明系统、对承诺的承诺和Ghadafi群盲签名,在标准模型下构建一个具有最优匿名性的可任意花费的等长可传递电子现金系统,该系统中电子现金的花费不受任何花费顺序限制,传递次数是任意次.基于对承诺的承诺,可以对所传递的序列号进行压缩,从而保证用户传递电子现金的长度是常量;基于Ghadafi群盲签名,实现了电子现金花费用户的任意性;在标准模型下,证明了新系统的安全属性,该系统具有不可伪造性、最优匿名性、不可重复花费性和不可诬陷性.