论文部分内容阅读
在当今大数据时代的环境下,互联网上的数据量愈发庞大,且其增长速率还有着不断加快的趋势。高速增长的数据量催生了各种各样以数据为中心的应用,而这些应用在丰富了互联网用户在工作、学习和生活等多方面体验的同时,也引发了用户对这一类应用愈发急切的需求。在这些面向大数据的应用中,多媒体数据相关应用凭借其丰富的内容和强大的表现力成为了主流,这也使得为多媒体数据相关应用提供基础支持的相关算法之一——图像检索算法成为了新的研究热点。但是在实际的应用中,由于图像检索算法兼具计算密集和数据密集的特征,在面临较大的数据量时,其效率难以满足当前用户的需求。在计算方面,高维数据和复杂的欧拉距离运算导致了极为庞大的计算量,耗费时间极为漫长;而在输入输出方面,庞大的数据量会在输入输出的带宽上造成巨大的压力,甚至可能因内存容量限制导致了多次反复的数据读取,使得计算极度缓慢。Vocabulary Tree作为当前的一个有着较高精确度用于进行特征匹配的主流图像检索数据结构,也同样存在着上述处理效率不足的问题,特别是其进行建树的训练阶段所耗费的时间更为漫长。如当今一些泛用性质的图像库可达到百万级别的图像张数,而Vocabulary Tree建树算法的串行实现对约101万张图像的数据库进行建立索引树,包括输入输出和计算处理的整个过程就需要耗费长达约12.6天的时间,这样的时间开销在实际应用中难以接受,亟需要有针对Vocabulary Tree建树算法本身的数据密集和计算密集特征进行加速优化的方法,才能保证其效率能满足当前的用户需求。本文基于对Vocabulary Tree建树算法基本逻辑和特征的分析,明确了该算法在性能方面的局限性所在,结合当前不断普及的多核处理器和集群环境,循序渐进地实现了多个Vocabulary Tree建树算法的并行优化版本。这些并行优化的设计兼顾计算密集和数据密集的特征,体现了从简单到复杂的各种不同设计思路。其中,针对计算并行优化的设计包括各种不同的并行任务的处理和分配方式,而针对输入输出优化的设计包括了数据的并行处理和格式调整。这些设计综合考虑了单机和集群环境的差异,实现了对Vocabulary Tree建树算法在处理计算和输入输出效率上的提升。本文的主要贡献包括:● 梳理了Vocabulary Tree建树算法的整个过程:分析其计算密集和数据密集特征的具体表现,并指出其潜在的并行优化空间以及实现并行化的主要难点。● 针对计算逻辑上的计算密集特征:设计并实现了Vocabulary Tree建树算法的包括通过预估计算量来分配处理器核的静态并行、在计算量变小时动态调用空闲处理器核的半动态并行和完全由处理器核主导的全动态并行设计在内的多种计算并行优化版本。● 针对输入输出上的数据密集特征:设计并实现了Vocabulary Tree建树算法输入输出部分的并行,随后面向更大规模的数据量分析了单机并行的局限性所在,在单机并行实现的基础上,结合了当前主流的MPI并行框架,设计并实现了Vocabulary Tree建树算法的集群数据并行优化版本,并进一步探讨数据格式调整和优化存储层次能带来的性能提升。实验结果表明,针对约11万张的图像库,单机48路并行可达到约36倍的计算加速、约36倍的输入输出加速和约32倍的总体并行加速效果;针对较大的61万张图像库,集群4机器节点8进程并行可达到近60倍的总体并行加速效果,而针对更大的101万张图像库,配合数据格式调整和存储层次优化,则有高达300倍左右的加速效果。