月: 2003年6月

モンテカルロ法がどのようなものであるかは、ここに分かりやすい説明があります。

この中に、モンテカルロ法を使った円周率πの求め方が紹介されていますが、ここで大切なのは、ランダムに発生させた事象を評価して、採択するか棄却するかを決めている事です。

LSIの論理セルも、これと似たような方法で配置を求めていきます。まず最初に、全くランダムにすべてのセルをLSI上にばら撒きます。次に1つの論理セルに注目して、他の論理セルと交換した場合の評価を行います。改善されれば採択、されなければ棄却します。評価は、仮想配線長が短くなるかどうかで判断します。これを満足できる結果が出るまで、延々と繰り返すのです。

この方法には、二つの欠点があります。一つ目は膨大な量の計算をしなければならない事です。特に大規模なLSIになればなるほど、指数関数的に計算量が増えますから、常識的な時間内で結果が得られるように考慮しなければなりません。

二つ目は、前にも述べましたが、最適解ではなく極小解に陥りやすい事です。いったん極小解に陥ると、そこから抜け出すには大きなエネルギーが必要になります。そしてどの極小解に陥るかは、初期条件に大きく影響されます。最適解が求まらないまでも、より良い極小解を導く為には、優れた初期条件を与えてやる事が重要です。

この事を、文学的に表現すると、次のようになります。

一つの最適解と無数の極小解が、広がりを持った空間に漂っています。一つの極小解を見つけた人は、さもそれが最適解だと信じて喜ぶのですが、すぐに別のもっと良い解がある事に気づくと、今度はその新しい解を最適解と信じるのです。そして、それを幾度となく繰り返すうちに最適解の存在さえ疑うようになり、もはや本当の答えを追求する事を諦めてしまうのです。

NP完全の話は、おそらくあまりピンとこないと思いますので、もう少し分かりやすく説明できるか挑戦してみたいと思います。

LSIの中でも論理LSIはメモリーと異なり、設計の段階で複数のトランジスターから構成される論理セル（ANDやOR等の基本ブロック）を、如何に平面的なシリコンウェハー上に配置し、如何に相互間を配線するかが重要です。

配線が長くなると信号遅延が増大するため、動作周波数（クロック速度）に制限を与えてしまいます。できるだけ配線長を短くするためには、まず論理セルの配置が適切に行われていなければなりません。

各論理セルには、それぞれ信号の入力と出力の為の端子があり、たとえば3入力のANDの場合は、3つの入力端子と1つの出力端子があります。

出力信号は、ほとんどの場合同時に複数の論理セルに接続され、多い物では100以上もの論理セルと接続されます。これらの論理セルを、すべての接続を最短にするように配置する事は、容易ではありません。

分かりやすくなるかどうか分かりませんが、別の例で考えてみましょう。

今、40人の生徒がいるクラスの席替えをしようとしています。できるだけ生徒全員が満足する席の配置を目指します。

仲が良い3人の友達と一緒になりたいという生徒がいたり、5人と仲がよい生徒がいたり、クラス全員の人気者がいたり、いろいろな条件がありそうです。

さらに、勉強したいから一番前で先生の話がよく聞こえる席が良いという生徒がいたり、先生から目が届かない席に行きたがる生徒がいたり、憧れの異性の側に行きたがる生徒がいたり、それぞれ異なった要求が出てきます。

問題は、ある一人の生徒を満足させるだけなら簡単なのですが、それが他の生徒を満足させるとは限らないと言うことです。LSIの場合は、生徒が数百万人いる教室の席替えをするようなものですから、あまり関わりたいとは思いませんね。

まだ問題の難しさがよくわからんとおっしゃる方がおられたら、こんな例は如何でしょうか？

家系図は、先祖から子孫への系譜を示す物ですから、だんだんと末広がりにわかりやすいように書いていますが、実際は先祖にたどっていく方向にも広がって行くわけです。

つまりすべての親から子、子から親の関係を図示し、数百万人分の系図を一枚の紙に書くのと同じ作業だと言えば、そう簡単ではないのが分かるのではないでしょうか。

話をLSIに戻します。ある一つの論理セルAの出力が、別の論理セルB、C、Dの入力に接続されており、論理セルBの出力は、別の論理セルE、F、Gの入力に接続されている。これを数百万個のセルに対して繰り返すのです。

初めから決まったルールや解法がないので、乱数を発生させながらヒューリスティックな方法で最適解を探して行きます。このような方法を、一般にギャンブルに例え、モンテカルロ法と呼んでいます。

さて、問題の複雑さを理解していただけたでしょうか？何かごちゃごちゃしていると感じて頂ければ十分です。

次回は、モンテカルロ法についてです。

そろそろ、夏休みの旅行の計画を立てる時期になりました。SARSも取りあえず一段落しそうですので、海外旅行に久しぶりに行こうとしておられる方も、いらっしゃるのではないでしょうか？

ところで、みなさんは飛行機に乗られるとき、窓側と通路側のどちらを希望されますか？窓側は、景色が見られる反面、トイレに行くときに気を使いますし、通路側はトイレに行きやすい反面、内側の人が通る時に立たなければなりませんし、景色もあまり見ることができません。

家族旅行などでは、身内ですからあまり気にしなくても良いのですが、一人で乗るときには、座席の場所は特に気になるでしょう。

ＤＣ１０型機の中央席は、5列が並んでいますので、その真ん中に座らされたらきついです。その代わり、同じＤＣ１０の窓側席は2列ですので、窓側からでも比較的楽に通路に出られますから、同じ飛行機でも天国と地獄です。

ところで、非常口のすぐ後ろの席は、足下が広くて、離着陸時にスチュアーデスさんとお話ができると言うことで人気がありますが、ある時席に着いたら何と目の前についたてがあり、すごく閉塞感があったことがあります。

私は、トイレを我慢してまでも景色を見たいたちですので、いつも窓側を指定するのですが、ある時US国内線でチェックインの時に、窓側をリクエストしたら、「全部窓側で且つ通路側だ！」と言われたことがあります。

聞き違えたと思っていたのですが、搭乗したのは確かに通路を挟んで1列ずつ、サーブ製のプロペラ機です。エアーと書かれたノブを引くと、直接外が見えます。

当然タラップのひもを引っ張ってドアを閉めたのはパイロット、愛想笑いを振りまいて操縦席に着きます。

まあ、マイクロバスに乗っていると思えば何と言うことはありませんし、機体との一体感があっておもしろいといえばおもしろいかもしれません。

着陸は明らかに機首を下げて、滑走路に突っ込んで行く感じがたまりません。預けた荷物は、降りたところで受け取れます。

気流の関係で揺れるときは半端ではありませんから、大きく揺れた経験がある人は二度と乗ることはないようです。

地方の都市に行くとき、飛行機のチェックインで窓側か通路側か聞いてくれないときは、覚悟をした方がよいかもしれません。

小学校の算数で習う円周率や四捨五入でさえも結構難しいものなのですが、実際の世界では当然のようにもっと複雑な問題があります。

研究室で本当のサイエンスのテーマとして扱われる物には、我々の生活とはあまり関係がないようなものも多いのですが、逆に複雑な問題でありながら私たちの生活になくてはならないものもあります。

先日お話ししましたパソコンのハードディスクを例に取ってみましょう。基板の実装面が見える状態ならば、数多くの部品が基板上にはんだ付けされているのが分かると思います。たいていは、表面実装の部品の小ささに気を取られますが、いくつかのLSI部品も同時に見える筈です。

製品によって異なりますが、最近のハードディスクの場合なら、一つのLSIチップに数百万から数千万ものトランジスターが搭載されています。

論理回路の最小単位は論理セルと呼ばれ、数個から数十個のトランジスターによって構成されます。それぞれの論理セルには複数の端子があり、別の論理セルと相互に接続されます。接続する為の配線は短いほど遅延が少なくなり、LSIの性能を向上させる事ができますから、できるだけ接続関係のある論理セルは近くに配置してやらなければなりません。

メモリーセルのような、同じ形で同じ機能のものを規則正しく並べるなら良いのですが、各々違う機能を持つ論理セルの場合は、そう簡単に並べる事はできません。

数学的には巡回セールスマン問題と言う、セールスマンが複数の都市を巡回するのに最短経路を見つける古典的な類似の問題がありますが、これまでに1万数千の都市までしか数式による解法は得られていません。

計算しなければならない対象が増えると共に、計算量が指数関数的に増える為、計算で求める事ができないとされています。このような問題を、NP完全問題と呼びます。

このような場合、数式による計算によって求める事はできず、ヒューリスティックな解法、つまりいろいろ場当たり的に試しては評価して、満足できる答えなら採択する、駄目ならもう一度やり直すといった方法を取ります。

ただ、いろいろ試すといっても、行き当たりばったりではいつまでも良い結果は出ませんから、早く収束するアルゴリズムを使う必要があります。

LSIの論理セルを配置する時に使われるアルゴリズムの一つに、シミュレーテッド・アニーリングがあります。擬似的焼きなましとでも言いましょうか。

固体の温度を融けるまで上げて分子に運動エネルギーを十分に与え、自由に移動させてから徐々に温度を下げる事によって、分子を安定した状態で再凝固させるのです。論理セル同士の接続の長さをポテンシャルとして定義してやれば、自然とポテンシャルの低い安定した位置に収まってくるという訳です。

ただ、最適解に落ち着くのが理想なのですが、極小解にはまってしまう事があり、しかも悪い事にどれが最適解か誰にも分からないので、何度も何度も繰り返してみて、少しでも最適解に近づけようと努力します。

このようにパソコンのハードディスクの部品一つ一つが、苦労を伴いながら設計されて行くのです。

そこで一言。

計算で答えが出てくるうちは、計算を楽しんでやろうじゃないか、小学生諸君！　（でも計算は面倒くさいね！おじさんも嫌いだよ。）

今日は、四捨五入のお話です。わざわざ説明するまでもありませんが、小学校で習って以来慣れ親しんできた、数字を丸める為の手法の一つです。

ある数字の桁に注目して、4以下なら切り捨て、5以上なら切り上げます。そうすると近いほうの切りの良い数字になりますから、その後の数字の扱いが楽になります。切り捨てる場合と切り上げる場合がありますから、一見最終結果に悪い影響を与える事はなさそうに思えます。

今、90から100までの数字が並んでいます。１の位を四捨五入するとき、四捨五入する前と後で、合計に変化があるかどうかを調べてみましょう。

90 → 90

91 → 90

92 → 90

93 → 90

94 → 90

95 → 100

96 → 100

97 → 100

98 → 100

99 → 100

100 → 100

四捨五入する前の合計は、1045、四捨五入した後の数字の合計は、1050です。

0から9までの数字で、0は切り上げも切り捨ても行われませんから、残りの1から9までの9つの数字で数の増減が起こります。1から4の切り捨ては9から6の切り上げに対応しますが、5を切り上げているのに対応する切り捨てがありません。切り捨てを4回、切り上げを5回行ったので、増加しているのです。

95を切り上げた時の5が合計の増加分になります。1の位の数字に0から9までの数字が出る確率が同じだとすれば、切り上げが必ず多く発生します。

また数字の取り方が5刻みの場合で、(79.5, 80.5,
68.0, 92.5, 84.0)のような場合に、下1桁を四捨五入した場合は、切り捨てがなく切り上げしか行われませんから、明らかに大きくなってしまい結果の妥当性に疑問が生じます。

そこで、5以外はこれまで通りに切り捨て・切り上げを行い、５の場合のみ50％の確率で起こる事によって切り上げるか切り捨てるかを選択する方法が考えられます。例えば、その一つ上の位の数字が奇数なら切り上げ、偶数なら切り捨てるなどの方法があります。（この方法では結果が偶数になりますから、後から2で割る場合などに有効です。）

このように数字を丸める方法を、四捨六入と呼び、測定値の計算などで広く使われています。必ず0から9までの数字が同じ確率で登場するとは限りませんし、母数の分布も傾向があるなど、その場合に応じた方法を採る必要がありますが、四捨五入には結果を少し大きく見せる傾向があるという事は、知っておく必要があります。

数字は一度結果が出てしまうと、途中の計算過程で何が起こっていたかが分からなくなるので、常に計算方法の妥当性に気を配りたいものです。