Threads:-例題ワークシート
Task Programming Model は、高度なマルチスレッド対応プログラミングモデルです。このワークシートを使用すると、従来のマルチスレッド型プログラミングの煩雑さを回避しながら複数のプロセッサの利点を活かした Maple コードを記述できます。
|
概要
|
|
以下のような単一スレッド型 Maple コードがあります。:
>
|
f := proc( fargs )
# Do some work
return cont( fc1( c1args ), fc2( c2args ) );
end proc;
|
| (1.1) |
ここで f を計算するには、最初に fc1 を実行してから fc2 を実行し、その後 cont を実行して引数としての fc1 と fc2 の値を返す方法があります。
Task Programming Model の場合、fc1 と fc2 および cont を一つずつ実行する代わりに、それぞれの関数に対応した task(タスク) を作成します。タスクとは小さな作業単位のことで、Maple では関数の呼び出しとして表されます。つまり、当該プロシージャを実行するためのプロシージャと引数です。このようなタスクは自動的にスケジュールが設定されて利用可能なスレッド上で実行されます。前述の cont は、fc1 と fc2 という戻り値と従属関係にあるため、cont は fc1 と fc2 が完了するまでは開始できません。また、タスクによっては、実行可能になるまで他のタスクの完了を待機する必要があります。実行タスクの戻り値は待機中のタスクに引数として渡されます。すべてのタスクの引数が利用可能になると、タスクを実行できるようになります。
タスクは新しいタスクを作成できます。自身が実行可能になるために別のタスクの完了を待機しているタスクがある状況下では、タスク同士の従属関係ツリーが作成されます。リーフ (葉) はいつでも実行できますが、内部ノードは引数が渡されてはじめて実行可能になります。
|
|
例題 1
|
|
次の例はこれらの従属関係を表したものです。
>
|
cont := proc( id, ret1, ret2 )
printf( "cont id %s\n", id );
return [ ret1, ret2 ];
end proc;
|
| (2.1) |
>
|
task := proc( id, level )
printf( "task id %s\n", id );
if ( level > 0 ) then
Threads:-Task:-Continue( cont, id,
Task=[task, sprintf( "%s->1", id ), level-1],
Task=[task, sprintf( "%s->2", id ), level-1] );
return "dummy";
else
return id;
end if;
end proc;
|
| (2.2) |
このコードにより、ID を出力してから自身の子タスクを作成するか、ID の出力後に単に自身の ID を返すといういずれかのタスクが作成されます。多重コアマシンで実行している場合は、出力は実行ごとに変化し、互いに組み合わされる場合もあります。
>
|
Threads:-Task:-Start( task, "root", 1 );
|
task id root
task id root->2
task id root->1
cont id root
| |
| (2.3) |
この簡潔な例では、最初にタスク root が実行され、次にルートの 2 つの子タスク、root->1 と root->2 が実行されます。その後、root に対して継続タスク cont が実行されます。次のように考えると継続ジョブの目的が理解できます。タスクとは、常に完了を目指して動作するものであり、いったん始動すると、他のタスクを待つことはありません。とはいえ、親タスクの完了前に子タスクが完了していない可能性があります。したがって、新しいタスクが作成されるときは、継続 タスクも作成されます。この継続タスクは、従属ツリーの現在実行中のタスクに置き換わります。これにより、継続ジョブ (上記の例 cont) からの戻り値がこれを作成したタスクの親 (root) に渡されます。この例では、子タスクの戻り値が含まれたリストが継続タスクの cont から返されます。この場合、cont の戻り値が root の親である Start に返されます。root の戻り値は破棄されます。
次に、やや大きいコードの実行例を示します。
>
|
Threads:-Task:-Start( task, "root", 3 );
|
task id root
task id root->2
task id root->2->2
task id root->2->2->2
task id root->2->2->1
cont id root->2->2
task id root->2->1
task id root->2->1->2
task id root->2->1->1
cont id root->2->1
cont id root->2
task id root->1
task id root->1->2
task id root->1->2->2
task id root->1->2->1
cont id root->1->2
task id root->1->1
task id root->1->1->2
task id root->1->1->1
cont id root->1->1
cont id root->1
cont id root
| |
| (2.4) |
この場合、実行されるタスク数が多くなるため、この例題を複数回実行するのは、複数の命令を出すようなものです。ただし、タスクの実行順序がどうであれ戻り値は常に同じです。
|
|
例題 2
|
|
次の例は、分割統治問題の解を求める場合の Task Programming Model の使用方法を示したものです。例では i の数を j に追加します。
>
|
cont := proc( a, b )
return a + b;
end proc;
|
| (3.1) |
>
|
task := proc( i, j )
local k;
if ( j - i < 1000 ) then
return add( k, k=i..j );
else
k := floor( (j-i)/2 ) + i;
Threads:-Task:-Continue( cont, Task=[ task, i, k ], Task=[task, k+1, j ] );
end if;
end proc;
|
| (3.2) |
>
|
Threads:-Task:-Start( task, 1, 10^8 );
|
| (3.3) |
Threads:-Task:-Start を呼び出すと、開始タスク task が作成され、このタスクの値またはその継続タスクが返されます。基本的な分割統治手法に従って task が開始します。ここでは、与えられた範囲の規模がチェックされ、この範囲が一定以下の場合、task は合計を直接計算します。範囲の大きさが一定以上の場合は半分に分割してからそれぞれに対して新たにタスクを作成します。計算が終了すると、結果の合計が継続ジョブの cont に返され、値が加算されて合計が返されます。Threads:-Task:-Continue 関数は子タスクと継続タスクを作成するために使用します。
|
|
Maple インターフェイス
|
|
Task Programming Model は、Start と Continue という 2 種類の関数で構成されています。
|
Threads:-Task:-Start
|
|
Start 関数は新しいタスクを作成し、その後、タスクの実行を開始します。Start で作成されたタスクが完了すると、Start はこのタスクによって返された値を返します。Start は Task の実行が終了してから呼び出すことができます。Start の使い方は次のとおりです。
Start( fcn, arg1, arg2, ..., argN )
これで次のように実行するタスクが作成されます。
fcn( arg1, arg2, ..., argN )
|
|
Threads:-Task:-Continue
|
|
Continue 関数は 2 種類の関数を実行します。最初に実行されるのは継続タスクを開始する関数で、次が子タスクを開始する関数です。継続タスクは、タスク従属ツリーにおける Continue の呼び出しに置き換わります。このようにして継続タスクの戻り値が現在のタスクの親に渡され、現在のタスクの戻り値は破棄されます。継続タスクは、継続の呼び出しで作成された任意の子タスクの親にもなります
Continue の使い方は次のとおりです。
Continue( fcn, arg1, arg2, ..., argN )
ここで fcn は継続関数であり、argi は継続関数に直接渡される引数または方程式です。
Task=[ cfcn, carg1, carg2, ..., cargN ]
この式の引数が Continue に渡されるとこのタスクは次のようにその子タスクを開始します。
cfcn( carg1, carg2, ..., cargN )
このタスクの戻り値は、これが作成された同じ場所で継続タスクに引数として渡されます。
|
|
|
動作方法
|
|
次に、Task Programming Model の動作方法を簡単に示します。
|
タスクとスレッド
|
|
Maple は、スレッドのプールを内部に作成しますが、ここで各種スレッドは kernelopts( numcpus ) という値と同等です。デフォルトではこれはコンピュータ上で利用可能なプロセッサの数を表します。このプールは Threads:-Task:-Start の初回の呼び出し時に作成されます。スレッドはいずれも 1 回に 1 つのタスクが実行可能です。作成されたタスクはその時点で従属関係ツリーを表したデータ構造体に格納されます。スレッドがタスクを終了すると、このデータ構造体から別のタスクを取り出します。
スレッドではなくタスクを記述することにより、Maple では作成された数々のスレッド同士でこれらのタスクを共有することができます。これによって 1 つのコードを複数のプロセッサに展開できるようになります。
|
|
タスクキュー
|
|
タスクの管理に使用するデータ構造体をタスクキュー(Task Queue)と言います。Task Queue には各スレッド用の両端キューが含まれています。キューにはタスクが格納されています。デフォルトでは、スレッドは常にキューの先端に位置するタスクを実行します。また、タスクが別のタスクを新規作成すると、現在のスレッドのキューに追加されます。スレッドによってキューが空であることが分かると、別のスレッドキューからタスクを移動させようとします。移動したタスクはキューの末尾に追加されます。
|
|
例題ワークシートのインデックスに戻る
|