AN OPTIMAL MULTIPLICATION ALGORITHM ON RECONFIGURABLE MESH

Authors
JANG JW PARK H PRASANNA VK
Citation
Jw. Jang et al., AN OPTIMAL MULTIPLICATION ALGORITHM ON RECONFIGURABLE MESH, IEEE transactions on parallel and distributed systems, 8(5), 1997, pp. 521-532
Citations number
35
Categorie Soggetti
System Science","Engineering, Eletrical & Electronic","Computer Science Theory & Methods
Journal title
IEEE transactions on parallel and distributed systems → ACNP
ISSN journal
10459219
Volume
8
Issue
5
Year of publication
1997
Pages
521 - 532
Database
ISI
SICI code
1045-9219(1997)8:5<521:AOMAOR>2.0.ZU;2-R
Abstract
An O(1) time algorithm to multiply two N-bit binary numbers using an N x N bit-model of reconfigurable mesh is shown. It uses optimal mesh s ize 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 AT(2) optimali ty over 1 less than or equal to T less than or equal to root N in a va riant of the bit-model of VLSI.