2008年03月13日

VLIW

命令語長を長くして、1命令で複数の処理を指定し
並列に実行できるようにした設計思想をVLIW(very long instruction word)
といいます。
インテル社のIA-64で採用されています
VLIWプロセッサは、整数/論理演算ユニット、浮動小数点演算ユニット
分岐ユニットなどの複数のユニットを装備しています。
コンパイル時に、同時に実行できる複数の命令を並列にならべて、各ユニットを割り付ける
仕組みです。



ebiguratan at 11:13|PermalinkComments(0)TrackBack(0)clip!

スーパスカラ方式

パイプライン処理を取り入れたCPUが、更なる速度向上を目指す場合、
命令の実行度をあげるため、命令の実行ユニットを複数搭載し
同時に実行できる命令数を増やす方法があります。
これをスーパスカラとよびます
スーパスカラもパイプライン同様、命令の実行順序や依存関係により
性能が変わります。パイプライン同様に、コンパイラが並行して実行できる命令を
解析する方法やアウトオブオーダが重要になります。





ebiguratan at 11:13|PermalinkComments(0)TrackBack(0)clip!

パイプライン処理

CPUの性能を向上させるための方法のひとつが、前項で述べた
クロック周波数の高速化です。これは1命令あたりの実行時間を短くして
性能を向上させる手法です。
一方、ひとつの命令の実行時間が同じでも、並列に実行することができれば
単位時間当たりの命令実行数は増加します。
すなわちスループットが向上するわけです。
この手法がパイプライン処理です。
ここでは、パイプラインやほかのスループットを向上させるための
アーキテクチャについて解説します


1.パイプライン
CPUの内部動作をいくつかのステージに分割して、ステージ単位で並行処理を行う仕組みです
例えば、情報処理技術者試験では、以下の5つのステージに分割したアーキテクチャが出題されます。

1.命令取り出し(IF:Instruction Fetch)
2.命令解読 (ID:Instruction Decode)
3.オペランドアドレス計算(OA:Operand Addressing)
4.命令実行 (E:Execute)
5.実行結果の格納(S:Store)

命令を直列に実行した場合とくらべ、パイプラインを採用した場合でも
1命令の実行時間は変わりません。
しかしお、命令の並行実行度を高めることにより、
スループットは向上します。
1命令に5CPIを必要とするCPUが2命令を直列に実行した場合
単純に10CPIかかります。
しかし、ステージ単位に並行実行が可能な
パイプライン処理を実行した場合、10CPIで6命令を実行できます。



直列処理の場合
例えば命令1と命令2を直列処理した場合

  1 2 3 4 5 6 7 8 9 10 (クロック)
1 IF ID OA E S
2         IF ID OA E S



パイプラインで処理した場合
1と同じクロック数で6個のもの命令を処理できることがわかります


1 2 3 4 5 6 7 8 9 10
1 IF ID OA E S
2   IF ID OA E S
3  IF ID OA E S
4   IF ID OA E S
5 IF ID OA E S
6         IF ID OA E S





ステージの分割数はCPUアーキテクチャによって異なります
例えば、初代のPentiumは、先ほどの例と同様の5ステージですが
pentium4では20ステージに分割して命令実行のスループットを向上させています
このようにパイプラインのステージを細分化したものをスーパーパイプラインと呼んでいます
しかし実際のパイプライン処理は上の図のようにはなかなかいきません
次のような場合においては特にです

1・分岐命令による分岐が発生した場合
2・前の命令の実行結果を必要とする場合
分岐命令がある場合、パイプライン中の命令を破棄する必要があります。
このため、実行効率の低下を招きます。このような現象を命令ハザードと呼びます
これを解決するためには、分岐命令による繰り返しを予測し
分岐命令が出現した場合は分岐先の命令をパイプラインに投入します。
そのためには、過去の分岐パターンを記憶し、パイプラインに投入する以前に判断する必要があります。
このような仕組みを分岐予測と呼びます
また前の命令の結果を次の命令で処理する場合、前の命令の実行を終わらなければ
次の命令は実行できません
上の図で言えば、データ1の結果をデータ2で使う場合
パイプラインで並行に処理することができないためデータ2は実行できないことがわかります。

例えば次のような命令があったとします

ADD R1.R2.R3  (R1=R2+R3)
SUB R4.R1.R5  (R4=R1-R5)

加算命令の実行結果を減算命令で使っています。
このような場合、パイプラインをつかっていると加算の結果が出力される前に
R1の値を読み出してしまうことになります。
このような現象をデータハザードと呼びます。
データハザードを回避するためには、コンパイラがあらかじめ命令の実行順序を適切に
修正して実行コードを出力するか
CPU内部で命令の依存関係を確認し、命令の実行順序を変更する
アウトオブオーダのような機能が必要になります。

また上の図の命令はすべて同じマシンサイクルで実行されていますが
実際には命令の種類によって実行に必要なマシンサイクルが異なります。
パイプラインを効率的に処理するためには命令の実行サイクルの均一化が効果的です
RISCがCISCよりも高速な理由のひとつに、命令実行のサイクルの均一化を図ったため
パイプラインの処理の効率が高いという点が上げられます。




ebiguratan at 11:13|PermalinkComments(0)TrackBack(0)clip!

CPUに関する問題

同じ命令セットをもつコンピュータAとBがある。
それぞれのCPUクロック周期と、あるプログラムを実行したときのCPI
は、表のとおりである。コンピュータAがこのプログラムを実行したときの処理時間は
コンピュータBの処理時間の何倍になるか。

       CPUクロック周期 CPI
コンピュータA  1ナノ秒   4
コンピュータB 4ナノ秒   0.5


1 1/32
2 1/2
3 2
4 8




解説
単純にCPIが8倍なのだから8倍を選択した人もいるのではないでしょうか
クロック周期が一緒であればそれいいのですが

CPUクロック周期とは1秒当たりに1回の振幅が起こる時間です
コンピュータAは1クロックあたり1ナノ秒(1秒に10億)なので、おおよそ1GhzのCPUでしょう
コンピュータBは4ナノ秒(1秒間に2500万)なので、おおよそ250MhzぐらいのCPUであることがわかります

CPIとは何クロックで命令がしょりできたかの指標でしたね
コンピュータAでの4クロック分とは
1クロックに1ナノ秒かかるので、1サイクルはそのまま4ナノ秒かかることになります

コンピュータBでの0.5クロック分とは
1クロックに4ナノ秒かかるので0.5クロックは2ナノ秒分であることがわかります

つまりコンピュータAの処理時間はコンピュータBの2倍です
従って正解は3になります。



ebiguratan at 11:12|PermalinkComments(1)TrackBack(0)clip!

マシンサイクル(クロック周波数)

CPUを含め、コンピュータの動作はクロックに従います
つまりコンピュータはすべて、マザーボード上に発振器(クリスタル)
をもち、そのクロック周波数を基準にして動作しています。
ただし、現在のほとんどのコンピュータは、そのロジックボード
(マザーボード)の提供する周波数の何倍かの周波数で動作しています
例えば、pentium4 3Ghzは、マザーボードが800MHz、CPUはその4倍の
クロックで動作しています
3Ghzということは、1秒間に30億回の振幅が発生します。
この1回の振幅する時間をマシンサイクルと呼びます。
従って、3GhzのCPUの1マシンサイクルは
30億分の1秒(1/3ナノ秒)になります。もし、1命令を平均
6マシンサイクルで実行できるのならば1命令の実行時間は2ナノ秒ということになります
またこのマシンサイクルのことを
CPI(Cycles Per Instrcution)といいます




ebiguratan at 11:12|PermalinkComments(0)TrackBack(0)clip!

CPUアーキテクチャ

1.CPUの動作原理
アーキテクチャとは本来建築様式のことですが、転じて組織や構造を意味するのように
なりました、CPUアーキテクチャとは、CPUの構造もしくは設計思想という意味です。
ここでは、CPUの動作原理について学習します

CPUは制御装置と演算装置からなり、そのおもたる役割は機械語命令の解読と実行です
現在のコンピュータはそのほとんどがノイマンアーキテクチャ
(ストアドプログラミング方式)を採用しているため、必ずメモリから命令
およびデータを取り出し、実行結果をメモリに書き込みます。

処理系列

1。命令の取り出し(フェッチ)
2.命令解読(デコード)
3.オペランド(アドレス計算)
4.オペランド(取り出し)
5.命令の実行
6.演算結果の格納

ここでの命令は、機械語命令の形をとります。


1.命令の取り出し
命令の取り出しはCPUの命令アドレスレジスタというものの中にある
内容をメモリ上のアドレス選択回路に送ります

このアドレス選択回路を通じて、該当するアドレスにある命令を見つけます
そしてメモリ上の読み書き回路を通じて、命令をCPUの命令レジスタに送ります
そして命令アドレスレジスタに命令後の長さを加算します

2.命令の実行
CPUの命令アドレスレジスタにはいっている命令をデコーダとよばれる
命令の解読装置(CPU内)に転送します
ここでデコーダが命令を解読しCPU内の演算回路におくられ初めて演算がおこなわれます



このCPU動作をいかに高速化していくかがコンピュータアーキテクチャの発展の歴史です
ハードウェアからみたコンピュータの必要用件は、データをいかに速く
大量にそして正確に処理できるかということです
CPUに限りませんが、高速化のために必要な要素は二つあります



1.処理時間の短縮
デバイス単体の高速化→一つ一つの処理時間を短縮できるように機能改善する
たとえばCPUのクロックをあげたりハードディスクの回転数を上げるなど

2.スループット(単位時間当たりの処理量)の向上
並行度を高める。つまり、単体の処理時間は変わらないが、一度に処理できる
データ量を多くする
たとえばCPUを何個も積んだりRAIDを組むなど、単体の性能に頼らず
平行して処理をさせることにより処理能力を上げます


やはりテクノロジーの進化というのは、=デバイス単体の高性能化
といってもいいのではないでしょうか
新しい素子、ナノテクノロジー、光エレクトロニクスなど
新しい技術が生まれてこそ進化です

これに対してスループットの向上はアーキテクチャや既存のテクノロジーの工夫により実現することができます




ebiguratan at 11:12|PermalinkComments(0)TrackBack(0)clip!

設問の具体例

1.改変
具体的な設問の例として「〜ができるようにへんこうするには、OO関数にどのような
処理を加えればよいか」などが挙げられます。このような設問では
具体的な追加処理(命令文)ではなく、処理内容を20字程度で
表現することを求められます。
もちろん記述に使う言葉はなるべく問題文にあるものを使うように心がけます

また「設問で何を聞かれているのか」を少しでも読み違えてしまうと
「理解できているのに解答がずれてしまっている」ということにもなりかねません。
記述した後は、もう一度、設問と自身の解答を読み直しましょう。

2.計算
具体的な設問の例として「図のようなデータの場合、プログラム文中の
☆(問題によってしるしはことなります)の命令は、何回実行されるか」
などが挙げられます。このような設問の場合は、特に計算するまでも無く
ソースプログラムの構造を把握していれば容易です。
問題文に記載されているたくさんの数字を使って、計算しなければならないような
設問の場合ケアレスミスをしないように、表を使って整理しながら計算を進めたり
必ず式には単位を書くなどの工夫をしてください。

3.メッセージ
具体的な設問の例として「プログラム文中の☆においてどのような
メッセージを表示させればよいか?」などがあげられます
既にプログラムの穴埋め作業で、どのようなメッセージを表示させればよいかは
漠然とわかるのではないかと思います。
ただ、これに限られた字数で表現すると
なかなか頭を悩ませてしまうところです。ここで、もう一度、問題文や図
プログラムにもどってください。その中から解答しなければならない
メッセージとは、違う種類のメッセージを発見したら
同じ表現方法を使って記述します。また、記述する際にメッセージで用いられる言葉は
なるべくもんだいぶんからピックアップしてください。


ebiguratan at 11:11|PermalinkComments(0)TrackBack(0)clip!

アルゴリズム問題の解き方

最初に、問題文と設問分を読み
どのようなプログラムであるか、どのようなことが問われているかを確認します。
大半の設問がソースプログラムの空欄を埋めるものであれば
穴埋めのための部分的なトレースだけで十分です。
しかし、穴埋め以外の設問が多くある場合
ソースプログラムを詳細に把握しなければなりません。
これは、設問に解答するためには、"問題文"とソースプログラムの両方をヒントにしなければならないものが多いからです。従って、どの程度トレースでいいのか
プログラムをどの程度把握すればよいのかは、最初に設問分を確認することによって
判断します。
まずは、ソースプログラムの穴埋めの設問から回答していきましょう。


1.ソースプログラムの把握手順
繰り返し処理の部分、分岐部分などを明確にします
自分なりの記号を使ってプログラムを見やすくするとわかりやすくなるでしょう
(特に多重For文や多重If文などわかりにくいものです)


2.パーツで考える
繰り返し部分や分岐部分をパーツと考え、それぞれがどのような役割をもっているか、
書き込みをしていくとよいでしょう。どのようなパーツかを把握しながら
空欄になっている部分を埋めていきます。


1分岐部分
分岐は、ある条件によって処理がわかれます。多くの場合
この”条件”や”処理”は、問題文中に直接記述されているか、
問題文中から容易に予測できます。
変数の役割が把握できず、その場で変数を使って記述することが困難な場合は
日本語でどのような処理をすればよいか、どのような条件かを記述しておくとよいでしょう。

2繰り返し処理
繰り返し部分全体で、何ができるのかを整理します
特に、入れ子(ネスト)構造になっている場合は、この作業が重要です
何回繰り返せばよいのかがわかれば繰り返し部分の役割が明確になります。
問題文にあるサンプルのデータで考えていくとよいでしょう。
このとき、継続条件を記述するのか、終了条件を記述するのかを必ず確認し
配列の添字がいくつから始まるのかもあわせて確認します。
また、繰り返し部分の条件で使われる変数がどこの位置で初期化されているか
どの位置で値を更新しているかを把握することが、繰り返しの部分の構造を整理する
突破口となることが多いです。変数の役割を確認するとともに、初期亜化
と値更新の位置を確認しましょう。




ebiguratan at 11:11|PermalinkComments(0)TrackBack(0)clip!

整列に関する問題

次の手順はシェルソートによる整列を示している
データ列 7,2,8,3,1,9,4,5、6
を手順1〜4に従って整列するとき、手順3を何回繰り返して
完了するか。ここで、「」は小数点以下を切り捨てた結果を表す

1 「データ数/3」→Hとする
2 データ列を互いにH要素分だけ離れた要素のあつまりからなる
部分列とし、それぞれの部分列を、挿入法を用いて整列する。
3 「H/3」→Hとする
4 Hが0であればデータ列の整列は完了し、0でなければ2に戻る



1、2
2、3
3、4
4、5






解説
まず今回のデータ数は9です
1により9/3=3 
H=3となり

2でH(3)要素分だけ離れた要素の集まりからなる部分列をつくります


ebiguratan at 11:11|PermalinkComments(0)TrackBack(0)clip!

高速ソート

ここでは前に紹介した整列法よりも
より高速に整列することに特化した整列法もあります

1.クイックソート
要素を中央の値で2分割し、中央よりも大きな値と小さな値に分けます
2分割した配列をそれぞれ同じように分割、要素の振り分けを行います。

61734825
   ↑3を中央値とする

213 74865
 左から3以上を発見し、右から3以下を発見したら入れ替え
 左は3>=の数 右は3<の数


213     74865
 ↑中央値     ↑中央値

1 23    74658
  ↑中央値    ↑中央値
1 2 3   465 78       

1 2 3   45 6 78  
         ↑中央値


12345678



ebiguratan at 11:11|PermalinkComments(0)TrackBack(0)clip!
Profile
Recent Comments