Take Advantage of Parallelism

Premise

Difference between concurrency and parallelism

http://tutorials.jenkov.com/java-concurrency/concurrency-vs-parallelism.html http://tutorials.jenkov.com/java-concurrency/concurrency-vs-parallelism.html

Process and Thread

  • マルチプロセス(multiprocess)
    http://www.ni.com/product-documentation/6424/ja/

    複数の処理を非常に短い時間で交代で行うことで,複数のタスクを同時処理するための機能.
    このタスクの切り替え処理のことをコンテキストスイッチと呼ぶ.
    それぞれのタスクはそれぞれのメモリ空間を持っているため,マルチプロセス化はマルチスレッドに比べて行いやすい.

  • マルチスレッド(multithread)
    http://www.ni.com/product-documentation/6424/ja/

    マルチスレッドとは,単一のプログラム(アプリケーション)内での作業を並列化するための機能.
    この場合,同一のメモリ空間を用いているため,ある変数の処理に当たって,その変数をロックしてあげなければならない.
    適切にスレッドをロックしなければ,デッドロックという現象に陥り,どこからも参照できない値ができてしまう.

(image:http://www.ni.com/product-documentation/6424/ja/)

Contents

Introduction

並列処理に関する細かい使用等は,ConceptsのParallelism.

Take advantage of parallelism

  • フリンの分類( Flynn's taxonomy)
    マイケル・J・フリン(Michael J. Flynn)によって1966年に提唱された,並列ハードウェアの分類法

    種類処理の方法使われている例
    SISD(Single Instruction stream, Single Data stream)命令,データ共に並列性のない逐次的なコンピュータIntel Pentium 4(~2008)
    SIMD(Single Instruction stream, Multiple Data stream)単一の命令列を複数のデータに適応するコンピュータx86 SSE命令
    MISD(Multiple Instruction stream, Single Data stream)複数の命令列を単一のデータに適応するコンピュータ(なし)
    MIMD(Multiple Instruction stream, Multiple Data stream)異なる命令列で異なるデータを処理するコンピュータIntel Core i7
  • SIMD型コンピュータについて
    https://ja.wikipedia.org/wiki/SIMD
    (img:https://ja.wikipedia.org/wiki/SIMD)

    SIMD型コンピュータではデータのベクトル,つまり1次元配列を操作する.SIMDでは単一の命令が与えられた時,その命令に対して全ての並列実行ユニットが同期して応答する,この仕組みによって命令のバンド幅や空間を小さくすることが可能となる.SIMD型マシンのもっとも得意とする操作はforループで配列を処理する場合であり,逆にcase文やswitch文はSIMDの苦手とする操作である.これはデータの内容に基づいて同期的ではなく,別々の操作を行わなければならないためである.SIMDの現代版は今日でも使われ続けている.
  • アムダールの法則(amdahlの法則) 逐次的アルゴリズムとそれに対応したアルゴリズムの並列化実装によって期待できる高速化の関係をモデル化したもの.
    一般にアムダールの法則は,

    S_latency(s) = 1/((1-P)+P/s)

    S_latency(s)...どのくらい速度が上昇するのかという理論的な比率
    s...改善量(プロセッサの数)
    P...問題の中で改善の影響を受ける実行時間
    https://en.wikipedia.org/wiki/Amdahl%27s_law
    (img:https://en.wikipedia.org/wiki/Amdahl%27s_law)

Parallel Scalability Isn’t Child’s Play

並列処理のプログラムを設計することは一般に難しいとされている.その例を以下のような例を使って示していく. コンピュータの構成と設計(下)から以下のような例を考える.

  • 問題の規模を変えずに,速度を向上させる場合.

    例: プロセッサの数を100個まで増やした時に速度が90倍に向上するようにしたい. アムダールの法則から,速度向上比= 90, プロセッサ数=100として,

    90 = 1/{(1-並列化の影響を受ける時間の割合(P)) + 並列化の影響を受ける時間の割合(P)/100}

    これを解くと並列化の影響を受ける時間の割合は0.999, つまり影響を受けない逐次処理の部分は約0.1%までしか許容されない.

この例からわかる様に問題の大きさを固定したまま,速度向上比を高めようとするのは困難を極める.この様に問題の規模を固定したまま達成される速度向上を強いスケーリングという.


では次に以下の様な例を考える.

  • プロセッサの数とともに問題の規模も大きくしていく場合

    例:和を2つ求めたい.1つは10個のスカラ値の和で,もう一つはサイズが10*10の2次元の配列同士の行列和である.行列の和だけが並列処理可能であると想定する.
    この時プロセッサを10個から40個に増やすとどれだけの速度上昇が得られるか.行列が20*20になった場合はどうか.

一回の加算に要する時間をtとする.この時,性能はtの関数としてかけると仮定する.
逐次処理では,どちらも並列化されないため,合計110tかかるとする.

アムダールの法則から,
改善後の実行時間 = 改善の影響を受ける実行時間/改善度 + 改善の影響を受けない実行時間

という様に表すことができるから,並列処理による改善後の実行時間は,

改善後の実行時間 = 100t/10 + 10t = 20t

よって10個のプロセッサを用いた場合の速度向上比率は

110t/20t = 5.5
40個のプロセッサを使用した場合は,

改善後の実行時間 = 100t/40 + 10t = 12.5t

よって40個のプロセッサを用いた場合の速度向上比率は,

110t/12.5t = 8.8t

それぞれ一つあたりの速度上昇比率に直すと,

プロセッサの個数全体の速度上昇比率プロセッサ1個あたりの速度上昇
105.50.55(55%)
408.80.22(22%)
100100.10(10%)


行列を20*20にした場合.
逐次処理のプログラムであれば,実行時間は,10t + 20*20t = 410tとなる.
10個のプロセッサを使用した場合,実行時間は

改善後の実行時間 = 400t/10 + 10t = 50t

したがって10個のプロセッサを用いた時の速度向上比率は,

410t/50t = 8.2

となる.40個のプロセッサを使用した場合も同様に,

改善後の実行時間 = 400t/40 + 10t = 20t

速度向上比率は,

410t/20t = 20.5

よってプロセッサ一つあたりの速度向上比を考えると,

プロセッサの個数速度向上比率プロセッサ1個あたりの速度向上比率
108.20.82(82%)
4020.50.51(51%)
10029.30.29(29%)


プロセッサの数の増大に比例して,問題の規模も大きくしていくことで達成される速度向上を弱いスケーリングという.

(from:コンピュータの構成と設計 第5版 下 (日本語) Paperback – 2014/12/6 by デイビッド・A・パターソン (著), ジョン・L・ヘネシー (著), 成田光彰 (翻訳))

Instruction-level parallelism

Instruction-level parallelism 依存関係がない処理を同時並列的に行うことで,高速化を行う手法.

Reference

cocori(Ryosuke Satoh)


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2019-07-27 (土) 12:55:45 (783d)