Copy
Kuninobu TANNO, "Sorting on an Eight-Neighbor Mesh-Connected Parallel Computer" in IEICE TRANSACTIONS on transactions,
vol. E72-E, no. 5, pp. 550-555, May 1989, doi: .
Abstract: Sorting is a fundamental problem of information processing both in theoretical interests and in practical applications. Enormous efforts have been made to develop high speed sorting algorithms, especially suited for SIMD or MIMD type parallel computers built in VLSI technology, especially for an nn 4-neighbor mesh-connected parallel computer. In this paper, we deal with a sorting algorithm assuming an eight-neighbor mesh-connected parallel computer with no wraparounds in rows or columns. The machine consists of N=nn processors (processing elements) which are arranged in a two-dimensional array and can communicate, if exist, with 8 neighbor processors. Our algorithm fully makes use of the communication capability, that is, we introduce a primitive operation which compares and exchanges four elements, simultaneously, between four processors. The algorithm sorts nn elements into shuffled row-major order and yields the sorting time of 2(4n-2log n-5)tr + (log2n-log n+1)tc. where tr and tc are defined as the times for a unit routing step and a comparison, respectively. It is shown that the algorithm is faster than ones for a 4-neighbor mesh-connected computer presented earlier by Nassimi and Sahni or Kumar and Hirschberg. The speedup is due to adequate combinations of the primitive operation in an 8-neighbor mesh-connected array with the property of shuffled row-major indexing. This paper is organized in the following manner: Firstly, we illustrate the structure and the function of an 8-neighbor mesh-connected parallel computer. Next, we describe and discuss our sorting algorithm precisely. Finally, we derive the sorting time of this algorithm and compare it with those of the algorithms developed for a 4-neighbor mesh-connected computer.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e72-e_5_550/_p
Copy
@ARTICLE{e72-e_5_550,
author={Kuninobu TANNO, },
journal={IEICE TRANSACTIONS on transactions},
title={Sorting on an Eight-Neighbor Mesh-Connected Parallel Computer},
year={1989},
volume={E72-E},
number={5},
pages={550-555},
abstract={Sorting is a fundamental problem of information processing both in theoretical interests and in practical applications. Enormous efforts have been made to develop high speed sorting algorithms, especially suited for SIMD or MIMD type parallel computers built in VLSI technology, especially for an nn 4-neighbor mesh-connected parallel computer. In this paper, we deal with a sorting algorithm assuming an eight-neighbor mesh-connected parallel computer with no wraparounds in rows or columns. The machine consists of N=nn processors (processing elements) which are arranged in a two-dimensional array and can communicate, if exist, with 8 neighbor processors. Our algorithm fully makes use of the communication capability, that is, we introduce a primitive operation which compares and exchanges four elements, simultaneously, between four processors. The algorithm sorts nn elements into shuffled row-major order and yields the sorting time of 2(4n-2log n-5)tr + (log2n-log n+1)tc. where tr and tc are defined as the times for a unit routing step and a comparison, respectively. It is shown that the algorithm is faster than ones for a 4-neighbor mesh-connected computer presented earlier by Nassimi and Sahni or Kumar and Hirschberg. The speedup is due to adequate combinations of the primitive operation in an 8-neighbor mesh-connected array with the property of shuffled row-major indexing. This paper is organized in the following manner: Firstly, we illustrate the structure and the function of an 8-neighbor mesh-connected parallel computer. Next, we describe and discuss our sorting algorithm precisely. Finally, we derive the sorting time of this algorithm and compare it with those of the algorithms developed for a 4-neighbor mesh-connected computer.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - Sorting on an Eight-Neighbor Mesh-Connected Parallel Computer
T2 - IEICE TRANSACTIONS on transactions
SP - 550
EP - 555
AU - Kuninobu TANNO
PY - 1989
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E72-E
IS - 5
JA - IEICE TRANSACTIONS on transactions
Y1 - May 1989
AB - Sorting is a fundamental problem of information processing both in theoretical interests and in practical applications. Enormous efforts have been made to develop high speed sorting algorithms, especially suited for SIMD or MIMD type parallel computers built in VLSI technology, especially for an nn 4-neighbor mesh-connected parallel computer. In this paper, we deal with a sorting algorithm assuming an eight-neighbor mesh-connected parallel computer with no wraparounds in rows or columns. The machine consists of N=nn processors (processing elements) which are arranged in a two-dimensional array and can communicate, if exist, with 8 neighbor processors. Our algorithm fully makes use of the communication capability, that is, we introduce a primitive operation which compares and exchanges four elements, simultaneously, between four processors. The algorithm sorts nn elements into shuffled row-major order and yields the sorting time of 2(4n-2log n-5)tr + (log2n-log n+1)tc. where tr and tc are defined as the times for a unit routing step and a comparison, respectively. It is shown that the algorithm is faster than ones for a 4-neighbor mesh-connected computer presented earlier by Nassimi and Sahni or Kumar and Hirschberg. The speedup is due to adequate combinations of the primitive operation in an 8-neighbor mesh-connected array with the property of shuffled row-major indexing. This paper is organized in the following manner: Firstly, we illustrate the structure and the function of an 8-neighbor mesh-connected parallel computer. Next, we describe and discuss our sorting algorithm precisely. Finally, we derive the sorting time of this algorithm and compare it with those of the algorithms developed for a 4-neighbor mesh-connected computer.
ER -
English
