本科系統(tǒng)結構課件 chapter6-3

§3共享主存構形陣列處理機中并行存儲器的無沖突訪問訪問需求并行存取向量中各分量信息；可按行、列、對角線等方法存取(步長不一致)。存在問題存儲器帶寬限制—存儲器帶寬達不到向量帶寬；訪存方式(步長)不同，產生訪存沖突。解決方法采用多體交叉存儲器--增加MEM帶寬對向量分組操作--解決MEM帶寬小于向量帶寬問題一維數組連續(xù)訪問m=4個元素訪問，無沖突按2變址，沖突，降低一半M應取質數，避免沖突（只要變址跳距與m互質）a8a4a0a12a9a5a1.a10a6a2.a11a7a3.0123二維數組同時訪問某一行、主對角線或次對角線上的所有元素，無沖突同時訪問某一列，沖突，降低成1/4a20a10a00a30a21a11a01a31a22a12a02a32a23a13a03a330123錯位存放a22a13a00a31a23a10a01a32a20a11a02a33a21a12a03a300123a21a13a00a22a01a30a23a10a02a31a11a03a320123a20a12a334總結選擇適當的存儲體數m--達到無沖突訪問一維向量：順序存放，防止步長與m成比例；m取質數，且與步長互質。多維向量：錯位存放，滿足行、列、對角線等方式；常用方法：存儲體數為質數，將向量變換成一維數組S，再對S進行處理。消息尋徑方式四種尋徑方式：線路交換，存儲轉發(fā)、虛擬直通和蟲蝕尋徑等。消息格式：消息是結點間通信的邏輯單位，它常常由任意數目的長度固定的包所組成，因此其長度是可變的。包是包含尋徑目的地址的基本單位。每個包需要一個序號，以便重新組裝消息?？梢詫M一步分成一些固定長度的片，尋徑信息和序號形成頭片，其余的片是數據片。消息包片DDDDDDSRR：在消息傳遞網絡中通信的信息單位：消息、包和片的格式R：導徑信息S：序號D：數據片線路交換(circuitswitch)先建立一條從源結點到目的結點的物理通路，然后再傳遞消息。傳輸時延公式：

T=(Lt/B)*D+L/B，

其中：Lt為建立路徑所需小信息包的長度

L為信息包的長度

D為經過的結點數

B為帶寬。優(yōu)點：實際通信時間較短，使用緩沖區(qū)缺點：建立源結點到目的結點的物理通路開銷很大，占用物理通路的時間長。線路交換：無沖突，獨享，資源浪費存儲轉發(fā)(storeandforward)每個結點有一個包緩沖區(qū)，包從源結點經過中間結點到達目的結點。存儲轉發(fā)網絡的時延與源和目的地之間的距離成正比。傳輸時延公式：

T=(L/B)*D+L/B=(D+1)*L/B優(yōu)點：占用物理通路的時間比較短。缺點：包緩沖區(qū)大，時延大（與結點距離成正比）。有沖突，有緩沖，分片，路由StoredandForward（存儲轉發(fā)）BufferBufferBuffer虛擬直通(virtualcutthrough)當接收到用作尋徑的消息頭部時，即開始路由選擇。通信時延公式：

T=(Lh/B)*D+L/B=(Lh

*D+L)/B

其中：Lh是消息的尋徑頭部的長度，一般有，L>>Lh×D；通信時延可以近似為：T＝L/B，與結點數無關。虛擬直通(virtualcutthrough)當出現尋徑阻塞時，只能將整個消息存儲在尋徑結點中。主要優(yōu)點：通信延遲與結點數無關。主要缺點：每個結點需要有足夠大的緩沖區(qū)來存儲最大信息包。在最壞的情況下與存儲轉發(fā)方式的通信時延是一樣的，經過的每個結點都發(fā)生阻塞，都需緩沖蟲蝕尋徑(wormhole)把包分成更小的片。每個結點的尋徑器中有