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
Penulisan
Penulisan
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.
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 :
Tidak ada komentar:
Posting Komentar