论文标题
通信有效的字符串分类
Communication-Efficient String Sorting
论文作者
论文摘要
令人惊讶的是，在分布式记忆并行机器上对字符串排序的算法几乎没有工作。我们根据多路合并原则为此问题开发有效的算法。这些算法仅检查确定排序顺序所需的字符。此外，通过（大致）仅（大致）交流这些字符，并仅通过一次交流相同前缀的重复来减少通信量。多达1280个核心的实验表明，这些算法通常比以前的算法快五倍以上。
There has been surprisingly little work on algorithms for sorting strings on distributed-memory parallel machines. We develop efficient algorithms for this problem based on the multi-way merging principle. These algorithms inspect only characters that are needed to determine the sorting order. Moreover, communication volume is reduced by also communicating (roughly) only those characters and by communicating repetitions of the same prefixes only once. Experiments on up to 1280 cores reveal that these algorithm are often more than five times faster than previous algorithms.
