Facilitating High-Performance Image Analysis on Reduced Hypercube (RH) Parallel Computers

摘要

The direct binary hypercube interconnection network has been very popular for the design of parallel computers, because it provides a low diameter and can emulate efficiently the majority of the topologies frequently employed in the development of algorithms. The last fifteen years have seen major efforts to develop image analysis algorithms for hypercube-based parallel computers. The results of these efforts have culminated in a large number of publications included in prestigious scholarly journals and conference proceedings. Nevertheless, the aforementioned powerful properties of the hypercube come at the cost of high VLSI complexity due to the increase in the number of communication ports and channels per PE (processing element) with an increase in the total number of PE's. The high VLSI complexity of hypercube systems is undoubtedly their dominant drawback; it results in the construction of systems that contain either a large number of primitive PE's or a small number of powerful PE's. Therefore, low-dimensional k-ary n-cubes with lower VSLI complexity have recently drawn the attention of many designers of parallel computers. Alternative solutions reduce the hypercube's VLSI complexity without jeopardizing its performance. Such an effort by Ziavras has resulted in the introduction of reduced hypercubes (RH's). Taking advantage of existing high-performance routing techniques, such as wormhole routing, an RH is obtained by a uniform reduction in the number of edges for each hypercube node. An RH can also be viewed as several connected copies of the well-known cube-connected-cycles network. The objective here is to prove that parallel computers comprising RH interconnection networks are definitely good choices for all levels of image analysis. Since the exact requirements of high-level image analysis are difficult to identify, but it is believed that versatile interconnection networks, such as the hypercube, are suitable for relevant tasks, we investigate the problem of emulating hypercubes on RH's. The ring (or linear array), the torus (or mesh), and the binary tree are the most frequently used topologies for the development of algorithms in low-level and intermediate-level image analysis. Thus, to prove the viability of the RH for the two lower levels of image analysis, we introduce techniques for embedding the aforementioned three topologies into RH's. The results prove the suitability of RH's for all levels of image analysis.