Misreading Chatエピソード86にインスパイアされた雛形が、おなじくHOPL4の論文からFortranにおけるcoarrayの歴史をひもときます。原論文が結構長かったため、紐解くのは前半部のみ、第6章まで。
- John Reid, Bill Long, and Jon Steidel. 2020. History of coarrays and SPMD parallelism in Fortran. Proc. ACM Program. Lang. 4, HOPL, Article 72 (June 2020), 30 pages. DOI: https://doi.org/10.1145/3386322 (This work is licensed under a Creative Commons Attribution 4.0 International License. Creative Commons — Attribution 4.0 International — CC BY 4.0)
免責事項
- 内容の正確性には可能な限り留意しておりますが、必ずしも正確性を保証するものではありません。記載内容に基づく一切の結果について、一切の責任を負いかねます。予めご了承ください。
Fortranの歴史
FORTRANは高水準言語のひとつ。長い歴史がある。同時代のプログラミング言語にたとえばCOBOLがある。業務用途のCOBOLとは異なり、FORTRANは科学技術計算 (High Performance Computing (HPC)) 向けに開発された。当時のHPCでは、計算性能を上げるのに各社が独自にカスタムしたハードウェアを作っていた。
文献*1によれば、FORTRANの黎明期においては前述のハードウェアのみならず、言語そのものに対してもベンダー独自の実装がなされていたようである。言語に対する標準化活動はUS National Standard（いわゆるANSI*2）として始まった（年代的に、この成果としてFORTRAN66が制定されたものと思われる）。標準化活動の組織は1988年にデッドロックに陥るも*3、のちに解消され、その後はISO Fortran Committee WG5という組織が言語規格を策定し、X3J3（のちのJ3）という組織がディテールの技術の部分を担当するようになる。（このあたりの両組織の力関係とか立場の事情は、論文だけではよくわからなかった）
このときのデッドロックが解消され・標準化がなされた結果として、年代的にFORTRAN90の規格が策定されたものと思われる。そこでは「配列機能が大幅に強化され*4」た（ただし、配列自体は最初期のFORTRANから使えた）。ここで登場する、そして論文タイトルにもある"coarray" [Numrich 1997] とは、この配列 (array) が異なるプロセス間で共存 (co-) するという意味で、並列処理に対する配列の拡張である。論文第6章では、以下のように記述されている：
Numrich invented the term co-array or coarray for the distributed object consisting of the collection of corresponding arrays (or scalars) on all the processors
計算の並列処理、つまり並列計算は1980年代から行われるようになった。1983年時点で、当時のユーザーからは並列計算を言語規格の改定に含めるようJ3に嘆願が出された。しかしJ3側としては、並列計算の未来はまだ不確実であり時期尚早ということで乗り気ではなく、並列計算は当時の改定には加えられなかった（残念）。
並列化について
共有メモリ型システム
前述の通り並列計算自体は1980年代から行われていた。初期の並列化は共有メモリ型システムでの並列化であって、複数のプロセッサーがひとつの（大容量の）メモリ*5にアクセスする。この共有メモリ型システムでの並列化プログラミングを標準化しようとする試みがライス大学主催のPCF (Parallel Computing Forum) として起こり、1991年にFORTRAN77の拡張がなされた（このときの拡張は、PCF (Parallel Computing Forum) Fortranとして文献*6に少し記述が見られる）。しかしこれは理論的また学術的であって、あまり流行らなかった。ベンダーとしては独自実装を発展させることで性能を上げ続けたこと、またPCFがフォーマルな標準化団体ではなかったので、独占禁止法（的なもの）に抵触することを懸念したから、らしい。
PCFの解散後に、ANSI X3H5という委員会が再び共有メモリ型システムでの並列化モデルを標準化しようとするも、うまくいかなかった。
1990年代半ばになって、各ベンダーでの共有メモリ型システムにおけるプログラミングの知見がたまってきたタイミングで、Lawrence Livermore National Laboratory (LLNL) は会議を開き、ベンダーとユーザーに共通の並列化モデルを取り入れるよう請願した。このときは前述の独占禁止法（的なもの）の問題も解決する方向にすすんだ。さきの2回の失敗とは異なり、このときの結果はOpenMPという共通の並列化プロトコルとして結実した。OpenMPは広く普及し、現在に至るまでアップデートが続けられている（執筆時点での最新版は2020/11/13にリリースされたversion 5.1）。
分散メモリ型システム
もうひとつの並列化の方法として、分散メモリ型システムでの並列化がある。これは複数のプロセッサーがメモリにある情報をお互いに交換しながらプログラムを実行していく。データの受け渡しにおいて長時間の待ちが発生しないよう、注意深く同期する必要があった。
Sunderam [1990] が記述したPVM (Parallel Virtual Machine) はこの同期の問題を対処し、バージョン3まで開発されたものの、のちにMessage Passing Interface (MPI) *7に取って代わられた（MPIのほうが性能が良かった）。MPIはOpenMP同様に普及し、執筆時点での最新版はversion 3.1であるが、4.0のdraftがすでに発行されているらしい*8。
ちなみにFortranにおける分散メモリ型システムにおけるもうひとつの並列化としてHigh Performance Fortran (HPF) というものが存在した。Wikipediaにある情報*9が詳しいのでそちらを参照してほしい。仕様が大変すぎて流行らなかったものの、日本では地球シミュレータで活躍したようだ。
並列化の発展
システムが発展していくにつれて、強いプロセッサーを少数で並列化することによる性能向上には限界があることがわかってきた。それに代わって、そこそこ強いプロセッサーを大量に並列化する (massively parallel processors (MPP)) ことで性能向上が図られるようになった。この論文の著者は元Crayの人で、当時のCrayの状況が記述されている：
In the mid-1990s Cray Research, then the dominant maker of powerful shared-memory vector systems, became convinced that MPP was the inevitable future and began investigating the field. （強調筆者）
このMPPの潮流は、たとえば理化学研究所の「富岳*10」しかり、現在に至るまで続いている。
ここでcoarrayを考案した前述のNumrichは、MPIのやり方は手間だし誤りやすい、ということで、MPIに代わってGET/PUTでデータを交換するやり方を考えた。MPIであれば
if (p==p1) then
call MPI_send (array1,size(array1),MPI_real,p2,tag,comm,ierr)
else if (p==p2) then
call MPI_recv (array2,size(array1),MPI_real,p1,tag,comm,status,ierr)
end if
と記述するところを、GET/PUTでは
if (p==p1) then
call put(array1,array2,size(array1),p2)
else if (p==p2) then
call get(array1,array2,size(array1),p1)
endif
と簡潔に書ける。こちらのほうが見た目的にもたやすい。最終的には、これを配列の添字になおして
if (p==p1) then
array2(:)[p2] = array1(:)
else if (p==p2) then
array2(:) = array1(:)[p1]
endif
みたく書けるようにした。もっとたやすくなった。Numrichはこの仕様を含めたFortranをF--と読んだ。いわく、C++は元のCに対して大きく変わっているが、F--は元のFortranに対してシンプルな変更しか加えていないから、と。
そして説明の順番が前後するけれども、上のようなシンプルな書き方ができるのは、各プロセッサーが対称なメモリ構造 (symmetric memory) を取っているからである。Numrichはこれをcoarrayと呼び、coarrayをベースに並列化の仕様を作った。MPIとの性能比較では、coarrayのほうがスケーリングが多少良かったようだ。
まとめ
ということで、Fortranでの初期のプログラミングからcoarrayに至るまでの歴史を追いかけた。Fortran2008もしくは2018における具体的なcoarray実装については、原論文の第7章以降を参考にしてほしい。
すでにMPIが存在するなかでNumrichがcoarrayを提案したのは、そのほうがよりシンプルに記述出来るから、ということだった。これはつまるところ、並列化の作法をプログラミング言語の外に持つか、それとも内に持つかの違いである。外に持てば言語自体は単純にできる一方で、並列化プロトコルの部分は複雑になる。逆に、並列化仕様を内部的に持つことで記述はシンプルに出来るものの、そのぶん言語としての複雑性は増してくる。ともに良し悪しがあるなかでどちらを選択するか、もっと抽象化すれば、ある技術（機能）を内製にするか、それとも外注するかという話にも繋がってきそうで、そう考えると何となく身近な話題にも思えてくる。
そして仕様策定、あるいは標準化活動というのは一筋縄ではいかないというのが、今回の並列化の歴史を読んでいてもよくわかる。共有メモリ並列化の標準化規格であるOpenMPが策定されるまでには、少なくとも2度の失敗があったし、分散メモリ並列化においても（この記事では触れていないが）その過程で種々の仕様・規格が出ては消えていった。標準化委員会というものがなかなか前に進まない、ということもよく可視化されている。各勢力が立場や感情を超えて一つの合意に至るのはなかなか難しい。
HOPLの論文は軒並み長めなので、全ページにわたって読むのはちょっときついけれど、歴史を学ぶこと自体は面白かったし、新しい発見や教訓も得られた。今後、読める範囲でもう何本か紹介できたらと思う。■
*1:Fortranが拓く世界、VSCodeが架ける橋 (slideshare.net) p. 5
*2:American National Standards Institute - ANSI Home
*3:議決に2/3以上の賛成が必要なところ、意見が半々に割れたそう
*4:計算機基礎B - 05. 配列 (1) (kyoto-su.ac.jp)
*5:表現として "メモリ空間" がより適切？
*6:Linux Parallel Processing HOWTO: 一般的な興味として (osdn.jp)
*7:たいへんに余談だが、Misreading Chatの森田さん、向井さんがMessage Passingというブログをちょうど開設されていて、命名はこのMPI由来かなと思われる
*8:SC 20 MPI Forum BoF Recorded Section - YouTube
