• DocumentCode
    2298804
  • Title

    Good algorithm design style for multiprocessors

  • Author

    Deng, X. ; Gu, N.

  • Author_Institution
    Dept. of Comput. Sci., York Univ., North York, Ont., Canada
  • fYear
    1994
  • fDate
    26-29 Oct 1994
  • Firstpage
    538
  • Lastpage
    543
  • Abstract
    We discuss a style of designing parallel algorithms with the following characteristics for a problem of the best known sequential time T(n): C1. Each processor spends O(T(n)/P) time in computing. C2. Each processor sends and/or receives O(n/P) messages of one-word-size. C3. The number of communication phases1 is constant, independent of the input size n. We show this is possible to achieve for several fundamental computational problems
  • Keywords
    communication complexity; computational complexity; parallel algorithms; algorithm design; computational problems; messages; multiprocessors; parallel algorithms; sequential time; Algorithm design and analysis; Application software; Computer science; Concurrent computing; Delay effects; Distributed computing; Parallel algorithms; Parallel machines; Phase change random access memory; Pipeline processing;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Parallel and Distributed Processing, 1994. Proceedings. Sixth IEEE Symposium on
  • Conference_Location
    Dallas, TX
  • Print_ISBN
    0-8186-6427-4
  • Type

    conf

  • DOI
    10.1109/SPDP.1994.346125
  • Filename
    346125
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2298804