ExMultiCore - デカルト言語 - 並列ロジック プログラミング言語 Wiki - デカルト言語 - 並列ロジック プログラミング言語

←　先頭のページに戻る

デカルト言語の並列コンピューティング : マルチコア対応機能

(注：この機能は、リリース0.12.0以降のバージョンでないと動作しません。)

　デカルト言語では、マルチコア対応機能をサポートします。この機能により、マルチコアシステム上での効率の良い並列コンピューティングが可能です。マルチコアのシステム上でこの機能を使用すると、N個のコアがあれば、N倍以上の速度のプログラムを書くこともできてしまいます。

1. 並列プロセスモデル

デカルト言語の並列機能では、並列プロセスを同時に多数実行し、結果を並列プロセスを発行した元プロセスに返す処理を実行します。

この並列機能で生成される並列プロセスのモデルは、共有メモリを持たない、個々のプロセスが完全に独立したものです。

デカルト言語では、個々のプロセスが独立しているため、並列処理を実行中のプロセス間の排他処理を行う必要がありません。プロセスは効率よく並列に処理されていきます。

現状ではマルチコアのSMPシステムしかサポートしません。

しかし、このプロセスモデルだと、PCクラスタのようなクラスタシステムにも拡張するのは容易に思えます。将来の検討課題ですね。

2. マルチコア対応の並列機能の構成

さて、デカルト言語のマルチコア対応の並列機能は、以下の４つの述語で実装されます。

1) newproc : 並列プロセス数を指定して並列実行

2) eachproc : 引数のリストの要素に対応して並列実行

3) firstnewproc : 並列プロセス数を指定して、最初にtrueで終了した並列プロセスの結果を回収

4) firsteachproc : 引数のリストの要素に対応して、最初にtrueで終了した並列プロセスの結果を回収

上記の1), 2)の機能により、Nコアのシステムであれば、N個のプロセスを同時に並列に実行することができ、最大でN倍の実行性能を得ることが可能となります。

また、3), 4)の機能では、大規模な並列処理による探索でも、最も最初に探索を完了した解を回収できるため、Nコアのシステム上でN倍以上(数十倍以上)で実行することさえ可能となるのです。

使い方等詳細は以下に示します。

3. newproc

newproc述語は、並列プロセス数を指定して並列実行する機能です。指定された数のプロセスが並列に生成されます。 newprocで生成された全プロセスが終了すると、呼び出したnewproc述語に制御が戻り、全プロセスの結果を回収します。

newproc述語は以下のような構文です。

       <newproc (プロセス番号変数 プロセス数) 並列実行する述語 ...>
       <newproc (プロセス番号変数 プロセス番号初期値 プロセス番号終り値) 並列実行する述語 ...>

       <newproc 結果変数 (プロセス番号変数 プロセス数) 並列実行する述語 ...>
       <newproc 結果変数 (プロセス番号変数 プロセス番号初期値 プロセス番号終り値) 並列実行する述語 ...>

プロセス番号変数には、プロセスごとに異なるプロセス番号が設定されます。 プロセス番号は、「並列実行する述語」でプロセスごとの処理を切り分けるのに使えます。

結果変数が指定されている場合には、「並列実行する述語」の先頭の述語の第一引数を結果として返します。 返すことのできる値は、アトムのみです。それ以外のリスト等の値が返された場合には、返り値は()として設定されることになります。 ちょっと不便なのですが、マルチコアのプロセス間では、文字列以外のリストなどのデータ構造が共有できないので、現状はどうしようもありません。

各プロセスから返された結果は、結果変数にプロセス番号順にリストとして設定されます。

結果変数が指定されていない場合には、プロセスの処理結果を回収しません。 ただし、その場合でも全プロセスの終了をnewproc述語は待つことになります。

以下にフィボナッチ数を計算する例を示します。

<fib 0 0>;
<fib 1 1>;
<fib #result #n>
        <#n1=#n-1>
        <#n2=#n-2>
        <#result = <fib _ #n1>+<fib _ #n2>>;

?<newproc (#i 17) <fib #r #i> ::sys <writenl #i #r>>;
?<newproc #result (#i 17) <fib #r #i> ::sys <writenl #i #r>>;

フィボナッチ数を0から16まで、並列に実行します。最後の２行がnewproc述語の実行です。

最後から２行目は、結果の回収を行わない、結果変数を指定しない記述です。

最後の行は、結果の回収を行い、#resultに結果のリストが格納されます。

実行結果は以下です。

$ descartes newproc.car
0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144
13 233
14 377
15 610
16 987
result --
        <newproc (Undef6 17) <fib Undef7 Undef6> ::sys <writenl Undef6 Undef7>>
-- true
0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144
13 233
14 377
15 610
16 987
result --
        <newproc (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987) (Undef24987 17) <
fib Undef24988 Undef24987> ::sys <writenl Undef24987 Undef24988>>
-- true

２つ目の実行では、resultとして、結果のリストが格納されているのがわかるでしょうか？

なお、実行性能は、ほぼコア数に比例して向上していました。

4. eachproc

eachproc述語は、並列プロセス数を指定して並列実行する機能です。指定されたリストの要素のプロセスが並列に生成されます。 eachprocで生成された全プロセスが終了すると、呼び出したeachproc述語に制御が戻り、全プロセスの結果を回収します。

eachproc述語は以下のような構文です。

       <eachproc (要素変数 要素リスト) 並列実行する述語 ...>

       <eachproc 結果変数 (要素変数 要素リスト) 並列実行する述語 ...>

要素変数には、要素リストの中の要素ごとに異なる値が各プロセスに設定されます。 設定される要素は、「並列実行する述語」でプロセスごとの処理を切り分けるのに使えます。

結果変数が指定されている場合には、「並列実行する述語」の先頭の述語の第一引数を結果として返します。 各プロセスから返された結果は、結果変数にプロセス順にリストとして設定されます。

結果変数が指定されていない場合には、プロセスの処理結果を回収しません。 ただし、その場合でも全プロセスの終了をeachproc述語は待つことになります。

以下にフィボナッチ数を計算する例を示します。

<fib 0 0>;
<fib 1 1>;
<fib #result #n>
        <#n1=#n-1>
        <#n2=#n-2>
        <#result = <fib _ #n1>+<fib _ #n2>>;

?<eachproc (#i (7 8 12 14 11 10 6)) <fib #r #i> ::sys <writenl #i #r>>;
?<eachproc #result (#i (7 8 12 14 11 10 6)) <fib #r #i> ::sys <writenl #i #r>>;

フィボナッチ数を7, 8, 12, 14, 11, 10, 6のそれぞれに対して、並列に実行します。最後の２行がeachproc述語の実行です。

最後から２行目は、結果の回収を行わない、結果変数を指定しない記述です。

最後の行は、結果の回収を行い、#resultに結果のリストが格納されます。

実行結果は以下です。

$ descartes eachproc.car
7 13
8 21
12 144
11 89
10 55
6 8
14 377
result --
        <eachproc (Undef6 (7 8 12 14 11 10 6)) <fib Undef7 Undef6> ::sys <writenl Undef6 Undef7>>
-- true
7 13
8 21
11 89
12 144
10 55
6 8
14 377
result --
        <eachproc (13 21 144 377 89 55 8) (Undef9 (7 8 12 14 11 10 6)) <fib Undef10 Undef9> ::sys <writenl Undef9 Undef10>>
-- true

並列に実行されているため、実行順序が順不同になっていますね。

5. firstnewproc

firstnewproc述語は、並列プロセス数を指定して並列実行する機能です。指定された数のプロセスが並列に生成されます。 firstnewprocで生成されたプロセスのうち一つが終了すると、その結果を回収し、呼び出したfirstnewproc述語に制御が戻ります。 最初に終了した以外のプロセスの実行はすべて中断させます。

つまり、最も最初に結果が得られたプロセス以外は中断されて結果は捨てられ、最初に得られた結果だけが返されます。

firstnewproc述語は以下のような構文です。

       <firstnewproc (プロセス番号変数 プロセス数) 並列実行する述語 ...>
       <firstnewproc (プロセス番号変数 プロセス番号初期値 プロセス番号終り値) 並列実行する述語 ...>

       <firstnewproc 結果変数 (プロセス番号変数 プロセス数) 並列実行する述語 ...>
       <firstnewproc 結果変数 (プロセス番号変数 プロセス番号初期値 プロセス番号終り値) 並列実行する述語 ...>

プロセス番号変数には、プロセスごとに異なるプロセス番号が設定されます。 プロセス番号は、「並列実行する述語」でプロセスごとの処理を切り分けるのに使えます。

結果変数が指定されている場合には、「並列実行する述語」の先頭の述語の第一引数を結果として返します。 返すことのできる値は、アトムのみです。それ以外のリスト等の値が返された場合には、返り値は()として設定されることになります。

各プロセスから返された結果は、結果変数にプロセス番号順にアトムとして設定されます。 newproc述語とは異なり、リストではないことにご注意ください。

結果変数が指定されていない場合には、プロセスの処理結果を回収しません。

6. firsteachproc

firsteachproc述語は、並列プロセス数を指定して並列実行する機能です。指定されたリストの要素のプロセスが並列に生成されます。 firsteachprocで生成されたプロセスのうち一つが終了すると、その結果を回収し、呼び出したfirsteachproc述語に制御が戻ります。 最初に終了した以外のプロセスの実行はすべて中断させます。

つまり、最も最初に結果が得られたプロセス以外は中断されて結果は捨てられ、最初に得られた結果だけが返されます。

firsteachproc述語は以下のような構文です。

       <firsteachproc (要素変数 要素リスト) 並列実行する述語 ...>

       <firsteachproc 結果変数 (要素変数 要素リスト) 並列実行する述語 ...>

要素変数には、要素リストの中の要素ごとに異なる値が各プロセスに設定されます。 設定される要素は、「並列実行する述語」でプロセスごとの処理を切り分けるのに使えます。

結果変数が指定されている場合には、「並列実行する述語」の先頭の述語の第一引数を結果として返します。 返すことのできる値は、アトムのみです。それ以外のリスト等の値が返された場合には、返り値は()として設定されることになります。

各プロセスから返された結果は、結果変数にプロセス番号順にアトムとして設定されます。 eachproc述語とは異なり、リストではないことにご注意ください。

結果変数が指定されていない場合には、プロセスの処理結果を回収しません。

7. デカルト言語の並列処理プログラミングのコツ

便利なnop述語

nop述語は、引数に何が書かれていても何もしない述語です。 文法的にシンタックスエラーになるような場合を除き、引数に文字列、リスト、変数、述語など何が書かれていても、何もしません。

常に実行はtrueで成功します。

    <nop ～>

このような何もしない述語が、デカルト言語で並列処理をするのにとても便利なのです。

どのように使うかというと、上記までの項で説明したマルチコア機能の結果変数に値を返すために使うと便利なのです。

例えばnewproc述語で、並列に述語を実行し結果を集める場合、最初に実行された述語の第一引数の値が返されます。 しかし、都合よく最初の述語の第一引数に並列処理を行った結果を設定するのは実際には面倒なことが多いのです。

   <newproc #結果変数 (#i 1 10) <述語１ #変数1> <述語2 #変数2>>

上記では、#変数1の値が結果として、結果変数に設定されますが、実際には、述語1を実行し述語2を実行した後に#変数2の値を返したい場合には困ってしまいます。

このような場合には、nop述語を使えば簡単に解決できるでしょう。

   <newproc #結果変数 (#i 1 10) <nop #変数2> <述語１ #変数1> <述語2 #変数2>>

<nop #変数2>を最初の述語とすることで、#変数2の値が結果として帰ります。 nop述語は増やしても何も実行しないのでオーバーヘッドはありません。 #変数2には、述語1と述語2が実行された後の値が設定されます。

このように、nop述語を使うと並列プロセスの返り値を任意の値に自在に設定することができるようになります。

for, foreach述語との関係

for述語は、引数の述語を指定回数繰り返し実行します。 構文を見てみましょう。

<for (変数 実行回数) 述語...>
<for (変数 初期値 最終値) 述語...>
<for 結果変数 (変数 実行回数) 述語...>
<for 結果変数 (変数 初期値 最終値) 述語...>

newproc述語の構文とそっくりです。

<newproc (プロセス番号変数 プロセス数) 並列実行する述語 ...>
<newproc (プロセス番号変数 プロセス番号初期値 プロセス番号終り値) 述語 ...>
<newproc 結果変数 (プロセス番号変数 プロセス数) 並列実行する述語 ...>
<newproc 結果変数 (プロセス番号変数 プロセス番号初期値 プロセス番号終り値) 述語 ...>

実は、for述語とnewproc述語は、役割もよく似ています。

どちらも、引数の述語を繰り返し実行します。 異なるのは、for述語は、シングルコアで指定された順番に実行されることです。 newproc述語は、指定された述語はすべて実行されますが、順不同に並列に実行されます。 つまり、最も大きな違いは、並列にマルチコアで実行するかしないかが大きな違いであり、論理的には同じ処理を実行するのです。

実行する順番が重要な場合や、マルチコア実行ではオーバーヘッドが大きくなりすぎる場合には、for述語を用います。

多数のマルチコアを持つシステムでパフォーマンスを求める処理には、newproc述語を用いたほうがよいです。 しかし、newproc述語では、プロセスを生成しなければならないため、そのオーバーヘッドがあり、あまりに簡単な処理を引数の述語の処理とすると効率が悪いことがあるでしょう。

どちらを使うのが良いかは、プログラマが十分に条件や環境を熟慮して決めるべきでしょう。

foreach述語とeachproc述語も同様の関係です。

構文を見てみましょう。

<eachproc (要素変数 要素リスト) 述語 ...>
<eachproc 結果変数 (要素変数 要素リスト) 述語 ...>

<foreach (変数 リスト) 述語...>
<foreach 結果変数 (変数 リスト) 述語...>

対応していることが分かると思います。 foreach述語はシリアルに順に実行され、eachproc述語は並列に順不同に実行されることが違いです。

同様に、firstnewproc述語にはfirstfor述語が対応し、firsteachproc述語にはfirstforeach述語が対応します。

<firstnewproc (プロセス番号変数 プロセス数) 並列実行する述語 ...>
<firstnewproc (プロセス番号変数 プロセス番号初期値 プロセス番号終り値) 述語 ...>
<firstnewproc 結果変数 (プロセス番号変数 プロセス数) 並列実行する述語 ...>
<firstnewproc 結果変数 (プロセス番号変数 プロセス番号初期値 プロセス番号終り値) 述語 ...>

<firstfor (変数 実行回数) 述語...>
<firstfor (変数 初期値 最終値) 述語...>
<firstfor 結果変数 (変数 実行回数) 述語...>
<firstfor 結果変数 (変数 初期値 最終値) 述語...>

<firsteachproc (要素変数 要素リスト) 並列実行する述語 ...>
<firsteachproc 結果変数 (要素変数 要素リスト) 並列実行する述語 ...>

<firstforeach (変数 リスト) 述語...>
<firstforeach 結果変数 (変数 リスト) 述語...>

同時に実行するプロセス数

同時に実行されるプロセス数とコア数の関係について簡単に示します。

あまり厳密なものではなく、およその傾向についての説明でご勘弁ください。

以下は、デュアルCPU(2コア)のシステムで実行した、for述語とnewproc述語での実行結果です。 for述語の結果をsingle, newproc述語での実行結果をparallelと表示しています。

プロセスはコア数を超えて作成することができます。あまり、プロセス数を多くするとプロセス生成やプロセススイッチのためのオーバーヘッドが大きくなって、システムのCPU時間が100%喰われてしまい、高負荷状態でシステムハングしたような状態に陥るのでご注意ください。

ここでは、8プロセスの実行を比較しています。

1プロセスの場合と2プロセスの場合に、parallelの実行時間がほぼ同等になっています。 コア数以内のプロセスの実行は、最も効果的です。

また、3プロセス以上では、プロセス数の増加とともに徐々に実行時間も増えていきますが、singleほどの上昇率ではなく、常にparallelの実行時間のほうが、半分近くになっています。 つまり、コア数以上のプロセス数に対しても、並列実行は効果があることを示しています。

次に示すのは、16コアのシステムを使える機会があったので試してみた結果です。

さすがにこれほどのコア数を持つ高性能なシステムなので、調子に乗って64プロセスまで作成してみました。それでも、システムが高負荷状態でレスポンスが悪化したりしないのはさすがです。

やはり、並列実行の効果は劇的です。 プロセス数が増えてくると、圧倒的な性能差が得られます。

CPUのクロック数は今後近い将来に10倍以上になることは、期待できないのですが、それに匹敵する性能が、プログラムの機構にはよりますがマルチコアによって現在でも得られるのです。

以下は、上記の実行結果のうち、parallelの部分を拡大したものです。

やはり、16コアのシステムなので、16プロセスまではほぼ一定時間で完了しています。 17プロセス以上では実行時間が増加し、また、実行時間もばらついてくるようです。 しかし、増加率はプロセス数の増加に比べて急激ではありません。

これらの結果を見ると、個人の自家用PCでも、16コア以上のシステムが使えるような時代が到来するのが楽しみになりました。