• DocumentCode
    1296327
  • Title

    An optimal multiplication algorithm on reconfigurable mesh

  • Author

    Jang, Ju-wook ; Park, Heonchul ; Prasanna, Viktor K.

  • Author_Institution
    Dept. of Electr. Eng., Sogang Univ., Seoul, South Korea
  • Volume
    8
  • Issue
    5
  • fYear
    1997
  • fDate
    5/1/1997 12:00:00 AM
  • Firstpage
    521
  • Lastpage
    532
  • Abstract
    An O(1) time algorithm to multiply two K-bit binary numbers using an N×N bit-model of reconfigurable mesh is shown. It uses optimal mesh size and it improves previously known results for multiplication on the reconfigurable mesh. The result is obtained by using novel techniques for data representation and data movement and using multidimensional Rader Transform. The algorithm is extended to result in AT2 optimality over 1⩽t⩽√N in a variant of the bit-model of VLSI
  • Keywords
    data structures; multiprocessor interconnection networks; parallel algorithms; reconfigurable architectures; K-bit binary numbers; O(1) time algorithm; data movement; data representation; multidimensional Rader transform; optimal mesh size; optimal multiplication algorithm; reconfigurable mesh; Arithmetic; Computer networks; Concurrent computing; Digital signal processing chips; Helium; Image processing; Message passing; Multidimensional systems; Routing; 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.598278
  • Filename
    598278
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1296327