Ada 202x (11日目) - parallel
============================

.. post:: Dec 11, 2019
   :tags: ada, ada_2022

ランデブーはAdaの代名詞ではあるのですが、いつの間にかスレッドプールと自動並列化の時代になりまして。

経緯
----

.. role:: strike

gccにもlibgompだの付いてきまして、C言語やgfortranでもちょっとpragmaを書き足すだけで並列化できたりするわけですよ。
:strike:`Adaの自動並列化やOpenMPの実装は研究レベルでは存在していますが、少なくともGNATにはないです。`
gcc 9以降ではGNATでもOpenACC用のpragmaが使えます。
(OpenMP、GNU的には「\ `Offloading and Multi Processing`_\ 」らしいですがどういう経緯でしょう？libgompはOpenACC等も含むから？)

標準化された機能に限定しましても、C11以降は ``<threads.h>`` 、Fortran 2008以降はCoArrayも入りましたから明示的な並列化も標準の範囲でできるようになりました。

陽に ``task`` が書けるだけでは立場がなくなりそうなのです。

Ada 202xでの改善
----------------

予約語 ``parallel`` が追加されました。

以下 ``Total := Process (1) + Process (2) + Process (3) + Process (4)`` を求める例です。

まずは一番単純な使い方の ``parallel do`` 文。

.. code-block:: ada

 declare
    P : array (1 .. 4) of Float;
    Total : Float;
 begin
    parallel do
       P (1) := Process (1);
    and
       P (2) := Process (2);
    and
       P (3) := Process (3);
    and
       P (4) := Process (4);
    end do;
    Total := P'Reduce ("+", 0.0);

続いて ``parallel for`` 文。

.. code-block:: ada

 declare
    P : array (1 .. 4) of Float;
    Total : Float;
 begin
    parallel for I in 1 .. 4 loop
       P (I) := Process (I);
    end loop;
    Total := P'Reduce ("+", 0.0);

``parallel for`` 文では、並列化するスレッド(チャンク)の数をループ数とは別に指定することもできます。

.. code-block:: ada

 declare
    P : array (1 .. 2) of Float := (others => 0.0);
    Total : Float;
 begin
    parallel (Chunk in P'Range) for I in 1 .. 4 loop
       P (Chunk) := @ + Process (I);
    end loop;
    Total := P'Reduce ("+", 0.0);

ループの何回目の試行がどう割り振られるかはわかりませんが、同じスレッドならチャンクの番号も同じになりますので ``P (Chunk)`` の同期は不要です。

ユーザー定義コンテナを ``parallel for`` 文に対応させるため ``Parallel_Iterator`` が追加されています。
(またコンテナの実装が大変になりました……。)

ユーザー定義コンテナの ``Cursor`` は整数型に限りませんので計算で割り振りができませんし、いっそコンテナの構造に沿って分割してもらったほうが効率的だからでしょうか。

そして昨日も少し触れました ``'Parallel_Reduce`` です。

.. code-block:: ada

 begin
    -- Pに値を入れるところは省略
    Total := P'Parallel_Reduce ("+", 0.0);

.. container:: strike

 配列の要素と結果の型が異なる場合は並列化のため第3引数が必要です。
 この例の場合は両方 ``Float`` ですのでいらないです。

さてreduction式の対象は一度変数に入れる必要がないことを思い出しますと ``P`` 自体が不要な気がしてきます。
次のように書けそうですが、匿名の数列と ``'Parallel_Reduce`` の組み合わせは許されていません。

.. code-block:: ada

 declare
    Total : Float;
 begin
    Total := [for I in 1 .. 4 => Process (I)]'Parallel_Reduce ("+", 0.0);
      -- error

この組み合わせが許されていないのは逐次処理できず一旦コンテナを作らないといけないからではないでしょうか、と想像します。
aggregate式を ``Float_Array'(`` ``)`` で囲って型を付ければ恐らく文法上は通る形になると思いますが、それでも ``Process (I)`` の呼び出しを含むaggregate式自体は並列化されませんので意味はないです。

ですのでreduction式に限定してaggregate式も並列化できます。

.. code-block:: ada

 declare
    Total : Float;
 begin
    Total := [parallel for I in 1 .. 4 => Process (I)]'Reduce ("+", 0.0);

勿論スレッドの数も指定できます。

.. code-block:: ada

 begin
    Total := [parallel (Chunk in 1 .. 2)
              for I in 1 .. 4 => Process (I)]'Reduce ("+", 0.0);

Ada.Iterator_Interfaces.Parallel_Iterator
+++++++++++++++++++++++++++++++++++++++++

| http://www.ada-auth.org/standards/2xrm/html/RM-5-5-1.html#p4.1

Ada.Iterator_Interfaces.Parallel_Reversible_Iterator
++++++++++++++++++++++++++++++++++++++++++++++++++++

| http://www.ada-auth.org/standards/2xrm/html/RM-5-5-1.html#p4.8

関連AI
------

- `AI12-0119-1`_ **Parallel operations**
- `AI12-0251-1`_ **Explicit chunk definition for parallel loops**
- `AI12-0266-1`_ **Parallel Container Iterators**

所感
----

``task`` は宣言するだけでも行数必要ですから、すごくお手軽になりました。

reduction式に妙に力入ってるのほんと何なのでしょうね。

.. _`Offloading and Multi Processing`: https://gcc.gnu.org/onlinedocs/libgomp/#Introduction
.. _`AI12-0119-1`: http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai12s/ai12-0119-1.txt
.. _`AI12-0251-1`: http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai12s/ai12-0251-1.txt
.. _`AI12-0266-1`: http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai12s/ai12-0266-1.txt