Tugas Algoritma & Pengolahan Pararel
Kelompok:
Andhika Nugrahatama 50405070
Mariska Chairunnisa 50405457
M Arief Rahman Hakim 50405485
Santoso Budiman 50405665
Yang Citra Derisa 50405757
Kelas 4IA08
A PARALLEL MERGING ALGORITHM AND ITS IMPLEMENTATION WITH JAVA THREADS
ALGORITMA MERGE PARALLEL DAN IMPLEMENTASIYA DENGAN JAVA THREAD
SOWMYA PRABHA NAGARAJA sowmyaprabha@yahoo.com
YUAN PAN yuanpan33@usa.net
MEHDI BADII mbadii@pace.edu
Pace University,
Pleasantville, NY
Keberhasilan ilmu komputer untuk menjelaskan secara akurat dan memodelkan dunia nyata telah mendorong permintaan akan komputasi murah. Ilmuwan terus mencari cara untuk menguji batas teori, menggunakan komputasi kinerja tinggi untuk mengizinkan mereka untuk mensimulasikan sistem lebih realistis dengan lebih detail. Komputasi paralel menawarkan cara untuk menanggulangi masalah ini dengan biaya efektif.
Salah satu alasannya merupakan alasan ekonomi. Dengan membuat penggunaan komponen “off the shelf”, komputer paralel dapat menawarkan kinerja tinggi dengan harga lebih rendah daripada mesin yang menggunakan prosesor yang khusus. Selain itu, skalabilitas dari komputer paralel memungkinkan mereka untuk ditingkatkan sebagai kebutuhan. Dimana pada arsitektur seri upgrade prosesor adalah dengan menjadikan prosesor sebelumnya usang, arsitektur paralel dapat, secara teori, ditingkatkan dengan menambah prosesor lagi.
Namun demikian, ada alasan lain, dasar hukum fisik, yang pada akhirnya akan membatasi kecepatan prosesor tunggal, yang terlepas dari ekonomi. Gerakan informasi merupakan bentuk dasar dari komputer, tetapi kecepatan ini pada akhirnya dibatasi oleh kecepatan cahaya. Jika bukan jarak dijalani oleh informasi ini berkurang, akhirnya kebutuhan untuk menghindari ketidakpastian diperkenalkan oleh kuantum mekanik akan membatasi perpecahan di sepanjang jalan yang dapat dijalani oleh informasi.
Kedua alasan perekonomian dan fisika, digabungkan dengan skalabilitas yang melekat pada komputer paralel, mengarah ke masa depan komputasi performa tinggi yang didasarkan pada beberapa jalan pada ide dari parallelism.
Banyak pekerjaan telah dilakukan dalam bidang ini menggunakan berbagai teknik. Untuk contoh,
- algoritma pada distribusi memori komputer asynchronous[1] dimana algoritma mengurangi biaya operasi yang menggabungkan dan komunikasi, serta sebagian memecahkan masalah load balancing,
- metodologi untuk memprediksi kinerja algoritma paralel pada komputer paralel[2]. Metodologi ini terdiri dari dua langkah.Perrtama, mesin dikarakterisasikan dengan mengenumerasikan primitif operasi yang mampu melakukan bersama biaya operasi masing-masing. Selanjutnya, adalah suatu algoritma dianalisa oleh membuat tepat hitungan jumlah kali algoritma melakukan tiap jenis operasi.
- Penyortiran paralel menurut Overpartitioning [3] - Pendekatan ini membatasi biaya komunikasi
bergerak oleh setiap elemen antara prosesor paling banyak sekali, dan mengarah ke balancing dengan probabilitas tinggi.
Analisis Algoritma Paralel
Analisis algoritma merujuk kepada proses penentuan bagaimana suatu algoritma yang baik, yaitu bagaimana cepat, seberapa mahal untuk berjalan, dan seberapa efisien dalam penggunaan sumber daya yang tersedia. Begitu algoritma untuk beberapa masalah telah dirancang, biasanya dievaluasi dengan menggunakan kriteria sebagai berikut: running time, jumlah prosesor yang digunakan, dan biaya. Selain standar metrik ini, sejumlah teknologi lainnya terkait langkah-langkah yang terkadang digunakan ketika diketahui bahwa algoritma ini telah berjalan pada komputer yang didasarkan pada teknologi tertentu.
Sejak mempercepat perhitungan menjadi alasan utama di belakang kami dalam membangun paralel komputer, ukuran yang paling penting dalam mengevaluasi sebuah algoritma paralel karena itu dengan running time (n). Ini didefinisikan sebagai waktu yang diambil oleh algoritma untuk memecahkan masalah pada komputer paralel, yang berlalu dari saat algoritma mulai hingga berakhir.
Kedua kriteria paling penting dalam mengevaluasi sebuah algoritma paralel adalah jumlah prosesor yang diperlukan untuk memecahkan masalah.
Biaya algoritma paralel didefinisikan sebagai produk dari dua tindakan sebelumnya, maka
Biaya = paralel waktu berjalan * jumlah prosesor yang digunakan
i.e. c (n) = p (n) * t (n)
dimana p (n) adalah jumlah prosesor dan t (n) adalah running time paralel
Disamumsikan bahwa batas bawah terikat pada jumlah yang diperlukan dalam operasi berurut dalam worst case untuk memecahkan masalah. Jika algoritma paralel yang cocok untuk masalah ini biaya pasti akan lebih rendah dalam multiplicative faktor konstan, maka algoritma adalah biaya yang optimal. J paralel algoritma biaya tidak optimal jika berurut algoritma yang ada saat ini berjalan lebih kecil dibandingkan dengan biaya algoritma paralel.
Pendekatan Konseptual Kami
Bagus untuk menerapkan model arsitektur parallelism yang dapat diskala, setidaknya pada prinsipnya, sebagai masalah ukuran meningkat. Parallelism yang didukung oleh arsitektur ini adalah eksplisit dalam arti bahwa biasanya mereka secara eksplisit mendukung sebuah model pemrograman paralel. Arsitektur model ini telah diklasifikasikan bersama berbagai axes: SIMD atau MIMD, bersama memori-memori atau didistribusikan, untuk tujuan umum atau khusus, digabungkan dengan longgar atau ketat, penggunaan interkoneksi jaringan statis versus dinamis , dll.
Karya ini berkaitan dengan menggabungkan algoritma paralel. Algoritma yang asli dirancang untuk CREW SM SIMD komputer. SIMD arsitektur terdiri dari kumpulan prosesor homogen yang menjalankan instruksi secara bersamaan pada berbagai item data. Arsitektur SIMD akan sangat efisien untuk komputasi reguler pada kumpulan data besar sebagai typified oleh matriks computations padat. Karena arsitektur SIMD memiliki satu tempat program kontrol, desain dan debugging program maka biasanya lebih mudah daripada untuk arsitektur MIMD. Dengan demikian, keuntungan utama dari model ini yang kedua adalah hardware dan software desain masalah yang relatif sederhana.
Algoritma ini ditingkatkan dan dilaksanakan dengan fitur Multithreading Java. Yang dikehendaki
dari menggabungkan algoritma paralel, seperti jumlah thread yang digunakan oleh algoritma, adalah sub linear dan adaptif. Waktu running dari algoritma secara signifikan lebih kecil dibandingkan dengan algoritma berurut. Biaya dari algoritma yang optimal.
Untuk dua sequence diurutkan dari ukuran r dan s, dan dalam kasus terburuk di mana r = s = n, waktu putar O ((n / N) + log n), dimana N merupakan jumlah thread. Algoritma adalah biaya yang optimal untuk N = n / log n.
Pelaksanaan kami dan Algoritma
Pelaksanaan kami memiliki delapan kelas Java:
- Main - Menciptakan yang dimulai N threads
- Generator - mempopulasikan 2 array yang harus digabungkan dengan menghasilkan nomor acak
- MyThread - kelas dimana semua pekerjaan dilakukan seperti yang dijelaskan di bawah
- Pasangan - pasangan lain yang dijelaskan pada langkah 3 di bawah
- Tripel - menghasilkan triples dijelaskan pada Langkah 2 di bawah
- Printer - cetak output yaitu array yang telah digabung ke file
- Sorter - dua jenis input non array dalam urutan atas ke bawah
- Waiter - ini adalah kelas di mana semua thread menunggu
Algoritma
Biarkan A dan B yang akan diberikan array bersama dengan masing-masing elemen r dan s, diurutkan di
urutan nondecrease. Hal ini diperlukan untuk menggabungkan mereka ke dalam array C.
Seperti disajikan oleh Akl [4], maka algoritma adalah sebagai berikut:
Langkah 1: Algoritma memilih N-1 elemen dari array A untuk bersama array J ‘. J ini membagi N kira-kira sama dalam ukuran segmen. J bersama array B ‘N-1 elemen B juga dipilih. Untuk langkah ini, setiap Pi penyisipan J [i * r / N] dan B [i * r / N] secara paralel ke dalam i lokasi A dan B ‘ masing-masing.
Langkah 2: Langkah ini menggabungkan A dan B ‘menjadi deret bersama V ukuran 2n - 2. Setiap elemen v V merupakan triple terdiri dari elemen A ‘atau B’ diikuti oleh posisinya dalam A ‘atau B’ diikuti oleh nama A atau B.
Untuk langkah ini setiap Pi:
a. Berurut menggunakan prosesor Binary CARI setiap pencarian di array B ’secara paralel untuk menemukan seperti yang terkecil j A ‘[i] < b ' [j]. J jika ada, maka V [i + j -1] diatur oleh triple (A '[i], i, "A"),
lain V [i + N -1] diatur oleh triple (A '[i], i, "A").
b. Berurut menggunakan prosesor Binary CARI setiap pencarian yang array A 'untuk menemukan j terkecil seperti yang B '[i] < a [j]. J jika ada, maka V [i + j -1] ditentukan oleh tiga
(B '[i], i, "B"), jika V [i + N -1] ditentukan oleh tiga (B' [i], i, "B").
Langkah 3: Untuk menggabung A dan B dibagi menjadi array C, dengan indeks dari dua elemen (satu di A dan satu di B) di mana setiap prosesor adalah untuk mulai yang menggabungkan computed bersama dalam array T yang memerintahkan pasangan. Langkah ini dijalankan sebagai berikut:
a. P1 set T [1] oleh (1,1).
b. Setiap Pi, i> = 2, memeriksa apakah V [2i -2] adalah sama dengan (A [k], k, “A”) atau tidak. Jika sama maka pencarian Pi B
menggunakan Binary CARI untuk menemukan j terkecil seperti yang B [j]> A [k] dan set T [i] oleh (k * r / N, j),
lain J Pi pencarian menggunakan Binary CARI untuk menemukan j terkecil sedemikian rupa sehingga
J [j]> B ‘[k] dan set T [i] oleh (j, k * s / N).
Langkah 4: Masing-masing Pi, i
Perbaikan kami ke Algoritma
Kami telah membuat perbaikan berikut pada algoritma:
(a). Set N = minimum (r, s, p), di mana r, s, dan p adalah ukuran array A, B, dan jumlah prosesor di
sistem masing-masing. Asumsi ini menjamin bahwa jumlah prosesor yang tidak lebih besar dari ukuran setiap array. Mengubah nama "berurut Bergabung" ke "Teruskan berurut Bergabung" dan menentukan "Mundur berurut Bergabung" untuk menggabung dua subsequences dari ujung kanan subsequences.
(b). Pada langkah 4, setelah prosesor Pi merges nya subsequences, ia menemukan sibuk Pk prosesor, dan panggilan "MundurBerurut Bergabung "untuk menggabungkan subsequences dari Pk dari hak mereka berakhir, sementara Pk mereka adalah menggabungkan
dari kiri berakhir.
Analisis dari Algoritma
Meskipun kami telah meliputi penyortiran prosedur dalam program kami, kami tidak akan menyertakan analisis yang langkah karena fokus pada adalah menggabungkan dua array diurutkan. Prosedur sorting yang disertakan hanya untuk memberikan ketidaktetapan untuk seluruh program tersebut.
Langkah 1: Semua prosesor beroperasi secara paralel. Setiap prosesor computes dua subscripts; maka ini
langkah memerlukan waktu konstan.
Langkah 2: Langkah ini terdiri dari dua berurut Binary CARI prosedur diterapkan ke urutan
panjang dari N-1. Sebuah pernyataan berikut tugas masing-masing prosedur. Hal ini memakan waktu O (log N) waktu.
Langkah 3: Langkah 3 (a) terdiri dari konstan-waktu tugas.
Langkah 3 (b) paling banyak membutuhkan O (log s) waktu.
Langkah 4: Pengamatan: --
Array yang berisi 2n V - 2 unsur yang memisahkan C menjadi 2n - 1 dengan subsequences Ukuran maksimum sebesar (r / N + s / N). Ukuran maksimum ini terjadi jika, misalnya, satu dari unsur a'i A 'sama dengan sebuah elemen b'j dari B'. Maka r / N elemen kecil dari atau sama dengan a'i (dan lebih besar daripada
atau sama dengan a'i-1) juga lebih kecil dari atau sama dengan b'j. Demikian pula s / N elemen atau lebih kecil daripada setara dengan b'j (dan lebih besar dari atau sama dengan b'j, dan b'j-1) juga lebih kecil dari atau sama dengan a'i. Pada langkah 4 setiap dua prosesor menciptakan seperti subsequences C yang jumlah ukuran tidak lebih besar dari 2 (r / N + s / N),
kecuali PN, yang hanya menciptakan satu subsequence dari C. Penyalahgunaan berikut bahwa berurut Bergabung prosedur yang memakan waktu paling banyak O ((r + s) / N) waktu.
Pada kasus terburuk, r = s = n. Sejak n> = N, yang menjalankan algoritma dari waktu didominasi oleh
waktu yang diperlukan oleh Langkah 3 dan 4. Jadi
t (2n) = O ((n / N) + log n)
Sejak p (2n) = N, c (2n) = p (2n) * t (2n) = O (n + Nlogn), dan algoritma adalah biaya yang optimal ketika
N < = n / logn.
Kesimpulan
Tidak adanya komputer multiprocessor di lembaga ini bukan merupakan kendala dalam penelitian melibatkan algoritma paralel karena kita dapat menggunakan teknik seperti Multithreading yang tersedia dalam bahasa pemrograman seperti bahasa Java atau menggunakan simulator tersedia untuk algoritma paralel [5] di mana fungsi-fungsi simulator membolehkan programmer untuk menangani komunikasi dan sinkronisasi kebutuhan satu algoritma di tingkat yang lebih tinggi daripada sistem UNIX multiprocessing panggilan, sementara berkonsentrasi pada desain yg berbarengan
algoritma. Anyhow, juga memungkinkan untuk menggunakan sistem seperti panggilan tunggu dan sinyal dalam UNIX untuk tujuan ini [6].
References
[1] Efficient Implementation of Sorting Algorithms on Asynchronous Distributed-Memory Machine
(1993)
Zhou B. B., Brent R. P. and Tridgell A. Computer Sciences Laboratory. The ICPADS: International
Conference on Parallel and Distributed Systems, National Tsing Hua University, Hsinchu, Taiwan,
Republic of China
[2] An Experimental Analysis of Parallel Sorting Algorithms (1998)
Guy E. Blelloch Carnegie Mellon University Pittsburgh, PA 15213 C. Greg. Theory of Computing System
[3] Parallel Sorting by Overpartitioning (1994)
Hui Li and Kenneth C. Sevcik February 1994 Computer Systems Research.SPAA: Annual ACM
Symposium on Parallel Algorithms and Architectures
[4] The Design and Analysis of Parallel Algorithms (1989)
Selim G. Akl Prentice Hall, Inc.
[5] Simulating the DYNIX Operating System Parallel Programming Interface on a UNIX System
(1998)
M. Badii, Sofrware-Practice and Experience, Vol. 28(5), 463-480 (998)
[6] Dataflow Simulator
M. Badii and M. Mahimtura. Proceedings of Tenth Annual ESCC Conference, October 21-22 1994.
Jurnal Original:
http://www.research.ibm.com/masplas/masplas01/nagaraja.pdf
