Odd-Even, Compare-Exchange Parallel Sorting
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Danielopoulos, S. D.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Microprocessing and Microprogramming
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
We present a parallel sorting algorithm and its proof which sorts a sequence of n elements in time O(log2 n) with n/2 processors on an EREW-PRAM computational model. A sorting network directly implements the algorithm using O(n.log n)PEs. The algorithm is based on the elementary Compare-Exchange operation and has the advantage that it does not require a powerful computational model, uses the least amount of space for the sorting problem, has small constants and can be implemented directly on a sorting network. Furthermore, the architecture of the network is simple and makes no unrealistic technological assumptions.
Περιγραφή
Λέξεις-κλειδιά
parallel sorting, compare-exchange schemes, erew-pram, sorting networks, complexity, computation, algorithms, network, sorter
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής