Sistem Berkas Penggabungan Eksternal dengan Keseimbangan P-way

PENGGABUNGAN EKSTERNAL DENGAN KESEIMBANGAN P-WAY

            Karena kendala utama untuk menggunakan pengurutan gabungan sebagai rutin pengurutan eksternal adalah diperlukannya ruitin pengurutan eksternal jumlah besar berkas pada saat awal, maka perlu melakukan modifikasi proses penggabungan untuk membatasi jumlah berkas yang terbuka.

            Berkas asli didekomposisi menjadi beberapa “run” dengan cara melkukan pengurutan internal terhadap sejumlah besar blok rekaman yang dapat dibuat dalam memori utama. “Keseimbangan” dalam nama ini merupakan hasil dari kenyataan bahwa “run” dihasilkan merata pada P buah berkas eksternal. Berkas-berkas tersebut bisa berada secara fisik pada disks dari pada penggunaan pita-magnetik karena disks memiliki akses yang lebih cepat, tidak memerlukan penggulungan-balik (rewinding), dan memungkinkan rekaman dapat di akses secara langsung.

“Run” awal pada masing-masing berkas input P digabung dengan menggunakan pengurutan gabungan. Output gabungan membentuk “run”  yang besarnya dalah P kali ukuran “run” yang asli; “run” yang dihasilkan tersebut secara merata berada pada set kedua berkas output P. Ketika semiua “run” pada berkas P asli telah di proses, maka satu “pass” sudah selesai. Pada “pass” berikutnya, berkas output dari “pass” yang dihasilkan sebelumnya menjadi berkas input yang sebelumnya menjkadi berkas output. “Pass” berikutnya menggabungkan berkas yang dihasilkan dari “pass” pertama membentuk berkas yang memiliki ukuran sebesar P-kali ukuran sebelumnya.

Proses penggabungan terus berjalan membentuk “run” yang lebih besar sampai diperoleh sebuah “run” tunggal, yaitu berkas yang sudah di urutkan. Karena ada berkas masukan Yang terpisah dari berkas output, maka diperlukan berkas sebanyak total 2P. Jika digunakan pita-magnetik, karena di perlukan berkas yang cukup besar, maka dibutuhkan sebanyak 2P penggerak pita-magnetik. Keseimbangan dua arah pengurutan gabungan membutuhkan empat berkas. Jika jumlah penggerak pita-magnetis yang tersedia atau berkas adalah F, berjumlah gasal, maka jumlah berkas masukan berada di antaranya.

Contoh: dengan asumsi  bahwa digunakan berkas disk dengan P = 3, maka data standar dapat di proses, sebagai berikut :

                                    27, 18, 29, 28, 13, 16, 18 and 53

Untuk ilustrasi, dianggap bahwa ukuran “run” awal berjumlah satu, dalam praktik yang sebenarnya, jelas akan terlibat sejumlah besar rekaman, sehingga jumlah “run” juga akan sangat banyak. Rekaman contoh tersebut kemudian didistribusikan sebagaimana diperlihatkan sebagai berikut :

Disk yang menerima hasil penggabunggabungan rekaman dari “pass” pertama,menjadi disk-input untuk “pass” kedua yang akan menghasilkan berkas urut final,sebagai berikut:

            

PEMBAHASAN

            Jumlah “pass” yang diperlukan dalam pengurutan gabungan P-way seimbang menunjukkan indikasi adanya unjuk-kerja yang baik karena semua rekaman diproses setiap “pass” dan waktu input/output yang diperlukan untuk mengakses rekaman pada penyimpanan tambahan mendominasi waktu untuk melakukan operasi. Sementara itu pengurutan gabungan dua-arah yang seimbang membutuhkan “pass” sebanyak :

                                                           

Dengan r adalah jumlah awal “run”. Dengan kata lain, untuk kisaran “run” sejumlah r, membutuhkan “pass” sejumlah k, dengan 2^k-1 < r ≤ 2^k. Perhatikan bahwa jumlah “pass” adalah sama dengan “pass” yang diperlukan untuk pengurutan gabungan internal jika “run” dianggap sama dengan jumlah berkas awal. Berapa banyak “pass” akan diperlukan jika rekaman standar yang diurutkan dengan algoritma pengurutan gabungan dua-arah yang seimbang dengan “run” awal masing-masing terdiri atas dua rekaman ? karena r akan menjadi lima dalam kasus tersebut, maka tiga “pass” akan diperlukan.