Computer File
Finite concurrent disjoint sets dengan sifat linearizable dan bounded wait-free
Hampir seluruh CPU yang dijual pada saat sekarang memiliki prosesor lebih dari satu. Program sekuensial hanya memberdayakan 1 prosesor saja, walaupun di dalam CPU memiliki lebih dari satu prosesor. Untuk bisa memberdayakan lebih dari 1 prosesor, diperlukan program yang berjalan secara paralel. Sebuah program menyimpan data-data yang dibutuhkannya di dalam struktur data. Jika program ingin bekerja secara paralel, maka struktur datanya pun harus bisa diakses secara paralel. Disjoint sets adalah sebuah struktur data yang banyak digunakan untuk menyelesaikan masalah minimum spanning tree dan graph connectivity problem. Pada penelitian ini, dirancang struktur data disjoint sets dengan representasi rooted-tree yang dapat bekerja di lingkungan paralel. Disjoint sets yang dibangun memiliki sifat bounded wait-free dan linearizable. Ukuran disjoint sets(N) terbatas, dan batasannya ditentukan terlebih dahulu di awal. Ada 3 operasi dasar yang dimiliki yaitu makeset, findset, dan union. Operasi makeset digunakan untuk membuat himpunan baru di dalam disjoint sets. Kompleksitas untuk operasi makeset adalah O(N). Operasi findset digunakan untuk mencari perwakilan dari himpunan. Kompleksitas untuk operasi findset adalah O(N). Operasi union digunakan untuk menggabungkan dua himpunan yang saling lepas. Kompleksitas untuk operasi union adalah O(N3). Disjoint sets diimplementasikan dalam bahasa pemrograman Java. Hasil dari implementasi diperiksa dengan cara model checking menggunakan kakas Java Path Finder.
Kata-kata kunci: Disjoint Sets, Paralel, Linearizable, Bounded Wait-Free, Java Path Finder, Struktur Data, Concurrent
Barcode | Tipe Koleksi | Nomor Panggil | Lokasi | Status | |
---|---|---|---|---|---|
skp31437 | DIG - FTIS | Skripsi | INFO VIR f/15 | Perpustakaan | Tersedia namun tidak untuk dipinjamkan - Missing |
Tidak tersedia versi lain