Pararel Computation & Algoritma Shor

Nama Kelompok :         1. Alicia Oksiany

                                      2. Maghfira Zahra Sani

                                      3. Regita Indah .D.

                                      4. Safira

Kelas                           : 4IA20

Dosen                          : Lely Prananingrum

Mata Kuliah                 : Pengantar Komputasi Modern  

Parallel Computation

A. Parallelism Concept

Komputasi paralel didefinisikan sebagai penggunaan sekumpulan sumberdaya komputer secara simultan untuk menyelesaikan permasalahan komputasi. Secara prinsip komputer paralel membagi permasalahan sehingga menjadi lebih kecil untuk dikerjakan oleh setiap prosesor / CPU dalam waktu yang bersamaan/simultan / concurrent dan prinsip ini disebut paralelisme. Konsep program parallel :

–  Memerintahkan set instruksi (pandangan programmer).

–  File executable (pandangan sistem operasi)

Pada dasarnya, konsep parallel system merupakan suatu bentuk penawaran solusi dari proses computing yang terlalu berat, sehingga dapat dipecah sedemikian hingga tidak memberatkan system kerja komputer itu sendiri

Berdasarkan tingkat paralelismenya prosesor paralel dapat dibagi menjadi beberapa tingkat(level) sebagai berikut :

1. Komputer Array.

2. Prosesor array : beberapa prosesor yang bekerja sama untuk mengolah set instruksi yang sama dan data yang berbeda – beda atau biasa disebut SIMD (Single Instruction-stream Multiple Data)

3. Prosesor vektor : beberapa prosesor yang disusun seperti pipeline.

4. Multiprosesor, yaitu sebuah sistem yang memiliki 2 prosesor atau lebih yang saling berbagi memori.

5. Multikomputer, yaitu sebuah sistem yang memiliki 2 prosesor atau lebih yang masing-masing prosesor memiliki memori sendiri.

B. Distributed Processing

Yang dimaksud Distribusi Processing adalah mengerjakan semua proses pengolahan data secara bersama antara komputer pusat dengan beberapa komputer yang lebih kecil dan saling dihubungkan melalui jalur komunikasi. Setiap komputer tersebut memiliki prosesor mandiri sehingga mampu mengolah sebagian data secara terpisah, kemudian hasil pengolahan tadi digabungkan menjadi satu penyelesaian total. Jika salah satu prosesor mengalami kegagalan atau masalah yang lain akan mengambil alih tugasnya.

Contoh dari Distributed Data Processing System adalah: ATM, komputer yang dirancang untuk tugas-tugas melaksanakan proyek, analisis finansial, penjadwalan waktu dan akuntansi. Contoh lainnya, pengolahan data pada server yahoo yang tersebar hampir di seluruh dunia secara distribusi, setiap wilayah mempunyai server masing-masing. Seperti di indonesia mempunyai server tersendiri sehingga pengolahan data tidak di pusat melainkan di wilayah masing-masing.

C. Architectual Parallel Computer

Komputasi paralel adalah salah satu teknik melakukan komputasi secara bersamaan dengan memanfaatkan beberapa komputer secara bersamaan. Biasanya diperlukan saat kapasitas yang diperlukan sangat besar, baik karena harus mengolah data dalam jumlah besar ataupun karena tuntutan proses komputasi yang banyak. Untuk melakukan aneka jenis komputasi paralel ini diperlukan infrastruktur mesin paralel yang terdiri dari banyak komputer yang dihubungkan dengan jaringan dan mampu bekerja secara paralel untuk menyelesaikan satu masalah. Untuk itu diperlukan aneka perangkat lunak pendukung yang biasa disebut sebagai middleware yang berperan untuk mengatur distribusi pekerjaan antar node dalam satu mesin paralel. Selanjutnya pemakai harus membuat pemrograman paralel untuk merealisasikan komputasi.

Arsitektur paralel komputer menurut Klasifikasi Flynn’s:

• SISD

Single Instruction – Single Data. Komputer ini memiliki hanya satu prosesor dan satu instruksi yang dieksekusi secara serial. Komputer ini adalah tipe komputer konvensional. Menurut mereka tipe komputer ini tidak ada dalam praktik komputer paralel karena bahkan mainframe pun tidak lagi menggunakan satu prosesor. Klasifikasi ini sekedar untuk melengkapi definisi komputer paralel. Beberapa contoh komputer yang menggunakan model SISD adalah UNIVAC1, IBM 360, CDC 7600, Cray 1 dan PDP 1.

• SIMD

Single Instruction – Multiple Data. Komputer ini memiliki lebih dari satu prosesor, tetapi hanya mengeksekusi satu instruksi secara paralel pada data yang berbeda pada level lock-step. Komputer vektor adalah salah satu komputer paralel yang menggunakan arsitektur ini. Beberapa contoh komputer yang menggunakan model SIMD adalah ILLIAC IV, MasPar, Cray X-MP, Cray Y-MP, Thingking Machine CM-2 dan Cell Processor (GPU).

• MISD

Multiple Instructions – Single Data. Teorinya komputer ini memiliki satu prosesor dan mengeksekusi beberapa instruksi secara paralel tetapi praktiknya tidak ada komputer yang dibangun dengan arsitektur ini karena sistemnya tidak mudah dipahami. Sampai saat ini belum ada komputer yang menggunakan model MISD.

• MIMD

Multiple Instructions – Multiple Data. Komputer ini memiliki lebih dari satu prosesor dan mengeksekusi lebih dari satu instruksi secara paralel. Tipe komputer ini yang paling banyak digunakan untuk membangun komputer paralel, bahkan banyak supercomputer yang menerapkan arsitektur ini. Beberapa komputer yang menggunakan model MIMD adalah IBM POWER5, HP/Compaq AlphaServer, Intel IA32, AMD Opteron, Cray XT3 dan IBM BG/L.

Sistem komputer paralel dibedakan dari cara kerja memorinya menjadi shared memory dan distributed memory. Shared memory berarti memori tunggal diakses oleh satu atau lebih prosesor untuk menjalankan instruksi sedangkan distributed memory berarti setiap prosesor memiliki memori sendiri untuk menjalankan instruksi.

D. Pengantar Thread Programming

Threading / Thread adalah sebuah alur kontrol dari sebuah proses. Konsep threading adalah menjalankan 2 proses ( proses yang sama atau proses yang berbeda ) dalam satu waktu. Contohnya sebuah web browser mempunyai thread untuk menampilkan gambar atau tulisan sedangkan thread yang lain berfungsi sebagai penerima data dari network. Threading dibagi menjadi 2 :

• Static Threading

Teknik ini biasa digunakan untuk komputer dengan chip multiprocessors dan jenis komputer shared-memory lainnya. Teknik ini memungkinkan thread berbagi memori yang tersedia, menggunakan program counter dan mengeksekusi program secara independen. Sistem operasi menempatkan satu thread pada prosesor dan menukarnya dengan thread lain yang hendak menggunakan prosesor itu.

• Dynamic Multithreading

Teknik ini merupakan pengembangan dari teknik sebelumnya yang bertujuan untuk kemudahan karena dengannya programmer tidak harus pusing dengan protokol komunikasi, load balancing, dan kerumitan lain yang ada pada static threading. Concurrency platform ini menyediakan scheduler yang melakukan load balacing secara otomatis. Walaupun platformnya masih dalam pengembangan namun secara umum mendukung dua fitur : nested parallelism dan parallel loops.

E. Algoritma Shor

Pada tahun 1994 Peter Shor (Bell Laboratories) menemukan algoritma kuantum pertama yang secara prinsip dapat melakukan faktorisasi yang efisien. Hal ini menjadi sebuah aplikasi kompleks yang hanya dapat dilakukan oleh sebuah komputer kuantum. Pemfakotiran adalah salah satu masalah yang paling penting dalam kriptografi. Misalnya, keamanan RSA (sistem keamanan perbankan elektronik) - kriptografi kunci publik - tergantung pada pemfaktoran dan hal itu akan menjadi masalah yang besar. Karena banyak fitur yang bermanfaat dari komputer kuantum, para ilmuwan berupaya lebih untuk membangunnya. Apabila, pemecahan segala jenis enkripsi saat ini memerlukan waktu hampir seabad pada komputer yang ada, mungkin hanya memakan waktu beberapa tahun pada komputer kuantum

Algoritma Shor adalah contoh lanjutan paradigma dasar (berapa banyak waktu komputasi diperlukan untuk menemukan faktor bilangan bulat n-bit?), tapi algoritma ini tampak terisolir dari kebanyakan temuan lain ilmu informasi quantum. Sekilas, itu cuma seperti trik pemrograman cerdik dengan signifikansi fundamental yang kecil. Penampilan tersebut menipu; para periset telah menunjukkan bahwa algoritma Shor bisa ditafsirkan sebagai contoh prosedur untuk menetapkan level energi sistem quantum, sebuah proses yang fundamental. Seiring waktu berjalan dan kita mengisi lebih banyak pada peta, semestinya kian mudah memahami prinsip-prinsip yang mendasari algortima Shor dan algoritma quantum lainnya dan, kita harap, mengembangkan algoritma baru.

Sebagai contoh  Algoritma Shor yang paling sederhana adalah menemukan faktor-faktor untuk  bilangan  15,  di mana membutuhkan sebuah komputer kuantum dengan tujuh qubit.  Para  ahli  kimia mendesain dan menciptakan sebuah molekul yang memiliki tujuh putaran nukleus. Nukleus dari lima atom fluorin dan dua atom karbon yang dapat berinteraksi satu dengan yang lain sebagai qubit, dapat diprogram dengan menggunakan denyut-denyut  frekuensi radio dan dapat dideteksi melalui peralatan resonansi  magnetis nuklir (nuclear magnetic resonance, atau NMR) yang mirip dengan yang banyak digunakan di rumah-rumah sakit dan laboratorium-laboratorium kimia.

Langkah langkah algoritma shor 

Masalah yang hendak dipecahkan adalah: Diketahui sebuah bilangan komposit N, dicari sebuah bilangan bulat x dengan x bernilai 1 < x < N. .

1. Algoritma Shor untuk mencari faktor dari bilangan bulat n, dapat dipecah menjadi langkah-langkah berikut: Menentukan apakan N adalah prima, genap, atau perpangkatan dari bilangan prima. Jika ya, maka Algoritma Shor tidak akan dipakai. Terdapat algoritma konvensional yang efisien untuk menentukan jenis n dan memfaktorkannya. Langkah ini akan dilakukan di komputer konvensional.

 2. Ambil bilangan bulat q, dimana q adalah nilai dari perpangkatan 2 yang memenuhi: n2 ≤ q < 2n2 . Langkah ini akan dilakukan di komputer konvensional.

3. Mencari bilangan bulat random x yang relatif prima dengan n. Terdapat algoritma konvensional yang efisien untuk proses ini. Langkah ini akan dilakukan di komputer konvensional.

4. Membuat quantum register yang dipartisi menjadi dua bagian, katakan register 1 dan register 2. Register satu harus cukup besar untuk merepresentasikan bilangan bulat sebesar q-1, sedangkan register 2 sebesar n-1. Langkah ini perlu dilakukan di komputer quantum.

5. Masukkan kedalam register 1 superposisi yang setara dari semua bilangan bulat 0 sampai q-1, dan register 2 bilangan bulat 0. Langkah ini dapat dilaksanakan dengan menggunakan hadamard gates. Langkah ini perlu dilakukan di komputer quantum. Pada langkah ini, state dari quantum memory register adalah: ∑ − = 1 0 | ,0 1 q a a q

6. Aplikasikan fungsi x n a mod ke dalam semua bilangan bulat di dalam register 1, dan menyimpan hailnya di register 2. Karena prinsip pararellisme quantum, proses ini hanya perlu dilakukan sekali saja. Langkah ini perlu dilakukan di komputer quantum. Pada langkah ini, state dari quantum memory register adalah: ∑ − = 1 0 | , mod 1 q a a a x n q

7. Mengukur dan memeriksa nilai yang disimpan pada register 2, mendapatkan nilai k. Langkah ini perlu dilakukan di komputer quantum. Langkah ini akan membuat register 1 semua superposisi state a dimana x n k a mod ≠ “kolaps”. Setelah langkah ini, state dari quantum memory register adalah: ∑= ∈ 〉 a a A a k A ' ' | ', || || 1 Dengan A adalah himpunan dari a’ dimana x n k a mod = , dan ||A|| adalah jumlah elemen dalam himpunan tersebut.

8. Menghitung transformasi quantum Fourier pada register 1. Langkah ini perlu dilakukan di komputer quantum.

 9. Ukur nilai state register satu, katakan nilai ini sebagai m. Bilangan bulat m memiliki probabilitas tinggi adalah kelipatan q/r, dimana r adalah periode yang kita cari. Langkah ini perlu dilakukan di komputer quantum.

10. Gunakan nilai m untuk mencari nilai r, dengan nilai m dan q diketahui. Jika r tidak dapat ditentukan, maka kembali ke langkah 4. Langkah ini akan dilakukan di komputer konvensional.

11. Setelah r diketahui, faktor n dapat ditentukan dengan menghitung gcd(xr/2 + 1, n) dan gcd(xr/2-1,n). Disaat ini faktor n telah ditemukan, dan Algoritma telah selesai. Langkah ini akan dilakukan di komputer konvensional.[6]

Kelemahan dan kelebihan

Berbeda dengan komputer konvensional yang deterministik, komputer quantum bersifat nondeterministik dan probabilistik, yang berarti suatu algoritma kadang kala dapat berhasil dan kadang kala akan gagal biarpun untuk kondisi yang sama. Hal ini dikarena sifat pengukuran dalam mekanika quantum yang probabilistik. Akibatnya, Algoritma Shor dapat gagal menemukan faktor karena beberapa sebab, diantaranya:

• Hasil pengukuran dari transformasi quantum fourier dapat berupa 0, membuat langka ke 10 tak mungkin dilakukan.

• Kadang hasil faktorisasi algoritma akan menghasilkan 1 dan n, yang secara definisi benar tetapi tidak berguna

• Bila hasil r ganjil, maka langkah ke 10 tidak dapat dilakukan Walaupun begitu, probabilitas sukses akan bertambah setiap kali algoritma diulang. Dalam Algoritma Shor yang dimodifikasi dengan penentuan order, probabilitas sukses setelah 2 kali jalan lebih dari 60%, dan probabilitas sukses setelah 4 kali jalan lebih dari 90%.[2]

Maka walaupun perlu berjalan untuk waktu yang tak ditentukan, waktu tersebut adalah polinomial. Lebih tepatnya, Algoritma Shor berjalan dengan kecepatan O((log n)2 *log log n) pada komputer quantum, dan harus melakukan paska prosesing selama O(log n) pada komputer konvensional. Secara utuh algoritma ini polinomial.

Sumber :

https://krustybrain.wordpress.com/2013/05/25/tugas-4-softskill-pengantar-komputasi-modern-sem-8/

https://muhammadadly.wordpress.com/2016/05/10/parallel-computation/