MAKALAH PENGANTAR KOMPUTASI MODERN
MATERI ALGORITMA SHOR, ARSITEKTUR PARALEL KOMPUTER, PARALLELISM CONCEPT,
PENGOPERASIAN QUBIT
DISUSUN OLEH
:
1. ERVANNA
53414646
2. GALANG
MAHARDIKA
54414427
3. REZA RIZKI
PRADANA
59414187
4. YAN SEN
5C414347
KELAS :
4IA23
UNIVERSITAS
GUNADARMA
MATAKULIAH :
PENGANTAR KOMPUTASI MODERN
DOSEN : LELY
PRANANINGRUM
QUANTUM
BIT
(Yan Sen)
Pada komputasi quantum, ada
keterhubungan dengan biner. Pada pc dan komputasi quantum sama-sama
menggunakan bahasa komputer yang disebut biner. Biner adalah basis 2 dalam
bahasa matematika karena hanya terdiri dari dua digit, yaitu 1 dan 0. Dalam
komputasi kuantum unit dasar dari informasi adalah qubit (quantum bit). Qubit
membentuk dasar dari komputasi kuantum. Qubit dalam komputasi quantum berbeda
dari biner yang biasa di gunakan pada pc lama. Misalkan, Dalam komputer klasik
mengatakan memiliki dua bit. Kedua bit bisa terdiri dari satu dari kombinasi
berikut: 00/01/10/11. Dalam komputasi kuantum, dua qubit juga dapat
terdiri dari satu dari keempat kombinasi tersebut di atas yang disebut state
bagian dasar komputasi. Sementara sepasang klasik bit dapat menyimpan nomor ini
hanya satu per satu, sepasang qubit juga bisa eksis dalam superposisi dari
dasar empat state atau antara 0 dan 1. Ini berarti bahwa sepasang qubit secara
simultan dapat terdiri dari semua empat state yang mungkin atau kombinasi (00,
01, 10, 11). Dengan demikian, qubit dapat berisi sejumlah besar informasi dan
hasil ini dalam komputer kuantum yang secara eksponensial lebih kuat daripada komputer
klasik (non-kuantum). Ada empat perangkat kontrol yang dapat digunakan untuk
membuat qubit:
1. Perangkap
ion
2. Titik-titik
kuantum
3. Semiconductor
impurities
4. Sirkuit
superkonduktor
Pengoperasian
pada Data Qubits adalah dengan kedua nilai yang disimpan pada setiap qubit akan
selalu mempengaruhi operasi komputer kuantum. Selain itu, sebuah n qubits
sama-sama ber-superposisi dari 0 dan 1, dia berperan untuk mengkodekan 2n
nilai. Komputer kuantum dapat menghitung nilai keseluruhannya sekaligus.
Keadaan paralel ini memiliki istilah Paralelisme Kuantum. Setiap rangkaian yang
tercipta selalu memiliki rangkaian kuantum yang sesuai. Jadi dapat disimpulkan
bahwa teknologi yang diterapkan pada komputer kuantum mampu melakukan
perhitungan pada semua nilai pada waktu yang hampir sama, dengan waktu yang
sama komputer konvensional hanya bisa melakukan perhitungan tunggal.
ALGORITMA SHOR
(Ervanna)
Algoritma Shor adalah algoritma
yang berjalan pada komputer kuantum yang berguna untuk faktorisasi bilangan
bulat. Inti dari algoritma ini merupakan bagaimana cara menyelesaikan
faktorisasi terhaadap bilangan interger
atau bulat yang besar. Algoritma ini ditemukan oleh Peter Shor pada tahun 1995.
Efisiensi algoritma Shor adalah efisiensi kuantum
Transformasi Fourier, dan modular eksponensial. Jika sebuah komputer kuantum
dengan jumlah yang qubit memadai
dapat beroperasi tanpa mengalah kebisingan dan fenomena interferensi kuantum
lainnya, algoritma Shor dapat digunakan untuk memecahkan kriptografi kunci
publik skema seperti banyak digunakan skema RSA. Dengan menggunakan algoritma
ini, sebuah komputer kuantum dapat memecahkan sebuah kode rahasia yang saat ini
secara umum digunakan untuk mengamankan pengiriman data. Kode yang disebut kode
RSA ini, jika disandikan melalui kode RSA, data yang dikirimkan akan aman
karena kode RSA tidak dapat dipecahkan dalam waktu yang singkat. Selain itu,
pemecahan kode RSA membutuhkan kerja ribuan komputer secara paralel sehingga
kerja pemecahan ini tidaklah efektif.
Algoritma Shor bergantung pada hasil dari teori
bilangan. Hasil ini adalah: fungsi periodik. Dalam konteks algoritma Shor, n
akan menjadi bilangan yang akan difaktorkan. Jika dua bilangan tersebut adalah
coprime itu berarti bahwa pembagi umumnya adalah 1. Perhitungan fungsi ini
untuk jumlah eksponensial, dari itu akan mengambil waktu eksponensial pada
komputer klasik. Algoritma Shor memanfaatkan paralelisme kuantum untuk
melakukan jumlah eksponensial operasi dalam satu langkah.
Hambatan runtime dari algoritma
Shor adalah kuantum eksponensial modular yang jauh lebih lambat dibandingkan
dengan kuantum Transformasi Fourier dan pre-/post-processing klasik. Ada
beberapa pendekatan untuk membangun dan mengoptimalkan sirkuit untuk eksponensial
modular. Yang paling sederhana dan saat ini yaitu pendekatan paling praktis
adalah dengan menggunakan meniru sirkuit aritmatika konvensional dengan gerbang
reversibel, dimulai dengan penambah ripple-carry. Sirkuit Reversible biasanya
menggunakan nilai pada urutan n ^ 3, gerbang untuk n qubit. Teknik alternatif
asimtotik meningkatkan jumlah gerbang dengan menggunakan kuantum transformasi
Fourier, tetapi tidak kompetitif dengan kurang dari 600 qubit karena konstanta
tinggi.
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.
PARALLELISM
CONCEPT
(Reza Rizki
Pradana)
Parallel
Computation merupakan kemampuan
menjalankan tugas atau aplikasi lebih dari satu dan dijalankan secara bersamaan
pada sebuah komputer. Secara umum, ini adalah sebuah teknik dimana sebuah
masalah dibagi dalam beberapa masalah kecil untuk mempercepat proses
penyelesaian masalah.
Teknologi komputasi paralel sudah berkembang lebih dari dua dekade, penggunaannya
semakin beragam mulai dari kebutuhan perhitungan di laboratorium fisika nuklir,
simulasi pesawat luar angkasa, hingga prakiraan cuaca. Secara prinsip komputer
paralel membagi permasalahan sehingga menjadi lebih kecil untuk dikerjakan oleh
setiap prosesor (CPU) dalam waktu yang bersamaan/simultan (concurrent). Prinsip ini disebut paralelisme.
Paralellism
Concept merupakan sub bagian dari
Parallel Computation yang di fokuskan dalam pembahasan konsep yang digunakan
dalam membentuk komputasi paralel. Terdapat 2 hukum dalam paralell computation,
yaitu :
a. Hukum Amdahl
Amdahl berpendapat, “Peningkatan kecepatan secara paralel akan
menjadi linear, melipatgandakan kemampuan proses sebuah komputer dan mengurangi
separuh dari waktu proses yang diperlukan untuk menyelesaikan sebuah masalah”.
b. Hukum Gustafson
Pendapat yang dikemukakan Gustafson hampir sama dengan Amdahl, tetapi
dalam pemikiran Gustafson, sebuah komputasi paralel berjalan dengan menggunakan
2 atau lebih mesin untuk mempercepat penyelesaian masalah dengan memperhatikan
faktor eksternal, seperti kemampuan mesin dan kecepatan proses tiap – tiap
mesin yang digunakan.
Paralelisme dalam komputasi paralel merupakan hal yang diciptakan dan
dimanfaatkan. Inti dari Parallelism Concept atau lebih umum disebut dengan
Konsep Paralelisme adalah pemrosesan yang dilakukan secara paralel pada
prosesor. Pada prakteknya, komputasi paralel memanfaatkan beberapa CPU untuk
memproses operasi pada perangkat lunak tertentu. Beberapa perangkat lunak
bekerja sangat lambat ketika ditangani oleh satu CPU karena operasinya yang
rumit atau prosesnya yang banyak. Prosesor dengan satu CPU seperti ini disebut
dengan single-core. Seiring berkembangnya penerapan ilmu paralel, prosesor
modern mulai menerapkan multi-core, dimana sebuah prosesor memiliki lebih dari
satu CPU, sehingga dapat memproses operasi lebih cepat.
Gambar diatas merupakan sebuah ilustrasi dari komputasi paralel, dimana
terdapat beberapa masalah yang dibagi kedalam beberapa bagian agar masalah
tersebut dapat diatasi dengan cepat. Pada gambar tersebut terdapat beberapa CPU
(Central Processing Unit) yg memproses
beberapa masalah secara bersamaan.
ARSITEKTUR KOMPUTER PARALEL
(Galang Mahardika)
Arsitektur Komputer Paralel adalah sekumpulan elemen pemroses
(Processing Elements) yang bekerjasama dalam menyelesaikan sebuah masalah
besar. Arsitektur paralel diperlukan karena :
·
Tuntutan aplikasi
·
Trend Teknolog
·
Trend Arsitekture
·
Ekonomi
Trend saat ini :
· Kebanyakan mikroprosesor sekarang ini mempunyai fasilitas untuk
mendukung multiprosesor.
· Server dan workstation berarsitektur multiprosesor : Sun, SGI, DEC,
COMPAQ
· Mikroprosesor yad (dan sekarang) adalah multiprosesor
Untuk melakukan berbagai jenis komputasi paralel diperlukan
infrastruktur mesin paralel yang terdiri dari banyak komputer yang dihubungkan
dengan jaringan dan mampu bekerja secara paralel untuk menyelesaikan satu
masalah. Untuk digunakan perangkat lunak pendukung yang biasa disebut
middleware yang berperan mengatur distribusi antar titik dalam satu mesin paralel.
Selanjutnya pemakai harus membuat pemrograman paralel untuk merealisasikan
komputasi.
Yang perlu diingat adalah komputasi paralel berbeda dengan multitasking.
Pengertian multitasking adalah komputer dengan processor tunggal mengeksekusi
beberapa tugas secara bersamaan. Walaupun beberapa orang yang bergelut di
bidang sistem operasi beranggapan bahwa komputer tunggal tidak bisa melakukan
beberapa pekerjaan sekaligus, melainkan proses penjadwalan yang berlakukan pada
sistem operasi membuat komputer seperti mengerjakan tugas secara bersamaan.
Sedangkan komputasi paralel sudah dijelaskan sebelumnya, bahwa komputasi
paralel menggunakan beberapa processor atau komputer. Selain itu komputasi
paralel tidak menggunakan arsitektur Von Neumann.
Untuk lebih memperjelas lebih dalam mengenai perbedaan komputasi tunggal
(menggunakan 1 processor) dengan komputasi paralel (menggunakan beberapa
processor), maka kita harus mengetahui terlebih dahulu pengertian mengenai
model dari komputasi. Ada 4 model komputasi yang digunakan, yaitu:
- SISD
- SIMD
- MISD
- MIMD
1.
SISD
Yang merupakan singkatan dari Single Instruction, Single Data adalah
satu-satunya yang menggunakan arsitektur Von Neumann. Ini dikarenakan pada
model ini hanya digunakan 1 processor saja. Oleh karena itu model ini bisa
dikatakan sebagai model untuk komputasi tunggal. Sedangkan ketiga model lainnya
merupakan komputasi paralel yang menggunakan beberapa processor. Beberapa
contoh komputer yang menggunakan model SISD adalah UNIVAC1, IBM 360, CDC 7600,
Cray 1 dan PDP 1.
2.
SIMD
Yang merupakan singkatan dari Single Instruction, Multiple Data. SIMD
menggunakan banyak processor dengan instruksi yang sama, namun setiap processor
mengolah data yang berbeda. Sebagai contoh kita ingin mencari angka 27 pada
deretan angka yang terdiri dari 100 angka, dan kita menggunakan 5 processor.
Pada setiap processor kita menggunakan algoritma atau perintah yang sama, namun
data yang diproses berbeda. Misalnya processor 1 mengolah data dari deretan /
urutan pertama hingga urutan ke 20, processor 2 mengolah data dari urutan 21
sampai urutan 40, begitu pun untuk processor-processor yang lain. 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).
3.
MISD
Yang merupakan singkatan dari Multiple Instruction, Single Data. MISD
menggunakan banyak processor dengan setiap processor menggunakan instruksi yang
berbeda namun mengolah data yang sama. Hal ini merupakan kebalikan dari model
SIMD. Untuk contoh, kita bisa menggunakan kasus yang sama pada contoh model
SIMD namun cara penyelesaian yang berbeda. Pada MISD jika pada komputer
pertama, kedua, ketiga, keempat dan kelima sama-sama mengolah data dari urutan
1-100, namun algoritma yang digunakan untuk teknik pencariannya berbeda di
setiap processor. Sampai saat ini belum ada komputer yang menggunakan model
MISD.
4.
MIMD
Yang merupakan singkatan dari Multiple Instruction, Multiple Data. MIMD
menggunakan banyak processor dengan setiap processor memiliki instruksi yang
berbeda dan mengolah data yang berbeda. Namun banyak komputer yang menggunakan
model MIMD juga memasukkan komponen untuk model SIMD. Beberapa komputer yang
menggunakan model MIMD adalah IBM POWER5, HP/Compaq AlphaServer, Intel IA32,
AMD Opteron, Cray XT3 dan IBM BG/L.
REFERENSI :
Tidak ada komentar:
Posting Komentar