1、本版權歸劉吉超所有 侵版必究1. 非線性流水線（Nonlinear Pipelining）：是指流水線中除了串行連接的通路外，還有反饋回路。2. 等分寬度（channel bisection width）：將某一網絡切成相等兩半的各種切法中，沿切口的最小通道邊數。3. 向量處理機（vectorcomputer）：具有向量數據表示兵能通過向量指令處理向量元素的處理機4. 網絡直徑（network path）：互聯網絡任意兩節點之間的路徑最大值。5. MIMD：多指令流多數據流，多個控制器并行的控制多個處理器。6. 靜態流水線（static pipelining）：同一時間，流水線的各段只能按同一

2、種功能的連接方式工作。7. 動態流水線（type pipelining）:一段時間內，當某些段正在實現某種某些運算，另一些段正在實現另一種運算。8. 數據表示（Data representation）：能有機器硬件直接識別和引用的數據類型。9. 并行處理機（Parallel Prosessor）：重復設置多個同樣的pe，按照一定方式相互互連，在統一的控制部件（cu）的控制下，各自的對分配來的數據并行的完成同一指令所規定的操作。10. SIMD：單指令多數據流，能夠復制多個操作數，并把它們打包在大型寄存器的一組指令集。1. 代標識符的數據表示：為了縮短高級語言與機器語言的這種語義差距， 可讓機器

3、中的每個數據如下所示，都帶有類型標志位。標志符數據表示的主要優點為：（1） 簡化了指令系統和程序設計。 (2) 簡化了編譯程序。 (3) 便于實現一致性校驗。 (4) 能由硬件自動完成數據類型的變采用標志符數據表示帶來的問題可能有兩個。 (1) 每個數據字因增設標志符， 會使程序所占用的主存空間增加。 (2) 采用標志符會降低指令的執行速度。 2.CISC(Complex Instruction Set Computer）復雜指令集系統計算機：時間 60年代至70年代中期（2）方法：用一條指令代替一串指令增加新的指令 增強指令功能，設置功能復雜的指令 增加尋址方式 增加數據表示方式（2）優化的

4、途徑：面向目標代碼 面向高級語言 面向操作系統3. RISC(Reduced Instruction Set Computer）精簡指令系統計算機：時間：七十年代初至現在只保留功能簡單的指令,功能較復雜的指令用軟件實現，提高流水線效率。4.模擬與仿真（Simulation Emulation）：定義：在一臺現有的計算機上實現另一臺計算機的指令系統。全部用軟件實現的叫模擬，用軟件、硬件、固件混合實現的叫仿真模擬的實現方法：在A計算機上通過解釋或編譯實現B計算機的指令系統。A機器稱為宿主機，B機器稱為虛擬機。仿真的實現方法：直接用A機器的一段微程序解釋執行B機器的指令。A機器稱為宿主機，B機稱為目

5、標機。優缺點比較 （1）模擬方法速度低，仿真方法速度高（2）仿真需要較多的硬件（包括控制存儲器）（3 ）系統結構差別大的機器難于用仿真方法實現（4） 除了指令系統之外，還有存儲系統、I/O系統、中斷系統、控制臺的操作等模擬方法用于計算機系統的設計過程 在一臺已有的機器上用模擬方法實現正在設計中的機器的指令系統等。具體過程如下：設計方案模擬性能評價修改設計投產5. 緊耦合以及松散耦合多處理機6.尋徑算法有哪些？各有什么特點？存儲轉發（Store-and-Forward） 缺點： 每個結點必須對整個消息進行緩沖，緩沖器較大。 網絡時延與發送消息所經歷的結點數成正比虛擬直通（Virtual cut

6、through）中間結點沒有必要等到整個消息全部被緩沖后再作出路由選擇，只要消息的目的信息域可用后，就可以作出路由選擇。線路交換（Circuit Switching） 在傳遞一個消息之前，就為它建立一條從源結點到目的結點的物理通道。在傳遞的全部過程中，線路的每一段都被占用，當消息的尾部經過網絡后，整條物理鏈路才被廢棄。缺點：物理通道非共享 傳輸過程中物理通道一直被占用Wormhole交換（Wormhole Switching)優點：（1）每個結點的緩沖器的需求量小。（2）較低的網絡傳輸延遲。（3）通道共享性好、利用率高。（4）易于實現Multicast和Broadcast。6. W （Omeg

7、a）網絡：開關單元：22四功能開關ISC：洗牌變換+恒等變換控制方式：采用單元控制方式。當目的地址編碼從高位開始的第i位（從0開始）為0時，第i級的22開關的輸入端與上輸出端連接，否則輸入端與下輸出端連接。例子：UIUC的CedarIBM的RP3NYU的Ultracomputer網的特點(2)：并不是所有的置換在網中一次通過便可以實現。 網是阻塞網絡：出現沖突時，可以采用幾次通過的方法來解決沖突。網的特點(3)：當采用kk開關元件時，則可以定義k路洗牌函數來構造更大的級數為logkn的網絡。1.稀疏向量：定義：0元素很多，非0元素很少的向量稱為稀疏向量采用壓縮方法存儲稀疏向量可以節省存儲空間。

8、可以還原之后進行運算，也可以用壓縮方法直接進行運算2. 向量的縱橫處理方式：3. 有三種處理方式： 橫向處理方式，又稱為水平處理方式，橫向加工方式等。向量計算是按行的方式從左至右橫向地進行。也稱為水平處理方式，橫向加工方式等逐個分量進行處理：假設中間結果為T(I)計算第1個分量：T(1) B(1)C(1)Y(1) A(1)T(1)計算第2個分量：T(2) B(2)C(2)Y(2) A(2)T(2) 計算最后一個分量：T(N) B(N)C(N)Y(N)A(N)T(N) 存在兩個問題： 在計算向量的每個分量時，都發生寫讀數據相關。流水線效率低 如果采用多功能流水線，必須頻繁進行流水線切換 橫向處理

9、方式對向量處理機不適合 即使在標量處理機中，也經常通過編譯器進行指令流調度。縱向處理方式，又稱為垂直處理方式，縱向加工方式等。向量計算是按列的方式自上而下縱向地進行。 也稱為垂直處理方式，縱向加工方式等T(1) = B(1) + C(1)T(2) = B(2) + C(2)T(n) = B(n) + C(n)Y(1) = A(1)T(1)Y(2) = A(2)T(2)Y(N) = A(N) T(N) 采用向量指令只需要2條： VADD B， C， T VMUL A， T， Y 這種處理方式適用于向量處理機 數據相關不影響流水線連續工作。 不同的運算操作只需要切換1次。 這種處理方式適用于存儲器

10、-存儲器結構縱橫處理方式，又稱為分組處理方式，縱橫向加工方式等。橫向處理和縱向處理相結合的方式。用于寄存器-寄存器結構的向量處理機中，向量寄存器的長度是有限的。當向量長度N大于向量寄存器長度n時，需要分組處理。 分組方法： 其中：為余數, 共分組。 組內采用縱向處理方式，組間采用橫向處理方式。因此，也稱為分組處理方式，縱橫向加工方式等。 運算過程為： 第組：T(1, n) = B(1, n) + C(1, n)Y(1, n) = A(1, n)T(1, n) 第組：T(n+1, 2n) = B(n+1, 2n)C(n+1, 2n)Y(n+1, 2n) = A(n+1, 2n)T(n+1, 2n

11、) 最后第k+1組：T(kn+1, N) = B(kn+1, N) + C(kn+1, N)Y(kn+1, N) = A(kn+1, N) + T(kn+1, N) 每組用兩條向量指令， 每組發生相關兩次， 其中組內發生數據相關一次， 組間切換時發生相關一次。 主要優點：減少訪問主存儲器的次數 例如：中間變量T不寫入主存儲器4. 非線性流水線調度的任務是要找出一個最小的循環周期，按照這周期向流水線輸入新任務，流水線的各個功能段都不會發生沖突，而且流水線的吞吐率和效率最高。1.非線性流水線的表示線性流水線能夠用流水線連接圖唯一表示對于非線形流水線，連接圖不能唯一表示工作流程，因此，引入流水線預約

12、表一張預約表可能與多個流水線連接圖相對應一個流水線連接圖對應與多張預約表非線性流水線的沖突 啟動距離：連續輸入兩個任務之間的時間間隔 流水線沖突：幾個任務爭用同一個流水段（2）立方體網絡中的E立方體尋徑：假設有一個N = 2n個結點的n方體。每個結點的二進制編碼為：b = bn-1 bn-2 b1 b0s = sn-1 sn-2 s1 s0d = dn-1 dn-2 d1 d0如何確定一條從s到d的步數最小的路徑？將n維表示成i = 1, 2, n，其中第i維對應結點地址中的第i-1位。設v = vn-1 vn-2 v1 v0是路徑中的任一結點。方法： （1）計算方向位。 使 i = 1 , v = s， 開始下面的步驟。（2）如果ri = 1，則從當前結點v尋徑到下一結點 ； 如果ri = 0，則跳過這一步。（3）i = i + 1，如果 i n，則轉第（2）步，否則退出。如下面的例子：尋徑： （1）計算方向位。i = 1，v = s 特點：尋徑按照從維1到維4的順序進行。 如果s和d的第i位相同，則沿維i的方向不需要尋徑，否則從當前