平行處理
程式層式的平行:允許多個程式同時執行,使用time sharing(分時)作業即可
副程式層式的平行:允許同一個程式的副程式同時執行,使用 multitasking(多工)作業即可
instruction-level parallelism(指令層式的平行):允許同一個程式中多個指令同時執行,需硬體支援 ex:superscalar machine
平行處理電腦可解決
1主記憶體問題
2匯流排結構問題,也稱范諾曼瓶頸,可分為:
physical bottleneck(實際的瓶頸):整體效能受限於匯流排結構的頻寬
可藉由連接網路取代匯流排結構解決
logical bottleneck(邏輯的瓶頸):受限於命令式語言
可藉由函數式語言取代命令式語言解決
………….
parallel machine(平行電腦)
常見的有：
array processor(陣列處理器電腦)
平行電腦中最適合處理向量資料的電腦架構
屬於SIMD架構，專門處理vector data(向量資料)
平行處理技巧：
VLIW(very long instructionword machine超長指令字組電腦)
屬於MISD架構，將數個允許同時執行的運算包裝成一個很長的指令，一個指令的功能相當於循序電腦的多個指令，因此可減少指令存取的次數
需要power多，因為有多個獨立的電路需要同時執行
平行處理技巧：將CPI降低到小於一，提昇計算速度
multiprocessor(多處理器電腦)
屬於MIMD架構，使用多個處理器同時執行
平行電腦中最具擴充性的電腦架構
可分為
multi- processor(多處理器系統):也稱tightly coupled system(緊密結合系統)
多個cpu,memory,i/o互相連接
ex:SMP,NUMA
multi-computer(多電腦系統):也稱loosely coupled system(鬆散結合系統)
多個相互獨立的 cpu,memory,i/o透過網路互連
ex:cluster
pipelined computer(管線式電腦)
平行電腦中最具成本效益的電腦架構
需要的power少，因為只需要一個共用計時器來驅動所有硬體階段的同步執行
平行處理技巧：將CPI降低到為1，提昇計算速度
優點:成本低，因為對硬體電路所需要的改變不大，最符合成本效率
缺點:和管線作業一樣
ps:pipeline是指管線作業，就是將工作切割並可同時執行多個子工作
ps:superpipeline是指將工作切割的更細增加管線深度並提高管線週期頻率，並對所有單元盡可能採用pipleline，也就是特別加強的pipeline
super scalar machine(超純量電腦)
允許一個計時週期信號同時啟動多個指令的執行,提供instruction-level parallelism
需要power多，因為有多個獨立的電路需要同時執行
平行處理技巧：將CPI降低到小於一，提昇計算速度
限制有:
程式平行化的限制:需先進行指令間關係分析,只有獨立的指令才可同時執行
硬體資源限制:一次可同時執行指令的個數,須考慮硬體是否能支援
ps:傳統電腦僅能一個計時週期信號啟動一個指令的執行
data-flow machine(資料流程電腦)
平行電腦中具最佳處理效果的架構
採data driven的執行方式
ps:control flow machin(控制流程電腦)屬循序的執行方式
vector computer(向量電腦)
也稱numeric supercomputer(數值超級電腦)
平行電腦中最追求效能的架構
使用管線式電腦,陣列處理器電腦,多處理器電腦的技術
…………….
SMP(symmetric multiprocessing,對稱式多重處理器)
一部電腦內至少具有2個能力相近的處理器
使用共用相同的主記憶體和I/O裝置
使用的技術包括:time-shared bus(分時匯流排),multiport memory(多埠記憶體)
SMP作業系統設計需考量的有:
concurrent process(同時發生的程序)
scheduling(排程)
synchronization(同步)
memory management(記憶體管理)
reliability and fault tolerance(可靠度及容錯)
clusters(叢集)
將一組互連的電腦(節點)如同單一的計算資源一般地運算
優點包括:
absolute scalability(絕對規模)
incremental scalability(遞增尺度)
high availability(高可用度)
superior price/performance(良好的成本/效能)
使用的技術包括:
failure management(失效管理)
load balancing(負載平衡)
parallelizing computation(平行計算)
NUMA(nonuniform memory access,不均勻記憶體存取)
在單一系統上可支援更多處理器
ps:一般SMP限制處理器約為16-64個
ps:SMP屬於UMA(均勻存取記憶體)
…………………………..
平行電腦的連接網路分為
static interconnection network(靜態連接網路)
常用於無共用記憶體,並用訊息傳遞的多電腦系統
所有組成元件的連接固定
dynamic interconnection network(單階動態連接網路)
常使用共用記憶體,不適用於組成元件個數太多的多cpu系統
所有組成元件的連接使用switch(交換開關)
多階動態連接網路
switch(交換關關)較少,並分為以下兩種
cross-bar switch-based switch(交叉點型交換關關)
cell-based switch(細胞型交換開關)
static interconnection network可分為
exhaustive or completely connected network(完整連接網路)
各CPU與所有CPU連結
一維陣列網路
與最相鄰的2個CPU連結
適用於管線作業的處理器管線
2-d mesh network(二維陣列網路),也稱nearest neighbor mesh(鄰近網狀結構)
與最相鄰的4個CPU連結
容易佈線與擴充,特別適用於超大型積體電路的製作
ex:陣列處理器電腦ILLIAC IV
systolic array(心藏壓縮式陣列)
與最相鄰的6個CPU連結
x連接網路
與最相鄰的8個CPU連結
cube network(立方體連接網路)
3維空間的連接網路,各cpu有3位元的座標,可連接8個cpu
hypercube network(超立方體網路)
N維空間的連接網路,可連接2^N個cpu,且會有N*2^(N-1)條鏈結相連
dynamic interconnection network可分為
single bus(單一匯流排)
有一定頻寬,不適合大量cpu的系統
system and local bus(系統匯流排,區域匯流排)
適用於單一微cpu的系統擴充為多個微cpu的系統
不適合大量處理器的系統
cross-bar switch(交叉點交換網路)
每個記憶體模組有一條專用的匯流排與其它的組成元件連接
不適用於組成元件個數較多的多cpu系統
multiport memory(多連接埠記憶體)
各記憶體模組有多連接埠,可與多個組成元件連接
製作成本太高
cell- based switch的多階動態連接網路
使用 destination-tag(目的地標籤)的路徑選擇演算法
可分為
baseline network(底線連接網路)
連接2^n個輸入與輸出,需n個階段,各階段要用2^(n-1)個switch
2進制的連接網路
omega network(奧米茄連接網路)
連接2^n個輸入與輸出,需n個階段,各階段要用2^(n-1)個switch
2進制的連接網路
使用perfect shuffle(完美洗牌)的鏈結安排方式
delta network(三角洲連接網路)
連接x^n個輸入與輸出,需n個階段,各階段要用x^(n-1)個switch
x進制的連接網路
使用perfect shuffle(完美洗牌)的鏈結安排方式
………………………………..
multi-processor系統使用cache是效能的關鍵
多個cpu若對共用記憶體進行存取,會使得存取衝突的機率增加
使用多個 cache可減少對共用記憶體存取的次數,減少衝突
同一份資料存放在多個cache中,會導致cache中資料不一致的情形發生
保持cache內容一致方式有
軟體實作:
1將每個資料項目區分成為shared or non-shared(共用與非共用)以及read-only or writeable(唯讀與可寫入)
2將 writeable的shared資料項目集中存放在一個特殊區域中並加以控制,即可保持一致性
硬體實作
1使用snooper(窺視器)監視共用記憶體匯流排
2cache,cpu, 共用記憶體之間制定cache consistency protocol
ps:snooper是一種cache控制器
cache consistency protocol(快取記憶體一致性協定)
保持資料在多個cache仍然具有一致性的內容,有以下2種:
write through protocol(貫穿式寫入的協定)
實作簡單,效果只比軟體實作好一些
每一次寫入都使用貫穿式寫入,snooper會監控每次寫入的活動
write once protocol(僅寫一次的協定)
實作複雜,效果較好
第一次寫入使用貫穿式寫入,之後的寫入在snooper cache中進行
有以下四種狀態
invalid(無效的狀態)
clean(乾淨的狀態)
reserved(保存的狀態)
dirty(骯髒的狀態)
…………………………..
管線作業的流程控制
為防止不同工作在管線內部發生衝突,並決定新工作進入管線而不會引起衝突的時間
預留表:表示工作在管線中的執行流程
衝突向量
狀態轉移圖:可表示管線內部所有可能的狀態
貪婪迴路
最小平均延遲