多级位示图目录的推广和溢出处理

本文推广文[1]提出的多级位示图目录的概念,在其有关算法中引入多倍字位操作,讨论存储地溢出的处理方法。本文提出的才技术使多级位示图目录的结构和有关算法更具普遍性和实用性。     

RTEMS存储管理的研究与改进

对嵌入式实时操作系统RTEMS的两种存储管理方法——分区和区域进行了分析和研究。分区管理是将内存划分为大小相等的缓存块,以队列的形成将空闲缓存块组织在一起,并以缓存块为单位动态地分配。区域管理以可变大小的内存段进行分配,用双向链表来管理空闲内存段,采用首次适应算法对内存进行分配。由于区域管理算法复杂,因此,本文提出带辅助位示图的位示图存储管理方案,使内存分配更加简单,同时也解决了空闲区合并问题,提高了RTEMS的可靠性和实时性。     

SQM:基于Spark的大规模单图上的子图匹配算法

针对大规模数据图下基于回溯法的子图查询算法的准确率低、开销大等问题，为提高查询准确率，降低大图下的查询开销，提出一种基于Spark的子图匹配（SQM）算法。首先根据结构信息过滤数据图，再将查询图分割成基本查询单元；然后对每一个基本查询单元分别匹配后进行Join操作；最后运用并行化提高了算法的运行效率，减小了搜索空间。实验结果表明，与Stwig、TurboISO算法相比，SQM算法在保证查询结果不变的情况下，速度提高了50%。     

共享存储多处理机目录组织技术研究

当前，绝大多数分布式共享存储系统采用基于目录的Cache一致性协议。介绍了几种典型的目录组织方案，并对它们进行了比较。提出一种新的目录组织方案。该方案采用位向量和有限指针混合的两级目录结构，在存储开销上比位向量目录优越，比有限指针目录增加不多；而在时间性能上，优于有限指针目录，接近位向量目录。与已有的方案相比它更适于超大规模的多处理机系统。     

一种基于数据访问特征的层次化缓存优化设计

随着片上可集成的处理器核数增加,多核处理器的片上通信延迟不断增大,目录存储开销也随之线性增长.层次化缓存结构将片上缓存递归划分为多级区域,并将数据复制到各级区域内以减小片上通信延迟,同时通过多级目录结构降低了目录存储开销.文中通过对数据访问特征进行分析,提出一种新型改进层次化缓存结构(EHCD),将从片外读入的数据直接...     

基于广度优先遍历加权图生成的启发式图分区

图分区质量极大程度上影响着计算机之间的通信开销和负载平衡, 这对于大规模并行图计算的性能是至关重要的. 然而, 随着图数据规模的越来越大, 图分区算法的执行时间成了一个不可避免的问题. 因此, 研究如何优化图分区算法的执行效率是有必要的. 本文提出了一个基于广度优先遍历加权图生成的启发式图分割方法, 该方法在实现较低的通信代价和较好负载平衡的同时, 只引入了少量的预处理时间开销. 实验结果表明, 本文的划分方法减少了复制因子, 降低通信开销, 并且引入的时间开销较小.     

一种新的基于递归分解的图可达性查询算法

针对现实中许多超大规模图可达性查询的问题,提出了一种新的基于递归分解的算法,即将原图递归分解成一系列生成树和剩余图两类子图,并通过分别查询这两类子图来减少查询开销.相比于区间标记、链分解、2-hop标签和路径树等传统算法,该算法不仅空间开销更小,且时间复杂度更低.仿真实验表明,该算法对处理大规模有向图可达性问题上存储规模更小且查询效率更高.     

Apriori算法用于频繁子图挖掘的改进方法

AGM算法最早将Apriori思想应用到频繁子图挖掘中。AGM算法结构简单,以递归统计为基础,但面临庞大的图数据集时,由于存在子图同构的问题,在生成候选子图时容易产生很多冗余子图,使计算时间开销很大。基于AGM算法,针对候选子图生成这一环节对原算法进行改进,减少了冗余子图的生成,使改进后的算法在计算时间上具有高效性;测试了在不同最小支持度情况下改进方法的时间开销。实验结果表明改进算法比原算法缩短了计算时间,提高了频繁子图的挖掘效率。     

基于Apriori图挖掘算法的优化及其在3D构造解析的应用

基于Apriori的图挖掘(Apriori-based Graph Mining,AGM)算法结构简单,以递归统计为基础,但在面临庞大图数据集时,由于存在子图同构问题,在生成候选子图时容易产生很多冗余子图,增大了计算时间的开销。因此在AGM算法基础上提出一种改进方法,通过增加约束来减少候选子图生成数量,同时引入三次元坐标对图的顶点间的距离进行计算,并归结到边的标识当中,以处理三维图结构数据。通过改进算法对化学化合物进行分析,描述其三维化学结构以及生理活性上的相互关系,并测试了不同条件下改进方法的时间开销,实验结果表明在边标识数较多的情况下改进算法比原算法缩短了计算时间,提高了效率。     

NTFS文件系统空间回收方法的研究

传统配置技术中配置容量往往得不到充分利用,并且已经分配的存储资源占用的存储空间即使被释放了也无法再次使用。为此,应用自动精简配置(TP)技术按需分配存储资源,解决存储资源的浪费问题。针对一般文件系统中空闲空间回收方法均需要占用额外的系统资源问题,提出SAN环境下基于NTFS文件系统簇位示图的空间智能回收方法。实验结果表明,NTFS文件系统的空间回收方法可有效回收空闲空间,当TP页大小设置在KB级时,回收效率可达90%以上,同时该方法推迟了容量预警和在线扩容的时间,提高了存储利用率。     

位图连接索引服务机制研究

位图连接索引是数据仓库中一种有效的优化表间连接操作性能的索引机制。在大内存分析处理应用场景下,位图连接索引不仅需要权衡索引的内存和CPU开销,还需要进一步考虑处理器平台所带来的性能收益和数据访问延迟。提出了基于服务的位图连接索引管理机制,其主要特点体现在三个方面：独立于数据库的自管理索引机制;基于存储空间约束的TOP K关键字位图连接索引机制;处理器敏感（processor-conscious）的位图连接索引技术。索引服务将索引从数据库中内置的数据结构变成数据库外的索引服务层,通过对用户查询负载的分析模块和索引服务管理模块改变传统的由数据库管理员人工管理索引的模式,同时借助于协处理器和内存云技术提高索引服务的性能和灵活性。实验测试结果表明,索引服务机制能够有效地提高索引存储和访问效率,在通用GPU的强大并行处理能力的支持下,位图连接索引服务的性能和数据库整体查询处理性能都得到了显著的提升。     

位图在嵌入式系统内存管理中的应用

嵌入式系统内存管理要求有较高的可靠性及确定性。传统的内存管理方法使用链表来维护空闲内存,内存的分配时间与链表的长度有关,确定性不够。采用位图的方式进行内存管理,内存的分配和回收都是常数时间,可以显著提高内存管理的确定性及可靠性。     

基于位图的键值存储哈希优化

内存键值存储系统中索引方法决定了系统的时间性能和空间开销,是改进和优化的关键因素。哈希索引提供了O（1）时间复杂度的访问操作,但会产生存储冲突,引起访问性能下降。为此,提出了一种基于位图的键值存储哈希优化方法,可以避免存储冲突提升访问性能。该方法将共前缀的键哈希到同一个块,减少键存储空间;在块内使用层次位图结构,全域位图表示所有键的后缀部分来避免存储冲突,摘要位图支持快速定位和范围查询加速。实验结果表明,优化后的哈希索引在多种负载上均能取得较高吞吐量并具有良好的并发性能,同时内存占用较现有方案大大降低。     

云存储日志结构文件系统中段回收机制的研究

针对云存储文件系统中,复杂的检索和回收过程导致系统处理用户数据的能力下降问题,基于日志结构分布式文件系统（HDFS-based Log-structured File System ,HLFS）,提出一种针对系统资源进行有效回收管理来提高云存储空间有效利用率的方法,通过位图标记的方式找到HLFS中段资源的使用情况,实现对HLFS中段资源的管理回收。实验结果表明,位图标记应用于云存储系统中资源管理之后,能够改善垃圾回收的效率。     

Visual C++在动态显示过程屏幕闪烁的消除

采用 GDI位图及内存设备环境改进屏幕显示 ,通过创建内存设备环境以及与显示兼容的位图 ,先将图形绘制在与内存设备环境兼容的位图中 ,这样显示时就只需将图形从位图中复制到显示器屏幕上 ,缩短了显示图形所用的时间 ,并且不必擦除背景 ,实现了无闪烁的连续过程     

开源RTOS内存管理机制分析和改进

针对开源RTOS(FreeRTOS)内存分配时间不确定及内存利用率低、不能很好支持动态内存分配等不足,研究FreeRTOS的内存管理机制并比较几种典型动态内存管理算法的优缺点。移植修改过的TLSF算法对管理机制进行改进,较小的内存分成固定大小的内存块,用一级位图索引组织,较大的内存用二级间隔表组织。实验结果表明该方法能较好地提高内存分配速度和利用率。     

基于网格搜索的船体不规则分段动态堆放方法

针对船体分段建造后在堆场中的空间调度问题,提出基于网格搜索的分段动态空间调度算法。首先,利用改进的粒子群算法产生多个可行的分段堆放序列;然后,采用基于网格搜索的定位策略对堆放序列进行空间布局解码。在解码过程中,运用位图对场地及投影多边形进行信息描述,快速寻找多边形的最佳定位位置。考虑分段堆放问题的动态性的时空关联性,同时以场地平均利用率和需要挪动的场地内分段总数的综合加权作为评价函数,利用改进的粒子群算法对方案进行择优,得到近似最优解,实现了堆放方案的全局优化。通过对船厂实际生产数据的实证分析以及堆放算法间的对比分析,结果证明,所提算法在综合评价场地利用率、移动分段数和运算效率的条件下是最优的。     

多层构架的物资编码管理系统的设计与实现

针对目前已投入使用的各种物资编码管理系统，如：“外贸行业物资编码管理系统”等，普遍存在着系统维护和扩展问题，在分析用户需求的基础上，按照Struts框架的规范，使用Struts组件，设计并实现了物资编码管理系统的改进．在数据维护方面，对物资的计量类型和计量单位做了科学的划分和管理，实现了物资属性的规范描述；在编码编制中，给出了新的编码信息结构，将编码基本信息和所属规格信息分别存储，以便于编码的查重工作；在查重处理中，采用多线程的方法，将查重处理作为后台进程进行，允许其它工作同时进行，有效地解决了查重处理时间过长的问题；在物资编码审批中，给出了严格而周密的编码审批流程，实现了物资编码的科学管理，充分发挥了Struts框架的优点，实现了应用程序的易维护性和可扩展性。     

基于Bin位图索引的多维查询优化算法

在属性基数（该属性可能的取值数）很高的情况下,简单位图索引需要占用太大存储空间。Bin位图索引可以很好解决这个问题。这种索引不像简单位图索引那样建立在不同的属性值上,而是建立在属性范围上,但候选检查往往占用大部分的查询时间。为了提高查询性能,提出一种排序方法来对各属性进行排序,以减少候选检查数目,并在此基础上提出动态预扫描算法。实验结果表明,排序和动态预扫描算法都取得了良好的效果。