Quicksort on a linear array with a reconfigurable pipelined bus system

Yi Pan; Mounir Hamdi

Quicksort on a linear array with a reconfigurable pipelined bus system

Yi Pan^*, Mounir Hamdi

^*Corresponding author for this work

University of Dayton

Research output: Contribution to conference › Paper › peer-review

29 Citations (Scopus)

Abstract

Based on the current fiber optic technology, a new computational model, called a linear array with a reconfigurable pipelined bus system (LARPBS), is proposed in this paper. A parallel quicksort algorithm is implemented on the model, and its time complexity is analyzed. For a set of N numbers, the quicksort algorithm reported in this paper runs in O(log₂ N) average time on a linear array with a reconfigurable pipelined bus system of size N. Besides proposing a new algorithm on the model, some basic data movement operations involved in the algorithm are discussed. We believe that these operations can be used to design other parallel algorithms on the same model. Future research in this area is also identified in this paper.

Original language	English
Pages	313-319
Number of pages	7
Publication status	Published - 1996
Externally published	Yes
Event	Proceedings of the 1996 2nd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN - Beijing, China Duration: 12 Jun 1996 → 14 Jun 1996

Conference

Conference	Proceedings of the 1996 2nd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN
City	Beijing, China
Period	12/06/96 → 14/06/96

Cite this

@conference{eae5c832f2084c78b5f9696d822408a1,

title = "Quicksort on a linear array with a reconfigurable pipelined bus system",

abstract = "Based on the current fiber optic technology, a new computational model, called a linear array with a reconfigurable pipelined bus system (LARPBS), is proposed in this paper. A parallel quicksort algorithm is implemented on the model, and its time complexity is analyzed. For a set of N numbers, the quicksort algorithm reported in this paper runs in O(log2 N) average time on a linear array with a reconfigurable pipelined bus system of size N. Besides proposing a new algorithm on the model, some basic data movement operations involved in the algorithm are discussed. We believe that these operations can be used to design other parallel algorithms on the same model. Future research in this area is also identified in this paper.",

author = "Yi Pan and Mounir Hamdi",

year = "1996",

language = "English",

pages = "313--319",

note = "Proceedings of the 1996 2nd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN ; Conference date: 12-06-1996 Through 14-06-1996",

}

TY - CONF

T1 - Quicksort on a linear array with a reconfigurable pipelined bus system

AU - Pan, Yi

AU - Hamdi, Mounir

PY - 1996

Y1 - 1996

N2 - Based on the current fiber optic technology, a new computational model, called a linear array with a reconfigurable pipelined bus system (LARPBS), is proposed in this paper. A parallel quicksort algorithm is implemented on the model, and its time complexity is analyzed. For a set of N numbers, the quicksort algorithm reported in this paper runs in O(log2 N) average time on a linear array with a reconfigurable pipelined bus system of size N. Besides proposing a new algorithm on the model, some basic data movement operations involved in the algorithm are discussed. We believe that these operations can be used to design other parallel algorithms on the same model. Future research in this area is also identified in this paper.

AB - Based on the current fiber optic technology, a new computational model, called a linear array with a reconfigurable pipelined bus system (LARPBS), is proposed in this paper. A parallel quicksort algorithm is implemented on the model, and its time complexity is analyzed. For a set of N numbers, the quicksort algorithm reported in this paper runs in O(log2 N) average time on a linear array with a reconfigurable pipelined bus system of size N. Besides proposing a new algorithm on the model, some basic data movement operations involved in the algorithm are discussed. We believe that these operations can be used to design other parallel algorithms on the same model. Future research in this area is also identified in this paper.

UR - http://www.scopus.com/inward/record.url?scp=0029701774&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0029701774

SP - 313

EP - 319

T2 - Proceedings of the 1996 2nd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN

Y2 - 12 June 1996 through 14 June 1996

ER -

Quicksort on a linear array with a reconfigurable pipelined bus system

Abstract

Conference

Other files and links

Fingerprint

Cite this