1. Home page
  2. Search

PARALLEL COMPUTATIONS ON RECONFIGURABLE MESHES

This item is provided by the institution :
National Technical University of Athens   

Repository :
Digital Library of National Technical University of Athens | Dspace@NTUA   

see the original item page
in the repository's web site and access all digital files if the item*



PARALLEL COMPUTATIONS ON RECONFIGURABLE MESHES (EN)
PRASANNAKUMAR, VK (EN)
MILLER, R (EN)
STOUT, QF (EN)
REISIS, DI (EN)
journalArticle (EN)
2014-03-01T01:09:30Z
1993 (EN)
This paper introduces the mesh with reconfigurable bus (reconfigurable mesh) as a model of computation. The reconfigurable mesh captures salient features from a variety of sources, including the CAAPP, CHiP, polymorphic-torus network, and bus automaton. It consists of an array of processors interconnected by a reconfigurable bus system, which can be used to dynamically obtain various interconnection patterns between the processors. In this paper, we introduce a variety of fundamental data-movement operations for the reconfigurable mesh. Based on these operations, we also introduce new algorithms that are efficient for solving a variety of problems involving graphs and digitized images. The algorithms we present are asymptotically superior to those previously obtained for the aforementioned reconfigurable architectures, as well as to those previously obtained for the mesh, the mesh with multiple broadcasting, the mesh with multiple buses, the mesh-of-trees, and the pyramid computer, to name a few. Highlights include a logarithmic time algorithm to label the connected components of a graph given its adjacency matrix, as well as polylogarithmic time algorithms to solve problems involving convexity and connectivity of figures in images. We also show the power of reconfigurability by solving some problems, such as exclusive OR, more efficiently on the reconfigurable mesh than is possible on the PRAM. (EN)
Engineering, Electrical & Electronic (EN)
Computer Science, Hardware & Architecture (EN)
RECONFIGURABLE MESH (EN)
ARRAY (EN)
VLSI (EN)
COMPUTERS (EN)
MESH (EN)
PRAM (EN)
INFORMATION-TRANSFER (EN)
ALGORITHMS (EN)
IMAGE ALGORITHMS (EN)
GRAPH ALGORITHMS (EN)
PARALLEL ALGORITHMS (EN)
PYRAMID COMPUTER (EN)
MESH-OF-TREES (EN)
FINDING MAXIMUM (EN)
IEEE TRANSACTIONS ON COMPUTERS (EN)
English
IEEE COMPUTER SOC (EN)
National Technical University of Athens
Digital Library of National Technical University of Athens | Dspace@NTUA
Κεντρική Βιβλιοθήκη Ε.Μ.Π.
Ιδρυματικό Αποθετήριο
Δημοσιεύσεις μελών Δ.Ε.Π. σε περιοδικά



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)