2014年5月19日

erlang - multicore

對 erlang 來說,不需要修改程式,就可以運作在多核新的 CPU 上,提昇執行速度。唯一的條件是,必須要以 spawn 多個行程的方式實作程式,不能用巨大的序列程式實作,序列化程式必須要改寫成行程的方式。

如何讓程式在多核心 CPU 上執行地更快

原則如下

  1. 使用多個行程
    要讓 CPU 保持忙碌,唯一的方式就是使用多個行程

  2. 避免副作用 side effect
    具有共享記憶體,兩個thread可同時寫入相同記憶體位置的共時系統,會利用上鎖的方式來保護寫入的區域,一般是由程式語言在內部以 mutex 或同步化的方式來實現 lock。
    erlang 不具有共享記憶體,不存在這個問題,共享資料可透過 ETS/DETS

    "public" ETS table 可被多個行程共享,只要知道 table 識別字的行程都可以讀寫此 table,這相當危險,所以 programmer 必須注意程式邏輯,加上使用的限制:
    2.1 同一時間只有一個行程會去寫入資料,其他行程只會讀取資料
    2.2 負責寫入 ETS table 的行程永遠要正確,不能寫入錯誤的資料

    "protected" ETS table 比較安全,只有一個行程可以寫入 table,其他行程可讀取資料。

    ETS/DETS 的目的是用來實現 Mnesia,如果要在行程之間共享記憶體,應用程式應該使用 Mnesia 的 transaction,盡可能不要獨立使用 ETS/DETS。

  3. 避免序列化瓶頸
    序列化瓶頸就是數個共時行程需要存取序列資源,最常見的序列化瓶頸是 disk IO,這是無法避免的。

    每一次產生了「註冊行程」,就會產生一個潛在的序列瓶頸,盡量避免使用「註冊行程」,如果使用「註冊行程」實作 server,必須確定它會很快地回應 request。

    解決序列瓶頸的唯一方法就是改變演算法,改成分散式演算法,這在網路程式或多核心程式常常會用到。

    分散式訂票系統:如果要賣票,通常會用單一售票處處理所有票務,但這會產生序列瓶頸,解決方式就是開設兩個售票處,第一個售票處分配偶數號,第二個售票處分配奇數號,如果售票處1賣完了,再把第二個售票處的票移到第一個賣。雖然解決問題,但兩張票的座位就會不在隔壁,這是 distributed hash table 的研究範圍。

  4. 小訊息,大運算

平行化序列程式碼

lists:map 的用途是可將 list 內所有元素都放入 F 估算一次。

map(_, []) -> [];
map(F, [H|T] -> [F(H)|map(F,T)].

改呼叫新版的 pmap 就可以馬上加速序列程式

pmap 是呼叫 (catch F(H)),而 map 是呼叫 F(H),因為 pmap 必須確保當估算 F(H) 產生例外時,pmap 能正常結束。

如果 F(H) 有使用到 process dictionary,則 pmap 跟 map 的行為就不一樣了,因為 pmap 是用另一個行程來估算 F(H),所以就無法用 pmap 平行化

pmap(F, L) -> 
    S = self(),
    %% make_ref() returns a unique reference
    %%   we'll match on this later
    Ref = erlang:make_ref(), 
    Pids = map(fun(I) -> 
                       spawn(fun() -> do_f(S, Ref, F, I) end)
               end, L),
    %% gather the results
    gather(Pids, Ref).

do_f(Parent, Ref, F, I) ->    
    Parent ! {self(), Ref, (catch F(I))}.

gather([Pid|T], Ref) ->
    receive
        {Pid, Ref, Ret} -> [Ret|gather(T, Ref)]
    end;
gather([], _) ->
    [].

使用 pmap 取代 map 之前,下面這些是必須考慮的重點

  1. 共時性的單位大小 granularity
    工作量很小的時候,不要使用 pmap,因為產生 process 消耗掉的成本比直接執行 map 還多。
    例如 map(fun (I) -> 2*I, L)

  2. 不要建立太多行程
    pmap(F, L) 建立了 length(L) 個平行行程,如果 L 很大,就會一下子建立了很多行程。

  3. 思考抽象邏輯
    pmap 重視回傳值的元素順序,如果不在意回傳值的順序,可以改寫為

     pmap1(F, L) -> 
         S = self(),
         Ref = erlang:make_ref(),
         foreach(fun(I) -> 
                         spawn(fun() -> do_f1(S, Ref, F, I) end)
                 end, L),
         %% gather the results
         gather1(length(L), Ref, []).
    
     do_f1(Parent, Ref, F, I) ->                        
         Parent ! {Ref, (catch F(I))}.
    
     gather1(0, _, L) -> L;
     gather1(N, Ref, L) ->
         receive
             {Ref, Ret} -> gather1(N-1, Ref, [Ret|L])
         end.

    另外的方式,可使用固定數量 K 個行程來實現 pmap,K 可對應到 multicore 的核心數量。

小訊息,大運算

L = [L1, L2, ..., L100],
map(fun lists:sort/1, L).
其中 L的每個元素都是 1000 個亂數整數 的 list

L = [27, 27, ... , 27],
map(fun ptests:fib/1, L).
其中 L是100個數字27,計算 fibonacci(27) 一百次

分別測量兩個函數花的時間,改成 pmap,再測量一次時間。第一個排序運算,使用 pmap 時,排序本身速度快,不同 process 之間傳送的資料比較多。第二個 fibonacci 有遞迴運算,要花比較多時間計算,但傳送的資料較少。

因為 fibonacci 的資料量少,工作量大,因此可以預測在多核心環境,第二個的效率改進會比第一個大。

SMP erlang

從 Erlang R11B-0 開始,在 Intel duo/quad CPU 預設就開啟了 SMP(symmetric multiprocessing),這是指具有兩個或多個一樣的CPU,連接到單一共享記憶體的運算環境,這些CPU可能是單或多晶片。

在其他平台要開啟SMP,必須要使用 --enable-smp-support 設定。

SMP erlang 有兩個設定值,用來決定如何運作
erl -smp +S N

  1. -smp
    啟動 SMP Erlang
  2. +S N
    以 N scheduler 執行 erlang,每一個 erlagn scheduler 都是一個完整的 VM,如果不用此參數,預設數量為 SMP 機器上的邏輯處理器數量。
-module(ptests).
-export([tests/1, fib/1]).
-import(lists, [map/2]).
-import(lib_misc, [pmap/2]).

tests([N]) ->
    Nsched = list_to_integer(atom_to_list(N)),
    run_tests(1, Nsched).

run_tests(N, Nsched) ->
    case test(N) of
        stop ->
            init:stop();
        Val ->
            io:format("~p.~n",[{Nsched, Val}]),
            run_tests(N+1, Nsched)
    end.

test(1) ->
    %% Make 100 lists 
    %%   Each list contains 1000 random integers
    seed(),
    S = lists:seq(1,100),
    L = map(fun(_) -> mkList(1000) end, S),
    {Time1, S1} = timer:tc(lists,    map,  [fun lists:sort/1, L]),
    {Time2, S2} = timer:tc(lib_misc, pmap, [fun lists:sort/1, L]),
    {sort, Time1, Time2, equal(S1, S2)};
test(2) ->
    %% L = [27,27,27,..] 100 times
    L = lists:duplicate(100, 27), 
    {Time1, S1} = timer:tc(lists,    map,  [fun ptests:fib/1, L]),
    {Time2, S2} = timer:tc(lib_misc, pmap, [fun ptests:fib/1, L]),
    {fib, Time1, Time2, equal(S1, S2)};
test(3) ->
    stop.

%% Equal is used to test that map and pmap compute the same thing
equal(S,S)   -> true;
equal(S1,S2) ->  {differ, S1, S2}.

%% recursive (inefficent) fibonacci
fib(0) -> 1;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).

%% Reset the random number generator. This is so we
%% get the same sequence of random numbers each time we run
%% the program

seed() -> random:seed(44,55,66).

%% Make a list of K random numbers
%%    Each random number in the range 1..1000000
mkList(K) -> mkList(K, []).

mkList(0, L) -> L;
mkList(N, L) -> mkList(N-1, [random:uniform(1000000)|L]).

測試結果,使用 pmap 在 smp 數量超過 2 之後,速度大約都會快兩倍。

> erl -boot start_clean -noshell -smp +S 1 -s ptests tests 1 >> results
> erl -boot start_clean -noshell -smp +S 2 -s ptests tests 2 >> results
> erl -boot start_clean -noshell -smp +S 3 -s ptests tests 3 >> results

{1,{sort,37334,45348,true}}.
{1,{fib,1615806,1625368,true}}.
{2,{sort,36983,24956,true}}.
{2,{fib,1641762,812359,true}}.
{3,{sort,36484,24912,true}}.
{3,{fib,1590642,902385,true}}.

參考

Erlang and OTP in Action
Programming Erlang: Software for a Concurrent World