2010年3月13日 星期六

multi-core、multi-thread 以及 Java 和 Python 的 thread 實現方式

過去一直搞不懂 multi-cpu 和 multi-core 的差別, 以及 process 和 thread 的差別。今天總算一次弄明白了。

何謂 multi-core? 為何要用 multi-core?

「multi-CPU, multi-core and hyper-thread」清楚地說明三者的差別:
  • hyper-threading: 在單一 CPU 內複製 architectural state 以減少 context switch 的時間。複製的量可以不只一份, OS 會當成多個 processor 用。比方說單 CPU 複製一份 architectural state, OS 就當作有兩個 logical processor。若 OS 的 scheduling 沒有考慮到 CPU 裝置是 hyper-threading, 有可能會拖慢速度, 畢竟實際能計算的裝置仍只有一份。目前 Intel 仍有在使用這個技術。
  • multi-CPU 顧名思意很容易理解。缺點是 CPU 之間溝通費時。若 CPU 1, 2 共用同塊記憶體位址, 在 CPU 1 讀完一串資料後, CPU 2 更改了其中一個位置的值, CPU 1 必須也更新 cache 內的值。可以想見要確保多個 CPU cache 和 RAM 同步的成本有多高。
  • multi-core 的好處是在一塊晶片上做進多個 CPU (multi-CPU 則是多個晶片)。於是可先配置好資料互通的線路, 減少同步資料的時間, 亦可能共用 cache。Wikipedia 上的示意圖滿清楚的。
「多核心處理器有前途嗎?」說明為何 multi-core 是目前的主流。主要的原因有三點:
  • 提高 CPU 頻率所提昇的速度和多消耗的電不成比例, 對多數人來說這不合成本。
  • 提高 CPU 頻率讓指令更難平行化 (我看不懂這點)。
  • RAM 跟不上 CPU 的發展, 於是得發展 CPU cache 和其它技術減輕這方面的影響, 使得技術變複雜。
這樣看來, 與其在同樣的大小的晶片內做一顆更強的 CPU, 還不如降低 CPU 頻率, 在同樣大小晶片內塞入更多核心。

對 OS 來說, 不管是 multi-CPU 還是 multi-core, 都會被當作有多個 CPU 可使用。Linux 下可看 /proc/cpuinfo 了解實際上擁有的 CPU 數量和核心數 [*1]。

回頭看 CPU 共享記憶體拖慢速度的議題。若 CPU 之間不需用到同塊記憶體, 也就沒有 CPU 同步資料的問題。什麼時候 CPU 之間會共用到同塊記憶體呢? 這很常發生嗎? 答案是當 process 之間用 shared memory 溝通, 或是使用 multi-thread 時。

thread 與 multi-core / multi-CPU

multi-thread 是很常見的使用情境, 好處是容易撰寫程式之間的溝通, 溝通速度快並能減少複製同樣的資料到不同記憶體。至於 multi-thread 好還是 multi-process 好, 則是另一個議題了。

不同的 VM 實作 thread 的方式不同。green thread 指 VM 自己管 thread, 而 native thread 表示該 VM 用的 thread 等同於 OS thread。native thread 才能享有 multi-core / multi-CPU 的好處, 讓工作平行化能加快執行速度。JVM 的 thread 因版本和作業系統而異, 在 Linux 下是 native thread。可透過 ps -eLF 得知 JVM 用的 thread 是那一種。

下面是我在 四核心 CPU、Ubuntu 8.04 下的使用例子:
$ java -version
java version "1.6.0_07"
Java(TM) SE Runtime Environment (build 1.6.0_07-b06)
Java HotSpot(TM) 64-Bit Server VM (build 10.0-b23, mixed mode)
$ ps -eLF
UID        PID  PPID   LWP  C NLWP    SZ   RSS PSR STIME TTY          TIME CMD
...
fcamel    1145  7850  1145  0   19 353540 246044 2 Mar04 pts/8    00:00:00 java -jar selenium-server.jar
fcamel    1145  7850  1146  0   19 353540 246044 2 Mar04 pts/8    00:00:00 java -jar selenium-server.jar
fcamel    1145  7850  1147  0   19 353540 246044 2 Mar04 pts/8    00:00:00 java -jar selenium-server.jar
fcamel    1145  7850  1148  0   19 353540 246044 3 Mar04 pts/8    00:00:00 java -jar selenium-server.jar
fcamel    1145  7850  1149  0   19 353540 246044 0 Mar04 pts/8    00:00:00 java -jar selenium-server.jar
fcamel    1145  7850  1150  0   19 353540 246044 1 Mar04 pts/8    00:00:00 java -jar selenium-server.jar
...

從上表可看出 selenium-server 有一個 process ID (PID) 和多個不同的 thread ID (LWP: light-weight process), 且被分散在不同的核心上執行 (PSR: 目前該 process 被配置到那個 processor )。

雖然前文提到 native thread 可以直接被 OS 排程, 因此能用 multi-thread 平行化加速。不幸的是, CPython 使用 native thread 卻無法透過 multi-core 加速, 反而會變慢。詳細的原因請見 Dabeaz Beazley說明。目前若想平行化 CPython 的程式, 只能用 multi-process (如透過模組 multiprocess), 但這種作法多了不少搬記憶體的額外時間。

備註

  1. processor 的數量表示 Linux 可用的 CPU 量; physical id 的量表示實體 CPU 數量; 同樣的 physical id 下, 不同 processor 會有不同 core id, 其中 cpu cores 表示該 CPU 的核心數。

2010-03-14 更新

  • 參考 sby 等人的說明後, 發覺說錯 hyper threading 的部份, 更正內文。另修正其它段落一些措詞。

6 則留言:

  1. 提高 CPU 頻率讓指令更難平行化 (我看不懂這點)。 <- 我猜是教科書講的,要提高 freq 的最直接方法是 deep pipeline ,但是相對而言 instruction dependency 會更嚴重,所以更難平行化。不過我不知道原來是不是要講這個 XD。

    與其實說提高 freq 會讓 CPU 耗更多電,不如說,提高 freq 並不見得會讓功率效能比變的更漂亮 XD。

    cache 近十年來都是很嚴重的問題啊 ... 但是我也不知道要講什麼 XD

    發完言有一種我是跑來亂的感覺 XD。

    回覆刪除
  2. Intel最新的CPU產品線都還有Hyper-Threading! :)

    回覆刪除
  3. 更新 hyper threading 的部份啦, 感謝。

    @yen3: 經你這麼一說, 我才想起 deep pipeline 的觀念, 多了解一點了。回頭看原文的說法, 似乎不只是更難平行化, 也提到頻率變高後平行化的幫助不明顯。還無法參透原文說明的前因後果。

    回覆刪除
  4. 1. System programmers looking for more depth should read: "What every programmer should know about computer memory" by Ulrich Drepper (maintainer of glibc, author of much of the modern Linux libpthread):
    http://lwn.net/Articles/250967/

    2. To obtain shared memory pages between multiple OS processes one could use shmget, mmap etc.

    3. "Parallelizing" an exiting code base to run efficiently on SMP is non trivial in both design and implementation. Can you implement a correct multi producer multi consumer queue like Python's Queue module using pthreads or Java? How long would it take you.

    回覆刪除
  5. Wow, I'll read "What every programmer should know about computer memory" latter. Thanks.

    I have no idea about the the 3rd question. Maybe I'll take some time to think the problem and read the source codes of Python's queue module. Good suggestion.

    回覆刪除
  6. 我想第二點是說目前從ILP(指令平行度)找平行越來越難找,而不如從TLP(Thead level)下去找平行吧,既然如此就勢必要發展出多核來找TLP平行吧。

    回覆刪除

在 Fedora 下裝 id-utils

Fedora 似乎因為執行檔撞名,而沒有提供 id-utils 的套件 ,但這是使用 gj 的必要套件,只好自己編。從官網抓好 tarball ,解開來編譯 (./configure && make)就是了。 但編譯後會遇到錯誤: ./stdio.h:10...