2005/05/17 数値解析学と演習 福井 先生 # 計算機の基礎の話は本日で終り # 来週から、いよいよ数値計算の話 (前回、やった..) ノイマン型の計算機 => プログラム内蔵型計算機 プログラムとデータが同じメモりの中に共存している プログラムとデータの区別はない IC の指している先がプログラム ( の一部となっている命令 ) # IC (Instraction Counter), PC (Program Counter), 命令カウンタ IC は、一命令単位で命令を指し示す ( 実行後は、次の命令を指す ) IC の内容は ( メモり内の位置を表す ) アドレス アドレスは、 1 byte 単位だが、命令は、それより長いことが多い 4, 6, 8 byte の長さになることもある Jump (分岐) 命令は、IC の書き換えで実現される => IC を明示的に書き換えることが jump/go 命令 ノイマン型の計算機の計算の仕組 (プログラムもデータもメモり内にある) # a = b + c をどう計算するか ? 1) (CPU は、IC にはいっているアドレスが指す) メモり内の命令を取り出し => フェッチ ( 命令をメモりから取り出すこと ) 2) 命令の内容を解読する => デコード ( 取り出した内容がどのような命令かを判断する ) データの中に命令が「詰込まれて」いる ( エンコードされている ) これは、命令を可能なかぎり小くし、メモりを節約するため しかし、扱い難い => 扱いやすい形にする必要がある => デコード # 例 : デジカメの写真 # 保存する場合は、jpeg 形式 ( 圧縮された形 ) に変換する # => エンコード ( サイズを小くする ) # 表示する場合は、元に戻す必要がある ( 展開 ) # => デコード ## ここで、命令が「足し算」であることに気が附く 3) データをメモりから取り出す => ロード # 同じメモりから情報を取り出す作業だが、コードとデータでは区別して表現している。 ## b を取り出す 4) ## c を取り出す 5) 計算 ## 足し算を行う 6) 計算結果をメモりに書き込む => ストア # 命令の実行の中で、何度も、メモリと CPU の間で情報のやり取りがある # a = b + c の場合は 3 度読んで、1 度書く # メモりアクセスの回数は、命令によって異る # a = - b ならば、 2 度読んで、1 度書く ## メモりアクセスの特徴 ## コードの場合は、Read Only, データの場合は Read/Write 両方 # ここまでは、古典的な PC の動作の話、今の CPU はもっと、複雑なことをしている 今風の CPU の速度 1 GHz 程度 1 動作を 10^(-9) 秒 ( 1 ns ) で実行できる # 1970 年頃の世界最初の Cray I は一命令 12.5n # つまり、今の計算機はこの 10 倍速い.. # CPU そのものは速いのだが、それだけで速度がきまるか .. ? ## 命令を実行するには、メモりから命令を読み出す必要がある.. 現在のメモリの形式 : DRAM ( Dynamic Randa Access Memory ) 「メモりアクセスは遲い」... Why ? アドレスを指定しないメモりは読み出せない DRAM は、データを読み出すとその内容が失われる 読み出す度にもう一度、書き戻す必要がある DRAM は、コンデンサーで実現されている 放っておくと、内容が失われる # コンデンサーの特性 ( 放電 ) ## コンデンサー : 足付きのオレンジの丸いやつ # メモりは、状態を保存しているから、役に立つ ## 黒板が役立つのは、チョークが黒板に張り付いているから 何もなくても、データの更新を行う必要がある => リフレッシュ 1 秒間に、4096 回、リフレッシュを行う # リフレッシュサイクル プロセッサーからメモりにデータを要求して、そのデータが戻ってくるまで.. 50ns 位かかる ( データアクセスタイム ) # SRAM なら、これだけの話 DRAM の場合同じ所に読み書きを要求すると... 150ns 位待たされる ( サイクルタイム ) # DRAM の特性 プロセッサーの速度に対して、メモりの速度は、2 桁位遲い !! # 値段の安いメモりだと、もっと、遲い可能性がある !! 現在の計算機の問題点 プロセッサーだけ速くしても、メモりが遲いとシステム全体としては速くならない !! => メモリ遅延 # 昔は、CPU よりメモりが速かった時代もあったのだが.. CPU の速度向上に比較して、メモりの速度向上は、それほどでない # 逆転後、その差は広がるばかり.. # どの様にして、CPU の速度とメモりの速度の差を埋めるか ?? # 工夫(その内) ◯ メモりのバンク化 (インターリーブ化) メモりのシステムを二つに分ける 連続してアクセスする場合、その二つのデータを交互に読むようにすれば、異るシステムなので、それぞれ 50ns でアクセスできる => メモりを複数枚ずつ収める ( バンク変化 ) # 現在は、一枚のメモりボード内が既にバンク化 => バンク化が上手く行くためには、複数のバンクを利用しないと駄目 # プログラムの仕組によって、同じバンクを使うと遅くなる # 計算機の高速化の技術 # 半導体を速くすれば、常に速くなる # 上記のテクニックは、ある仮定をおいてあって、その仮定が成立しないだめ ◯ キャッシュメモリ ( 隠しメモリ ) # 最初に導入されたのは IBM 360/61 : 30 年前位のシステム CPU のカタログの中に、最近は必ずのっているのが、キャッシュサイズ # 記憶装置の属性 : 容量と速度は、反比例する ## この属性を満さないメモりは、淘汰されてしまう !! # Memory : 10^(-7) sec, 1 G byte # HD : 10^(-3) sec, 100M byte (1 T でもよさそう..) ## SRAM ( 10ns - 20ns ) ## CPU : SRAM : DRAM = 1 : 10 : 100 CPU と (DRAM) メモリの間に、少し速い(SRAM) メモりを入れる (この SRAM メモりが..) キャッシュメモり => DRAM メモりは、メインメモリと呼ぶ SRAM 上に DRAM の内容の一部の Copy を作っておく 同じ内容であれば、DRAM にアクセスせずに SRAM (上の Copy への)アクセスだけですむ => 理想では 10 倍くらい速くアクセス可能 !! # 小さいプログラムなどは、すっかりキャッシュに入る 大量データを扱うようなプログラムでは、データ側がキャッシュには入りきらないので、性能が出ない cf. 行列計算 このような場合は、SRAM と DRAM の内容の入れ換えが頻繁に生じるので、全然、性能がでない。 普段の計算では、だいたい、データもキャッシュに入るものなので、十分な性能がでる ◯ キャッシュと、連続アクセス 連続アクセス : 一度、アドレスを指定した後、その次のアドレスのデータを(データにアクセスしなくても..)自動的にキャッシュに Copy してしまう仕組 最初のデータのアクセスでは、100n かかる ( これは避けられない ) が その次ぎからは ( 初めてのアクセスなのに、キャッシュに入っているので.. ) 10ns でアクセスできる # 「メモリは、連続してアクセスされる」というメモりの使用方法(局所性)に関する「特殊な仮定」に基く技術 !! => プログラムを工夫すれば、メモりアクセスの局所性を最大限にすることもできる # キャッシュは Read の時はなんら問題ない : wirte の時は工夫が必要 キャッシュのコーヒレンシー(メモリとの同期)の問題 単純に write を行うと、キャッシュに反映されない => メインメモリとの間に矛盾がしょうじる => どこかで、キャッシュからメモりに書き出す必要がある weite back # write の仕組は色々ある => BIOS で設定可能 コードは、read しかないので、キャッシュが完全に上手くゆく データは r/w があるので、write back の問題を考える必要がある 特性が異るので、同じ仕組で実現するのは望ましくない 最近は、命令キャッシュ( I-Cache ) とデータキャッシュ ( D-Cache ) を分けていることが多い。 # 福井先生はキャッシュが嫌い # 自分でコントロールできない # 計算機によって、キャッシュサイズが異る # 色々な工夫をしても、あまり上手く行かない 例 : 大きな行列を行方向と列方向で零クリアすると速度 2, 3 倍違う C と Fortran では、添字の進方向が違うので同じアルゴリズムでも速度が異る => 興味がある人はやってみる # キャッシュが溢れるサイズじゃないと意味がない ## 今の PC では、時間計測が msec しか 最近の高速化技術の傾向 仮定が成立しないと速くならないことが多い => 投機的実行 # 「投資的実行」にすべきじゃ.. ## 費すコストが無駄にならないようにすべきでしょう !! # if 文の then と else を同時に実行してしまい、後で、条件で分岐 # => 成立しなかった方の計算結果を捨ててしまう ( 投機的 ) # => 条件が成立していないのでエラーになる可能性もある ◯ パイプライン 例 : 石油の輸送 油田で採掘した石油をパイプに入れる 入れ初めてから暫くはでないが.. 一旦出始めると、あとは連続で.. # あたかも、採掘したものが直ぐでる 計算機の中のパイプライン 一つの命令を複数のステップに分割し、ステップ毎に(同時に..)異る計算を行う => 時間的並列 ( <=> 空間的な並列処理 : CPU が二台ある場合など.. ) 例 : 浮動小数点の加算 ( a = b + c ) => 結構色々なステップがある データの取り出し 指数合せ 加算 丸め 個々の作業は回路的には別の形で実現されている 一つの計算で、一つ目の回路が使い終り二つ目回路を使い始めたら.. 二つ目の計算で一つ目の回路をつかっても構わない.. (同じ計算を繰り返し行うとすると..) 一つ目の命令の実行は、時間がかかるが.. 二つ目以降の命令の実行は、直に終るかのように見える !! => パイプライン パイプライン前 ( 三段 ) 一つ目の命令 １２３ 二つ目の命令 １２３ 三つ目の命令 １２３ 四つ目の命令 １２３ パイプライン後 ( 三段 ) 一つ目の命令 １２３ 二つ目の命令 １２３ 三つ目の命令 １２３ 四つ目の命令 １２３ # 三段のパイプラインだと、事実上三倍になる # 今の仕組だと最大 20 段位にもなっている !! 行列演算みたいに、同じ命令を何度も繰り返す場合は上手く働く if 文などがあると、だめ コンパイラが命令を並び換えて、上手く行くように工夫している # 上手く行く時には上手く行くが.. (投機的) # 空間並列の話は、12 頃に... == [まとめ] 前回の復習 ( ノイマン型 ) 計算機を高速化する仕組 データバンク キャッシュ パインプライン # 演習でやる計算の場合は、データサイズが小さいので上記のような仕組は関係ない # => 仕事でやる場合は、上記の仕組が問題になる ## 1 week が 1 day になるのは大変重要 ## 1 week もたつと、「何をしていたか人間が忘れてしまう」 !! 「理想な計算機」は、「どんな場合も速くなる」こと 実際は、「仮定が成立しないと速くならない計算機」 # 将来は.. ? 2010 年位は CMOS だろうが、その後は.. ? # 3 年後はまあ、わかる、10 年後は、何がおきているか解らない..50 年立つと.. 来週から、演習を行う 演習は、原則として、演習室で.. あぶれたら考える