MAKALAH M10
Komputasi Modern
AJI SANJAYA
50417398
4IA21
Algoritma Shor
Algoritma Shor, dinamai oleh matematikawan Peter Shor, adalah algoritma kuantum yaitu merupakan suatu algoritma yang berjalan pada komputer kuantum yang berguna untuk faktorisasibilanganbulat.AlgoritmaShordirumuskanpadatahun1994.Intidarialgoritmaini merupakan bagaimana cara menyelesaikan faktorisasi terhadap bilangan integer atau bulat yangbesar.
Efisiensi algoritma Shor adalah karena efisiensi kuantum Transformasi Fourier, dan modular eksponensial. Jika sebuah komputer kuantum dengan jumlah yang memadai qubit dapat beroperasitanpamengalamikebisingandanfenomenainterferensikuantumlainnya,algoritma Shor dapat digunakan untuk memecahkan kriptografi kunci publik skema seperti banyak digunakan skema RSA. Algoritma Shor terdiri dari duabagian:
Penurunan yang bisa dilakukan pada komputer klasik, dari masalah anjak untuk masalah ketertiban-temuan.
Sebuah algoritma kuantum untuk memecahkan masalahorder-temuan.
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.
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 sebagaiqubit,dapatdiprogramdenganmenggunakandenyut-denyutfrekuensiradiodandapat dideteksi melalui peralatan resonansi magnetis nuklir (nuclear magnetic resonance, atau NMR) yang mirip dengan yang banyak digunakan di rumah-rumah sakit dan laboratorium- laboratoriumkimia.
Quantum Gates
Pada saat ini, model sirkuit komputer adalah abstraksi paling berguna dari proses komputasi dansecaraluasdigunakandalamindustrikomputerdesaindankonstruksihardwarekomputasi praktis. Dalam model sirkuit, ilmuwan komputer menganggap perhitungan apapun setara dengan aksi dari sirkuit yang dibangun dari beberapa jenis gerbang logika Boolean bekerja pada beberapa biner (yaitu, bit string) masukan. Setiap gerbang logika mengubah bit masukan kedalamsatuataulebihbitkeluarandalambeberapamodedeterministikmenurutdefinisidari gerbang. dengan menyusun gerbang dalam grafik sedemikian rupa sehingga output dari gerbang awal akan menjadi input gerbang kemudian, ilmuwan komputer dapat membuktikan bahwa setiap perhitungan layak dapatdilakukan.
Quantum Logic Gates, Prosedur berikut menunjukkan bagaimana cara untuk membuat sirkuit reversibel yang mensimulasikan dan sirkuit ireversibel sementara untuk membuat penghematan yang besar dalam jumlah ancillae yang digunakan.
Pertama mensimulasikan gerbang di babak pertamatingkat.
Jauhkan hasil gerbang di tingkat d / 2 secaraterpisah.
Bersihkan bitancillae.
Gunakan mereka untuk mensimulasikan gerbang di babak keduatingkat.
Setelah menghitung output, membersihkan bit ancillae.
Bersihkan hasil tingkat d /2.
Sekarang kita telah melihat gerbang reversibel ireversibel klasik dan klasik, memiliki konteks yang lebih baik untuk menghargai fungsi dari gerbang kuantum. Sama seperti setiap perhitungan klasik dapat dipecah menjadi urutan klasik gerbang logika yang bertindak hanya pada bit klasik pada satu waktu, sehingga juga bisa setiap kuantum perhitungan dapat dipecah menjadi urutan gerbang logika kuantum yang bekerja pada hanya beberapa qubit pada suatu waktu. Perbedaan utama adalah bahwa gerbang logika klasik memanipulasi nilai bit klasik, 0 atau 1, gerbang kuantum dapat sewenang-wenang memanipulasi nilai kuantum multi-partite termasuk superposisi dari komputasi dasar yang juga dilibatkan. Jadi gerbang logika kuantum perhitungannya jauh lebih bervariasi daripada gerbang logika perhitungan klasik.
Penerapan Quantum Computing
Pada tahun 2000, IBM sudah membuat quantum computer dengan 5 qubits dengan atom sebagaiprosesornya.danD-WaveperusahaankomputerasalVancouver,Canadameriliskabar bahwa pihaknya telah mampu untuk beroperasi dengan prinsip quantum yang jauh ebih cepat dari komputer yang ada saat ini.
Komputer yang diberi nama “Orion” ini, menggunakan teknik cetakan rata yang sistematis, dipadukan dengan sebuah chip niobium superkonduksi dan suhu ultrarendah, dapat mengerjakan 16 qubit. Chip inti harus dingin hingga mendekati titik nol absolut (-125.15ºC), agar supaya dalam proses perhitungannya tetap dalam kondisi kuantum
Perusahaan D-Wave menuturkan, bahwa komputer kuantum ini bisa mengoperasikan 64ribu hitungan secara bersamaan, dan prototipe komputer kuantum yang diperlihatkannya pada 13 Februari 2007 merupakan komputer tipe bisnis yang pertama di dunia, di dalamnya ditanami chip kuantum yang dapat mengoperasikan 16 qubit.
Parallelism concept
Paralelisme (parallelism) lahir dari pendekatan yang biasa dipergunakan oleh para perancang sistem untuk menerapkan konsep pemrosesan konkuren. Teknik ini meningkatkan kecepatan prosesdengancaramemperbanyakjumlahmodulperangkatkerasyangdapatberoperasisecara simultan disertai dengan membentuk beberapa proses yang bekerja secara simultan pada modul-modul perangkat keras tersebut. Secara formal, pemrosesan paralel adalah sebuah bentuk efisien pemrosesan informasi yang menekankan pada eksploitasi dari konkurensi kejadian-kejadian dalam proses komputasi.Pemrosesan paralel dapat terjadi pada beberapa tingkatan (level) proses. Tingkatan tertinggi pemrosesan paralel terjadi pada proses di antara banyak job (pekerjaan) atau pada program yang menggunakan multiprogramming, time sharing, dan multiprocessing. Multiprogramming kemampuan eksekusi terhadap beberapa prosesperangkatlunakdalamsebuahsystemsecaraserentak,jikadibandingkandengansebuah proses dalam satu waktu, dan timesharing berarti menyediakan pembagian selang waktu yang tetap atau berubah-ubah untuk banyak program. Multiprocessing adalah dukungan sebuah sistem untuk mendukung lebih dari satu prosesor dan mengalokasikan tugas kepada prosesor- prosesor tersebut. Multiprocessing sering diimplementasikan dalam perangkat keras (dengan menggunakan beberapa CPU sekaligus), sementara multiprogramming sering digunakan dalamperangkatlunak.Sebuahsistemmungkindapatmemilikiduakemampuantersebut,salah satu di antaranya, atau tidak sama sekali. Pemrosesan paralel dapat juga terjadi pada proses di antaraprosedurproseduratauperintahperintah(segmenprogram)padasebuahprogram.Untuk meningkatkan kecepatan proses komputasi, dapat ditempuh dua cara:
Peningkatan kecepatan perangkat keras.
Komponen utama perangkat keras komputer adalah processor. Meskipun kecepatan processor dapatditingkatkanterus,namunkarenaketerbatasanmateripembuatnya,tentuadasuatubatas kecepatan yang tak mungkin lagi dapat dilewati. Karena itu timbul ide pembuatan komputer multiprocessor.Denganadanyabanyakprocessordalamsatukomputer,pekerjaanbisadibagi- bagikepadamasing-masingprocessor.Dengandemikianlebihbanyakprosesdapatdikerjakan dalam satu saat. Peningkatan kecepatan setiap proses bisa dicapai melalui peningkatan kecepatan perangkat lunak. Kecepatan perangkat lunak sangat ditentukan olehalgoritmanya.
Peningkatan kecepatan perangkat lunak
Program komputer untuk komputer sekuensial harus menyediakan sederetan operasi untuk dikerjakan oleh prosesor tunggal. Program komputer untuk komputer paralel harus menyediakansederetan operasi untuk beberapa prosesor untuk dikerjakan secara paralel, termasuk operasi untuk mengatur dan mengitegrasikan prosesor-prosesor yang terpisah tersebut mengerjakan suatu komputasi yang koheren. Kebutuhan akan pembuatan dan pengaturan berbagai aktivitas komputasi paralel menambah dimensi baru proses dari pemrograman komputer. Algoritma untuk problem yang spesifik harus diformulasikan sedemikian rupa, agar menghasilkan aliran operasi paralel yang kemudian akan dieksekusi di prosesor yang berbeda. Karena itu, meskipun arsitektur multiprosesor dan multikomputer mempunyaipontensiyangtinggiuntukmeningkatkankemampuankomputasi,potensiiniakan tercapaimelaluipengertianyangbaikmengenaibahasapemrogramanparaleldanperancangan algoritmaparalel.
Tingkat Paralelisme
Berdasarkan tingkat paralelismenya prosesor paralel dapat dibagi menjadi beberapa tingkat 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 MultipleData)
Prosesor vektor : beberapa prosesor yang disusun sepertipipeline.
Multiprosesor, yaitu sebuah sistem yang memiliki 2 prosesor atau lebih yang salingberbagi memori.
Multikomputer, yaitu sebuah sistem yang memiliki 2 prosesor atau lebih yang masing- masing prosesor memiliki memorisendiri.
Jenis-Jenis Pemrosesan Paralel
Pemrosesan paralel dapat dibagi ke dalam beberapa klasifikasi, sebagai berikut :
Berdasarkan simetri penjadwalannya, pemrosesan parallel dapat dibagi dalam beberapa jenis:
Asymmetric Multiprocessing(ASMP)
Symmetric Multiprocessing(SMP)
ClusteringPoliteknik Telkom SistemKomputer
Berdasarkan aliran instruksi dan datanya, pemrosesan parallel dapat dibagi dalam beberapa jenis:
SISD (Single Instruction on Single DataStream)
SIMD (Single Instruction on Multiple DataStream)
MISD (Multiple Instruction on Single DataStream)
MIMD (Multiple Instruction on Multiple DataStream)
Berdasarkan kedekatan antar prosesor, pemrosesan parallel dapat dibagi dalam beberapa jenis:
Multikomputer (Loosely Coupled/ local memory) dengan memori yangterdistribusi
Multiprosesor (Tightly Coupled/ global memory) dengan memori yang dapat digunakan bersama (sharedmemory)
Distributed Processing
Distributed Processing adalah kemampuan menjalankan semua proses pengolahan data secara bersama antara komputer yang berfungsi sebagai pusat dengan beberapa komputer yang lebih kecil dan saling dihubungkan melalui jalur komunikasi.
Setiapkomputertersebutmemilikiprosesormandirisehinggamampumengolahsebagiandata 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. Dalam proses distribusi sudah mutlak diperlukan perpaduan yang mendalam antara teknologi komputer dan telekomunikasi, karena selain proses yang harus didistribusikan,semuahostkomputerwajibmelayaniterminal-terminalnyadalamsatuperintah dari komputerpusat.
Definisi umum dari pemrosesan terdistribusi merupakan cara untuk mempercepat pengolahan dataatauinformasidenganmendistribusikanpekerjaanatauintruksikebanyakkomputeryang telah dipilih untuk memberi kekuatan pemrosesan yang lebih cepat. Tujuan dari komputasi terdistribusiadalahmenyatukankemampuandarisumberdaya(sumberkomputasiatausumber informasi) yang terpisah secara fisik, ke dalam suatu sistem gabungan yang terkoordinasi dengan kapasitas yang jauh melebihi dari kapasitas individualkomponen-komponennya.
Tujuan lain yang ingin dicapai dalam komputasi terdistribusi adalah transparansi. Kenyataan bahwa sumber daya yang dipakai oleh pengguna sistem terdistribusi berada pada lokasi fisik yang terpisah, tidak perlu diketahui oleh pengguna tersebut. Transparansi ini memungkinkan pengguna sistem terdistribusi untuk melihat sumber daya yang terpisah tersebut seolah-olah sebagai satu sistem komputer tunggal, seperti yang biasa digunakannya. Dalam prosesnya setiap komputer berinteraksi satu sama lain untuk mencapai tujuan bersama.
Architectural Parallel Computer
Arsitektur komputer paralel ada beberapa versi pengertian. Di sini saya akan menjelaskan sedikit tentang arsitektur komputer menurut Flynn. Sesuai taksonomi Flynn, seorangDesigner Processor, Organisasi Prosesor dibagi menjadi 4:
SISD
SingleInstruction–SingleData.Komputerinimemilikihanyasatuprosesordansatuinstruksi 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 PDP1.
SIMD
SingleInstruction–MultipleData.Komputerinimemilikilebihdarisatuprosesor,tetapihanya mengeksekusi satu instruksi secara paralel pada data yang berbeda pada level lock-step. Komputer vektor adalah salah satu komputer paralel yang menggunakan arsitektur ini. BeberapacontohkomputeryangmenggunakanmodelSIMDadalahILLIACIV,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 supercomputeryang
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.
ProgrammingEnvironmentdanSoftwareTools.Softwareyangdigunakanuntukpemrograman paralel termasuk softwarependukungnya.
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 dapatdilaksanakan (dieksekusi) secara sejajar dengan ulir lainnya, dengan menggunakan cara time slice (ketika satu CPU melakukan perpindahan antara satu ulir ke ulir lainnya) atau multiprocess(ketikaulir-ulirtersebutdilaksanakanolehCPUyangberbedadalamsatusistem). 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-divisionmultipleks), di manasebuah CPU bekerja pada ulir yang berbeda, di mana suatu kasus ditangani tidak sepenuhnya secara serempak, untuk CPU tunggal pada dasarnya benar-benarmelakukan
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 :
Ruangalamat.
Himpunan berkas yangdibuka.
Proses-prosesanak.
Timer-timer.
Snyal-sinyal.
Sumber daya-sumber daya lain milikproses.
Jenis-jenis Thread Berdasarkan Waktu Penciptaannya
Staticthreads
Jumlah thread yang akan dibuat ditentukan saat penulisan dan kompilasi program. Tiapthread langsung dialokasikan stacktetap.
Keunggulan =sederhana.
Kelemahan = tidak fleksibel.
Dynamicthreads
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
Single ThreadProcess
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.
MultithreadProcess
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.
Manfaat Thread
Thread bermanfaat untuk Multithreading yang berguna untuk Multiprocessor dan Singleprocessor.
Kegunaan untuk system Multiprocessor adalah :
Sebagai unit pararel atau tingkat granularitas pararelisme.
Peningkatan kinerja disbanding berbasisproses.
Kegunaan Multithreading pada Singleprocessor adalah :
Kerja foreground dan background sekaligus di satuaplikasi.
Penanganan asynchronous processing menjadi lebihbaik.
Mempercepat eksekusiprogram.
Pengorganisasian program menjadi lebihbaik.
Model Multithread
User (pengguna)thread
User thread didukung di atas kernel dan diimplementasi oleh thread library pada user level. library menyediakan fasilitas untuk pembuatan thread, penjadualan thread, dan managemen
threadtanpadukungandarikernel.Didalamfasilitasuser-levelthreadyangmurni,semuatugas manajemen thread dilakukan oleh aplikasi dan kernel tidak mengetahui keberadaanthread.
Tiga kunci thread libraries :
POSIXPthread
Win32thread
Javathread
Adapun kelemahannya yang dialami yaitu apabila kernelnya merupakanthread tunggal maka apabila salah satu user-level thread menjalankan blockingsystem call maka akan mengakibatkanseluruhprosesdiblokwalaupunadathreadlainyangdapatjalandalamaplikasi tersebut.
Kernelthread
Kernel thread didukung langsung oleh sistem operasi. Pembuatan, penjadualan, dan managemen thread dilakukan oleh kernel pada kernel space.Pembuatan dan pengaturankernel thread lebih lambat dibandingkan userthread.
Keuntungannyaadalahjikasebuahthreadmenjalankanblockingsystemcallmakakerneldapat menjadualkan thread lain di aplikasi untuk melakukaneksekusi. Pada lingkungan multiprocessor, kernel dapat menjadwal thread-thread pada processor yangberbeda.
Contoh sistem operasi yang mendukung kernel thread adalah Windows NT, Solaris, Digital UNIX.
Thread Libraries
Thread libraries menyediakan pemrogram dengan API untuk menciptakan dan memanage thread.
Dalam pengimplementasiannya ada dua cara, diantaranya:
Keseluruhan library pada ruangpemakai.
Kernel-support library yang didukung dengan OS. Berdasarkan PemetaanThread
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 GreenThread
GNU PortableThread
One-to-One
Setiap user-level thread memetakan ke kernel thread, akan tetapi user thread hanya dapat menggunakan satu kernel thread.
Contoh :
WindowsNT/XP/2000
Linux
Solaris 9 andlater
Many-to-Many
Mengijinkan beberapa user-level thread memakai beberapa kernelthread.
Mengijinkan system operasi untuk menciptakan beberapa kernelthread.
Keuntungan dari sistem ini ialah kernel thread yang bersangkutan dapat berjalan secara paralel padamultiprosessor.
Keuntungan Thread
Terdapat empat keuntungan utama dari program yang multithreading yaitu sebagai berikut:
Responsiveness
Membuat aplikasi yang interakti' menjadi
multithreadingdapatmembuatsebuahprogramterusberjalanmeskipunsebagiandariprogram tersebutdiblokataumelakukanoperasiyangpanjang,karenaitudapatmeningkatkanrespons
kepada user. Sebagai contohnya dalam web browser yang multithreading, sebuah threaddapat melayani permintaan user sementara thread lain berusaha menampilkanimage.
ResourceSharing
Thread berbagi memori dan sumber daya dengan thread lain yang dimiliki oleh proses yang sama. Keuntungan dari berbagi kode adalah mengi8inkan sebuah aplikasi untuk mempunyai beberapa thread yang berbeda dalam lokasi memori yang sama.
Economy
Dalam pembuatan sebuah proses banyak dibutuhkan pengalokasian memori dansumber daya. Alternatifnyaadalahdenganuserthread,karenathreadberbagimemoridansumberdayaproses yangmemilikinyamakaakanlebihekonomisuntukmembuatdancontextswitchthread.Akan sulit untuk mengukur perbedaan waktu antara proses dan thread dalam hal pembuatan dan pengaturan, tetapi secara umum pembuatan dan pengaturan proses lebih lama dibandingkan thread.PadaSolaris,pembuatanproseslebihlama24kalidibandingkanpembuatanthread,dan context switch proses 5 kali lebih lama dibandingkan context switchthread.
Utilization of multiprocessorarchitectures
Keuntungan dari multithreading dapat sangat meningkat pada arsitektur
multiprocessor, dimana setiap thread dapat berjalan secara pararel di atas processor yang berbeda. Pada arsitektur processor tunggal, CPU menjalankan setiap thread secara bergantian tetapihal ini berlangsung sangat cepat sehingga menciptakan ilusi pararel, tetapi padakenyataannyahanyasatuthreadyangdijalankanCPUpadasatu-satuanwaktu(satu-satuan waktu pada CPU biasa disebut time slice atauquantum).
Thread Programming Thread di Linux
-GNU/Linux menggunakan POSIX Standar Thread API
-Dikenal dengan pthread
-Program dengan thread harus di-compile dengan "-lpthread" contoh : gcc testhread.c -o thread-lpthread
Program diidentifikasikan dengan threadID
-Type data : pthread_t
Fungsi-fungsi programming pthread :
pthread_t = tipe datathread
pthread_mutex_t = tipe data mutex thread
pthread_create = int pthread_create(pthread_t *thread, const pthread_attr_t *attr,void
*(*start_routine)(void*), void *arg); Parameter : Pertama-->thread ID
Kedua >thread atribut (NULL untuk default atribut)
Ketiga >thread yang ingin dijalankan
Keempat-->parameter untuk fungsi yang dijalankan
Fungsi yang digunakan untuk menciptakan thread baru dalam suatu proses dengan atribut ditentukanolehattr.JikaattrdiisiNULL,atributdefaultakandimuat.Jikapemanggilanfungsi berhasil, fungsi akan menyimpan ID dari thread ciptaan pada rujukan yang ditunjukthread
pthread_detach = int pthread_detach(pthread_tthread);
Fungsi ini digunakan untuk mengindikasikan pada implementasi bahwa ruang penyimpanan thread pada thread bisa diminta kembali ketika thread berakhir
pthread_cancel = int pthread_cancel(pthread_tthread);
Fungsi ini digunakan untuk meminta agar thread dibatalkan. Kondisi kemampuan membatalkan dan tipedari thread yang dituju menentukan kapan pembatlan terjadi.
pthread_mutex_lock = int pthread_mutex_lock(pthread_mutex_t*mutex);
Fungsiinidigunakanuntukmengunciobjekmutexyangdirujukolehmutex.Jikamutexsudah dikunci,thradpemanggilakanditahanhinggamutexmenjaditersedia(tidakterkunci).Operasi inimengembalikanobjekmutexyangdirujukolehmutexpadakeadaanterkuncidenganthread pemanggil sebagaipemiliknya
pthread_mutex_unlock = int pthread_mutex_unlock(pthread_mutex_t*mutex);
Fungsi ini berguna untuk membebaskan objek mutex yang dirujuk mutex. Bagaimana cara mutex dibebaskan tergantung dari tipe atribut mutex
pthread_mutex_destroy = int pthread_mutex_destroy(pthread_mutex_t*mutex);
Fungsi ini menghancurkan objek mutex yang dirujuk oleh mutex, sehingga objek tersebut menjadi tidak terinisialisasi.
PENGANTAR MASSAGE PASSING
Pemrosesan Paralel adalah komputasi dua atau lebih tugas pada waktu bersamaan dengan tujuan untuk mempersingkat waktu penyelesaian tugas-tugas tersebut dengan cara mengoptimalkan resource pada sistem komputer yang ada. Pemrosesan paralel dapat mempersingkat waktu ekseskusi suatu program dengan cara membagi suatu program menjadi bagian-bagian yang lebih kecil yang dapat dikerjakan pada masing-masing prosesor secara bersamaan. Suatu program yang yang dieksekusi oleh n prosesor diharapkan dapat mempersingkat waktu eksekusi n kali lebih cepat. Salah satu komputer yang menggunakan metode pemrosesan paralel adalah SMP (Single Multi Processor). Sebuah sistem paralel setidaknya terdiri dari Message Passing Interface (MPI) dan sebuah pengatur beban kerja (job scheduler).
Pada bagian komputasi parallel ini akan dibahas tentang Message Passing dan OpenMP. Pembahasan Jurnal:
AlgoritmagenetikasekuensialuntukmenyelesaikanContainerLoadingProblembekerjahanya dengan menggunakan satu processor saja meskipun dijalankan pada system multicore.Tujuan dari penelitian ini adalah untuk mengoptimalkan kinerja system multicore. Untuk mengoptimalkan kinerja system multicore diperlukan adanya paralelisasi algoritma genetika untuk menyelesaikan Container LoadingProblem.
Dalam penelitian ini paralelisasi yang digunakan adalah paralelisasi shared memory menggunakan OpenMP. Paralelisasi dalam OpenMP dilakukan melalui penyisipan pragma OMP paralel. Dari algoritma genetika serial Container Loading Problem akan diparalelisasi menggunakan OpenMP menjadi algoritma genetika parallel Container Loading Problem. Selanjutnya akan dilakukan pengujian waktu eksekusi algoritma dan perhitungan speedup.
Hasil dari penelitian ini berupa hasil pengujian kinerja algoritma parallel yang menunjukkan bahwa waktu komputasialgoritma paralel lebih kecil dari algoritma sekuensial sebelum diparalelisasi menggunakan OpenMP. Waktukomputasi yang lebih kecil ini menyatakan efisiensi kinerja algoritma paralel yang lebih baik dari algoritmasekuensial.Peningkatan
efisiensiinijugadapatdiidentifikasidariSpeedupparalelisasiyangsemakinbesar.Kesimpulan diperoleh dari penelitian ini adalah bahwa paralelisasi terhadap algoritma genetika untuk menyelesaikan Container Loading Problem akan meningkatkan efisiensi waktu komputasi melalui pemanfaatan sistem multicore.
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 menerimapesanyangterdiridarinolataulebihbyte,strukturdatayangkompleks,ataubahkan segmenkodekeproseslainnyadandapatmelakukansinkronisasi.ParadigmaMessagepassing yaitu:
Banyak contoh dari paradigma sekuensial dipertimbangkanbersama-sama.
Programmer membayangkan beberapa prosesor, masing-masing dengan memori, dan menulis sebuah program untuk berjalan pada setiapprosesor.
Proses berkomunikasi dengan mengirimkan pesan satu samalain.
Terdapat beberapa metode dalam pengiriman pesan yaitu :
Synchronous MessagePassing
Pengirimmenungguuntukmengirimpesansampaipenerimasiapuntukmenerimapesan.Oleh karena itu tidak ada buffering. Selain itu Pengirim tidak bisa mengirim pesan untuk dirinya sendiri.
Ansynchronous MessagePassing
Pengirim akan mengirim pesan kapanpun dia mau. Pengirim tidak peduli ketika penerima belum siap untuk menerima pesan. Oleh karena itu diperlukan buffering untuk menampung pesansementarasampaipenerimasiapmenerimapesan.Selainitupengirimdapatpesanuntuk dirinyasendiri.
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 dibagidiantara thread-thread dan dapat terlihat dari setiap thread. Terkadang program akan membutuhkan variabeldengannilaithreadspesifik.Jikasetiapthreadmemilikivariabelduplikatakansangat berpotensi memiliki nilai yang berbeda-beda pada setiap variabel duplikattersebut.
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.
