CourseraのParallel, Concurrent, and Distributed Programming in Java Specializationを修了した
Rice UniversityのParallel, Concurrent, and Distributed Programming in Java Specializationを修了した。
名前の通り、このSpecializationは以下の3つのコースからなる。
前回言及したのは最初のコースである。残りの2つも無事修了したので、晴れて全課程完了となった。 備忘のために2つのコースでの学習内容を引用しておく。
Concurrent Programming in Java
個人的に3つのコースの中で一番ためになった。
- 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
このコースはHadoop、Spark、Kafka、OpenMPIといった定番OSSの紹介が主で、コーディング課題はこれらのOSSに軽くふれるものだった。デモビデオの内容をほぼそのまま写経すれば課題クリアとなるので、これまでのコースの中で一番簡単だった。
- 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.
HadoopとSparkの違いがわかってよかった。両方ともMapReduceパラダイムに基づいた分散処理用のフレームワークだが、SparkはHadoopよりもメモリを積極的に使うことで、より効率的な分散処理を実現しようとするもの。
- 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はこれら「リスキー」な機能を根本的に見直そうとしているらしい。 www.infoworld.com
- 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.
なんとこのSpecializationも終盤になってようやくプロセスとスレッドの違いが解説される。reactiveモデルにもややふれる。
結論
Javaに限らず、並列コンピューティングの概要を体系的に学びたかったので、広く浅くさまざまな概念を学べるこのSpecializationは非常に有益だった。定期的に復習して忘れないようにしたい。
