Tugas Komputasi Modern M10

 GERBANG LOGIKA QUANTUM 

Dalam komputasi kuantum dan khususnya sirkuit kuantum model komputasi, sebuah gerbang logika kuantum (atau hanya gerbang kuantum ) adalah dasar sirkuit kuantum operasi pada sejumlah kecil qubit . Mereka adalah blok bangunan sirkuit kuantum, seperti gerbang logika klasik untuk sirkuit digital konvensional.

Tidak seperti banyak gerbang logika klasik, gerbang logika kuantum bersifat reversibel . Namun, dimungkinkan untuk melakukan komputasi klasik hanya menggunakan gerbang reversibel. Misalnya, gerbang Toffoli reversibel dapat mengimplementasikan semua fungsi Boolean, seringkali dengan biaya harus menggunakan ancilla bits . Gerbang Toffoli memiliki ekuivalen kuantum langsung, menunjukkan bahwa sirkuit kuantum dapat melakukan semua operasi yang dilakukan oleh sirkuit klasik.

Gerbang kuantum adalah operator kesatuan , dan digambarkan sebagai matriks kesatuan relatif terhadap beberapa basis . Biasanya kita menggunakan basis komputasi , yang jika kita tidak membandingkannya dengan sesuatu, hanya berarti bahwa untuk sistem kuantum tingkat d (seperti qubit , register kuantum , atau qutrit dan qudit ) kita telah memberi label vektor basis ortogonal 

Gerbang logika kuantum umum dengan nama (termasuk singkatan), bentuk sirkuit dan matriks kesatuan yang sesuai.

ALGORITMA SHOR 

Algoritma Shor adalah algoritma untuk kuantum komputer yang berguna mencari faktor suatu bilangan yang sangat besar. Proses ini dapat memecahkan RSA, public-key cryptosystem yang paling umum digunakan.

Bagaimana cara kerjanya?

Ternyata, jika kita bisa mencari periode dari suatu deretan bilangan yang sangat panjang, kita bisa melakukan faktorisasi suatu bilangan yang sangat besar. Transformasi Fourier dapat digunakan untuk mencari periode. Sementara, komputer kuantum yang memiliki ruang keadaan yang sangat besar, dapat digunakan untuk mengambil sampel dari hasil transformasi Fourier terhadap deretan bilangan yang sangat panjang. Dengan probabilitas yang besar, sampel ini dapat kita gunakan untuk melakukan komputasi klasik yang menghasilkan faktor dari suatu bilangan.

Contoh komponen klasik dari algoritma ini adalah sebagai berikut. Jika kita ingin melakukan faktorisasi bilangan besar N, deretan bilangan yang harus kita cari periodenya adalah xa$x^a$ (mod N). Misal N = 91 dan x$x$= 2. Deretan bilangannya adalah 1, 2, 4, 8, 16, 32, 64, 37, 74, 57, 23, 46, 1, 2, 3, …. Periodenya adalah 12. Untuk mencari faktornya, perhatikan xb$x^b$ dengan b$b$ adalah setengah dari periode, yaitu 6. Jika kita beruntung, dan ini kemungkinannya adalah 1/2, maka xb−1$x^b-1$ akan mengandung salah satu faktor sementara xb+1$x^b+1$ mengandung faktor lainnya. Untuk b = 6, bilangan ini adalah 64 - 1 = 63 yang memiliki faktor 7 dan 64 + 1 = 65 yang memiliki faktor 13. Kita bisa mencari faktor-faktor ini menggunakan rumus Euclid untuk Faktor Persekutuan Terbesar (FPB). Contohnya, FPB dari 91 dan 63 adalah 7.

Untuk menjelaskan transformasi Fourier kuantum sedikit lebih sulit dan tempatnya terlalu sempit di sini. Intinya adalah, ini adalah algoritma Cooley-Tukey Fast Fourier Transform yang diadaptasikan ke komputer kuantum. Untuk mencari periode dari deretan sepanjang 2k$2^k$ dibutuhkan k2$k^2$ gerbang kuantum. Ini bukan bagian yang paling memakan waktu lama dalam algoritma ini. Yang paling memakan waktu adalah menghitung deretan xa$x^a$ dalam komputer kuantum, yang membutuhkan kurang lebih k3$k^3$ gerbang kuantum jika N adalah bilangan k$k$-bit. Scott Aaronson memiliki penjelasan yang lebih rinci mengenai hal ini di dalam 

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 :

Komputer Array.

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)

Prosesor vektor : beberapa prosesor yang disusun seperti pipeline.

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

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

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.

Distributed data processing /  pemrosesan data terdistribusi

Merupakan sekumpulan peralatan pemrosesan yang saling terhubung melalui jaringan yang mengerjakan tugas-tugas tertentu.

Pemrosesan terdistribusi dapat dikelompokan berdasarkan beberapa kriteria yaitu :

Struktur antar hubungan

Kesaling tergantungan komponen-komponen.

Keselarasan antar komponen.

Distributed database system / system database terdistribusi

Merupakan sekumpulan database yang saling terhubung secara logical dan secara fisik terdistribusi pada berbagai tempat melalui jaringan computer.

Sistem yang mengelola  database terdistribusi dan menyediakan mekanisme agar distribusi transparent adalahdistributed database management system (DDBMS).

Ciri-ciri untuk system yang bukan merupakan system database terdistribusi :

Sistem yang berisi kumpulan file

Berbagai arsitektur fisik berkait dengan system multiprocessor.

Ciri sistem database distribusi

Data disimpan pada sejumlah tempat. Setiap tempat secara logic terdiri dari processor tunggal.

Processor pada tempat yang berbeda tersebut dihubungkan dengan jaringan computer.

Bukan sekumpulan file yang berada pada berbagai tempat tetapi merupakan database pada berbagai tempat.

Setiap tempat mempunyai kemampuan untuk mandiri memproses permintaan user yang membutuhkan akses kedata ditempat tersebut, dan juga mampu untuk memproses data yang tersimpan di tempat lain

Keuntungan dan Kelemahan sistem database distribusi

–         Keuntungan :

Pengelolaan secara transparan data terdistribusi dan replicated : setiap pengelolaan terjadi secara terbuka dan datanya terdistribusi

Mengacu pada struktur organisasi : sesuai dengan struktur database distribusi yang sudah ada

Meningkatkan ketersediaan data : setiap data yang diinginkan sudah tersedia

Memudahkan pengembangan system : kemudahan untuk mengupdate system database terdistribusi sangat mudah

–         Kelemahan :

Control integritas lebih sulit : control yang di perlukan sangat sulit dan butuh pemahaman lebih lanjut

Biaya pengembangan : penguleuaran biaya untuk pengembangan lebih mahal

Kurang standarisasi : tidak ada standarisasi untuk Batasan minimal

Menambahkan kebutuhan penyimpanan : kuota untuk penyimpanan masih sedikit

Menambah biaya pelatihan : sama seperti biaya pengembangan , biaya pelatihan juga tidak murah.

Architectural Parallel Computer

 Pemrosesan paralel telah dikembangkan sebagai teknologi yang efektif dalam komputer modern untuk memenuhi permintaan akan kinerja yang lebih tinggi, biaya yang lebih rendah, dan hasil yang akurat dalam aplikasi kehidupan nyata. Peristiwa bersamaan yang umum di komputer saat ini karena praktek multiprogramming, multiprocessing, atau multicomputing.

Komputer modern memiliki paket perangkat lunak yang kuat dan ekstensif. Untuk menganalisis perkembangan kinerja komputer, terlebih dahulu kita harus memahami perkembangan dasar perangkat keras dan perangkat lunak.

Tonggak Perkembangan Komputer Ada dua tahap utama pengembangan komputer - bagian mekanik atau elektromekanis . Komputer modern berkembang setelah pengenalan komponen elektronik. Elektron mobilitas tinggi di komputer elektronik menggantikan bagian operasional di komputer mekanik. Untuk transmisi informasi, sinyal listrik yang bergerak hampir dengan kecepatan cahaya menggantikan roda gigi atau tuas mekanis.

Elemen Komputer Modern Sistem komputer modern terdiri dari perangkat keras komputer, set instruksi, program aplikasi, perangkat lunak sistem, dan antarmuka pengguna.

Masalah komputasi dikategorikan sebagai komputasi numerik, penalaran logis, dan pemrosesan transaksi. Beberapa masalah kompleks mungkin memerlukan kombinasi ketiga mode pemrosesan.

Evolusi Arsitektur Komputer Dalam empat dekade terakhir, arsitektur komputer telah mengalami perubahan yang revolusioner. Kami mulai dengan arsitektur Von Neumann dan sekarang kami memiliki multikomputer dan multiprosesor.

Kinerja sistem komputer Kinerja sistem komputer bergantung pada kemampuan mesin dan perilaku program. Kemampuan mesin dapat ditingkatkan dengan teknologi perangkat keras yang lebih baik, fitur arsitektur canggih, dan manajemen sumber daya yang efisien. Perilaku program tidak dapat diprediksi karena bergantung pada aplikasi dan kondisi run-time.

Pengantar Thread Programming

Threading adalah sebuah alur control dari sebuah proses. Konsep thread menjalankan 2 proses yang sama atau yang beda 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.

Mekanisme ini terhitung lambat karena disebut dengan statis. Selain itu teknik ini tidak mudah diterapkan dan rentan kesalahannya

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.

Analisa

Thread adalah bentuk kecil dari program yang akan dieksekusi oleh processor. Pada sebuah single processor multi-threading biasanya terjadi dengan pengaturan waktu pemrosesan thread. Sehingga processor berganti-ganti dan membagi waktu untuk menyelesaikan thread tetapi tidak pada paralel computing. Dengan multi-processor atau multi-core, multi-threading bisa berlangsungsecara bersamaan, maka di situ lah tantangan untuk para programmer agar dapat membuat program yang dapat di proses secara paralel.

Kesimpulan

Komputasi parallel sangat bermanfaat dibidang teknologi masa kini. Sebuah thread adalah informasi terkait dengan penggunaan sebuah program tunggal yang dapat menangani beberapa pengguna secara bersamaan. Sebuah thread merupakan informasi yang dibutuhkan untuk melayanin satu pengguna individu atau permintaan pelayanan tertentu. Thread dapat memungkinkan program untuk mengetahui pengguna sedang masuk didalam proses secara bergantian dan akan kembali masuk atas nama pengguna berbeda

Massage Passing

Massage Passing merupkan suatu teknik bagaimana mengatur suatu alur komunikasi messaging terhadap proses pada system. Message passing dalam ilmu komputer adalah suatu bentuk komunikasi yang digunakan dalam komputasi paralel, pemrograman-berorientasi objek, dan komunikasi interprocess. Dalam model ini, proses atau benda dapat mengirim dan menerima pesan yang terdiri dari nol atau lebih byte, struktur data yang kompleks, atau bahkan segmen kode ke proses lainnya dan dapat melakukan sinkronisasi. Paradigma Message passing yaitu :

1.  Banyak contoh dari paradigma sekuensial dipertimbangkan bersama-sama.

2.Programmer membayangkan beberapa prosesor, masing-masing dengan memori, dan menulis sebuah program untuk berjalan pada setiap prosesor.

3. Proses berkomunikasi dengan mengirimkan pesan satu sama lain.

Terdapat beberapa metode dalam pengiriman pesan yaitu :

·        Synchronous Message Passing

Pengirim menunggu untuk mengirim pesan sampai penerima siap untuk menerima pesan. Oleh karena itu tidak ada buffering. Selain itu Pengirim tidak bisa mengirim pesan untuk dirinya sendiri.

·        Ansynchronous Message Passing

Pengirim akan mengirim pesan kapanpun dia mau. Pengirim tidak peduli ketika penerima belum siap untuk menerima pesan. Oleh karena itu diperlukan buffering untuk menampung pesan sementara sampai penerima siap menerima pesan. Selain itu pengirim dapat pesan untuk dirinya sendiri.

OpenMP (Open Multiprocessing)

OpenMP adalah Application Programing Interface (API) yang mendukung pemrograman multiprosesing shared memory dalam bahasa C/C++ dan fortran pada berbagai arsitektur dan sistem operasi diantaranya: Solaris, AIX, HP-UX,GNU/Linux, Mac OS X, dan Windows.

OpenMP adalah model portabel dan skalabel yang memberikan interface sederhana dan fleksibel bagi programer shared memory dalam membangun aplikasi paralel. Program multithread dapat ditulis dalam berbagai cara. Beberapa diantaranya memungkinkan untuk melakukan interaksi yang kompleks antar thread. OpenMP mencoba untuk memberikan kemudahan pemrograman serta membantu dalam menghindari kesalahan program, melalui pendekatan terstruktur. Pendekatan ini dikenal sebagai model pemrograman fork-join.

OpenMP bekerja berdasarkan model shared memory, maka secara default data dibagi diantara thread-thread dan dapat terlihat dari setiap thread. Terkadang program akan membutuhkan variabel dengan nilai thread spesifik. Jika setiap thread memiliki variabel duplikat akan sangat berpotensi memiliki nilai yang berbeda-beda pada setiap variabel duplikat tersebut.

Sinkronisasi (pengkoordinasian) aksi dari thread adalah sesuatu yang sangat penting untuk menjamin data yang harus dibagi dan untuk mencegah terjadinya data race condition. Secara default OpenMP telah menyediakan mekanisme untuk menunggu thread dalam suatu tim thread sehingga semua thread menyelesaikan tugasnya dalam region, kemudian dapat melanjutkan ke proses selanjutnya. Mekanisme ini dikenal sebagai barrier.