以太网并行处理程序退避方法分析

李 隽

(北京市通州区人民检察院 技术处，北京 101100)

1 引言

以太网的发送过程中，先由一个或多个节点产生发送帧和测试线，然后尝试发送并尽快在完成当前传输。如果是多于一个节点，节点会产生碰撞，生成随机的补偿时间，然后再次尝试发送。

我们假设在以太网上均匀工作站上运行并行处理的应用程序，并考虑任务交会帧的发送。例如，在一个消息传递中，我们可能有求根程序[1]。在这里，一个已知函数在所给间隔有一个单一根，此根是程序在一次平行迭代的结果（按照所需的精确度）。在任一给定的迭代中，当前的间隔要搜索n个小区间，其中，n是机器的总数量。每一个节点检查其指定节点的子区间，然后告知上层节点给定函数在此子区间信号是否发生变化。这些子区间中只有一个会发生这样的变化，然后，它会成为新的区间。新区间端点的值将被广播，使它们可以划分成新的子区间。在共享内存范式下（分布式共享内存），屏蔽操作会产生类似的模式。

出现在这里的问题是，在许多应用中任务时间（包括通信延迟）发生小的变异[2]。例如，上述的求根过程，函数得到的时间是非常的一致的。又如，一个堆排序的r项r的平均运行时间为O相关（r log r），而标准差为O（）[3]；问题在于，相对于平均值来说，标准偏差较小。

在实际应用中，多节点任务完成的同时，任务交会的操作将导致以太网上的碰撞。随机退避的结果将减缓应用程序。在这方面，由以太网硬件所引起的随机退避通常需要更长的时间。……