We analyze the impact of message-ordering, between outgoing messages from a sender to multiple receivers (called multicasts), on the completion time of a program for wormhole-routed distributed-memory systems. In most existing systems, messages in a multicast are generally being sent as separate unicast messages by the source processor itself. We study how best to order a set of outgoing messages by taking into account message criticality and architectural issues including link contention, multiple ports and adaptivity in routing. First, the simple algorithm of (Dikaiakos et al., 1992) is extended to obtain a static algorithm for nonfully-connected systems. Next, a dynamic message-ordering algorithm is proposed which works for any number of ports and takes advantage of routing adaptivity. Simulation results on random task graphs show improvement in completion time by 34% for static and 44% for dynamic, over naive sequential message-ordering.
展开▼
机译：我们分析了从发送者到多个接收者（称为多播）的传出消息之间的消息排序对蠕虫路由分布式内存系统程序完成时间的影响。在大多数现有系统中，多播中的消息通常由源处理器本身作为单独的单播消息发送。我们研究如何通过考虑消息的关键性和架构问题（包括链路争用，多个端口和路由的适应性）来最好地订购一组传出消息。首先，扩展了（Dikaiakos et al。，1992）的简单算法，以获得用于非完全连接系统的静态算法。接下来，提出了一种动态消息排序算法，该算法可用于任意数量的端口并利用路由自适应性。随机任务图上的仿真结果显示，相比幼稚的顺序消息排序，静态完成时间提高了34％，动态完成时间提高了44％。
展开▼
