Parallel Computation

BAB IV

Parallel Computation

4.1       Parallelism Concept

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

Tujuan Komputasi Paralel

Tujuan dari komputasi paralel adalah meningkatkan kinerja komputer dalam menyelesaikan berbagai masalah. Dengan membagi sebuah masalah besar ke dalam beberapa masalah kecil, membuat kinerja menjadi cepat.

Terdapat dua hukum yang berlaku dalam sebuah parallel processing. yaitu:

·         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 :

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 parallel (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.

4.2       Distributed Processing

Distributed Processing adalah kemampuan 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 maka prosesor yang lain akan mengambil alih tugasnya.

4.3       Architectural Parallel Computer

Arsitektur paralel komputer menurut Klasifikasi Flynn’s :

·         SISD

Single Instruction – Single Data. Komputer ini memiliki hanya satu prosesor dan satu instruksi yang dieksekusi secara serial. Komputer ini adalah tipe komputer konvensional. Menurut mereka tipe komputer ini tidak ada dalam praktik komputer paralel karena bahkan mainframe pun tidak lagi menggunakan satu prosesor. Klasifikasi ini sekedar untuk melengkapi definisi komputer paralel. 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 tetapi praktiknya tidak ada komputer yang dibangun dengan arsitektur ini karena sistemnya tidak mudah dipahami. Sampai saat ini belum ada komputer yang menggunakan model MISD.

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

4.4       Pengantar Thread Programming

Konsep threading adalah menjalankan 2 proses ( proses yang sama atau proses yang berbeda ) dalam satu waktu.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, karenanya disebut dengan static. Selain itu teknik ini tidak mudah diterapkan dan rentan kesalahan. Alasannya, pembagian pekerjaan yang dinamis di antara thread-thread menyebabkan load balancing-nya cukup rumit. Untuk memudahkannya programmer harus menggunakan protocol komunikasi yang kompleks untuk menerapkan scheduler load balancing. Kondisi ini mendorong pemunculan concurrency platforms yang menyediakan layer untuk mengkoordinasi, menjadwalkan, dan mengelola sumberdaya komputasi paralel.

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. Nested parallelism memungkinkan sebuah subroutine di-spawned (ditelurkan dalam jumlah banyak seperti telur katak) sehingga program utama tetap berjalan sementara subroutine menghitung hasilnya. Sedangkan parallel loops seperti halnya fungsi for namun memungkinkan iterasi loop dilakukan secara bersamaan.

4.5       Pengantar Message Passing dan OpenMP

Message Passing Interface (MPI)

Message 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. Objek didistribusikan dan metode sistem remote seperti ONC RPC,CORBA,Java RMI,DCOM,SOAP, .NET Remoting,CTO,QNX Neutrino RTOS,OpenBinder,D-Bus,Unison RTOS dan serupa pesan lewat sistem. Paradigma Message passing yaitu :

·         Banyak contoh dari paradigma sekuensial dipertimbangkan bersama-sama.

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

·         Proses berkomunikasi dengan mengirimkan pesan satu sama lain

OpenMP

OpenMP merupakan API yang mendukung multi-platform berbagi memori multiprocessing pemrograman C,C++,dan Fortran. Pada kebanyakan arsitektur prosesor dan system operasi termasuk Solaris,AIX,HP-UX,GNU/Linux,Mac OS X,dan Windows platform. Ini terdiri dari satu set perintah kompiler, rutinitas library, dan variable lingkungan yang mempengaruhi perilaku run-time. OpenMP dikelola oleh nirlaba teknologi konsorsium OpenMP Arsitektur Review Board (ARB atau OpenMP), bersama-sama didefinisikan oleh sekelompok perangkat keras komputer utama dan vendor perangkat lunak termasuk AMD,IBM,Intel,Cray,HP,Fujitsu, Nvidia,NEC,Microsoft,Texas Instruments,Oracle Corporation.

4.6       Pengantar Pemrograman CUDA GPU

GPU ( Graphical Processing Unit ) awalnya adalah sebuah prosesor yang berfungsi khusus untuk melakukan rendering pada kartu grafik saja, tetapi seiring dengan semakin meningkatnya kebutuhan rendering, terutama untuk mendekati waktu proses yang realtime, maka meningkat pula kemampuan prosesor grafik tersebut. akselerasi peningkatan teknologi GPU ini lebih cepat daripada peningkatan teknologi prosesor sesungguhnya ( CPU ), dan pada akhirnya GPU menjadi General Purpose, yang artinya tidak lagi hanya untuk melakukan rendering saja melainkan bisa untuk proses komputasi secara umum.

Penggunaan Multi GPU dapat mempercepat waktu proses dalam mengeksekusi program karena arsitekturnya yang natively parallel. Selain itu Peningkatan performa yang terjadi tidak hanya berdasarkan kecepatan hardware GPU saja, tetapi faktor yang lebih penting adalah cara membuat kode program yang benarbenar bisa efektif berjalan pada Multi GPU.

CUDA merupakan teknologi anyar dari produsen kartu grafis Nvidia, dan mungkin belum banyak digunakan orang secara umum. Kartu grafis lebih banyak digunakan untuk menjalankan aplikasi game, namun dengan teknologi CUDA ini kartu grafis dapat digunakan lebih optimal ketika menjalankan sebuah software aplikasi. Fungsi kartu grafis Nvidia digunakan untuk membantu Processor (CPU) dalam melakukan kalkulasi dalam proses data.

CUDA merupakan singkatan dari Compute Unified Device Architecture, didefinisikan sebagai sebuah arsitektur komputer parallel, dikembangkan oleh Nvidia. Teknologi ini dapat digunakan untuk menjalankan proses pengolahan gambar, video, rendering 3D, dan lain sebagainya. VGA – VGA dari Nvidia yang sudah menggunakan teknologi CUDA antara lain : Nvidia GeForce GTX 280, GTX 260,9800 GX2, 9800 GTX+,9800 GTX,9800 GT,9600 GSO, 9600 GT,9500 GT,9400 GT,9400 mGPU,9300 mGPU,8800 Ultra,8800 GTX,8800 GTS,8800 GT,8800 GS,8600 GTS,8600 GT,8500 GT,8400 GS, 8300 mGPU, 8200 mGPU, 8100 mGPU, dan seri sejenis untuk kelas mobile ( VGA notebook ).

Singkatnya, CUDA dapat memberikan proses dengan pendekatan bahasa C, sehingga programmer atau pengembang software dapat lebih cepat menyelesaikan perhitungan yang komplek. Bukan hanya aplikasi seperti teknologi ilmu pengetahuan yang spesifik. CUDA sekarang bisa dimanfaatkan untuk aplikasi multimedia. Misalnya meng-edit film dan melakukan filter gambar. Sebagai contoh dengan aplikasi multimedia, sudah mengunakan teknologi CUDA. Software TMPGenc 4.0 misalnya membuat aplikasi editing dengan mengambil sebagian proces dari GPU dan CPU. VGA yang dapat memanfaatkan CUDA hanya versi 8000 atau lebih tinggi.

Sumber :

·         http://ajuarna.staff.gunadarma.ac.id/Downloads/files/9254/ArtikelEpilog.pdf

·         http://dsitompul.files.wordpress.com/2008/11/komputasi-paralel3.doc

·         http://en.wikipedia.org/wiki/Parallel_computing

·         http://nanxkurniawan.wordpress.com/2010/05/25/komputasi-paralel/

·         http://seto.citravision.com/berita-49-parallel-computation---pengantar-thread-programming.html

·         http://seto.citravision.com/berita-50-parallel-computation--pengantar-message-passing-openmp.html

·         https://id.wikipedia.org/wiki/Komputasi_paralel

Pengantar Quantum Computation

BAB III

Pengantar Quantum Computation

3.1       Pendahuluan

Quantum Computation atau komputer kuantum adalah sebuah alat untuk perhitungan, dimana perhitungan ini menggunakan langsung fenomena kuantum mekanik dan perhitungan ini seperti superposisi dan belitan untuk melakukan operasi pada data. Kuantum komputer berbeda dari komputer tradisional yang didasarkan pada transistor. Perbedaan komputer kuantum dengan komputer klasik adalah pada sebuah komputer klasik memiliki memori terdiri dari bit, dimana tiap bit mewakili salah satu atau nol. Sedangkan sebuah komputer kuantum mempertahankan urutan qubit. Sebuah qubit tunggal dapat mewakili satu, nol, atau, krusial. 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.

Komputer kuantum berbeda dengan komputer DNA dan komputer klasik berbasis transistor, walaupun mungkin komputer jenis tersebut menggunakan prinsip kuantum mekanik. Sejumlah arsitektur komputasi seperti komputer optik walaupun menggunakan superposisi klasik dari gelombang elektromagnetik, namun tanpa sejumlah sumber kuantum mekanik yang spesifik seperti keterkaitan, maka tak dapat berpotensi memiliki kecepatan komputasi sebagaimana yang dimiliki oleh komputer kuantum.

Ide mengenai komputer kuantum ini berasal dari beberapa fisikawan antara lain 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). Pada awalnya Feynman mengemukakan idenya mengenai sistem kuantum yang juga dapat melakukan proses penghitungan. Fenyman juga mengemukakan bahwa sistem ini bisa menjadi simulator bagi percobaan fisika kuantum. Selanjutnya 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.

3.2       Entanglement

Para ahli fisika dari University of Maryland telah satu langkah lebih dekat ke komputer kuantum dengan mendemonstrasikan eksistensi entanglement antara dua gurdi kuantum, masing-masing diciptakan dengan tipe sirkuit padat yang dikenal sebagai persimpangan Josephson.

Dipublikasikan dalam jurnal Science edisi pekan ini, hasil ini menunjukkan kemajuan terbaru dalam upaya ilmiah menerapkan sifat fisika kuantum pada pembuatan komputer yang jauh lebih bagus dibanding superkomputer yang ada saat ini.

Tim fisikawan yang dipimpin oleh profesor Fred Wellstood dari Center for Superconductivity

Research (pusat penelitian milik Jurusan Fisika University of Maryland) mengatakan penemuan mereka adalah yang pertama mengindikasikan keberhasilan penciptaan entanglement antara qubit persimpangan Josephson. Entanglement adalah efek mekanik kuantum yang mengaburkan jarak antara partikel individual sehingga sulit menggambarkan partikel tersebut terpisah meski Anda berusaha memindahkan mereka.

Jadi apa itu Entanglement ? Entanglement adalah esensi komputasi kuantum karena ini adalah jalinan kualitas yang berhubungan dengan lebih banyak informasi dalam bit kuantum dibanding dengan bit komputing klasik,” demikian Andrew Berkley, salah satu peneliti. Temuan terbaru ini mendekatkan jalan menuju komputer kuantum dan mengindikasikan bahwa persimpangan Josephson pada akhirnya dapat digunakan untuk membangun komputer super canggih.

3.3       Pengoperasian data qubit

Ilmu informasi quantum dimulai dengan menggeneralisir sumberdaya fundamental informasi klasik bit menjadi bit quantum, atau qubit. Sebagaimana bit merupakan objek ideal yang diabstraksi dari prinsip-prinsip fisika klasik, qubit adalah objek quantum ideal yang diabstraksi dari prinsip-prinsip mekanika quantum. Bit bisa direpresentasikan dengan kawasan-magnetik pada cakram, voltase pada sirkuit, atau tanda grafit yang dibuat pensil pada kertas. Pemfungsian status-status fisikal klasik ini sebagai bit tidak bergantung pada detil bagaimana mereka direalisasikan. Demikian halnya, atribut-atribut qubit adalah independen dari representasi fisikal spesifik sebagai pusingan nukleus atom atau, katakanlah, polarisasi photon cahaya.

Bit digambarkan oleh statusnya, 0 atau 1. Begitu pula, qubit digambarkan oleh status quantumnya. Dua status quantum potensial untuk qubit ekuivalen dengan 0 dan 1 bit klasik. Namun dalam mekanika quantum, objek apapun yang memiliki dua status berbeda pasti memiliki rangkaian status potensial lain, disebut superposisi, yang menjerat kedua status hingga derajat bermacam-macam. Status-status qubit yang diperkenankan persisnya merupakan semua status yang harus bisa dicapai, secara prinsip, oleh bit klasik yang ditransplantasikan ke dalam dunia quantum. Status-status qubit ekuivalen dengan titik-titik di permukaan bola, di mana 0 dan 1 sebagai kutub selatan dan utara. Kontinum status antara 0 dan 1 membantu perkembangan banyak atribut luar biasa informasi quantum.

3.4       Quantum Gates

Dalam kuantum komputer dan khususnya model rangkaian kuantum perhitungan, sebuah quantum gates atau quantum logic gates adalah dasar kuantum sirkuit operasi pada sejumlah kecil qubit. Mereka adalah blok bangunan sirkuit kuantum, seperti logic gates klasik untuk sirkuit digital konvensional.

Untuk memanipulasi informasi dalam qubit, kita menggunakan gerbang kuantum (Quantum Gates). Sebuah gerbang kuantum bekerja mirip dengan gerbang logika klasik. Gerbang logika klasik mengambil bit sebagai input, mengevaluasi dan memproses input dan menghasilkan bit baru sebagai output. Gerbang logika kuantum  mengambil dalam qubit yang bisa eksis dalam keadaan superposisi. Ini membuka dimensi baru seluruh kemungkinan solusi dan output.

3.5       Algoritma Shor

Algoritma Shor adalah contoh lanjutan paradigma dasar (berapa banyak waktu komputasi diperlukan untuk menemukan faktor bilangan bulat n-bit?), tapi algoritma ini tampak terisolir dari kebanyakan temuan lain ilmu informasi quantum. Sekilas, itu cuma seperti trik pemrograman cerdik dengan signifikansi fundamental yang kecil. Penampilan tersebut menipu; para periset telah menunjukkan bahwa algoritma Shor bisa ditafsirkan sebagai contoh prosedur untuk menetapkan level energi sistem quantum, sebuah proses yang fundamental.

Sumber :

·        http://godekcadel.blogspot.com/2013/04/pengantar-quantum-computation.html

·        http://meowmeow8.blogspot.com/2013/05/pengantar-quantum-computation.html

·        http://no21reason.blogspot.com/2013/05/pengantar-quantum-computation.html

·        http://puhtuzhi.blogspot.com/2013/05/pengantar-quantum-computation.html

·        http://seto.citravision.com/berita-44-pengantar-quantum-computation--quantum-gates.html

·        http://ssebtiani.blogspot.com/2013/05/pengantar-quantum-computation.html