题目：哼唱检索的并行化方法 研究与实现

哼唱检索是一种新型的音乐检索方式，与常规的文本检索方式相比，哼唱检索为用户提供了更便捷、更自然、更人性化的检索方式和更佳的搜索体验。然而，当前的哼唱检索面临实时性差、音乐库规模小等诸多问题，影响了其实用性。哼唱检索系统中通常包含两个大的功能模块：特征提取和特征匹配。特征提取是从音乐中提取特征构造一个特征库，特征匹配则是利用提取的特征进行检索，找到用户哼唱的音乐。

本论文以大规模音乐库的哼唱检索为研究对象，针对当前大规模音乐库哼唱检索实时性差的问题，采用GPU和MPI作为核心的加速手段，对哼唱检索中的特征提取算法和特征匹配算法进行优化和加速，以提升大规模音乐库哼唱检索的性能。

本论文主要研究内容和取得的成果如下：


多声部音乐的特征提取算法及其GPU加速


为了能构造一个大规模的特征库，当前的系统都选择从MP3、wav等多声部音乐而不是MIDI文件中提取最能代表音乐属性的音高特征。本论文优化实现了一种和当前最优算法准确率非常接近，但复杂度显著降低的多声部音乐特征提取算法。为了提高特征提取能的实时性，同时对算法进行了GPU加速，将提取时间由几秒降到几十毫秒，加速比接近100倍，使算法达到可实时应用的程度。


基于SPRING算法的子序列匹配及其GPU加速


从多声部音乐中提取的音高序列是一种时间序列，因而其检索算法实际上是一种时间序列匹配算法。由于哼唱序列长度小于特征库中序列的长度，因而在哼唱检索系统中，检索是一个子序列匹配任务。为了减小子序列匹配的复杂度，本论文采用一种类DTW的SPRING算法作为核心的匹配方法，同时利用其计算的特殊性，采用斜对角线计算方式进行GPU加速，使单节点的处理能力达到每秒50000个子序列匹配。


基于MPI的分布式子序列匹配


由于单节点的处理能力有限，达不到处理大规模数据的要求，本论文设计并实现了一个基于MPI的分布式子序列匹配算法。测试结果表明，利用MPI对匹配算法进行分布式计算具有良好的扩展性，并且适用于实时的哼唱检索。