三維重構(gòu)算法中球諧函數(shù)的并行計算的實現(xiàn)

肖晨陽　施游

摘要：采用基于球坐標系的病毒三維重構(gòu)算法中球諧函數(shù)的計算非常復(fù)雜，在單機單核上耗時很長。通過分析，該文實現(xiàn)了一種基于OpenMP的多核并行方法，可以提高球諧函數(shù)計算速度，實驗結(jié)果證明方法簡單有效。

關(guān)鍵詞：多核系統(tǒng)；并行計算；OpenMP

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2017）33-0083-02

結(jié)構(gòu)決定功能，生物大分子同樣如此。生物大分子三維結(jié)構(gòu)研究對于了解其功能及生物學(xué)機制等具有非常重要的意義。結(jié)構(gòu)生物學(xué)方法包括X射線晶體學(xué)方法（X-ray crystallography）、核磁共振技術(shù)（nuclear magnetic resonance spectroscopy）和冷凍電鏡技術(shù)[Cryo-electron microscopy （Cryo-EM） single particle]。近年來，隨著冷凍電子顯微鏡技術(shù)的發(fā)展、三維重構(gòu)算法的不斷完善及計算機計算能力的不斷提高等，冷凍電鏡技術(shù)，特別是冷凍電鏡單顆粒技術(shù)（Cryo-EM single particle）已成為解析大型蛋白質(zhì)復(fù)合體、病毒乃至細胞器高分辨三維結(jié)構(gòu)的最有力工具之一，其在結(jié)構(gòu)生物學(xué)中正扮演著越來越重要的角色。

在生物大分子三維重構(gòu)實現(xiàn)中需要用到數(shù)萬個二維投影顆粒的冷凍電鏡照片，對二維投影顆粒的處理過程中每次都要重復(fù)進行中心移位，球諧函數(shù)計算等處理操作。普通的計算機單核線程處理時間長。而目前我們配備的計算機都具有八個以上線程核心，配備的服務(wù)器線程核心高達48個，傳統(tǒng)的串行程序只會跑滿一個線程核心，其他線程核心處于閑置狀態(tài)。因此充分利用線程核心很有必要。

OpenMP標準形成于二十世紀九十年代，用于多處理器核心并行程序設(shè)計的一套方案，能夠充分利用現(xiàn)有的CPU的硬件資源，目前OpenMPC、C++和Fortran等程序語言，也支持GNU的編譯器，符合我們當(dāng)前使用的程序設(shè)計方案。采用OpenMp可以在現(xiàn)有的程序代碼中提專用的pragma等編譯指導(dǎo)語句，編譯器可以自動將程序進行并行化，容易改造，成本比較低。

采用基于球坐標系的病毒三維重構(gòu)算法，已經(jīng)成為基于冷凍電鏡技術(shù)進行三維重構(gòu)的重要方法。其中關(guān)于對稱匹配函數(shù)的計算量大，耗時長。

對稱匹配函數(shù)的計算包括組合系數(shù)[Aμl，m]和球諧函數(shù)[Yl，m]兩部分，高階組合系數(shù)可以由低階系數(shù)通過復(fù)雜遞推關(guān)系獲得。球諧函數(shù)可表示為：

[Yl，m（θ，?）=（-1）m（2l+1）（l-m！4π（l+m）！Pml（cosθ）eim?] （1）

其中[Pml（cosθ）]為締合勒讓德多項式，可表示為：

[Pml（cosθ）=12ll！sinmθdl+m（dcosθ）l+m（cos2θ-1）l] （2）

由上可見，單個球諧函數(shù)的計算變得非常復(fù)雜，而對于球諧函數(shù)組成的對稱匹配函數(shù)，比如，l=1000，需要Y1000，0， Y1000，1， ….， Y1000，1000共1001個球諧函數(shù)的組合，而且考慮基函數(shù)完備性，l=1000時還有35種不同的多重性（μ=35），即35種不同的組合方法，因此，整個計算過程變得更加復(fù)雜。我們從此算法過程可以看出，35種組合方法的組合系數(shù)和球諧函數(shù)的計算可以由通過OpenMp并行處理。

如圖1所示為并行程序設(shè)計流程圖，圖2 為串行程序設(shè)計的流程圖，二者的主要區(qū)別在于串行程序每次計算一個顆粒，并行程序每次計算100個顆粒。

由于每個顆粒的計算完全獨立，不需要進行數(shù)據(jù)共享和數(shù)據(jù)通訊，所以用OpenMP非常方便，僅僅使用 ！$OMP PARALLEL ，！$OMP END PARALLEL即可。以下為偽代碼：

program main

Use omp_lib

Call ReadPara（100）

！$OMP PARALLEL

Do pid=first，last

Call ComputeStick（para）

End do

！$OMP END PARALLEL P

End program

ReadPara函數(shù)是讀入多個顆粒數(shù)據(jù)，ComputeStick函數(shù)是計算球諧函數(shù)。

結(jié)果與分析：

我們使用計算CPV病毒的程序（以下簡稱為串行程序），計算過程是取10409個顆粒進行計算。在主頻3.5G intel i7的CPU上運行，串行程序，需要時間是接近3小時。經(jīng)過并行化改造后，僅僅需要30分鐘左右，執(zhí)行效率提高了5倍。采用OpenMp方法對原來程序改造，修改代碼很少，效果明顯。

參考文獻：

[1] 周偉明.多核計算與程序設(shè)計[M].武漢： 華中科技大學(xué)出版社，2009.

[2] 張平，李清寶，趙榮彩.OpenMP并行程序的編譯器優(yōu)化[J].計算機工程，2006，32（24）：37-40.

[3] Parallel Programming in Fortran 95 using OpenMP [EB/OL].Fortran Coder.http：//www.fcode.cn

[4] OpenMp homepage [EB/OL] .http：//www.openmp.org/endprint