以太網(wǎng)并行處理程序退避方法分析

李 雋

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

1 引言

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

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

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

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

2 分析

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

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

假設(shè)Uk是獨立變量。那么

這里

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

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

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

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

得到的結(jié)果。

以Ui和Uj代入X和Y，

δ2是密度f的方差。

3 模擬

在預(yù)計的時間η內(nèi)，所有的節(jié)點都成功發(fā)送一個消息，需要解決下列問題：

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

?所有其他因素固定不變的情況下，如何設(shè)置系統(tǒng)n的最優(yōu)值δ？

?設(shè)c為尺度參數(shù)的任務(wù)時間的密度函數(shù)，

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

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

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

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

圖1c=0.1

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

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

圖2c=0.8

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

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

圖3c=0.1分布圖

圖4c=0.8分布圖

圖5c=10.0分布圖

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

4 討論與結(jié)論

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

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

[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.