mpi中利用自定義歸約操作實作merge

在歸并排序中，很重要的一步是将兩個排序數組合并成一個數組，這個操作叫merge。merge操作可以用來解決某些Top K問題。

在哼唱搜尋中，使用者通過哼唱一個音樂片段去搜尋與其相似的音樂。背景的實作主要有兩個步驟：特征提取和特征比對。特征提取是從原始波形音樂檔案中提取最能代表音樂的特征。特征比對就是利用提取的特征與特征庫進行比對，找到最相似的音樂。在實際情況中，特征庫往往很大，目前商用的特征庫已達千萬級别，這樣的規模已經遠遠超過單機的處理能力，是以需要利用叢集進行特征的比對。

在叢集的每個節點上各存放特征庫的一部分，所有不相交的特征庫子集構成完整的特征庫。叢集的每個節點首先從主節點接收經過特征提取的使用者哼唱特征，然後與自己的部分特征庫進行比對，傳回Top K。最後利用MPI的規約函數将每個節點上的Top K規約成一個Top K傳回給使用者。

主要的代碼就是利用自己定義的規約操作完成merge操作。

1.       特征比對的結果是一個表示兩個音樂相似性的距離，越小說明兩首歌越相似。首先定義規約的資料結構：

2.       利用定義的資料結構聲明一個MPI類型：

我們采用的方法是利用MPI的MPI_Type_struct聲明一個結構資料類型。在distance結構體中共有兩個變量，是以MPI_Type_struct的中間三個參數都是長度為2的數組。這裡需要注意的是，結構體的變量個數與結構體聲明的個數無關，而與變量的類型數相關。例如結構體：

該結構體共有6個變量，但是在MPI結構類型中隻有兩個塊{double,int}，長度分别是{4,2}。

MPI_Type_struct的五個參數意義分别是：第一個參數指明結構體變量的塊數，上面的兩個例子都是2；第二個參數指明每個塊的長度，上面的例子分别是{1,256}和{4,2}；第三個參數指明每個塊的偏移，簡單的結構體可以利用sizeof獲得，此外還可以利用MPI_Type_extent和MPI_Address獲得；第四個參數指明每個塊的變量類型；第五個參數就是根據我們聲明的結構體傳回的MPI變量類型。

3.       自定義歸約操作實作merge：

使用者自定義的歸約操作是原型為：typedef void MPI_User_function(void *invec, void *inoutvec, int*len, MPI_Datatype *datatype);的函數。該函數有四個參數，第一個參數是資料輸入，第二個是資料輸入和輸出，第三個參數是資料的長度，第四個是自定義歸約操作的資料類型。

merge操作就是将兩個排好序的數組合并成一個，這裡有一點不同的是：合并的結果長度和輸入資料長度相同，也即兩個Top K結果合并成一個Top K結果。輸入和輸出的資料類型即是我們之前聲明的類型distance。合并代碼和正常的合并代碼類似，但稍有不同。由于第二個變量既表示輸入有代表輸出，是以我們無法進行原地merge操作，在此我們引入一個臨時變量result，将merge的結果先放入到result變量，最後再将result的結果拷貝到inout數組中。雖然這樣顯得浪費空間，但是這保證了正确性。

4.       主代碼調用：

主代碼流程比較簡單，從指令行擷取要比對的序列，然後将該序列從MASTER廣播到所有的程序。每個程序利用廣播的序列與特征庫進行比對，然後将結果進行排序。最後利用自定義歸約操作将排好序的檔案歸約到MASTER程序。