Improved bounds for routing and sorting on multi-dimensional meshes

Torsten Suel

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    We show improved bounds for 1-1 routing and sorting on multi-dimensional meshes and tori. In particular, we give a fairly simple deterministic algorithm for sorting on the (/-dimensional mesh of side length n that achieves a running time of 3dn/2+o(n) without making any copies of the elements. We give deterministic algorithms with running times of 5dn/4 + o(n) and Zdn/4 + o(n) for the d-dimensional mesh and torus, respectively, that make one copy of each element. We also show lower bounds for sorting with respect to a large class of indexing schemes, under a model of the mesh where each processor can hold an arbitrary number of packets. Finally, we describe algorithms for permutation routing whose running times come very close to the diameter lower bound.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994
    PublisherAssociation for Computing Machinery, Inc
    Pages26-35
    Number of pages10
    ISBN (Electronic)0897916719, 9780897916714
    DOIs
    StatePublished - Aug 1 1994
    Event6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994 - Cape May, United States
    Duration: Jun 27 1994Jun 29 1994

    Publication series

    NameProceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994

    Other

    Other6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994
    CountryUnited States
    CityCape May
    Period6/27/946/29/94

    ASJC Scopus subject areas

    • Software
    • Theoretical Computer Science
    • Hardware and Architecture

    Fingerprint Dive into the research topics of 'Improved bounds for routing and sorting on multi-dimensional meshes'. Together they form a unique fingerprint.

    Cite this