Space and time complexities of balanced sorting on processor arrays

研究成果: 雜誌貢獻期刊論文同行評審

2 引文 斯高帕斯(Scopus)

摘要

A processor is balanced in carrying out a computation if its computing time equals its I/O time. When the computation bandwidth of a processor is increased, like when multiple processors are incorporated to form an array, the critical question is to what degree the processor's memory must be enlarged in order to alleviate the I/O bottleneck to keep the computation balanced. In this paper, for the sorting problem, we present two balanced algorithms on linearly connected and mesh-connected processor arrays, respectively, and show that they reach the derived lower bounds of memory sizes. We also verify that the time complexities of the algorithms are optimal under their respective hardware constraints.
原文英語
頁(從 - 到)365-378
頁數14
期刊Journal of Complexity
6
發行號4
DOIs
出版狀態已發佈 - 1990

引用此