DAI HOC QUOC GIA HA N O I

TINH TOAN HIEU N A N G CAO
VA LfNG D U N G VAO BAI TOAN
MO P H O N G DONG L U C P H A N Ttf
Bao cao tong hdp de tai nghien ciiu khoa hoc cap
DHQG do Trudng Dai hoc cong nghe quan ly)

Ma so: QC.05.01
Chu nhiem de tai: Nguyen Hai Chau
OAI HOC QUOC GIA HA NQi
TRUNG TAM THONG ''iN ^HIJ VlE^

1 ' cU
Ha Noi - 2006


M u c luc
D a n h m u c h i n h ve

2

D a n h muc b a n g

3

1

D a n h sach can b o t h a m gia thUc hien de tai

5


N O I D U N G C U A D E TAI
3.1 Dat va,n d l
3.2 T5ng quan ve tfnh lire tu'dng tac nhanh trong mo phong dong luc
phan tii
3.2.1 Cac thuat toan nhanh trong ITnh vuc mo phong dpng luc phan
td
3.2.2 Thuat toan FMM va cac biin t h i
3.2.2.1
Thuat toan FMM
3.2.2.2
Thuat toan cua Anderson
3.2.2.3
Thuat toan ciia Makino
3.2.3 May tinh chuyen dung song song G R A P E va iing dung . . .
3.2.4 Cai dat thuat toan nhanh tren phan ciing chuyen dung . . .
3.2.4.1
Cai dat thuat toan tree tren p h i n ciing G R A P E . .
3.2.4.2
Cai dat thuat toan FMM tren p h i n ciing MD-ENGINE
3.3 Npi dung va kit qua nghien ciiu
3.3.1 Cac kho khan cin giai quylt
3.3.2 Giai phap va kit qua ciia chung toi
3.4 Thao luan

9
9
10
11
12



D a n h muc hinh ve
3.1
3.2
3.3
3.4
3.5

3.6

3.7
3.8
3.9
3.10

3.11
3.12

3.13
3.14

Y tudng chmh cua thuat toan tinh luc FMM
PhUdng phap cua Anderson
PhUdng phap P^M^ ciia Makino
Kiln triic cd ban ciia mpt he may tfnh G R A P E
May tmh MDGRAPE-2 (PCI) co t i c dp cue dai tUdng dUdng 48GFlops
vdi 4 chip MDGRAPE-2 (m5i chip co t i c dp cue dai tUdng duong
16GFlops)
May tfnh MDGRAPE-2 (Compact PCI) co t i c dp cUc dai tUdng

16

16

17
18
19
20

22
23

24
26

27


D a n h muc bang
1.1

3.1

3.2

3.3

Danh sach can bp, cong tac vien, hpc vien cao hpc va sinh vien tham
gia thuc hien d l tai
Cac pha tfnh toan va cac cdng thiic tUdng iing dUdc sii dung trong


TS

2

Nguyin Hai Chau
(chu nhiem d l tai)
T. Ebisuzaki

TS

3

A. Kawai

TS

4

Vu Bdi H i n g

ThS

5

T r i n Manh Tudng

CN

6

Dai hpc cdng nghe, DHQGHN
Trung tam tfnh toan cao cip, Vien
nghien ciiu vat ly va hda hpc Nhat
Ban
Hpc vien Cdng nghe Saitama,
Nhat Ban
Khoa Cdng nghe thdng tin, trudng
Dai hpc cdng nghe, DHQGHN.
Khoa Toan Cd Tin hoc, trudng
DHKHTN, DHQGHN.
Khoa Cdng nghe thdng tin, trudng
Dai hpc cdng nghe, DHQGHN.
Khoa Cdng nghe thdng tin, trudng
Dai hpc cdng nghe, DHQGHN.
Khoa Cdng nghe thdng tin, trudng
Dai hpc cdng nghe, DHQGHN.
Khoa Cdng nghe thdng tin, trudng
Dai hpc cdng nghe, DHQGHN.
Khoa Cdng nghe thdng tin, trudng
Dai hpc cdng nghe, DHQGHN.

1


Tom t a t nhiJng ket qua chinh
cua de tai nghien ciJu khoa hoc
2.1

Ten de tai



NHIING KET QUA CHINH CUA D^ TAI NGHIEN ClfU KHOA H0C7

K i t qua phuc v u thu'c t l

Da hoan thanh bp chudng trinh cai dat thii nghiem thuat toan FMM tren may tfnh
MDGRAPEI-2. Cac kit qua nghien ciiu cua dl tai cho thiy, thuat toan do chung
tdi thilt kl va cai dat cd hieu nang cao va dp chfnh xac thoa man cac yeu ciu cua
nhilu ling dung trong linh vUc md phong dpng luc phan tii. Thuat toan cai dat nay
CO kha nang tfch hdp vdi mpt so iing dung vl MD da dUdc triln khai nhu NAMD.
May tfnh MDGRAPE-2 cd tai Ha Npi va kha nang sii dung may tfnh nay vao md
phong la kha thi.
2.3.3

K i t q u a d a o tao

• Da hudng din tot nghiep 03 sinh vien bao ve thang 6/2006 vl dl tai tfnh toan
hieu nang cao (xem cac bia luan van kem theo).
• Dang hudng din 01 hpc vien cao hpc vl dl tai tfnh toan hieu nang cao, du
kiln bao ve 12/2006.
2.3.4

K i t q u a n a n g c a o t i e m \\ic k h o a h o c

Nghien ciiu vl cac thuat toan, tlm hilu vl tfnh toan song song, tfnh toan hieu nang
cao, tfnh toan cum va tfnh toan thdng lUdng cao. Da hudng din sinh vien, td chiic
seminar va giang day vl ITnh vUc tfnh toan hieu nang cao, tfnh toan song song va
tfnh toan cum cho cac sinh vien tii nam 2004. Nam hpc 2006-2007 se giang day vl
tfnh toan song song cho hpc vien cao hpc cua khoa Cdng nghe thdng tin, trudng Dai
hpc Cdng nghe.

on a conventional computer connected to GRAPE. In order to take full advantage
of the dedicated hardware, we modified the FMM using Pseudoparticle Multipole
Method and Anderson's method. In the modified algorithm, multipole and local
expansions are expressed by distribution of a small number of imaginary particles
(pseudoparticles), and thus they can be evaluated by GRAPE. Results of numerical
experiments show that G R A P E accelerates the FMM by a factor of 3-60 depending
on the accuracy. Its performance exceeds that of Barnes-Hut treecode on GRAPE
at high accuracy (root-mean-square relative force error ~ 10~^), in the case of closeto-uniform distribution of particles.
K e y w o r d s : Molecular dynamics, numerical simulation, fast multipole method, tree
algorithm, Anderson's method, pseudoparticle multipole method, special-purpose
computer.


NOI D U N G CUA DE TAI
3.1

Dat v4n d l

Md phong dpng lue phan tii la mpt trong nhiing phUdng phap phd biin dUdc sii
dung trong vat ly/hoa hpc d l nghien ciiu cac he nhilu hat. Md phdng ddng luc phan
tii dUa tren dinh luat 2 Newton ve chuyen ddng: F = ma^ trong dd F la luc tac
dung tren hat; m, a tUdng iing la khdi lUdng va gia tdc cua hat. Tuf cac thdng tin
ve luc tac dung tren mdi hat, xac dinh gia tdc cua mdi hat trong he. Giai phudng
trinh chuyin dpng d l sinh ra mdt dudng cong md ta vi trf, van toc, gia toc cua cac
hat tai cac mdc thdi gian khac nhau. Tii dudng cong nay, trang thai tilp theo hay
trang thai trUdc ciia he se dUdc du bao.
Xet tren khfa eanh tfnh toan, viec thuc hien bai toan md phong ddng luc phan
tii cd t h i dUdc md ta qua cac budc sau:
1. Chpn vi trf ban d i u cua cac hat vdi dien tfch cho trude trong he.
2. Chpn mdt tap hdp van tdc khdi tao ciia cac hat. Cac van toc nay thudng dUdc

va
N

^(^"'^)-E7'

(3.2)

trong dd TV la s6 lUdng c^c hat, rJ va QJ tUdng iing la vi trf va dien tfch ciia hat j ,
r la khoang each giiia hat i va j dUdc dinh nghia bdi cdng thiic r — \ / | 7 \ — fj\'^.
D l dang t h i y ring d budc 4, thuat toan tfnh luc tUdng tac tmh dien ddn gian
n h i t chfnh la thuc hien tfnh luc tUdng tac giiia timg cap hat. Do dd, chiing ta se
phai thuc hien N{N — l ) / 2 phep tfnh luc dua vao phUdng trinh (3.1). Ndi each khac,
thuat toan ddn gian nay (sau day gpi t i t la thuat todn tinh lUc trUc tiep) cd dp phiic
tap tfnh toan 0{N'^).
Trong cae budc tfnh toan neu tren, budc tfnh luc tUdng tac tren mdi hat (budc
4) la nhiem vu nang n l n h i t xet vl mat tfnh toan. Bdi vay cin phai ap dung, cai
dat cac thuat toan cd dp phiic tap tfnh toan 0{N) hoac 0{N log N) va/hoac sieu
may tfnh, may tfnh song song hoac may tfnh chuyen dung tdc dp cao d l thUc hien
nhiem vu nay.
D l tai cua chiing tdi cd hai nhiem vu chfnh.
Nhiem vu thii n h i t la nghien ciiu, tim hilu cac vin d l cd sd ciia tfnh toan hieu
nang cao va iing dung ciia tfnh toan hieu nang cao vao bai toan md phdng ddng
luc phan tii. Trong p h i n cd sd tfnh toan hieu nang cao, chiing tdi nghien ciiu, tim
hieu cac vin d l cd lien quan tdi cac kiln triic, mdi trudng va cdng cu tfnh toan hieu
nang cao: Cum may tfnh P C Linux va mdt sd p h i n ciing chuyen dung cd tdc dp cao
chuyen danh cho bai toan md phong TV-body hoac md phong ddng luc phan tii.
Nhiem vu thii hai la nghien ciiu mdt iing dung cu t h i cua tfnh toan hieu nang
cao. Chiing tdi nghien ciiu va d l x u i t phUdng phap mdi d l tang tdc dp tfnh luc tinh
dien x i p xi tren may tfnh chuyen dung song song MDGRAPE-2, n h i m tang tdc bai
toan md phong dpng lue phan tii.

Nhiem vu nghien ciiu iing dung ciia dl tai rdi vao hudng thii ba. Chiing tdi nghien ciiu
phUdng phap cai dat thuat toan khai triln da cue nhanh (fast multipole algorithm)
tren may tfnh chuyen dung MDGRAPE-2 va d l x u i t phUdng phap mdi d l tang tdc
dp tfnh lUc x i p xi.
Sau day chiing tdi se lin ludt trinh bay cac phUdng phap tang tdc dp tfnh toan
luc trong md phong ddng lUc phan til theo ea ba hudng nhu da neu tren.

3.2.1

Cac t h u a t t o a n nhanh trong linh v\lc m o phong d o n g liic phan

tit

'

Trong cac bai toan md phdng dpng luc phan tii cd diln (tiic la khdng cd cac tfnh
toan lUdng tii), cdng viec tfnh luc tUdng tac giiia cac hat chilm nhilu thdi gian n h i t
- khoang 95% tdng sd thdi gian chay chUdng trmh. Thuat toan tfnh luc ddn gian
n h i t dUdc gpi la thuat toan true tilp cd dp phiic tap 0{N'^). Nhu vay khi TV ldn, thdi
gian tfnh lUc se r i t ldn va cac md phdng ddng luc phan tii vdi hang trieu hoac hang
chuc trieu hat se ton r i t nhilu thdi gian, tham chf ngay ca khi sii dung GRAPE.
Do dd da ed nhilu nghien ciiu d l x u i t cac thuat toan vdi dp phiic tap 0(TV) hoac
0{N log TV) d l tfnh x i p xi luc vdi dp chfnh xac dilu khien dudc.
Nam 1985, A. Appel lin d i u tien d l x u i t thuat toan phan cip d l tfnh luc vdi
dp phiic tap O(TVlogTV) [3]. Dua tren kit qua cua A. Appel, nam 1986 P. Hut va
J. Barnes da phat triln thuat toan tree vdi dp phiic tap O(AMogTV) [5]. Thuat toan
nay nhanh chdng dude sii dung rpng rai trong md phong vat ly thien van do tfnh
ddn gian va hieu qua ciia nd. Nam 1987, L. Greengard va V. Rokhlin da phat triln
thuat toan khai triln da cue nhanh (fast multipole algorithm - FMM) d l tfnh luc
x i p xi trong khdng gian 2 chilu [19]. Day la mdt thuat toan r i t phiic tap, dac biet la


Local expansion

Hinh 3.1: Y tudng chfnh ciia thuat toan tfnh luc FMM.
Chiing ta cin nhd lai la thuat toan tfnh lUc trUc tilp tfnh luc giiia timg cap hat,
ndi each khac thuat toan nay ed dp phiie tap tfnh toan O(TV^). Trong khi dd, y tudng
chfnh Clia thuat toan FMM la tfnh luc tUdng tac giua cac nhdm hat, sau dd tfnh x i p
xi lUc va t h i nang tren mdi hat bing each sii dung khai triln da cue va khai triln
Taylor. Cd 5 pha chfnh trong thuat toan FMM. Hinh 3.1 md ta y tudng cua FMM.
Trong dd, M2M, M2L va L2L la ba pha d i u tien cua thuat toan cd y nghla nhu sau.
M2M la biin ddi khai triln da euc-khai triln da cue, M2L la biin ddi khai triln da
cUc-khai trien Taylor va L2L la biin ddi khai trien Taylor-khai trien Taylor. Tiep
theo cac pha nay la pha tfnh luc tUdng tac "gin" va tfnh lUc tUdng tac "xa". Tfnh
luc tUdng tac g i n dUde thuc hien nhu thuat toan tfnh lUc true tilp. Luc tUdng tac
xa dudc thuc hien nhd viec liy dao ham rieng eua t h i nang dat dude tu* pha L2L.
Chiing ta ky hieu hai pha tfnh luc tUdng tac gin va xa tUdng iing la Fnear va FjarTrong 5 pha tfnh toan ndi tren, M2L, Fnear va Fjar la cac pha tfnh toan tdn thdi
gian n h i t .
Mac dil FMM dat dUdc dp phiic tap tfnh toan 0(N) nhung do tfnh chit plnic
tap ciia thuat toan n h i t la cac cdng thiic biin ddi trong cac pha M2M. M2L va L2L.


3. NOI DUNG CUA DE TAI

13

hi$u nang dat dUdc trong cai dat cua FMM chua cao. Thdi gian thue hien FMM chi
thuc su thap hdn thdi gian thuc hien thuat toan tfnh luc true tilp khi so hat TV kha
ldn, khoang 65535 trd len. Bdi vay, cd nhilu biin t h i ciia FMM n h i m lam giam su
phiic tap khi cai dat FMM de dat dUdc hieu nang eao hdn. Sau day la mdt sd biin
t h i diln hinh.


1=1 n=0

vdi r < a (khai triln trong). 0 day Wi la cac trpng sd va p la cac sd hang khdng bi
c i t khi rdi rac hda. Sau day chiing ta gpi p la c i p khai trien. Hinh 3.2 minh hpa y
tudng phUdng phap ciia Anderson.
3.2.2.3

T h u a t t o a n cua M a k i n o

Makino [39] d l x u i t phUdng phap khai tnen da cUc gid hat (Pseudo-Particle Multipole Method - gpi t i t la P^M^hoac phUdng phap gia hat). P-^M^ sii dung cac cdng
thiic la biin the ciia cac cdng thiic khai trien da cue. Ldi fch cua phudng phap nay
la tinh ddn gian va hdn nu:a, cac cdng thiic cua P^M^ cd the dupe thuc hien tren
may tfnh chuyen dung GRAPE.


'3.

NOI

DUNG

CUA

DE

15

TAI

2 thi viec nghich dao cdng thiic khai trien da
cue la r i t khd. Trong trudng hdp nay, Makino da dUa ra mdt each giai ddn gian.
Ong da ed dinh vi trf cua cac gia hat theo t-desgin c i u va chi giai phudng trinh d l
tim dien tfch eua cac gia hat. Cach tilp can nay d i n din viec giai mOt he phUdng
trinh tuyIn tfnh mac dii so lUdng gia hat cd tang len. Do dd xet mdt each tdng the,
each tilp can eiia Makino da lam cho bai toan ddn gian di kha nhilu.
Vdi each tilp can neu tren, Makino da dua ra dupe cdng thiic khai triln ngoai
cho phUdng phap gia hat nhu sau:
N


TAI

gdc giu'a fi vk vector vi trf Rj ciia gia hat j . Chiing minh dl din tdi cdng thiic (3.8)
cd trong tai Heu [39].
3.2.3

M a y t i n h chuyen dung song song G R A P E va iJng dung

HOST
COMPUTER

Positions,
charges
GRAPE
Forces

Hinh 3.4: Kiln triic cd ban ciia mdt he may tfnh GRAPE,

.ijsoju ) l ' l \

Hinh 3.5: May tfnh MDGRAPE-2 (PCI) cd toc dp cue dai tUdng dUdng 48GFlops
vdi 4 chip MDGRAPE-2 (mdi chip cd tdc dp cue dai tUdng dUdng 16GFlops).
May tfnh chuyen dung song song GRAPE dUdc chl tao tai Vien nghien ciiu vat
ly va hda hpc Nhat Ban (RIKEN [59]) dl tfnh luc tUdng tac hoac thi nang giira cac
hat. Day la mdt may tfnh ed kiln triic da xu" ly pipeline. GRAPE khdng phai la mpt
may tfnh cd thi hoat dpng dpc lap. Dl sii dung GRAPE chiing ta cin mdt he may
tfnh gdm cd mpt may tfnh thdng thudng, vf du IBM-PC (sau day gpi la ma.y chu)
va mdt may tfnh GRAPE. Chiing ta gpi t i t he ma\" tfnh nay la he GRAPE.



3. NQI DUNG CUA DE TAI

18

trong dd TV la s6 lUdng cac hat, fj va qj tUdng iing la vi trf va dien tich eua hat j , r^
la khoang each mem (danh cho cac ufng dung vat ly thien van) giiia hat i va j dUdc
dinh nghla bdi cong thiic Vs = %/'\fi — fj\'^ + e^ trong dd e la tham sd mim.
Dl tfnh luc /(fl), may chii cin gufi dii lieu cho GRAPE bao gom f,, fj, qj, e, va
A^. GRAPE tfnh luc f{fi) vdi mpi i sau dd giM kit qua tra lai may chii. Thi nang
(t>{fi) dUde tinh tUdng tu.
Doi vdi bai toan mo phdng dpng luc phan tuf, chiing ta khdng ed tham sd mim,
dilu dd cd nghia la € = 0. Khi dd cac phUdng trinh (3.9) va (3.10) trd thanh (3.1)
va (3.2).
Mdi may ehu cd thi lien kit vdi nhilu may GRAPE dl tang tdc dp tfnh luc
va cae he may GRAPE cd thi lien kit vdi nhau dl tao thanh mpt cum may tfnh
GRAPE vdi tdc dp tinh toan rit cao. Hinh 3.7, 3.8 va 3.9 minh hpa mdt cum may
tfnh GRAPE dUde dat ten la MDM [54] nhin tir mat trude, mat sau va ben trai.
Cum may tfnh nay cd tdc dp tUdng dUdng 78TFlops.

Hinh 3.7: Cum may tfnh GRAPE nhin tii mat trUdc [54]
Trong nam 2005, phien ban tilp theo cua MDGRAPE-2 la MDGRAPE-3 [61]
da dUdc che tao thii thanh cdng. Mdi chip MDGRAPE-3 ed tdc dp tUdng dUdng
165GFlops d tan so 250MHz va 200GFlops d tin so 300MHz (nhanh hdn MDGRAPE2 tii 10 din 12 lin). Thang 6/2006, cum may tfnh MDGRAPE-3 dimg dl md phdng
cac ling dung du doan ciu triic protein da dUdc hoan thanh va dUde dat ten la
Protein Explorer. Protein Explorer la may tfnh diu tien tren thi gidi dat tdc dp
tfnh toan vUdt ngudng 1 Petaflops vdi tdc dp 1.4PFlops. nhanh hdn may tfnh diing
dau trong Top500 [56] nam 2006 la IBM BlueGen khoang 3 lin. Tuy nhien Protein
Explorer la may tfnh chuyen dung nen khdng dUdc xip hang trong Top500.
Trong phin tilp theo chiing tdi trinh bay cac nghien ciiu va kit qua da cd vl
viee cai dat thuat toan nhanh tren cac phin ciing chuyen dung, tren cd sd dd thuc


3.

NOI

DUNG

CUA

DE

TAI

20

Hinh 3.9: Cum may tfnh GRAPE nhin tii ben trai [54].
tilp Fnear eiia FMM ma khdng tang tdc dude pha M2L va pha tfnh luc xa Fjar hai trong ba pha tfnh toan tdn thdi gian n h i t ciia FMM (xem p h i n 3.2.2.1).

3.3
3.3.1

Noi dung va k i t qua nghien ciJu
C a c k h o k h a n c 4 n giai q u y e t

Nhiem vu nghien ciiu ciia ehiing tdi la tim each tang toc dp tfnh luc tUdng tac tinh
dien cho bai toan md phdng dpng luc phan tii. Nhiem vu nay n i m trong hudng
nghien ciiu thii 3 nhu da neu trong p h i n 3.2.
Trong thuat toan FMM, cac pha M2L, Fnear va Fjar la tdn thdi gian n h i t . Do
dd cin phai sii dung GRAPE dl tfnh toan n h i m tang tdc cac pha nay. Tfnh toan
eho pha Fnear tren GRAPE la hiin nhien vi pha nay sii dung cdng thiic (3.1). Nhu

khai trien Taylor
cac gia h a t gay r a
Khai
Biin
cdng
Khai

Sail dd, ap dung giai phap tfnh luc mdi nhd vao cdng thiic (3.12). chiing tdi da
tang tdc thuat toan FMM va dat dUdc cac ket qua kha quan the hien trong cac thuc
nghiem tren p h i n ciing MDGRAPE-2.
Chiing tdi da thilt lap hai he thdng may tfnh GRAPE. He thong thii nhit (goi
t i t la he I) cd mdt card MDGRAPE-2 phien ban Compact PCI (64 pipelines, tdc


3. NQI DUNG CUA DE TAI

22

10000 E
-4—'

C/3

c
O
u

1000 =

s


1000 =

C
O

U

128K

256K

512K

IM

2M

Number of particles A^
Hinh 3.11: TUdng tU nhu hinh 3.10 nhung vdi he II.
dp cue dai tUdng dUdng 192GFlops) va mdt may chu Compaq DS20E (Alpha 21264,
667MHz). He thong thii hai (gpi t i t la he II) cd mpt card MDGRAPE-2 phien ban
PCI (16 pipelines, tdc dp cue dai tUdng dUdng 48GFlops) va mpt may chu Intel
Pentium 4 2.2GHz sii dung bo mach ehii Intel D850. Chiing tdi da thii nghiem thuat
toan FMM cai dat tren G R A P E vdi dp chfnh xac tfnh luc t h i p (cip khai trien p — I)
va cao (p == 5) vdi phan bd cac hat gin ddng n h i t trong khdi lap phudng. K i t qua
thuc nghiem dUde minh hpa tren cac hinh 3.10, 3.11, 3.12, 3.13 va bang 3.2. K i t qua
thuc nghiem tren he I cho tren cac hinh 3.10 va 3.12. K i t qua thue nghiem tren he
II eho tren cac hinh 3.11, 3.13 va bang 3.2.
Su: dung cdng thiic (3.12), ehiing tdi da tfnh toan dUde pha Ffar tren GRAPE.

" • * — '

CO

13
U

128K

256K

512K

IM

2M

4M

Number of particles A^
Hinh 3.12: So sanh thdi gian tfnh lUc cua thuat toan FMM va thuat toan tree tren
he I. Dudng cong cd cac hinh trdn thi hien hieu nang ciia FMM tren may tfnh
MDGRAPE-2. Dudng cong vdi cac hinh tam giac la hieu nang ciia thuat toan tree
tren MDGRAPE-2. Cae hinh trdn va tam giac td den la hieu nang tUdng iing vdi
dp ehfnh xae eao {p = 5), khdng td den iing vdi dp chfnh xac thip (p — 1).