Reconfigurable tesh connected parallel computers
B.M. Maziarz, V.K. Jain · 1998
Computing structures for the twenty-first century will require sub-micron technologies, highly parallel architectures capable of performing at teraflops level, and software paradigms that have not been invented yet. One of the major obstacles in the design and construction of such parallel computers is the binding ether for the processing modules. This dissertation develops efficient and cost effective connectivity for highly scalable, expandable, and manufacturable parallel computing structures. Specifically, a new class of modular interconnection networks--Tori Connected Meshes (TESH)--is investigated. Important characteristics of the network, that are critical to microchip implementation on the one hand and efficient embedding of applications on the other, are studied in depth. It is shown that the wiring complexity of the TESH is up to four times smaller than that of a comparable mesh network, and an order of magnitude smaller than that of the hypercube. Also, recognizing that the brain of a network is the set of its distributed routers, this critical sub-system is designed for the TESH network. From the perspective of the semiconductor industry, defect tolerance is exceedingly important for economical manufacturing of large-scale computing structures. To automate this process, an efficient methodology and corresponding software for reconfiguration and defect circumvention are developed. It includes placement, that assigns logical nodes to healthy physical nodes, and routing, that reconfigures switches to bypass the defective components--cells, switches and links. Theoretical predictions as well as simulations indicate that yields approaching 100% can be attained for 256- to 4096-node computing structures. This creates the potential for manufacturing TESH based parallel machines with tens to hundreds of tera-ops performance. Advanced algorithms such as real-time solution of partial differential equations, 2-D wavelet transforms, and multi-layer artificial neural networks are mapped using the parallelism of a TESH connected array of processors. The partial differential equation models are relevant in modeling various physical phenomena such as fluid flow, and dynamic electromagnetic fields. It is also well known that their real-time solution (which would make them attractive to the industry as well as the scientific community) requires tens to hundreds of tera-ops per second. The 2-D wavelet transform, on the other hand, finds application in digital video and image processing such as a fingerprint or retina scan identification. Both of these algorithms are implemented in such a way so as to completely hide the communication overhead. Even more important, it is shown that the performance of a TESH implemented algorithm is comparable to the MESH based algorithm. This is significant because TESH networks are easier to implement due to the much reduced wiring than MESH networks. We believe that this dissertation has taken a significant step toward providing the ether for highly scalable, expandable, and manufacturable parallel computing structures of the future.