KOMPUTASI PARALEL EIGENVALUE DALAM PENYELESAIAN DIFUSI MULTIGROUP MENGGUNAKAN METODA HOUSEHOLDER DEFLASI DAN DIVIDE CONQUER

KOMPUTASI PARALEL EIGENVALUE DALAM PENYELESAIAN DIFUSI MULTIGROUP MENGGUNAKAN METODA HOUSEHOLDER DEFLASI DAN DIVIDE CONQUER Mike Susmikanti∗, Winter Dewayatna∗∗

ABSTRAK KOMPUTASI PARALEL EIGENVALUE DALAM PENYELESAIAN DIFUSI MULTIGROUP MENGGUNAKAN METODA HOUSEHOLDER DEFLASI DAN DIVIDE CONQUER. Dalam teknologi nuklir, pemecahan persamaan difusi secara umum memerlukan perhitungan eigenvalue (nilai karakteristik) dan eigenvektor (vektor karakteristik). Seringkali dijumpai nilai karakteristik yang akan dicari berada dalam matriks yang besar. Komputasi paralel merupakan alternatif penyelesaian untuk memecahkan persoalan operasi terhadap matriks yang besar dengan banyak nilai karakteristik. Komputasi paralel dirancang untuk efisiensi penggunaan beberapa komputer, perhitungan yang cukup besar dan kecepatan perhitungan. Terdapat metoda eigenvalue yang dapat diterapkan secara paralel untuk mencari nilai karakteristik dan vektor karakteristik antara lain Metoda Power Iterasi (Householder Deflasi) dan Metoda QR Iterasi (Divide Conquere). Dalam hal ini akan dilakukan perbandingan metoda eigenvalue householder deflasi dan divide conquer yang salah satu diharapkan dapat lebih efisien untuk membantu perhitungan lebih cepat. Penerapan algoritma paralel eigenvalue dilakukan terhadap penyelesaian persamaan difusi multigroup untuk mencari nilai karakteristik dan vektor karakteristik yang menyatakan k-effektivitas dan distribusi fluks. Adapun penerapannya diambil model multigroup dengan variasi banyak diskritisasi. Penerapan simulasi penyelesaian eigenvalue secara paralel dilakukan secara integrasi menggunakan program dengan bahasa C dan Message Passing Interface (MPI) dalam sistem komputer Multi-Core. Diperoleh hasil kinerja paralel dengan metoda eigenvalue householder deflasi dan divide conquer dalam penyelesaian persamaan difusi multigroup. Kata kunci : Eigenvalue, Paralel, Multigroup, Householer Deflasi, Divide Conquer

ABSTRACT EIGEN VALUE PARALLEL COMPUTING IN SOLVING DIFFUSION MULTIGROUP DIFFUSION USING HOUSEHOLDER DEFLATION AND DIVIDE CONQUER METHODS. In nuclear technology, solving the diffusion equation generally requires calculating eigenvalues (characteristic values) and eigenvector (characteristic vector). Often found characteristic value to be searched is in a large matrix. Parallel computing is an alternative solution to solve the large matrix operations with a lot of value characteristics. Parallel computing is designed for efficient use of multiple computers, the calculation is quite large and the speed of computations. There eigenvalues method that can be applied in parallel to find the characteristic values and characteristic vectors include Power Iteration Method (Householder deflation) and the method of QR iterations (Divide Conquered). In this case will do the comparison method of eigenvalues Householder divide conquer deflation and which one is expected to be more efficient to help faster computation. Implementation of parallel algorithms performed on completion eigenvalues multigroup diffusion equation to find the value characteristics and the characteristics of the states vector k-effectiveness and flux distribution. The application is taken multigroup models with many variations discretization. The application of parallel simulation completion ∗

Pusat Pengembangan Informatika Nuklir - BATAN Serpong, e-mail: [email protected] Pusat Teknoloi Bahan Bakar Nuklir – BATAN Serpong

∗∗

341

Lokakarya Komputasi dalam Sains dan Teknologi Nuklir, 10 Oktober 2012 (341-352)

eigenvalues integration is done using a program with C language and the Message Passing Interface (MPI) in the Multi-Core computer system. Parallel performance results obtained by the method of Householder deflation eigenvalues and divide conquer the completion of multigroup diffusion equations. Keywords: Eigenvalue, Parallel, Multigroup, Householder Deflation, Divide Conquer

PENDAHULUAN Perhitungan kritikalitas dan distribusi fluks neutron pada analisis fisis difusi desain multigrup memerlukan hasil perhitungan nilai eigen dan vektor eigen. Terdapat beberapa metode penyelesaian sistem nilai eigen secara lokal maupun global. Penyelesaian nilai eigen bertujuan untuk memperoleh nilai eigen yang terbesar atau dominan ataupun terkecil, ataupun dari yang terbesar sampai yang terkecil serta sebaliknya. Perhitungan eigen value dalam penyelesaian multigroup kemungkinan akan memakan waktu lama dan termasuk dalam perhitungan secara global. Dalam tulisan ini ingin dilakukan analisis kinerja penerapan beberapa metoda eigen value secara paralel agar efisien. Dalam hal ini akan dilakukan perbandingan metoda nilai eigen Householder Deflasi dan Divide Conquer yang diharapkan dapat membantu perhitungan lebih cepat. Metoda divide conquer merupakan metoda QR yang dimodifikasi secara paralel. Sedangkan metoda householder deflasi merupakan metoda deflasi yang diperluas secara paralel. Adapun penerapannya untuk kedua metode ini diambil penyelesaian model multigroup dengan variasi diskritisasi. Penerapan simulasi penyelesaian eigen value secara paralel dilakukan secara integrasi menggunakan program dengan bahasa C dan Message Passing Interface (MPI) dalam sistem komputer Multicore.

METODOLOGI Penyusunan algoritma paralel eigenvalues (nilai eigen) dan eigen vector (vektor eigen) adalah mengaproksimasi nilai eigen mutlak terbesar, kedua, ketiga, keempat, dan seterusnya serta vektor eigen matriks. Dengan menggabungkan metode pangkat langsung (direct power) dan metode deflasi, nilai eigen yang berbeda dari matriks bilangan real dapat diaproksimasi menggunakan metoda Householder Deflasi. Diperlukan pemecahan eigen secara global untuk nilai eigen dengan ukuran matriks yang besar, dalam hal ini digunakan prosedur QR yang dimodifikasi untuk penyelesaian paralel yaitu algoritma Divide Conquer [1, 2]. Perbandingan kinerja algoritma paralel eigenvalue diterapkan pada penyelesaian sistem difusi multigroup pada komputer Quard Core, terhadap masing-masing node yang dinyatakan dalam satuan waktu menggunakan konsep MPI (Message Passing Interface). Algoritma Paralel Householder Deflasi 342

Komputasi Paralel Eigenvalue dalam Penyelesaian Difusi Multigroup ... (Mike Susmikanti, Winter Dewayatna)

Transformasi householder sangat berguna dalam deflasi matriks. Mereduksi ukuran n x n menjadi (n-1) x (n-1), sering digunakan dalam pemecahan nilai eigen lokal khususnya dalam menggabungkan dengan metoda tanpa iterasi ataupun metoda dengan iterasi. Tujuannya adalah menghitung subdominan nilai eigen sesudah menghitung maksimum dan minimum nilai eigen dengan metoda pangkat atau metoda pangkat kebalikan. Misalkan telah dihitung maksimum nilai eigen λi dan vektor eigen vi diperoleh matriks transformasi householder H pada persamaan (1) [1], α   

H vi =  0  = α ei

(1)

:   0  

Adapun algoritma paralel Householder deflasi dapat diuraikan sebagai berikut, 1. Hitung maksimum nilai eigen λ1 dan vektor eigen v1 yang berhubungan, menggunakan metoda pangkat ataupun metoda pangkat kebalikan, 2. Tentukan matriks House Holder H menggunakan vektor eigen v1 3. Bentuk Matriks G = HAHT 4. Ekstrak nilai eigen pada G11 5. Definisikan An-1 ∞ G2:n,2:n 6. Ulangi proses pada matriks A yang baru didefinisikan, An-1 Prosedur deflasi dapat diterapkan lebih efisien untuk perhitungan nilai eigen dalam ukuran matriks yang tidak cukup besar [2]. Prosedur deflasi dapat dinyatakan seperti pada gambar 1, Proses 0 X0 X0 0 1 Proses 1

X0 2

X00

X0 1

X1 0

X1 1

X2 0

X2 1

X03

X02 X1 2

X1 3

X2 2

X2 3

X2 X2 X24 X25 X04 X0 X0 X0 X2 2 3 5 2 3 4 Kirim data Terima Data Gambar 1. Proses Paralel Deflasi

X2 5

X1 X11 X12 0 Proses 2 X2 0

X2 1

X03

X0 4

X13 X14

X0 5 X15

Algoritma Paralel Divide Conquer

343


Algoritma paralel divide conquer mencakup langkah berikut [1], 1. Reduksi A, Bentuk matrik tridiagonal penuh yang simetri M T 2. Matriks T dibagi kedalam Dua matriks tridiagonal simetri T1 dan T2, sehingga

 T1 0   + bkZZT 0 T 2  

T = 

3. Diagonalisasi T1 & T2 menggunakan pendekatan matriks orthogonal Q1 & Q2, D1 dan D2 matrik diagonal T1 = Q1D1Q1T dan T2 = Q2D2Q2T dst

 Q1

4. Bentuk ζ =  0

0   z Q 2 

ξ i2 =0 a) Nilai eigen diberikan dalam persamaan 1 + bk ∑ i =1 d i − λ n

ξ i2 b) Tentukan λ demikian sehingga f( λ ) = 0, dimana f( λ ) = 1 + bk ∑ i =1 d i − λ n

c) Tentukan vektor eigen vi dari matriks M dengan

 Q1 0   yi dimana yi = (D- λ I)-1 ξ 0 Q 2  

vi = 

d) Ulangi proses rekursif (memanggil dirinya sendiri) untuk T1 dan T2 Algoritma paralel Divide Conquer dapat diuraikan pada gambar 2,

344


P0 50 25

25

P1

P2 25

25

12

P3

12

13

P4

P5

12 6

P6

13 6

6

13

12 7

6

13 6

6

7

Gambar 2. Proses Paralel Divide Conquer

Penyelesaian Numerik Persamaan Difusi Multigroup Pertama dilakukan pembentukan matriks koefisien difusi multigroup M. Berikutnya melakukan penyelesaian perhitungan distribusi fluks seperti yang dinyatakan dalam persamaan (2) [3, 4],

Mφ = S

(2)

M : Matriks koefisien difusi multigroup, φ : distribusi fluks, S : Sumber fisi. Struktur matriks multigroup dinyatakan dalam gambar 3,

 m11   m 21      m51     

m12 m 22 m32

m14 m 23 m33 m 43

m 25 m34 m 44

m36 m 45 . .

m62 mn 4

     m 47   m58    m n −1n −1 . m n −1 n  m nn −1 m nn 

=

 S11     S11  S   11   S11   .     .     S11  S   11 

Gambar 3. Struktur matriks hasil perhitungan koefisien difusi multigroup

345


Persamaan difusi multigroup dinyatakan dalam persamaan (3) [3, 4].

1 x1 S k

− ∇D1∇φ1 + ∑ R φ1 = 1

1 − ∇D2∇φ2 + ∑R φ2 = x21S + ∑S φ1 2 12 k − ∇D2 ∇φ 2 + ∑R φ 2 = 2

1 x 21 S + ∑S φ1 + ∑S φ 2 12 23 k

− ∇D 2 ∇φ 2 + ∑ R φ 2 = 2

(3)

1 x 21 S + ∑ S φ1 + ... + ∑ S φ G −1 12 G −1 , G k

Misalkan tidak ada upscattering dan sumber fisi didefinisikan dalam persamaan (4), G

S ( r ) ≡ ∑ν g ∑ f φ g ( r )

(4)

g

g =1

Kerapatan spasial sumber fisi dimisalkan sama dalam persamaan difusi tiap group. Secara umum untuk membentuk matriks koefisien difusi multigroup dinyatakan dalam persamaan (5) [3, 4], i→ g

(−∑ s

i

Dig,i −1 (∆ i,i −k )

+ 2

) (−

Dig,i − k (∆

Dig,i +1 (∆ i,i −k )

i ,i − k

+ 2

)2

) (−

D ig,i −1 (∆

i ,i −1

Dig,i +k

)2

) (−∑ s

g i

+

Dig,i − k (∆

Dig,i +1 Dig,i +k − − ) ( ) ( ) (∆ i,i −k )2 (∆ i,i −k )2 (∆ i,i −1)2

i ,i − k

)2

+ (5)

Strategi iterasi untuk penyelesaian nilai eigen pada struktur matriks difusi multigroup untuk perhitungan k-effectivitas (keff) dan distribusi fluks φ sebagai berikut [3, 4] (1) Pertama memberikan tebakan untuk kelipatan eigen value k(0), vektor sumber (0) S ( 0) dan distribusi suhu atau fluks awal φ (2) Sebelumnya membuat struktur matriks multigroup M, kemudian melakukan perhitungan M φ (n+1) =

1 k (n)

S ( n ) , untuk iterasi fluks φ (n+1) berikutnya. Penyelesaian

ini termasuk sejumlah bagian tahapan berikut,

346


(2-1) Satu penyelesaian karakteristik persamaan difusi yang homogen didalamnya untuk tiap energi group g adalah

Ag φ gn +1 =

1 k

(n)

S ( n ) + R g −1φ g( n−)1 ≡ ϕ g n

Dengan memecahkan pertama untuk group energi yang tertinggi g = 1 ( n + `1)

( R0 ≡ 0, φ 0

≡ 0 ) dan menggunakan φ1( n+1) untuk menyelesaikan φ2( n+1) , dan

seterusnya, untuk menyelesaikan group-group dibawahnya. (2-2) Menyelesaikan homogen dalam difusi, demikian sehingga iterasi didalamnya ke iterasi diluarnya menjadi konvergen. (3) Memperoleh, M φ ( n +1) =

1

k

(n)

Fφ ( n ) ,

Dan kemudian menggunakan M φ (n+1) =

Untuk menentukan k ( n +1) = k ( n )

1

k

( n +1)

Fφ ( n+1) ,

Fφ ( n+1} Fφ ( n+1} Fφ ( n} Fφ ( n}

(4) Mengulang (1)-(3) sampai k(n+1) dan φ (n+1) konvergen

HASIL DAN PEMBAHASAN Algoritma paralel eigen value dengan metoda Househoulder Deflasi dan Divide Conquer akan dibandingkan dalam penyelesaian sistem difusi multigroup pada komputer Quard Core. Proses perhitungan k-eff dan distribusi fluks dilakukan menggunakan konsep MPI (Message Passing Interface) dalam sistem Open Source LINUX [5]. Input Geometri material menggunakan 2 dimensi dengan arah aksial 40 satuan panjang serta arah radial 25 satuan panjang. Geometri dibagi dalam 8 partisi dan 5 partisi. Model multigroup dibagi dalam empat group energi, sehingga membentuk matriks dengan order 160 x 160. Input sifat material mengandung sigma absorbsi (penampang lintang), konstanta difusi dan produktivitas per fisi. Tebakan awal untuk nilai distribusi fluks adalah 100.0, Batas konvergenitas adalah 0.0000001 dan k-effective sebesar 1.00. Pada tahap awal, dilakukan perhitungan semua unsur pada matriks koefisien M, mengikuti

347


persamaan (4) tersebut diatas. Bentuk matriks merupakan matriks diagonal dengan order matriks 160 x 160. Data konstanta target empat group untuk satu dari posisi irradiasi dengan Uranium 6.1866 g ( x 106 b ) digunakan dinyatakan pada Tabel 1 [6], Tabel 1. Data Konstanta Target empat group Uranium 6.1866 g ( x 10-6 b ) untuk satu posisi IP2 Group 1 2 3 4

Dg 1481 976 1278 1079

∑ gabs 1820 391 1467 1982

ν ∑g 58 84 993 18677

∑ gscat 3312 226 222

Catatan: IP2 adalah posisi iradiasi Sigma absorbbtion ( ∑ gabs ) untuk group-1

ke group-4 adalah 0.001820,

0.000391, 0.001467 dan 0.019822. Sigma scatering ( ∑ gscat ) untuk group-1 ke group2, group-2 ke group-3 dan group-3 ke group-4 masing-masing adalah 0.003312, 0.000226 dan 0.000222. Koefisien difusi (Dg) untuk tiap group masing-masing adalah 0.001481, 0.000976, 0.001278 dan 0.001079. Penampang lintang (ν ∑ g ) untuk tiap group masing-masing adalah 0.000058, 0.000084, 0.000993 dan 0.018677. Nilai kritikalitas yang dinyatakan dengan k-eff, menggunakan metoda householder deflasi merupakan nilai eigen yang diperoleh sebesar 1.019101. sedangkan menggunakan metoda divide conquer diperoleh nilai eigen k-eff adalah 1.018210. Nilai distribusi fluks yang dinyatakan pada Tabel 2, dalam psi(1) sampai psi(160) merupakan vektor eigen. Perbandingan waktu komputasi paralel perhitungan kritikalitas dan distribusi fluks diantara penggunaan metoda eigen householder deflasi dan divide conquer dalam sistem komputer Quard-Core terhadap matriks ukuran 160 x 160 dinyatakan pada Tabel 3.

348


Tabel 2. Nilai Kritikalitas dan Distribusi Fluks Dengan Metoda Eigen Value Householder Deflasi dan Divide Conquer Fluks (Node) psi(1) psi(2) psi(3) psi(4) psi(5) psi(6) psi(7) psi(8) psi(9) : : psi(159) psi(160)

Metoda Eigen Value Householder deflasi k-eff = 1,008091 0,037196 0,038009 0,038032 0,039033 0,039891 0,039892 0,039893, 0,039894 0,039894 : : 0,841042 0,841042

Divide Conquer k-eff = 1,008210 0,026980 0,023771 0,020649 0,037055 0,083747 0,098991 0,388308 0,611554 0,685873 : : 0,931767 0,955175

Tabel 3. Perbandingan Waktu Komputasi metode eigen householder deflasi dan divide conquer Node 1 2 3 4

Waktu Paralel Householder Deflasi (detik.) 8,957 5,475 3,431 1,337

Waktu Paralel Divide conquer (detik.) 9,695 6,851 5,455 3,326

Grafik kinerja komputasi paralel perhitungan kritikalitas dan distribusi fluks dengan metoda householder deflasi dan divide conquer dinyatakan pada gambar 3,

349


Gambar 3. Kinerja komputasi paralel perhitungan kritikalitas

KESIMPULAN Dilakukan analisis kinerja penerapan metoda eigenvalue secara paralel yang diterapkan pada model multigroup untuk perhitungan kritikalitas dan distribusi fluks neutron. Diperoleh kinerja masing-masing penyelesaian eigenvalue menggunakan metoda householder deflasi dan divide conquer. Algoritma eigenvalue householder deflasi dan divide conquer dapat diaplikasikan dengan ukuran matriks koefisien difusi yang cukup besar dalam waktu singkat dengan sistim paralel. Diperoleh waktu komputasi dengan metode householder deflasi lebih cepat sedikit dibandingkan divide conquere. Penerapan simulasi penyelesaian eigenvalue secara paralel dilakukan secara integrasi menggunakan program C dan Message Passing Interface (MPI) dalam sistem komputer Multi-Core.

DAFTAR PUSTAKA 1. KARNIADAKIS, GEORGE E.;KIRBY LL, ROBERT M, “Parallel Scientific Computing in C++ and MPI”, Cambridge University Press, First Published, (2003). 2. T.H. MICHAEL, “Parallel Numeric Algorithm”. www.cse.illinois.edu/courses/ cs554/notes/12_Eigenvalues (2011). 3. DUDERSTADT, J. J.,HAMILTON, L. J., (1976), “Nuclear Reactor Analysis”, John Wiley & Sons, Inc., (1976). 4. J.R. LAMARSH, A.J. BARATTA, “Introduction to Nuclear Enginerring”, Prentice-hall, ISBN 0-201-82498 (2001).

350


5. GRAMMATIKAKIS, MILTOS D.; FRANK HSU, D. AND KRAETZL, MIRO, “Parallel System Interconnections and Communications”, CRC Press LLC, New York, 2001. 6. W. DEWAYATNA, “Irradiation Safety Analysis”, FPM Target in Reactor Terace RSG-GAS, (1995).

DISKUSI IRWAN ARY DHARMAWAN Berapa jumlah “n” dalam grafik speed up? MIKE SUSMIKANTI Dengan metoda Divide Conquer jumlah n dalam grafik speed up maksimal yang dapat disimulasikan yaitu matrik 160 x 160, karena metode Divide Conquer mengikuti konsep pohon biner.

DAFTAR RIWAYAT HIDUP 1. 2. 3. 4. 5. 6. 7.

Nama : Dra. Mike Susmikanti Instansi / Unit Kerja : PPIN-BATAN Pekerjaan / Jabatan : Fungsional Peneliti Riwayat Pendidikan : S1 Matematika Univ. Indonesia Pengalaman Kerja : Bidang Komputasi, PPIN, BATAN (1980-sekarang) Organisasi Profesional :Publikasi Ilmiah yang pernah disajikan/diterbitkan : (dalam tahun terakhir) • Identifikasi Sifat Material Nuklir Terhadap Hasil Simulasi Molekuler Dinamik dengan Jaringan Syaraf Tiruan Menggunakan Metoda Backpropagation SEMANTIK 2011. Universitas Dianuswantoro, Semarang, 2011. • Artificial Neural Network Modeling to Evaluate the Phenomena of Stainless Steels and Coolant Material in High Temperature, SEIE, Universitas Negeri Malang 2011. • Pemodelan Jaringan Syaraf Tiruan untuk Mengevaluasi dan Memprediksi Sifat Bahan Pendingin Reaktor, SNATI 2011, Yogyakarta, UII 2011. • Performance of Public Cluster Molecular Dynamics For Protein Analysis, ICOWOBAS, Universitas Airlangga, Surabaya 2011.

351


• •

•

352

Analisis Kinerja Penyelesaian Persamaan Difusi 2-D Menggunakan Modifikasi LU Dekomposisi dalam Sistem Komputer Multi-Core, SRITI, AKAKOM, Yogyakarta 2011. Molecular Dynamics Simulation for Study the Effect of Molybdenum in Stainless Steel on the Corrosion Resistance by Lead-Bismuth M. Susmikanti1), D. Andiwijayakusuma1), Ghofir1), A. Maulana2) ICANSE 2011 Kerjasama PPIN BATAN ITB Denpasar Bali November 2011. Optimasi pendugaan Paramater Dalam Analisis Stress dan Strain Terhadap Material Menggunakan Algoritma Genetika, Mike Susmikann, SNATI 2012 UII – Yogyakarta, 16-17 Juni 2012.

KOMPUTASI PARALEL EIGENVALUE DALAM PENYELESAIAN DIFUSI MULTIGROUP MENGGUNAKAN METODA HOUSEHOLDER DEFLASI DAN DIVIDE CONQUER

Recommend Documents