私がZ80用のμITRON仕様のRealTime-OSとしてHOS-80を、公開してから20年が経ちました。
以降、H8やARM用など多くの組み込みプロセッサと関わりつつ、HOSも多くのプロセッサに対応してきましたが、やがてFPGAと出会い、MIPS互換プロセッサとしてJelly を公開しました。当初はシリコンOSが視野にあったのですが、諸々の新しい気づきもあって、現在アプローチの方向性を変えて当ブログにて RealTime GPU の設計に取り組んでいる次第です。
さてここでリアルタイムコンピューティングについて考えてみたいと思います。
20世紀に入り、1936年にアラン・チューリングが、その論文「計算可能数について──決定問題への応用」の中で、いわゆる今のコンピューターが現実に作成可能であることを示しました（もっとも、数学的に計算するということを正しく定義したのが初めてであって、チャールズ・バベッジによって、１９世紀には既に階差機関・解析機関が作成・提案されていたことは良く知られる事実ではありますが）。
これらによって、数学的に定義された入力に対する出力を機械によって実施できることが示され、いわゆる計算機における「演算量」や「計算時間」というものが定義可能となりました。 クイックソートがO(N logN)の演算量オーダーだとか、NP完全問題がなどの議論が可能になったわけです（チューリングの意図は、「計算」とは何かの定義の試みなので、図らずもといった部分はありますが、とにもかくにも計算機を数学的に論ずることが可能になったわけです）。
しかしここにはまだ明確なリアルタイムの概念はありませんでした(ただし後の最悪実行時間(WCET)などの概念には非常に重要です）。
ジョン・フォン・ノイマンらによって、ENIAC が生み出され、シーモア・クレイによりCray-1が生み出されて以降、日本の京などに繋がるスーパーコンピューターの系譜も、基本的にはリアルタイム保証という概念はなく、沢山の「演算量」をこなせることを主眼に大規模なコンピューターへと進化してきました。
一方で、上記とは少し違う系譜で、リアルタイム制御分野へのコンピュータの適用も進んでまいりました。
おそらく世界最初のワンチップマイコンといってよいであろう 4004 は、日本のビジコン社とインテルの共同開発品です(日本の嶋正利さんなどはとても有名ですね)。
そして、やがて制御分野にマイコンが使われるという事が起こり始めます。
ただ、当初は自動車のインジェクションの燃料噴射"量"を計算するなどの、あくまで数式を解く目的で（つまり計算機としての従来どおりのまっとうな目的で）搭載されていたようです。
私の調べた範囲においては、本当の意味で "タイミング" の制御にマイコンが本格的に使われたのは、日産のECCSあたりからではなかろうかと思います。計算機科学自体が、なにかと欧米の後追い感の強い分野ではありますが、我が国がある程度は強い分野がリアルタイムコンピューティングと言っても良いのではないでしょうか？
少しジャンルを変えて、ゲーム機の歴史を調べてみると1972年のOdyssey(マグナボックス)、1975年のHOME-PONG(アタリ)あたりが先駆けですが、日本では任天堂のファミリーコンピューター(Nintendo Entertainment System)のヒットで一躍家庭に普及したコンピューターかと思います。
コントローラを操作するとインタラクティブに映像が動くというリアルタイムコンピューティングの基本の上に、CRTと同期させる光線銃などをはじめ、非常にわくわくさせてくれる応用アプリがあったのを記憶しております。これもリアルタイムシステムの一つかと思います。
私はZ80あたりから、コンピュータを始めましたが、当時はNOPを挟んでタイミングを取ったり、といったことが当たり前に行われておりました。キャッシュも分岐予測もありませんでしたので、命令表からサイクル数を数えて、ループの中でNOPを挟んでPWM波形を作ったり、ループ回数で時間を計ったりといったことが一般的に行われていました。
この当時、CPUは非常に貴重な１個のリソースでしたので、重要な１個のCPUをいつ、どの演算に割り当てるかというスケジューリングの問題はリアルタイム制御には欠かせず、CPUタイムのアロケーターである RealTime-OS は非常に重要なものでした。私はこの頃RealTime-OSに惹かれてどっぷり嵌っていたわけです。
さて、ここで一旦話を戻して、リアルタイムシステムとは何かについて復習しておきます。
まず、リアルタイムシステムでは時間軸に対して価値が定義できることが重要です。時間軸が無視できるコンピューティングの場合、結果が正しいかどうかが問われますが、リアルタイムシステムでは、結果が出る時間も非常に重要です。例えば自動車が衝突した後に、「ブレーキを掛けなさい」という計算結果が出ても手遅れなわけです。
普段あまり意識しないかも知れませんが、例えば10ms単位でタイムシェアリングシステム(TSS)でマルチタスクしているOSは人間には同時にタスクが動いているように見えますが、時速100kmで走る自動車にとっては、10msでも 27.8cm も移動する時間なのです。普通にPCを使っていても、最新鋭のCPUを使っていてすら、体感できるレベルでレスポンスが悪いと感じることはよくあると思いますが、実行時間を保証する計算機システムを作るのは意外に難しいことなのです。
リアルタイムシステムのよくある分類として、以下のようなものがあります(この絵も過去に何度も書いてきた気がします)。
すなわち狭義には、デッドラインが定義できるものがリアルタイムシステムと言う訳です。そしてデッドラインに間に合わなかった後に起こる価値関数の変化が、不連続か否かなどでクラス分けされていると言えます。これはフェールセーフ含めて、RealTime-OSのスケジュール優先度を決める上では非常に重要な概念です。
ただ、実際にはタイミング制御においては、時間軸に対して下記のようになるケースも多いと思います（この絵は今回始めて書きますが、例えばエンジンの点火タイミングなどを考えてみてください。早過ぎてもダメですよね）。
タイミングよく何かをするということは非常に重要です。この場合、価値関数に極大値があることが重要でして、結局のところ、時間軸に対する価値が最大化するように最大限の努力を払うコンピューティングシステムともいえるわけです。
ただ、計算が速すぎた場合に、計算結果の出力を遅らせるのはそれほど難しくは無いので、しばし計算機科学としては前者のハードリアルタイム～ソフトリアルタイムにクラス分けされて扱われます。
話を計算機アーキテクチャに戻します。NOPを挟んでタイミングをとるような技法が使えていた時代から、ムーアの法則でトランジスタ数は増加し、現在は下手すると有り余るトランジスタをどうやって休ませずに稼動させるかという別の悩みを持つ次元に来ました。nVidia社のTegraのようにHPC分野のコンピュータアーキテクチャをエッジコンピューティング(必然的に組み込み分野)に持ち込もうという動きもあり、リアルタイム制御分野で使えるリソースも大きく変わってきました。
しかしながら、単純にHPC分野の最新の成果を持ち込んだとしても、ここまでの話のようにHPC分野は決してリアルタイム分野に対するアーキテクチャ進化をしておりませんので、即座に高い効果が期待できない部分があります。GPUなどはゲーミングの歴史からある程度この分野への応用力は保持しているとは思えますが、主な市場がPCから出発している為、どうしてもPC用のデバイスやOSにアーキテクチャ制約を受けて進化してきており、組み込みリアルタイム制御の分野に最適なアーキテクチャとは言えない部分もあるのは否定できないと思います。
では、並列化時代のリアルタイムシステムの進むべき方向は何なのかという疑問に行き着きます。実際、「１個のCPUをいつどの演算に割り当てるか」という問題を超えて、どのトランジスタをどれだけどこに配置することで、「クリティカルパスとなる演算のWCETを短縮するか？」という問題が発生し始めております。
並列系においてトランジスタが好きなだけ使えるという仮定の下でリアルタイム問題を解く場合、スケジューリング問題ではなく、並列化アルゴリズムの時間方向の段数の圧縮の問題と、真の演算に関わる部分以外の計算機アーキテクチャに関わる時間(DMA転送など)の除去の問題に帰着してくると考えられます。
前者に関しては例えばソーティングネットワークのようなアルゴリズムの改善は多数提案されており、今後も問題領域ごとに様々な手法が生まれて来ると思われます。
個人的に興味深く思っているのは後者のコンピュータアーキテクチャに関わる部分です。リアルタイムコンピューティングにおいてそもそもノイマン・アーキテクチャ自体がボトルネックになる可能性を含んでいるからです。ノイマン型コンピュータは、基本的には記憶装置から記憶装置への転送に伴って演算を行います。mov命令やload/store命令のような転送だけで演算しない命令も存在します(もちろんスーパースカラで必死に裏に隠しますが)。
リアルタイムコンピューティングに適したアーキテクチャを考えた場合、入力から出力までに余計なものを挟まずに、最適化された演算器のみを On-The-Fly で通すのがもっとも最適化された形かと私は考えております。
On-The-Fly 演算とは何かというと、要するにメモリになるべくデータを貯めずに演算してしまうことです。アーキテクチャ的にはアナログコンピュータに近いものかもしれません。メモリは過去の事象を覚えておいてくれるので履歴として利用するには非常に便利なデバイスなのですが、遅延素子にもなりうるデバイスで、特に「処理しやすい単位でデータが揃うまで待つ」、「処理しやすいフォーマットにデータを並べ直す」など、処理の容易化の為に使ってしまうと、リアルタイム性のみに着目するとなんとかして排除したくなる部分になってきます。
演算器はデジタル演算器、履歴参照には膨大なメモリ、という現代半導体のメリットを最大限享受しつつ、基本データパスはアナログ時代並みに貫通させたアーキテクチャという、のが私の思い描いているアーキテクチャです。
こうなるとノイマン型向けのプログラムは困難になってくると予想されますので、例えばMATLAB-Simulink に代表されるようなのようなデータフロー型の演算モデル記述がフットしてくるようにも思います。
実行形態としても例えばプログラマブルとするなら、FPGAのようなデータフローを直接配置できるデバイスが向いているのかも知れません。
一方でこの分野は、例えば、新しい演算回路をクラウドのストアからエアダウンロードで買ってくるとか、利用量で課金するとか、そういったレベルのインフラはまったく整っていません。そもそも普遍的に実行体を記述できる共通言語や中間言語すら整備できておりません。
逆にこれらが整ってくれば、パソコンやゲーム機の画面の外、まさにリアルな時空間の中に真のリアルタイムコンピューティングが普及してくる可能性もあります。
少なくとも私は、攻殻機動隊とか電脳コイルのような世界観の実現には現在のコンピュータアーキテクチャにブレークスルーを与える進歩が必要と考えています。鉄腕アトムに始まって、様々なSFやアニメのような、本当の生活空間でコンピュータが活躍する時代を夢想する今日この頃であります。
かつて、GRAPEというスーパーコンピュータが東京大学で重力多体問題を解くという目的のために、わずか20万円の部材費で作成され、世界を驚かせたことがあるそうです。
私も長い期間リアルタイムコンピューティングに関わってきた人間ですので、リアルタイム性というただ一点でよいので、一度 Intel/AMD/nVidia に勝てるアーキテクチャにトライしてみたいと考えている次第です。
新しいコンピュータを創るというと、個人には夢みたいな話ですが、FPGAというデバイスは、LSIを起こさなくともアーキテクチャに関しては定量的に実現可能性を提示できるデバイスですので、GRAPEまでは行かなくとも、一石を投じることが出来ればと思い、無い知恵を絞っている次第です。
コメント