二维网格虫孔路由算法的实时扩展* (2006年)

随着计算机技术的迅速发展，大规模并行处理机（MPP）已成为高性能计算领域的核心组成部分。MPP由成千上万个处理器组成，采用分布式的私有存储器和特殊的网络互连结构以实现处理器间的消息传递。这些处理器通过各种网络拓扑结构相互通信，包括线性结构、环形结构、树型、网格以及超立方体等复杂结构。本文主要关注在二维网格结构（2-DMesh）上的MPP系统。 传统的MPP路由机制采用存储-转发机制，消息以包的形式进行传输，每个节点在转发包之前必须将其完整地存储在本地缓冲区中。这种方式对缓冲区的需求较大，并且传输时延会随着源节点到目的节点之间距离的增加而变长。为了解决这一问题，Dally在1986年提出了虫孔路由机制，它允许消息在传输时不需要完整的包存储，而是将包分割成微片，每个微片仅占一个字节到两个字节大小。微片被头微片引导，沿着路由路径流水线式传输，头微片包含路由信息，而后续数据微片则不包含路由信息。这种方法显著减少了缓冲区的需求，并且将包传输时延与源节点和目的节点之间的距离解耦，从而大大提高了消息传递的效率。 虫孔路由算法主要分为确定性算法和自适应算法两种。确定性算法为每个源和目的节点对提供固定的路径，其优点是简单且能最大程度避免死锁，但缺点在于缺乏灵活性。自适应算法可以提供多种路径选择，对紧急数据能够提供最短路径，并有助于实现全局网络负载均衡，但其缺点是实现复杂，且难以精确计算最大通信时延，因此在MPP体系中适用性较低。 在大规模并行系统的路由通信中，由于需要处理大量数据和消息，简单的路由选择机制和小容量的缓冲区成为了首选的设计前提。因此，确定性的虫孔路由机制通常更受青睐。然而，随着实时应用需求的不断增长，对虫孔路由算法的实时扩展成为了研究的重点。实时系统对延迟和数据传输的稳定性有着严苛要求，因此，对虫孔路由算法进行实时扩展，需要深入分析和比较各种主要实时虫孔路由算法的优缺点，并在此基础上提出改进方案。 在技术文献《二维网格虫孔路由算法的实时扩展》中，作者张宇亮和张立臣针对上述问题进行了深入研究，提出了对二维网格MPP环境下的虫孔路由算法的实时扩展。文章通过基金项目支持，包括国家自然科学基金、广东省自然科学基金和广东省高校自然科学研究基金的资助，进行了相关研究工作。 文章发表于2006年，通过比较分析不同实时虫孔路由算法的性能，总结了各种算法的优缺点，并基于大规模并行处理机的特性，对二维网格结构中的虫孔路由算法进行了实时扩展。这些实时扩展技术对于提高大规模并行处理机的性能，尤其是在实时通信方面，具有重要的实际应用价值。 关键词包括大规模并行处理机（MPP）、虫孔路由、实时通信、虚通道以及优先级倒置等。这些词汇涵盖了文章研究的核心内容和应用范畴。文中提到的虚通道（VirtualChannel）是一种提高网络吞吐量的技术，通过在物理链路上虚拟出多个独立的逻辑通道来提升数据传输效率，这在虫孔路由中尤其有用。而优先级倒置（PriorityInversion）是一个在实时系统中常见的问题，它描述了高优先级任务因为低优先级任务占用资源而被延迟的情况，这在设计实时虫孔路由算法时需要特别注意。 这篇文章为我们提供了在大规模并行处理机环境下二维网格虫孔路由算法实时扩展的全面分析和比较，为相关领域的研究和应用提供了宝贵的参考和指导。