ALGORITMA PARALEL ODD EVEN TRANSPOSITION PADA MODEL JARINGAN NON-LINIER

Abstract

Odd-even-transposition adalah suatu algoritma paralel yang merupakan pengembangan dari algoritma sekuensial “bubble sortâ€. Algoritma odd-even-transposition ini didesain khusus untuk model jaringan array linier (homogen). Untuk n elemen data, kompleksitas waktu dari algoritma bubble sort adalah O(n2), sedangkan pada odd-even-transposition yang bekerja di atas n prosesor adalah ï‘(n). Ada peningkatan kecepatan waktu pada kinerja algoritma paralel ini sebesar n kali dibanding algoritma sekuensialnya. Hypercube dimensi k adalah model jaringan non-linier (non-homogen) terdiri dari n = 2k prosesor, di mana setiap prosesor berderajat k. Model jaringan Fibonacci cube dan extended Lucas cube masing-masing merupakan model subjaringan hypercube dengan jumlah prosesor < 2k prosesor dan maksimum derajat prosesornya adalah k. Pada paper ini, diperlihatkan bagaimana algoritma odd-even-transposition dapat dijalankan juga pada model jaringan komputer cluster non-linier hypercube, Fibonacci cube, dan extended Lucas cube dengan kompleksitas waktu O(n). Odd-even-transposition is a parallel algorithm which is the development of sequential algorithm “bubble sortâ€. Odd-even transposition algorithm is specially designed for linear array network model (homogeneous). For n data elements, the time complexity of bubble sort algorithm is O(n2), while the odd-even-transposition that works with n processor is ï‘(n). There in an increase in the speed of time on the performance of this parallel algorithms for n times than its sequential algorithm. K-dimensional hypercube is a non-linear network model (non-homogeneous) consists of n = 2k processors, where each processor has k degree . Network model of Fibonacci cube and extended Lucas cube are the hypercube sub-network model with the number of processors <2k processors and maximum processor degree is k. In this paper, it is shown how the odd-even-transposition algorithm can also be run on non-linear hypercube cluster, Fibonacci cube, and extended Lucas cube computer network model with time complexity O(n).