Hasil Pencarian  ::  Simpan CSV :: Kembali

"Penggabungan dua himunan terutut (merging) merupakan salah satu bahan pembahasan dalam bidang ilmu komputer, khususnya yang berkenaan dengan analisa dan kompleksitas algoritma serta kecepatan komputasi. Salah satu usaha untuk nenigkatkan kecepatan komputasi masalah penggabungan ialah dengan menggunakan proses paralel. Oleh karena itu penulis membahas algoritma paralel Penggabungan dari dua buah himpunan terurut pada model komputasi paralel SM CREW (Shared-Memory concurrent Read, Exclusive Write) dari kelas komputer SIMD (Single Instruction Stream Multiple Data Stream) dan SM EREW (Shared-Memory Exlusive Read, Exclusive Write) dari kelas Computer SIMD (Single Instruction Stream Multiple Data Stream), serta analisa algloritma-algoritma tersebut. Untuk implementasinya dipakai metoda simulasi dengan bahasa pemrogaman ADA, karena bahasa pemrogaman ini mendukung dalam simulasi pemrosesan seeara paralel. Dengan membuat simulasi ini dapat diperoleh hasil yang bisa dipakai untuk memperkirakan kemungkinan jika diimplementasikan pada kondisi yang sesungguhnya."

"ABSTRAK Tesis ini membahas disain, implementasi dan analisa kinerja algoritma paralel integrasi numerik adaptif yang mempunyai paradigma tree computation. Implementasi algoritma paralel ini dilakukan pada jaringan komputer PC dengan bahasa pemrograman C yang berbasis PVM (parallel virtual machine). Ujicoba pengukuran dan analisa kinerja dari algoritma tersebut dilakukan pada jumlah slave yang bervariasi dari mesin-mesin komputer yang heterogen. Parameter-parameter yang diukur adalah nilai speedup, efisiensi penggunaan prosesor, computation to communication ratio, job allocation untuk mendapatkan load balancing yang merata, dan distribusi waktu eksekusi. Ada tiga model algoritma paralel yang ditawarkan dalam integrasi numerik adaptif ini. Model pertama menawarkan suatu cara dimana setiap node yang terbentuk pada tree computation akan dikerjakan oleh prosesor yang berbeda. Master akan mengirimkan node-node sebagai sub-sub problem. ke slave-slave secara ternus menerus sehingga semua slave tidak ada yang idle. Hasil yang diterima master belum tentu hasil akhir, sehingga mungkin sekali sub problem tersebut akan dipecah menjadi sub-sub problem bare yang akan dikirim kembali ke slave-slave. Pada solusi model kedua, master mengirim node-node sebagai sub-sub problem ke semua slave. Slave akan melakukan komputasi secara rekursif sampai diperoleh hasil akhir, sehingga terbentuk suatu sub tree computation pada setiap slave. Hasil akhir yang diterima master akan dikumpulkan untuk mendapatkan total hasil akhir. Slave yang telah selesai akan diberi sub problem berikutnya. Sedang pada model ketiga, master membagi problem secara liner sesuai dengan jumlah mesin yang terlibat, tanpa memperhatikan volume beban komputasi dari setiap sub problem. Selanjutnya master dan slave-slave akan melakukan komputasi secara rekursif sampai diperoleh hasil akhir. Jadi baik pada master maupun slave akan terbentuk sub-sub tree computation. Master akan menerima hasil dari setiap slave untuk dikumpulkan menjadi total hasil akhir. "

"ABSTRAKDalam aplikasi pengolahan citra sering digunakan Fast Fourier Transform (M). Tujuan dari penggunakan FFT ini adalah agar citra yang akan diolah, di transformasikan ke dalam daerah frekuensi, sehingga dapat dilewatkan dalam filter. Transformasi yang digunakan pada aplikasi pengolahan citra ini adalah FFT 2 Dimensi. Dibutuhkan waktu yang agak lama untuk melakukan transformasi citra, terutama untuk ukuran citra yang besar seperti 256 x 256 dan 512 x 512. Semakin besar ukuran citra yang ditransformasikan semakin banyak komputasi yang dilakukan, sehingga waktu yang dibutuhkan akan semakin lama. Untuk mempersingkat waktu maka digunakan pemrograman paralel. Algoritma dari aplikasi pengolahan citra ini dibagi menjadi 3 bagian : Transformasi Fourier 2D, Filterisasi, dan Invers Transformasi Fourier 2D. Program paralel ini akan di coba untuk dimplementasikan dan diukur pada jaringan komputer berbasis PVM yang terdapat di PAU Universitas Indonesia. Akan dibandingkan waktu komputasi pada keadaan serial dari paralel dengan menggunakan beberapa prosesor. Sehingga nampak jelas adanya penambahan percepatan komputasi pada pemrograman paralel. Dengan melihat penambahan percepatan komputasi akan terlihat efektifitas dari pemaralelan program nampak lebih efektif apabila dibandingkan dengan program serial, selanjutnya bisa di analisa faktor apa saja yang membuat percepatan komputasi pada program paralel tidak optimal."

"Tugas akhir ini menjelaskan tiga buah algoritma untuk menyelesaikan masalah knapsack 0/1 berkendala tunggal. Ketiga algoritma tersebut, terdiri atas sebuah algoritma serial dan dua buah algoritma paralel. Algoritma serial yang dibahas, diperkenalkan oleh Horowitz dan Sahni. Algoritma paralel yang pertama diperkenalkan oleh Lee, Shragowitz dan Sahni, sedangkan, algoritma kedua oleh Lin dan Storer. Prinsip-prinsip pemrograman dinamik digunakan pada setiap algoritma untuk memperoleh penyelesaian masalah. Secara serial masalah knapsack 0/1 memiliki kompleksitas 0(mc). Jika dengan menggunakan algoritma dari Lee dapat diselesaikan dalam 0(mc/n + c.2log n + c2), sedangkan dengan Lin-Storer dalam 0 (mc log n)/n). Untuk memperjelas pemahaman terhadap proses paralel tersebut, dibuat sebuah simulasi yang berdasarkan algoritma paralel Lin-Storer."

"Untuk menghitung nilai suatu polinomial berderajat n-1 dengan variabel tunggal pada n buah titik yang berbeda secara serempak dapat dilakukan secara paralel dengan menerapkan metode Homer (secara serial), dimana n buah prosesor masing-masing mengevaluasi polinomial untuk satu titik. Cara tersebut memerlukan 0 (n2) operasi aritmatik dan 0 (n) waktu paralel. Skripsi ini membahas tentang suatu algoritma yang menerapkan metode Divide and Conquer dan memberikan waktu kompleksitas paralel 0 (log3 n) dengan hanya menggunakan 0 (n log3 n) jumlah operasi aritmatik. Simulasi paralelnya dapat dilihat dalam program-program lampiran."

"Tugas akhir ini membahas mengenai Pembentukan Algoritma Parallel untuk menyelesaikan Masalah Jalur Terpendek. Secara umum, masalah jalur terpendek dapat dibedakan menjadi dua jenis masalah, yaitu single sourcedan all pairs, dengan ukuran masalah n (banyaknya vertex). Metode yang dipakai untuk menyelesaikan masalah jalur terpendek, yaitu metode Dijkstra dan Floyd. Metode Dijkstra dan Floyd dapat diinterpretasikan sebagai algoritma parallel yang menggunakan model Shared Memory (SM) SIMD (Single Instruction, Multiple Data), dengan N processor. Algoritma parallel Dijkstra dalam menyelesaikan masalah jalur terpendek single source menggunakan jenis akses memori EREW/CREW, memiliki kompleksitas waktu O(n log2 n), untuk N 2- n/log2 n dan O(n2/N), untuk N < n/log2 n. Dan algoritma Floyd untuk menyeselesaikan masalah jalur terpendek all pairs menggunakan jenis akses memori CREW, dalam O(n3IN) waktu, untuk N < n."

"Pemrograman paralel pada mesin berbasis transputer dengan menggunakan peranti lunak bantu konvensional, seperti INMOS ANSI C, temyata cukup mempersulit pemakai. Kesulitan tersebut timbul karena pemakai harus mengetahui berbagai masalah teknis pemrograman dan aspek mesin dari transputer itu sendiri. Kesulitan tersebut dapat diatasi dengan membangun suatu wahana pemprograman paralel yang dapat menyembunyikan berbagai aspek teknis tersebut. Untuk mengatasi kesulitan tersebut, penulis melakukan penelitian yang bertujuan untuk membangun TransPVM, yaitu wahana pemrograman paralel berbasis message passing pada mesin berbasis transputer, dengan mengimplementasikan primitif-primitif dari Parallel virtual Machine (PVM). Dengan TransPVM pemprograman paralel dapat dinyatakan dalam sintaks PVM sehingga dapat diterapkan baik pada lingkungan PVM maupun TransPVM tanpamelakukan banyak perubahan pada program. Hasil yang diharapkan dari penelitian ini adalah: (l) TransPM dapat mempermudah pemrograman pada mesin berbasis transputer; (2) TransPVM dapat mempersingkat langkah pemrograman yang diperlukan pada mesinberbasis transputer."