[发明专利]一种基于GPU的旋律匹配并行化方法

摘要

一种基于GPU的旋律匹配并行化方法，该方法有四大步骤步骤1在CPU上的计算准备工作；步骤2在GPU上进行的计算前的变量初始化操作；步骤3在GPU上进行的实际的DTW计算；步骤4在CPU上进行的后续结果整理。该方法首先对DTW算法中累积距离矩阵的计算顺序进行改变，采用对角线计算的方法，消除矩阵元素计算之间的数据依赖性，达到使用GPU对单个DTW计算进行加速的目的；然后将对角线计算的方法与多个DTW计算任务之间的并行计算相结合，使得GPU在对单个DTW计算进行加速的同时也能够对多个DTW计算进行并行计算，达到GPU对多个DTW计算也能进行加速的目的。本发明编程简单，加速比和性价比高，它在计算机技术领域里具有广阔地应用前景。

主权项

一种基于GPU的旋律匹配并行化方法，首先要明确累积距离矩阵的对角线计算方法；在经典DTW算法中，核心是要计算两个序列X和Y的累积距离矩阵D，由经典DTW算法的相关定义，假设序列X与Y等长；在经典DTW算法中，计算每一个元素的时候都需要这个元素左方、上方以及左上方的元素的值，除了第0列和第0行中的元素，这就使得计算的数据依赖性较强，每个元素必须依次计算；为了消除这种数据依赖性，基于GPU的旋律匹配并行化方法改变了元素的计算顺序，按照对角线的方式进行计算，即计算顺序变为：(1)初始化矩阵元素D(0,0)，D(0,1)，D(1,0)；(2)对于i从2到N‑1，同时计算位于对角线D(0,i):D(i,0)上的各个元素；在计算对角线上的任意一个元素时，这个元素左方、上方以及左上方的元素的值都已经被计算出来了，利用GPU来对DTW算法本身做并行化处理；无论采用何种方式进行计算，DTW算法最终的计算结果都会得到一个N×N的累积距离矩阵D，在经典的DTW算法中，只需要N×2的空间就足以完成计算；在累积距离矩阵的对角线计算方法中，计算一条对角线上的值，在矩阵中体现为一个上三角；将D的一条对角线对应到F中的一行，对角线D(5,0):D(0,5)对应到F(1,0):F(1,5)，在计算某一条对角线上的某个元素时，所依赖的是D(1,2)，D(1,3)和D(2,2)，转化到F中，d(2,3)对应的应当是f(i,3)(i＝0,1,2)，假设i＝2，则D(2,3)对应的是F(2,3)，那么它所依赖的三个元素也对应到F中后分别是F(0,2)，F(1,3)和F(1,2)；F为3×N的数组空间；在计算中，F是循环利用的，每次计算只需要用到两行元素，剩余的一行就用来保存结果，当前需要依赖的是第0行和第1行元素，那么此次计算的结果就保存到第2行中，到了下一次计算，所依赖的就是第1行和第2行元素，第0行元素就不再需要了，就将这一次计算的结果覆盖到第0行中去，如此往复；基于GPU的旋律匹配并行化方法所针对的计算对象是一个长度为N的待匹配序列X以及一个包含M个序列的序列库Y，Y中的最大序列长度为L，基于这个前提，具体的步骤如下：步骤1：在CPU上的计算准备工作，具体的步骤细分如下：步骤11：将要进行计算的待匹配序列X以及序列库Y读入到内存中；步骤12：在GPU的全局内存中分配计算所需要的空间；步骤13：将CPU读入的数据拷贝到GPU的全局内存中；步骤2：在GPU上进行的计算前的变量初始化操作，具体的步骤细分如下：步骤21：通过调用GPU核函数对所有的累积距离矩阵进行初始化；步骤3：在GPU上进行的实际的DTW计算，具体的步骤细分如下：步骤31：通过循环调用GPU核函数逐步计算累积距离矩阵，得到DTW距离；步骤4：在CPU上进行的后续结果整理，具体的步骤细分如下：步骤41：将GPU计算得到的结果拷贝回CPU；步骤42：使用CPU对结果进行遍历，找到最小的值作为X与Y的DTW距离；其中，步骤11中，需要将X以及Y中的所有序列首先读入到内存中；其中，步骤12中，GPU全局内存中所需要的空间包括：存储X和Y中的所有序列所需要的空间，M个累积距离矩阵所需要占用的存储空间；其中，步骤13中，要进行拷贝的数据为序列X和序列库Y；其中，步骤21中，这里需要的线程总数为M，一个线程用来初始化一个累积距离矩阵；其中，步骤31中，这里需要的线程总数为M×min(L,N)，需要的循环次数为L+N‑1，一次循环中，计算的是M个累积距离矩阵相同位置对角线上的所有元素，一次循环的一个线程中对应的是M个累积距离矩阵中的一个矩阵的一条对角线上的一个元素的计算；其中，步骤41中，M个累积距离矩阵会得到M个DTW距离，将这M个DTW距离拷贝回CPU；其中，步骤42中，遍历的对象是M个DTW距离，选取其中最小的值。