ALGORITMA PARALEL ODD EVEN TRANSPOSITION PADA MODEL JARINGAN NON-LINIER

Ernastuti ., Ravi A. Salim, Haryanto .

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).

Keywords


bubble sort; extended lucas cube; fibonacci cube; jaringan cluster non-linier hypercube; odd even transposition

Full Text:

PDF


DOI: http://dx.doi.org/10.21609/jiki.v3i2.144

Refbacks

  • There are currently no refbacks.


Copyright © Jurnal Ilmu Komputer dan Informasi. Faculty of Computer Science Universitas Indonesia.

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View JIKI Statistic