多核多緒多樂趣

「多核心處理器有前途嗎?」幾年前,或許只是單純的疑問句,而到了今時今日,無庸置疑地已經成為了肯定句。

有沒有注意到,曾經每年都在急速成長的 CPU 處理速度,已經停留在 2 至 3G MHz 很久的一段時間了呢?在個人電腦的硬體配備中,已經由追求 CPU 的速度提升,轉向追求核心數量的增加。主流的 CPU 規格也逐漸由雙核心進步到四核心、六核心,甚至是未來的八核心中央處理器。「多核心」聽起來很酷,而這個所謂的多核心處理器的意義何在?

「Programming for Parallelism」中,共有 8 段配上中文字幕的影片,由 Intel 公司的 James Reinders 由淺至深地簡介了多核心硬體發展的必要性,以及相關程式應用技術的入門概念。其中在第一段的影片內容中,提到關於提升處理器時鐘頻率的作法,有幾項很關鍵的問題點:

  • 繼續往上提升處理器的時鐘頻率有什麼問題?功率是我們最常聽見的說法。提高處理器的時鐘頻率,對於執行速度的提升會越來越不明顯;也許性能提升了 13%,但是功率的卻多耗損了 73%。所以如果我們繼續提升處理器的時鐘頻率,一來電費不划算,二來使用 CPU 煎牛排再也不是夢想。
  • 另一個問題在於記憶體。過去幾年間,CPU 很快樂的以倍速飛快地成長著,然而在現實世界的硬體市場中,記憶體的時鐘頻率已經遠遠地跟不上處理器時鐘頻率的提升。就算處理器的動作再快,也得從記憶體拿取資料,並且將計算完畢的資料恭恭敬敬地交回給記憶體才行,所以在記憶體速度跟不上的情況下,處理器運算速度再快也只能空轉等待。
  • 還有一個問題點在於可平行處理的指令集。能夠進行平行處理的指令集,已經被開發利用得差不多了,接下來即使不斷提升處理器的速度,也不能保證得到更好更快的執行效能,而只是徒增更多 CPU 閒置發呆的時間。

深刻體會上述三項提升處理器時鐘頻率的發展限制之後,總算有聰明絕頂的人想出更好的解決方案:「我們何不在一個處理器之中,塞入更多的內核單位,功率大致與原先相同,卻能大幅提昇處理器的性能至 73% 左右?」因此我們有了雙核心、四核心,以及六核心處理器。處理器核心的數目,未來將會不斷往上成長。

既然瞭解了多核心硬體的發展,已經成為勢在必行的現在進行式以及未來的趨勢,那麼身為遊戲開發者或遊戲程式設計者,也該回頭問問自己:「這和我有什麼關係?」關於這個問題,請聽聽以下兩位開發者的發言:

  • TV Games 開發者 A 君:在 Cosole 程式的開發設計之中,為了彌補非常有限的主記憶體與繪圖記憶體空間,程式設計者必須將處理器的效能發揮至極限。目前 XBox360 中已經使用了三核心的 PowerPC 處理器系統,可預見的是,未來的電視遊樂器 Console,將會朝向更多核心的平行硬體架構方向發展。
  • PC Games 開發者 B 子:以目前的情況來說,要將程式特別為多核心處理器進行最佳化,是非常困難的事,畢竟 PC 平台不像 Console 平台一樣,屬於單一制式化的硬體規格。但是在未來的二至三年內,多核心處理器的電腦系統,也將會在 PC 平台中佔有相當大的比例。

對於程式設計者,甚至是專案的執行製作者來說,認識多核心的運用潛力,並且學習如何使用相關的技術,已經是刻不容緩的存亡關鍵。而為了正確應用多核心的程式開發技術,有三項至關緊要的關鍵概念必須謹記於心:

  • 可擴展性 (Scalability):擴展的目的並不是為了使用 8 個核心以獲取 8 倍的效能,我們需要的是維持程式系統的可擴展性,不將程式的多緒架構寫死,限定只能在雙核或是四核的硬體系統中執行,而是要能夠使程式系統不論在多少核心的情況下都能夠正常運作,並且同時獲得執行效能上的提升。
  • 正確性 (Correctness):防止競賽條件 (Race Condition) 與鎖死 (Deadlock) 狀況的產生,並且確認你的多緒程式系統,能夠在單緒的環境下得到正確的執行結果,對於專案的後續測試、除錯與維護程序,將會有非常大的助益與影響。
  • 可維護性 (Maintainability):為了因應不斷快速成長與變化的多緒程式設計技術發展,程式設計者要避免直接使用低階或原始的程式模組如 pthread 或 Windows 執行緒,而應該利用各項高階的抽象化工具與函式庫,例如:OpenMP、MPI、執行緒結構模組 (Threading Building Blocks),才能夠達到良好的可維護性以及跨平台能力。

關於 OpenMP 的使用,來看一個最簡單的迴圈範例:

#include < stdio.h >
#include < omp.h >

void main()
{
	#pragma omp parallel for
	for (int i = 0; i < 16; i++) {
		printf("thread [%d]: print number %d\n", omp_get_thread_num(), i);
	}
}

上述的程式碼,編譯執行後的結果如下所示:

thread [0]: print number 0
thread [0]: print number 1
thread [0]: print number 2
...
thread [0]: print number 15

接著,請在 Visual Studio 的程式專案環境中,開啟專案屬性設定,在 [ C/C++ ][ 語言 ] 頁面中,將 [ OpenMP 支援 ] 項目改成 [ 是 ] 的選項,然後在雙核心的電腦上執行程式,將得到非常不一樣的執行結果:

thread [0]: print number 0
thread [1]: print number 8
thread [0]: print number 1
thread [0]: print number 2
thread [1]: print number 9
thread [0]: print number 3
thread [0]: print number 4
thread [1]: print number 10
thread [0]: print number 5
thread [0]: print number 6
thread [1]: print number 11
thread [0]: print number 7
thread [1]: print number 12
thread [1]: print number 13
thread [1]: print number 14
thread [1]: print number 15

如程式輸出的結果所示,只要在 for 迴圈前使用神奇的 #pragma omp parallel for 指令,並且開啟 OpenMP 的編譯選項,就能夠使迴圈中的程式碼以多執行緒的方式進行平行處理,而獲得執行效能上的提升。即使是在傳統單核心的處理器系統中,同樣能夠正確編譯並且執行上述的程式範例,不會造成任何問題。

對於既存的程式碼來說,只要正確地使用 OpenMP 技術,無須大幅更動現有程式碼的結構與計算邏輯,就能夠很快速地得到多核心運算的執行成效,甚至能夠在專案開發後期,經過效能量測之後,再對其中效能吃緊的迴圈與函式,進行平行處理的最佳化改善。然而,OpenMP 比較不適合用來處理複雜的多緒同步工作,我們仍然需要其他技術的輔助。

關於「鎖」這個東西,有位著名的文學家曾說過:「鎖,或是不鎖,都是個問題!(誤)」在多執行緒的程式中,由於任何一段程式碼的執行過程,都可能隨時被另一個執行緒中斷,因此在多核心技術的處理程序中,資料的同步化可以說是最令人頭痛而且十分艱鉅的任務。一般在多緒程式中常見的作法,是利用 Mutex 或是所謂的 Lock 機制,保護資料不會同時被多個執行緒進行讀寫動作:

void MyClass::SetValue(int iValue)
{
    m_kMutex.Lock(); // 鎖定!
    m_iValue = iValue; // 安~心~操~作~~~
    m_kMutex.Unlock(); // 解鎖!
}

上述方法的缺點在於 Lock() 函式與 Unlock() 函式必須成對的使用,萬一發生忘記解鎖或是誤加兩次鎖的情形,就會造成資料鎖死而無法進行讀取與寫入的動作。因此,後來又發明了一種比較安全的鎖:

void MyClass::SetValue(int iValue)
{
    Lock kLock(m_kMutex);
    m_iValue = iValue;
}

上例中的鎖,是一個在函式本體中宣告的物件變數,只會在它生存的 Scope 中發生作用。當 Lock 物件生成時,在建構式中會自動喚起鎖定的動作,然後當程式離開 SetValue() 函式時,物件變數自動被毀滅,就會在解構式中喚起解鎖動作解除鎖定。利用上述的方法,在進行資料賦值前,先鎖定資料的讀取,使其他的執行緒不能然後在賦值完畢後,再將鎖定解除。而能夠保持資料的同步。

但是使用這種「鎖定 - 操作 - 解鎖」的三步驟方法,會造成程式執行效能低落,以及容易造成資料鎖死狀況的發生,進而產生各種惱人難纏的程式臭蟲。所以在多緒的程式系統中,仍然要盡量減少 Lock 機制的使用,才不會對效能造成太多的負面影響。為了改善鎖定機制的不足之處,有人想出了更好更快速的 Lock-Free 資料結構與演算法,既無須開鎖關鎖,又可提升執行效能,總算為苦命的程式設計者帶來一線曙光。

所謂的 Lock-Free 演算法,是利用電腦硬體提供的基原操作 (Atomic Operation) 所完成的一種資料處理程序:

// This function is atomic
template < class T >
bool CAS(T* addr, T exp, T val)
{
    if (*addr == exp) {
        *addr = val;
        return true;
    }
    return false;
}

範例中的 Compare and Swap (CAS) 函式,定義了一項基原操作:比較一個記憶體的值與一個已知的值,如果相等就將新的值存入記憶體中。x86 的硬體架構來說,能夠保證上述這項操作會一次處理完畢,不會被其他執行緒中斷,因此也就不需要仰賴鎖定與解鎖的機制以達成資料同步化的目標。

利用硬體所提供的 CAS 函式,以及其他的基原操作函式,就能夠免除 Lock 機制的問題,大幅提升多執行緒程式的執行效能。而所謂的 Lock-Free 資料結構,就是以 Lock-Free 演算法實作完成的一些基礎容器,例如 Linked List、Queue、Stack 與 Map 等等。然而,目前這些 Lock-Free Container 的實作方法相當複雜而不直覺,同時各種程式語言的支援與相關程式庫也在迅速發展中,未來應該能夠見到有如 STL 般的標準函式庫的誕生。

至此,已經介紹了多核心硬體發展的必要性、多核心技術的關鍵概念、OpenMP 基礎,以及神妙的 Lock-Free 演算法。如果以書籍中的資訊來看多緒技術在遊戲中的發展趨勢,在去年發行的《Game Programming Gems 6》,其中有一篇關於 Lock-Free 演算法,以及一篇 OpenMP 使用的文章,兩篇都是關於實作應用技術的內容。而在今年剛發行的《Game Programming Gems 7》中,則有一篇關於 Threading Engine 的設計與實作,以及一篇多緒工作系統的文章,已經進一步發展至高階的引擎系統架構。可以預見的是,未來將會有越來越多的網站資源、教學文章與論文期刊產生。

如同遊戲專案的開發流程,對於中央處理器來說,現在的年代已經不是單打獨鬥的英雄世紀了!取而代之的是,良好分工並且合作無間的團隊精神與合作模式。如果在遊戲的程式系統中,沒有善加利用多執行緒程式開發技術的威力,即使未來 CPU 硬體進步到 16 核或 32 核以上,依然是 1 個核跑得滿頭大汗,其他核在旁邊搧風納涼,完全發揮不了團結分工力量大的優勢。

想起不很久的從前,由 DOS 系統跨入 Windows 系統的年代裡,掛了一批跟不上腳步的人;之後由 2D 繪圖技術發展為 3D 繪圖技術時,又掛了另外一批人。未來會不會再發生如此巨大並且撼動人心的結構性變化?相較於其他領域的科學理論,電腦科學與計算機圖學正處於青春正甜的豆蔻年華,幾乎可以相當肯定地說:改變,是必然發生的未來。

以我自己的情況來說,不論是多核心的相關知識或多執行緒程式的開發經驗,都十分有限而貧乏至極,仍然需要投注更多的心力與時間學習,才能夠真的將這些技術與知識應用於未來的專案之中。

遊戲界,即將全面跨入「多核多緒多樂趣」的新時代。而你,準備好了嗎?

參考資料:

延伸閱讀:

  • Game Programming Gems 6: (1.1) Lock-Free Algorithms
  • Game Programming Gems 6: (1.2) Utilizing Multicore Processors with OpenMP
  • Game Programming Gems 7: (1.4) Design and Implementation of a Multi-Platform Threading Engine
  • Game Programming Gems 7: (1.9) Multithread Job and Dependency System

8 Replies to “多核多緒多樂趣”

  1. 又是一篇很好的簡介。我還未有機會看 Gems 7…

    除了以上介紹的方案,我覺得一個常用的多緒方式是 producer-consumer pattern。

    而有時候,使用 multi-thread 不是因為 single thread 效能不足,而是因為要等 I/O,例如 background loading 就算是單核也需要 multi-thread。最近玩Xbox360,發覺不少遊戲還是在過關卡時等很長的載入時間,一般歐美遊戲在這方面比日本遊戲好。

    另外,前文中的

    Lock kLock;

    我覺得應該改為

    Lock kLock(m_kMutex);
    // Lock::Lock(Mutex& mutex) : mMutex(mutex) { mutex->Lock(); }
    // Lock::~Lock() { mMutex->Unlock() }

    如果只是從 local variable (lock) 裡建立 mutex 就沒有意義了? 還是有其他背後的精妙之處?

    半路:
    Producer-Consumer Pattern 是指將 threads 當作 Consumer,由 Producer 產生任務分派給各個 threads 進行工作嗎?不知道和 threading pool 的概念有沒有相似性呢。

    現在遊戲的資料量越來越龐大,Background Loading 的重要性也越來越高。如果在傳統單核心 CPU 的情況下使用多緒,會對遊戲主程式迴圈造成效能影響,但是如果在多核系統中,就應該能夠比較適當地使用 Background Loading 才對;但是不止日本遊戲在這方面做得不夠好,台灣也幾乎沒看過使用這項技術的遊戲。

    沒錯,Lock kLock(m_kMutex) 才是正確的用法。 Orz
    文章內容已更正,感謝堪誤。

  2. 補充資料:Getting More From Multicore

    這是微軟在 GDC 2008 的其中一篇演講資料,下載檔案中有包含投影片檔以及錄音檔。這個 PPT 的內容真的非常不錯,值得一讀!除了投影片的內容外,也別忘記閱讀底下備忘稿的部分,有更詳細的解釋與說明文字。或者也可以一面閱讀,一面聽內附的錄音檔。

    其中提到了三種多緒的執行模型 (Execution Models):

    • Bulk Synchronous Processing (BSP)
    • Communication Sequential Processes (CSP)
    • Task Pool

    目前最熱門也是最複雜的技術,應該就屬 Task Pool 的執行模型了。
    等我學習完之後,再寫範例程式來試試~:D

  3. 題外話–
    增加核數目不一定會增加效能, 還要考慮程式的特性. 可以參考下篇:
    http://blog.csdn.net/drzhouweiming/archive/2007/04/10/1559718.aspx

    所以如果有許多執行緒有共用鎖的行為, 理論上最好能放在同一個核上執行.
    多核中的記憶體同步是個有趣的研究問題, 不管在硬體設計或是編譯器, 作業系統支援.

    半路:
    感謝提供有用的知識連結~ :D

    原來鎖的存在會造成核心數目提升效能的瓶頸,
    難怪要逐漸往 Lock-Free Algorithm 的方向前進了。
    我想,未來的硬體架構,應該也會提供更好的多緒程式支援性。
    目前的狀況下,還是盡可能減少鎖定的使用吧。

  4. 不會 OMP 也不用怕, 用 MCSTL 也可以.

    半路:
    噢!這個實在太酷了~~
    只要在程式中有使用到 sort, find, for_each 等 STL algorithm,
    就能夠不改一行程式碼的享受到多核運算的好處。真是夠神!
    如果有時間的話,應該要來試用看看。

    非常感謝您的分享~ :D

  5. 剛去那邊繞了一圈 好像所有文章都是抄來的
    要是我還不敢把自己相片和學校名字秀出來 哈哈

Leave a Reply