.png){kind=icon}
返回
Sorting by parallel insertion on a one-dimensional subbus array
.png){kind=icon}
PRE
AI
DOI：10.1109/12.736441.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We consider the problem of sorting on a one-dimensional subbus array of processors, an architecture that communicates using a segmentable bus. The subbus broadcast operation makes possible a new class of parallel sorting algorithms whose complexity we analyze with the parallel insertion model. We give per-input lower bounds for sorting in the parallel insertion model and demonstrate sorting strategies that are optimal by matching those lower bounds. For each of our sorting strategies, we discuss the issues involved in implementing them on subbus machines. Finally, we empirically evaluate the performance of our sorting strategies by applying them to shearsort, a common two-dimensional mesh sorting algorithm. Our results suggest that for sorting the subbus broadcast capability gives at most a slight advantage over using only nearest neighbor communication.
Keyword:
subbus array
sorting
parallel algorithms
lower bounds
segmented-bus architecture
reconfigurable mesh architecture
odd-even transposition sort
bubble sort
期刊
IF:
3.8
论文数:
5.3K
被引数:
9.8K
机构
暂无机构信息
引用论文
.png){kind=icon}
A Bayesian hierarchical model for multiple imputation of urban spatio-temporal groundwater levels
PREAI
分享收藏 没有更多内容
没有更多内容