视频服务器的磁盘I/O调度算法

讨论了视频服务器的Ｉ／Ｏ 调度问题．通过对磁头移动和旋转延时的优化， 得出了双向扫描（Ｂｉ－ＳＣＡＮ）调度算法．对需要同时支持多种视频速率的异构系统， 在Ｂｉ－ＳＣＡＮ算法的基础上，给出了固定数据长度（ＣＤＬ）和固定时间长度（ＣＴＬ）两种调度方案的接纳控制条件．通过模拟实验比较了这两种调度方案的性能，

RAID的并行I/O调度算法分析

由于越来越多的应用受限于I/O,存储系统正起着越来越重要的作用。磁盘阵列RAID是一种提供高性能I/O的最常见存储设备。本文分析了RAID并行I/O调度算法的I/O执行时间和磁盘利用率,为合理配置高性能阵列提供了依据。

RAID控制器中I／O调度算法研究

介绍应用于RAID控制器的I/O调度算法的设计与实现.主要目标是把来自RAID模块针对每个磁盘的具体读写请求按照响应的策略放入对应磁盘的读写I/O队列.然后根据具体请求的优先级和读写特性,对响应请求在队列中的次序进行调整或者对前后项进行合并,实现I/O请求的调度策略.

关于求平面点集凸包的一个O(n)时间算法的商榷

王志强等于 1998年提出了一个计算平面点集凸包的新算法 ,并且声称该算法的最坏时间复杂度为 O(n) ,从而为线性时间排序提供了可能性 .该文对王志强等提出的求平面点集凸包算法的时间分析提出不同观点 ,进一步明确了平面点集凸包算法和排序算法的时间下界为 Ω(nlogn)

边赋权森林ω-路划分的O(n)算法

w-路划分问题是路划分问题的一般化,它源于并行计算机系统、计算机网络与分布式控制系统等一类广播通信问题.设置最少的信息源节点,使得在指定的时间内将信息源节点所拥有的信息发送到其余节点,并且保证不同通信线路之间不得相交.从Hamilton路的NP-完全性不难看出,w-路划分问题属于NP-完全问题.通过构造性证明技术,获得了边赋非负权路径、树和森林的w-路划分问题的一些性质.分别提出了求解边赋非负权路径和边赋非负权树的w-路划分问题的线性时间算法,讨论了算法的局部实现技术,详细地分析了这些算法的复杂度.以这两个算法为基础,提出了一个线性时间算法求解边赋非负权森林的w-路划分问题.所提出的算法直观简明、操作容易,只需要较少的运行时间和较小的存储空间.

磁带库系统的随机I/O调度算法

由于磁带库随机存取的性能很差,需要研究有效的随机I/O调度策略和算法以改善其在线存取的效率.对已有调度算法进行了分类、提炼和总结,利用仿真实验对静态调度、动态调度和基于复制的调度算法进行了深入研究,讨论了影响各种算法有效性的因素.针对已有算法在较重的负载条件下使系统性能急剧恶化的问题,还提出并研究了一种基于效益-代价均衡的调度算法.该算法引入效益-代价加权的概念,通过调节不同负载下的效益-代价加权比,极大地改善了已有算法在重负载下的有效性.该项研究为设计海量存储系统中的自适应调度算法提供了重要依据.

平面上两个点集间距离的O(nlogn)算法

定理"平面上两个点集的距离所在边是Voronoi图的Delaunay三角剖分中一条边"是本文的核心,在该定理基础上,本文提出如何用Voronoi图的Delaunay三角剖分算法求平面上两个点集的距离,并分析其复杂性.

Fibonacci堆及其在外存储算法中的应用

为了适应外存储算法在计算机程序设计中的应用需求,研究了外存储算法中数据结构的应用设计。基于Fibonacci堆在内存储中的特点,提出了一种新的适合外存储算法的数据结构,分析了该数据结构中各种操作的时间复杂度。其中除删除最小结点和更新结点的操作外,其他操作都具有单位时间的页面置换次数。最后以Fibonacci堆在Dijkstra算法中的应用为实例表明了该数据结构的可行性和有效性。

无里程计移动机器人多传感器融合定位算法

为解决无里程计移动机器人室内定位问题,提出一种不依赖里程计数据的多传感器融合定位算法。首先,使用RF2O算法从激光雷达信息中获取移动机器人的运动数据;其次,使用扩展卡尔曼滤波融合IMU数据和RF2O算法计算的数据得到初步的定位数据;最后,使用自适应蒙特卡洛定位算法对定位数据进行修正,解决误差累计问题,得到精确的定位结果。结果表明,本文提出的定位算法可以有效降低测量误差、缩短算法运行时间,具有定位精度高且计算量小的优点,可以满足无里程计的移动机器人的定位需求。

Linux I/O调度算法分析与研究

研究表明,好的磁盘调度算法可以明显优化磁盘的I/O性能,Linux提供四种调度算法可供选择。基于Linux 2.6.32内核源码,研究Noop、Deadline、Anticipatory、CFQ四种磁盘调度算法的基本原理和特点,分析每种算法的优缺点,这对系统管理员针对不同类型的应用场景来调整优化I/O调度算法有着重要意义。

斐波那契字符串前缀和的O(1)算法及其证明

作者在编写斐波那契字符串前缀和算法程序过程中,通过具体观察、抽象思维和程序验证等方式,结合斐波那契数列特点,提出了一种简单而奇妙的算法,即Sn=nφ,表示取整,φ为黄金分割比/5-1/2,将计算的时间复杂度从O(lg^2n)降为O(1),运用数学归纳法予以证明,并得出了任意一段字符串的求和公式、任意一个字符是“0”或“1”的计算公式等相关推论.

一种基于效益-代价均衡的磁带库调度算法

诸如数字图书馆等规模在1012字节以上的大型数据库需要在线存取大容量磁带库中的海量数据.由于这些需求都是对海量数据的随机存取,而磁带库的随机存取性能很差,所以,研究有效的磁带库随机I/O调度策略和算法是改善磁带库系统性能的重要课题.提出并研究了一种基于效益-代价均衡的调度算法,给出一种有效的效益-代价加权比的估算方法.该算法根据系统的工作负载特点,动态调节调度的效益和代价的加权比,从而改善了磁带库系统在各种负载下的系统性能.研究解决了已有磁带库调度算法的对工作负载敏感的问题,极大改善了调度算法在重负载下的有效性.

基于水平加权关联规则挖掘算法的研究

针对传统关联规则各项目具有着相似的出现频率和相同的重要性两个前提假设,提出了加权关联规则的概念,重点研究了水平加权关联规则MINWAL(O)算法的基本思想,指出该算法的不足及优化算法,旨在对加权关联规则挖掘算法的扩展和改进奠定基础.

流星余迹通信网络的路由算法

流星余迹通信是一种重要的应急通信方式。其通信网络具有传输延时长和链路间歇中断的特点,适用于这种特殊网络的路由算法具有明显的针对性,有待深入研究。文中在研究流星余迹网络拓扑结构的基础上,基于OPNET仿真软件构建流星余迹组网模型,结合适用于DTN(Delay Tolerant Network)网络的ED(Earliest Delivery)算法和EDLQ(Earliest Delivery with Local Queue)算法的特点,分析通信时延模型,提出一种改进的OED(Optimistic Earliest Delivery)算法。基于已建立的模型对数据传输成功率和网络吞吐量进行仿真。仿真结果表明,OED算法在组网网络的数据吞吐量和数据传输成功率方面优于ED算法和EDLQ算法,能够避免因队列溢出导致的数据包丢失;通过增大节点容量,OED算法的数据通过率相对于ED算法和EDLQ算法分别提升了20%和8%;路由算法的选择不影响流星余迹节点间链路的平均持续时间和平均中断等待时间。OED算法在流星余迹网络中具有较强的适应性,能够为流星余迹组网的建设提供参考。

MPI-IO中Collective I/O的优化

本文对MPI-IO库中Collective I／O的实现算法Two-phase I／O提出了改进。通过选取主联络进程来减少第 一阶段进程间的通信量,从而减少Two-phase I／O方法在通信过程中的时间消耗,提高了整体的I／O性能。

基于SOC的对象存储控制器的设计与实现

对象存储重新划分了传统文件系统的功能,并将存储管理功能下放到智能存储设备中。采用基于对象接口,利用智能存储设备的计算能力改善存储性能,获得了更好的可扩展性、安全性以及跨平台无缝共享能力,目前正得到广泛的研究和应用。对象存储控制器是对象存储系统的核心部件,是对象存储系统性能发挥的关键。介绍了一种新型的基于SOC的对象存储控制器的设计和实现。测试结果表明,设计的对象存储控制器在性能、可靠性、成本和功耗方面都具有巨大优势。最后介绍了几种正在研究的对象存储控制器的并行优化方法。

一种基于WDM光网络的静态波长路由优化算法

研究了WDM光网络中的静态波长路由问题,基于负载的均衡可以改善网络的性能这一事实,提出了一种优化的路由算法(O-Spread算法),文中进行了算法仿真,结果表明优化算法与传统的最短路由算法相比,能够有效地减小网络对于波长数目的需求。

基于Xen的虚拟磁盘调度算法改进

Xen目前所采用的I/O调度算法能够较好的保证公平性;但在实际应用中,不同的虚拟机可能有不同的性能需求。该文研究了Xen虚拟存储的实现和I/O调度算法的原理,提出了基于反馈的动态优先级调度策略,通过对比测试验证了磁盘带宽在不同虚拟机之间的按需分配。

Linux 2.6内核进程调度策略与算法分析

Linux 2.6内核采用了新开发的调度器,该调度器基于O(1)算法。新的调度器基于每个CPU来分布时间片,并且取消了全局同步和重算循环。文中详细分析了新的调度器策略和算法,最后进行了总结。

基于BP神经网络PID算法的斗轮机自动取料流量控制优化

为解决斗轮取料机自动取料流量控制难题,提高干散货码头生产作业效率,采用B P神经网络PID控制算法对取料机取料流量控制进行优化。分析目前斗轮机取料流量控制现状,在常规PID控制方法的基础上采用BP神经网络进行改进优化,利用BP神经网络的自学习、自适应等特性,实现对PID控制参数的在线整定和优化。采用MATLAB Simulink仿真软件,建立BP神经网络PID控制模型,通过在天津某煤炭码头进行现场工程应用,证明模型的有效性和可靠性,表明BP神经网络PID算法能进一步提高干散货码头整体生产作业效率,延长大机设备使用寿命。