annotate 5.tex @ 2:35b71ac6ce17 default tip

update tags
author convert-repo
date Mon, 10 Nov 2008 05:00:42 +0000
parents 685b35adf419
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
685b35adf419 Initial revision
kono
parents:
diff changeset
1 \section{ CbCでのCellのプログラムの流れ}
685b35adf419 Initial revision
kono
parents:
diff changeset
2
685b35adf419 Initial revision
kono
parents:
diff changeset
3 CbCを用いて、Many Core Architecture のプログラムを作成する
685b35adf419 Initial revision
kono
parents:
diff changeset
4 流れは以下のようになる。
685b35adf419 Initial revision
kono
parents:
diff changeset
5
685b35adf419 Initial revision
kono
parents:
diff changeset
6 {\small
685b35adf419 Initial revision
kono
parents:
diff changeset
7 \begin{verbatim}
685b35adf419 Initial revision
kono
parents:
diff changeset
8 1. C によりアルゴリズムをシーケンシャルに記述する
685b35adf419 Initial revision
kono
parents:
diff changeset
9 2. データを並列用に分割した構造に変更する
685b35adf419 Initial revision
kono
parents:
diff changeset
10 3. Cの記述をCbCの記述に変換する(必要な部分のみ。手動)
685b35adf419 Initial revision
kono
parents:
diff changeset
11 4. コードセグメントを並列実行用に分割する
685b35adf419 Initial revision
kono
parents:
diff changeset
12 5. FIFOスケジューラにより動作を確認する
685b35adf419 Initial revision
kono
parents:
diff changeset
13 6. SPUスケジューラによりCell上での動作を確認する
685b35adf419 Initial revision
kono
parents:
diff changeset
14
685b35adf419 Initial revision
kono
parents:
diff changeset
15 \end{verbatim}
685b35adf419 Initial revision
kono
parents:
diff changeset
16 }
685b35adf419 Initial revision
kono
parents:
diff changeset
17
685b35adf419 Initial revision
kono
parents:
diff changeset
18 これらの各過程すべてでエラーが入る可能性がある。また、
685b35adf419 Initial revision
kono
parents:
diff changeset
19 論理的なエラーだけなく、仕様に沿った十分な性能が出るか
685b35adf419 Initial revision
kono
parents:
diff changeset
20 どうかも検証する必要がある。
685b35adf419 Initial revision
kono
parents:
diff changeset
21
685b35adf419 Initial revision
kono
parents:
diff changeset
22 1 の段階は通常のCのプログラミングであり、この部分がちゃんと
685b35adf419 Initial revision
kono
parents:
diff changeset
23 動くことが必須である。この段階では、入力に対して出力が
685b35adf419 Initial revision
kono
parents:
diff changeset
24 一意に決まる状況であり、テストは容易である。バグも
685b35adf419 Initial revision
kono
parents:
diff changeset
25 実行トレースの二分法により容易に行うことが出来る。
685b35adf419 Initial revision
kono
parents:
diff changeset
26
685b35adf419 Initial revision
kono
parents:
diff changeset
27 4段階まではプログラム変換の問題であり、一つ前の段階と
685b35adf419 Initial revision
kono
parents:
diff changeset
28 同じ結果を得られるかどうか検証する必要がある。
685b35adf419 Initial revision
kono
parents:
diff changeset
29
685b35adf419 Initial revision
kono
parents:
diff changeset
30 5 段階以前はアーキテクチャに依存しないので、ターゲット
685b35adf419 Initial revision
kono
parents:
diff changeset
31 が開発途中の段階でも記述することが可能である。しかし、
685b35adf419 Initial revision
kono
parents:
diff changeset
32 5段階では、FIFOスケジューラの替わりに、Randomスケジューラ
685b35adf419 Initial revision
kono
parents:
diff changeset
33 などを使うことができ、並列実行特有の非決定的な実行が
685b35adf419 Initial revision
kono
parents:
diff changeset
34 導入される。
685b35adf419 Initial revision
kono
parents:
diff changeset
35
685b35adf419 Initial revision
kono
parents:
diff changeset
36 非決定的な実行は、クロックベースのハードウェアでは
685b35adf419 Initial revision
kono
parents:
diff changeset
37 入力の任意性から生じることが多い。ハードウェアでも
685b35adf419 Initial revision
kono
parents:
diff changeset
38 複数のタスクを使用したり、外界と相互作用する場合は
685b35adf419 Initial revision
kono
parents:
diff changeset
39 非決定的な実行が現れる。
685b35adf419 Initial revision
kono
parents:
diff changeset
40
685b35adf419 Initial revision
kono
parents:
diff changeset
41 段階5では、これらの非決定的な実行でも4段階までと
685b35adf419 Initial revision
kono
parents:
diff changeset
42 同じ仕様を満たすことを検証する必要がある。これは、
685b35adf419 Initial revision
kono
parents:
diff changeset
43 逐次型のプログラムでは出て来ない問題である。
685b35adf419 Initial revision
kono
parents:
diff changeset
44
685b35adf419 Initial revision
kono
parents:
diff changeset
45 段階6では、段階5まできちんと動いていれば、問題なく
685b35adf419 Initial revision
kono
parents:
diff changeset
46 動作すると期待される。しかし、FIFOスケジューラと
685b35adf419 Initial revision
kono
parents:
diff changeset
47 SPUスケジューラでは、同期機構の実現が異なることが
685b35adf419 Initial revision
kono
parents:
diff changeset
48 ある。これは、並列実行と同期機構のの粒度と意味論
685b35adf419 Initial revision
kono
parents:
diff changeset
49 が異なるために起きると考えられる。
685b35adf419 Initial revision
kono
parents:
diff changeset
50
685b35adf419 Initial revision
kono
parents:
diff changeset
51 ここで、段階1が仕様であり段階5が実装であると
685b35adf419 Initial revision
kono
parents:
diff changeset
52 考えることもできる。実際のプログラムとは別に、
685b35adf419 Initial revision
kono
parents:
diff changeset
53 実行時に満たして欲しい仕様の記述がある場合もある。
685b35adf419 Initial revision
kono
parents:
diff changeset
54 これらの記述は、例えば、「計算がいつか終る」
685b35adf419 Initial revision
kono
parents:
diff changeset
55 等の時相論理的な記述になる。時相論理としては、
685b35adf419 Initial revision
kono
parents:
diff changeset
56 LTTL\cite{wolper82}, CTL*\cite{synBTTL}, ITL\cite{kono93b}
685b35adf419 Initial revision
kono
parents:
diff changeset
57 などを使うことができる。
685b35adf419 Initial revision
kono
parents:
diff changeset
58
685b35adf419 Initial revision
kono
parents:
diff changeset
59