共享内存并行系统上空间数据检索及优化研究 .pdfVIP

共享内存并行系统上空间数据检索及优化研究

长久以来,科学计算、企业数据处理、多媒体等领域推动并行计算向更高性

能、更低成本、更多样地适应需求的方向发展。随着信息检索相关应用中数据量

的增加,以及查询难度和需要实时响应的查询数量的增加,提供相关信息检索服

务必须以强有力的并行计算平台做支撑。

空间数据检索是信息检索领域一个快速发展的领域。随着手机,掌上电脑、

GPS等移动计算设备及各种移动传感器的普及使用,越来越多的应用需要计算随

时间不断变化的移动物体信息。

在不远的未来,计算将无处不在；需要管理大量的位置相关的物体,既有静止

的对象,也有大量位置不断变化的移动对象。基于位置的服务相关应用是正是利

用了这些空间信息为用户提供多种多样的服务,比如基于位置的手机业务和电子

商务；智能交通；智能监控系统；无线传感器网络系统等。

在多种多样的应用中,大多数的应用的数据规模远远超出的单CPU的处理能

力,而且还会不断地增加。本论文主要研究并行平台上的空间数据索引和检索问

题,以及相关的并行优化方法。

特别是线程级并行和指令级并行相结合的并行优化方法、共享内存系统上支

持并发访问的大规模移动对象的索引、支持并发的移动点持续查询、不同粒度的

锁协议及lock-free并发控制方法。本文针对并行优化以及空间数据索引的研究,

可以有效改善并行平台上的空间数据索引的相关应用,具有重要的学术价值和广

泛的应用前景。

具体而言,本文的主要研究成果、贡献和创新点可概括为以下几点：(1)研究

多核多线程并行和SIMD指令级并行相结合的方法本文研究了多核平台上的线程

级并行和指令级并行的优化方法。线程级并行和指令级并行相结合,可以充分利

用CPU的多核多线程资源和SIMD指令级并行资源。

特别是在指令级并行中,使用SIMD指令,可以把占大量CPU时间的随机条件

分支转化成算术逻辑指令,从而可以使用指令级并行。该方法应用到大规模图像

特征提取中,并创造性地使用SIMD指令消除了在图像特征提取中存在的若干程

序热点,使其性能有明显提升。

(2)提出共享内存系统上GKd-树索引结构移动对象的空间数据索引是高效

支持移动对象更新和查询的关键。本文研究了现有的移动对象索引算法,针对内

存中常用的网格索引和Kd-树索引的不足,提出了GKd-树索引结构。

对于空间索引的位置查询操作、位置更新操作和区域查询操作有更好的算法

复杂度；并具有便于并行化和支持并发控制的特性。GKd-树索引改善了现有的基

于区域划分的空间移动对象数据索引,可以高效地支持大规模移动对象的并发检

索。

(3)提出共享内存系统上“查询即索引”的索引结构在移动对象管理的相关

的应用中,有很大部分应用中查询是持续的,可以利用查询的持续性对查询进行

优化。本文针对原有持续性索引中索引结构和查询结果相分立带来的冗余和同步

等开销,提出“查询即索引”的索引结构。

新的索引方法将索引和查询结果相统一,并且通过使用基于对象ID的辅助

索引和空间索引相结合的方式,降低了持续查询的复杂度,便于并行化和支持并

发控制,使数据更新和持续性查询的吞吐量、查询实时性等有明显提升。(4)研究

并优化应用于移动对象索引的细粒度锁和无锁化并发控制方法在原有的并发移

动对象索引中,一个显著问题是锁的粒度过高,不利于支持大规模且并发到来的

更新和查询操作。

使用细粒度锁可以减小并发冲突的范围,提高并发度；基于CPU的CAS指令

的事务性内存并发控制,可以使对象在不同索引区域中的移动操作并发无锁化

(lock-free)、无阻塞。该方法和改变索引结构时使用的粗粒度锁相结合,可以使

索引的并发控制更加灵活、更高效、更加适用于多变的应用环境。