CourseraのParallel, Concurrent, and Distributed Programming in Java Specializationを修了した

Rice UniversityのParallel, Concurrent, and Distributed Programming in Java Specializationを修了した。


  • Parallel Programming in Java
  • Concurrent Programming in Java
  • Distributed Programming in Java

前回言及したのは最初のコースである。残りの2つも無事修了したので、晴れて全課程完了となった。 備忘のために2つのコースでの学習内容を引用しておく。

Concurrent Programming in Java


  • 1週目

    In this module, we will learn about threads and locks, which have served as primitive building blocks for concurrent programming for over five decades. All computing platforms today include some form of support for threads and locks, and make them available for use by developers in a wide range of programming languages. We will learn how threads can be created, joined, and synchronized using structured (e.g., synchronized statements/methods) and unstructured (e.g., java.util.concurrent libraries) locks in Java. We will also learn about new classes of bugs that can arise when concurrent programs need to access shared resources. These bugs are referred to as violations of liveness/progress guarantees, and include deadlock, livelock, and starvation. We will conclude this module by studying different solutions to the classical "Dining Philosophers" problem, and use these solutions to illustrate instances of deadlock, livelock and starvation.

Deadlock, livelock, starvationという重要概念が紹介される。また形式検証や並列プログラミング界隈でよく目にする"Dining Philosophers"問題にもふれる。

  • 2週目

    In this module, we will learn different approaches to coordinating accesses to shared resources without encountering the deadlock or livelock bugs studied earlier. Critical/isolated sections are higher-level concurrent programming constructs (relative to locks) that simplify the implementation of mutual exclusion by guaranteeing the absence of deadlocks and livelocks. Object-based isolation relaxes the constraints imposed by critical sections by allowing mutual exclusion to be specified on a per-object basis, as illustrated in the Spanning Tree example. Java's atomic variables represent an important, but restricted, case of object-based isolation that is implemented efficiently on all hardware platforms. Finally, we will learn how object-based isolation can be further relaxed with read/write access modes.

Intersection Emptinessを毎回判定して、共通部分が空ならdeadlockを気にせず並列処理できます、という手法が紹介される。Intersection Emptinessは場合によっては計算量が爆発するので気を付ける必要がありそう。また、基本的なatomic操作はCPUに専用命令が用意されているので高速だと知る。

  • 3週目

    In this module, we will learn another high-level approach to concurrent programming called the "Actor" model. A major difference between the Actor model and the Isolated Sections model is that there are no data races possible in the Actor model because it does not allow for any form of shared variables. However, as in all concurrent programming models, higher-level forms of nondeterminism are still possible in the Actor model due to an inherent asynchrony in the order in which messages may be delivered. We will study multiple examples of concurrency using the Actor model, including the classical Sieve of Eratosthenes algorithm to generate prime numbers, as well as producer-consumer patterns with both unbounded and bounded buffers.

アクターモデルの紹介。Producer-Consumer patternはエンタープライズ分野で頻出。よくキューが詰まって問題になっている印象。

  • 4週目

    In this module, we will study Concurrent Data Structures, which form an essential software layer in all multithreaded programming systems. First, we will learn about Optimistic Concurrency, an important multithreaded pattern in which two threads can "optimistically" make progress on their assigned work without worrying about mutual conflicts, and only checking for conflicts before "committing" the results of their work. We will then study the widely-used Concurrent Queue data structure. Even though the APIs for using concurrent queues are very simple, their implementations using the Optimistic Concurrency model can be complex and error-prone. To that end, we will also learn the formal notion of Linearizability to better understand correctness requirements for concurrent data structures. We will then study Concurrent Hash Maps, another widely-used concurrent data structure. Finally, we discuss a concurrent algorithm for finding a Minimum Spanning Tree of an undirected graph, an algorithm that relies on the use of Concurrent Data Structures under the covers.

楽観ロックやConcurrent Hash Mapの紹介。いづれエンタープライズ分野で頻出。

Distributed Programming in Java


  • 1週目

    In this module, we will learn about the MapReduce paradigm, and how it can be used to write distributed programs that analyze data represented as key-value pairs. A MapReduce program is defined via user-specified map and reduce functions, and we will learn how to write such programs in the Apache Hadoop and Spark projects. The MapReduce paradigm can be used to express a wide range of parallel algorithms. One example that we will study is computation of the TermFrequency – Inverse Document Frequency (TF-IDF) statistic used in document mining; this algorithm uses a fixed (non-iterative) number of map and reduce operations. Another MapReduce example that we will study is parallelization of the PageRank algorithm. This algorithm is an example of iterative MapReduce computations, and is also the focus of the mini-project associated with this module.


  • 2週目

    In this module, we will learn about client-server programming, and how distributed Java applications can communicate with each other using sockets. Since communication via sockets occurs at the level of bytes, we will learn how to serialize objects into bytes in the sender process and to deserialize bytes into objects in the receiver process. Sockets and serialization provide the necessary background for the File Server mini-project associated with this module. We will also learn about Remote Method Invocation (RMI), which extends the notion of method invocation in a sequential program to a distributed programming setting. Likewise, we will learn about multicast sockets,which generalize the standard socket interface to enable a sender to send the same message to a specified set of receivers; this capability can be very useful for a number of applications, including news feeds,video conferencing, and multi-player games. Finally, we will learn about distributed publish-subscribe applications, and how they can be implemented using the Apache Kafka framework.

オブジェクトのシリアライズ/デシリアライズを利用して、いわゆる「クラサバ」アプリを作成する方法が解説される。エンタープライズ分野で非常によくみる構成だが、Javaシリアライズ/デシリアライズやRemote Method Invocation (RMI)は深刻な脆弱性の泉源となってきたので、実際に使用する場合は十分に注意しなければならない。以下の記事によると、Oracleはこれら「リスキー」な機能を根本的に見直そうとしているらしい。

  • 3週目

    In this module, we will learn how to write distributed applications in the Single Program Multiple Data (SPMD) model, specifically by using the Message Passing Interface (MPI) library. MPI processes can send and receive messages using primitives for point-to-point communication, which are different in structure and semantics from message-passing with sockets. We will also learn about the message ordering and deadlock properties of MPI programs. Non-blocking communications are an interesting extension of point-to-point communications, since they can be used to avoid delays due to blocking and to also avoid deadlock-related errors. Finally, we will study collective communication, which can involve multiple processes in a manner that is more powerful than multicast and publish-subscribe operations. The knowledge of MPI gained in this module will be put to practice in the mini-project associated with this module on implementing a distributed matrix multiplication program in MPI.

Single Program Multiple Data (SPMD)が紹介される。MPIに関わると地獄、みたいな言説をTwitterで見かけたがどうなんでしょう。

  • 4週目

    In this module, we will study the roles of processes and threads as basic building blocks of parallel, concurrent, and distributed Java programs. With this background, we will then learn how to implement multithreaded servers for increased responsiveness in distributed applications written using sockets, and apply this knowledge in the mini-project on implementing a parallel file server using both multithreading and sockets. An analogous approach can also be used to combine MPI and multithreading, so as to improve the performance of distributed MPI applications. Distributed actors serve as yet another example of combining distribution and multithreading. A notable property of the actor model is that the same high-level constructs can be used to communicate among actors running in the same process and among actors in different processes; the difference between the two cases depends on the application configuration, rather the application code. Finally, we will learn about the reactive programming model, and its suitability for implementing distributed service oriented architectures using asynchronous events.




Coursera Parallel Programming in Javaを受講した

社会人になるまでなんとなく Java を避けていたが、必要に迫られて学びはじめてみると、周辺ツールやライブラリ、学習資料が非常に充実していて驚いた。学生の頃はわからなかったが、いまなら Javaエンタープライズ分野で使われる理由がよくわかる。

4月に Coursera からコースの案内メールが来た。Rice University が提供する、Parallel, Concurrent, and Distributed Programming in Java Specialization というコースが紹介されていた。面白そうなので受講してみることにした。

今回修了したのは、その3つのクラスからなるコースの1つ目「Parallel Programming in Java」。4週間のクラスだったので、主に土日に1週分を学習し、4週ですべての課題を提出して修了条件を満たした。

コースの難易度は、同じ Coursera の有名クラス「Machine Learning」などと比べるとかなり簡単で、クラス毎に用意されたフォーラムの書き込みを見ると、2日程度ですべての教材と課題を消化した人もいるようだ。

クラス名に Java と入っているが、Java の並行処理ライブラリの使い方を懇切丁寧に解説するようなクラスではない。はじめに並列コンピューティングの概念を説明して、それを実現する Java の機能をさらっと紹介するという構成になっている。


  • 1週目

    We will learn about task creation, task termination, and the “computation graph” theoretical model for understanding various properties of task-parallel programs. These properties include work, span, ideal parallelism, parallel speedup, and Amdahl’s Law. We will also learn popular Java APIs for task parallelism, most notably the Fork/Join framework.

  • 2週目

    We will learn about futures, memoization, and streams, as well as data races, a notorious class of bugs that can be avoided with functional parallelism. We will also learn Java APIs for functional parallelism, including the Fork/Join framework and the Stream API’s.

  • 3週目

    We will start by learning how parallel counted-for loops can be conveniently expressed using forall and stream APIs in Java, and how these APIs can be used to parallelize a simple matrix multiplication program. We will also learn about the barrier construct for parallel loops, and illustrate its use with a simple iterative averaging program example. Finally, we will learn the importance of grouping/chunking parallel iterations to reduce overhead.

  • 4週目

    We will learn how Java’s Phaser API can be used to implement “fuzzy” barriers, and also “point-to-point” synchronizations as an optimization of regular barriers by revisiting the iterative averaging example. Finally, we will also learn how pipeline parallelism and data flow models can be expressed using Java APIs.


修了条件を満たすには、毎週 mini project と呼ばれるプログラミング課題をクリアする必要がある。これも難易度は高くなくて、とくに1週目の project 以外は、ほぼ完成しているソースコードが提供されるため、それを少し改変すればよい。これには少々拍子抜けしたが、数ヶ月前に同クラスが開講された際のフォーラムの書き込みを見ると、そのときはすべて一からコードを書く必要があったようだ。

Mini project がなぜ今のような「お手軽」な形になったのかは不明だが、想像はできる。実は、この mini project は授業内容との乖離や、意図がわかりずらい出題になっている等の「問題」が少々ある。それらに対する問い合わせが殺到した結果、最初からある程度完成されたものを提供するようになったのではないだろうか。

個人的には気軽に楽しく受講できたので満足している。次の Concurrent Programming in Java も楽しみだ。

Ubuntu で『ソフトウェアの基礎』を読む

この記事は Ubuntu 14.04 上に Proof General と Coq をインストールし、Emacs から『ソフトウェアの基礎』を読む(実行する)ためのメモです。日本語の解説記事が見つからなかったので書きました。なお、筆者は Coq や Proof General に関して素人なので、誤りなどがありましたらご指摘いただけると幸いです。

Proof General と Coq のインストール

Emacs はインストールしてあるものとします。Proof General と Coq は以下の apt コマンドでインストールできます。

sudo apt install proofgeneral coq

補足: apt-get install ではなく apt install となっているのは誤りではありません。Ubuntu 14.04 から「aptコマンド」が使えるようになりました。詳細はこの記事をご参照ください。(2014/09/03 追記)

注意: 2014年8月31日現在、apt でインストールした Proof General のバージョンは 4.3pre130510 です。開発版は 4.3pre131011 のようですが、この記事では無視します。一方、インストールした Coq は 8.4pl3 ですが、最新版は 8.4pl4 です。8.4pl3 には重大なバグがあり、8.4pl4修正されたそうですが、近日中に 8.5 がリリースされる予定 (pdf) ということもあり、この記事では面倒を避けて古いものをそのまま使います。最新版を使いたいという方は以下の記事などをご参照ください。


有志による日本語訳はこちらの「ソース」からダウンロードできますが、最終更新日が2011年6月とやや古いので、原文の方を以下のリンクからダウンロードします。なお、原文のバージョンは現時点で 3.1 (July 2014) です。


tar zxvf sf.tar.gz


それでは、動作確認のために解答したフォルダの中の Basics.vEmacs で開きます。


光栄にも将軍が我々を歓迎してくれました。閣下のご尊顔を拝していると、Basics.v のバッファに自動で切り替わります。自動で移動しない場合は手動でバッファを切り替えてください。なお、環境によっては Proof General のツールバーが表示されているはずです。


ふむふむと読んでいって Exercise 1 まで進めたとします。おんどりの導くままに正解と思うコードを入力し、そのコードの下あたりにカーソルを移動させたら、おもむろに C-c C-return を押します(つまり Ctrl を押したまま c を押し、次に Ctrl を押したまま Enter を押す)。


すると、カーソルより上の画面の背景の色が変わり、上図のように画面が3分割されます。一番下の画面 *response*nandb is defined と表示されていればとりあえずOKです。文法などに誤りがある場合は *response* にエラーメッセージが表示されますので、コードを修正しましょう。

次に、自分で定義した nandb が正しいか確かめましょう。Exercise 1 の下に Example(* FILL IN HERE *) Admitted. からはじまる文が並んでいます。本文に従って (* FILL IN HERE *) Admitted.Proof. reflexivity. Qed. に書き換えたら、それらの行の下付近にカーソルを移動させて、再度 C-c C-return を押します。

自分で定義した nandb が正しければ背景の色が変わり、*response* には何も表示されません(あるいは test_nandb4 is defined などと表示されます)。nandb に誤りがあれば、エラーが出力されます。例えば以下のような:

Toplevel input, characters 0-11:
Error: Impossible to unify "true" with "nandb false false".


どうやら Example test_nandb2 でエラーが起きたようです。このテストが通るように nandb を書き直したら、再度 C-c C-return を押して正しさを確認しましょう。


以上のように、『ソフトウェアの基礎』を読んで実行するときは、実行したい行にカーソルを移動させて C-c C-return を押せば大体やりたいことが実現できます。CheckEval のある行も C-c C-return でOKです。

Proof General には他にも便利な機能がありますので、公式ページのドキュメントなどをご参照ください。よく使うキーバインドこちらのページにまとまっています。

補足: Basics の中間付近からステップ実行が必須になります。ツールバーを利用してもよいですが、キーボードから操作できた方がなにかと便利ですので、1ステップ進む C-c C-n と1ステップ戻る C-c C-u をぜひ活用しましょう。また、Proof General の機能である Electric Terminator がオンになっていると、ピリオドを入力した際にその部分まで自動的に評価してくれます。機能のオン・オフは C-c . と押すことで切り替えられます。(2014/09/03 追記)

MATLAB の正規化周波数について

MATLAB の Signal Processing Toolbox を使っていると、このページの例のように横軸が「Normalized Frequency (正規化周波数)」になっているグラフが頻出する。しかし、MATLAB の正規化周波数は信号処理の教科書や技術書に書かれているものとやや異なる。そのため、使いはじめたばかりの学生(かつての自分含む)が混乱することがある。

実は、MATLAB の正規化周波数は「ナイキスト周波数」が基準となっている。以下、公式の FAQ から引用する。

This toolbox uses the convention that unit frequency is the Nyquist frequency, defined as half the sampling frequency. The cutoff frequency parameter for all basic filter design functions is normalized by the Nyquist frequency. For a system with a 1000 Hz sampling frequency, for example, 300 Hz is 300/500 = 0.6. To convert normalized frequency to angular frequency around the unit circle, multiply by π. To convert normalized frequency back to hertz, multiply by half the sample frequency. Frequency Response - MATLAB & Simulink

抄訳: Signal Processing Toolbox の単位周波数はナイキスト周波数であり、標本化周波数の半分です。(略) 標本化周波数が 1000 Hz ならば、300 Hz は(正規化周波数では)300/500=0.6 となります。正規化周波数を単位円上の角周波数に変換するには π を乗算し、ヘルツに変換するには標本化周波数の半分を乗算してください。

たいていの教科書では、正規化周波数は F = f / fs と書かれている。ここで f は周波数、fs は標本化周波数である。同様に正規化角周波数は Ω = ω / fs = 2πf / fs = 2πF と書かれている。この定義に基づいた教科書的な IIR フィルタの例を見てみよう。IIR フィルタの伝達関数

 \displaystyle H(z)=\frac{\sum^M_{m=0}a_mz^{-m}}{\sum^N_{n=0}b_nz^{-n}}

で与えられる。ここで  z=e^{j\Omega}=e^{j2\pi F} として、ある低域通過フィルタの振幅特性を計算すると以下のようになる。

f:id:hark00:20140808193608p:plain:w250 f:id:hark00:20140808193613p:plain:w250

図の横軸は教科書的な正規化周波数である。左図は横軸を 0.5 まで、右図は 1.0 までとした。正規化角周波数に変換する場合は 2π を乗算すればよいので、0.5 は π、1.0 は 2π に変換される。

さて、標本化定理によると、標本化前の信号(原信号)の最大周波数が f のとき、原信号を標本化後の信号から正しく復元するためには、標本化周波数を 2f より大きくしなければならない。言いかえると、標本化周波数が fs ならば fs / 2 以上の周波数を持つ原信号は正しく復元できない。この標本化周波数の半分 fs / 2 をナイキスト周波数と呼ぶ。

冒頭で引用したように、MATLAB の正規化周波数はナイキスト周波数を基準としている。つまり、fs / 2 が単位周波数となるように設計されている。そのため上図では 0.5 であった横軸の点が 1.0 となる。下図のように。


さきほどは正規化角周波数に変換するために 2π をかけたが、今回は π をかければよい。MATLAB の正規化周波数の単位が ×π rad/sample になっているのは、これが理由である。

なお、MATLAB に似た無料の数値計算ソフトである Scilab の正規化周波数は、自分の知るかぎり教科書通りである。そのため、使用に際して上記のような混乱はなかったと思う。




一般に無閉路有向グラフ (DAG) は隣接行列の形で表すことができますが、隣接行列の累乗の和を計算すると、すべての二頂点間の経路重みの総和を計算することができます。実はこの計算過程をちょっと変えて、半環の一種であるトロピカル半環を用いると、すべての頂点間の最短経路が求められるというお話です。


与えられた無閉路有向グラフ (以下、単にグラフ) のすべての二頂点間の経路重みの総和を計算しようと思ったとき、そのグラフの隣接行列の累乗の和を計算するという方法が使えます。ここで経路重みの総和とは、ある始点からある終点までの各経路について、同じ経路上の辺の重みを乗算し、それらの結果をすべて足し合わせたものとします。



頂点 1 から頂点 4 までの経路は 2 本あります。それぞれの経路の重みは 2 × 3 = 6 と 10 × 20 = 200 で、これらを足した 206 が頂点 1 から頂点 4 までの経路の重みの総和です。

では、経路重みの総和をグラフの隣接行列の累乗の和から求めてみます。上図のグラフの隣接行列 M は以下のようになります。

 M = \begin{pmatrix} 0 & 2 & 10 & 0 \\ 0 & 0 & 0 & 3 \\ 0 & 0 & 0 & 20 \\ 0 & 0 & 0 & 0 \end{pmatrix}


 M^{*} = \sum_{n\in\mathbb{N}} M^{n}

グラフの直径を r とすると、n > r の場合の M の n 乗は零行列になりますので、以下の計算では無視しています。上のグラフの直径は 2 なので、n = 2 まで計算すれば十分です。なお、閉路のあるグラフでは、n = k のとき長さ k 以下の経路の重みの総和が求められます。


これですべての二頂点間の経路重みの総和が計算できました。図にある通り、頂点 1 から頂点 4 への経路重みの総和は、1 行目の 4 列目を見ればよいので、206 であることがわかります。



  • 0 を  \infty で置換する
  • 行列の任意の2要素 x, y の乗算 xy の代わりに加算 x + y を計算する
  • 行列の任意の2要素 x, y の加算 x + y の代わりに min(x, y) を計算する


 A=\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix},\ B=\begin{pmatrix} 10 & 20 \\ 30 & 40 \end{pmatrix}


 A+B=\begin{pmatrix} 1+10 & 2+20 \\ 3+30 & 4+40 \end{pmatrix},
\ A\times B=\begin{pmatrix} 1\cdot 10 + 2\cdot 30 & 1\cdot 20 + 2\cdot 40 \\ 3\cdot 10 + 4\cdot 30 & 3\cdot 20 + 4\cdot 40 \end{pmatrix}


 A+B=\begin{pmatrix} 11 & 22 \\ 33 & 44 \end{pmatrix},\ A\times B=\begin{pmatrix} 70 & 100 \\ 150 & 220 \end{pmatrix}


 A+B=\begin{pmatrix} \min(1,10) & \min(2,20) \\ \min(3,30) & \min(4,40) \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}


 A\times B=\begin{pmatrix} \min(1+10,2+30) & \min(1+20,2+40) \\ \min(3+10,4+30) & \min(3+20,4+40) \end{pmatrix} = \begin{pmatrix} 11 & 21 \\ 13 & 23 \end{pmatrix}

となります。では、このようなルールで  M^* を計算してみましょう。


計算結果を見ると、行列の各要素が二頂点間の最短距離になっていることがわかります。1 行目の 4 列目は 5 ですが、これは頂点 1 から頂点 4 までの最短距離に対応しています。実際、上のグラフを見ると頂点 1 から頂点 4 までの最短距離は 2 + 3 = 5 となっています。



半環の中でも、加法として min を、乗法として  + を持つ半環をトロピカル半環と呼びます。



  • Mohri, M. (2002). Semiring frameworks and algorithms for shortest-distance problems. Journal of Automata, Languages and Combinatorics, 7(3), 321-350. [ pdf ]