皆さんはプログラミング言語をいくつ知っているだろうか？

C言語, Python, R, java, MATLAB…

パッと思いつく有名どころはこれくらいか。

留学前までは僕はせいぜいこのくらいの言語についてしか詳しく知らなかった。

しかし、私の大学の先生や先輩曰く、

「一つのプログラミング言語さえ極められれば、他の言語もすぐにマスターできるようになる」

とのことだった。上記の言語のある程度の動かし方を習得した私は、すっかり自分がプログラミングの基礎をマスターしたような気になっていた。

しかし、デンマークに留学して、既存のプログラミング知識だけでは通じない言語がまだこの世に存在しているということを思い知った。

今回は、本留学で僕を最も苦しめたプログラミング言語であるFutharkについて紹介しようと思う。

Futharkとは

Futharkは、多次元のデータ並列性に特化した言語だ。

データ並列性とは簡単にいえば、異なるデータに対して同じ操作を同時に行うことである。

最も簡単な例はベクトルの足し算だ。次のようなNumPyのコードを考えよう。

import numpy as np

def inc_scalar(x):
   for i in range(len(x)):
      x[i] = x[i] + 1
   return x

def inc_par(x):
   return x + np.ones(x.shape)

この二つの関数は、両方とも、ベクトルの要素のそれぞれに対し、1を足すという操作を行なっている。

ここで重要なのが、1つ目の関数はforループを用いているため、要素の1つ1つに対して順番に操作を行っているという点だ。対して、2つ目の関数では、1を足すという操作が全ての要素に対して一気に行われている。

つまり、1つ目の関数は順次処理である一方、2つ目の関数は並列処理で計算を行っている。

並列計算は、データの数が膨大になればなるほど威力を発揮する。例えば、長さ10000のベクトルについてinc_scalar関数を実行しようとすると、forループを10000回繰り返さなければならず手間が掛かる。

そのため、大規模データを処理することを考えた時、いかにして計算を並列に行うかが鍵となってくるのだ。

NumPyの欠点

上に説明したとおり、NumPyでも一応並列計算っぽいものはできるにはできる。

ただ、NumPyには並列性に関して、重大な欠点がある。それは、NumPyのデータ並列性は一次元までしか対応していないということだ。

例えば、次のような操作を実行することを考える。

• ベクトルのそれぞれの要素に対して、もし奇数ならば1を引き、偶数ならば2で割る

これをNumPyで実行しようとしたら、次のようなコードを書くしかない。

def f(x):
  x = x.copy()
  for i in range(len(x)):
    if x[i] % 2 == 0:
      x[i] = x[i] / 2
    else: x[i] - 1
  return x

これはforループを用いた順次処理のコードである。そのため、NumPyではこのような操作を並列に実行することができないのだ。

尚、これをFutharkで記述しようとすると、以下のようになる。

def func [n] (x:[n]i32) :[n]i32 = 
  map(\i -> if i % 2 == 0 then i / 2 else i - 1) x

たったこれだけのコードで並列計算が可能だ

このように、FutharkではNumPyよりも複雑な操作を容易に並列実行できる。

これこそがFutharkの強みだ。

Futhark（並列計算）の厄介なところ

ここまでだと、Futharkはそこまで難しくないんじゃないかと思う人もいるかもしれない。

ただし、Futharkの真価を発揮するためには、この並列性を最大限に活用した構文を書かなければならない。

つまり、for loopのような順次処理は極力ないことが望ましい。

例えば、次のようなscan関数を並列に実行するにはどうしたらいいだろうか？

もし並列計算などを考えなくても良いのならば、以下のようなコードを書けば良い

def scan(x):
  for i in range(len(x)):
    if i != 0:
      x[i] += x[i-1]
  return x  

ただ、もしscan関数をfutharkで並列に実装しようとすると、話は一気に複雑になる。ループの回数を極力減らし、かつ計算量が大きくなりすぎないようなコードを考えなければならない。

なお、scan関数のfutharkでの実装の一例としては次のような実装が考えられる。

def ilog2 (x: i64) = 63 − i64.i32 (i64.clz x)

def workefficient [n] (xs: [n]i32): [n]i32 =
let m = ilog2 n
let upswept = loop xs = copy xs f o r d<m do
  map(\i −> if (i+1)%(2∗∗(d+1))==0 then xs[i] + xs[i−2∗∗d] else xs[i]) (iota n)
let upswept[n−1] = 0
let downswept = loop xs = upswept for d<m do
   map(\i −> if (i +1)%(2∗∗(m−d) )==0 then xs [i] + xs[i −2∗∗(m−d−1)] else
   if (i +1)%(2∗∗(m−d−1))==0 then xs[i+2∗∗(m−d−1)] else xs[i])) (iota n)
in downswept

詳細な説明は割愛するが、一気にコードが複雑になっているのが目に伺えるだろう。

更に厄介なところ

これがFutharkにおいて一番厄介なところだが、Futharkは不規則な入れ子構造を処理することができない。

つまり、

という配列のように、サイズや型の異なる要素に対しては並列な処理ができない。

なので、もしこのような入れ子構造を処理するには平坦化という工夫が必要になる。説明は省くが、平坦化は計算が複雑になればなるほど難しくなる。

余談だが、僕が授業中に、セミソートのアルゴリズムを平坦化している途中に起きたエラーを紹介したい。

セミソートは、異なるキーの間の順番を指定せずに、同じキーを連続して並び替えるソートアルゴリズムだ。

だから、次のような入力Ａに対して、出力はＢにもＣにもなり得る。

セミソートは単純なソートに比べると、アルゴリズムの複雑性は跳ね上がる。

僕はDong et al. (2023)を参考にセミソートアルゴリズムを実装したのだが、その途中でおかしなことが起こった。

https://dl.acm.org/doi/pdf/10.1145/3558481.3591071

なぜかこの部分のコードが、不規則なmapであると判断されているのだ。

let A_matrix = 
      map(\i -> let A' = Light_keys[offsets[i]:offsets[i+1]]
                let (rest, A'_sorted) =
                  loop A = (copy A', []) while (length ((\(x,y) -> x)A)) > a do
                        let (arr, sorted) = copy A
                        let (arr', offsets') = semisort_step hash arr
                        let new_arr = arr'[:(last offsets')]
                        let new_sorted = concat arr'[(last offsets'):] sorted
                        in (new_arr, new_sorted)
                let rest_sorted = Basecase hash rest
                let A'_sorted_new = concat A'_sorted (replicate (offsets[nL] - offsets[i+1]) dummy_ne) 
                                         |> concat rest_sorted
                                         |> concat (replicate offsets[i] dummy_ne)
               in map(\i -> A'_sorted_new[i])(iota nL)
      )(iota ((length offsets)-1))

僕の頭の中では、mapの最後に、大きさをnLと指定しているため、これは不規則な入れ子構造にはならないと考えていた。

恐らくだが、concat関数を多用しており、サイズの大きさが途中で変化するのがまずいのだろうか。

もしこの部分のエラーの詳細について詳しくわかる人がいたら教えてほしいです。

高岡の野望

Futhark は個人的にとても苦戦した言語でありつつも、勉強した後に振り返ってみればなんだかんだ楽しかったし、良い機会だった。

今後社会においてデータの数はますます増していくだろうし、ビッグデータを操るプログラミング手法として、この並列プログラミングを学んだ経験がどこかで生きる日が来るかも知れない。

だが、やはり学び初めの者に対して敷居の高い言語である感はやはり否めない。

現段階で僕が調べた限り、futharkの使い方を詳しく日本語で解説しているWebサイトは存在しない。

それならば、僕が先陣を切って作ってみようか、とも今考えている。

時間があるかはわからないし、需要もあるかはわからないけど、せっかく学んだ知識なのだ。

復習の意味も込めて、時間があればいつかやってみようと思う。