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:
1432-4350(200103/04)34:2<101:AFFSSA>2.0.ZU;2-3
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. 101-114

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 odd-even 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 disk-striped 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