串列演演算法并行化

并行計算，是將一個計算任務分攤到多個處理器上並同時運行的計算方法。由於單個CPU 的運行速度難以顯著提高，所以計算機製造商試圖將多個CPU 聯合起來使用。在巨型計算機上早已採用專用的多處理器設計，多台計算機通過網路互聯而組成的并行工作站也在專業領域被廣泛使用。台式機和筆記本電腦現在也已廣泛地採用了雙核或多核CPU。雙核CPU 從外部看起來是一個CPU，但是內部有兩個運算核心，它們可以獨立進行計算工作。在同時處理多個任務的時候，多核處理器可以自然地將不同的任務分配給不同的核心。但只運行一個以常規的串列代碼寫成的程序時，如何將計算任務拆分成多個部分並分解到多個核心上同時運行，是很困難的事情。有時甚至需要人工來讀懂原來代碼的含義，並以適合併行計算的語言重寫程序。這需要耗費大量的人力物力。最容易被并行化的計算任務稱為“易并行”1的，它可以直觀地立即分解成為多個獨立的部分，並同時執行計算。例如將一個數組裡的所有元素求和。我們可以先將數組分成兩段，對每段各自求和，最後再把結果相加。如果兩段的大小劃分得當，我們可以讓雙核CPU 的每個核心的運算量相當，在數組規模很大時，總的運算速度比單核CPU 能提高接近一倍。但並不是所有程序都能夠分解成這種效果。在軟體行業中很自然地提出這個問題：希望設計一種方法，能夠將一個常規的串列程序分解成兩個部分，使之能夠在CPU 的兩個核心上并行運算，並且希望能夠盡量發揮雙核心的計算能力。一般來說，如果兩個核心的運算量

//1有時也稱作“自然并行”。

//1基本相當，那麼總的運算效率較高2。如果出現某個核心空閑等待的狀態，雙核CPU 的運算力就沒有被充分的利用起來。