• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Euro-Par Parallel Processing Conference; 20050830-0902; Lisbon(PT) >Routing and Scheduling for a Novel Optical Multistage Interconnection Network
【24h】

Routing and Scheduling for a Novel Optical Multistage Interconnection Network

机译：新型光多级互连网络的路由和调度

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Multistage Interconnection Networks (MINs) are popular in computing and communication applications. Recently, there have also been significant advances in electro-optic switches that have made Optical MINs (OMINs) a good choice for the nigh channel bandwidth and low communication latency of high performance computing and communication applications. However, OMINs introduce crosstalk which results from coupling two signals within one switching element. Under the constraint of avoiding crosstalk, what we are interested in is how to realize a permutation that requires the minimum number of passes. This routing problem is an NP-hard one, and many heuristic algorithms have been devised to find a solution. In [9], Chau and Xiao have proposed an algorithm, called the Remove Last Pass (RLP) algorithm, to avoid crosstalk and route the traffic in an OMIN more efficiently. In this paper, we focus on the routing and scheduling of a novel OMIN, the base-2 MIN, propounded by Chau and Fu in [8]. Our experiments prove that any permutation can be realized in no more than three passes in the base-2 OMIN by using the RLP algorithm, when the network has no more than 512 nodes. The base-2 OMIN requires only n(logn+1) switching elements (SEs) for an nxn network, compared to the crossbar, which requires O(n~2) SEs for an nxn network. Therefore, the base-2 MIN should be a good candidate for communication subsystems in a parallel computing environment.
机译：多级互连网络（MIN）在计算和通信应用中很流行。近来，电光开关也取得了重大进步，这使光学MIN（OMIN）成为高性能计算和通信应用的近信道带宽和低通信等待时间的理想选择。但是，OMIN会引入串扰，这是由于在一个开关元件内耦合两个信号而引起的。在避免串扰的约束下，我们感兴趣的是如何实现需要最少通过次数的置换。这个路由问题是一个NP难题，并且已经设计出许多启发式算法来寻找解决方案。在[9]中，Chau和Xiao提出了一种算法，称为“ Remote Last Pass（RLP）”算法，以避免串扰并更有效地路由OMIN中的流量。在本文中，我们关注于Chau和Fu在[8]中提出的新型OMIN（以2为底的MIN）的路由和调度。我们的实验证明，当网络的节点数不超过512个时，使用RLP算法可以在以2为基的OMIN中以不超过3个通道实现任何置换。与之相比，以2为基础的OMIN对于nxn网络仅需要n（logn + 1）个交换元件（SE），而对于nxn网络则需要O（n〜2）个SE。因此，以2为底的MIN应该是并行计算环境中通信子系统的理想选择。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号