检索结果-南通市图书馆

Key-Value型NoSQL本地存储系统研究

在线全文

学校读者我要写书评

暂无评论

计算机学报 2018年第8期41卷 1722-1751页

作者：马文龙朱妤晴蒋德钧熊劲张立新孟潇包云岗中国科学院计算技术研究所先进计算机系统研究中心北京100190 中国科学院大学北京100049 工业和信息化部信息中心北京100846

NoSQL系统因其高性能、高可扩展性的优势在大数据管理中得到广泛应用,而key-value(KV)模型则是NoSQL系统中使用最广泛的一种存储模型.KV型本地存储系统对于以机械磁盘为持久化存储的情形,存在许多性能优化技术,但这些优化技术面对当前... 详细信息

NoSQL系统因其高性能、高可扩展性的优势在大数据管理中得到广泛应用,而key-value(KV)模型则是NoSQL系统中使用最广泛的一种存储模型.KV型本地存储系统对于以机械磁盘为持久化存储的情形,存在许多性能优化技术,但这些优化技术面对当前的硬件发展新趋势,如多核处理器、大内存和低延迟闪存、非易失性内存NVM(Non-Volatile Memory)等,难以充分发挥新硬件的优势,如数据索引、并发控制、事务日志管理等技术在多核架构下存在多核扩展性问题,又如数据存储策略不适应闪存SSD(Solid State Drive)的新存储特性而产生了IO利用率低效的问题.针对多核处理器、大内存和闪存、NVM等硬件发展新趋势,文中面向当前的大数据应用背景,综述了KV型本地存储系统在索引技术、并发控制、事务日志管理和数据放置等核心模块上的最新优化技术和系统研究成果.从处理器、内存和持久化存储的角度概括了KV型本地存储系统当前存在的最优技术,总结了当前研究尚未解决的技术挑战,并对KV型本地存储系统在CPU缓存高效性、事务日志扩展性和高可用性等方面的研究进行了展望.

关键词： NoSQL 键值存储多核扩展性并发数据结构日志结构合并型存储 SSD/NVM

TSO内存模型下限界可线性化的可判定性研究

在线全文

学校读者我要写书评

暂无评论

软件学报 2022年第8期33卷 2896-2917页

作者：王超吕毅吴鹏贾巧雯西南大学计算机与信息科学学院软件研究与创新中心重庆400715 计算机科学国家重点实验室(中国科学院软件研究所) 北京100190 中国科学院大学北京100049

TSO-to-TSO可线性化、TSO-to-SC可线性化和TSO可线性化是Total Store Order(TSO)内存模型下可线性化的3个变种.提出了k-限界TSO-to-TSO可线性化和k-限界TSO可线性化,考察了k-限界TSO-to-TSO可线性化、k-限界TSO-to-SC可线性化和k-限界TSO可线性化的验证问题.它们分别是这3种可线性化的限界版本,都使用k-扩展历史,这样的扩展历史对应的执行有着限界数目(不超过k个)的函数调用、函数返回、调用刷出和返回刷出动作.k-扩展历史对应执行中的写动作数目是不限界的,进而执行中使用的存储缓冲区的大小也是不限界的,对应的操作语义是无穷状态迁移系统,所以3个限界版本可线性化的验证问题是不平凡的.将定义在并发数据结构与顺序规约之间的k-限界TSO-to-TSO可线性化、k-限界TSO-to-SC可线性化和k-限界TSO可线性化的验证问题归约到k-扩展历史集合之间的TSO-to-TSO可线性化问题,从而以统一的方式验证了TSO内存模型下可线性化的3个限界版本.验证方法的关键步骤是判定一个并发数据结构是否有一个特定的k-扩展历史.证明了这个问题是可判定的,证明方法是将这一问题归约为已知可判定的易失通道机器的控制状态可达问题.本质上,这一归约将每一个函数调用或函数返回动作转化为写、刷出或cas(compare-and-swap)动作.在TSO-to-TSO可线性化的定义中,一个函数调用或函数返回动作会同时影响存储缓冲区和控制状态.为了模拟函数调用或函数返回动作对存储缓冲区的影响,在每个函数调用或函数返回动作之后立刻执行一个特定的写动作.这个写动作及其对应的刷出动作模拟了函数调用或函数返回动作对存储缓冲区的影响.引入观察者进程,为每个函数调用或函数返回动作“绑定”一个观察者进程的cas动作,以这种方式模拟了函数调用或函数返回动作对控制状态的影响.因此证明了TSO内存模型下可线性化的这3个限界版本都是可判定的,进而证明了在TSO内存模型下判定可线性化的这3个限界版本的复杂度都在递归函数的Fast-Growing层级■中.通过证明已知对应复杂度的单通道简单通道机器的可达问题和TSO内存模型下可线性化的3个限界版本可以互相归约得到这个结论.

关键词：并发数据结构可线性化 TSO内存模型可判定性易失通道机器

在线全文

学校读者我要写书评

暂无评论

基于低冲突帮助机制的快速无等待哈希表算法

计算机工程 2015年第11期41卷 52-58页

作者：李鹏飞张坤龙康超凡天津大学计算机科学与技术学院天津300072

针对现有无等待哈希表算法未充分利用哈希表的固有并行性,造成线程之间存在高冲突和高冗余的问题,提出一种快速无等待哈希表算法。利用可冻结集合思想简化哈希表操作,采用CAS原子指令保证插入、删除与查找操作均为无等待。根据哈希表结... 详细信息

针对现有无等待哈希表算法未充分利用哈希表的固有并行性,造成线程之间存在高冲突和高冗余的问题,提出一种快速无等待哈希表算法。利用可冻结集合思想简化哈希表操作,采用CAS原子指令保证插入、删除与查找操作均为无等待。根据哈希表结构改进帮助机制,使得哈希桶的实现为无等待,只有在扩展哈希表时哈希桶之间才提供帮助。实验结果表明,该算法能降低线程操作间的冲突,提高帮助操作的并行度,当查找率为0、键值范围为0~256且线程数为8时,其吞吐率是现有无等待哈希表算法的2.5倍。

关键词：并发数据结构哈希表无等待可线性化可扩展

并发多播队列的实现框架及其多种实现的性能分析

在线全文

学校读者我要写书评

暂无评论

小型微型计算机系统 2017年第6期38卷 1237-1242页

作者：张其良张昱中国科学技术大学计算机科学与技术学院合肥230027

开发易用且高效的并发数据结构对降低并行编程的难度和有效利用并行资源非常重要.针对所提出的易于编程的确定性消息传递多线程编程模型DetMP,除可以基于所提出的单生产多播共享虚拟内存模型(SPMC)实现以外,还可以基于传统的多线程共享... 详细信息

开发易用且高效的并发数据结构对降低并行编程的难度和有效利用并行资源非常重要.针对所提出的易于编程的确定性消息传递多线程编程模型DetMP,除可以基于所提出的单生产多播共享虚拟内存模型(SPMC)实现以外,还可以基于传统的多线程共享虚拟内存模型来实现.为了分析消息通道的实现机制(如数据的存储组织、并发访问的同步控制)对DetMP程序性能的影响,提出一个并发多播队列的框架CMQue,并基于Pthreads实现了6种并发多播队列.我们评估了6种并发多播队列和SPMC通道,结果表明消息通道的实现机制对程序性能影响很大,SPMC通道在CPU核资源充足时具有很好的可伸缩性.

关键词：多播队列并发数据结构同步控制多线程编程模型生产-消费

在线全文

学校读者我要写书评

暂无评论

基于改进区块链的智能制造安全模型

计算机科学 2021年第2期48卷 295-302页

作者：王卫红陈震宇浙江工业大学计算机学院杭州310023

针对传统区块链智能制造安全模型存在的区块构建和数据查询速度慢、插入查询操作的时间复杂度高等难题,提出了基于改进区块链的智能制造安全模型。首先为了克服传统区块链耗电量大和吞吐量低的弊端,引入新型Merkle Patricia树(MPT)扩展... 详细信息

针对传统区块链智能制造安全模型存在的区块构建和数据查询速度慢、插入查询操作的时间复杂度高等难题,提出了基于改进区块链的智能制造安全模型。首先为了克服传统区块链耗电量大和吞吐量低的弊端,引入新型Merkle Patricia树(MPT)扩展区块链结构,以提供节点状态的快速查询;然后针对MPT不支持并发操作和高负载状态下性能较差的问题,设计无锁并发缓存Merkle Patricia树,支持无锁的并发数据操作,可以提升在多核系统下的效率;最后采用具体仿真实验分析了所提模型的性能。结果表明,改进区块链的智能制造安全模型可以有效降低插入查询操作的时间复杂度,大幅提升区块构建和数据查询的速度,相较于传统模型,获得了更优的整体性能。

关键词：智能制造工业物联网区块链 Merkle Patricia树并发数据结构

在线全文

学校读者我要写书评

暂无评论

基于帮助机制的无界无等待通用构造算法

计算机工程 2017年第11期43卷 22-26页

作者：苏浩张坤龙李鹏飞天津大学计算机科学与技术学院

已有的无等待通用构造算法大多只考虑有界无等待的情况,并不适用于无界无等待并发模型。为此,提出一种新的无等待通用构造算法——UWUC。该算法使用Fetch&Add对象和列地址选通脉冲对象,给出新的排队方法,利用任意一段时间内到达的线程... 详细信息

已有的无等待通用构造算法大多只考虑有界无等待的情况,并不适用于无界无等待并发模型。为此,提出一种新的无等待通用构造算法——UWUC。该算法使用Fetch&Add对象和列地址选通脉冲对象,给出新的排队方法,利用任意一段时间内到达的线程数有限的特性,实现无界无等待的通用构造。实验结果证明了该算法的无等待特性。

关键词：并发数据结构无等待通用构造无界无等待非阻塞列地址选通脉冲

在线全文

学校读者我要写书评

暂无评论

非阻塞无序链表的研究

非阻塞无序链表的研究

作者：赵玉姣天津大学

学位级别：硕士

随着计算机硬件技术的高速发展,多核处理器已经开始被广泛使用,并发编程技术的应用可以极大的提升性能。锁的应用虽然可以保证资源的独享以及并发程序的正确性,但是随着线程数的增加,竞争的激烈,可能会造成多个线程的等待,甚至产生死锁... 详细信息

随着计算机硬件技术的高速发展,多核处理器已经开始被广泛使用,并发编程技术的应用可以极大的提升性能。锁的应用虽然可以保证资源的独享以及并发程序的正确性,但是随着线程数的增加,竞争的激烈,可能会造成多个线程的等待,甚至产生死锁等问题。而非阻塞的算法可以避免死锁,并提供更好的扩展性,但是非阻塞算法的编程更加复杂,后期维护也相对困难,在竞争较少的情况下,可能由于其结构的复杂性而导致性能低于使用锁的算法。尽管如此,实现一个并发的低延迟的无阻塞数据结构仍然是非常有价值的。本文针对链表这一最基本的数据结构进行了非阻塞实现的研究,提出了一个并发无序无锁的链表算法、两个无等待算法,以及一个兼容性的调整算法,该算法既保证了链表的无等待特性,又保持了比较好的性能。这些链表所对应的数据抽象集合为一个不含重复数据的无序的集合。算法的主要思想是将数据与操作结合在一个结点中,线程之间可以通过共享链表上面的结点内容进行通信与控制,并通过线程之间的互相帮助来完成无阻塞的实现。除此之外,还将查找设计为一个只读的方法,以此来提升整体性能。在实验中,将线程数、操作的比例以及键值范围作为可变参数进行调整并与一些经典算法进行比较来验证其性能。实验结果表明当线程数较多、查找的操作比例偏高且链表长度较长的情况下,本文提出的算法性能非常良好。

关键词：非阻塞链表并发数据结构

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于无锁方法的二叉搜索树算法研究

基于无锁方法的二叉搜索树算法研究

作者：于欣河北科技大学

学位级别：硕士

随着多核/众核技术的发展,高并发的数据结构成为并发程序设计的研究热点。二叉搜索树应用范围广泛,在并发数据结构中占有重要地位。高并发无锁二叉搜索树算法的设计与实现将对并发程序的设计提供强有力支持。目前针对二叉搜索树算法的研... 详细信息

随着多核/众核技术的发展,高并发的数据结构成为并发程序设计的研究热点。二叉搜索树应用范围广泛,在并发数据结构中占有重要地位。高并发无锁二叉搜索树算法的设计与实现将对并发程序的设计提供强有力支持。目前针对二叉搜索树算法的研究,存在多个线程对共享资源的同步访问问题。传统解决方案使用锁机制进行同步,以确保线程的安全访问,但容易引起锁竞争和死锁等问题,导致算法效率低下。针对二叉搜索树算法使用锁机制引起的问题,本文提出了一种新的无锁算法。该算法使用比较和交换(CAS)指令,在异步共享内存系统中完成对二叉搜索树的搜索,插入和删除操作。本文算法使用外部(面向叶子)搜索树模型,该模型的优点是不存在删除具有两个孩子结点的情况,从而提高了删除操作的效率。与研究二叉搜索树需要获得内部节点的方式不同,本文算法运用整体的思想,通过操作子树来处理插入和删除操作。本文介绍了无锁二叉搜索树算法的设计细节,在各种条件(不同的树形大小,工作量分布和争用度)下进行了实验,将本文的算法与Bronson等人基于锁的算法、Ellen等人基于无锁的算法进行了吞吐量大小的比较。实验结果表明,当线程数大于4时,本文算法的吞吐量优于其他两个并发BST算法,可以有效地减少更新(插入或删除)操作之间的争用。当并发性较高时,本文的算法将具有一定竞争力。

关键词：并发数据结构无锁二叉搜索树 CAS 可扩展

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于并行计算的多机器人任务调度方法

基于并行计算的多机器人任务调度方法

作者：李兴宝南京理工大学

学位级别：硕士

多机器人协作系统是一个具有多个机器人和多个共享资源的复杂离散事件动态系统,而多机器人任务调度则旨在调度机器人利用系统中可用资源来完成给定的若干任务,调度的目标是使得所有任务能在最短时间内完成,以最大化系统资源的利用率,尽... 详细信息

多机器人协作系统是一个具有多个机器人和多个共享资源的复杂离散事件动态系统,而多机器人任务调度则旨在调度机器人利用系统中可用资源来完成给定的若干任务,调度的目标是使得所有任务能在最短时间内完成,以最大化系统资源的利用率,尽量减少系统可用资源的空闲等待时间。多机器人最优任务调度在现实中许多领域都具有十分重要的意义。例如在柔性制造系统中,最优的任务调度不仅意味着单位时间内能产出更多的产品以应对千变万化的市场需求,还能极大地提高系统资源的使用率、降低产品生产成本等等;又例如在自动化军事领域,最优的任务调度意味着能更快地对敌情做出反应、迅速完成打击目标任务等等。然而,多机器人任务调度问题属于最难解的一类NP-hard组合优化问题,甚至对于一些小规模问题,都无法在可接受的多项式时间内求解出一个最优解决方案。其应用前景虽然十分诱人,但其本身固有的计算复杂性给其应用带来了巨大的挑战,针对上述难点,本文提出基于并行计算的多机器人快速任务调度方法,利用更多物理计算资源的并行工作方式来加速问题求解过程,具体内容包括:(1)提出一种基于多核计算的并行A算法用于多机器人任务调度。通过将串行A算法扩展结点的方式转换为并行多结点扩展从而得到并行A算法;基于多核计算的并行算法使用共享内存模型,存在数据竞争访问问题,为此设计了两种高效的支持并发访问的Treap数据结构用于表示OPEN列表,并设计了两种高效的支持并发访问的二叉平衡树用于表示CLOSED列表;采用OPENMP框架实现并行算法,在4核计算设备上进行实验测试最高观察到了2.4倍的加速比;观察到散列分区机制对于设计并发数据结构的通用性,本文将其抽象提升为一种独立于特定问题的并发数据结构设计方法,并将其应用到基于共享内存模型的Petri网可达图并行生成算法中,不仅验证了此设计思想的有效性和通用性,还提出了一个能快速生成Petri网可达图的并行算法。(2)基于多核计算的并行A算法性能通常受限于机器所拥有的实际物理核数,对此提出一种基于多机计算的并行A算法用于多机器人任务调度。通过将串行A算法扩展结点的方式转换为并行多结点扩展从而得到并行A算法;基于多机计算的并行算法使用分布式内存模型,采用一个散列分区机制分别将OPEN列表和CLOSED列表拆分成若干个子列表并将其分布式存储于各个计算节点上;采用MPI消息传递接口实现并行算法,在由高速路由器间接相连的两个计算节点上进行实验测试最高观察到了1.4倍的加速比。(3)为了能更加充分地利用系统物理计算资源来加速多机器人任务调度问题的求解,提出将上述两种方法相结合的多核+多机并行计算的A搜索算法。通过在多机并行A算法的基础上,让每一个计算节点都并行处理其分配到的后继结点而得到并行算法;将每一个计算节点拥有的OPEN子列表和CLOSED子列表使用多核并行A中的方法,设计为高效支持并发访问的数据结构以应对数据竞争访问问题;混合使用OPENMP框架+MPI消息传递接口实现此并行算法,在由高速路由器间接相连的两个4核计算节点上进行实验测试最高观察到了约4倍的加速比。(4)针对A算法在内存方面的大量需求,提出一种基于Spark云计算平台的并行IDA算法用于多机器人任务调度。采用并行窗口搜索方法对IDA算法进行并行化,将具有不同代价阈值的深度优先搜索并行实施,通过实验验证了这种方法的可行性与有效性。

关键词：多机器人任务调度离散事件动态系统并行计算 A*算法 IDA*算法 Spark云计算散列分区机制并发数据结构 Petri网可达图