![]() Unlike previous work with binary trees and rectangular meshes, these classes of graphs do not lend themselves to straightforward hypercube embeddings with low dilation and expansion values. He presents several algorithms for embedding specific classes of graphs into the hypercube. Furthermore, the recent development of the direct-connect hypercube technology has effectively eliminated dilation as a serious problem with embeddings into the hypercube. Successful results with quadtree and pyramid source graphs using this approach indicate that achieving optimal expansion for individual tasks is not always advantageous. He introduces the concept of multiple graph embeddings into a single hypercube without relegating separate tasks to distinct subcubes. In this thesis, the author examines recent research which drastically reduces the significance of expansion and dilation as more » embedding efficiency gauges. Second, the store-and-forward technology of the first generation of hypercubes necessitated the development of adjacency-preserving or, at least, minimal dilation embeddings. First, a reliance upon subcube assignment as a task allocation technique has served to emphasize expansion as an important gauge of the efficiency of an embedding. Previous work in this area has been based upon two basic premises. The hypercube network has exhibited a strong propensity for the implementation of algorithms designed for other topological structures by means of graphical embedding. This complements a recent result showing the problem is NP-complete when the source is a tree (hence planar) of unbounded degree and the target is a hypercube whose size is given, but not optimal. It is shown that it is NP-complete to decide if any given graph in this class has a dilation one embedding in its optimal hypercube. Another class of source networks is also considered: those whose communication graphs are known only to be planar and of vertex degree at most five. For n-D meshes dilation is at most 4n minus 1, marginally improving on the best sequential algorithm guaranteeing dilation at most 4n plus more » 1. For 3-D meshes, dilation, is at most eight, slightly worse than the best sequential algorithms guaranteeing dilation at most seven. For 2-D meshes dilation is at most two, which is optimal. Except for 3-D meshes, the dilation achieved here is no more than for the sequential algorithms. It is argued that hypercube embeddings should, if possible, be computed by parallel algorithms, underscoring the significance of the algorithms presented, since existing algorithms appear to be inherently sequential. Parallel algorithms suitable for hypercube execution are given to embed any mesh in its optimal hypercube, thereby minimizing expansion. ![]() The embedding should keep certain simulation costs small, the most significant being dilation and expansion. This requires the communication graph of the preferred network be mapped, or embedded into that of the available one. The natural or preferred interconnection network implied by the communication needs of the parallel algorithm must be simulated by some actually available network whose interconnections are different from those of the preferred one. The mapping problem arises whenever a parallel algorithm is implemented on an array of processors.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |