互连与通信课件.pptVIP

3.傳輸時延與吞吐量 一個消息的傳輸時延：從它在源結點進行發送初始化到它在目的結點完整的被接收所耗費的時間。 一個網路的傳輸時延：在一定條件下發送消息的平均時延。 網路的吞吐量：單位時間內網路所能傳輸的消息數目或長度。 4.傳輸時延的公式 其中，Ts稱為建立時延，Tn稱為網路時延，Tb稱為阻塞時延。 它們具體定義如下： 建立時延Ts：一個消息在源結點和目的結點上裝配和分解、從記憶體拷貝到通信緩衝區以及正確性驗證等所耗費的時間。它和機器本身的硬體、軟體技術有關。 其中： Tss稱為源結點時延：從發送進程開始消息發送初始化到消息的頭部進入網路所經歷的時間。 Tsd稱為目的結點時延：從消息的尾部到達目的結點到消息完全被接收進程接收所經歷的時間。 網路時延Tn：消息頭部從源結點進入網路到消息的尾部到達目的結點的時間間隔。 其中： Tp?D稱為結點時延：其中Tp是消息在它所經過的路徑上的每個中間結點上的平均時延，D為中間結點或源結點與目的結點之間的距離。 L/B稱為線路時延：其中L為消息長度，B為結點之間的通道帶寬。 阻塞時延Tb：消息傳遞過程中其他所有可能的時延（主要原因是資源衝突）。 5.網路的拓撲結構 第一代並行電腦：HyperCube 第二代並行電腦：n—Mesh 6.網路的尋徑演算法 決定發送一個消息到其目的地所經過的路徑。 可以分為： 最短路徑演算法 非最短路徑演算法 或者： 確定性演算法：路徑的選擇只依賴於它所發送的消息的源結點和目的結點。 可適應演算法：消息從結點A到結點B可以由幾條不同的路徑。 7.網路的流控制 當一個消息在網路中沿著某條路徑傳送時，互連網絡如何來為它分配通道和緩沖器。 3.4.2尋徑演算法 我們介紹四種尋徑方式： 存儲轉發（Store-and-Forward） 虛擬直通（Virtualcutthrough） 線路交換（CircuitSwitching） Wormhole交換（WormholeSwitching) 1.存儲轉發 當一個消息到達中間結點A時，A把整個消息放入其通信緩衝器中，然後在尋徑演算法的控制下選擇下一個相鄰結點B，當從A到B的通道空閒並且B的通信緩衝器可用時，把消息從A發向B。缺點： 每個結點必須對整個消息進行緩衝，緩衝器較大。 網路時延與發送消息所經歷的結點數成正比 2.虛擬直通 中間結點沒有必要等到整個消息全部被緩衝後再作出路由選擇，只要消息的目的資訊域可用後，就可以作出路由選擇。 其中，Lh為消息頭部開始到其目的資訊域的長度，顯然有LLh，所以D的影響比較小。 而當通向下一結點的通道忙或結點的緩衝器非空閒時，必須把整個消息緩衝起來，這時和存儲轉發一樣。 3.線路開關 在傳遞一個消息之前，就為它建立一條從源結點到目的結點的物理通道。在傳遞的全部過程中，線路的每一段都被佔用，當消息的尾部經過網路後，整條物理鏈路才被廢棄。 其中，Lc是為消息建立物理通路所傳遞的控制資訊的長度。當LLh時，D的影響較小。 缺點： 物理通道非共用 傳輸過程中物理通道一直被佔用 4.Wormhole Dally於1986年提出。 首先把一個消息分成許多片，消息的頭片包含了這個消息的所有尋徑資訊。尾片是一個其最後包含了消息結束符的片。中間的片均為數據片。 片是最小資訊單位。每個結點上只需要緩衝一個片就能滿足要求。 用一個頭片直接開闢一條從輸入鏈路到輸出鏈路的路徑的方法來進行操作。每個消息中的片以流水的方式在網路中向前“蠕動”。每個片相當於Worm的一個節，“蠕動”以節為單位順序的向前爬行。 當消息的頭片到達一個結點A的尋徑器後，尋徑器根據頭片的尋徑資訊立即做出路由選擇： （1）如果所選擇的通道空閒而且所選擇的結點B的通信緩衝器可用，那麼這個頭片就不必等待，直接通過結點A傳向下一個結點B；隨後的其他片跟著相應的向前“蠕動”一步。當消息的尾片向前“蠕動”一步後，它剛才所佔用的結點就被放棄了。 （2）如果所選擇的通道非空閒或者所選擇的結點的通信緩衝器非可用，那麼這個頭片就必須在此結點的通信緩衝器中等待，直到上述兩者都可用為止；其他片也在原來的結點上等待。此時，被阻塞的消息不從網路中移去，片不放棄它所佔有的結點和通道。這是Wormhole技術和其他流