エキスコン（２１） －ソーティングのためのハードウェア化実現性－

　前回のエキスコン（20）では、炉端老人からソーティングを行うためのハードウェア化としてFPGAで実現できるであろうか？　という課題が示されていた。ソーティングとはランダムに並んでいる数値の列を大小順に並べ替えることである。文字列であれば、文字のコンピュータ内部表現として大小関係が付けられているので、アイウエオ順に並べ替えるとしてもよい。少しばかり調べてみたが、結論から先に述べると理論的には実現できるが、現在のFPGAの規模では難しい、と考えられる。

　まず理論的な実現性について述べる。ソーティングをネットワーク構造のハードウェアで実現できないか、筆者は独自に考えてみた。すぐに思いついたのがトーナメント方式によるソーティングである。近く選抜高校野球が行われる。高校野球はトーナメント方式で優勝校を定める。この方式によるソーティングをトーナメント方式で考えればよい。トーナメントの試合形式では、参加校がｎ校あるとすれば、たかだかlog n回の試合で優勝校が定まる。ここでlogの底は２であるから、仮に64校が出場しても、参加校としては６回の試合数で優勝が定まる。全体の試合数はn－１であり、オーダとしてはn であるからこのことをOrd (n) と表すことにする。トーナメント方式によるソーティングをネットワークで処理する考え方を基にすると、ソーティングは記憶素子を用いない組み合わせ論理回路のみで実現可能であることは明白である。そこでインターネットを検索したところ、古くから多くのソーティング・ネットワークが提案されており、筆者の勉強不足であることを思い知らされた。

　代表的なソーティング・ネットワークは、バイトニック・ソーティングによるものである。処理に要する比較回路の段数は、Ord (log n)² であるから、これを組み合わせ論理回路で構成すれば、入力が与えられてから出力が得られるまでに要する処理時間は極めて短くできる。仮に比較回路の処理速度を１マイクロ秒として、10億個のデータをソーティングするとすれば、１ミリ秒すなわち千分の一秒で処理できることになる。この組み合わせ論理回路の規模は、Ord n (log n)² となる。 

　このような規模を必要とするソーティング・ネットワークをFPGAで実際に実現することは、現時点では困難であろう。その理由を次に述べる。

　10億個のデータをソーティングするために必要な比較回路素子の数は10の12乗個、すなわち一兆個程度となる。比較回路自体の構成には10の3乗程度の論理素子を必要とするであろうから、素子数は10の15乗個と厖大な数になる。さらに比較回路間の接続配線も輻輳する。FPGAの作成を行うメーカーの資料を見ると配線領域の増大は、回路個数の増大と共に大きな課題になっている。現在市場に供給されているFPGAの論理素子数は10万個、すなわち10の5乗個程度にすぎないから、バイトニック・ソーティング機能を組み込むことはできそうもない。

　それであれば、実現できる範囲のソーティング・ネットワークをFPGAで構成し、これを用いるためにデータを分割して処理する方式も考えられる。様々に調べていると画像処理にもソーティングが使われているようなので、あるいはすでに分割処理する手法が開発されていることも想像できる。

　いずれにしても、ソーティングの並列高速処理は、エキスコンに関わる将来課題の一つであろう。　（応）

キーレス・ドアとカー・ナビの最新事情

　10年近く愛用した自家用車は、まだまだ健在であったがエアコンが故障し、その修理代の見積もりが、あまりにも高額であったことから新車に入れ替えた。その新車はキーレス・エントリー・ドアと呼称はしているものの電子キーが必要であり、家人との使い廻しもあるので、余分のキーに購入した。電子キーを持参していれば、ドアノブにタッチするだけで、ドアの開け閉めができ、エンジンの始動・停止も従来のようなキー操作は必要としない。
　確かに便利である。
　このキーを持っていると、近づいただけでドアのアンロックとかロックをする機種もあるそうだが、これは好ましくないであろう。持ち主の施錠とか解錠の意志が届くことが必定と考える。カーのドアは、建築物のドアとは異なり、カーから降りて遠ざかることだけでロックされるとすれば荷物の運搬などに支障が生じる。
　ところが、ある日このキーレス・ドアが突然作動しなくなった。ドアノブの操作をどのように行ってもキーレスとしては動作しない。いたし方ないので、従来方式によりドアのキー・スロットに鍵を差し込んで開け閉めをすることになった。これまで正常動作をしていたのであるから、何らかの異常な調整を知らない内に実施したためかと思いこみ、マニュアルを隅々まで調べたところ、オプションとしてキーレス・エントリーを作動しない方法もある。しかしながら、そのためにはディラーに持ち込みなさい、と記されている。
　筆者の持っているはキーは、もしかするとキー内蔵の電池が消耗しているかも知れない、新車なのにそんなに早く電池が消耗するのか、といぶかりながら家人のキーを借りようとした。
　ところが家人は「キーがない」といい、探したが見つからない。
　可哀想に真っ青になる。
　何となく予感がしたこともあり、夜空の寒中、ふるえながら懐中ライトを持ち出して車内を見たところ、キーがあったではないか。
　ナルホドと感心する。キーレス・エントリーのためのキーを車内に置いた場合は、キーレス・ドアは作動しない。キーを車内に置き忘れたままドア・ロックしたならば、ドライバーは難民状態に陥ることになる。キーレス・エントリー・ドアのためのキーが車内にあるか車外にあるかを判定する機能を持ち合わせているが、これをどのように判定するか疑問を持つと同時に、日本車の設計技術者は、そこまで配慮したことに感心する。
　車内にあったキーを家人に渡した後は、正常に動作するようになり、ディラーに訪問する必要はなくなった。

　いま一つは新しいカー・ナビの機能である。
　永らく愛用した車にもナビを装備していたが、この中にひそむ案内嬢は、道を間違えると何とか元の道に戻そうと盛んに語りかけてくる。それほどあらかじめ設定されていた道が優れているのだろうか、と案内嬢が憎らしく思えてくる。
　入れ替えた新しい車両の案内嬢はいかに、とわざと道を間違えてみたところ、たちどころに新たな道程を設定して案内をする。心なしか、これまでの案内嬢より、声も美しく響く。
　ナビの仕様書をひもとくと、ナビの中には動体の慣性センサーがあり、道を間違えたとき、GPS人工衛星からの信号を処理すれば、そのために後れ時間が生じることを防止する手法である。
これまたナルホドと理解した。
　筆者は海外旅行でも、ナビつきのレンタカーを３年ほど前に利用したことがある。このナビの道案内は何故か男性の声であり、道を間違えると「calculating 」、すなわち計算中、としばらくの間わめき続けたものである。新しい道程を設定するまでに、かなりの時間を要する。
　さらに日本の最新のカー・ナビでは鳥瞰図、すなわち飛ぶ鳥の視点のような図のもとに案内されるから、あたかもヘリコプターに乗っている者から指示されるように画面が動く。これまた分かり易い。
　愛くるしいお嬢さまがフレンドリーに案内をするように進化しつつあることを知ることになった。
できればハンドルさばきとアクセル位置をセンスして、さらに早めに案内を変更するようになればいいなあ、とも思う。
やがてそうなるであろうが、そのようなナビは、工場装備になるのではないかと推量する。カーショップに並んでいるカー・ナビ製品については、車両の操作にまで立ち入って案内するために３次元の加速センサーを装備しなければ、実現しそうもないからである。
（応）

追記
　この記事に、ある知人から日本語では関連記事が見あたらないが、下記のような英文の紹介文があるというコメントをいただいた。

It's Very Clever
The system is also smart enough to know if you've left the key in the car.
In which case, it won't let you lock the door unless the key is outside the car with you.

エキスコン（２０） 炉端老人の話題－非ノイマン型コンピュータのこと－

　おや、きたな。
ナニナニ先日送ってもらったFPGAの資料をもとに議論したいって、か。
うん、待っていたところだ。

　FPGAには少しばかり関心があった。Field Programmable Gate-array Logicsを省略してFPGAといったな。最初に米国のXilinx社が、マイクロプロセッサの周辺回路の構成を容易に実施するため、論理回路をゲートアレイとして組み込んだ半導体素子を準備しておき、この内部の接続配線を現場で組み上げるために利用したものだ。試作のためなどの研究目的、さらには少量他品種の製品には都合がよかったので、深く静かに市場が拡大していったようだ。
届いた資料を読んでみると、最近ではSoC型といってゲートアレイの他にマイクロプロセッサの機能を持つコアとか、記憶装置に相当するものまで組み込まれているFPGAが出現している。
極端な言い方をすれば、その内にワンチップのパソコンも出現することになりそうだ。まことに隔世の感がする。

　おーい、ばあさん。今回は、濃いお茶を入れてくれ。
　話しが長くなりそうだ。

　ほう、積和演算器とか乗算器もFPGAで集積できるのか。高速フーリェ変換器、つまりFFTを内蔵させることも夢ではなくなったということだ。アナログ変換回路までも内蔵できるとすれば医用機器にも大きな進歩が期待できる。
つい、先日のことになるが、この老人も医者のところで超音波の診断を受けたが、精度がよくないらしくてよく解らないという。結局のところCTスキャンによる診断をしなければならなかった。それでキチンとした診断がでたがね。
なに、心配することはない。ありきたりの老人病だ。
　その内に町医者が精度のよい超音波診断器を手軽に使いこなすことになるだろうなぁ。
診断は確実に早くできるようになるさ。

　えっ、前処理として組み込んだソフトウェアから、ゲートアレイに展開するアプリケーションまであるというのかい。
それはすごいことだが、ソフトウェアとして開発されていたアルゴリズムがすべてFPGAに展開できるかどうか、この老人にはとても理解できない。
　先ほどのFFTならば、単純な積和演算のネットワークとして構成できるから、ゲートアレイによって実現できることは理解できるがね。それでも巨大なネットワークだ。まさにスパコンを通り越したエキスコンになるだろう。

　例えば、ソーティングのアルゴリズムがあるね。このアルゴリズムを元にして、そのままFPGAに展開できるのかい。ソーティングとは、でたらめに並んでいるデータを順序よく大きなデータから小さなデータへ、あるいはその逆に並べ替えることだ。簡単な課題だが、ノイマン型コンピュータではデータ数が大きくなれば多大な時間がかかることから、能率のよいアルゴリズムの開発が行われた。仮に巨大なFPGAでこれが実現すれば、でたらめに並んだデータが一瞬にして大小関係が整列したデータに変換されることになる。
更に一般的に言ってみよう。
　あらゆる順序回路がFPGAに展開できるとすればソフトウェアがなくなるなぁ。
　つまりノイマン型コンピュータがなくなるってことだ。

　そうか、記憶素子もFPGAの素子の中に準備されているので、実現できるはずだというのかい。それではソーティングのFPGAを実現できたら信用しよう。
　そういえば、ヒトの脳は非ノイマン型コンピュータと見なしてよいようだ。
だからといって人工頭脳の実現であると、この老人に説得しても、そこまでそうだとはいえない。
　ニューロンの中で生じるかも知れないという、不確定があっては、FPGAの実用性がないことは確かだ。ヒトは、不確定性のもとに迷いが生じる。それがニューロンの不確定性と関わりがあるかどうかは、よくわからないが。
話題が外れたな、ゴメン。

　オヤ、もう帰るのかい。
そうかソーティング・アルゴリズムがFPGAに展開できるかどうか、考えるというの。

　せっかく、ばあさんが入れた濃いお茶だ。
　すすって行きなさいよね。
（納）