LARGE-SCALE SORTING IN UNIFORM MEMORY HIERARCHIES

被引：12
|
作者：
VITTER, JS
NODINE, MH
机构：
[1] Department of Computer Science, Brown University, Providence
来源：
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING | 1993年 / 17卷 / 1-2期
关键词：
D O I：
10.1006/jpdc.1993.1008
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We present several efficient algorithms for sorting on the uniform memory hierarchy (UMH), introduced by Alpern, Carter, and Feig, and its parallelization P-UMH. We give optimal and nearly optimal algorithms for a wide range of bandwidth degradations, including a parsimonious algorithm for constant bandwidth. We also develop optimal sorting algorithms for all bandwidths for other versions of UMH and P-UMH, including natural restrictions we introduce called RUMH and P-RUMH, which more closely correspond to current programming languages. © 1993 Academic Press, Inc.
引用
收藏
页码：107 / 114
页数：8
相关论文
共 50 条
  • [1] LARGE-SCALE CHROMOSOME SORTING
    FAWCETT, JJ
    LONGMIRE, JL
    MARTIN, JC
    DEAVEN, LL
    CRAM, LS
    METHODS IN CELL BIOLOGY, VOL 42: FLOW CYTOMETRY, 2ND EDITION, PT B, 1994, 42 : 319 - 330
  • [2] Hierarchies in the large-scale structures of the Universe
    Goldman, T.
    Perez-Mercader, Juan
    INTERNATIONAL JOURNAL OF MODERN PHYSICS D, 2006, 15 (08): : 1199 - 1215
  • [3] Sky-Sorter: A Processing-in-Memory Architecture for Large-Scale Sorting
    Zokaee, Farzaneh
    Chen, Fan
    Sun, Guangyu
    Jiang, Lei
    IEEE TRANSACTIONS ON COMPUTERS, 2023, 72 (02) : 480 - 493
  • [4] Latent Task Adaptation with Large-scale Hierarchies
    Jia, Yangqing
    Darrell, Trevor
    2013 IEEE INTERNATIONAL CONFERENCE ON COMPUTER VISION (ICCV), 2013, : 2080 - 2087
  • [5] LASH: Large-Scale Sequence Mining with Hierarchies
    Beedkar, Kaustubh
    Gemulla, Rainer
    SIGMOD'15: PROCEEDINGS OF THE 2015 ACM SIGMOD INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, 2015, : 491 - 503
  • [6] SA Sorting: A Novel Sorting Technique for Large-Scale Data
    Shabaz, Mohammad
    Kumar, Ashok
    JOURNAL OF COMPUTER NETWORKS AND COMMUNICATIONS, 2019, 2019
  • [7] GPU-accelerated large-scale distributed sorting coping with device memory capacity
    Shamoto, Hideyuki (shamoto.h.aa@m.titech.ac.jp), 1600, Institute of Electrical and Electronics Engineers Inc., United States (02):
  • [8] A Hierarchical Sorting Swarm Optimizer for Large-scale Optimization
    Lan, Rushi
    Zhang, Li
    Tang, Zhiling
    Liu, Zhenbing
    Luo, Xiaonan
    IEEE ACCESS, 2019, 7 : 40625 - 40635
  • [9] Large-scale optical traps on a chip for optical sorting
    Sun, Y. Y.
    Yuan, X. -C.
    Ong, L. S.
    Bu, J.
    Zhu, S. W.
    Liu, R.
    APPLIED PHYSICS LETTERS, 2007, 90 (03)
  • [10] Retention of memory for large-scale spaces
    Ishikawa, Toru
    MEMORY, 2013, 21 (07) : 807 - 817
12345