Komputasi Modern - Part V

Komputasi Modern

Blog ini dibuat untuk menyelesaikan tugas mata kuliah Komputasi Modern

Quantum Gates

Quantum Gates / Gerbang Quantum merupakan sebuah aturan logika / gerbang logika yang berlaku pada quantum computing. Prinsip kerja dari quantum gates hampir sama dengan gerbang logika pada komputer digital. Jika pada komputer digital terdapat beberapa operasi logika seperti AND, OR, NOT, pada quantum computing gerbang quantum terdiri dari beberapa bilangan qubits, sehingga quantum gates lebih susah untuk dihitung daripada gerang logika pada komputer digital.

Quantum gate termasuk sebuah petunjuk yang memiliki cara atau perhitungan dari komputasi kuantum tersebut dan khususnya model rangkaian kuantum perhitungan, sebuah gerbang kuantum (quantum atau gerbang logika) adalah dasar kuantum sirkuit operasi pada sejumlah kecil qubit. Tidak seperti banyak gerbang logika klasik, gerbang logika kuantum yang reversibel. Namun, komputasi klasik dapat dilakukan dengan menggunakan hanya gerbang reversibel. Misalnya, gerbang Toffoli reversibel dapat melaksanakan semua fungsi Boolean. Gerbang ini memiliki setara kuantum langsung, menunjukkan bahwa sirkuit kuantum dapat melakukan semua operasi yang dilakukan oleh sirkuit klasik.

Quantum gerbang logika yang diwakili oleh matriks kesatuan. Gerbang kuantum yang paling umum beroperasi pada ruang satu atau dua qubit, seperti yang umum gerbang logika klasik beroperasi pada satu atau dua bit. Ini berarti bahwa sebagai matriks, gerbang kuantum dapat dijelaskan oleh 2 × 2 atau 4 × 4 matriks kesatuan.

Algoritma Shor

Algoritma Shor, dinamai oleh matematikawan Peter Shor, adalah algoritma kuantum yaitu merupakan suatu algoritma yang berjalan pada komputer kuantum yang berguna untuk faktorisasi bilangan bulat. Algoritma Shor dirumuskan pada tahun 1994.  Inti dari algoritma ini merupakan bagaimana cara menyelesaikan faktorisasi terhadap bilangan integer atau bulat yang besar.

Algoritma Shor didasarkan dari sebuah teori bilangan:fungsi F(a) = xamod n adalah feungsi periodik jika xadalah bilangan bulat yang relatif prima dengan n.Dalam Algoritma Shor, n akan menjadi bilangan bulatyang hendak difaktorkan.

Menghitung fungsi ini di komputer konvensionaluntuk jumlah yang eksponensial akan membutuhkan waktu eksponensial pula. Pada masalah ini algoritmaquantum shor memanfaatkan pararellisme quantumuntuk melakukannya hanya dengan satu langkah.

Karena F(A) adalah fungsi periodik, maka fungsi inimemiliki sebuah periode r. Diketahui x0mod n = 1,maka xr mod n =1, begitu juga x2r mod n danseterusnya.

Dengan informasi ini dan manipulasi persamaansederhana berikut:

xr ≡ 1 mod n

(xr/2)2 ≡ 1 mod n

(xr/2)2 - 1≡ 0 mod n

Dengan anggapan r adalah angka genap

(xr/2 – 1)(xr/2 + 1) ≡ 0 mod n

Parallerism Concept

Paralelisme (parallelism) lahir dari pendekatan yang biasa dipergunakan oleh para perancang sistem untuk menerapkan konsep pemrosesan konkuren. Teknik ini meningkatkan kecepatan proses dengan cara memperbanyak jumlah modul perangkat keras yang dapat beroperasi secara simultan disertai dengan membentuk beberapa proses yang bekerja secara simultan pada modul-modul perangkat keras tersebut

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.
• 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.
2. Multiprosesor, yaitu sebuah sistem yang memiliki 2 prosesor atau lebih yang saling berbagi memori.
3. Multikomputer, yaitu sebuah sistem yang memiliki 2 prosesor atau lebih yang masing-masing prosesor memiliki memori sendiri.

Jenis-Jenis Pemrosesan Paralel

Pemrosesan paralel dapat dibagi ke dalam beberapa klasifikasi, sebagai berikut :

1. Berdasarkan simetri penjadwalannya, pemrosesan parallel dapat dibagi dalam beberapa jenis:
• Asymmetric Multiprocessing (ASMP)
• Symmetric Multiprocessing (SMP)
• ClusteringPoliteknik Telkom Sistem Komputer
2. Berdasarkan aliran instruksi dan datanya, pemrosesan parallel dapat dibagi dalam beberapa jenis:
• SISD (Single Instruction on Single Data Stream)
• SIMD (Single Instruction on Multiple Data Stream)
• MISD (Multiple Instruction on Single Data Stream)
• MIMD (Multiple Instruction on Multiple Data Stream)
3. Berdasarkan kedekatan antar prosesor, pemrosesan parallel dapat dibagi dalam beberapa jenis : 

• Multikomputer (Loosely Coupled/ local memory) dengan memori yang terdistribusi
• Multiprosesor (Tightly Coupled/ global memory) dengan memori yang dapat digunakan bersama (shared memory)

Distributed Processing

Komputasi terdistribusi adalah suatu sistem pada jaringan komputer yang dihubungkan dengan cara tertentu sehingga tampak seperti satu komputer bagi pemakai individual. Komputasi terdistribusi menggunakan sumber data komputer yang ada dan melibatkan banyak komputer yang terdistribusi dan terpisah secara geografis yang bertujuan untuk memecahkan berbagai macam persoalan komputasi dalam skala besar.

Komputasi terdistribusi mentransformasikan banyak komputer dalam satu jaringan yang dapat digunakan secara efektif seperti halnya sebuah komputer saja, sehingga memaksimalkan penggunaan sumber daya komputasi. Hal ini berarti bahwa setiap klien dalam jaringan dapat mengakses setiap file data yang terdapat dalam jaringan, menjalankan program komputer yang ada dalam jaringan (baik yang ada dalam server maupun yang ada dalam klien).

Sistem pengolahan data terdistribusi dapat diakses oleh pengguna dengan menggunakan dua aplikasi yaitu berupa aplikasi lokal dan aplikasi global, sehingga distributed data processing system memiliki karakteristik yaitu :

• Kumpulan dari data logik yang digunakan bersama-sama.
• Data di bagi menjadi beberapa fragment.
• Fragment mungkin mempunyai copy ( replika ).
• Fragment / replika nya di alokasikan pada yang digunakan.
• Setiap site berhubungan dengan jaringan komunikasi.
• Data pada masing-masing site dibawah pengawasan DBMS.
• DBMS pada masing-masing site dapat mengatasi aplikasi lokal, secara otonomi.
• Masing-masing DBMS berpastisipasi paling tidak satu global aplikasi

Message 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. 

Message-passing dilakukan oleh prosesor-prosesor yang terlibat dalam komputasi paralel untuk melakukan pertukaran data dan sinkronisasi antar prosesor. Pertukaran data pada message-passing dibuat dengan menghubungkan sekumpulan komputer melalui sebuah interkoneksi jaringan. Setiap komputer memiliki sebuah prosesor dan memori lokal, seperti ditunjukkan pada gambar diatas, dan komunikasi antar komputer dilakukan melalui interkoneksi jaringan. Pesan tersebut berisikan data yang diperlukan dalam komputasi. 

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.

Architectural Parallel Computer

Arsitektur komputer paralel ada beberapa versi pengertian. Organisasi Prosesor dibagi menjadi 4 :

SISD

Single Instruction – Single Data. Komputer ini memiliki hanya satu prosesor dan satu instruksi yang dieksekusi secara serial. Komputer ini adalah tipe komputer konvensional. 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. Sampai saat ini belum ada komputer yang menggunakan model MISD karena sistemnya tidak mudah.

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. Komponen-komponen utama dari arsitektur komputer paralel cluster PC antara lain:

• Prosesor (CPU). Bagian paling penting dalam sistem, untuk multicore terdapat lebih dari satu core yang mengakses sebuah memori (shared memory).
• Memori. Bagian ini dapat diperinci lagi menjadi beberapa bagian penyusunnya seperti RAM, cache memory dan memori eksternal.
• Sistem Operasi. Software dasar untuk menjalankan sistem komputer.
• Cluster Middleware. Antarmuka antara hardware dan software.
• Programming Environment dan Software Tools. Software yang digunakan untuk pemrograman paralel termasuk software pendukungnya.
• User Interface. Software yang menjadi perantara hardware dengan user.
• Aplikasi. Software berisi program permasalahan yang akan diselesaikan.
• Jaringan. Penghubung satu PC (prosesor) dengan PC yang lain sehingga memungkinkan pemanfaatan sumberdaya secara simultan.

Pengantar Thread Programming

Thread dalam sistem operasi dapat diartikan sebagai sekumpulan perintah (instruksi) yang dapat dilaksanakan (dieksekusi) secara sejajar dengan ulir lainnya, dengan menggunakan cara time slice (ketika satu CPU melakukan perpindahan antara satu ulir ke ulir lainnya) atau multiprocess (ketika ulir-ulir tersebut dilaksanakan oleh CPU yang berbeda dalam satu sistem). Ulir sebenarnya mirip dengan  roses, tapi cara berbagi sumber daya antara proses dengan ulir sangat berbeda. Multiplethread dapat  dilaksanakan secara sejajar pada sistem komputer. Secara umum multithreading melakukan time-slicing  (sama dengan time-division multipleks), di mana sebuah CPU bekerja pada ulir yang berbeda, di mana suatu kasus ditangani tidak sepenuhnya secara serempak, untuk CPU tunggal pada dasarnya benar-benar melakukan sebuah pekerjaan pada satu waktu. Thread saling berbagi bagian program, bagian data dan sumber daya sistem operasi denganthread lain yang mengacu pada proses yang sama. Thread terdiri atas ID thread, program counter, himpunan register, dan stack. Dengan banyak kontrol thread proses dapat melakukan lebih dari satu pekerjaan pada waktu yang sama.

Karakteristik Thread

Proses merupakan lingkungan eksekusi bagi thread-thread yang dimilikinya. Thread-thread di satu proses memakai bersama sumber daya yang dimiliki proses, yaitu :

• Ruang alamat.
• Himpunan berkas yang dibuka.
• Proses-proses anak.
• Timer-timer.
• Sinyal-sinyal.
• Sumber daya-sumber daya lain milik proses.

Jenis-jenis Thread Berdasarkan Waktu Penciptaannya

1. Static Threads

Jumlah thread yang akan dibuat ditentukan saat penulisan dan kompilasi program. Tiap thread langsung dialokasikan stack tetap.

Keunggulan = sederhana.

Kelemahan = tidak fleksibel.

2. Dynamic Threads

Penciptaan dan penghancuran thread “on-the-fly” saat eksekusi. Penciptaan thread biasanya menspesifikasikan fungsi utama thread (seperti pointer ke procedure) dan ukuran stack, dapat juga ditambah parameter-parameter lan seperti prioritas panjadwalan.

Keunggulan = fleksibel.

Kelemahan = lebih rumit.

Jenis – Jenis Proses Thread

1. Single Thread Process

Sebuah proses tradisional atau heavyweight process mempunyai single thread yang berfungsi sebagai pengendali. Dapat diartikan sebagai proses yang bekerja secara berurutan sesuai dengan urutan masing-masing thread (terstruktur) dan hanya mengerjakan satu tugas dalam satu waktu.

2. Multithread Process

Merupakan satu atau beberapa thread yang dijalankan secara bersamaan(multiproses), dimana masing-masing thread tersebut dijalankan pada jalur masing-masing. Setiap thread pada multithread menjalankan kode atau script program secara berurutan. Multithread dapat diartikan juga sebagai suatu proses dengan thread banyak dapat mengerjakan lebih dari satu tugas pada satu satuan waktu. Multithread sering pula disebut dengan multiproses atau multitasking pada system operasi.

Berdasarkan Pemetaan Thread 

Model multithreading berdasarkan dengan pemetaan dibedakan menjadi tiga bagian, yaitu:

• Many-to-One 

Banyaknya User-Level thread yang dipetakan ke kernel thread tunggal, akan tetapi dari beberapa user thread dapat menggunakan satu kernel thread saja.

Contoh :

Solaries Green Thread

GNU Portable Thread

• One-to-One 

Setiap user-level thread memetakan ke kernel thread, akan tetapi user thread hanya dapat menggunakan satu kernel thread.

Contoh :

Windows NT/XP/2000

Linux

Solaris 9 and later

• Many-to-Many

Mengijinkan beberapa user-level thread memakai beberapa kernel thread.

Mengijinkan system operasi untuk menciptakan beberapa kernel thread.

Keuntungan dari sistem ini ialah kernel thread yang bersangkutan dapat berjalan secara paralel pada multiprosessor.

DAFTAR PUSTAKA / REFERENSI

https://www.slideshare.net/IrfannurCahyo3/quantum-gates

http://flamekaizer.blogspot.com/2012/09/apa-itu-multi-programming-multi.html

https://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2008-2009/Makalah2008/Makalah0809-087.pdf  (algoritma shor)

http://repository.politekniktelkom.ac.id/Courseware/Semester%201/Sistem%20Komputer/Cousware%20Siskom%20(indoVERSION)/BAB%20XII.pdf

http://komputer.yn.lt/adalah/?arti=Distributed%20Processing

https://fskita.com/2018/07/13/distributed-data-processing-system-berserta-contoh-implementasi/

http://seto.citravision.com/berita-48-parallel-computation–architectural-parallel-computer.html

http://ebook.repo.mercubuana-yogya.ac.id/FTI/tugas_doc_20151/14121004-SIF50_P_5-SO_Artikel%20Thread_SI_21_14121004_Adito%20Efri.pdf

https://lancangkuning.com/post/17303/pengertian-thread.html

http://world-just-for-you.blogspot.com/2014/11/thread-proses-dan-thread-programming.html

https://bundet.com/d/81-pengertian-thread-multi-threading-pada-java

https://elib.unikom.ac.id/files/disk1/367/jbptunikompp-gdl-syahrilnas-18320-3-babii.pdf

http://albertojuanpablo.blogspot.com/2016/05/parallel-computation-pengantar-message.html