Mercurial > hg > Papers > 2016 > kkb-master

annotate slide/pre.md @ 25:7fc1656c2819

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
revision
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Fri, 19 Feb 2016 12:52:10 +0900
parents
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
25
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 % ode Segment と Data Segment を持つ Gears OS の設計
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 % Shohei KOKUBO
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 % 22/Feb/2016
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 # 並列環境下におけるプログラミング
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 マルチコア CPU の性能を発揮するには、処理をできるだけ並列化しなければならない。
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 これはアムダールの法則により、並列化できない部分が並列化による性能向上を制限することから言える。
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 つまり、プログラムを並列処理に適した形で記述するためのフレームワークが必要になる。
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 # 並列環境下におけるプログラミング
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 マルチコア CPU 以外にも GPU や CPU と GPU を複合したヘテロジニアスなプロセッサが登場している。
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 並列処理をする上でこれらのリソースを無視することはできない。
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 しかし、これらのプロセッサで性能を引き出すためにはそれぞれのアーキテクチャに合わせた並列プログラミングが必要になる。
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 並列プログラミングフレームワークではこれらのプロセッサを抽象化し、CPU と同等に扱えるようにすることも求められる。
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 # Cerium の問題点
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 - Task 間の依存関係
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 - データの正しさを保証できない
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 - データの型情報
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 - 並列処理の組み合わせが型的に安全なのか保証できない
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 - メモリ確保
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 - ある Thread がメモリを確保しようとしている間、他の Thread はメモリを確保することができない。結果、処理速度の低下に繋がる
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 - オブジェクト指向と並列処理
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 - 一般的に参照透過な処理は並列化を行いやすい。一方、オブジェクト指向ではオブジェクトの状態によって振る舞いが変わるため並列処理との相性が悪い
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 # Gears OS
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 - Code Segment と Data Segment という単位で構成される
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 - Code Segment は並列処理の単位
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 - Data Segment はデータそのもので型情報を持つ
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 - Continuation based C(CbC) による実装
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 - 並列化、ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行える
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 - Allocator
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 - Thread ごとに独立したメモリ空間を持つ
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 - TaskQueue
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 - Task の管理
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 - CAS 命令を利用して操作することでデータの一貫性を保証する
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 - Persistent Data Tree
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 - Data Segment の管理
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 - 非破壊木構造で構築するので平行して読み書き可能
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 - Red-Black Tree アルゴリズムを用いて平衡性を保ち、挿入・削除・検索における処理時間を保証する
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
41
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 # Gears OS
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 - Worker
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 - TaskQueue から Task を取得し、実行
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 - 並列に実行される Code Segment は通常の Code Segment と同等
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 - 依存関係のない Code Segment はすべて並列に動作させることが可能
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 - 1 CPU と 12 CPU で約11.8倍の性能向上を確認
7fc1656c2819 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 - Gears OS の実装自体が Gears OS を用いて並列処理を記述する際の指針となっている