We consider the problem of dimension-ordered embedding of complete binary trees into 3-dimensional meshes without link contention. In this paper, the embedding problems are studied under two different network models: half-duplexed networks and full-duplexed networks. Gibbons and Paterson showed that a complete binary tree T/sub p/ could be disjointedly embedded into a full-duplexed 2-dimensional mesh of optimum size without dimension-ordered routing. Using the dimension-ordered routing, the authors showed that T/sub p/ could be embedded into a 3-dimensional mesh of optimum size with link congestion two. This paper presents the dimension-ordered embedding algorithms of the complete binary trees into the wormhole routed 3-dimensional meshes without link contention achieving expansion of no larger than 1.125 of optimum in half-duplexed network model and optimum in full-duplexed network model.
展开▼
机译：我们考虑将完整的二叉树按维度排序嵌入到3维网格中而没有链接争用的问题。本文在两种不同的网络模型下研究了嵌入问题：半双工网络和全双工网络。 Gibbons和Paterson表明，完整的二叉树T / sub p /可以不加区分地嵌入到具有最佳大小的全双工二维网格中，而无需按维度进行排序。使用维排序的路由，作者表明T / sub p /可以嵌入到具有链接拥塞两个的最佳大小的3维网格中。本文提出了将完整的二叉树按尺寸顺序嵌入到虫洞路由的3维网格中的算法，该算法没有链接争用，使得半双工网络模型和全双工网络模型的最优展开不大于1.125。
展开▼
