Paralelisasi Transformasi Fourier Para Arsitektur General Purpose Graphic Processing Unit Untuk Klasifikasi Alat Musik Dengan Solo Instrumen

Seminar Nasional Pascasarjana XI – ITS, Surabaya 27 Juli 2011 ISBN No.

Paralelisasi Transformasi Fourier Para Arsitektur General Purpose Graphic Processing Unit Untuk Klasifikasi Alat Musik Dengan Solo Instrumen

Ridwan Rismanto 1*, Nanik Suciati 2, Wahyu Suadi 3 Institut Teknologi Sepuluh Nopember, Surabaya, Indonesia123* [email protected]

Abstrak Proses klasifikasi alat musik pada instrumen solo dilakukan melalui tiga tahap, yaitu proses pengambilan sampel, proses ekstraksi fitur yang terdiri dari Fast Fourier Transform (FFT) dan Analisa Spektrum serta proses klasifikasi menggunakan Backpropagation Neural Network. Penelitian ini melakukan sebuah pendekatan untuk meningkatkan kecepatan proses ekstraksi fitur pada FFT dengan memanfaatkan arsitektur General Purpose Graphic Processing Unit (GPGPU). Pemrosesan FFT dilakukan dengan memanfaatkan kemampuan komputasi paralel pada GPGPU yang diimplementasikan menggunakan NVIDIA CUDA sebagai framework untuk interaksi antara bahasa tingkat tinggi (C/C++) dengan Graphic Processing Unit (GPU). Paralelisasi FFT pada proses ekstraksi fitur terbukti dapat mempercepat eksekusi FFT sebanyak 25 kali lipat dibandingkan dengan FFT pada CPU jika tanpa memperhitungkan waktu transfer memory to memory (MMT) dan 4 kali jika memperhitungkan MMT. Sedangkan waktu proses ekstraksi fitur itu sendiri dapat dipercepat hingga 1,6 kali. Kata kunci : klasifikasi alat musik, backpropagation, komputasi paralel, GPGPU, CUDA, FFT

1. Pendahuluan Penggunaan komputer untuk melakukan proses klasifikasi pada data sinyal telah banyak dilakukan dan menjadi bahan penelitian di berbagai bidang, antara lain pengenalan suara (speech and speaker recognition), analisa seismic, klasifikasi jenis binatang dari suara dan analisa medis, dan klasifikasi alat musik pada instrumen solo [1]. Proses klasifikasi alat musik pada instrumen solo memanfaatkan algoritma backpropagation pada jaringan syaraf tiruan untuk mengenali jenis alat musik berdasarkan fitur-fitur yang telah diekstraksi dari sinyal input. Fitur-fitur yang digunakan untuk proses klasifikasi ini didapat dari analisa spektrum pada sinyal input yang telah melalui proses Fast Fourier Transform (FFT). Dari proses analisa spektrum ini akan didapat fitur-fitur yaitu spectral centroid, spectral kurtosis, spectral slope, spectral spread dan spectral rolloff [7], [8]. Pada penelitian sebelumnya [1], waktu yang dibutuhkan untuk proses pengenalan satu buah sinyal input dengan format Wave adalah 3 sampai 7 detik pada kondisi komputer dalam keadaan normal (tanpa beban pemrosesan tambahan). Sedangkan pada Madeley [2], untuk mengekstraksi fitur sinyal input sepanjang 12,5 detik dibutuhkan waktu sebesar 12 detik. Agar sistem ini dapat digunakan untuk proses klasifikasi secara real time, maka waktu untuk

mengekstraksi fitur harus lebih baik lagi [2]. Untuk mencapai tujuan itu maka pada penelitian ini dilakukan pendekatan komputasi paralel pada General Purpose Graphic Processing Unit (GPGPU) untuk memparalelisasikan proses FFT pada tahap ekstraksi fitur.

1.2 Komputasi paralel pada GPGPU Dengan arsitektur multi core, GPU dapat diprogram untuk melakukan proses komputasi secara paralel dengan arsitektur Single Instruction Multiple Data (SIMD) [6]. FFT sebagai salah satu tahap ekstraksi fitur dari data sinyal adalah salah satu jenis algoritma yang berhubungan dengan pemrosesan data yang berupa matriks dan vektor, sehingga dapat diimplementasikan dan mengambil keuntungan dari komputasi paralel dengan arsitektur SIMD pada GPGPU [3]. NVIDIA dengan CUDA (Compute Unified Device Architecture) telah memungkinkan pengembang memanfaatkan resource GPU dari NVIDIA untuk melakukan proses komputasi paralel. Dalam penelitian ini CUDA digunakan sebagai framework untuk memparalelkan proses FFT.

Seminar Nasional Pascasarjana XI – ITS, Surabaya 27 Juli 2011 ISBN No.

2. Metode yang diterapkan 2.1 Klasifikasi alat musik dengan instrumen solo Secara garis besar, proses pengklasifikasian dilakukan melalui tiga tahap yaitu : 1. Pengambilan sampel. 2. Ekstraksi fitur 3. Klasifikasi dengan Neural Network Sampel sinyal didapat dari file input berupa PCM Audio (.wav) yang dibagi menjadi beberapa frame. Tiap-tiap frame kemudian diekstraksi fitur-fiturnya untuk proses training dengan Neural Network. Data sinyal input terdiri dari 6 jenis alat musik yang dimainkan oleh musisi dan direkam dan diubah menjadi data digital dengan proses sampling. Data set serupa juga digunakan pada Madeley [2]. Data alat-alat musik tersebut antara lain : 1. Trombone 4. Trumpet 2. Tenor Saxophone 5. Clarinet 3. Alto Saxophone 6. Flute Fitur-fitur yang diambil pada proses ekstraksi fitur antara lain : spectral centroid, spectral kurtosis, spectral slope, spectral spread dan spectral rolloff. Fitur set ini sesuai dengan yang digunakan pada Madeley[2] dan Gunawan [1] serta Livshin dan Rodhet [7], [8]. Pada penelitian ini, tiap sinyal input dibagi menjadi 500 frame untuk data training dan 1000 frame untuk data testing. Frame-frame tersebut kemudian akan diacak untuk menghilangkan unsur-unsur musik seperti ritme dan nada. Tiap frame berdurasi 25 milidetik sehingga pada sampling rate 44,1kHz akan terdapat 211 elemen dan transform size. Penetapan konfigurasi ini berdasarkan Madeley [2], dimana panjang tiap frame telah memencukupi untuk proses ekstraksi fitur dan tidak melebihi panjang sinyal input keseluruhan (Gambar 1).

transformasi, {f0, f1, ... , fN-1} adalah input dari fungsi diskrit dan {F0, F1, ... , FN-1} adalah hasil dari transformasi Fourier. Asumsikan terdapat data sampel sebanyak N = 8, maka fungsi DFT dapat dituliskan sebagai berikut :

(2) Setelah disederhanakan, maka terbentuklah persamaan baru sebagai berikut :

(3) Tiap persamaan pada tanda dalam kurung adalah independen satu sama lainnya sehingga dapat dijalankan secara terpisah pada thread yang berbeda. Kode program untuk mengkalkulasikan persamaan ini dieksekusi oleh kernel CUDA sesuai dengan jumlah dimensi N. 2.2 Implementasi FFT secara paralel Paralelisasi dilakukan pada proses ekstraksi fitur, yaitu pada proses FFT seperti dapat dilihat pada Gambar 2.

Gambar 1. Pembagian sinyal input menjadi frame

2.1 Paralelisasi FFT Versi diskrit dari Transformasi Fourier (DFT) adalah sebagai berikut [5], [9] :

(1) Persamaan (1) adalah discrete Fourier transform –DFT. Disini N adalah dimensi

Gambar 2.Arsitektur sistem dan implementasi FFT secara paralel

Pada penelitian ini digunakan NVIDIA CUDA dengan versi 3.0 64bit yang dijalankan pada sistem operasi Windows 7 x64, dan klasifikasi alat musik pada Matlab versi 7.6.0 (R2008a). CUDA adalah arsitektur hardware dan software

Seminar Nasional Pascasarjana XI – ITS, Surabaya 27 Juli 2011 ISBN No.

untuk pemrograman dan manajemen komputasi pada GPU sebaga device untuk melakukan komputasi data paralel. CUDA menyediakan ekstensi pada bahasa C yang disebut dengan kernel pada pengembangan source code [10]. Proses FFT secara parallel dipisahkan dari program utama, kemudian subprogram ini dicompile dalam bentuk MEX file yang kemudian dapat dipanggil dari dalam Matlab. Beberapa tahap implementasi paralel FFT pada GPGPU : 1. Alokasi memori pada device (GPU). Sesuai hirarki memori pada CUDA, ruang memori pada device akan dialokasikan pada Global Memory. 2. Proses transfer data dari host ke device. Proses komputasi FFT dilakukan pada device, dimana device memiliki memori mandiri yang terpisah dari memori host. Semua data yang dibutuhkan oleh proses yang dieksekusi pada device hanya dapat diakses melalui memori device. 3. Proses komputasi FFT pada device. 4. Proses transfer data dari device ke host. Proses selanjutnya setelah proses FFT selesai adalah proses yang dilakukan pada host, oleh karena itu data yang telah selesai diolah pada memori device harus ditransfer balik ke memori host. 5. Dealokasi memori pada device. 2.3 Zero-padding dan data precission Dikarenakan perilaku dari thread, block, grid dari arsitektur GPGPU pada CUDA, maka dapat dikatakan bahwa FFT secara parallel pada GPGPU akan lebih optimal jika jumlah n-point DFT atau transform size—nya sebanyak 2n (powers of single factor) [3]. Oleh karena itu tiap data yang akan diproses pada FFT akan dipadding dengan 0.0f agar mendekati powers of single factor untuk memaksimalkan performa FFT. Implementasi FFT pada penelitian sebelumnya dilakukan pada bahasa C, dimana bilangan real dan imajiner dipisah kedalam dua vektor yang berbeda. Proses padding juga dilakukan untuk menyesuaikan tipe data complex pada Matlab agar sesuai dengan tipe data complex pada CUDA, yaitu menggabungkan bilangan real dan imajiner pada satu vektor. Spesifikasi GPU yang digunakan dalam penelitian ini hanya mendukung single precission floating point. Oleh karena itu, sebelum proses transfer data dari host ke device diperlukan konversi dari double precission ke single precission. Pseudo-code dari proses ini dapat dilihat pada Gambar 3.

Gambar 3. Pseudo code tahap padding dan konversi data pada proses klasifikasi

2.4 Evaluasi dan pengukuran Tahap evaluasi pada penelitian ini dilakukan dengan mencatat waktu pemrosesan FFT pada FFT secara sekuensial dan pada FFT secara parallel. Pencatatan waktu pemrosesan dilakukan dengan memanggil fungsi Matlab yaitu tic dan toc untuk FFT pada CPU, sedangkan pada GPU digunakan QueryPerformanceFrequency dan QueryPerformanceCounter. Fungsi ini akan dipanggil sebelum proses kalkulasi FFT dan sesudahnya; pada FFT sekuensial dan parallel. Khusus untuk FFT parallel akan dilakukan dua kali pengukuran waktu yaitu : 1. Pengukuran waktu sebelum dan sesudah proses FFT parallel tanpa mempertimbangkan MMT (Memory to Memory Transfer). 2. Pengukuran waktu sebelum dan sesudah proses FFT parallel dengan mempertimbangkan MMT. Kedua tahap diatas diperlukan karena proses transfer data dari host memory ke device memory sendiri akan memakan waktu, dimana pada proses ini maka host dan device akan menunggu hingga proses transfer selesai. Pengukuran dilakukan pada saat looping proses ekstraksi fitur pada tiap frame. Untuk mengumpulkan data pengukuran pada GPU, maka dibuatlah matriks berdimensi MxN dimana M adalah jumlah iterasi sesuai dengan jumlah frame, dan N adalah jumlah variabel waktu yang akan diukur. Tiap instrumen alat musik yang diproses akan memiliki matriks tersendiri. Lebih jelasnya dapat dilihat pada Gambar 4.

Seminar Nasional Pascasarjana XI – ITS, Surabaya 27 Juli 2011 ISBN No.

Gambar 5. Error-rate Neural Network untuk FFT pada CPU dan GPU

Gambar 4. Matriks untuk menyimpan data pengukuran waktu

Peningkatan kecepatan (SP) dari paralel FFT pada GPU dibandingkan dengan kecepatan FFT pada CPU didapatkan dari persamaan berikut [4] :

Tabel 1: Hasil klasifikasi data pada FFT CPU. Trombone Trombone Tenor Sax Alto Sax Trumpet Clarinet Flute

88.20% 0.80% 4.40% 6.40% 0.60% 5.40%

Tenor Sax Alto Sax 0.20% 0.20% 86.60% 3.60% 3.00% 77.20% 0.20% 0.20% 3.00% 2.40% 0.40% 8.80%

Trumpet 11.40% 0.80% 0.20% 91.80% 12.40% 22.00%

Clarinet

Flute

0.00% 0.00% 7.60% 0.60% 14.00% 1.20% 0.60% 0.80% 80.60% 1.00% 1.60% 61.80%

(4) Dimana TPC adalah waktu komputasi FFT pada CPU dan TGPU adalah waktu komputasi FFT pada GPU dan waktu yang dibutuhkan untuk transfer data antara host dan device.

3. Pembahasan Hasil Pengujian dilakukan pada hardware dengan spesfikasi : Intel Core 2 Duo U7300 @ 1,3 GHz, memori 4096 MB DDR3 dan GPU NVIDIA GeForce G210M. GPU ini memiliki 512 MB memori, 2 multiprosesor dan 16 core yang beroperasi pada clock rate 1,47 GHz. Konfigurasi frame yang digunakan untuk kedua platform yaitu CPU dan GPU adalah sama, yaitu 500 frame dengan durasi 25 milidetik tiap frame-nya, dengan jumlah elemen dan transform size adalah 211.

3.1 Hasil klasifikasi Dapat dilihat pada Gambar 5, bahwa errorrate pada Neural Network terjadi sedikit bias, yaitu 3111 pada FFT CPU dan 2216 pada FFT GPU. Perbedaan ini sangat dimungkinkan mengingat akurasi hasil komputasi antara CPU dan GPU sedikit berbeda dikarenakan data precission yang berbeda, yaitu double precission pada CPU dan single precission pada GPU. Perbedaan error-rate ini juga dimungkinkan karena hasil generate bobot pada Neural Network yang acak selain juga disebabkan karena pengambilan frame pada data sampel yang dilakukan secara acak.

Tabel 2: Hasil klasifikasi data pada FFT GPU. Trombone Tenor Sax Alto Sax Trumpet Trombone Tenor Sax Alto Sax Trumpet Clarinet Flute

91.40% 1.40% 0.80% 3.80% 0.00% 1.40%

2.20% 92.00% 6.60% 0.80% 1.20% 0.60%

0.00% 4.60% 88.40% 1.40% 1.80% 2.00%

3.20% 0.80% 1.00% 80.20% 0.00% 15.60%

Clarinet 0.00% 1.20% 0.00% 0.00% 95.80% 1.00%

Flute 3.20% 0.00% 3.20% 13.80% 1.20% 79.40%

Pada Tabel 1 dan Tabel 2 dapat dilihat perbedaan hasil training antara fitur yang diekstraksi menggunakan FFT pada CPU dan GPU, dimana akurasi hasil training ini sangat dipengaruhi oleh error-rate pada Neural Network.

3.2 Pengukuran waktu Untuk menentukan waktu hasil eksekusi FFT pada GPU didapatkan dari waktu eksekusi FFT ditambah waktu transfer memori dari host ke device dan sebaliknya, seperti pada persamaan berikut :

Tgpu  Th 2 d  TFFT  Td 2 h

(5)

Dimana Tgpu adalah total waktu eksekusi FFT pada GPU, Th2d adalah waktu transfer memori dari host ke device, TFFT adalah waktu eksekusi FFT pada GPU, Td2h adalah waktu transfer memori dari device ke host. Gambar 6 menunjukkan hasil pengukuran waktu eksekusi FFT pada GPU dan CPU pada proses ekstraksi fitur tiap data alat musik.

Seminar Nasional Pascasarjana XI – ITS, Surabaya 27 Juli 2011 ISBN No.

0.012

W aktu (detik)

0.01 0.008

MMT

0.006

GPU

0.004

CPU

0.002 0 Trombone Tenor Sax Alto Sax

Trumpet

Clarinet

Flute

Instrumen

Gambar 6. Waktu eksekusi FFT pada GPU dan CPU

Gambar 7 menunjukkan selisih waktu pada tiap iterasi. Dapat disimpulkan bahwa pada 500 iterasi, waktu eksekusi FFT stabil berada pada rata-rata 0,010063 detik pada CPU dan 0,002360 detik pada GPU. 0.012

Waktu (detik)

0.01 0.008 CPU

0.006

GPU + MMT

yaitu hanya berkisar diantara 1,5-1,6x. Hal ini disebabkan karena FFT hanya merupakan satu dari 6 tahap ekstraksi fitur lainnya. Waktu transfer memori dari host ke device dan sebaliknya pun ternyata cukup berpengaruh pada waktu total eksekusi FFT pada GPU yaitu sekitar 83% waktu total adalah memory to memory transfer pada data dengan jumlah elemen dan transform size 211. Pada percobaan dengan jumlah elemen dan transform size yang berbeda, waktu yang dibutuhkan untuk transfer memori dari host ke device dan eksekusi FFT hampir seimbang yaitu 0,000953 dan 0,001734 pada jumlah elemen 217 namun waktu untuk transfer memori dari device ke host tetap lebih besar daripada eksekusi FFT, yaitu 0,002277. Hal ini dikarenakan memori DDR3 pada G210M memiliki transfer rate untuk device ke host yang lebih rendah yaitu 1352,2 MBps dibandingkan dengan transfer rate untuk host ke device yaitu 1820,4 MBps. Gambar 8 menunjukkan grafik selisih waktu antara transfer data dan eksekusi FFT.

0.004 0.002 0 100

199

298

397

496

Waktu (detik)

1

Iterasi

Gambar 7. Waktu eksekusi FFT pada tiap iterasi

Tabel 3 menunjukkan peningkatan kecepatan antara CPU dengan GPU tanpa MMT dan GPU dengan MMT pada tiap data alat musik. Perbandingan peningkatan kecepatan total waktu ekstraksi fitur dapat dilihat pada Tabel 4.

0.0045 0.004 0.0035 0.003 0.0025 0.002 0.0015 0.001 0.0005 0

Host to Device FFT Device to Host

2 11

2 16

2 17

2 18

Jumlah Elemen

Gambar 8. Selisih waktu antara transfer memori dari host ke device (h2d)), device to host (d2h) dan eksekusi FFT

Tabel 3: Peningkatan kecepatan eksekusi FFT

Instrumen

1 2 3 4 5 6

Waktu (detik) 0.010042 0.010049 0.010081 0.010057 0.010096 0.010053

Peningkatan Kecepatan

GPU

CPU Waktu tanpa MMT (detik)

Waktu dengan MMT (detik)

0.000396 0.000393 0.000413 0.000395 0.000401 0.000385

0.002379 0.002354 0.002382 0.002349 0.002349 0.002345

Tanpa Dengan MMT MMT 25.4 25.6 24.4 25.5 25.2 26.1

4.2 4.3 4.2 4.3 4.3 4.3

Tabel 4: Peningkatan kecepatan total waktu ekstraksi fitur Instrumen CPU (detik) GPU (detik) 1 2 3 4 5 6

10.271058 9.833668 9.852464 9.890035 9.838902 9.777052

6.690781 6.142269 6.026518 6.111425 6.060907 5.997911

Peningkatan Kecepatan 1.5 1.6 1.6 1.6 1.6 1.6

Dari Tabel 3 dan Tabel 4 diatas dapat dilihat bahwa peningkatan kecepatan eksekusi FFT antara CPU dengan GPU adalah berkisar antara 25x (non MMT) dan 4x (dengan MMT). Akan tetapi peningkatan kecepatan pada proses ekstraksi fitur keseluruhan relatif lebih kecil

4. Kesimpulan Pemanfaatan arsitektur multi-core pada GPU dengan komputasi paralel untuk memparalelisasikan FFT dapat meningkatkan performa FFT pada proses ekstraksi fitur untuk klasifikasi alat musik. Algoritma FFT dapat dieksekusi dengan 25x lebih cepat jika tanpa mempertimbangkan waktu transfer memory to memory. Pada kondisi tertentu, yaitu pada jumlah elemen dan transform size lebih kurang dari 216, waktu yang dibutuhkan untuk transfer memori bahkan lebih besar daripada waktu yang dibutuhkan untuk mengeksekusi FFT itu sendiri. Untuk proses ekstraksi fitur itu sendiri dapat dipercepat hingga 1,6x dibandingkan dengan eksekusi FFT pada CPU. Peningkatan kecepatan ekstraksi fitur dapat lebih ditingkatkan lagi dengan memparalelisasi tahap-tahap ekstraksi fitur yang lainnya, serta menggunakan device GPU dengan kemampuan transfer memori yang lebih cepat dan clock rate yang lebih tinggi.

Seminar Nasional Pascasarjana XI – ITS, Surabaya 27 Juli 2011 ISBN No.

General Purpose Graphic Processing Unit dengan CUDA sebagai pendekatan untuk sistem komputasi paralel memungkinkan komputasi berskala besar (High Performance Computing – HPC) pada lingkungan pengguna komputer desktop. Dengan perkembangan device GPU yang lebih mutakhir serta kemampuan komputasi yang semakin besar, dikombinasikan dengan mapping algoritma yang tepat untuk arsitektur GPGPU dapat menghasilkan performa dengan lebih baik. 5. Pustaka [1] Gunawan, (2009). Penerapan Algoritma Backpropagation Untuk Klasifikasi Musik Dengan Solo Instrumen, Seminar Nasional Aplikasi Teknologi Informasi 2009 (SNATI 2009). [2] Madeley, Davyd, (2007). Automatic Computer Classification of Solo Musical Instruments, Creative Commons AttributionNoncommercial-No Derivative Works 2.5 Australia. [3] W. Gao, (2009). Real-time 2D parallel windowed Fourier transform for fringe pattern analysis using Graphic Processing Unit, Optics Express 23147, Vol. 17, No. 25. [4] Y. Maimaitijiang, (2009). Evaluation of Parallel FFT Implementations on GPU and Multi-core PCs for Magnetic Induction Tomography, IFMBE Proceedings 25/IV, pp. 1889-1892. [5] S. Chernenko, Fast Fourier transform –FFT, Librow, Digital signal processing (DSP) software development, Article 10 [Online], http://www.librow.com/articles/article-10 [Januari 2011]. [6] NVIDIA, “ CUDA Programming Guide Version 3.0”, NVIDIA Corporation, [Online]. http://developer.download.nvidia.com/comp ute/cuda/2_3/toolkit/docs/ [Desember 2010]. [7] A. A. Livshin and X. Rodet, (2004). Instrument recognition beyond separate notes - indexing continuous recordings, in Proc. Int. Computer Music Conf. [8] A. A. Livshin and X. Rodet, (2004)/ Musical instrument identification in continuous recordings, in Proc. of the 7th Int. Conference on Digital Effects, pp. 222 – 227. [9] J. W. Cooley, J. W. Tukey, (1965). An algorithm for the machine computation of the complex fourier series, Math. Computation, 19:2978211;301. [10] Sanders, Jason, (2011). CUDA by example : an introduction to general-purpose GPU programming / Jason Sanders, Edward Kandrot, Addison-Wesley, NVIDIA Corporation, ISBN 978-0-13-138768-3.