LAPORAN TAHUNAN PENELITIAN HIBAH BERSAING

LAPORAN TAHUNAN PENELITIAN HIBAH BERSAING

METODE EFISIENSI AREA INTEGRATED CIRCUIT (IC) DENGAN REDUKSI WORDLENGTHS UNTUK MENINGKATKAN KINERJA PERANGKAT KOMPUTASI ELEKTRONIK

Tahun ke 1 dari rencana 3 tahun

Zulfikar, S.T., M.Sc.

NIDN. 0020077507

Hubbul Walidainy, S.T., M.T.

NIDN. 0026087301

UNIVERSITAS SYIAH KUALA NOVEMBER 2014

LAPORAN TAHUNAN PENELITIAN HIBAH BERSAING

METODE EFISIENSI AREA INTEGRATED CIRCUIT (IC) DENGAN REDUKSI WORDLENGTHS UNTUK MENINGKATKAN KINERJA PERANGKAT KOMPUTASI ELEKTRONIK

Tahun ke 1 dari rencana 3 tahun

Zulfikar, S.T., M.Sc.

NIDN. 0020077507

Hubbul Walidainy, S.T., M.T.

NIDN. 0026087301

UNIVERSITAS SYIAH KUALA NOVEMBER 2014

RINGKASAN Perkembangan teknologi integrated circuit (IC) yang kian pesat dan kebutuhan akan bertambahnya informasi yang dapat disajikan dalam sebuah perangkat komputasi elektronik dewasa ini telah mendorong para peneliti untuk menemukan cara menghemat area yang terpakai oleh rangkaian komputasi dalam sebuah IC. Penelitian ini bertujuan menerapkan metode baru dengan cara reduksi wordlengths untuk menghemat area dari suatu IC guna meningkatkan kinerja dari perangkat komputasi elektronik. Dengan berkurangnya wordlengths, maka area yang dibutuhkan dalam sebuah IC untuk rangkaian komputasi akan semakin kecil. Pada penelitian ini, untuk tahun pertama dipilih rangkaian pembangkit bilangan random jenis berdasarkan algoritma Linear Congruential Generator (LCG) sebagai target untuk diefisiensikan. Rangkaian tersebut dirancang dengan menggunakan blok-blok dasar operasi aritmatika seperti penambah, pengurang dan pengali. Tahapan awal dari teknik reduksi wordlength yang diajukan telah berhasil diaplikasikan pada rangkaian tersebut. Rangkaian pembangkitan bilangan random 8 bit dan teknik perancangannya disajikan secara detail. Hasil simulasi behavior, synthesis, simulasi waktu dan perbandingan penerapan terhadapa beberapa chip FPGA dari Xilinx dipaparkan pada bab 5. Hasil awal dari penelitian ini telah dipublikasikan pada jurnal internasional IJECCE edisi Juli-Agustus 2014. Dan hasil lanjutan telah diterima pada seminar internasional ICCEI 2015. Hasil lanjutan ini lebih efisien dari rancangan sebelumnya. Dengan demikian penelitian ini telah mencapai tujuan keseluruhan.

Keywords: Integrated Circuit, Penghematan Area, Reduksi Wordlengths, VHDL, FPGA, Linear Congruential Generator

i

PRAKATA Penelitian ini bermaksud untuk menghemat area suatu IC dari perangkat komputasi elektronik dengan harapan kinerja perangkat tersebut semakin meningkat. Penelitian ini memakai menerapkan teknik reduksi/ pengurangan wordlength dari rangkaian pembangkitan bilangan random. Diharapakan area yang dibutuhkan dalam sebuah IC untuk rangkaian bilangan random semakin kecil. Adapun Metode dan tahapan penelitian yang digunakan adalah sebagai berikut: 



Studi Literatur, mempelajari beberapa rangkaian aritmatika kompleks yang akan dijadikan sasaran penelitian. Implementasi Software, pemodelan rangkaian-rangkaian target ke dalam hardware melalui program VHDL akan dilakukan. Beberapa program simulasi telah dipilih, antara



lain Xilinx ISE dan Quartus Altera. Perbandingan, bersama dengan rancangan metode baru, akan disimulasikan juga rangkaian-rangkaian aritmatika konvensional yang telah dipakai saat ini. Jika area dari rangkaian dengan metode baru tidak lebih hemat, maka akan dilakukan pemrograman



ulang. Perbandingan akan dilakukan melalui software dari Xilinx dan Altera. Pengembangan Lanjut, setelah diimplementasikan ke FPGA, akan dikaji kemungkinan penghematan lebih lanjut terhadap rangkaian yang dipilih. Jika memungkinkan akan dilakukan dan dimulai pemrograman ulang. Penulis mengucapkan terima kasih yang sebesar-besarnya kepada pihak-pihak yang telah

membantu terlaksananya penelitian ini.

ii

DAFTAR ISI RINGKASAN

i

PRAKATA

ii

DAFTAR ISI

iii

DAFTAR TABEL

v

DAFTAR GAMBAR

vi

DAFTAR LAMPIRAN

vii

BAB I. PENDAHULUAN

1

BAB II. STUDI PUSTAKA

3

2.1 VHDL

3

2.2 Paket Library IEEE untuk Konversi Bilangan

3

2.3 Linear Congruential Generator

4

BAB III. TUJUAN DAN MANFAAT PENELITIAN

5

3.1 Tujuan Penelitian

5

3.2 Mamfaat Penelitian

5

BAB IV. METODE PENELITIAN

6

BAB V. HASIL YANG DICAPAI

8

5.1 Desain Rangkaian LCG

8

5.1.1 Rangkaian Umum dari LCG

8

5.1.2 Reduksi Wordlengths

9

5.2 Implementasi dan Analisa

10

5.2.1 Simulasi Behavior

10

5.2.2 Hasil Synthesis

11

5.2.3 Simulasi Waktu

12

5.2.4 Perbandingan

13

5.3 Desain LCG Efisien

14

5.3.1 Rangkaian

14

5.3.2 Perbandingan

15

BAB VI. RENCANA TAHAPAN BERIKUTNYA

18

BAB VII. KESIMPULAN DAN SARAN

19 iii

DAFTAR PUSTAKA

20

iv

DAFTAR TABEL Tabel I. Daftar perintah konversi bilangan antara integer, signed dan unsigned

4

Tabel II. Daftar perintah konversi bilangan antara standard logic vector, signed dan unsigned

4

Tabel III. Perbandingan frekuensi maksimum diantara chip-chip Xilinx

13

Tabel IV. Perbandingan area yang dibutuhkan diantara chip-chip Xilinx

14

Tabel V. Perbandingan area yang diperlukan diantara chip-chip Xilinx

15

Tabel VI. Perbandingan maksimum frekuensi diantara chip-chip Xilinx

16

Tabel VII. Perhitungan area berdasarkan hasil synthesis untuk modulus 8 bit (desain sebelumnya)

16

Tabel VIII. Perhitungan area berdasarkan hasil synthesis untuk modulus 8 bit (desain baru)

16

Tabel IX. Perhitungan area berdasarkan hasil synthesis untuk modulus 16 bit (desain sebelumnya)

17

Tabel X. Perhitungan area berdasarkan hasil synthesis untuk modulus 16 bit (desain baru) Tabel XI. Perhitungan area berdasarkan hasil synthesis untuk modulus 32 bit (desain sebelumnya) Tabel XII. Perhitungan area berdasarkan hasil synthesis untuk modulus 31 bit (desain baru)

v

17 17 17

DAFTAR GAMBAR Gambar 4.1 Fishbone diagram metode penelitian

6

Gambar 5.1 Blok diagram operasi LCG

8

Gambar 5.2 Rangkaian umum dari LCG

9

Gambar 5.3 Rangkaian sinyal pengendali untuk rangkaian LCG

9

Gambar 5.4 Reduksi wordlength pada blok pengali

10

Gambar 5.5 Reduksi wordlength pada blok penambah

10

Gambar 5.6 Hasil dari simulasi behavior dengan m=255, seed=7, a=3, c=1

11

Gambar 5.7 Hasil dari simulasi behavior dengan m =216-1, seed=7, a=3, c=1

11

Gambar 5.8 Hasil dari simulasi behavior dengan m = 231-1, seed=7, a=3, c=1

11

Gambar 5.9 Pegamatan lebih dekat dari simulasi waktu

12

Gambar 5.10 Desain rangkaian yang di ajukan untuk efisiensi area lebih lanjut (n=8)

14

Gambar 5.11 Desain wordlengths pada blok pengali

15

Gambar 5.12 Desain wordlengths pada blok penambah

15

vi

DAFTAR LAMPIRAN LAMPIRAN I: BIODATA KETUA TIM PENELITI

21

LAMPIRAN II: BIODATA ANGGOTA TIM PENELITI

24

LAMPIRAN III: Publikasi Artikel pada Jurnal Internasional

26

LAMPIRAN IV: Publikasi Artikel pada Seminar Internasional

32

vii

BAB 1 PENDAHULUAN

Sekarang ini banyak rangkaian elektronika diimplementasikan kedalam sebuah Integrated Circuit (IC). Kecendrungan untuk masa yang akan datang semakin banyak rangkaian elektronika diimplementasikan kedalam IC, hal ini dikarenakan faktor biaya produksi yang murah jika diproduksi dalam jumlah yang banyak. Seiring dengan itu, tuntutan akan semakin besarnya rangkaian elektronika ntuk suatu aplikasi tertentu mendorong para peneliti untuk menemukan cara yang lebih efisien untuk merealisasikan suatu rangkaian elektronika kedalam sebuah IC. Salah satu faktor efisiensi yang sangat penting dalam merealisasikan suatu rangkaian elektronika kedalam sebuah IC adalah area (besarnya ukuran IC). Sebagai contoh, sebuah telepon genggam produksi sekarang ini mempunyai kemampuan berlipat ganda jika dibandingkan dengan telepon genggam produksi 10 tahun yang lalu dengan ukuran yang sama tentunya, hal ini salah satunya dikarenakan efisiensi area pada IC. Kapasitas IC di dalam telepon genggam produksi sekarang ini jauh lebih besar walaupun dengan ukuran (dimensi) yang sama dengan sebelumnya. Hal ini bergantung dari teknologi terbaru pembuatan rangkaian terintegrasi. Penghematan area dari suatu IC lebih lanjut juga bisa dicapai dengan menyederhanakan rangkaian komputasi elektronik. Rangkaian tersebut digunakan untuk perhitungan-perhitungan seperti penjumlahan, pengurangan, pembagian, perkalian dan lain-lain. Penghematan rangkaian ini akan lebih terasa jika diterapakan pada perhitungan lebih dari satu tingkatan (komplek). Metode yang akan digunakan adalah reduksi wordlengths (lebar kata). Dengan diterapkannya metode ini, diharapkan area yang terpakai didalam suatu IC menjadi lebih kecil. Sehingga suatu IC dengan ukuran yang sama bisa menampung lebih banyak rangkaian untuk aplikasi lain. Pada penelitian ini, untuk tahun pertama dipilih rangkaian pembangkit bilangan random sebagai target untuk diefisiensikan. Bilangan random telah digunakan dalam kehidupan sehari-hari sejak jaman dahulu kala. Sekarang ini, sebuah mainan anak-anak yang harganya murah pun sudah terdapat rangkaian bilangan random didalamnya. Sebagai contoh, sebuah telepon mainan akan berbunyi berbedabeda jika tombol yang sama di tekan lebih dari satu kali.

1

Beberapa teori bilangan random telah diperkenalkan sejak bebrapa dasawarsa terakhir. Sebuah teori tentang Linear Congruential Generator (LCG) telah diperkenalkan oleh Lehmer (D H Lehmer.1954). Teori ini merupakan salah satu teori tertua dan sangat banyak dipakai dengan prinsip Pseudorandom Number Generator (PNG) (Wikipedia.org. Linear....2014). Park dan Miller memberikan suatu kontribusi yang sangat bagus untuk LCG (S K Park dkk. 1988). Berkat kontribusi ini, teknik pembangkitan bilangan random ini digunakan pada MATLAB (Numerical Computing.2008). Banyak pembangkit bilangan random lain yang telah diperkenalkan dan digunakan dalam berbagai aplikasi. Beberapa teknik tersebut adalah Blum Shub, Wichmann-Hill, Complementary multiply with carry, Inversive congruential generator, ISAAC (cipher), Lagged Fibonacci generator, Linear feedback shift register, Maximal periodic reciprocals, Mersenne twister, Multiply-with-carry, Naor-Reingold Pseudorandom Function, RC4 PRGA, Well Equidistributed Long-period Linear, dan Xorshift (wikipedia.org. List of ...2014, N Harald. 1992, A Note of .... 2009, Wolfram Mathematica. 2008). Hardware (perangkat keras) untuk pembangkitan bilanagan random tersedia sebagaimana tersedianya algoritmanya. Hardware tersebut telah digunakan sejak tahun 2008. Produk hardware keluaran LETech adalah yang tercepat diantara semua hardware untuk pembangkitan bilangan random. Produk ini telah dikembangkan sejak tahun 2008 (www.letech.jpn.com. 2014, wikipedia.org. Comparison.... 2014). Penelitian untuk menemukan algoritma yang sesuai dalam hal pembangkitan bilangan random merupakan bidang yang eksis sampai sekarang. Banyak peneliti menggunakan Field Programmable Logic Array (FPGA) untuk pengetesan dan pengujian ide-ide baru. Beberapa diantaranya telah direalisasikan kedalam hardware dan dijual di pasaran (wikipedia.org. List of ...2014, wikipedia.org. Comparison.... 2014). Pada awalnya, algoritma dari LCG digabungkan dengan teknik Monte Carlo telah digunakan untuk membangkitkan bilangan random non uniform menggunakan MATLAB (Zulfikar. 2009). Setelah itu, kami mengembangkan rangkaian pembangkit bilanagn random dan mengimplementasikan kedalan FPGA (Zulfikar. 2014). Pada publikasi tersebut faktor increment c diabaikan (c=0). Pada tahap awal penelitian ini telah berhasil dikembangkan teknik pembangkitan bilangan random tanpa mengabaikan faktor increment c (Zulfikar dan H Walidainy. 2014). 2

BAB 2 TINJAUAN PUSTAKA

2.1 VHDL Very High Speed Integrated Circuit Hardware Description Language (VHDL) adalah suatu bahasa pemrograman untuk menjelaskan penggunaan hardware (perangkat keras) pada perangkat electronic design automation (EDA). Bahasa ini digunakan untuk menjelaskan sistem pensinyalan digital dan pensinyalan gabungan seperti IC dan Field Programmable Gate Arrays (FPGA) (M Anis dkk. 2009, P P Chu. 2006, S Hauck dkk. 2007, S Kilts. 2007). Secara umum, program VHDL digunakan untuk menuliskan modul-modul berbasis teks yang menjelaskan sebuah rangkaian logika. Kemudian diperlukan suatu simulasi untuk menguji rancangan logika tersebut. Untuk hal ini, dibutuhkan file tambahan yang disebut dengan testbench. Beberapa vendor FPGA menyediakan fitur testbench yang lebih mudah digunakan yang disajikan dalam bentuk Graphical User Interface (GUI) (P P Chu. 2006, S Hauck dkk. 2007). Xilinx ISE, Altera Quartus, Synopsys Symplify dan Menthor Graphic adalah sebagian software (perangkat lunak) yang sering digunakan untuk FPGA. Paket software ini hanya memerlukan program VHDL dan testbench nya saja. 2.2 Paket Library IEEE untuk Konversi Bilangan Setiap program VHDL harus mempunyai paling tidak satu library. Library tersebut merupakan library dasar yang berisikan informasi dari semua gerbang-gerbang dasar yang dibutuhkan untuk pengimplementasian FPGA. Untuk rangkaian yang besar dan melibatkan perhitungan aritmatika yang komplek, akan lebih baik dan mudah jika semua operasi perhitungan dilakukan dalam format bilangan integer. Namun hal ini membutuhkan perhatian khusus dalam memprogram koneksi-koneksi antar blok rangkaian dasar. Jika dilakukan dengan tepat, penghematan area yang optimal akan didapatkan. Banyak vendor pihak ketiga menyediakan paket/ library untuk mempermudah perhitungan aritmatika. IEEE juga menyediakan library tersebut yang diberi nama Numeric_std 1076.3 (IEEE.NUMERIC_STD.ALL). Paket library tersebut menyediakan dua cara mengkonversi bilangan antara integer dan standard logic vector baik melalui format signed atau unsigned. Untuk tujuan perhitungan aritmatika tertentu, operasi-operasi perhitungan juga dapat dilakukan hanya dalam format signed 3

atau unsigned saja. Tabel I menunjukkan perintah-perintah pengkonversian bilangan-bilangan antara format integer, signed dan unsigned. Sementara itu, tabel II menampilkan daftar perintah untuk mengkonversi antara format unsigned, signed dan standard logic vector. Dengan menggabungkan perintah-perintah yang ada pada kedua table tersebut, kita bisa melakukan konversi langsung antara format standard logic vector dengan integer (www.doulos.com. 2013). Table I. Daftar perintah konversi bilangan antara integer, signed dan unsigned Dari/ ke Integer Signed Unsigned

Integer to_integer( ) to_integer( )

Signed to_signed( ,length) signed( )

Unsigned to_unsigned( ,length) unsigned( ) -

Tabel II. Daftar perintah konversi bilangan antara standard logic vector, signed dan unsigned Dari/ ke Standard logic vector Signed Unsigned

2.3

Standard logic vector std_logic_vector ( ) std_logic_vector ( )

Signed signed( ) unsigned( )

Unsigned unsigned( ) unsigned( ) -

Linear Congruential Generator Terdapat sebuah metode yang sangat popular dan paling sering digunakan untuk

membangkitkan bilangan random yang disebut LCG. Ide dari metode ini telah diperkenalkan oleh Lehmer sesuai dengan rumus sekuensial berikut ini (D H Lehmer.1954): X n1  (aX n  c) mod m

(1)

Dimana m adalah modulus, a adalah pengali, dan c adalah increment (penambah). Parameterparameter a, c dan m harus dipilih dengan sangat hati-hati untuk menghindari pengulangan dari bilangan yang sama sebelum m (N Harald. 1992, A Note of .... 2009, Wolfram Mathematica. 2008). Saran yang diberikan oleh Park dan Miller dengan memilih c=0 akan memberikan hasil yang bagus (S K Park dkk. 1988). Modulus m harus merupakan bilangan primer yang besar, pengali a adalah integer dengan batasan 2, 3, ..., m-1. Panjang siklus dari LCG tidak akan melebihi modulus m, tetapi dapat dimaksimalkan dengan menggunakan tiga kondisi berikut ini (A Note of .... 2009, D E Knuth. 2002): 





c adalah bilangan prima yang berhubungan dengan modulus m. Pengali a–1 adalah faktor kali dari setiap pembagi modulus m. Pengali a–1 adalah faktor kali dari empat ketika modulus m adalah faktor kali dari empat. 4

BAB 3 TUJUAN DAN MANFAAT PENELITIAN

3.1 Tujuan Penelitian Penelitian ini secara umum bertujuan untuk menghemat area dari suatu IC dari perangkat komputasi elektronik. Diharapkan kinerja perangkat komputasi elektronik tersebut semakin meningkat. Penelitian ini akan menggunakan teknik reduksi wordlengths dari rangkaian komputasi aritmatika. Dengan berkurangnya wordlengths, maka area yang dibutuhkan dalam sebuah IC untuk fungsi yang sama akan semakin kecil. Pada tahap awal, penelitian ini bertujuan khusus untuk: 1. Melakukan analisis statistik terhadap semua wordlengths yang digunakan dari rangkaian komputasi elektronik. 2. Mereduksi wordlengths dari rangkaian komputasi elektronik tersebut. 3. Membandingkan area dari rangkaian komputasi elektronik yang telah direduksi wordlengths nya dengan area dari rangkaian komputasi elektronik konvensional. Pada tahap lanjutan, penelitian ini bertujuan khusus untuk: 1. Melakukan analisis statistik secara mendalam terhadap semua sinyal-sinyal (data) yang mungkin digunakan untuk masukan ke rangkaian komputasi elektronik. 2. Mereduksi wordlengths lebih lanjut, sehingga dicapai hasil yang lebih optimal dari sebelumnya. 3. Mendokumentasikan dan mendiseminasikan hasil penelitian tersebut kepada pihak terkait baik di tingkat nasional maupun internasional. 3.2 Mamfaat Penelitian Suatu perangkat elektronik akan lebih bernilai jual jika dilengkapi dengan berbagai macam aplikasi atau fungsi tambahan. Hal ini senada dengan perkembangan teknologi perangkat elektronik selama ini, dimana makin banyak (beragam) aplikasi tambahan yang dimasukkan kedalam suatu perangkat elektronik dengan ukuran atau dimensi yang sama dengan sebelumnya. IC merupakan komponen utama tempat aplikasi-aplikasi disematkan. Jadi kebutuhan untuk menghemat area IC menjadi keharusan. Dengan penghematan area IC maka akan ada ruang untuk menambahkan rangkaian untuk aplikasi yang lain.

5

BAB 4 METODE PENELITIAN

Penulis telah menginisialisasi penelitian ini dengan mempublikasikan konsep dasar reduksi wordlengths dari rangkaian aritmatika. Hasil implementasi konsep desain kedalam FPGA menunjukkan bahwa area yang dibutuhkan lebih sedikit dibandingkan dengan metode konvensional (Zulfikar. 2012). Metode penelitian yang digunakan untuk penghematan area dari IC dengan metode reduksi wordlengths tertuang dalam fishbone diagram (diagram tulang ikan) seperti terlihat pada Gambar 4.1.

Gambar 4.1 Fishbone diagram metode penelitian Berikut adalah penjelasan metode penelitian yang tersusun seperti pada gambar 4.1: 

Studi Literatur, pada tahap awal,

penulis akan mendalami beberapa rangkaian

aritmatika komplek yang akan dijadikan sasaran penelitian. Setiap tahun akan dipilih 1 (satu) buah rangkaian. Studi statistik terhadap aplikasi rangkaian tersebut akan dilakukan secara mendalam. Mendalami program bahasa pemrograman hardware VHDL dan teknologi FPGA (Xilinx, Altera) terbaru untuk menjalankan metode yang direncanakan 

terhadap rangkaian yang telah ditentukan. Implementasi Software, pemodelan rangkaian-rangkaian target kedalam hardware memlalui program VHDL akan dilakukan. Beberapa program simulasi telah dipilih, 6

antara lain: Modelsim, Xilinx ISE dan Quartus Altera. Konsep konversi bilangan sangat 

membantu dalam penerapan. Perbandingan, bersama dengan rancangan metode baru, akan disimulasikan juga rangkaian-rangkaian aritmatika konvensional yang telah dipakai saat ini. Jika area dari rangkaian dengan metode baru tidak lebih hemat, maka akan dilakukan pemrograman



ulang. Perbandingan akan dilakukan melalui software dari Xilinx dan Altera. Implementasi Hardware, urutan proses untuk mengimplementasikan rangkaian yang dirancang kedalam hardware FPGA adalah: Translation, Mapping, Place & Route,



Program Generation, dan Downloading. Pengujian Hardware, untuk pengujian ini akan dilakukan beberapa tahapan seperti: pengujian visual, pengujian dengan alat ukur dan pengujian akan dilakukan untuk



berbagai macam kemungkinan. Pengembangan Lanjut, setelah diimplementasikan ke FPGA, akan dikaji kemungkinan penghematan lebih lanjut terhadap rangkaian yang dipilih. Jika memungkinkan akan dilakukan dan dimulai pemrograman ulang. Metode penelitian yang telah dijelaskan diatas adalah untuk satu tahapan proses dari suatu

rangkaian komputasi elektronik. Hal ini ditargetkan akan selesai selama 1 (satu) tahun. Untuk tahun ke 2 dan ke 3, proses seperti pada fishbone diagram tersebut akan diulang dari awal. Pada tahun ke 2 dan ke 3, implementasi dan pengujian juga akan dilakukan pada software Quartus Altera. Hal ini dilakukan untuk menjustifikasi metode yang telah dirancang dengan berbagai kemungkinan yang tidak didapatkan pada implementasi rangkaian di tahun pertama. Jumlah publikasi setiap tahunnya adalah 2 (dua). Publikasi pertama sekitar bulan Agustus – September, publikasi kedua pada akhir tahun. Publikasi pertama baru bisa dilakukan setelah tahapan Pengujian Hardware. Setelah dilakukan pengembangan untuk penghematan lanjutan, diharapkan hasil penelitian akan lebih baik, sehingga publikasi kedua akan layak untuk dimuat pada jurnal baik ditingkat nasional maupun internasional. Indikator capaian penelitian ini berdasarkan perbandingan dengan metode konvensional. Jika area yang diperlukan lebih sedikit dari area yang dibutuhkan oleh metode konvensional, maka penelitian ini dinilai berhasil. Indikator capaian kedua adalah diterimanya hasil penelitian ini pada seminar dan jurnal ilmiah.

7

BAB 5 HASIL DAN PEMBAHASAN

Penelitian ini dimulai pada awal tahun 2014. Saat ini target dari penelitian ini telah tercapai 100%. Tujuan tahap awal dari penelitian ini telah tercapai. Hal ini diperkuat dengan diterima dan telah dipublikasi hasil awal penelitian ini pada jurnal internasional. Kemudian, Tujuan tahap lanjutan dari penelitian ini juga telah berhasil dicapai dengan baik. Hasil capaian ini telah ditulis dalam bentuk artikel ilmiah dan telah diterima pada seminar internasional. Berikut akan dipaparkan beberapa rancangan desain rangkaian bilangan random dan hasil-hasil dari eksekusi terhadap desain tersebut kedalam FPGA. 5.1 Desain Rangkaian LCG 5.1.1. Rangkaian Umum dari LCG Gambar 5.1 menunjukkan menunjukkan blok diagram umum dari LCG (seed diabaikan). Rangkaian tersebut membutuhkan blok-blok pengali, penambah, pembanding dan pengurang. Blok pengali digunakan untuk mengalikan nilai acak sebelumnya (X) dengan a. Kemudian hasilnya ditambahkan dengan increment c. Langkah selanjutnya membandingkan dengan modulus m. Hasilnya dianggap sebagai bilangan random jika lebih kecil dengan m. Sebaliknya, jika hasilnya lebih besar dari m, maka dikurangi dengan m. Bilangan hasil pengurangan ini kemudian dianggap sebagai bilangan random.

Gambar 5.1 Blok diagram operasi LCG Blok diagram pada gambar 5.1 melibatkan operasi aritmatik seperti perkalian, penambahan, pengurangan, dan pembandingan. Untuk menyederhanakan proses, rangakain dirancang dengan menggunakan teknik reduksi wordlength seperti yang telah di sarankan sebelumnya (Zulfikar. 2012). Dengan demikian, blok pengurang dan pembanding dapat dihilangkan, rangkaian modifikasi seperti terlihat pada gambar 5.2.

8

Gambar 5.2 Rangkaian umum dari LCG Rangkaian yang dirancang tersebut terdiri-dari sebuah multiplexer (pemilih), sebuah pengali, sebuah penambah, sebuah buffer (penyimpan sementara) yang bisa di clear kan isinya, dan tiga buah buffer yang dikendalikan oleh sinyal kontrol enable. Port-port masukan seed, A dan C digunakan untuk memasukkan nilai inisial awal, mengalikan dan menambahkan ke rangkaian. Sementara port O digunakan untuk menarik keluar bilangan-bilangan random yang dihasilkan. Rangkaian dikendalikan oleh dua buah sinyal kontrol yaitu enable dan reset. Saat kondisi awal, sinyal reset haru menjadi HIGH (enable = LOW) untuk meng clear kan nilai yang tersimpan sebelumnya di dalam buffer B4. Sinyal enable menentukan kapan operasi harus dimulai. Nilai inisial awal (seed), increment dan pengali harus sudah ada pada port-port masukan sebelum sinyal enable menjadi HIGH (reset = LOW). Kemudian, setiap kali clock menjadi HIGH, sebuah bilangan random dihasilkan. Gambar 5.3 menunjukkan konfigurasi rangkaian dari sinyal-sinyal kontrol tersebut.

Gambar 5.3 Rangkaian sinyal pengendali untuk rangkaian LCG 5.1.2 Reduksi Wordlength Rangkain pada gambar 5.2 dapat digunakan untuk wordlength berapa saja. Pengurangan wordlength harus direncanakan dengan sebaik mungkin untuk menghindari hasil dari operasi yang tidak diinginkan. Sebagai contoh, rangkaian LCG didesain untuk digunakan pada nilai maksimum wordlength adalah 8 bit, konfigurasi net (jalur) dari blok pengali dan blok penambah ditunjukkan pada gambar 5.4 dan gambar 5.5. 9

Gambar 5.4 Reduksi wordlength pada blok pengali

Gambar 5.5 Reduksi wordlength pada blok penambah Berdasarkan aturan aritmatika dan untuk kepentingan penghematam area, hasil perkalian dari B4 (8 bit) dan B1 (8 bit) akan membutuhkan 15 bit untuk menampung nilai hasil perkalian. Pada rancangan, kami mengabaikan (tidak menghubungkan) tujuh net tertinggi dari X(8) sampai X(14) seperti terlihat pada gambar 5.4. Hal yang sama juga dapat dilakukan terhadap net dari penambah. Pada kasus penambah, hanya satu net (M(8)) yang diabaikan, hal ini seperti terlihat pada gambar 5.5. 5.2

Implementasi dan Analisa Desain rangkaian LCG telah diimplementasikan kedalam FPGA. Hasil dari simulasi

behavior dan waktu serta synthesis disajikan. Analisa dan perbandingan telah dilakukan. Rangkain pada gambar 5.2 telah diimplementasikan kedalam program FPGA. Simulasi behavior telah dijalankan menggunakan Xilinx ISE design suite. Beberapa data penting hasil dari synthesis di tunjukkan. Perbandingan area dan kecepatan telah dilakukan terhadap beberapa chip Xilinx. 5.2.1 Simulasi Behavior Gambar 5.6 menunjukkan hasil dari simulasi behavior dengan modulus m=255, seed=7, pengali a=3 dan increment c=1. Dapat dilihat bahwa bilangan-bilangan yang dihasilkan adalah acak dari 7 sampai dengan 255.

10

Gambar 5.6 Hasil dari simulasi behavior dengan m=255, seed=7, a=3, c=1 Gambar 5.7 dan gambar 5.8 menunjukkan hasil simulasi behavoir dengan modulus m=216–1 dan m=231–1 secara berurutan. Dapat dilihat bahwa semua bilangan yang dihasilkan tidak ada yang melebihi modulus.

Gambar 5.7 Hasil dari simulasi behavior dengan m =216-1, seed=7, a=3, c=1

Gambar 5.8 Hasil dari simulasi behavior dengan m = 231-1, seed=7, a=3, c=1 5.2.2. Hasil Synthesis Berikut ini adalah beberapa data penting hasil synthesis dari rangkaian yang dirancang dengan menggunakan modulus m=255 terhadap chip Xilinx Virtex 7: HDL Synthesis Report Macro Statistics # Multipliers :1 8x8-bit multiplier :1 # Adders/Subtractors :1 16-bit adder :1 # Registers :4 8-bit register :4 # Multiplexers :1 8-bit 2-to-1 multiplexer :1 ----------------------------------------------------------------------------------------------------Slice Logic Utilization: Number of Slice Registers: 16 out of 437600 0% Number of Slice LUTs: 10 out of 218800 0%

11

Number used as Logic: 10 out of 218800 0% Slice Logic Distribution: Number of LUT Flip Flop pairs used: 17 Number with an unused Flip Flop: 1 out of 17 5% Number with an unused LUT: 7 out of 17 41% Number of fully used LUT-FF pairs: 9 out of 17 52% Number of unique control sets: 2 -----------------------------------------------------------------------------------------------------Minimum period: 3.710ns (Maximum Frequency: 269.513MHz) Minimum input arrival time before clock: 2.023ns Maximum output required time after clock: 0.575ns Maximum combinational path delay: No path found

Dari laporan hasil synthesis dapat dilihat bahwa rangkaian yang dirancang membutuhkan sebuah pengali 8x8 bit, sebuah penambah 16 bit, empat buah register 8 bit, dan sebuah multiplekser 2-ke-1 8 bit. Dalam area, dapat dilihat dari kebutuhan slice yaitu 16 slice register dan 10 slice LUT. Penyebaran dari slice logic dari total 19 adalah 9 untuk penggunaan penuh pasangan LUT-FF, 7 untuk LUT yang tidak digunakan dan 1 untuk flip-flop yang tidak digunakan. Rangkaian juga membutuhkan 2 set kontrol khusus. Kecepatan dari rangkaian yang dirancang adalah maksimum 270 MHz ketika diimplementasikan kedalam chip Virtex 7. Waktu antar kedatangan minimum sebelum clock adalah 2,023 ns. Maksudnya adalah data harus sudah berada pada input masukan sebelum waktu tersebut tercapai. Waktu maksimum yang dibutuhkan untuk menampilkan data pada output adalah 0,5775 ns setelah clock. 5.2.3 Simulasi Waktu Gambar 5.9 menunjukkan close look dari simulasi waktu. Disana ada beberapa glitch ketika bilangan berubah dari 67 ke 202. Ini terjadi karena waktu dari pinggir clock ke pad-pad output bervariasi. Variasinya berkisar antara 9,399 ns samapai 9,818 ns.

Gambar 5.9 Pegamatan lebih dekat dari simulasi waktu 12

5.2.4 Perbandingan Empat buah chip Xilinx telah dipilih untuk perbandingan kecepatan dan area dari rangkaian yang dirancang. Tabel III memperlihatkan perbandingan dari kecepatan maksimum untuk rangkaian yang diimplementasikan dengan modulus m=255 (8bit), m=216-1 (16bit) dan m=231-1 (31 bit) terhadap chip Virtex 7, Spartan 6, Kintex 7 dan Zynq. Tabel III. Perbandingan frekuensi maksimum diantara chip-chip Xilinx Jenis Chip Virtex 7 Spartan 6 Kintex 7 Zynq

Frekuensi Maksimum (MHz) 8 bit 270 154 309 272

16 bit 270 154 270 272

31 bit 139 73 158 140

Untuk modulus m=255, chip yang paling cepat adalah Kintex 7 dan chip yang paling lambat adalah Spartan 6. Akan tetapi, untuk modulus m=216-1, chip yang paling cepat adalah Zynq. Secara umum, Kintex 7 adalah chip yang cepat dan Spartan 6 adalah yang lambat. Tabel IV memperlihatkan perbandingan area dari keempat chip yang disebutkan sebelumnya. Dapat dilihat bahwa semua chip membutuhkan area yang sama untuk wordlength yang sama tentunya. Untuk modulus m=255, chip-chip membutuhkan 16 slice dan 10 LUT. Area yang dibutuhkan menjadi dua kali lipat ketika diimplementasikan dengan modulus 16 bit. Sementara ketika modulus diganti dengan 31 bit, area yang dibutukan semua chip meningkat sekitar 3 kali lipat. Tabel IV. Perbandingan area yang dibutuhkan diantara chip-chip Xilinx Area yang dibutuhkan Jenis Chip

8 bit

16 bit

31 bit

Slices

LUTs

Slices

LUTs

Slices

LUTs

Virtex 7

16

10

32

18

92

63

Spartan 6

16

10

32

18

92

63

Kintex 7

16

10

32

18

92

63

Zynq

16

10

32

18

92

63

13

5.3

Desain LCG Efisien Gambar 5.2 memperlihatkan rancangan LCG sebelumnya (Zulfikar dkk. 2014).

Rangkaian tersebut menggunakan wordlengths yang sama yaitu n untuk perhubungan antar blokblok. Rangkaian tersebut terdiri dari (asumsi modulus = 2n):     

Sebuah n x n-bit multiplier Sebuah n-bit 2-to-1 multiplexer Sebuah n-bit adder 3 x n enable buffers (B1, B2, B3) n buffers (B4) Untuk aplikasi tertentu, rangkaian tersebut dapat ditingkatkan (diefisienkan) lebih lanjut.

Dengan menggunakan blok-blok rangkaian yang sama, Kami mengajukan sebuah rangkaian yang areanya lebih efisien. Desain ini membutuhkan beberapa asumsi. 5.3.1 Rangkaian Rancangan berdasarkan pada kenyataan bahwa dalam aplikasi hanya menggunakan pengali dan penambah dengan angka tertentu saja (http://en.wikipedia.org . 2014. Linear...). Sebagai contoh, kita merancang sebuah rangkaian untuk modulus 8-bit. Diasumsikan bahwa wordlengths dari pengali menggunakan 3-bit dan wordlengths dari penambah adalah 2-bit. Gambar 5.10 menunjukkan rangkaian modifikasi dari rancangan sebelumnya.

Gambar 5.10 Desain rangkaian yang di ajukan untuk efisiensi area lebih lanjut (n=8) Desain rangkaian sebelumnya menggunakan wordlengths yang sama disemua koneksi. Oleh karena itu, blok pengali harus di terapkan dengan rangkaian 8x8-bit (asumsi n=8). Namun, desain terakhir membutuhkan lebih sedikit rangkaian. Gambar 5.11 memperlihatkan konfigurasi hubungan dari blok pengali.

14

Gambar 5.11 Desain wordlengths pada blok pengali Berdasarkan rule aritmatika dan untuk mengurangi area (Zulfikar dkk. 2012. FPGA Based... ), perkalian dari B4 (8 bit) dan B1 (3 bit) akan memerlukan 10 bit. Pada rancangan, kami abaikan (tidak dihubungkan) kedua net (kabel) tertinggi X(8) dan X(9). Begitu juga dengan blok penambah, penambahan dari X (8 bit) dan B2 (2 bit) akan membutuhkan 9 bit. Pada kasus ini hanya sebuah net M(8) yang diabaikan seperti diperlihatkan pada gambar 5.12.

Gambar 5.12 Desain wordlengths pada blok penambah 5.3.2

Perbandingan Empat jenis chip Xilinx dipilih untuk perbandingan kecepatan dan area antara desain baru

dengan dengan desain sebelumnya. Tabel V memperlihatkan perbandingan area yang dibutuhkan untuk modulus m=28 (8 bit), m=216 (16 bit) dan m=231 (31 bit) pada chip Virtex 7, Spartan 6, Kintex 7 dan Zynq. Tabel V. Perbandingan area yang diperlukan diantara chip-chip Xilinx Area Occupies 8 bit

16 bit

31 bit

(Slices/LUTs)

(Slices/LUTs)

(Slices/LUTs)

Chips

[13] Virtex 7

Proposed [13]

Proposed

[13]

Proposed

16/10

19/30

32/18

36/62

92/63

66/122

Spartan 6 16/10

19/30

32/18

33/19

92/63

67/122

Kintex 7

16/10

19/30

32/18

35/62

92/63

65/122

Zynq

16/10

19/30

32/18

35/62

92/63

65/122

15

Tabel VI memperlihatkan perbandinagn kecepatan dari rancangan baru dan sebelumnya. Dapat dilihat bahwa, desain terakhir lebih cepat. Frekuensi maksimum yang dapat diraih adalah bervariasi dari 154 MHz sampai 411 MHz. Dengan meningkatnya wordlenths, frekuensi maksimum menurun. Spartan 6 adalah chip yang paling lambat, Kintex 7 dan Zynq adalah yang terbaik dalam hal ini. Tabel VI. Perbandingan maksimum frekuensi diantara chip-chip Xilinx Chips [13] 270 154 309 272

Virtex 7 Spartan 6 Kintex 7 Zynq

Maximum Frequency (MHz) 8 bit 16 bit 31 bit Proposed [13] Proposed [13] Proposed 376 270 361 139 337 248 154 158 73 209 411 270 397 158 369 411 272 397 140 369

Dalam rangka membuat perbandingan yang lebih detail, area dari rangkaian yang dirancang terhadap yang sebelumnya di implementasikan ulang, di analisa, dan dilakukan beberapa perhitungan dari hasil synthesis. Tabel VII sampai dengan Tabel XII menjelaskan lebih terhadap perbandingan area. Area di representatsikan dalam hal penggunaan flip-flop dan full adder. Dari tabel VII dan VIII, jumlah Flip-flop dan adder dari rangkaian yang didesain terakhir kira-kira setengah dari yang sebelumnya. Rangkaian tersebut akan lebih efisien lagi jika di rancang untuk modulus yang lebih tinggi seperti terlihat pada tabel IX, tabel X untuk m=216 dan tabel XI, tabel XII untuk m=231. Tabel VII. Perhitungan area berdasarkan hasil synthesis untuk modulus 8 bit (desain sebelumnya) Circuits Multipliers Adders Registers

Bit Size 8x8-bit 16-bit 8-bit Total

Counts 1 1 4

Flip-Flops 32 32

Full Adders 64 16 80

Tabel VIII. Perhitungan area berdasarkan hasil synthesis untuk modulus 8 bit (desain baru) Circuits Multipliers Adders Registers

Bit Size 8x3-bit 11-bit 8-bit 3-bit 2-bit Total

Counts 1 1 2 1 1

Flip-Flops 16 3 2 21


16

Tabel IX. Perhitungan area berdasarkan hasil synthesis untuk modulus 16 bit (desain sebelumnya) Circuits Multipliers Adders Registers


Counts 1 1 4

Flip-Flops 64 64


Tabel X. Perhitungan area berdasarkan hasil synthesis untuk modulus 16 bit (desain baru) Circuits Multipliers Adders Registers

Bit Size 17x3-bit 20-bit 17-bit 16-bit 3-bit 2-bit Total

Counts 1 1 1 1 1 1

Flip-Flops 17 16 3 2 38


Tabel XI. Perhitungan area berdasarkan hasil synthesis untuk modulus 32 bit (desain sebelumnya) Circuits Multipliers Adders Registers


Counts 1 1 4

Flip-Flops 124 124


Tabel XII. Perhitungan area berdasarkan hasil synthesis untuk modulus 31 bit (desain baru) Circuits Multipliers Adders Registers

Bit Size 31x3-bit 32-bit 31-bit 3-bit 2-bit Total

Counts 1 1 2 1 1

Flip-Flops 64 3 2 69


Rancangan baru diturunkan dari kebiasaan dari data masukan ke sistem, dia dapat bervariasi berdasarkan aplikasi LCG. Yang pasti suatu hal yang dapat dipelajari disini adalah disana ada peluang untuk mengurangi area yang terpakai dan meningkatkan kecepatan apapun aplikasinya.

17

BAB 6 RENCANA TAHAPAN BERIKUTNYA

Penelitian penghematan area dari rangkaian komputasi elektronik direncanakan akan selesai setelah 3 tahun. Pada tahun pertama (2014), penelitian ini mempunyai dua tahapan tujuan yaitu tahap awal dan tahap lanjutan. Kedua tahapan tersebut telah tercapai dengan baik. Tahun berikutnya (2015), peneliti berencana memilih rangkaian transformasi Fourier. Sebagaimana pada tahun yang telah berjalan, penelitian penghematan area terhadap rangkaian transformasi fourier juga akan dijabarkan kedalam dua tahapan. Tahapan awal terdiri dari langkah-langkah sebagai berikut: 1. Melakukan analisis statistik terhadap semua wordlengths yang digunakan dari rangkaian transformasi Fourier jenis Discrete Fourier Transform (DFT). 2. Mereduksi wordlengths dari rangkaian tersebut. 3. Membandingkan area dari rangkaian DFT yang telah direduksi wordlengths nya dengan area dari rangkaian DFT konvensional dan yang diajukan orang lain. Tahapan lanjutan terdiri dari langkah-langkah sebagai berikut: 1. Melakukan analisis secara statistik secara mendalam terhadap semua data-data yang mungkin digunakan untuk masukan ke rangkaian DFT. 2. Dari analisa tersebut, akan dirancang rangkaian DFT modifikasi. Hal ini bertujuan untuk mencapai hasil yang lebih optimal. 3. Mendokumentasikan dalam bentuk laporan penelitian dan mendiseminasikan hasil rancangan lanjutan tersebut pada jurnal internasional.

18

BAB 7 KESIMPULAN DAN SARAN

Tujuan awal dan lanjutan dari penelitian ini pada tahun 2014 telah tercapai. Rangkaian yang dipilih adalah LCG yang digunakan untuk pembangkitan bilangan random. Rancangan dan implementasi dari LCG kedalam FPGA telah berhasil dilakukan. Hasil awal dari penelitian ini telah dipublikasikan pada jurnal internasional IJECCE edisi juli-agustus 2014. Rancangan yang lebih efisien telah berhasil dirancang. Dari hasil perbandingan, rangkaian modifikasi jauh lebih efisien dalam hal area dan kecepatan dibandingkan dengan yang didesain pada tahapan awal. Hasil penelitian dari desain yang terakhir telah di terima pada seminar internasional ICCEI 2015.

19

DAFTAR PUSTAKA

A note on random number generation. September 2009. Christophe Dutang dan Diethelm Wuertz. D E Knuth. 2002. The Art of Computer Programming: seminumerical algorithms. Vol. 2, Edisi Ketiga. Massachusetts: Addison-Wesley. D H Lehmer. 1954. Random number generation on the BRL high speed computing machines. Oleh M L Juncosa. Math. Rev. 15, 559 F Severance. 2001. System Modeling and Simulation. John Wiley & Sons, Ltd. p. 86. http://en.wikipedia.org. 2014. Comparison of hardware random number generators. 10 Maret http://en.wikipedia.org. 2014. List of random number generators, 11 Maret http://en.wikipedia.org . 2014. Linear congruential generator, 10 Maret http://www.letech.jpn.com. 2014. Genuine Random Number Generator (GRANG). 10 Maret. M Anis dkk. 2009. Low-Power Design of Nanometer FPGAs: Architecture and EDA. Morgan Kaufmann. N Harald. 1992. Random Number Generation and Quasi-Monte Carlo Methods. Society for lndustrial and Applied Mathematics. Philadelphia. Numerical Computing with MATLAB. 2008. By Cleve B. Moler, SIAM. P P Chu. 2006. RTL Hardware Design Using VHDL: Coding for Efficiency, Portability, and Scalability. Jhon Wiley and Sons. S Hauck dkk. 2007. Reconfigurable Computing: The Theory and Practice of FPGA-Based Computation. Morgan Kaufmann. S K Park dan K W Miller (1988). Random number generators: good ones are hard to find. Association for Computing Machinery. 31(10). pp: 1192-2001. S Kilts. 2007. Advanced FPGA Design: Architecture, Implementation, and Optimization. Wiley-IEEE Press. Wolfram Mathematica ® Tutorial Collection. 2008. Random Number Generation. www.doulos.com. 2013. VHDL Vector Arithmetic using Numeric_std. 8 th March. Zulfikar. 2009. Generating Non Uniform Random Numbers Using Residue and Rejection Methods. Jurnal Rekayasa Elektrika. Vol. 8 No. 2. Zulfikar. 2014. FPGA Implementations of Uniform Random Number based on Residue Method. Jurnal Rekayasa Elektrika. Vol. 11 No. 1. Zulfikar. 2012. Novel Area Optimization in FPGA Implementation Using Efficient VHDL Code. Jurnal Rekayasa Elektrika. Vol. 10 No. 2. Zulfikar dkk. 2012. FPGA Based Complete Set of Walsh and Inverse Walsh Transforms for Signal Processing. Jurnal Electronics and Electrical Engineering. Vol.18. No. 8. Pp: 3-8.

Zulfikar dkk. 2014. Design and Implementations of Linear Congruential Generator into FPGA. International Journal of Electronics Communication and Computer Engineering. Vol. 5, Issue 4. Pp: 809-813.

20

LAMPIRAN I: BIODATA KETUA TIM PENELITI A. Identitas Diri 1 2 3 4 5 6 7 8 9 10 11

Nama Lengkap (dengan gelar) Jenis Kelamin Jabatan Fungsional NIP NIDN Tempat dan Tanggal Lahir E-mail Nomor Telepon/HP Alamat Kantor Nomor Telepon/Faks Lulusan yang Telah Dihasilkan

12. Mata Kuliah yang diampu

Zulfikar, S.T., M.Sc. L Lektor 197507202006041003 0020077507 Kampung Sentosa, 20 Juli 1975 [email protected] 081280239034 Jl Syech Abdurrauf, Darussalam 0651-7554336 S-1= 3 orang; S-2= - orang; S-3= - orang 1. Elektronika Digital 2. Perancangan VLSI 3. Elektronika Industri 4. Teknik Digital 5. Elektronika Telekomunikasi

B. Riwayat Pendidikan Nama Perguruan Tinggi Bidang Ilmu Tahun Masuk-Lulus Judul Skripsi/Thesis

Nama Pembimbing/Promotor

S-1 Universitas Sumatera Utara Teknik Elektro 1994-1999 Pengalokasian pita suara dan data ke dalam jaringan BISDN Ir. Zulfin, M.T.

S-2 King Saud University Teknik Elektro 2008-2011 An Intellectual Property Core for Spectrum Analysis, Synthesis and Processing of Periodic Multiple Digital Signals Prof. Shuja A Abbasi

C. Pengalaman Penelitian Dalam 5 Tahun Terakhir No.

Tahun

1

2014

2

2010

3

2009

Judul Penelitian

Sumber

Metode Efisiensi Area Integrated Circuit (IC) dengan Reduksi Wordlengths untuk Meningkat kan Kinerja Perangkat Komputasi Elektronik An Advanced Application Specific IC Research Development of a MATLAB based Silicon Process Technology Simulator

KSU : King Saud University NPST: National Plant for Sciences Technology, Saudi Arabia

21

Pendanaan Jml (Juta Rp)

DIPA

46

NPST

4.800

KSU

80

D. Pengalaman Pengabdian Kepada Masyarakat dalam 5 Tahun Terakhir No.

Tahun

1

2012

2

2008

3

2006

Judul Pengabdian Kepada Masyarakat Pembinaan kelistrikan untuk keamanan dan penghematan energi kepada masyarakat Gampong Mon Mata Kecamatan Lhong Aceh Besar Studi UKL-UPL Pembangunan PLTMH Bergang Pelatihan Pengelolaan Manajemen Laboratorium Komputer SMA di Propinsi Nanggroe Aceh Darussalam

Sumber

Pendanaan Jml (Juta Rp)

Mandiri

5,8

BRR

20

BRR

180

E. Publikasi Artikel Ilmiah Dalam Jurnal Dalam 5 Tahun Terakhir No. Judul Artikel Ilmiah 1

FPGA Implementation of Uniform Random Number Using Residue and Rejection Method

2

Design of Linear Congruential Generator based on Wordlengths Reduction Technique into FPGA

3

Processing of Multiple Digital Signals Based on Real-time Walsh Transform

4

FPGA Based Complete Set of Walsh and Inverse Walsh Transforms for Signal Processing Novel Area Optimization in FPGA Implementation Using Efficient VHDL Code Design and Implementation of an Improved Arbitrary Waveform Generator Based on Walsh Functions Perancangan Pengontrolan Traffic Light Otomatis

5

6

7

Nama Jurnal

Volume/Nomor/ Tahun

Jurnal Rekayasa Elektrika

Volume 11 / Nomor 1 / Tahun 2014

International Journal of Electronics Communication Computer Engineering International Journal of Electrical and Computer Engineering Electronics and Electrical Engineering

Volume 5 / Nomor 4 / Tahun 2014 Volume 3 / Nomor 2 / Tahun 2013


Rekayasa Elektrika


International Journal of Physical Sciences


Rekayasa Elektrika


F. Pemakalah Seminar Ilmiah (Oral Presentation) dalam 5 Tahun Terakhir No. Nama Pertemuan Ilmiah / Seminar 1 IEEE International Conference on Electrical Control & Computer Engineering (INECCE 2011)

Judul Artikel Ilmiah FPGA Based Processing of Digital Signals using Walsh Analysis

22

Waktu dan Tempat 21 – 22 Juni 2011, Pahang, Malaysia

2

IEEE International Conference on Advances in Computing, Control and Telecommunication Technologies (ACT 2010)

FPGA Based Analysis and Multiplication of Digital Signals

2 – 3 Desember 2010, Jakarta

G. Karya Buku dalam 5 Tahun Terakhir No. Judul Buku

Tahun

Jumlah Halaman

Penerbit

1 H. Perolehan HKI dalam 5–10 Tahun Terakhir No. Judul/Tema HKI 1

Tahun

Jenis

Nomor P/ID

I. Pengalaman Merumuskan Kebijakan Publik/Rekayasa Sosial Lainnya dalam 5 Tahun Terakhir No. Judul/Tema/Jenis Rekayasa Sosial Tahun Tempat Respon Lainnya yang Telah Diterapkan Penerapan Masyarakat 1 J. Penghargaan dalam 10 tahun Terakhir (dari pemerintah, asosiasi atau institusi lainnya) Institusi Pemberi Penghargaan No. Jenis Penghargaan Tahun 1 Semua data yang saya isikan dan tercantum dalam biodata ini adalah benar dan dapat dipertanggungjawabkan secara hukum. Apabila di kemudian hari ternyata dijumpai ketidaksesuaian dengan kenyataan, saya sanggup menerima sanksi. Demikian biodata ini saya buat dengan sebenarnya untuk memenuhi salah satu persyaratan dalam pengajuan Hibah Penelitian Bersaing

Banda Aceh, 28 November 2014 Ketua,

(Zulfikar) 23

LAMPIRAN II: BIODATA ANGGOTA TIM PENELITI A. Identitas Diri 1 2 3 4 5 6 7 8 9 10 11

Nama lengkap (dengan gelar) Jenis Kelamin Jabatan Fungsional NIP NIDN Tempat dan Tanggal Lahir E-mail Nomor Telepon/HP Alamat Kantor Nomor Telepon/Faks Lulusan yang Telah Dihasilkan

12

Mata Kuliah yang Diampu

Hubbul Walidainy, ST, MT L Lektor 197308262000121001 0026087301 Banda Aceh, 26 agustus 1973 [email protected] 0651 22905 Jl Syech Abdurrauf no 7, Darussalam S-1 = 32 orang; S-2 = … orang; S-3 = … orang 1. Dasar Telekomunikasi 2. Kalkulus 1 3. Elektronika Telekomunikasi 4. Analisis Numerik

B. Riwayat Pendidikan Nama Perguruan Tinggi Bidang Ilmu Tahun Masuk-Lulus Judul Skripsi/Tesis/Disertasi

S1 Univ. Gadjah Mada Teknik Elektro 1992-1998 Studi Kelayakan UMTS

Nama Pembimbing/Promotor

Adhi Soesanto, MSc, PhD

S2 Univ. Gadjah Mada Teknik Elektro 1999-2003 Proses Adaptif untuk Menghapus Gema Prof. Adhi Soesanto, MSc, PhD

C. Pengalaman Penelitian Dalam 5 Tahun Terakhir No 1

Tahun 2012

Judul Sumber DIPA

Laboratorium Eksperimen: Pengaturan Tinggi

Pendanaan Jml (Juta Rp) 15

Permukaan Cairan pada Tangki Secara Otomatis Menggunakan UniTrain Berbasis PID

D. Pengalaman Pengabdian Kepada Masyarakat dalam 5 Tahun Terakhir No

Tahun

1

2014

2

2012

Judul Metode Efisiensi Area Integrated Circuit (IC) dengan Reduksi Wordlengths untuk Meningkat kan Kinerja Perangkat Komputasi Elektronik Pelatihan Dasar Antena Dan Fiber Optik Untuk Siswa SMK Telkom di Kota Banda Aceh

24

Sumber DIPA

Mandiri

Pendanaan Jml (Juta Rp) 46

8

E. Publikasi Artikel Ilmiah Dalam Jurnal dalam 5 Tahun Terakhir No

Judul Artikel Ilmiah

Nama Jurnal

Volume/ Nomor/Tahun

1

Design of Linear Congruential Generator based on Wordlengths Reduction Technique into FPGA

International Journal of Electronics Communication Computer Engineering


2

Analisa Kegagalan Call pada BTS Flexy di PT Telkom Kandatel Banda Aceh

Jurnal Rekayasa Elektrika

Vol 9, no 1, april 2010

F. Pemakalah Seminar Ilmiah (Oral Presentation) dalam 5 Tahun Terakhir No

Nama Pertemuan Ilmiah /Seminar

Judul Artikel Ilmiah

Waktu dan Tempat

1

SNETE 2011

Analisis Network Error Pada Jaringan Lokal Akses Tembaga (JARLOKAT) Studi Kasus di Sto Kancatel Lhokseumawe

24 oktober 2011

Semua data yang saya isikan dan tercantum dalam biodata ini adalah benar dan dapat dipertanggungjawabkan secara hukum. Apabila di kemudian hari ternyata dijumpai ketidaksesuaian dengan kenyataan, saya sanggup menerima risikonya. Demikian biodata ini saya buat dengan sebenarnya untuk memenuhi salah satu persyaratan dalam pengajuan Hibah Penelitian Bersaing.

Banda Aceh, 28 November 2014 Anggota I,

(Hubbul Walidainy)

25

LAMPIRAN III: Publikasi Artikel pada Jurnal Internasional Berikut adalah artikel yang telah dipublikasi pada Internasional Journal of Electronics Communication and Computer Engineering (IJECCE), Volume 5, Issue 4, Juli-Agustus 2014.

26

International Journal of Electronics Communication and Computer Engineering Volume 5, Issue 4, ISSN (Online): 2249–071X, ISSN (Print): 2278–4209

Design and Implementations of Linear Congruential Generator into FPGA Zulfikar

Hubbul Walidainy

Department of Electrical Engineering Syiah Kuala University, Banda Aceh 23111, Indonesia Email: [email protected]

Department of Electrical Engineering Syiah Kuala University, Banda Aceh 23111, Indonesia Email: [email protected]

Abstract – This paper exposes circuit design of linear congruential generator (LCG) and implementation in FPGA. The circuit is derived from LCG algorithm proposed by Lehmer. Wordlengths reduction technique has been used to simplify the circuit. Several nets connection among the blocks of the circuit are ignored or disconnected. Simulation either behavior or timing have been done successfully. Four best Xilinx chips are chosen to gather comparison data of maximum speed and area occupied. Kintex 7 is the fastest chip among all it is about 309 MHz and Spartan 6 is slowest one which is only 73 MHz. The area occupied is similar among all of the selected chips.

for testing their ideas. Several of these has been realized into hardware and sell into the market [5],[10]. Initially, the algorithm of LCG combined with MonteCarlo method has been used for generating non uniform random numbers using Matlab [11]. After that, we develop the circuit of random number generator and implemented in FPGA [12]. In the paper, the increment factor (c) has been ignored (c = 0). Beside, we present novel design and FPGA implementation of LCG algorithm without ignoring the increment. The rest of this work report are organized as follows. Section II deals with theory of LCG algorithm. The design circuit of LCG for FPGA implementation and nets connections are covered in section III. Section IV provides some implementations data and analysis. Finally, the conclusions are viewed in section V.

Keywords – Linear Congruential Generator, FPGA, Xilinx, word lengths reduction, Kintex.1

I. INTRODUCTION Random numbers have been used in daily activities since long times ago. Nowadays, a small and cheap kid’s toy containing a random number circuit inside it. For example, in a toy like (that mimic) mobile phone will ring different types of sound when the same button is pressed more than one time. Several random numbers theory have been introduced in the last several decades. Linear congruential generator (LCG) that introduced 1954 by Lehmer [1] is the oldest and the most widely used pseudorandom number generator (PNG) [2]. Park & Miller suggest good parameters for LCG [3]. The suggestion is used in Matlab for generating uniform random numbers [4]. Many other random number generators have been proposed and also used in many applications. Blum BlumShub, Wichmann-Hill, Complementary multiply with carry, Inversivecongruential generator, ISAAC (cipher), Lagged Fibonacci generator, Linear feedback shift register, Maximal periodic reciprocals, Mersenne twister, Multiply-with-carry, Naor-Reingold Pseudorandom Function, RC4 PRGA, Well Equidistributed Long-period Linear, and Xorshift are some of the well-known methods [5]-[8]. Hardware for generating random number also available as well as its algorithm. The hardware have been used since 2008. LETech is the fastest among all hardware for computing random numbers, this hardware has been developed since 2008 [9], [10]. Research for finding the suitable algorithm of generating random number is well establish field until now. Many researchers use field programmable gate arrays (FPGA)

II. LINEAR CONGRUENTIAL GENERATOR There is a popular method and most used to generate random number called linear congruential generator. The idea was introduced by Lehmer according to sequential formula in (1) [1]. (1) X n 1  ( aX n  c ) mod m Where m is modulus, a is multiplier, c is increment. Parameters a, c and m have to be chosen carefully in order to avoid repetition of similar numbers before m [6]-[8]. Park & Miller suggested a good results will be obtained by choosing c=0 [3]. The modulus m should be a large prime integer, multiplier a will be an integer in the range 2, 3, . . . , m-1. The cycle length of LCG will never exceed modulus m, but it can be maximized using three following conditions [7], [13]:  c is relatively prime to modulus m,  multiplier a-1 is a multiple of every dividing modulus m,  multiplier a-1 is a multiple of four when modulus m is a multiple of four.

III. LCG CIRCUIT DESIGN A. General Circuit of LCG

Fig.1 shows block diagram LCG operation in general (seed is ignored). It requires multiplier, adder, comparator and subtractor blocks. Multiplier is used to multiple previous random value X with a, then add with increment c. After that it is compared to modulus m. The number is considered as random number if it is smaller or equal to m. The authors gratefully acknowledge the financial support from Otherwise, the number then subtracted with m. The result Research Center of Syiah Kuala University, Indonesia under project of this is then consider as random number. Hibah Bersaing. Copyright © 2014 IJECCE, All right reserved 809

Inter ternational Journal of Electronics Communication an and Computer Engineering Volume 5, Issue 4, ISSN (Online): 2249–071X, X, ISSN (Print): 2278–4209 The block diagram of Fig. 1 is inv involving arithmetic operation such as multiplication, additio ition, subtraction and comparison. In order simplify the proc ocess, the circuit is designed using word lengths reductionn technique that has been suggested in [14]. Then subtarcto ctor and comparator Fig. 2. blocks can be removed, as shown in thee F The designed circuit consist of a multiplexer, a ed clear), and three multiplier, an adder, a buffer (required buffers (required enable). Ports input SSeed, A and C are used to pass initial value, multiplier andd increment into the circuit. Meanwhile, port O is used to taking out the resulted random numbers.

Fig.1. Block diagram m oof LCG operation

2. General circuit of linear congruential generator Fig.2. als enable and reset. The circuit is controlled by two signals GH (enable=LOW) to Initially, signal reset have to be HIGH clear the previous stored values in the buffer B4. Signal enable determine when the operationn sshould be started. Pre-defined value (seed), increment andd multiplier have to be available at the input ports before eenable goes HIGH lock goes HIGH, a (reset=LOW). Then, every times cloc random number resulted. Fig.3shows the circuit of the two signal controls. Fig.4. Word lengths reductio ction in multiplier’s block

ned LCG circuit Fig.3. Signal controls of the designe

B. Wordlengths Reduction The circuit of Fig. 2 can be used forr any word lengths. The reduction of word lengths have to cconstruct carefully lt. For example, the to avoid undesirable operation result. word lengths of 8 LCG is designed for using maximum w lier block and adder bit, the nets configurations of multiplie block are shown in the Figs. 4 and 5.

Fig.5. Word lengths reduc uction in adder’s block Based on arithmetic rules an and to reduce area [15], the multiplication of B4 (8 bit) andd B1 (8 bit) would require 15 bit at the output. In the des esign, we simply truncated (disconnected) the seven-highe her nets (X(8) up to X(14)), this design is shown in the Fig. g. 4. Similarly, we can do the er. In this case only one net same thing to the nets of adder (M(8)) disconnected as shownn in the Fig. 5..

Coopyright © 2014 IJECCE, All right reserved 810

Inter ternational Journal of Electronics Communication an and Computer Engineering Volume 5, Issue 4, ISSN (Online): 2249–071X, X, ISSN (Print): 2278–4209

IV. IMPLEMENTATIONS AND DISCUSSIONS A. Behavior Simulation The circuit in the Fig. 2 has beenn implemented into FPGA program. The simulations have ve been done using Xilinx ISE design suite. Some importan tant data of synthesis rea and speed have result is shown. The comparison of are been done over several Xilinx’s chips.

Fig.6 shows behavior simu mulation result of modulus m=255, seed=7, multiplier a=3 =3 and increment c=1. It can be seen the resulting numberss aare random starting from 7 and all numbers are smaller than an 255. Figs.7 and 8 show behaviorr si simulation result of modulus m=216–1 and m=231–1 respe pectively. Also all number produced there never exceed mo modulus.

mulation behavior result of m=255, seed=7, a=3, c=1 Fig.6. Simu

mulation behavior result of m=216-1, seed=7, a=3, c=1 Fig.7. Simu

mulation behavior result of m=231-1, seed=7, a=3, c=1 Fig.8. Simu

B. Synthesis result Some important synthesis data of the designed circuit tex 7 chip are: using modulus m=255 into Xilinx Virtex HDL Synthesis Report Macro Statistics # Multipliers :1 8x8-bit multiplier :1 # Adders/Subtractors :1 16-bit adder :1 # Registers :4 8-bit register :4 # Multiplexers :1 8-bit 2-to-1 multiplexer :1 ------------------------------------------------------------------------Slice Logic Utilization: Number of Slice Registers: 16 out off 437600 0% Number of Slice LUTs: 10 out of 218800 0% Number used as Logic: 10 out of 218800 0% Slice Logic Distribution:

Number of LUT Flip Flop pairs irs used: 17 Number with an unused Flip Flo Flop: 1 out of 17 5% Number with an unused LUT:: 7 out of 17 41% Number of fully used LUT-FF F ppairs: 9 out of 17 52% Number of unique control sets: s: 2 ------------------------------------------------------------------------Minimum period: 3.710nss (Maximum Frequency: 269.513MHz) Minimum input arrival time bef efore clock: 2.023ns Maximum output required timee after clock: 0.575ns Maximum combinational path th ddelay: No path found From HDL synthesis report, rt, the design circuit requires an 8x8-bit multiplier, 16-bit ad adder, four 8-bit register and 8-bit 2-to-1 multiplexer. In term rms of slice logic utilization, the design occupies 16 slice re registers and 10 slice LUTs. The distribution of slice logic ic ffrom total amount of 17 are 9 for fully used LUT-FF pairs, s, 7 to unused LUT and 1 for unused flip-flop. The circuit als also requires 2 unique control sets.

Coopyright © 2014 IJECCE, All right reserved 811

Inter ternational Journal of Electronics Communication an and Computer Engineering Volume 5, Issue 4, ISSN (Online): 2249–071X, X, ISSN (Print): 2278–4209 The speed of the circuit limited to around 270 MHz when it is implemented into Virtex 77. Minimum input arrival time before clock is 2.023 ns. Th This means the data should be available at input port befo fore that time. The maximum output required time after cloc lock is 0.5775 ns.

C. Timing Simulation Fig.9 shows a close look of timing simulation result. the number change from 67 There are some glitches whenn th to 202. This is because timee from clock edge to pads from 9.399 ns to 9.818 ns varied. This variation range fr t). (post-PAR static timing report).

Fig.9. A close view of timing simulation

D. Comparison Four best Xilinx chips has been ch chosen in order to compare the speed and area of the design igned circuit. Table I shows comparison of maximum frequ quency required for modulus m=255 (8 bit), m=216-1 (16 bit) and m=231-1 (31 bit) over Virtex 7, Spartan 6, Kintex 7 an and Zynq chips. Table I : Maximum frequency comparis rison among Xilinx chips Maximum Freque uency (MHz) Chips 8 bit 16 bit it 31 bit Virtex 7 270 270 139 Spartan 6 154 154 73 Kintex 7 309 270 158 Zynq 272 272 140

area becomes twice when usin ing modulus around 16 bits. Meanwhile when the moduluss is changed to 31 bits, the occupied slices and LUTs incr crease to around three time. clear views of this behavior. Figs. 11 and 12 show a more cle ies among Xilinx chips Table II: Area occupies Chips Virtex 7 Spartan 6 Kintex 7 Zynq

8 bit Slices LUTs 16 10 16 10 16 10 16 10

Are rea Occupies 16 bit Slic lices LUTs 32 18 32 18 32 18 32 18

31 bit Slices LUTs 92 63 92 63 92 63 92 63

For m=255, the fastest chip is Kintex tex 7 and the slowest one is Spartan 6, but for m=216–1, th the fastest chips is Zynq. In general, Kintex 7 is the fastes test and Spartan 6 is the slowest chip. A more clear view of this figure can be seen graphichally in the Fig. 10.

Fig.11. Comparison of slice utiliz tilization among Xilinx chips

Fig.10. Comparison of maximum freque uency among Xilinx chips Table II views area comparison am among four Xilinx chips. It can be seen that all chip occup upies the same area. For m=255, the chips required 16 slicess and 10 LUTs. The

Fig.12. Comparisonn oof LUTs required Coopyright © 2014 IJECCE, All right reserved 812

International Journal of Electronics Communication and Computer Engineering Volume 5, Issue 4, ISSN (Online): 2249–071X, ISSN (Print): 2278–4209

V. CONCLUSION Design and implementation of linear congruential generator into FPGA have been done successfully. It is required special care of wordlengths connecting among the blocks of the circuit. By applying wordlengths reduction technique, a more efficient circuit has been obtained. The maximum frequency of the design circuit is 309 MHz (Kintex 7, m=255), and the minimum frequency is 73 MHz (Spartan 6, m=231–1). Kintex 7 is the best chip of applying the design LCG circuit. Further improvement of the design may be obtained by analyzing behavior of seed, multipliera and increment c. Finally, it is difficult to compare the result to the previous works since there is no available similar circuit or method before.

REFERENCES [1]

[2]

[3]

[4] [5]

[6]

[7] [8] [9]

[10]

[11]

[12]

[13]

[14]

[15]

D. H. Lehmer, “Random number generation on the BRL high speed computing machines,” by M. L. Juncosa. Math. Rev. 15 (1954), 559 http://en.wikipedia.org (2014) - Linear congruential generator, 10th March http://en.wikipedia.org/wiki/ Linear_congruential _generator S. K. Park, and K. W. Miller, “Random number generators: good ones are hard to finnd,” Association for Computing Machinery, 31(10), pp: 1192-2001, 1988. Numerical Computing with MATLAB, By Cleve B. Moler, SIAM,2008 http://en.wikipedia.org (2014) - List of random number generators, 11th March http://en.wikipedia.org/wiki/List_of_ random_number_generators N. Harald, “Random Number Generation and Quasi-Monte Carlo Methods,” Society for lndustrial and Applied Mathematics, Philadelphia, 1992. A note on random number generation, Christophe Dutang and Diethelm Wuertz, September 2009 Wolfram Mathematica ® Tutorial Collection, RANDOM NUMBER GENERATION, 2008 http://www.letech.jpn.com (2014) - Genuine Random Number Generator (GRANG), 10th March http://www.letech.jpn.com/ rng/about_rng_e.html http://en.wikipedia.org (2014) - Comparison of hardware random number generators, 10th March http://en.wikipedia.org/wiki/ Comparison_of_hardware_random_number_generators Zulfikar, “Generating Non Uniform Random Numbers Using Residue and Rejection Methods,” Transaction of Journal Rekayasa Elektrika, Vol. 8 No. 2, October 2009 Zulfikar, “FPGA Implementations of Uniform Random Number based on Residue Method,” Transaction of Journal Rekayasa Elektrika, Vol. 11 No. 1, April 2014 D. E. Knuth, “The Art of Computer Programming: seminumerical algorithms,” Vol. 2,3rd edition edn, Massachusetts: Addison-Wesley, 2002 Zulfikar, “Novel Area Optimization in FPGA Implementation Using Efficient VHDL Code,” Transaction of Journal Rekayasa Elektrika, Vol. 10 No. 2, October 2012 Zulfikar, Abbasi, S A and Alamoud A R M, “FPGA Based Complete Set of Walsh and Inverse Walsh Transforms for Signal Processing,” Transaction of Electronics and Electrical Engineering Journal, Vol.18. No. 8, Pp: 3-8, October 2012.

AUTHOR’S PROFILE Zulfikar was born in Beureunuen, Aceh, Indonesia, in 1975. He received his B.Sc. degree inElectrical Engineering from North Sumatera University, Medan, Indonesia, the M. Sc. Degree inElectrical Engineering from King Saud University, Riyadh, Saudi Arabia, in 1999 and 2011,respectively. He joined as teaching staff in the Department of Electronics at Politeknik Caltex Riau, Pekanbaru, Indonesia in 2003. He served as head of Industrial Control Laboratory, Politeknik Caltex Riau from 2003 to 2006. In 2006, he joined the Electrical Engineering Department, Syiah Kuala University.His current position is head of Digital Laboratory, and his current research interests include VLSI design and System on Chips (SoC).

Hubbul Walidainy was born in Banda Aceh, Aceh, Indonesia, in 1973. He graduated from Electrical Engineering Department at Gadjah Mada University, Yogyakarta, Indonesia, in 1998. The Master Degree inElectrical Engineering from Gadjah Mada University, Yogyakarta, Indonesia, in 2003. He joined in the Department of Electrical Engineering, Syiah Kuala University,Aceh, Indonesia in 2000, as a teaching staff.His current position is the head of Telecommunication Laboratory.

Copyright © 2014 IJECCE, All right reserved 813

LAMPIRAN IV: Publikasi Artikel pada Seminar Internasional Berikut adalah artikel yang telah terima pada Internationa Conference on Communication and Electronics Information (ICCEI) 2015.

32

An Improve Design of Linear Congruential Generator based on Wordlengths Reduction Technique into FPGA Zulfikar 1, HubbulWalidainy 2 Department of Electrical Engineering Syiah Kuala University, Banda Aceh 23111, Indonesia 1 [email protected], 2 [email protected] Abstract — this paper exposes an improve design of linear congruential generator (LCG) based on wordlengths reduction technique into FPGA. The circuit is derived from LCG algorithm proposed by Lehmer and the previous design. The wordlengths reduction technique has been developed more in order to simplify further the circuit. The propose design based on the fact that in applications only specific input data were used. Some nets connections between blocks of the circuit are ignored or truncated. Simulations either behavior or timing have been done and the results is similar to its algorithm. Four best Xilinx chips has been chosen to extract comparison data of peed and area occupied. Further comparison of area occupies in terms of flip-flop and full adder has been made. In general, the propose design overcome the previous published LCG circuit. Index Terms—Linear Congruential Generator, FPGA, Xilinx, word lengths reduction, Improve LCG.

I. INTRODUCTION The use of random numbers has become habit in daily activities since long times ago. Right now, even a cheap kid’s toy containing a random number circuit inside it. For instance, in a toy that mimic mobile phone will ring variation types of sound when the same button is pressed many time. Random numbers theory have been re-introduced in the last several decades. Linear congruential generator (LCG) that introduced 1954 by Lehmer [1] is the oldest and the most commonly used pseudorandom number generator (PNG) [2]. Park and Miller suggest a good parameters for LCG [3]. Their idea has been used in Matlab for generating uniform random numbers until now [4]. Many other theory of random number generators have been proposed and also used in many applications. Blum Blum Shub, Wichmann-Hill, Complementary multiply with carry, Inversive congruential generator, ISAAC (cipher), Lagged Fibonacci generator, Linear feedback shift register, Maximal periodic reciprocals, Mersenne twister, Multiply-with-carry, Naor-Reingold Pseudorandom Function, RC4 PRGA, Well Equidistributed Long-period Linear, and Xorshift are some of the common and well-known methods [5]-[8]. Hardware for generating random number also available as well as their algorithms. Hardware have been used since 2008. LETech is the fastest among all hardware for generating random numbers, this hardware has been developed and marketed since 2008 [9],[10]. Research for searching suitable algorithms of generating random numbers is well establish field until now. Researchers use field programmable gate arrays (FPGA) for testing their algorithms. Some of good design has been realized into hardware and sell into the market [5],[10]. Initially, The algorithm of LCG that has been combined with Monte Carlo method used for generating non uniform The authors gratefully acknowledge the financial support from Syiah Kuala University, Ministry of Education and Culture, Indonesia under project Hibah Bersaing, No. 498/UN11/S/LK-BOPT/2014, 26 May 2014.

random number in Matlab [11]. Later, the development of this has been implemented in FPGA [12]. In the paper, the increment factor (c) has been ignored (c=0). Later then, the technique for generating random number based on full LCG algorithm also available [13]. The paper exposed the LCG circuit design without ignoring the increment factor. We analyze that the technique may be improve further. In this work, we design the more efficient circuit by reducing wordlengths of some input data. Moreover the technique proposed in [13] will produce slightly different random numbers than the original LCG algorithms. The rest of the paper is organized as follows. Section II deals with theory of LCG algorithm. The design of improve LCG circuit for FPGA implementation and nets modifications are explained in section III. The deep analysis and implementations are presented in section IV. Finally, the conclusions are summarized in section V. II. THEORY A. Linear Congruential Generator There is a popular method and most used to generate random number called linear congruential generator. The idea was introduced by Lehmer according to sequential formula in (1) [1]. X n1  (aX n  c) mod m

(1)

Where m is modulus, a is multiplier, c is increment. Parameters a, c and m have to be chosen carefully in order to avoid repetition of similar numbers before m [6]-[8]. Park & Miller suggested a good results will be obtained by choosing c=0 [3]. The modulus m should be a large prime integer, multiplier a will be an integer in the range 2, 3, . . . , m-1. The cycle length of LCG will never exceed modulus m, but it can be maximized using three following conditions [7],[14]:  c is relatively prime to modulus m,  multiplier a-1 is a multiple of every dividing modulus m,  multiplier a-1 is a multiple of four when modulus m is a multiple of four. B. Parameters in Common Use of LCG The requirements mentioned in the previous section are referred to Hull-Dobell theorem [15]. LCG are able to produce the pseudo random number that can pass test of randomness. The condition is sensitive in choosing the good parameters c, m, and a. In history, poor choices had been led to the ineffective realizations or implementations of LCG itself. As an example of the poor parameters choice is RANDU (see Table I), this method was commonly implemented in the early 1970 and

cause to many results that are currently being questioned. Random numbers resulted by LCG will be more efficient when the modulus approach very high numbers, often reach the maximum computer (machine) ability such as m=232 or TABLE I.

m=264. Table I lists the parameters of LCGs in commonly use, including built in functions such as rand() that used in runtime libraries of various compilers [2].

PARAMETERS IN COMMON USED FOR LCG APPLICATIONS [2]

Source

m

(multiplier) a

(increment) c

Numerical Recipes 232 1664525 1013904223 Borland C/C++ 232 22695477 1 glibc (used by GCC) 231 1103515245 12345 ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++ 231 1103515245 12345 Borland Delphi, Virtual Pascal 232 134775813 1 Microsoft Visual/Quick C/C++ 232 214013 (343FD16) 2531011 (269EC316) Microsoft Visual Basic (6 and earlier) 224 1140671485 (43FD43FD16) 12820163 (C39EC316) RtlUniform from Native API 231 − 1 2147483629 (7FFFFFED16) 2147483587 (7FFFFFC316) Apple CarbonLib, C++11's minstd_rand0 231 − 1 16807 0 C++11's minstd_rand 231 − 1 48271 0 MMIX by Donald Knuth 264 6364136223846793005 1442695040888963407 Newlib 264 6364136223846793005 1 VAX's MTH$RANDOM, old versions of glibc 232 69069 1 Java's java.util.Random, glibc [ld]rand48[_r]() 248 25214903917 11 RANDU 231 65539 0

III. LCG CIRCUIT DESIGN A. General Circuit of LCG Fig. 1 show the LCG circuit proposed in [13]. The designed circuit used equal wordlengths of n for connection between blocks. The designed circuit consist of (assumed modulus=2n): - A n x n-bit multiplier - A n-bit 2-to-1 multiplexer - An n-bit adder - 3 x n enable buffers (B1, B2, B3) - n buffers (B4)

Fig. 1. General circuit of linear congruential generator [13]

Fig. 2. Proposed circuit design of a more efficient area (n=8)

For certain applications, the design may be improve further. By using the same circuit blocks, we proposed a circuit for a more efficient area. This design requires some assumptions. The design based on the fact that in application only specific multiplier and increment were used [2]. Here as an example, we design an efficient circuit for modulus of maximum 8-bit. It is assumed that the wordlength of multiplier use 3-bit and the wordlength of increment c use 2bit data. Fig. 2 show a slight modification circuit of the previous design.

The proposed circuit in the Fig. 2 is also controlled by two signals enable and reset. The controlling process is equal to the previous design. Initially, signal reset have to be HIGH (enable=LOW) in order to clear the stored values in the buffer B4. Signal enable determine whenever the operation should be started. Pre-defined data of seed, increment and multiplier have to be available at the input ports just before signal enable goes HIGH (reset must be LOW). After that, each times the clock goes HIGH, a random number is produced. Fig.3 views the circuit configuration of the two control signals.

Fig. 3. Signal controls of the designed LCG circuit [13]

In practice, the proposed circuit will also reduce number of net connections between CE1, CE2 and buffers. B. Wordlengths Reduction The circuit of Fig. 2 used equal wordlengths everywhere. Therefore, the multiplier block have to be implement with an 8x8-bit circuit (assumed n=8). However, the proposed design requires smaller circuit. Fig. 4 shows the net connections configuration of the multiplier block.

Fig. 4. Proposed wordlengths reduction in multiplier’s block

Based on arithmetic rules and to reduce area [16], the multiplication of B4 (8 bit) and B1 (3 bit) would require 10 bit

at the output. In the design, we simply truncated (disconnected) the two higher nets of X(8) and X(9). Similarly, we can do the same thing to the nets of the adder. Again, based on arithmetic rules and to reduce area [15], the addition of X (8 bit) and B2 (2 bit) would require 9 bit at the output. But, in this case only one net (M(8)) disconnected as shown in the Fig. 5

Fig. 5. Proposed wordlengths reduction in adder’s block

.Simulation and Comparisons In order to evaluate wether the design works properly, we simulate the proposed circuit in the Fig. 2. Either behavior and timing simulation have been done using Xilinx ISE Design Suite 14.2. Some important information of synthesis result is presented. The comparison to the previous design of area and speed have been done to several Xilinx’s chips. The implementations have been done using three wordlengths 8-bit, 16-bit, and 31-bit. The wordlengths for seed and output are equal wordlengths design. Meanwhile, some input use smaller wordlengths which are multiplier 3bit, increment 2-bit. C. Behavior Simulation Fig. 6 shows input data and results of behavior simulation using modulus m=28, seed=7, multiplier a=3 and increment c=1. It can be seen the result numbers are random starting from 7 and all numbers are smaller than 28. Figs. 7 and 8 show behavior simulation results of modulus m=216 and m=231, respectively. The simulation also numbers which exceed the modulus.

Fig. 6. Simulation behavior result of proposed design using m=28, seed=7, a=3, c=1

Fig. 7. Simulation behavior result of proposed design using m=216, seed=7, a=3, c=1

Fig. 8. Simulation behavior result of proposed design using m=231, seed=7, a=3, c=1 Number of bonded IOBs:

D. Synthesis results Some important data after synthesis step of the propose design circuit using modulus m=28 into Xilinx Zynq chip are: HDL Synthesis Report Macro Statistics # Multipliers 8x3-bit multiplier # Adders/Subtractors 11-bit adder # Registers 2-bit register 3-bit register 8-bit register # Multiplexers 8-bit 2-to-1 multiplexer

: : : : : : : : : :

1 1 1 1 4 1 1 2 1 1

=========================================== Advanced HDL Synthesis Report Macro Statistics MACs 8x3-to-8-bit MAC # Registers Flip-Flops # Multiplexers 8-bit 2-to-1 multiplexer

: : : : : :

1 1 19 19 1 1

Device utilization summary: Selected Device : 7z010clg400-3 Slice Logic Utilization: Number of Slice Registers: 19 Number of Slice LUTs: 30 Number used as Logic: 30

out of out of out of

35200 0% 17600 0% 17600 0%

Slice Logic Distribution: Number of LUT Flip Flop pairs used:40 Number with an unused Flip Flop: 21 out of4052% Number with an unused LUT: 10 out of 40 25% Number of fully used LUT-FF pairs:9 out of 40 22% Number of unique control sets: 3 IO Utilization: Number of IOs:

24

Fig. 9. A close look of timing simulation

21

Specific Feature Utilization: Number of BUFG/BUFGCTRLs: 1

out of 10021% out of

323%

Timing Summary: --------------Speed Grade: -3 Minimum Minimum Maximum Maximum

period: 2.436ns (Maximum Frequency: 410.526MHz) input arrival time before clock: 0.892ns output required time after clock: 0.511ns combinational path delay: No path found

From HDL synthesis report, the propose design circuit requires an 8x3-bit multiplier, 11-bit adder, two 8-bit register, one 3-bit register, one 2-bit register and 8-bit 2-to-1 multiplexer. In terms of slice logic utilization, the design occupies 19 slice registers and 30 slice LUTs. The distribution of slice logic from total amount of 40 are 9 for fully used LUT-FF pairs, 10 to unused LUT and 21 for unused flip-flop. The circuit also requires 3 unique control sets. The maximum frequency of the circuit limited to around 410.52 MHz when it is implemented into Zynq. The minimum input arrival time before clock is 0.892 ns. This means the data should be available (arrive) at input port before that time. The maximum output required time after clock is 0.511 ns. E. Timing Simulation Fig. 9 shows a more close view of timing simulation result. The figure view transition between 202 and 95. There are some glitches appears because of the time from clock edge to pads varied. The variation values are ranging from 8.390 ns to 8.527 ns (post-PAR static timing report).

post-PAR static timing report Clock Clock to Pad ------------+-----------------+------------+-----------------+------------+------------------+--------+ |Max (slowest) clk| Process |Min (fastest) clk| Process | | Clock | Destination | (edge) to PAD | Corner | (edge) to PAD | Corner |Internal Clock(s) | Phase | ------------+-----------------+------------+-----------------+------------+------------------+--------+ O<0> | 8.390(R)| SLOW | 4.033(R)| FAST |Clock_BUFGP | 0.000| O<1> | 8.391(R)| SLOW | 4.035(R)| FAST |Clock_BUFGP | 0.000| O<2> | 8.404(R)| SLOW | 4.046(R)| FAST |Clock_BUFGP | 0.000| O<3> | 8.440(R)| SLOW | 4.071(R)| FAST |Clock_BUFGP | 0.000| O<4> | 8.397(R)| SLOW | 4.037(R)| FAST |Clock_BUFGP | 0.000| O<5> | 8.422(R)| SLOW | 4.049(R)| FAST |Clock_BUFGP | 0.000| O<6> | 8.425(R)| SLOW | 4.052(R)| FAST |Clock_BUFGP | 0.000| O<7> | 8.527(R)| SLOW | 4.155(R)| FAST |Clock_BUFGP | 0.000| ------------+-----------------+------------+-----------------+------------+------------------+--------+

F. Comparison Four Xilinx chips have been chosen for area and speed comparison between the proposed design circuit and the previous one. Table I views comparison of area occupies of modulus m=28 (8 bit), m=216 (16 bit) and m=231(31 bit) over Virtex 7, Spartan 6, Kintex 7 and Zynq chips. TABLE II.

MAXIMUM FREQUENCY COMPARISON AMONG XILINXCHIPS Maximum Frequency (MHz)

Chips

8 bit [13]

16 bit

Proposed [13]

of the propose and the previous methods. Table IV up to table IX show the more about area comparison. The area is represent in terms of flip-flop and full adder used. From tables IV and V, the numbers of flip-flip and adder of the propose design is about a half the previous design. The propose design become more and more efficient when for higher modulus as can be seen at tables VI and VII for m=216 and tables VIII and IX for m=231. TABLE IV.

CALCULATION OF AREA BASED ON SYNTHESIS RESULTS FOR MODULUS 8 BIT [13]

31 bit

Proposed

[13]

Proposed

Circuits

Bit Size

Counts

Flip-Flops

Full Adders

Multipliers

8x8-bit

1

-

64

Virtex 7

270

376

270

361

139

337

Adders

16-bit

1

-

16

Spartan 6

154

248

154

158

73

209

Registers

8-bit

4

32

-

32

80

Kintex 7

309

411

270

397

158

369

Zynq

272

411

272

397

140

369

Table II views the speed comparison of the proposed design and the previous one. It can be seen that the proposed design is faster. The maximum frequency that can be reached vary from 158 MHz to 411 MHz. As the word lengths is increased, the maximum frequency is decrease. Spartan 6 is the slowest chip, Kintex 7 and Zynq are the best choice. TABLE III.

TABLE V.

CALCULATION OF AREA BASED ON SYNTHESIS RESULTS FOR MODULUS 8 BIT (PROPOSE DESIGN)

Circuits

Bit Size

Counts

Flip-Flops

Full Adders

Multipliers

8x3-bit

1

-

24

Adders

11-bit

1

-

11

Registers

8-bit

2

16

-

3-bit

1

3

-

2-bit

1

Total

AREA OCCUPIES COMPARISON AMONG XILINX CHIPS Area Occupies

Chips

Total

8 bit (Slices/LUTs)

16 bit (Slices/LUTs)

TABLE VI. 31 bit (Slices/LUTs)

Counts

Multipliers

16x16-bit

1

Adders

32-bit

1

-

16-bit

4

64

[13]

Proposed

[13]

Proposed

Virtex 7

16/10

19/30

32/18

36/62

92/63

66/122

Spartan 6

16/10

19/30

32/18

33/19

92/63

67/122

Registers

19/30

32/18

35/62

92/63

65/122

Zynq

16/10

19/30

32/18

35/62

92/63

65/122

Based on synthesis report, for m=2 8, the area (both slices and LUTs) requires of the propose design is more than the previous design. This is slightly different for m=2 16, the number of slices is about three times and the number of LUTs is almost equal. When the proposed design is implemented using m=231, the number of slices is less, even though the number of LUTs is still more. Table III shows this phenomena. In order to make a more detail comparison, the area of the design circuit and the previous one are re-implemented, analyzed and we put some calculations of the synthesis results

CALCULATION OF AREA BASED ON SYNTHESIS RESULTS FOR MODULUS 16 BIT [13] Bit Size

Proposed

16/10

35

Circuits

[13]

Kintex 7

2 21

Total TABLE VII.

Flip-Flops

Full Adders 256

64

32 288

CALCULATION OF AREA BASED ON SYNTHESIS RESULTS FOR MODULUS 16 BIT (PROPOSE DESIGN)

Circuits

Bit Size

Counts

Flip-Flops

Full Adders

Multipliers

17x3-bit

1

-

51

Adders

20-bit

1

-

20

Registers

17-bit

1

17

-

16-bit

1

16

-

3-bit

1

3

-

2-bit

1

Total

2

-

38

71

TABLE VIII.

CALCULATION OF AREA BASED ON SYNTHESIS RESULTS FOR MODULUS 31 BIT [13]

[5]

[6]

Circuits

Bit Size

Counts

Multipliers

31x31-bit

1

Flip-Flops Full Adders -

961

Adders

32-bit

1

-

32

Registers

31-bit

4

124

Total

124

[7] [8]

983 [9]

TABLE IX.

CALCULATION OF AREA BASED ON SYNTHESIS RESULTS FOR MODULUS 31 BIT (PROPOSE DESIGN) [10]

Circuits

Bit Size

Counts

Flip-Flops

Full Adders

Multipliers

31x3-bit

1

-

93

Adders

32-bit

1

-

32

Registers

31-bit

2

64

-

3-bit

1

3

-

2-bit

1

Total

2

-

69

125

The propose design is derivate from the habit of input data, it might be vary based on LCG application. For sure, one thing that can be learned from the design is there are space to efficient area and improve the speed whatever application it is.

[11]

[12]

[13]

[14]

[15]

[16]

IV. CONCLUSIONS An improve design and implementation of linear congruential generator into FPGA have been done successfully. It is assumed that the design circuit is used for specific applications. In general, the propose design circuit is far faster and less the use flip-flop and full adder. In term of slices and LUTs based on FPGA synthesis, the propose design require more than the design published in [13]. It can be justified, the previous one used equal word lengths while the propose circuit implement multi word lengths. Therefore, the number of slices and LUTs increase for the propose design. REFERENCES [1] [2]

[3]

[4]

D. H. Lehmer, “Random number generation on the BRL high speed computing machines,” by M. L. Juncosa. Math. Rev. 15 (1954), 559 http://en.wikipedia.org (2014) - Linear congruential generator, 10th March http://en.wikipedia.org/wiki/Linear_congruential_generator S. K. Park, and K. W. Miller, “Random number generators: good ones are hard to finnd,” Association for Computing Machinery, 31(10), pp: 1192-2001, 1988. Numerical Computing with MATLAB, By Cleve B. Moler, SIAM,2008

http://en.wikipedia.org (2014) - List of random number generators, 11th March http://en.wikipedia.org/wiki/List_of_random_number_generators N. Harald, “Random Number Generation and Quasi-Monte Carlo Methods,” Society for lndustrial and Applied Mathematics, Philadelphia, 1992. A note on random number generation, Christophe Dutang and Diethelm Wuertz, September 2009 Wolfram Mathematica ® Tutorial Collection, RANDOM NUMBER GENERATION, 2008 http://www.letech.jpn.com (2014) - Genuine Random Number Generator (GRANG), 10th March http://www.letech.jpn.com/rng/about_rng_e.html http://en.wikipedia.org (2014) - Comparison of hardware random number generators, 10th March http://en.wikipedia.org/wiki/Comparison_of_hardware_random_num ber_generators Zulfikar, “Generating Non Uniform Random Numbers Using Residue and Rejection Methods,” Transaction of Journal Rekayasa Elektrika, Vol. 8 No. 2, October 2009 Zulfikar, “FPGA Implementations of Uniform Random Number based on Residue Method,” Transaction of Journal Rekayasa Elektrika, Vol. 11 No. 1, April 2014 Zulfikar and Hubbul Walidaiy, “Design of Linear Congruential Generator based on Wordlengths Reduction Technique into FPGA,” Transaction of International Journal of Electronics Communication Computer Engineering, Vol. 5 No. 4, pp: 809-813, July 2014 D. E. Knuth, “The Art of Computer Programming: seminumerical algorithms,” Vol. 2,3rd edition edn, Massachusetts: Addison-Wesley, 2002 F. Severance, “System Modeling and Simulation,” John Wiley & Sons, Ltd. p. 86, 2001 Zulfikar, Abbasi, S A and Alamoud A R M, “FPGA Based Complete Set of Walsh and Inverse Walsh Transforms for Signal Processing,” Transaction of Electronics and Electrical Engineering Journal, Vol.18. No. 8, Pp: 3-8, October 2012.

Zulfikar was born in Beureunuen, Aceh, Indonesia, in 1975. He received his B.Sc. degree in Electrical Engineering from North Sumatera University, Medan, Indonesia, the M. Sc. Degree in Electrical Engineering from King Saud University, Riyadh, Saudi Arabia, in 1999 and 2011, respectively. He joined as teaching staff in the Department of Electronics at Politeknik Caltex Riau, Pekanbaru, Indonesia in 2003. He served as head of Industrial Control Laboratory, Politeknik Caltex Riau from 2003 to 2006. In 2006, he joined the Electrical Engineering Department, Syiah Kuala University. His current position is head of Digital Laboratory, and his current research interests include VLSI design and System on Chips (SoC).

Hubbul Walidainy was born in Banda Aceh, Aceh, Indonesia, in 1973. He graduated from Electrical Engineering Department at Gadjah Mada University, Yogyakarta, Indonesia, in 1998. The Master Degree in Electrical Engineering from Gadjah Mada University, Yogyakarta, Indonesia, in 2003. He joined in the Department of Electrical Engineering, Syiah Kuala University, Aceh, Indonesia in 2000, as a teaching staff. His current position is the head of Telecommunication Laboratory.

LAPORAN TAHUNAN PENELITIAN HIBAH BERSAING

Recommend Documents