• DocumentCode
    761167
  • Title

    An optimal algorithm for permutation admissibility to multistage interconnection networks

  • Author

    Shen, Xiaojun ; Xu, Mao ; Wang, Xiangzu

  • Author_Institution
    Comput. Sci. Telecommun. Program, Missouri Univ., Kansas City, MO, USA
  • Volume
    44
  • Issue
    4
  • fYear
    1995
  • fDate
    4/1/1995 12:00:00 AM
  • Firstpage
    604
  • Lastpage
    608
  • Abstract
    This paper introduces a simple O(NlogN) sequential algorithm that determines the admissibility of an arbitrary permutation to an N×N Multistage Cube-Type Network (MCTN) implemented by 2×2 switching elements (SEs) in contrast to previous O(Nlog2N) algorithms. It is proven that the new algorithm is optimal in the sense that any algorithm, based on bit-operations, has to examine at least (N/4)logN different bits among the total NlogN bits in the binary representations of the destinations numbered from 0 through N-1
  • Keywords
    multistage interconnection networks; parallel algorithms; O(NlogN) sequential algorithm; arbitrary permutation; bit-operations; multistage cube-type network; multistage interconnection networks; optimal algorithm; permutation admissibility; Algorithm design and analysis; Cities and towns; Computer science; Multiprocessor interconnection networks;
  • fLanguage
    English
  • Journal_Title
    Computers, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9340
  • Type

    jour

  • DOI
    10.1109/12.376176
  • Filename
    376176
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=761167