Embedding hex/cells into tree/hypercube networks
Qatawinah, Awad Ibrahim · 2008
Graph embedding or graph mapping is an important aspect for interconnection networks used for communication between processors in parallel systems. Some parallel algorithms use communication structures which can be represented by hex-cells. In order to run these algorithms on a tree-hypercube multiprocessor system, without changing the current topology and the running application, their communication graphs need to be embedded into tree- hypercube. In this research, we have designed an algorithm for embedding hex-cells of n nodes into tree-hypercube TH(2,d) where d >= 2. The embedding has dilation one, congestion one, and expansion 1.1. In the algorithm an embedding of irregular shape of hex-cells into tree-hypercube TH(2,d) where d >= 2 is performed.