エントリー

2010年08月の記事は以下のとおりです。

コンピュータ基礎の基礎~仮想マシン支援機構

  • 2010/08/05 18:14
  • カテゴリー:備忘録

 コンピュータ基礎の基礎,今日が一応の最終回という事で,仮想マシンについてとりあげます。

 コンピュータのハードウェアにはCPU,メモリ,I/Oがあって,その上でソフトウェアは動いています。では,そのソフトウェアでCPUやメモリ,I/Oを記述し,ハードウェア上で仮想的に別のハードウェアを作り出して,その上で別のソフトウェアを動かすと,どんなメリットがあるでしょうか。

 かつて,大型の汎用機は,新機種に置き換わるときに,お客さんが使っているソフトウェアが使えなくなることが大問題でした。今のようにパッケージソフトなどなく,お客さんが自分の都合で作ったソフトばかりなわけですから,新機種がいかに魅力的であっても,苦労して作ったソフトが走ってくれなければ困ります。

 しかし,互換性の問題は,いつの時代も技術的な進歩の妨げになるものです。そこでコンピュータメーカーは,新機種上で旧機種を仮想的に作り出し,過去のソフトウェアはここで動かすことで,ユーザーの不安を取り除くことにしました。

 このように,過去の資産の継承という目的で登場したのが,仮想マシンという技術です。歴史的には随分と昔からある技術ですが,最近特に注目を集めているのは,高性能化するコンピュータを有効に利用するため1台のコンピュータを仮想的に複数台にし,台数を減らしてコストを削減したり,資産継承ではなく異なるOSを走らせて各々得意とするアプリケーションを走らせるなど,もう少し積極的な目的で使われる事が増えたからです。

 仮想マシンには,大きくわけて2つの方法があります。

 1つは,エミュレータに代表される方式で,ホストOS型と呼ばれるものです。その名の通り,実ハードウェア上にまず1つのOSが走っており,このOSの上で仮想マシンを実現するソフトウェアを走らせます。このOSをホストOSを言いますが,仮想マシンもこのホストOSの機能を使って作られます。

 もう1つは仮想マシンモニタ型というものです。ハードウェアとOSの間に,ハードウェアを仮想マシンモニタというソフトウェアを1段挟みます。仮想マシンモニタはハードウェアを仮想化するもので,ここから上位レイヤーに対して,仮想化されたハードウェアを提供します。この上で複数のOSが走るわけですが,すべて別々の仮想マシンで動いているわけです。

 ホストOS方式は実装は楽ですし,仮想マシンがあたかもホストOSのアプリケーションのように見えるのでわかりやすく,またホストOSは仮想化されたハードウェアで動いているわけではないので,仮想マシンによって生まれる制約がありません。

 その代わり,ホストOSの提供するサービスによって実装されている仮想マシンは,競合するリソースや演算パワーを割り振るオーバーヘッドの影響が大きく,速度的にも信頼性の点でも今一歩です。

 これに対して,仮想マシンモニタ型の仮想マシンは,なにせハードウェアが直接見えず,あるのは複数の仮想マシンです。面倒なリソースの配分はこの仮想マシンモニタが行ってくれますし,それぞれの仮想マシンで動くOSはどれも対等な扱いです。それに,仮想マシンモニタがあるおかげでオーバーヘッドも小さく済みます。

 とはいえ,この仮想マシンモニタもソフトウェアなわけで,出来るだけ軽く作るのが望ましいです。そのために,ハードウェアの支援,とりわけCPUに仮想マシンモニタを支援するような機構を入れ込むことが,近年のCPUでは当たり前になっています。

 では,x86で仮想マシンを実現するのに,問題となっていることを見ていきます。

 まず,x86には,実行レベルという概念があります。リング0からリング3までの4段階があり,実行レベルが上がれば上がるほど,アクセス出来るリソースに制約が多くなってきます。OSやBIOSは最低レベルで動いて全てにアクセス出来ないといけませんが,アプリケーションが最上位で動いてくれると,万が一ソフトが暴走してもOSに動作を妨げたり,マシン全体に影響を与えるような動きを防いでくれます。

 この,レベルによってアクセス出来る範囲を変え,信頼性を高める技術をリングプロテクションと呼んでいますが,高度なOSを実装するには必須の機能の1つです。

 x86の場合,OSは全てのリソースにアクセス可能なリング0で実装されてきました。リング1や2はOSの一部が使い,最上位で最も制約の多いリング3はアプリケーションが使う事になっています。もしアプリケーションがOSの動きを妨げるようなレジスタを書き換えようとしたら,例外が発生して保護するようになっているわけですね。

 仮想マシンを実現する仮想マシンモニタを実装するには,OSよりも下位のリングで動かす必要がありますが,仮想マシンモニタをリング0で動かしてしまうと,OSはリング1や2で動かすことになってしまいます。
 
 しかし,OSは全てのリソースにアクセスしようとしますから,リング1や2でリング0でなければアクセス出来ないリソースをアクセスしてしまうと,例外が発生してしまいます。

 仮想マシンモニタは,この例外を受けると,その命令をエミュレートしてOSの代わりにレベル0でアクセスを代行し,結果をOSに渡してあげます。しかし,想像が付くようにこの方法はいちいち例外を監視し,命令のエミュレートを行うために,オーバーヘッドが大きくて速度が上がりません。

 別の問題もあります。

 x86はその名の通り,8086に端を発する歴史あるプロセッサです。互換性を維持してここまで来た驚異のプロセッサですが,これも簡単なことではなく,無理な建て増しを繰り返して,矛盾をギリギリの所で回避して成し遂げた産物です。

 例えばpopfという命令ですが,なんとリングレベルによって異なる動作をする命令だったりします。ということは,仮想マシンモニタの上で動いているOSが,リング0で動いているつもりで実行したpopf命令が,実はリング1や2で別の動作をすることが起きてしまうのです。

 この場合,悪いことに例外も発生してくれませんから,仮想マシンモニタはpopf命令がこないかどうか,常に監視する必要が生じるのです。これはさすがに足を引っ張りそうですね。

 ここ数年で用意されたx86の仮想マシン支援機能では,この問題を効果的に解決しています。まず,リング0からリング3まのリングをもう1つ用意し,それぞれVMXrootとVMXnon-rootと呼ぶようにしました。そして仮想マシンモニタをVMXrootで動作させ,OSをVMXnon-rootで動作させるのです。

 VMXnon-rootで動作するOSが,もし特権命令を実行したら,即座に処理をVMXrootに切り替え,仮想マシンモニタに制御を移します。VMXnon-rootのリング0では,リソースにアクセス出来ない代わりに,VMXrootで走っている仮想マシンモニタが動いてくれるわけですね。

 こうすると,例外によって処理を代行することもなく,またpopfをいちいち監視することもなく,オーバーヘッドを大幅に削減できることがおわかり頂けると思います。

 これに加えて,それぞれの独立した仮想マシンは,各々のコンテキストを保存しておかなければいけないのですが,その保存領域を専用に用意してあり,仮想マシンの切り替え時にはこれらの待避と復帰が自動で行われるようになっていて,これも大幅にオーバーヘッドを削減することに貢献しています。

 さらに,I/Oについても仮想マシンの支援の仕組みが考えられています。I/OとOSを繋ぐのはデバイスドライバですが,I/Oも仮想マシンモニタで管理されると,従来のデバイスドライバは当然使えません。またI/Oのエミュレータが仮想マシンモニタから提供されるようなものですので,非常に遅くなります。

 そこで,DMAのアドレスをハードウェアでリマップする機能を持たせてあります。こうすると,実際のI/Oデバイスのアドレスを直接仮想マシンに提供出来るようになるため,従来のデバイスドライバがそのまま利用出来るようになるばかりか,高速にアクセスが可能になってくれます。

 ただし,仮想マシンモニタが行ってくれていた排他制御はできなくなってしまいますので,ここはハードウェアによる排他制御が可能になるよう,PCIeの仕様が拡張されているので,これを用いることになっているそうです。


 さて,長々とコンピュータの基礎的な事項についてまとめを行って来ました。最終的には仮想マシンの支援機構までやってきましたが,ふと気が付くのは,従来は出来るだけハードウェアの規模を小さくして,その中で最大限の処理能力を出そうと言う目的で新しい技術が開発されてきたところが,最近では使う事の出来るトランジスタの数が膨大になり,処理能力を上げるためにどうやって回路規模を大きくするかを考えると言った,アプローチの違いがあるように感じます。

 例えばキャッシュメモリをたくさん積むことや,4コア,6コアという多数のコアを実装するマルチコアプロセッサなどは,その例だと思います。見方によってはインスタントで安易な高速化の方法が利用出来るようになるほど,トランジスタがふんだんに利用出来るようになったということでしょうか。

 しかし,喜んでばかりもいられません。微細化によってトランジスタの数が増えても,その微細化は消費電力の増大と発熱の問題を助長します。いつの時代も,こうしてバランスを取りながら,知恵と工夫でコンピュータの性能は上がり続けるのだと思うと,私などはワクワクしてしまいます。

 今後,どういう流れになっていくのでしょうか。特にマルチプロセッサの次に来るのは,いったいどういう技術でしょうか。楽しみです。

コンピュータ基礎の基礎~マルチプロセッサとマルチスレッド

  • 2010/08/03 17:00
  • カテゴリー:備忘録

 さて,今日はマルチプロセッサとマルチスレッドについてです。

 CPUは1980年代のRISCから1990年代のスーパースカラ,そして2000年代に入りマルチプロセッサに,その進化の方向が移ってきました。RISCはパイプラインとコンパイラ技術によって高速化をしようという試みでしたが,次にやってきたスーパースカラはソフトはそのまま変えずに,出来るだけハードウェアで並列な命令実行を行うものでした。CPU設計者が無茶な意地を張っていた時代です。

 そしてスーパースカラに限界が見えて,マルチプロセッサの時代になりますが,これはマルチプロセッサを前提にしたソフトウェアを作らなければ全く高速にはならず,その点でハードウェア設計者が再びソフトウェア設計者に頭を下げた,と言っていいかも知れません。

----

問題:
 ある問題について,その実行時間の95%は完全に並列処理が可能で,Nプロセッサを利用することによりN倍性能が向上する。しかし,残りの5%は全く並列処理を行うことが出来ない。この問題を10台のプロセッサを用いて並列処理を行った場合,1台で実行するのに比べて何倍高速に実行することが可能か?

----

 まず最初に,マルチプロセッサとアムダールの法則についてです。

 仕組みや構造はちょっと置いておいて,2つのプロセッサを用いると,処理時間は1/2になりそうなものです。とはいえ,人間でも同じですが,二人が手分けして仕事をしても,なかには手分けできない仕事もあります。こういうものはどちらかが処理するかありません。

 System360の設計者で,後に富士通と一緒にSystem360互換機をビジネスにするジーン・アムダールは,プロセッサの数と同時実行不可能な命令の割合から,最終的な処理速度がどれくらい高速化されるかを公式にしました。これがアムダールの法則です。

 プロセッサの数をNとし,同時に実行出来ない命令の処理時間の割合をFとします。

 まず,Fが0,つまり全ての命令が同時に実行出来るという状態を考えると,プロセッサの数が1の時に比べて,1/Nの時間で処理が終わります。

 逆に,Fが1,つまり全ての命令が同時に実行出来ないという状態を考えると,プロセッサの数であるNに全く関係なく,1つのプロセッサで処理せねばなりませんから,プロセッサの数が1のと同じ処理時間,つまり1倍となります。

 では,Fが0.5,つまり半分は同時に実行出来る場合はどうなるかです。Nに関係なく,絶対にかかってしまう処理時間は0.5です。残りの0.5は1/Nになりますね。もしプロセッサが2つだったら,0.5+0.5*1/2で,0.75です。プロセッサが1つの時に比べて0.75の時間で処理が終わるということになります。

 さて,一般化しましょう。プロセッサが1つ時に比べて,どのくらいの処理時間がかかるのかは,

 F + ((1-F) / N)

 ですね。何倍高速,と言う言い方にするには,これの逆数をとればよいです。

 では,この式を使って早速問題を解いてみましょう。

---
回答:
 全体の処理時間を1とすると,同時に実行出来ない時間は0.05,同時に実行出来る時間は0.95である。プロセッサの数が10であるから,プロセッサが1台の時の処理時間を1とすると,このシステムでは,

 0.05 + 0.95*1/10 = 0.145

 の時間で済むことになる。よって1/0.145=6.90倍高速に実行が可能である。
----

 アムダールの法則によると,プロセッサを10台も使い,しかも命令の並列性を95%まで高めても,7倍弱までしか速度が上がらないのです。なんだか割が合いませんが,プロセッサの数を2つに減らし,しかも命令の並列性が80%まで悪化していると,1.67倍にしかなりません。プロセッサの数を増やすことも大事ですが,実際には命令の並列性を高めることがもっと大切なのです。

 マルチプロセッサには,大きく分けて対象型と非対称型があります。例えば汎用CPUとDSPの組み合わせのように,プログラムを分け,それぞれのプロセッサの役割も決められているようなシステムは非対称型と言われますが,何せいろいろな方法がありますのできちんとした定義は難しいです。

 一方の対象型は,プログラムも役割も同一です。また共有しているメモリへのアクセスについても時間的空間的に平等です。その共有メモリについて,全てのメモリを同じアドレスで複数のプロセッサにアクセスが可能になっているものを集中共有メモリ方式といい,プロセッサごとにローカルメモリを持つものを分散共有メモリ方式と言います。

 言うまでもなく,同じメモリに全てのCPUがアクセス可能というのはプログラムを書くのが楽ですし,わかりやすいですからほとんどがこの方式といってもよいと思いますが,何分メモリが1つ,バスも1つですから,あるCPUがアクセスをしていたら,他のCPUは待たされてしまいます。処理速度がバスのせいで上がらないというわけです。おのずとCPUの数は制限を受けてしまいます。

 一方の分散共有メモリ方式は,命令の局所性をあてにして,バスを使わず自分だけのメモリをガンガンアクセス出来る仕組みですので,プロセッサの数はいくらでも増やすことが出来ます。

 しかし,他のCPUのローカルメモリにアクセスに行くには時間がかかってしまう傾向があります。これではマルチプロセッサでの高速処理が,メモリのアクセスでふっとんでしまいかねません。

 それぞれに一長一短がありますので,システムの規模やコストによって使い分けられています。

 ここでは,対象型の集中共有メモリ方式を例に考えていきます。

 バスとメモリを共有しているのですが,CPUごとにキャッシュメモリを置いてやると,バスやメモリへのアクセスが激減します。しかもキャッシュメモリはソフトウェアにはほとんど影響を与えません。これでマルチプロセッサは万々歳といいたいところなのですが,大きな問題があります。

 キャッシュというのは,メインメモリの一部を高速なメモリに蓄えておくものでした。メインメモリとキャッシュの内容が食い違うことが起こるので,これをどうやって解消するかという問題が,キャッシュでは重要なテーマの1つだったことを思い出して下さい。

 これがマルチプロセッサになると,さらに深刻です。なぜなら,自分の手元にあるキャッシュのアドレスを,他のプロセッサが変更しているかもしれず,その場合自分に変更の覚えがなくても,自分の手元のキャッシュの内容がメインメモリと食い違っていることがあるわけです。

 こうなるともうキャッシュの内容を信用できなくなってしまいます。さすがにまずいので,何らかの対策を取って,それぞれのCPUが持っているキャッシュの内容の一致をしなければなりません。これをキャッシュのコヒーレンシを保証するといいます。

 手段としてはいくつかありますが,ここではMESIプロトコルについて考えてみましょう。

 MESIプロトコルとは,

Modified
Exclusive
Shared
Invalid

 の頭文字を取ったものです。この4つはキャッシュメモリの状態を示すステートで,キャッシュのタグに書き込まれています。これらを持つステートマシンを考えます。4つのステートの状態を以下に示します。

M
 キャッシュメモリとメインメモリは不一致で,他のキャッシュメモリにはキャッシュされていない。

E
 キャッシュメモリとメインメモリは一致しており,他のキャッシュメモリにはキャッシュされていない。

S
キャッシュメモリとメインメモリは一致しており,しかも他のキャッシュメモリにもキャッシュされている。

I
 キャッシュメモリの内容が無効であることを示す。


 基本的には,Sのステートになるように制御がかかります。この制御を行うのが,メインメモリとキャッシュメモリの間に入る,スヌープコントローラです。スヌープとはのぞき見という意味だそうです。

 さて,2つのCPUが同じアドレスのデータをリードした場合を考えます。最初に1つ目のCPUがリードを行うと,1つ目のステートはIからEに遷移します。続いて2つ目のCPUのアクセスが起こると,1つ目のステートはEからSに遷移し,2つ目のステートはIからSになります。2つともSになっていますので,全てのデータが一致していますね。コヒーレンシは保たれています。

 ここでCPU1が書き込みを行ったとします。キャッシュの内容がメインメモリと不一致になりましたので,ステートはMに遷移します。同時に2つ目のステートはSからIになり,キャッシュを無効とします。無効になったのですから,1つ目のキャッシュの内容は2つ目のキャッシュにはキャッシュされていないことになり,Mで矛盾は生じません。

 そしてここでスヌープコントローラの出番です。スヌープコントローラは2つのキャッシュのステートがSになるように動きます。ここでは,1つ目のキャッシュの内容をメインメモリに書き出します。そしてそのデータを2つ目のキャッシュにも書きます。

 このことで2つのキャッシュとメインメモリの3つが全て一致しましたので,1つ目のキャッシュはMからSへ,2つ目のキャッシュのステートはIからSに遷移します。こうして,出来るだけSになるようにして,コヒーレンシを維持するのです。

 対象型のマルチプロセッサにおいては,CPUがいつアクセスを行ってそのデータが有効でなくてはなりません。しかしデータの保存場所がメインメモリだけではなく,それぞれのCPUのそばにも存在しているので,基本的には全てのデータが一致していないと,マルチプロセッサシステムとしては成り立ちません。


 さてさて,ここまででCPUの数は複数に出来ました。しかし前述の通り,複数の命令が同時に実行出来るようにしないと,CPUが同時に動いてはくれません。

 ぱっと思いつくのは,メモリ空間さえも独立しているプロセスを単位として,CPUに割り付けて同時実行することです。しかし,あくまでそのプロセスは1つのCPUで動いていますから,そのプロセスが重いときには,他の手の空いているCPUは手伝ってあげられません。

 かといってOSにはプロセスの中身を見て分割する機能まではありませんから,1つのプロセスを複数のCPUに割り当てることは不可能です。

 そこで,各プロセスの中に「ここは同時に動かしますよ」という印を付けることにします。

 こうして,同じプロセスの内で同時に動くのがスレッドです。同じプロセスですからそれぞれのスレッドは同じメモリ空間で動いています。

 実は,プロセスが情報の共有を行おうとすると,プロセス間通信などを行う事になりますが,これは結構オーバーヘッドも大きく,効率的とはいえません。しかしスレッドはメモリ空間が同じですから,グローバル変数で共有出来るので,とても高速で効率がよいのです。

 そして,わざわざ明示してくれた「同時に動かしますよ」と書かれたスレッドを,複数のCPUに割り当てるのです。どうですか,メモリは共有でグローバル変数で情報のやりとりが出来,同時実行可能とわざわざソフト屋が書いてくれているのです。

 ソフト屋さんとしては,これまで1つのプロセスを書いているつもりで済んでいたのが,どれとどれを同時に実行するかを考えて,スレッドという形で分割しないといけないことになりました。

 プロセスを分割してスレッドにする方法は,大きく分けて2つあります。1つはフォークジョインモデルで,文字通りソフト屋さんが同時実行可能な部分でスレッドと生成し,ソフト屋さんが設定した同期ポイントによってメインのスレッドと同期します。

 POSIXの場合,スレッドの生成はpthread_createで行います。こうして複数のスレッドが生成され,それぞれが同時実行される時に,CPUが複数あればスレッドをCPUに割り当てることで,処理能力を向上させることが出来るわけです。そして各スレッドの結果は,設定された同期ポイントで同期されます。

 しかし,いかにスレッドが軽いとはいえ,スレッドの生成や同期にはそれなりの時間も手間もかかります。スレッドに分割して複数CPUに割り当てて高速化出来ても,これらのオーバーヘッドで食いつぶしてしまうようだと意味がありませんから,スレッドとして同時実行される時間が十分に長い場合ことが条件です。

 もう1つはスレッドプールモデルと呼ばれます。これは複数のスレッドが定期的に実行されることが先に分かっている場合に有効な方法で,これら複数のスレッドをひとまとめにしたスレッドのプールを作成します。

 そして,このプールに情報を入力することで,複数のスレッドが動作して処理されていくのです。スレッドの生成をいちいち行いませんし,同期も頻繁に行いません。それにあらかじめスレッドをひとまとめにしておく関係で,各スレッドの対称性が高い,つまり似たような単位に区切って置けるということで,処理の効率が随分よくなります。


 ということで,例えばWEBブラウザでGoogle Chromeなどは1つのタブを1つのスレッドで処理しています。ですからCPUが増えれば増える程,同時に処理されるタブの数が増えるので,タブをたくさん立ち上げても処理速度が落ちません。また,タブの1つがエラーを出してこけても,スレッドという単位で独立していますから,そのタブが落ちて終わるだけです。(もちろんスレッドで共有されたメモリが壊されてしまえばプロセス,つまりアプリケーションが丸ごと落ちることもあります)

 しかし,CPUが1つしかない時には,スレッドの生成や同期に時間がかかってしまうので,そうした処理を行わない他のブラウザの方が軽くなることになります。そう考えると,マルチコアが当たり前になった昨今のパソコンを使い切るのが,Google Chromeということになりますね。

 そして,CPUの進化がマルチコアと言う方向に進んでいる現在,ソフトを書く上でもどことどこを同時に実行出来るか考え,それをスレッドという単位でまとめることがとても重要な技術になってきます。こうして半導体の進歩とソフトウェアの進歩は歩調を合わせることになり,コンピュータ全体の処理能力が高まっていくことになりました。どちらか一方だけではだめ,そんな時代が来たことを改めて感じます。

コンピュータ基礎の基礎~浮動小数点の扱いとIEEE754

  • 2010/08/02 20:17
  • カテゴリー:備忘録

 コンピュータ基礎の基礎,今回は浮動小数点演算です。

 一般に,我々がコンピュータを扱うときには,整数で表現が可能な演算が中心です。しかし,コンピュータが計算機である以上,小数点を扱う演算も日常的に起こります。

 Z80のように乗除算さえ持たないCPUを搭載した昔のパソコンでも,浮動小数点演算が出来た事を考えると,整数しか扱えないCPUも,プログラム次第で浮動小数点が扱えることになりますが,このように2進数で浮動小数点演算を行う場合には,その扱い方,つまりフォーマットが非常に重要です。

 かつては,この各社でバラバラだったフォーマットも,IEEE754という国際標準によって統一されており,データフォーマットの違いによるデータ互換のなさなど,不便な点が解消されてきました。

 まず,最初に,2進数で小数点の付いた数をどうやって表現するかです。

 思い出して欲しいのは,2進数というのは2になると桁が上がる数でした。一桁増えるごとに2倍になるのが2進数です。これはいいですね。

 10進法では,桁が増えるごとに10倍になるわけですが,では小数点から以下の桁はどうだったかというと,小数第一位が1/10,小数第二位が1/100と,桁が小さくなるごとに1/10ごとになっていきます。

 2進数でも同じ事で,小数第一位は1/2で0.5,小数第二位は1/4で0.25となっていきます。小数点以下が01なら0.25,10なら0.5,11なら0.75となるわけですね。

 では具体的に,小数点の付いた数を2進数で表現してみましょう。14.75を2進数で表現すると,まず小数点から上である14は1110です。次に小数点以下ですが,0.75から0.5を引き算すると0.25ですので,小数第一位と小数第二位の両方のビットが立ちます。

 よって,14.75は,2進数では1110.11となります。簡単ですね。

 浮動小数点というのは,小数点が動く表現方法です。先程の14.75は,1.475x10の-1乗,というわけですが,このうち1.475を仮数,10を基数,そして-1を指数といいます。これも基本ですね。

 問題はここから先です。この1110.11という0と1の列びを,どうやってメモリに格納するのかです。例えば小数点から上の1110の部分を何ビットで格納すればいいでしょうか。8ビット?10ビット?各社でバラバラだと,そのデータに互換性が出てこないのも頷けます。

 そこで1985年に制定された標準形式がIEEE754です。もう少し見ていきましょう。IEEE754のフォーマットは,以下のようになっています。

(1)基数は2で,基数はデータに含めない。
 基数というのは何の2乗とか3乗かを示す数字でした。IEEE754は2進数を扱うフォーマットですから,基数は2です。わかりきったことなのでいちいちこれをフォーマットには入れません,と言う意味です。

(2)仮数は1以上,2未満に揃える。これを正規化という。
 先程の14.75も,浮動小数点で表現すると1.475x10の-1乗となりました。このことで仮数部は10未満になります。IEEE754でも同じ事で,仮数部を1以上未満で扱う事にします。

(3)0の表現は,指数と仮数の全ビットをゼロにする。
 仮数部を0にすれば絶対にゼロなのですが,IEEE754では仮数部が0で指数部が最大になっているものを∞の表現に割り当てます。ゆえに全ビットゼロとしなければなりません。

(4)仮数も指数も2進数で表現する。
 これもまああたり前の話です。14は1110ですし,0.75は0.11です。

(5)MSBが符号ビットで,0が正,1が負を示す。
 当然正の数も負の数も扱いますので,符号ビットを考えておかねばなりません。MSB,つまり最上位のビットに符号の役割を与えます。

(6)単精度は32ビットで,符号1ビット,指数部8ビット,仮数部23ビットである。0から22ビットまでが仮数部,23から30ビットが指数部,31ビットが符号ビットである。
 IEEE754には単精度と倍精度の2つがありますが,このうち単精度は指数部を8ビット,仮数部を23ビットとしてあります。

(7)単精度の場合は,指数部は実際の指数に127を足し,仮数部は整数部分の1を省略する。
 正規化してあるので,仮数部は必ず1以上2未満になりますから,整数部分の1をわざわざ記述する必要がありません。また,指数部に足される127という数値をバイアス値と言います。バイアスを加えるのは,指数部が負の数を取ることがあるからです。

(8)倍精度は64ビットで,符号1ビット,指数部11ビット,仮数部が52ビットである。0から51ビットが仮数部,52から62ビットが指数部,63ビットが符号ビットである。

(9)倍精度の場合,指数部は実際の指数に1023を足し,仮数部は整数部分の1を省略する。


 ルールとしてはこんな感じです。

 では,2.5を単精度で表現してみましょう。

 まず,2.5を2進数で書きます。2は2進数で10,0.5は2進数で0.1ですから,10.1となります。

 これを正規化します。10.1x2^0ですから,これをシフトし,1.01x2^1とします。ここで,仮数部が1.01,指数部が1,そして基数が2となります。

 仮数部は整数部分を省略しますから,01となります。なお,基数2も省略します。また符号ビットは正ですので0です。

 仮数部は1になりますが,これにバイアス値である0x7fを足し,0x80とします。

 これらから,以下のようになります。

0 10000000 01000000000000000000000


 それでは次に0.1を倍精度で表現してみましょう。

 実はこの0.1をに2進数で正確に表現するのが不可能なのです。

 0.1ですから,0.5よりも,0.25よりも,0.125よりも小さいです。この段階で0.000まで確定です。

0.1-2^(-1)=-0.4  0.0
0.1-2^(-2)=-0.15  0.00
0.1-2^(-3)=-0.025  0.000

 さらにもうヒトケタ小さくしますと,0.0625です。ここでようやく1になり,0.0001です。しかし余りが0.0375でます。

0.1-2^(-4)=0.0375  0.0001

 余りである0.0375を使って以後計算します。

0.0375-2^(-5)=0.00625  0.00011
0.00625-2^(-6)=-0.009375  0.000110
0.00625-2^(-7)=-0.0015625  0.0001100
0.00625-2^(-8)=-0.00234375  0.00011001
0.00234375-2^(-9)=0.000390625  0.000110011
0.000390625-2^(-10)=-0.0005859375  0.0001100110
0.000390625-2^(-11)=-0.00009765625  0.00011001100
0.000390625-2^(-12)=0.000146484375  0.000110011001

 というわけで,ちゃんと証明したわけではありませんが,どうやら00110011・・・手な具合に循環していそうです。これでは永遠に割り切れることはないでしょう。つまり,0.1は2進数でちゃんと表現出来ないということになるのです。

 それはそれとして,先に進みましょう。0.0001100110011・・・を正規化します。1.100110011・・・x2^-4となります。よって仮数部は1.100110011・・・,指数部は-4です。

 指数部は倍精度の時には0x3ffをバイアスとして足します。すると指数部は0x3fbです。そう,指数部が負の数を取ることがあるから,バイアスを足すのでしたね。

 よって,64ビットで表現される倍精度フォーマットでは,以下のようになります。

0 01111111011 1001100110011001100110011001100110011001100110011001・・・

 一見するとこれいいように思いますが,実は循環する数字がそのままカットされているので,決まった範囲に数値が収まるように,丸めを行います。言ってみれば,3.14159・・・とせず,3.14と小数第2位までで表現するのと同じ事です。

 IEEE754では,4つの丸めが定義されています。

・最近接偶数丸め(RN)
 最も近くの表現できる値へ丸めます。基本的には0捨1入としますが,ちょうど中間の場合には,偶数になるよう,つまり仮数部の一番低位の数字が0になるようにします。誤差の蓄積もなく,もっともおすすめの方法です。

・0方向丸め(RZ)
 常に0に近い方に丸めます。いわゆる切り捨てです。

・+∞への丸め(RP)
 正の無限大に近い方に丸めます。

・-∞への丸め(RM)
 負の無限大に近い方に丸めます。

 さて,先程の数字ですが,標準では最近接偶数丸めを使います。入りきらなかった最初の数字は1ですので,これは0に丸めます。つまり,110011は,1000000に丸めます。よって,0.1は倍精度では,

0 01111111011 1001100110011001100110011001100110011001100110011010

 となります。


 この丸めによって,実は,10進数で0.0000000000000000055511151231257827021181583404541015625もの誤差を含んでいることになるわけですが,これがデジタルコンピュータの本質的な問題であるという事です。

ページ移動

  • ページ
  • 1
  • 2

ユーティリティ

2010年08月

1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 - - - -

検索

エントリー検索フォーム
キーワード

ユーザー

新着画像

新着エントリー

過去ログ

Feed