平行計算和計算機叢集/理論
人們用計算機叢集做什麼？
- 網路
- 搜尋引擎索引
- 資料庫
- 科學和工程工作
- 天氣建模和預測
- 分子建模
- 產品設計和模擬
一般來說，實現並行架構有兩種方法。它們可以分別使用，也可以將這兩種方法組合起來使用。共享記憶體模型是一種所有處理器共享記憶體和地址空間的模型。架構中的所有處理器都可以訪問所有連線的主記憶體。訊息傳遞模型是一種將資訊打包到訊息中的模型。這些資訊的離散單元可以傳遞給架構中的各個 CPU。這兩種架構都有各自的優缺點。
共享記憶體模型是所有 CPU 都可以定址機器主記憶體的模型。通常，主記憶體可以透過匯流排訪問。這使得所有 CPU 都可以使用記憶體地址，並且地址可以在不同的 CPU 之間傳遞。讓所有 CPU 都透過匯流排訪問記憶體會引入一些問題。比如匯流排的頻寬，如果匯流排很小，而 CPU 的數量很多，那麼 CPU 使用率的最佳化將難以實現。通常，匯流排通訊會使用本地快取來增強。處理器的 L1 和 L2 快取，然後就會引入快取一致性的挑戰。如何確保主記憶體和快取中的資料足夠更新，以便所有 CPU 都能看到正確的資料。這裡有幾種策略可以實現正確和最佳化的操作。
訊息傳遞系統具有與 CPU 不直接連線的記憶體，甚至可能分佈在各個地理位置。這會導致傳送和接收系統，其中資料被打包成訊息，並透過網路傳送到網路中的其他機器。
Hadoop 的核心是兩個開源框架的組合：MapReduce 和 HDFS。兩者都是基於谷歌釋出的同名白皮書的開源實現。MapReduce 是一個基於谷歌同名框架的處理框架。MapReduce 會獲取儲存在 HDFS 中的資料，並在叢集中的每個節點上進行處理。MapReduce 由程式設計師定義兩個過程：Map 和 Reduce。Mapper 以鍵值對的形式獲取資料。Mapper 也會輸出鍵值對。Reducer 的輸入格式是一個鍵和一個向量，其中包含由 Mapper 輸出的該鍵的所有值。HDFS 是 Hadoop 檔案系統。HDFS 是谷歌分散式檔案系統的實現。HDFS 是一個軟體實現，它將檔案的儲存分佈到叢集中的多個節點。預設複製因子為 3，以確保以極高的機率不會丟失任何資料。
並行處理是在多個處理器上同時執行相同的任務（分割並專門調整），以便獲得更快的結果。並行性可以來自具有多個處理器的單臺機器，也可以來自連線在一起形成叢集的多臺機器。
阿姆達爾定律是 邊際收益遞減定律 的一個證明：雖然可以將計算機的某個部分加速一百倍甚至更多，但如果改進隻影響總體任務的 12%，那麼最好的 加速 可能只能達到 倍更快。
更準確地說，該定律關注的是對計算進行改進後可以實現的 加速，改進影響了計算的 P 比例，改進的加速為 S。（例如，如果一項改進可以加速 30% 的計算，P 將為 0.3；如果改進使受影響的部分速度提高一倍，S 將為 2。）阿姆達爾定律指出，應用改進後整體加速將為
- .
為了理解該公式的推導過程，假設舊計算的執行時間為 1，以某個時間單位計量。新計算的執行時間將是未改進部分所花費的時間（即 1 − P）加上改進部分所花費的時間。改進部分的執行時間是其原執行時間除以加速比，因此改進部分的執行時間為 P/S。最終的加速比是透過將舊執行時間除以新執行時間計算得出，這正是上面公式所做的操作。
在並行化的特殊情況下，阿姆達爾定律指出，如果 F 是計算中無法並行化的部分（即順序執行的部分）的比例，(1 − F) 是可以並行化的部分的比例，那麼使用 N 個處理器所能達到的最大加速比為：
- .
當 N 趨近於無窮大時，最大加速比趨近於 1/F。在實際應用中，當 (1 − F)/N 比 F 小很多時，價效比會隨著 N 的增加而迅速下降。
例如，如果 F 僅為 10%，無論 N 的值有多大，問題最多隻能加速 10 倍。因此，平行計算 僅適用於少量處理器，或者 F 值非常低的所謂簡單並行問題。並行程式設計 的一大技巧就是嘗試將 F 降低到儘可能小的值。