小学校の算数で習う円周率や四捨五入でさえも結構難しいものなのですが、実際の世界では当然のようにもっと複雑な問題があります。
研究室で本当のサイエンスのテーマとして扱われる物には、我々の生活とはあまり関係がないようなものも多いのですが、逆に複雑な問題でありながら私たちの生活になくてはならないものもあります。
先日お話ししましたパソコンのハードディスクを例に取ってみましょう。基板の実装面が見える状態ならば、数多くの部品が基板上にはんだ付けされているのが分かると思います。たいていは、表面実装の部品の小ささに気を取られますが、いくつかのLSI部品も同時に見える筈です。
製品によって異なりますが、最近のハードディスクの場合なら、一つのLSIチップに数百万から数千万ものトランジスターが搭載されています。
論理回路の最小単位は論理セルと呼ばれ、数個から数十個のトランジスターによって構成されます。それぞれの論理セルには複数の端子があり、別の論理セルと相互に接続されます。接続する為の配線は短いほど遅延が少なくなり、LSIの性能を向上させる事ができますから、できるだけ接続関係のある論理セルは近くに配置してやらなければなりません。
メモリーセルのような、同じ形で同じ機能のものを規則正しく並べるなら良いのですが、各々違う機能を持つ論理セルの場合は、そう簡単に並べる事はできません。
数学的には巡回セールスマン問題と言う、セールスマンが複数の都市を巡回するのに最短経路を見つける古典的な類似の問題がありますが、これまでに1万数千の都市までしか数式による解法は得られていません。
計算しなければならない対象が増えると共に、計算量が指数関数的に増える為、計算で求める事ができないとされています。このような問題を、NP完全問題と呼びます。
このような場合、数式による計算によって求める事はできず、ヒューリスティックな解法、つまりいろいろ場当たり的に試しては評価して、満足できる答えなら採択する、駄目ならもう一度やり直すといった方法を取ります。
ただ、いろいろ試すといっても、行き当たりばったりではいつまでも良い結果は出ませんから、早く収束するアルゴリズムを使う必要があります。
LSIの論理セルを配置する時に使われるアルゴリズムの一つに、シミュレーテッド・アニーリングがあります。擬似的焼きなましとでも言いましょうか。
固体の温度を融けるまで上げて分子に運動エネルギーを十分に与え、自由に移動させてから徐々に温度を下げる事によって、分子を安定した状態で再凝固させるのです。論理セル同士の接続の長さをポテンシャルとして定義してやれば、自然とポテンシャルの低い安定した位置に収まってくるという訳です。
ただ、最適解に落ち着くのが理想なのですが、極小解にはまってしまう事があり、しかも悪い事にどれが最適解か誰にも分からないので、何度も何度も繰り返してみて、少しでも最適解に近づけようと努力します。
このようにパソコンのハードディスクの部品一つ一つが、苦労を伴いながら設計されて行くのです。
そこで一言。
計算で答えが出てくるうちは、計算を楽しんでやろうじゃないか、小学生諸君！ （でも計算は面倒くさいね！おじさんも嫌いだよ。）