Ryuzのブログ

以前書いたように、作成中のリアルタイムGPUを用いた電脳メガネの作成を企て中です。

そこで電脳メガネの究極の目的は視覚のハッキングと以前書きましたが、視覚のハッキングとは何か、ということをもう少し考察しておこうと思います。

考察に先立って、人がものを見て認識するということは何か？そもそも認識の主体者である自我とは何か？ といったところから話をスタートしてみたいと思います。

少なくとも私は、私を私だと認識していて、今この文章を書いている自分のそれが自我がだと認識しています。ただ、他の人が自分を自分と認識しているかどうかは知る由も確める術もありません。なので、ここでは自分以外にも自我が存在し、それが他人だろうが、AIだろうが、自分を自分と認識する何か上がればそれは自我だという定義の元で、話を進めます。

　ここに、AさんとBさんの２つの自我としての意識が存在したとして、それぞれが現実空間の同じものを見たときに、その認識までが同じとは限りません。

　例えば赤いりんごがあったとして、その「赤」という部分の認識が、脳内で人それぞれ同じという保証は何も無いわけです。各認識がそれぞれ脳内でそれを「赤」として学習していれば、それは内部認識が異なってもなんの問題も無いわけです。実際には色だけではなく形の捕らえ方含めて視覚から入ってくるものだけでも実に様々な要素が様々な捕らえ方で人それぞれで異なる認知がなされていると思われます。

　この場合、現実世界(リアル)は、まったく異なる脳内認識をしているAさんとBさんのコミュニケーションとして中間言語として機能します。
　Aさんの認識の為の視神経の回路は、400nm～750nmの間の波長の分布を、Aさんの意識にとっての「赤」に現実世界で見たものを変換してくれます。そして外部に情報を発信する際に、共通言語としての「あか」という発音を声帯の筋肉を震わせることによって発します。Bさんも同様に現実世界の「あか」という発音を、Bさんの認識にとっての「赤」に変換して意識しているわけです。これは仮に自我をもったAIが発生しても同じことです。

　さて、こういった中で、リアルと意識との間にコンピューティングを介在させることが出来れば、現実世界以外に、AさんとBさんのコミュニケーション経路が作れるかもしれません。
　例えば、バーチャルな空間を作って、そこを現実世界の代替となる中間言語として機能させるわけです。例えばオンラインゲームの世界では、自分のアバターを操作して、オンラインで他者とコミュニケーションできる点でそういった要素も含んでいるかと思います（将来AIと会話する時代が来れば、別の意味でももっと重要かもしれません。）

　ただ、今回はもっとリアルに近いところでのハッキングを考えています。藤井直敬先生のSubstitutional Realityなどはかなりリアルに迫っていると思いますが、それでもまだリアルとARのシームレスなスイッチなので、もっと密結合したMixed Realityを考えてみたいと思います。

　ではいったい、現実世界と意識の間で、どこをハッキングすればそれが可能になるでしょうか？

　例えば、電脳コイルというアニメでは、メガネによって視覚の入り口で視野を自在に制御しています。攻殻機動隊のような世界観では、光学迷彩のような物理世界のハックから、作中でゴーストと呼んでいる意識界面ぎりぎりのハックまで多彩に存在します。

　現実でも脳とコンピュータを繋ぐ実験もあれば、夢を記録する装置までいろいろあり、脳内の認識の仕組みも解明は進んでいくと思われます。将来的には脳の中まで迫ったコンピューティングもできるかもしれません。ただ、そのあたりはデバイスの問題で私の専門ではないので接続方法は一旦置いておいて、計算機として純粋にこういった箇所に適用したときに耐えられるスペックとは何かを考えてみたいと思います。

　人間の５感の中で、もっとも人間が頼っている情報が視覚で、一説には情報量の8割を占めているとも言われます。
　また、人間が応答する上で、障害物を避けるなどで、リアルタイム性をもっとも必要とするのも視覚です。一方で、コンピューティングとして考えた場合、処理対象の情報が非常に多く、且つ、高い応答周波数を出すのが難しい領域でもあります。

　視覚のハッキングを行うのは、光に対する刺激が、意識に届くまでの過程のどこかに演算を差し込めれば良い訳ですが、現時点ではもっともやりやすい方法は情報が光であるうちに加工してしまうことでしょうか。

　光が光源をでて、桿体細胞/錐体細胞にて受光されるまでのどこかに処理を差し込めれば良い訳です。
　光源側に手を入れるのが、いわゆるリアルタイムプロジェクションマッピングの領域で、後者がリアルタイムヘッドマウントディスプレイになってくるわけです。前者については方々でそれなりの評価を頂きつつありますが、今回は後者に対する試みです。

　演算場所はデバイスに依存して変わっていくにせよ、コンピューティングとして画像処理を考えた場合、そこにリアルタイム性が必須です。
　この分野、リアルタイム画像処理といったときに、スループットとして、現実に合う帯域が出せれば「リアルタイム処理達成」と言ってしまうケースが多々あるので、ここで一度、真のリアルタイム処理の定義をしておきたいと思います。

　一般の画像処理は、TVが生まれた当初からのNTSC規格が60Hz程度で来たこともあり、16.6ms程度の処理速度をリアルタイムと言ってしまうことが多々あります。
　一方で、現実世界を考えた場合、ちょっとHMDをつけて首を振っただけで、16.6msあれば見たい対象は数ピクセル以上ずれてしまいます。これではMixed Realityは成り立ちません。

　これでは真のリアルタイム処理とはいえません。結局のところ画像処理したい対象の物理的なダイナミクスに対して、必要十分な応答周波数を出せるレスポンス性が無ければリアルタイム処理とは言えないと思います。
　必要な応答周波数は、シーンごとに変わってしますが、筆者の経験上、最低でも数ms程度、出来れば数百usオーダーの応答速度が出せれば現実世界と認識の間でシームレスな画像処理を用いた作用が可能になってきます。

　まずは、解像度とか画質とか、そういったパラメータは一旦置いておいてよいので、応答周波数の一点だけに絞って、限界点を確認しつつ、新しい世界を垣間見てみたいと思っている次第です。

　私が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までは行かなくとも、一石を投じることが出来ればと思い、無い知恵を絞っている次第です。

Spectre/Meltdown脆弱性が巷を賑わせているようです。
当初漠然とした情報が飛び交っていましたが、いろいろと詳細が出始めてきたようですが、改めて、「セキュアなCPUを作る」事と、「パフォーマンスの良いCPUを作る」事の間に乖離が大きいことを感じました。

下記に非常にわかりやすい記事を見つけて読んでみました。
http://milestone-of-se.nesuke.com/nw-advanced/nw-security/meltdown-spectre/

なるほど確かに立派にサイドチャネル攻撃が成立してますね。特にMeltdownの方はダイレクトにデータ読めてますね。恐ろしや。

バグの詳細や影響に関しては世の中に詳しい記事が多数あるので置いておいて、CPU設計の観点から考えてみたいと思います。

現在のOS上のコードは、アプリからOSのシステムコールを呼びながら実行されますので、１つのスレッドがユーザー空間とカーネル空間を往復しながら動きます。TSSやSMTによって同じコアで複数プロセスも動き得ます。したがってこれをパフォーマンス良く動かそうとすると、１つのCPUコアからアクセスされるキャッシュ上にさまざまなプロセスレベルのデータが混在して載ったまま、効率よくかつアクセス保護された状態で動くことが求められます。

一方で、キャッシュへのアクセスは、候補データのアクセスと、TLB/MMUなどへのアクセスは並行して進行しますので、現状アーキではデータ読み出し時点でそのデータにアクセス権があるかどうか知るすべが無く、ガードする手が無いわけです。

もちろん、アクセス権の確立を待って、データを利用する作りにすればよいわけですが、そんなことをすればCPUの性能が大幅に落ちるのが簡単に予想されます。「新CPUはセキュアになったけど、旧製品やライバル社より３倍遅くなりました！」では誰も買わないのは目に見えているので、根本対策は非常に難しいわけです。

現状の、「アクセス違反がわかったら、後からキャッシュを削除」という機構もそれ自体複雑怪奇な機構ですが、上記の事情からやむなく至った解なのだと思います。ただやはり根本的な対策では無く、サイドチャネル攻撃をやりにくくするジャミング的な対策だったわけで、今回のように思わぬ回避コードが出てきてしまったわけです。

もっと言うとサイドチャネル攻撃の根本的な原因は、リソースの共有にあります。ものすごく極端な例を挙げると、たとえばあるインターネットのショッピングサイトで、Web上で商品をカートに入れたり出したりを繰り返してその時間を計ったとします。もし他に誰もアクセスが無ければ非常に高速に画面は切り替わるでしょう。ここに他の誰かが何か商品を買うためにアクセスを開始すると同じサーバーの負荷が増えた分処理は遅くなるでしょう。

ほとんどバタフライ効果のような話になりますが、この遅れ具合は、何の商品を買ったかや、送り先の住所やクレジットカードの番号などのデータ内容などと相関を完全にゼロにすることは不可能です。相関がゼロで無い以上、多面的な方向からこういった相関のありそうな情報を集めまくって、統計的に他人の情報を推測できる可能性はゼロではありません。したがってリソースの共有を一切止めて、ユーザの数だけ個別に専用サーバーを置くなどしない限り、100%セキュアなサーバーを作るというのは出来ないわけです。

結局のところ、100%セキュアなサーバーはありえない前提の中で、「限りなく100%に近く、実用上は問題なレベルの安全性」をどう確保するか？ という議論に落ち着くしかなく、今後もそういう方向が続かざるを得ないだろうと思います。

話をCPUに戻しますと、現状に対して取れる策は、パフォーマンスを犠牲にしてでもある程度根本的な対策を行うか、パフォーマンス劣化の少ないジャミング処置を追加していくかしかないと思います。

回路設計で取れそうな対策を思いつく範囲で考えてみます。

  ・ キャッシュ上のデータにアクセス権もつけておいて、不正データは固定値や乱数に置き換える
     （ページテーブルについているアクセス権を全キャッシュラインにつけるのでbitが増えますね）
  ・ アクセス権の無い汚染されたデータに関わるアクセスをすべてロールバックする
     (とても大変な回路になりそうです)
  ・ アクセス権の無いアクセスを見つけたらその場でキャッシュを全フラッシュする
     (投機実行の不正アクセスは普通に起こる事象なのでパフォーマンスが大きく落ちます)
  ・コンテキストごとに別キャッシュを用意する
     (リソース膨大になりますね＆特権スイッチが重くなりますね)
  ・コンテキストごとにキーを変えて、ストア/ロードでデータを暗号化/複合化する
     (キャッシュ上のbitは増やさずに、違うコンテキストのデータが化けるようにする。でも確実にステージ増えますね。OSの対応も必須だし、コンテキスト間通信も大変)
  ・厳密な時計を提供するのを止める
     (解析の難易度を上げることができますが、正確なタイマの必要なアプリが困る)
  ・ランダムにキャッシュフラッシュやCPU停止を行い撹乱する
     （ただの嫌がらせですね。クラッカーも困るけど、普通のユーザーも困る）

とかでしょうか？私の頭ではイマイチな案しか思いつけません。

あとはOSや重要なデータを扱う専用のアプリ内での処理など、ソフトとあわせての検討で

  ・ そもそもこの方法でアクセスできるところに重要なデータを置かない
       （kernel page-table isolationなどですね）
  ・ 重要なデータがどのアドレスに存在するか推論しにくくする
       (配置をランダムにするとか、時々移動するとか、ASLRの類ですね)
  ・各種OSのスイッチなどのタイミングやランダムな時間でキャッシュをクリアする
     （全方位的ただの嫌がらせ、パート２）

などの対症療法でしょうか？

いずれにせよ、本当に大変そうです。

そうなってくると、最終的にはデータセンターのようなセキュア向けのCPUと、とにかく演算量が欲しいHPC向けとで、CPUが分化する可能性もあるのかもしれません。
今のGPGPUのような、完全な別デバイスに性能の欲しい計算だけをオフロードするのも有効な解に思います。

短期的には性能意落ちるパッチでの対処になると思いますので普通に不便になりそうですが、CPUの進化という意味では、今後どのような対策が出てくるのか、興味深いところです。

各種アルゴリズムの計算量はしばし重要な問題である。
またリアルタイムシステムや並列系の計算機(FPGAも含む)を考える場合、ワーストケースの検討も重要である。

例えばIn-placeアルゴリズムの中で最速に属するクイックソートのアルゴリズムは平均して O(n log n) の計算オーダーが期待できるが、単純な適用だとワーストケースでは O(n^2) である。

仮にソーティング専用の並列計算機構造を作る場合、ワーストケースにも耐えられるように構成する必要がある。

計算オーダーはしばしチューリングマシンのモデルを前提に語られて来た。
チューリングマシンはもともと有限の計算ユニットと、無限の長さのテープでの計算機モデルであるので、そのまま有限個数に固定された演算器と、解きたい問題に対して十分な量のメモリが存在する一般的な計算機の構成にそのまま対応づく。

この場合、演算に要する計算時間は、そのまま演算量のオーダーに対応づく。

しかしながら、並列計算機の構成そのものをアルゴリズムに対して設計できるケースでは話が少し変わってくる。

ここで、計算ユニットの方も、解きたい問題に対して十分な量を自由に割り当て可能として、答えを求めるのに必要な時間を考えてみる。

例えば n 個のデータの中から最大値を求めるアルゴリズムを考える。
言うまでもなく演算量は O(n) である。

ここで、計算ユニットが n より十分小さい有限個に固定されているいわゆる普通の計算機であれば、計算時間は n に対応づく。

しかしながら、比較器を n に対応づく個数割り当てることが出来れば、いわゆるトーナメント式に比較を行うことで 計算時間は log n に対応づく。

これは演算器が nに対応づく個数の並列計算機で単発の計算を行う場合は並列度の問題でもあり、アルゴリズムの前半では多くの演算器が稼動し、並列度は高く、後半では並列度が下がっていく。

また、n個のデータセットが m回入力され、最大値をm回求めるような計算を、スループット１で行うパイプライン計算機を設計する場合は、計算ユニットの個数にも関連する。
n log n に対応づく演算器の個数が必要であるが、この場合は演算ユニットはすべて100%稼動し、log n の時間の後に、毎サイクル結果が出力される(ただ残念ながらまだGPGPUなどはこのパイプライン演算での並列化は苦手なので、このあたりはまだまだFPGAなどの担当範囲と思われる)。

  各種アルゴリズムに置いて計算量のオーダーが示されることは多い。しかしながら、計算ユニットを任意個アサインできる前提の場合の、最悪計算時間のオーダー、その際の計算ユニットのオーダー、その計算ユニット数に対する並列度(稼働率)のオーダー、などはあまり示されることが無い。

  これらは専用計算機を設計する場合には従来までの非常に重要であったし、GPGPUなどの出現で「計算ユニットが n より十分小さい有限個に固定されている」という前提が崩れ始めている現状において非常に重要な課題と考える。

余談だが、少し先のソートの話をもう少し考察して見る。
最大値と最小値はトーナメント型の計算機構成で log n の計算時間で解ける。一方で、２番目とか３番目とかでは敗者復活戦が必要になり、演算時間が増えていき、中央値の探索で最悪値となる。

最大値と最小値以外の計算については、有名な「選択アルゴリズム」というのが存在する。
wikipedia によると、かのクヌース先生が下限としてにたようなことを記載されているようであるが、「この下限は k=2 のとき成り立つが、さらに大きな k ではもっと複雑な下限が存在する」とさらっと凄い事が書かれている。

選択的アルゴリズムもベースがクイックソートなので、一見すると計算量のワーストケースが O(n) ではなく O(n log n) になってしまうような気もしなくも無い。
が、「中央値の中央値」によって、O(n) の計算量で確実に中央一定比率の区画のピボットを選択が保証できるアルゴリズムが存在する。クイックソートもこのアルゴリズムとの併用で最悪時演算量を O(n log n) で保証できたりする。多くの従来型計算機のソフトウェア実装だとここまでやると逆に計算が遅くなるケースも多く、質の良い乱数でのピボット選択が重要になるようだが、系列系ではこの手の最悪値保証は重要である。

並列系では中央値の中央値は log n の計算時間であるにもかかわらず、nに対する固定比率で絞り込めるところが肝で、これを再帰的に行うことでオーダーを１ランク落とすことが出来る。

上記を加味すれば、並列系での中央値選択 は log n のオーダーの時間で達成できそうな気がする。
当然ながら、 log n のオーダーの時間でソーティングができる計算機構成が組めることになる。

データの数よりも演算器の数が多いということは最近では十分ありえる。
特に画像処理の場合、例えば 一定のフィルタサイズでメディアンフィルタとか、特徴量の上位数個の抜出とか、統計系の演算が発生するケースは十分あるが、GPUのコア数やFPGA化する場合の比較器の数とか、データ数より演算器が多く、このオーダーを達成できるケースは多々ある。

かつて、単調に増加していたCPUのクロック周波数は、ここ十数年4GHz前後でとどまり、代わりに計算並列度が飛躍的に向上している。
SIMDやマルチから始まり、メニーコアとなり、この先どこまで行くか分からない。
FPGAなども同様に多くの高度な演算を搭載できるようになってきたために、行き着くところは同じところに向かっている。

優れたアルゴリズムを考える場合、単に計算量や、消費メモリ量だけでなく、並列度という概念は改めて重要であるし、これらを扱える共通的な指標は今後まずます重要であると考える。

＜追記＞
　クイックソート的な回路を考える元気は無いので、ひとまず log n の時間でn個のデータのソートが可能かどうかだけ考察して見た。

　1.  n(n-1)個の演算器を用意してすべてのデータ同士の比較を行う[1サイクル]
      (同値のものは初期位置で優劣をつける)
  2.  各nの大小較結果をトーナメント型で数え上げる [log n サイクル]
  3.  数え上げた数を位置として結果メモリにストアする[1サイクル]

　1が既に馬鹿ソート感をかもし出していたり、メモリアクセスの問題はまあおいておいて、理屈としては出来そうだ。

　FPGAだと3の部分で巨大なセレクタが出来てしまい、1サイクルでは難しいが、セレクタを log n サイクルで組んでもオーダーは変わらない。中央値などのk番目要素が欲しいだけならただのマルチプレクサである。
  後は 1を工夫して、log n 掛かって良いので、演算器数を圧縮できれば良いわけであるが、2と組み合わせて最適化が必要だろうなぁ。
  実用的なところで効率の良いメディアンフィルタとか作れたら面白いかなと思う今日この頃。
  画像処理の場合スループット１というケースが多いので、単純選択ソートだと n^2 のオーダーの比較器を並べることになるので、ある程度フィルタサイズが大きくなってくると工夫の余地が多数出てきそうな気がする。

ふと表題のようなお馬鹿なことを考えてみた。

ロードストア命令や分岐命令は普通にあり、レジスタも例えば32bit汎用レジスタが16本とか普通にあるが、なぜか算術演算だけはNANDしかないというプロセッサだ。

算術命令は任意のレジスタの任意のビットを２つ指定して、任意のレジスタの任意のビットに書き出す命令のみとする。

当然、NANDは万能なので一応は一通り何でも演算できるはずだ。

加算ひとつで数百命令使いそうだが、それでも例えばGHzクラスで動けば、MHz時代のCPUの性能は出るはずだ。

ここで、さすがにこれをマクロ命令でやるのはバカらしいので、マイクロコード方式の命令実行を考えてみる。
そうすると、マイクロコードを書き換えればどんな演算命令も自在に定義できるではないか！

って、当たり前だ、というか別に普通のプロセッサでも原理的には何でも出来る。

だがここでちょっと考えてみたい。上記の任意のビットにNANDを適用するのは現在のCPUでも何命令かを組み合わせなければ実現できない。

早い話が、近代的な非常に高度で多機能なALUも、演算の用途によってはNANDゲート１個に性能で負けるケースがありうるわけだ。

もちろん一般のCPUの命令は多くのケースで非常に高い効率で演算できるように非常に良く考えられて設計されている。
一方で極々まれにCPUでは非効率になってしまう演算もあって、例えばFPGAなりの方がまだ適しているケースがあったりする。

ここで、もう一歩踏み込んで考えて見る。
FPGAのようにLUT方式的なALUを用意して、テーブルやマイクロコードを自由に入れ替える命令を有したらどうなるだろうか？

普通のCPUは扱いやすい形式の演算だけが異様なまでに早い(IEEE754形式とか)。
でも、CPUの得意なデータ型ではないデータ型を効率よく扱いたい場合も極々稀にある。

自らの演算器自体を再定義しながら動くCPUとかあったら面白いかもなぁ  などと考えて見るも、やっぱりノイマン型をとる限りは、どんな演算でもはハードマクロな既存演算の組み合わせでやったほうが早いかもなとも思ってみたりして。

また時間のあるときにでも再考察して見たい。

　Digilent の ZYBO(格安Zynqボード)が発売延期を繰り返しているようで、ワクワクしながら様子見しています。

　実は別件でちょっとだけZynqを火入れ確認程度に触ったことがあるのですが、なかなかスジがいいなと感じています。
  特質すべきは(XILINXの動向も含めて)

　　・CPUコアから起動とロジック書き込みを前提としていること
　　　(それでいてJTAGからは従来のFPGAと同じに使える)
    ・パーシャルリコンフィギュレーション技術
　  ・超安価な高位合成ツール

  といったところです。

  こうなってくると、たとえばアップルストアやGooglePlay からソフトを買うように FPGA回路がエアダウンロードされてくる時代が近づいているのを感じます。

　その際、問題となるのが互換性の問題でしょう。
　世代やメーカー、スピードグレードなどによりRTL回路は変わるので、当然ながら統一的な規格や中間言語のような記述、端末側での動的合成などが必要になります。
　また、デバイスごとのスピードの問題もあるので、クロックの抽象化や低即時にパフォーマンスが落ちるのみで住む（故障やシステム破綻につながらない）外部とのI/Fとしての標準プロトコルも必要にあってくると思われます。

　言うなればハードウェア用に新しいOSのようなものがこれから必要になってくると思います。
　ソフトウェアのOSがかつてそうであったように、非常に面白い領域が誕生してくれるのではないかと期待しています。

　ちなみにFPGAのような領域では、浮動小数点やその他SIMDなどの効き易い計算ジャンルはCPU(AVXとかNEONとか)やGPUに適わないと思っています。
　一方でバイナリ系のデータを扱う領域においては極めて強力です。通信系の処理とか一部のバイナリ系画像処理とか、そういったジャンルで面白い用途(キラーアプリ)がもう少し身近に現れてくれると計算機のアーキテクチャももっともっと面白くなるのではと思います。

　FPGAの老舗のXILINXがFPGA部に拘らずに、NEONなどを詰んだARMを混載してきたのは、今後を期待させてくれる事態だと思っています。

C言語の弱い部分はプリプロセッサである。
#if しかないが、せめて FOR文 ぐらい書けてくれ。

他にも FOPENして FSCAN して、ファイルの中身を配列初期値にしたり、三角関数や指数関数でループを回りながらテーブル初期値を算出したりしたい。
定数係数の重みを計算しながら、加算順序や構造体内をソーティングしたりしたい。
似たような関数をループで生成したい。

まあ、自作プリプロセッサを作れば済む話なんだが、なかなかスキルが及ばない。

ハードウェア記述言語の Verilog では、generate文がそこそこいい感じであるが、それでもまだまだ痒いところに手が届かない。

最強なのはLISPであろうか。コードとデータの区別がないので、マクロとプログラムが同じ言語で書かれていて区別はない。
しかも、コンパイル済みバイナリはインタプリタを含むし、インタプリタからコンパイルできるしでやりたい放題である。覚えたいが難しい言語である。

最近RTLを覚えたせいか、マクロの重要性を非常に痛感している。
いつか自分で言語を作るときはLSIP並みに自由度のあるマクロを搭載して、且つ、C言語やにやさしい言語にしたいものだ。

  多少の鈍りはあるものの、半導体業界でのムーアの法則は未だに健在である。
  しかしながらプロセッサの進化速度はポラックの法則その他に縛られいろいろとあらぬ方向に舵を切っている。

  近年目立つ変化といえば、プロセッサ単体での性能進化が急激に鈍り、マルチコア化に突っ走っていることであろう。
  シングルコアあたりの性能はあまり増えなくなった。

  さてここで、科学技術計算について考えてみよう。いわゆるHPC分野などである。
  科学技術計算などの分野で見ると、とにかくほしいのは FLOPS性能 である。

  FLOPS演算性能を手っ取り早く低コストで上げるのに効果的なのはいわゆるSIMDである。
  しかしながら、１プロセッサあたりのSIMDの並列性がムーアの法則で増えているかといえばNOである。
  64並列とか1024並列とかのぶっ飛んだサイズのSIMDがあれば面白そうだが、コストパフォーマンスのよい x86 レンジだとSSE命令で、単精度4並列、倍精度2並列の命令を有しているに過ぎない。
  「何で？」って疑問になるわけだが、想像するに１つはOSの問題が大きいと思う。
  簡単にレジスタが増やせないのである。レジスタを増やすということはタスクスイッチ時の退避復帰にコストがかかる上に、OSが対応する必要がある。
  他にも場合によっては割り込みハンドラなどデバイスドライバの範疇にも影響するかもしれない。
  また、勝手に新命令をつけてもOSの許可なくENABLEにできないはずだ。OSの知らない レジスタがあるということは、それを使ってプロセス間通信をされてしまうと、セキュリティーホールでしかない。

  そして、将来SIMDの並列度に対して汎用的なコードを書くのは難しいという問題もある。  反面マルチスレッドは粒度が荒い分まだ汎用的に対応しやすい。
画像処理のような鬼サイズのループを
#pragma omp parallel for で済ませてしまうようなケースは当面並列度の増加での分割粒度不足は起こるまい。

国家プロジェクト級のスパコンならともかく、ミドルレンジでコストパフォーマンスのよい演算を追及する層にとっては、まっとうなソフトウェアの生産性を保つ必要もあって、やっぱり売れ筋のプロセッサは今後もコア数が増える方向に進むと思う。

  コア数を増やすことに特化しているGPGPUも同じことで、単スレッドで使えるSIMD幅の増え方はそうは変わるまいと思う。

  一方でコアを増やし続けると発生するのが、通信と同期の問題である。たとえワンチップであってもだんだんとこれらが占めるコストは比率が増していくと考える。
  プログラマにとって、for文の分解は10個だろうと1万個だろうと同じことなのだが、ハードウェアリソースの消費比率が変わってきてしまうわけだ。コストパフォーマンスが悪化してしまう。もっともそれが問題にある分岐点はもうちょっと先ではないかとは思うが。

  で、最後にお約束のようにFPGAも考察しておく。   FPGAは恐らく今後もずっと、どう逆立ちしてもこれら汎用プロセッサに単精度や倍精度のFLOPSで勝つことはできないと思う。

  一方で、単精度や倍精度と極端に精度の違う問題や、極端に粒度な並列度を持った問題では高い効果を出すかもしれない(というかすでに出ている)。
  プロセッサがやれない 1024並列SIMDとかのレンジの演算も、ハードウェア記述言語であれば並列度に対して汎用性を持った生産性のよい記述ができる可能性はある。
  プロセッサの苦手レンジを狙って、ソフトや向けのツールとして台頭してくるのをもう少し期待しながら眺めてみたいと思う。

HPC分野においてFPGAが効力を発揮する可能性があるのは、一般のCPUやGPUがハードワイヤードとして持つ演算器と離れた演算精度を持つ場合と考える。
つまり、非常に小さなbit精度だが大量の演算が必要な場合と、倍精度よりも少し大きな精度が欲しいケースである。
そうは言っても、SandyBrigeなどの150GFLOPS級のCPUが5～6万で買えてしまう時代に果たしてどの程度アドバンテージがあるであろうか？
DegiKeyでFPGAの価格を調べてみると(XILINXだけだが)、廉価シリーズのSpartan6だと LX150T が 1.5万円ぐらいで買えてしまう(びっくり)。いつのまにかKintex-7も扱われているが、325Tしかなく、13万円ぐらい(それでも325って一昔前の感覚だとすさまじいな)。

しょうもないデータ取りをいろいろやったのでUPしておく。
「fpga.xls」をダウンロード

今のところあんまり価格メリットは無いかも。

ただし、今後この配分はまた変化する可能性は高いと考える。、何しろ一昔前にくらべて圧倒的にFPGAはこの分野に食い込んできている。その理由をいくつか考えてみる。

１．ポラックの法則に律速されない
  ただただ、ムーアの法則で伸びる。

2. 世の中は複雑
  単精度／倍精度だけで足りるほど単純ではない。

3. 拡張が容易
  単にFLOPS/$ が欲しいだけならもっとも費用対効果の良いFPGAを大量に並べればよい。特にパイプライン演算を組む場合、結果は安直である。
  CPUやGPUを大量に並べる場合の通信ボトルネックや、生産性低下は避けられない。

逆に問題点

1. H/W記述が必要
  ソフト屋視点で見ると現状のRTLははっきりいって言語的にいろいろ欠陥ありまくり。一方でもっとも性能が欲しい部分はどうせソフトでもSIMDなどを意識してアセンブラ的に書く。はっきり言って肝の部分の記述にかかる労力はあんまり変わらない。
  これは純粋に使いやすい言語の開発と、周辺部品の整備の問題と考える。

2. 書き換え速度が遅い/互換性がイマイチ
　前者はパーシャルリコンフィギュレーションなどである程度解に向かっているが、それでもノイマン型にくらべれば動的なプログラミング自由度が低い。後者もやはりCやFORTLANに比べると、ベンダー固有のライブラリの問題は多い気がする。
  半分はコンパイラ、半分は標準化の問題かと。

3. ツールの問題
　WebPack などフリーな開発環境が増えてきたにもかかわらず、オープンソース界で周辺ツールの発展がまだまだノイマン型ソフトウェアにくらべ遅いのは否めない。

  商用の SystemC とかに取って代わるような、オープンな独自言語＋ツールを作りたいなぁなどと夢想するのは私だけだろうか....（普段 Verilog な人なのですが、いろいろ言語的に改造したい部分が多い....）

昨日はTOP500しか載せられなかったが、一応一緒に収集していた他のデータも不完全ながら重ねてみた。

TOP500のような汎用計算機に対する、専用計算機の指標としてGRAPEのデータを拝借してみた。wikipedia などから適当にかき集めてきただけなのでいろいろと、集計ミスはありそうな気がしますが、ご容赦ください。

「flops.xls」をダウンロード

なんだか、GRAPEに関しては、同じライン上にGPGPUが入り込んできてしまったように見えますね。GPGPUは専用計算機というよりかは多少汎用性はある気がするので(GRAPE-DRも汎用性はあるようですが)、ここはGPGPU側の量産効果とプロセスの差が埋めているのかもしれませんね。

で、FPGAがどうなのかというところが個人的に非常に気になるところだったりするのですが、まっとうなFLOPS勝負をすると、多分まったくコストパフォーマンスでGPGPUなどに惨敗で、たとえばGRAPE-1のように演算精度がある程度低くても有意な結果が出るかわりに演算量が異常に多いといった分野はじめてアドバンテージが出てくるであろうなと想像しています。