Catalogo Articoli (Spogli Riviste)
OPAC HELP
Titolo: A framework for simple sorting algorithms on parallel disk systems
Autore: Rajasekaran, S;
 Indirizzi:
 Univ Florida, Dept CISE, Gainesville, FL 32611 USA Univ Florida Gainesville FL USA 32611 ept CISE, Gainesville, FL 32611 USA
 Titolo Testata:
 THEORY OF COMPUTING SYSTEMS
fascicolo: 2,
volume: 34,
anno: 2001,
pagine: 101  114
 SICI:
 14324350(200103/04)34:2<101:AFFSSA>2.0.ZU;23
 Fonte:
 ISI
 Lingua:
 ENG
 Soggetto:
 COMPLEXITY; NETWORK;
 Tipo documento:
 Article
 Natura:
 Periodico
 Settore Disciplinare:
 Engineering, Computing & Technology
 Citazioni:
 25
 Recensione:
 Indirizzi per estratti:
 Indirizzo: Rajasekaran, S Univ Florida, Dept CISE, Gainesville, FL 32611 USA Univ Florida Gainesville FL USA 32611 sville, FL 32611 USA



 Citazione:
 S. Rajasekaran, "A framework for simple sorting algorithms on parallel disk systems", THEOR C SYS, 34(2), 2001, pp. 101114
Abstract
In this paper we present a simple parallel sorting algorithm and illustrate its application in general sorting, disk sorting, and hypercube sorting. The algorithm (called the (I, m)mergesort (LMM)) is an extension of the bitonic and oddeven mergesorts. Literature on parallel sorting is abundant. Many of the algorithms proposed, though being theoretically important, may not perform satisfactorily in practice owing to large constants in their time bounds. The algorithm presented in this paper has the potential of being practical. We present an application to the parallel disk sorting problem. The algorithm is asymptotically optimal (assuming that N is a polynomial in M, where N is the number of records to be sorted and M is the internal memory size). The underlying constant is very small. This algorithm performs better thanthe diskstriped mergesort (DSM) algorithm when the number of disks is large. Our implementation is as simple as that of DSM (requiring no fancy datastructures or prefetch techniques. )As a second application, we prove that we can get a sparse enumeration sort on the hypercube that is simpler than that of the classical algorithm of Nassimi and Sahni [16]. We also show that Leighton's columnsort algorithm is a special case of LMM.
ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 18/01/20 alle ore 07:27:13