Selasa, 28 Juli 2015

Quantum Computation dan Pararel Computation


 
A. QUANTUM COMPUTING
Pengertian  Quantum Computing
Merupakan alat hitung yang menggunakan mekanika kuantum seperti superposisi dan keterkaitan, yang digunakan untuk peng-operasi-an data. Perhitungan jumlah data pada komputasi klasik dihitung dengan bit, sedangkan perhitungan jumlah data pada komputer kuantum dilakukan dengan qubit. Prinsip dasar komputer kuantum adalah bahwa sifat kuantum dari partikel dapat digunakan untuk mewakili data dan struktur data, dan bahwa mekanika kuantum dapat digunakan untuk melakukan operasi dengan data ini. Dalam hal ini untuk mengembangkan komputer dengan sistem kuantum diperlukan suatu logika baru yang sesuai dengan prinsip kuantum.
Sejarah singkat
  • Pada tahun 1970-an pencetusan atau ide tentang komputer kuantum pertama kali muncul oleh para fisikawan dan ilmuwan komputer, seperti Charles H. Bennett dari IBM, Paul A. Benioff dari Argonne National Laboratory, Illinois, David Deutsch dari University of Oxford, dan Richard P. Feynman dari California Institute of Technology (Caltech).
  • Feynman dari California Institute of Technology yang pertama kali mengajukan dan menunjukkan model bahwa sebuah sistem kuantum dapat digunakan untuk melakukan komputasi. Feynman juga menunjukkan bagaimana sistem tersebut dapat menjadi simulator bagi fisika kuantum.
  • Pada tahun 1985, Deutsch menyadari esensi dari komputasi oleh sebuah komputer kuantum dan menunjukkan bahwa semua proses fisika, secara prinsipil, dapat dimodelkan melalui komputer kuantum. Dengan demikian, komputer kuantum memiliki kemampuan yang melebihi komputer klasik.
  • Pada tahun 1995, Peter Shor merumuskan sebuah algoritma yang memungkinkan penggunaan komputer kuantum untuk memecahkan masalah faktorisasi dalam teori bilangan.
  • Sampai saat ini, riset dan eksperimen pada bidang komputer kuantum masih terus dilakukan di seluruh dunia. Berbagai metode dikembangkan untuk memungkinkan terwujudnya sebuah komputer yang memilki kemampuan yang luar biasa ini. Sejauh ini, sebuah komputer kuantum yang telah dibangun hanya dapat mencapai kemampuan untuk memfaktorkan dua digit bilangan. Komputer kuantum ini dibangun pada tahun 1998 di Los Alamos, Amerika Serikat, menggunakan NMR (Nuclear Magnetic Resonance).
B. Entanglement
Entanglement adalah efek mekanik kuantum yang mengaburkan jarak antara partikel individual sehingga sulit menggambarkan partikel tersebut terpisah meski Anda berusaha memindahkan mereka. Contoh dari quantum entanglement: kaitan antara penentuan jam sholat dan quantum entanglement. Mohon maaf bagi yang beragama lain saya hanya bermaksud memberi contoh saja. Mengapa jam sholat dibuat seragam? Karena dengan demikian secara massal banyak manusia di beberapa wilayah secara serentak masuk ke zona entanglement bersamaan.

C. Pengoperasian Data Qubit
Komputer kuantum memelihara urutan qubit. Sebuah qubit tunggal dapat mewakili satu, nol, atau, penting, setiap superposisi quantum ini, apalagi sepasang qubit dapat dalam superposisi kuantum dari 4 negara, dan tiga qubit dalam superposisi dari 8. Secara umum komputer kuantum dengan qubit n bisa dalam superposisi sewenang-wenang hingga 2 n negara bagian yang berbeda secara bersamaan (ini dibandingkan dengan komputer normal yang hanya dapat di salah satu negara n 2 pada satu waktu). Komputer kuantum yang beroperasi dengan memanipulasi qubit dengan urutan tetap gerbang logika quantum. Urutan gerbang untuk diterapkan disebut algoritma quantum.
Sebuah contoh dari implementasi qubit untuk komputer kuantum bisa mulai dengan menggunakan partikel dengan dua putaran menyatakan: “down” dan “up”. Namun pada kenyataannya sistem yang memiliki suatu diamati dalam jumlah yang akan kekal dalam waktu evolusi dan seperti bahwa A memiliki setidaknya dua diskrit dan cukup spasi berturut-turut eigen nilai , adalah kandidat yang cocok untuk menerapkan sebuah qubit. Hal ini benar karena setiap sistem tersebut dapat dipetakan ke yang efektif spin -1/2 sistem.
Algoritma pada Quantum Computing
Para ilmuwan mulai melakukan riset mengenai sistem kuantum tersebut, mereka juga berusaha untuk menemukan logika yang sesuai dengan sistem tersebut. Sampai saat ini telah dikemukaan dua algoritma baru yang bisa digunakan dalam sistem kuantum yaitu algoritma shor dan algoritma grover.
  • Algoritma Shor
Algoritma yang ditemukan oleh Peter Shor pada tahun 1995. 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 Grover
Algoritma Grover adalah sebuah algoritma kuantum yang menawarkan percepatan kuadrat dibandingkan pencarian linear klasik untuk list tak terurut. Algoritma Grover menggambarkan bahwa dengan menggunakan pencarian model kuantum, pencarian dapat dilakukan lebih cepat dari model komputasi klasik. Dari banyaknya algoritma kuantum, algoritma grover akan memberikan jawaban yang benar dengan probabilitas yang tinggi. Kemungkinan kegagalan dapat dikurangi dengan mengulangi algoritma. Algoritma Grover juga dapat digunakan untuk memperkirakan rata-rata dan mencari median dari serangkaian angka, dan untuk memecahkan masalah Collision.
Implementasi Quantum Computing
Pada 19 Nov 2013 Lockheed Martin, NASA dan Google semua memiliki satu misi yang sama yaitu mereka semua membuat komputer kuantum sendiri. Komputer kuantum ini adalah superkonduktor chip yang dirancang oleh sistem D – gelombang dan yang dibuat di NASA Jet Propulsion Laboratories.
NASA dan Google berbagi sebuah komputer kuantum untuk digunakan di Quantum Artificial Intelligence Lab menggunakan 512 qubit D -Wave Two yang akan digunakan untuk penelitian pembelajaran mesin yang membantu dalam menggunakan jaringan syaraf tiruan untuk mencari set data astronomi planet ekstrasurya dan untuk meningkatkan efisiensi searchs internet dengan menggunakan AI metaheuristik di search engine heuristical.
A.I. seperti metaheuristik dapat menyerupai masalah optimisasi global mirip dengan masalah klasik seperti pedagang keliling, koloni semut atau optimasi swarm, yang dapat menavigasi melalui database seperti labirin. Menggunakan partikel terjerat sebagai qubit, algoritma ini bisa dinavigasi jauh lebih cepat daripada komputer konvensional dan dengan lebih banyak variabel.
Penggunaan metaheuristik canggih pada fungsi heuristical lebih rendah dapat melihat simulasi komputer yang dapat memilih sub rutinitas tertentu pada komputer sendiri untuk memecahkan masalah dengan cara yang benar-benar cerdas . Dengan cara ini mesin akan jauh lebih mudah beradaptasi terhadap perubahan data indrawi dan akan mampu berfungsi dengan jauh lebih otomatisasi daripada yang mungkin dengan komputer normal

Quantum berlawanan dari fisika klasik dan semua intuisi kita. Engineering menghindari ilmu ini karena terlalu teoritis dan tidak bisa diaplikasi. Tapi ini mungkin adalah satu-satunya harapan untuk menghindari akhir dari kemajuan komputer. komputer. Meskipun kita selalu heran melihat model komputer baru muncul setiap bulan, secara teoritis ini ada ujungnya. Komputasi masa kini - komputer konvensional - dikerjakan oleh transistor, dan kecepatannya bergantung pada ukuran transistor. Kemajuan komputer yang sampai sekarang terjadi adalah karena transistor menjadi semakin kecil. Gordon Moore, co-founder dari Intel, pada tahun 60-an berkata, jumlah transistor per inchi persegi akan berlipat dua kali setiap tahun.
Suatu hari transistor itu bisa menjadi sebesar satu atom dan Richard Feynmann, fisikawan terhebat sejak Albert Einstein, berpendapat bahwa ini adalah ukuran transistor terkecil yang mungkin. Tentunya ini keberhasilan luar bisa untuk mencapai ukuran itu, namun apakah ini betul-betul akhir dari kemajuan komputer?
Tidak, dengan adanya Quantum Computer. Quantum Computer, berbeda dengan banyak istilah lain, memang memakai fenomena quantumyang tidak bisa ditiru komputer konvensional. Ini bukan pengembangan komputer biasa, melainkan konsep yang baru sama sekali.
Quantum Computer adalah alat hitung yang menggunakan sebuah fenomena mekanika kuantum, misalnya superposisi dan keterkaitan, untuk melakukan operasi data. Dalam komputasi klasik, jumlah data dihitung dengan bit; dalam komputer kuantum, hal ini dilakukan dengan qubit. Prinsip dasar komputer kuantum adalah bahwa sifat kuantum dari partikel dapat digunakan untuk mewakili data dan struktur data, dan bahwa mekanika kuantum dapat digunakan untuk melakukan operasi dengan data ini. Dalam hal ini untuk mengembangkan komputer dengan sistem kuantum diperlukan suatu logika baru yang sesuai dengan prinsip kuantum
Quantum Computer dapat memproses jauh lebih cepat daripada komputer konvensional. Pada dasarnya, quantum computer dapat memproses secara paralel, sehingga berkomputasi jauh lebih cepat.
Quantum Computer dapat jauh lebih cepat dari komputer konvensional pada banyak masalah, salah satunya yaitu masalah yang memiliki sifat berikut:
  1. Satu-satunya cara adalah menebak dan mengecek jawabannya berkali-kali
  2. Terdapat n jumlah jawaban yang mungkin
  3. Setiap kemungkinan jawaban membutuhkan waktu yang sama untuk mengeceknya
  4. Tidak ada petunjuk jawaban mana yang kemungkinan benarnya lebih besar: memberi jawaban dengan asal tidak berbeda dengan mengeceknya dengan urutan tertentu.

D. Quantum Gates
Tentang quantum gates dan algoritma shor , Algoritma Shor didasarkan dari sebuah teori bilangan: fungsi F(a) = xamod n adalah feungsi periodik jika x adalah bilangan bulat yang relatif prima dengan n. Dalam Algoritma Shor, n akan menjadi bilangan bulat yang hendak difaktorkan. Menghitung fungsi ini di komputer konvensional untuk jumlah yang eksponensial akan membutuhkan waktu eksponensial pula. Pada masalah ini algoritma quantum shor memanfaatkan pararellisme quantum untuk melakukannya hanya dengan satu langkah. Karena F(A) adalah fungsi periodik, maka fungsi ini memiliki sebuah periode r. Diketahui x0mod n = 1, maka xr mod n =1, begitu juga x2r mod n dan seterusnya.
dibawah ini adalah contoh gambar quantum computing :


Komputer Paralel

Komputasi Paralel
           
            Komputasi paralel adalah suatu bentuk komputasi dimana instruksi-instruksi dijalankan secara berkesinambungan. Masalah yang besar dapat dibagi menjadi beberapa masalah yang lebih kecil(submasalah), untuk kemudian diselesaikan secara serempak. Komputasi paralel telah digunakan untuk melakukan komputasi yang mensyaratkan unjuk kerja yang tinggi(high-performance computing). Teknik komputasi ini semakin berkembang dewasa ini, hal ini disebabkan oleh batasan fisik di dalam penskalaan frekuensi(frequency scaling[1]). Komputasi paralel telah menjadi paradigma yang mendominan di dalam arsitektur komputer, yaitu misalnya prosesor multicore.

            Program komputer paralel lebih susah untuk dibangun dibandingkan dengan program komputer serial, hal ini disebabkan keserempakan menimbulkan masalah yang potensial di dalam membagi pekerjaan menjadi subpekerjaan dan menggabungkan kembali subpekerjaan tersebut menjadi hasil oleh perangkat lunak,  diantaranya kondisi berebut(race condition).
Komunikasi dan sinkronisasi diantara unit pemroses(processing unit) menjadi satu diantara tantangan terbesar untuk menghasilkan program paralel dengan performa yang baik.

Sejarah Singkat

            Pada tahun 1958, Peneliti IBM, John Cocke dan Daniel Slotnick membahas tentang pemanfaatan paralelisme di dalam komputasi numerik untuk pertama kalinya. Burroughs Corporation memperkenalkan D825 pada tahun 1962, sebuah komputer dengan empat buah prosesor yang mengakses 16 modul memori dengan bantuan saklar bar-silang(crossbar switch).

Latar Belakang

            Komputasi paralel memanfaatkan beberapa elemen pemroses secara berkesinambungan untuk menyelesaikan permasalahan, dengan cara memecah masalah menjadi bagian-bagian independen, kemudian masing-masing bagian tersebut diselesaikan oleh masing-masing elemen pemroses sesuai dengan algoritma secara serempak. Elemen pemroses dapat terdiri dari unit pemroses yang heterogen, dan dapat pula terdiri dari unit pemroses yang homogen. Elemen pemroses dapat berupa komputer tunggal dengan banyak prosesor, beberapa komputer yang terhubung dalam suatu jaringan, perangkat keras yang dikhususkan untuk melakukan komputasi paralel, ataupun kombinasi dari perangkat-perangkat yang telah disebutkan.

            Penskalaan frekuensi menjadi alasan utama dalam peningkatan performa komputer sejak pertengahan 1980an sampai dengan 2004. Waktu eksekusi(runtime) dari sebuah program adalah banyaknya instruksi dikali dengan waktu rata-rata sebuah instruksi. Dengan menganggap faktor lain adalah konstan, meningkatkan detak frekuensi(clock frequency) akan menurunkan waktu rata-rata yang diperlukan untuk menjalankan sebuah instruksi, yang kemudian akan mengurangi waktu eksekusi.
Konsumsi daya sebuah chip dirumuskan dengan persamaan:

P = C x V2 x F




Dimana P adalah daya, C adalah kapasitansi, V adalah tegangan, dan F adalah frekuensi prosesor. Apabila frekuensi ditingkatkan, maka akan terjadi peningkatan daya yang dikonsumsi oleh sebuah prosesor.





Hukum Amdahl

            Secara teoritis, peningkatan kecepatan akibat paralelisasi adalah linear, yaitu apabila elemen pemroses digandakan, maka waktu ekseskusi akan menjadi setengahnya. Tetapi, sangat sedikit algoritma paralel yang dapat mencapai peningkatan kecepatan yang optimal.
           
            Menurut Hukum Amdahl, bagian kecil dari sebuah program yang tidak dapat lagi diparalelkan, akan membatasi peningkatan kecepatan yang dapat dicapai dari paralelisasi secara keseluruhan. Semua masalah mengandung bagian yang dapat diparalelkan dan bagian yang tidak dapat diparalelkan juga. Hubungan antara kedua bagian ini dinyatakan dalam:

S = 1 / (1-P)

Dimana S adalah besarnya peningkatan kecepatan dari sebuah program, P adalah besarnya bagian yang dapat diparalelkan.
           
            Tidak semua hasil dari paralelisasi dapat meningkatkan kecepatan. Secara umum, ketika sebuah pekerjaan dibagi menjadi lebih banyak subpekerjaan, subpekerjaan tersebut menghabiskan waktu lebih banyak, yaitu untuk berkomunikasi diantara subpekerjaan. Hal ini tidak akan membuat waktu eksekusi menjadi lebih singkat, melainkan sebaliknya, hal inilah yang disebut sebagai perlambatan paralel(parallel slowdown).

Taksonomi Flynn

            Michael J. Flynn menciptakan satu diantara sistem klasifikasi untuk komputer dan program paralel, yang dikenal dengan sebutan Taksonomi Flynn. Flynn mengelompokkan komputer dan program berdasarkan banyaknya set instruksi yang dieksekusi dan banyaknya set data yang digunakan oleh instruksi tersebut.


Instruksi Tunggal
(single instruction)
Instruksi Majemuk
(multiple instruction)
Data Tunggal
(single data)
SISD
(Single Instruction Single Data)
MISD
(Multiple Instruction Single Data)
Data Majemuk
(multiple data)
SIMD
(Single Instruction Multiple Data)
MIMD
(Multiple Instruction Multiple Data)

Jenis-Jenis Komputer Paralel

            Berdasarkan tingkatan  perangkat keras yang mendukung paralelisme, secara umum komputer-komputer paralel dapat diklasifikasikan:
·      Multicore processing
Merupakan prosesor yang memiliki beberapa unit pengeksekusi. Sebuah prosesor multicore dapat melakukan beberapa instruksi per siklus dari beberapa aliran instruksi.
·      Symmetric multiprocessing
Merupakan sebuah sistem komputer dengan beberapa prosesor yang identik, dapat menggunakan struktur berbagi memori atau memori tersendiri yang saling terhubung melalui bus.
·      Distributed computing
Merupakan sebuah sistem komputer dengan memori terdistribusi, dimana masing-masing elemen pemrosesan dihubungkan oleh jaringan.
·      Cluster computing
Merupakan sekumpulan komputer yang bekerja sama,dihubungkan oleh jaringan,  sehingga dapat dipandang sebagai sebuah kesatuan, cluster komputer ini dikoordinasi oleh sebuah komputer induk yang bertugas untuk mendistribusikan pekerjaan kepada masing-masing komputer lainnya.
·      Massive parallel processing
Merupakan sebuah komputer tunggal dengan banyak prosesor yang terhubung dalam sebuah jaringan. Di dalam MPP, tiap CPU mempunyai memory tersendiri, sistem operasi dan aplikasi yang sama. Tiap subsistem berkomunikasi satu dengan yang lainnya melalui interkoneksi berkecepatan tinggi.
·      Grid computing
Merupakan bentuk pemrosesan paralel yang paling terdistribusi. Grid computing memanfaatkan Internet sebagai saluran komunikasi antar komputer untuk menyelesaikan suatu permasalahan.
·      Specialized parallel computer
Komputer paralel yang dikhususkan untuk menyelesaikan tugas khusus.

Superkomputer

            Superkomputer merupakan komputer terdepan dalam hal kapasitas pemrosesan, yaitu kecepatan penghitungan.

            Superkomputer yang memanfaatkan beberapa CPU, secara umum akan memperoleh kecepatan melebihi komputer konvensional dengan cara memanfaatkan rancangan inovatif yang memungkinkan CPU tersebut untuk melakukan tugas-tugas secara paralel, dikhususkan untuk melakukan komputasi tertentu(biasanya kalkulasi numerik) dan melakukan tugas komputasi umum dengan kurang baik. Hirarki memori superkomputer dirancang dengan sangat berhati-hati untuk menjamin bahwa prosesor tetap memperoleh data dan instruksi setiap waktu.
           
            Hukum Amdahl juga berlaku pada superkomputer, perancangan superkomputer yang paling menyita adalah usaha untuk menghilangkan serialisasi dari perangkat lunak dan pemanfaatan perangkat keras.

Tantangan Superkomputer
·      Superkomputer menghasilkan panas yang berlebihan dan harus didinginkan dengan segera.
·      Superkomputer harus mempunyai waktu latensi(waktu yang diperlukan untuk perambatan sinyal) antar komponen yang sangat singkat.
·      Superkomputer memerlukan dan menghasilkan data dalam jumlah yang sangat besar dalam rentang waktu yang sangat singkat, sehingga diperlukan bandwidth media penyimpanan luar(external storage) yang cukup untuk menjamin bahwa informasi dapat ditransfer dengan cepat dan dapat disimpan ataupun diperoleh kembali dengan akurat.

            Arsitektur paralel superkomputer mengharuskan pemanfaatan teknik pemrograman yang spesial untuk mencapai kecepatan yang optimal.

Arsitektur Superkomputer Modern

            Superkomputer yang dikembangkan oleh CDC merupakan prosesor skalar yang lebih cepat sepuluh kali dibandingkan mesin tercepat yang ditawarkan oleh perusahaan lainnya. Pada tahun 1970an, superkomputer dikhususkan untuk bekerja pada prosesor vektor. Pada permulaan dan pertengahan tahun 1980an, mesin yang terdiri dari beberapa prosesor vektor yang bekerja secara paralel menjadi sesuatu yang standard. Pada umumnya prosesor yang dilibatkan berjumlah antara empat sampai enam belas. Pada akhir tahun 1980an dan tahun 1990an, peralihan dari prosesor vektor ke MPP(massive parallel processing) yang terdiri dari ribuan CPU. Superkomputer dewasa ini merupakan komputer cluster yang telah disesuaikan sekaligus memanfaatkan kelebihan prosesor dan mengkombinasikan dengan interkoneksi.

            Superkomputer digunakan untuk melakukan tugas penghitungan yang sangat intensif, misalnya masalah yang melibatkan fisika mekanika kuantum, peramalan cuaca, penelitian terhadap iklim, pemodelan molekuler(melakukan komputasi terhadap struktur dan sifat dari campuran kimia, makromolekul biologikal, polymer, kristal), simulasi fisik(misalnya simulasi pesawat terbang, simulasi menjinakkan senjata nuklir, penelitian terhadap fusi nuklir), kriptanalisis, dan lain sebagainya.

Rancangan Perangkat Keras dan Perangkat Lunak

            Tertanggal 31 November 2006, sepuluh superkomputer teratas tercatat mempunyai arsitektur level atas yang sama, yaitu merupakan cluster multiprosesor MIMD, dimana tiap-tiap prosesor merupakan SIMD. Kemampuan superkomputer berbeda-beda tergantung pada banyaknya multiprosesor per cluster, banyaknya prosesor per multiprosesor, dan banyaknya instruksi yang berkelanjutan per prosesor SIMD, diperoleh:
·      Sebuah komputer cluster adalah sekumpulan komputer yang terhubung kuat melalui sebuah jaringan berkecepatan tinggi. Cluster terdiri dari komputer-komputer yang heterogen.
·      Komputer multiprosesor merupakan sebuah komputer, beroperasi di bawah sebuah sistem operasi dan memanfaatkan lebih dari satu CPU.
·      Prosesor SIMD mengekseskusi instruksi yang sama terhadap lebih dari satu set data pada waktu yang bersamaan.

Kesimpulan

            Superkomputer melakukan komputasi paralel, dengan kata lain superkomputer adalah sama dengan komputer paralel, yaitu sama-sama melakukan komputasi paralel.

Referensi