• DocumentCode
    1293322
  • Title

    Exact bounds on running ASCEND/DESCEND and FAN-IN algorithms on synchronous multiple bus networks

  • Author

    Ali, Arshad ; Vaidyanathan, Ramachandran

  • Author_Institution
    Cirrus Logic Inc., Fremont, CA, USA
  • Volume
    7
  • Issue
    8
  • fYear
    1996
  • fDate
    8/1/1996 12:00:00 AM
  • Firstpage
    783
  • Lastpage
    790
  • Abstract
    We consider the problem of running ASCEND/DESCEND and FAN-IN algorithms on synchronous multiple bus networks with a restricted number of buses. Exact lower bounds on the time are derived. We present a method that runs FAN-IN algorithms optimally and ASCEND/DESCEND algorithms in one step beyond the lower bound
  • Keywords
    computational complexity; multiprocessor interconnection networks; parallel algorithms; processor scheduling; ASCEND/DESCEND; FAN-IN; lower bound; multiple bus networks; parallel algorithms; scheduling; synchronous multiple bus networks; synchronous parallelism; Algorithm design and analysis; Communications technology; Delay; Hypercubes; Optical fiber communication; Parallel algorithms; Parallel processing; Processor scheduling; Scheduling algorithm; Very large scale integration;
  • fLanguage
    English
  • Journal_Title
    Parallel and Distributed Systems, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    1045-9219
  • Type

    jour

  • DOI
    10.1109/71.532110
  • Filename
    532110
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1293322