以太網并行處理程序退避方法分析

李 雋

(北京市通州區人民檢察院 技術處，北京 101100)

1 引言

以太網的發送過程中，先由一個或多個節點產生發送幀和測試線，然后嘗試發送并盡快在完成當前傳輸。如果是多于一個節點，節點會產生碰撞，生成隨機的補償時間，然后再次嘗試發送。

我們假設在以太網上均勻工作站上運行并行處理的應用程序，并考慮任務交會幀的發送。例如，在一個消息傳遞中，我們可能有求根程序[1]。在這里，一個已知函數在所給間隔有一個單一根，此根是程序在一次平行迭代的結果（按照所需的精確度）。在任一給定的迭代中，當前的間隔要搜索n個小區間，其中，n是機器的總數量。每一個節點檢查其指定節點的子區間，然后告知上層節點給定函數在此子區間信號是否發生變化。這些子區間中只有一個會發生這樣的變化，然后，它會成為新的區間。新區間端點的值將被廣播，使它們可以劃分成新的子區間。在共享內存范式下（分布式共享內存），屏蔽操作會產生類似的模式。

出現在這里的問題是，在許多應用中任務時間（包括通信延遲）發生小的變異[2]。例如，上述的求根過程，函數得到的時間是非常的一致的。又如，一個堆排序的r項r的平均運行時間為O相關（r log r），而標準差為O（）[3]；問題在于，相對于平均值來說，標準偏差較小。

在實際應用中，多節點任務完成的同時，任務交會的操作將導致以太網上的碰撞。隨機退避的結果將減緩應用程序。在這方面，由以太網硬件所引起的隨機退避通常需要更長的時間。在文獻[4]中，提出編程關閉的概念來解決這個問題。假設有n個節點的任務需要處理，在節點k完成任務的時間為Tk時，運行在節點k的軟件會產生自己的關閉，延遲kδ為交會幀管理器節點在發送之前的時間。通過軟件產生一個小的、確定的補償，可以避免由以太網硬件產生不必要的長補償時間。

2 分析

令f表示每個Tk的概率密度函數，依據編程退避，確定預期的第一輪碰撞。在第一輪中，節點i和j發生碰撞，讓1ij等于1，否則為0。第一輪碰撞的總數是

讓τ表示一任務交會幀的傳輸時間。這通常將遠遠小于任務時間，因為幀通常含有非常少的數據。讓Uk表示節點k的實際時間，即開始發送時間

假設Uk是獨立變量。那么

這里

公式(1)表明E(N)是O(n2)的幅度。適合的編程退避快速增長的系統大小為n。

公式(2)，我們可以得到一個數量的下界。

引理：假設X和Y是連續的獨立的隨機變量，具有相同的變化γ2和EY=EX+d。然后

證明：首先定義Z為X?(Y?d)，從而有E[(X?Y)2]代替E[(Z?d)2]。后者的數量將等于2γ2+d2，因為Z的均值為0，方差為2γ2。然后讓g表示X?Y的密度

得到的結果。

以Ui和Uj代入X和Y，

δ2是密度f的方差。

3 模擬

在預計的時間η內，所有的節點都成功發送一個消息，需要解決下列問題：

?有多少通過編程退避來改善以太網硬件管理傳輸？

?所有其他因素固定不變的情況下，如何設置系統n的最優值δ？

?設c為尺度參數的任務時間的密度函數，

對于一些函數h和一些恒定的Q值，由于c的增加，得到密度具有相似的形狀，但更分散，并δ將正比c。

在模擬中，任務時間首先采取的是密度均勻U(1?c,1+c)。因此，周圍的平均值為1.0，與c一同起到尺度參數的作用。

幀的傳輸時間τ，假定為小于1.0的平均任務的時間。具體地，在這里給出的所有的模擬，τ=0.1。這是一個實際的假設，否則的通信被架空（甚至無碰撞）對于有效的加速并行來說太高。

公式(2)是一個典型的關于δ的遞減函數，隨著δ的增加，前端會出現更多的延遲η。因此，我們可以將η看作δ的函數。

圖1c=0.1

我們開始c=0.1進行一個模擬，在圖1中，系統為一個較小的值，32、64和128。這里是一個在任務時間內完成的擬模擬，這就形成對我們工作的幫助。因此，編程退避具有強大的加速任務交會過程，292%、439%和619%的大小。還要注意的是，對于更大的系統，編程退避顯現出更強大的作用。

作為n的函數，δ的最優值被看作是相對恒定的。近恒定查看時，在以下情況下：如果任務時間是完全不變的，δ的最優值為τ；此值將導致在一個時間表下，第(i+1)個節點開始后立即發送第i個。

圖2c=0.8

這種推理不能被應用于c=0.8的情況下，如圖2所示。在任務時間變化較大的情況下，相應的加大了加速比，較為溫和的條件是：158%、324%和507%。然而，有趣的是，δ的最優值與前面討論的情況類似。

如上文所述，如果任務時間是完全恒定的，δ的最佳值為τ。因此，我們所期望的最佳的δ只是略多于設置的任務時間。進行初步模擬值τ＜0.1。此外，典型值τ是經驗型的。

圖3c=0.1分布圖

圖4c=0.8分布圖

圖5c=10.0分布圖

然而，即使是用c=0.8的任務的時間分布具有一個相當小的標準差，所以我們轉向使用指數分布，參數c是分布的平均值。圖3和圖4分別對應c=0.1和c=0.8。圖1和圖2的結果是相似的。然而，結果為c=10.0，如圖5中所示，有很大的不同。這里的任務時間有足夠多的變量，編程退避簡單地產生多余的延遲是以太網卡所需要的。

4 討論與結論

我們構建一個理論模型，在任務時間的小變異的影響以太網的并行處理。該模型表明，總體任務交會時間上的順序O(n2)，我們得到一個下界的基礎上的任務時間的標準偏差。

作為一個潛在的解決這個問題，我們已經發現，編程退避可以產生非常大的加速，在實際中，任務時間是一個小的標準偏差。此外，最佳值δ在這種情況下，似乎是相當不敏感的類型分布，似乎是一般約10-20%，大于一個任務交會消息的傳輸時間。

[1]AKL S G.The Design and Analysis of Parallel Algorithms[M].Prentice Hall,1989.

[2]ADVE V S,VERNON M K.The Inf l uence of Random Delays on Parallel Execution Times.Proceedings of the 1993 ACM Sigmetrics Conference on Measurement and Modeling of Computer Systems.1993:61-73.

[3]GONNET G.Handbook of Algorithms and Data Structures.Addison-Wesley,1984.

[4]DAVIES G,MATLOFF N.Network-Specif i c Performance Enhancements for PVM.Proceedings of the 4th IEEE International Symposium on High-Performance Distributed Computing,1995:205-210.