8 並列処理ソフトウェアの課題と対策技術

8.2.1 非決定性

並列プログラムの挙動には「非決定性」を含む場合がある。非決定性を持つプログラムでは、状態遷移の分岐が排他的でない。これはテストプログラムや不具合事象の再現性が悪く、デバッグしにくい。

8.2.2 複雑性

並列に動作する別別のスレッドが別々の状態遷移を持つため、システムの状態はその組み合わせになり、複雑で、膨大な振る舞い空間をもつ。これはシステム挙動の網羅的な検証が困難である。

8.3.1 振る舞いの非決定性

プロセスPAとPBが並行に動作する場合、「可能な挙動」は組み合わせが膨大になりうる。

PA = ea1 -> ea2 -> ea3 -> Stop;
PB = eb1 -> eb2 -> eb3 -> Stop;

8.3.2 データ破壊・不整合

複数スレッドが共有メモリ領域を読み書きする場合に起きる。並列に動作する複数のスレッドが共有の記憶領域に対して同時に書き込むような場合に、データが適切に更新されず、矛盾・破壊する事がある。これではプログラムの機能（入出力仕様）が保証されない。データ破壊は同時書き込み時に起こる。また、データ不整合は複数のメモリ内の情報の間に成り立っていなければならない関係（条件）が崩れる。

8.3.3 デッドロック

並列に動作する複数のスレッドが共有の記憶域にアクセスするために組み込んだ「排他制御」が想定通りに動作せず、システムが停止してしまう。これではプログラムの可用性が保証されない。また、共有リソースのロックが外れなくなる。

次の例では、連続するタイミング1,2においてThread A,BがそれぞれリソースR1,R2を異なる順番でロックすることでデッドロックするケースを示す。

タイミング１：

ThreadAがリソースR1を利用(R1をロック）
ThreadBがリソースR2を利用(R2をロック）

タイミング２：

ThreadAがリソースR2を使おうとしてR1のアンロックを待つ
ThreadBがリソースR1を使おうとしてR2のアンロックを待つ
＜＜＜Deadlock＞＞＞

8.4.1 オートマトン ( A = {S, s0, E, T} )

有限オートマトンを用いる

8.4.2 プロセス代数 ( X = A op B )

並行プロセスを代数的な操作ができる「式」として表現する事で、並行動作するシステムの振る舞いを解析する。プロセス代数(CSP等)で、並行動作するシステム同士が協調動作する事を表現するのに「チャネル」の概念を使う。ここで、プリミティブ要素として「同期チャネル」を用意しているが、拡張要素として、「通信バッファ数」を指定できるモデルもある。

記述例

• プロセスPAとプロセスPBの並行合成演算

PA || PB

• 仕様を表現したプロセス Specと設計を表現したプロセスDsgが「詳細化関係(refinement)を満たすか」

Spec <refine> Dsg

8.4.3 現存するツール

より詳細はWikipediaを参照

8.4.4 モデル検査ツール適用の流れ

1. モデル作成
   • 挙動のモデル
2. 検証式(assertion)記述
   • 要件由来（機能・非機能）など、システムが満たしているべき性質を記述
   • 抽象的には以下のようなものが記述可能
     • 到達可能性
     • 安全性
     • 他(Deadlockしない、Livelockしない、など）

8.6.1 並列処理に向いたプログラミング言語

8.6.2 並列指向言語/ライブラリ

8.6.3 並列処理指向言語の例 – Go

• Kenneth Lane Thompson(Cの開発者)らによって開発された。
• 言語要素として Thread、Channelの概念を持つ。

ch := make(chan int, 8) // バッファサイズ8のint型チャネル

go hello();     // hello 関数を別Threadで実行. helloは別途定義した関数
go world();     // world 関数を別Threadで実行. worldは別途定義した関数

8.6.4 並列処理指向言語の例 – Rust

• Mozilla Researchの公式プロジェクト
• 速度、並行性、安全性を言語仕様として保証するC言語、C++に代わるシステムプログラミングに適したプログラミング言語を目指しており、強力な型システムとリソース管理の仕組みにより、メモリセーフな安全性が保証されている。

  • 「所有権(ownership)」概念の言語要素化

    → 安全でなければコンパイルが通らない

let(tx, rx): (Sender<i32>, Reciever<i32>) = mpsc::channel();

let child = thread::spawn(move || {<Thread手続き本体>})

8.6.5 マルチスレッド/通信 API

• マルチコアの活用のためにはプログラムが複数の並列実行可能な単位(Thread)に分割されている必要がある。プログラムをそのように構成するためには、Threadの生成/開始のようなThreadの実行制御に関わるものと、仮に共通にアクセスできるメモリがない場合に通信可能な、「Thread間通信」が実現できることが好ましい。

8.6.6 メッセージ送受信API

• 2つのEnd-Pointを指定し、「チャネル」オブジェクトを定義し、それに対して送受信する。

EndPoint ep1, ep2;
Channel ch =  new Channel<DataType>(ep1, ep2);

DataType data;
send(ch, data);  // Code in Thread 1
receive(channel, &data);    // Code in Thread 2

8.6.7 参考情報(MCAPI)

• MCAPI - The Multicore Association
  • https://www.multicore-association.org/workgroup/mcapi.php
• Wikipedia
  • https://en.wikipedia.org/wiki/MCAPI
• MCAPI事例(Mentor Graphics)
  • http://www.mentorg.co.jp/training_and_services/news_and_views/2010/autumn/feature_story2/index.html

8.7.1 マルチコアに対応したOSの機能

• Thread-Core Affinity (Static)
  • Configurationによってあらかじめ指定
• Thread-Core Migration (Dynamic)
  • 動的にCore割り当てを変える事ができる
• Message Passing
  • スレッド間通信機能

8.7.2 MulticoreOSの特徴(動作モデル)

遷移イベントはアプリケーションによるOSのAPIコール

1. Single Coreの場合
   • Runningになれるタスクは１個
2. Multi- Core(N-Core)の場合
   • RunningになれるタスクはN個

8.7.3 Single Core 3 task

• Single Core - ３task
• 優先度 : task1 > task2 > task3
• 制約
  1. あるタイミングでRunningになれるタスクは最大１つ
  2. もっとも優先度が高いreadyタスクがRunningになる
  3. readyタスクがあるのにRunningタスクがないことはない

8.7.4 2 Core 3 task

• Single Core - ３task
• 優先度 : task1 > task2 > task3
• 制約
  1. あるタイミングでRunningになれるタスクは最大2つ
  2. もっとも優先度が高いreadyタスクがRunningになる
  3. readyタスクがあるのにRunningタスクがないことはない

8.7.5 マルチコア対応RTOSの例

• eMCOS
  • https://www.esol.co.jp/embedded/emcos.html
• QNX
  • https://blackberry.qnx.com/jp
• POSIX対応OS (Posix Thread)
  • https://en.wikipedia.org/wiki/POSIX_Threads
• TOPPERS/FMP
  • https://www.toppers.jp/fmp-kernel.html

8.8.1 設計パターンとは

ソフトウェアのアーキテクチャ、デザイン、コーディングなどに対して、解決策としてのパターンを共有する。パターンはお互いに関連しあい、連携して利用されるパターン言語を形成する。

代表的な設計パタンのルーツは次の通り。現在は様々な領域でのパターン活動がある

• Pattern Language(Christopher Alexander )
• Software Design Pattern (GOF ※)
• Pattern Oriented Architecture Pattern (bushman)
• Taming Java Threads (Allen Holub)

※ Eric Gamma, Rechard Helm, Ralph Johnson, john Vissides

8.8.2 並列化ソフトウェア設計パターン

マルチ/メニーコアを利用したハードウェア上で動作する「並列処理ソフトウェア」に対しても、この「パターン」の蓄積・共有が有効だと思われる。

これらの設計パターンを用いる動機は、起こって欲しくない「設計由来の問題」をなくしたいことである。

• デッドロック
• 共有データの破壊
• 理解しがたい複雑さ
• デッドライン違反
• より効率的に処理を構成したい
• 複数コアの有効活用
  • 無駄な通信を少く
  • コア数非依存アルゴリズム（スケーラブル）

8.8.2.1 Pattern Template

活用可能なパターンカタログを作るために以下のような項目がそろっているのが望まれる

8.8.2.2 Pattern Example (From Eun-Gyu Kim / 2004)

http://snir.cs.illinois.edu/patterns/patterns.pdf

8.8.2.3 Concurrency Patterns (POSA2)

ソフトウエアアーキテクチャパターンの書籍(POSA:Pattern Oriented Software Architecture)中に並列処理パターンもいくつか紹介されている。

8.8.2.5 Structured Parallel Programming

• Subtitle : Patterns for Efficient Computation
• Michael McCool, Arch D. Robinson, James Reinders

並列プログラムを構成するためのパターンを紹介し、後半にはそれらを使った並列アルゴリズムの解説を行っている

8.9.1 並列化支援環境

並列化されていないプログラムのどこが並列化可能か、並列化する事による性能改善への寄与が大きいかといった情報を開発者へ提示。Threadプログラミング支援。

8.9.2 自動並列化技術

並列化されていないプログラムをスレッドライブラリなどを利用した並列化されたプログラムに変換する。

それにあたって、並列化されていないプログラムを解析（基本的にはデータフロー解析）して並行動作可能部分を抽出しスレッド化プログラムとして再構成する。さらに、限られたコア数に対してそれらのスレッドを割り当て配分する。

• CUDA – nVidia
  • GPGPU向け
• OpenCL - Khronos Group
  • Embedded Profile (組み込み向け)
• Intel Parllel Studio
  • 統合開発環境として提供
• Eclipse Parallel Tools Platform (PTP)
  • MPI, OpenMP, UPC(Unified Parallel C), OpenSHMEM ,OpenACCをサポート

8.9.3 自動並列化技術（具体例）

• eMBP( eSOL ) based on MBP ( Nagoya Univ.)
  • Input : (Simulink Block Model , C Code generated by Embedded
  • Output : Parallelized C Code (use multi-thread library)
• SILEXICA (SILEXICA)
  • Tool Set for support parallelization
• Automatic Parallelization Compiler
  • OSCAR (waseda Univ)
    • C source -> Parallelized C (with OSCAR API)
  • Intel Compiler
    • C source -> Parallelized C(with openMP)
    • (--parallel option)
  • Solaris Stuio Fortran (Loop optimizatation)
    • -autopar option
  • PLUTO (Not general)
    • Automatic parallelizer and locality optimizer fo raffine loop nests
    • http://pluto-compiler.sourceforge.net/

8.9.4 自動並列化の考え方

• 入力：並列化されていないプログラム
• 出力：並列化(Multi-Thread化）されたプログラム
• 並列化プロセス：
  • データフロー解析
    • 変数の代入関係を解析し、処理単位のデータ依存グラフ、タスクグラフを抽出。グラフ構造から並列可能な部分（ノード）が分かる
  • コア割り当て
    • ノード（タスク）が動作するコアを割り当てる。
  • 並列化コード生成
    • 別なコアに割り当てられた処理単位は別なスレッドとして動作するようなマルチスレッド・コードとして生成する。
• 並列化のゴール
  • 処理速度の向上（処理時間を最小化）
  • 低消費電力化（プロセッサの消費電力を最小化）
  • 上記２つのゴール指標はトレードオフ

8.9.5 モデルベース並列化技術

• 入力
  • データフローとして解釈できるモデル
  • そのモデルに対応して作成/生成されたプログラムコード(C言語プログラムなど）
• 出力
  • Thread化されたプログラム
  • Threadへのコア割り当て情報
• 並列化プロセス
  • データフローはモデルから取得
  • 負荷分散、クリティカルパスなどの制約を満たすコア割り当てのルールを適用する

8.9.6 MBDは並列設計に利用可能

モデルベースの設計ツールが対象としている「モデル（ソフトウェア観点）」には、「データフロー」モデル、および、「状態遷移モデル」をがあり、これらをグラフィカルエディタなどの支援のもとに設計すると、そこから並列性を自動抽出することが可能となる。

• データフロー
  • Matlab/Simulink
  • LabView
• 状態遷移モデル
  • Stateflow
  • EHSTM

8.9.6.1 MBDにおける並列化の例(eMBP / eSOL)

SimulinkモデルとSimulinkモデルから生成されたCソースコードから並列化（Thread化）されたCソースコードを出力。

Threadのコア割り当てのためにSHIM(IEEE Std 2804)を利用した性能見積もりを行う。

8.10.1 トレースフォーマットCTF

• フォーマット名: CTF(Common Trace Format)
  • https://www.efficios.com/ctf
• 対応ツール
  • TraceCompass
  • Eclipse-plug-in

8.10.1.1 CTF特徴

• 対象ファイルフォーマット
  • トレース要素定義ファイル(DSL) meta
    • イベントを定義
  • 対象ファイル
    • 計測データ
• MCAからも参照されている
  • TOOLS INFRASTRUCTURE WORKING GROUP (TIWG™)
    • https://www.multicore-association.org/workgroup/tiwg.php

8.10.2 可視化技術

8.10.2.1 CTF対応ツール

• TraceCompass
• Eclipse-plug-in

8.10.2.2 TOPPERS/TLV

• Trace Log Visualizer
• https://www.toppers.jp/tlv.html