Time lower bounds for parallel sorting on a mesh-connected processor array
type: Item
instance of: scholarly article
title: Time lower bounds for parallel sorting on a mesh-connected processor array
zbMATH Open document ID: 0659.68087
DOI: 10.1007/BF00288975
author: Yijie Han
author: Yoshihide Igarashi
published in: Acta Informatica
publication date: 1989-01-01T00:00:00Z
review text: We prove that \((1+\sqrt{6}/2)n\approx 2.22 n\) is a time lower bound independent of indexing schemes for sorting \(n^ 2\) items on an \(n\times n\) mesh-connected processor array. We distinguish between indexing schemes by showing that there exists an indexing scheme which is provably worse than a snake-like row-major indexing for sorting. We also derive lower bounds for various indexing schemes. All these results are obtained by using the chain argument which we provide in this paper.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4078825
zbMATH Keywords: time lower bound
zbMATH Keywords: sorting
zbMATH Keywords: mesh-connected processor array
zbMATH Keywords: indexing schemes
zbMATH Keywords: chain argument
zbMATH Keywords: parallel algorithm
reviewed by: Yanchang Han
MaRDI profile type: Publication
cites work: Sorting in Average Time $o(\log \,n)$
cites work: Q3709907
cites work: Indexing functions and time lower bounds for sorting on a mesh-connected computer
cites work: Lower bounds for sorting on mesh-connected architectures
cites work: Q3820021
cites work: Systolic Sorting on a Mesh-Connected Network
cites work: Tight Bounds on the Complexity of Parallel Sorting
cites work: Bitonic Sort on a Mesh-Connected Parallel Computer
cites work: Q3785964
cites work: Sorting on a mesh-connected parallel computer
cites work: The VLSI Complexity of Sorting
full work available at URL: https://doi.org/10.1007/bf00288975
OpenAlex ID: W1985905751
description: scientific article; zbMATH DE number 4078825