Tugas 1 - Pengantar Komputasi Modern

6:10 AM


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:
  1. SISD
  2. SIMD
  3. MISD
  4. 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.







Share This Story

Tags: ,

You Might Also Like

0 comments

Give your comment here

Translate