X は 2D の点のセットで、凸包は X のすべての点を含む多角形を定義する最小の点セットであるとします。これらの点がボード上に留められたくぎであると考えた場合、くぎを紐で作った輪で囲み、たるみがなくなるまで紐を張ると、凸包ができます。この場合、凸包は紐に接しているくぎです。

以下は、20 点の凸包の例です。

凸包を計算する 1 つの方法として、QuickHull アルゴリズムを使用できます。凸包上の 2 点 (たとえば、x 軸上の最小位置と最大位置の点) を結ぶ線を引いて、残りの点を 2 つのグループに分けます。2 つのグループの凸包が求められれば、それらを結合して全体の凸包を形成することができます。線の片側にある点のなかから、線から最も遠い位置にある点を求めます。この点は凸包上にも存在します。この点と線の 2 つの端点を使用して、さらに 2 本の線を定義します。これらの線は再帰的に処理できます。これまでに作成した凸包の外側に点が 1 つだけまたは 1 つも存在しない線が見つかった場合、その線の両端と 1 つの外点 (存在する場合) が凸包内にあると言えます。

このアルゴリズムは、再帰的なステップを並列で実行することで、並列化できます。以下のコードを使用すると、タスクプログラミングモデルを使用して QuickHull アルゴリズムとパラレル QuickHull を実装できます。

逐次アルゴリズムを並列アルゴリズムに変換するのに必要な追加コードはわずかです。これは、タスクプログラミングモデルでは、スレッドプログラミングの紛らわしくて乱雑な、バグが発生しやすいさまざまな側面が考慮されているためです。

いくつかの点を作成して QuickHull アルゴリズムを試してみましょう。

同じ点セットについて並列アルゴリズムを試してみます。

前述したように、QuickHull アルゴリズムに少しの修正を加えるだけで、かなりの高速化を実現できます。

Maple 16 では、メモリ管理システムが見直され、複数のスレッドが実行されているときのメモリ処理が改良されました。上記の例を大量の点を使用して実行すると、Maple 15 と Maple 16 の違いが明確になります。

問題のサイズが大きくなると、Maple 15 のメモリマネージャは問題の要求についていくことができなくなります。Maple 16 ではこの点が改善され、パフォーマンスが大幅に向上しました。以下のグラフは、上記のグラフを生成するのに使用されたメモリを示しています。

Maple 16 では、Threads:-Add、Threads:-Mul、Threads:-Seq、および Threads:-Map の各ルーチンが改良されました。これらのルーチンは、対応する最上位の Maple ルーチンの並列実装です。Maple では、各要素の実行コストを予測することはできません。そのため、マルチコア間で問題を分割する最適な方法を推測する必要があります。Maple 15 までは、非常に簡単なヒューリスティック手法が使用されていました。この手法は多くのケースで十分に機能していましたが、それ以外のケース (一般的なケースを含む) では不十分でした。Maple 16 では、高性能なヒューリスティック手法が使用され、より多くのケースで並列処理を有効に利用できます。また、ユーザーが問題の分割方法を指定できるようになりました。これにより、新しいヒューリスティック手法が最適に機能しないケースでも並列処理を活用できます。

要素数が少ない場合 (1000 未満)、Maple 15 のパフォーマンスはシングルスレッドと同じ程度です。   1000 ～ 2000 要素の場合、Maple 15 のパフォーマンスは多少良くなりますが、Maple 16 ほどではありません。2500 要素を超える問題の場合のみ、Maple 15 は Maple 16 と同等のパフォーマンスになります。

Maple 16 のヒューリスティック手法は Maple 15 より優れていますが、すべてのケースで最適というわけではありません。パフォーマンスが低下するケースとして、要素数が非常に少なく、各タスクの実行時間が長い場合が挙げられます。この場合、各要素をシングルタスクとして実行できるようにするアプローチが最も適しています。Maple 16 では、tasksize オプションを使用してユーザーがタスクのサイズを指定できます。以下は、このオプションの効果を示したものです。

したがって、実行時間が長くて数の少ないタスクの場合は、明示的に tasksize を指定することで、パフォーマンスを改善することができます。ただし、十分な数の要素が存在する場合、ヒューリスティック手法は非常によく機能します。

タスクプログラミングモデルは、Maple 開発者がライブラリやルーチンに並列処理を追加するために使用するものと同じプログラミング手法です。新しい Magma パッケージは、並列処理を使用して IsAssociative 関数を加速します。以下は、効果的な並列処理によって Maple をどの程度加速できるかを示したものです。