カテゴリー「計算機科学」の9件の記事

2016年5月29日 (日)

アルゴリズムの計算オーダーと並列度の話

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

上記を加味すれば、並列系での中央値選択 は 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と組み合わせて最適化が必要だろうなぁ。
  実用的なところで効率の良いメディアンフィルタとか作れたら面白いかなと思う今日この頃。
  画像処理の場合スループット1というケースが多いので、単純選択ソートだと n^2 のオーダーの比較器を並べることになるので、ある程度フィルタサイズが大きくなってくると工夫の余地が多数出てきそうな気がする。

2016年5月27日 (金)

ALUがNANDゲート1個のCPUは可能か?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2014年1月25日 (土)

FPGA回路をエアダウンロードする時代

 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を混載してきたのは、今後を期待させてくれる事態だと思っています。

2011年12月20日 (火)

プログラミング言語におけるマクロ

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

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

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

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

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

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

2011年12月13日 (火)

プロセッサはこの先どう進化するのか?

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

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

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

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

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

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

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

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

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

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

2011年11月30日 (水)

HPC分野におけるFPGAの考察

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はこの分野に食い込んできている。その理由をいくつか考えてみる。

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

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

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

逆に問題点

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

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

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

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

2011年11月29日 (火)

FLOPSいろいろ集計

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

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

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

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

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


2011年11月28日 (月)

TOP500のTOP集計

ちょっと興味があって、TOP500の歴代TOPを調べてみた。
いろいろな角度からの分析もできるように、TOP500のサイトから過去のXMLのリストをスクリプトでずらっとwgetしてきて、Perlでちょちょいと加工しただけだが、見事に綺麗な指数関数を描いていますね。 縦軸は r-max で 単位はGFLOPS です。

Top500

「top500.csv」をダウンロード

2011年11月15日 (火)

組み込みプロセッサ再考

京がいつのまにやらTOP500の二連覇をしている。なんだかんだで我が国の技術はたいしたもんだ。

ということで私のフィールドワークであるエンベディッド分野を計算機科学の観点で再考してみる。

計算機科学が単独での成立が難しい学問なのは多分そうなんだろうが、とりあえず一般的な指標で考えてみる。プロセッサを語る場合、もっともよく語られる重要要素は3つ、「演算性能」、「コスト」、「電力」である。 で、各社なにかしらの指標でTOPを狙ってチューニングしてくるわけである。

「演算性能」一本勝負
    とにかく最高性能が欲しいという分野である。組み込み機器にもWindowsやLinuxがどんどん入ってきており、性能があるほどサクサク動く。 Core i7 とか、PowerPC とか比較的この路線のプロセッサではなかろうか。

「演算性能」/「コスト」
  これも割りと需要の多いレンジ。いわゆるコスパの一番いいプロセッサである。PC系に多い気がしますね。 今だと Core i5 のレンジかな。

「演算性能」/「電力」
  MIPS/W を追求する世界。やっぱARMとかが筆頭なきがする。モバイルで重要な指標な指標。   挙げていないが、「互換性」というパラメータを引き合いに出すと、ATOMとかVIAの互換チップとかいろいろ。

「コスト」一本勝負
  我々が良く使うマイコンはまさにこのレンジが多い(爆死)。やりたい事ができる最低限の 性能があれば、後はとにかく安いやつを選択というパターン。   PICやAVRのような小型のものから、各社の16bit~32bitの下位グレードあたりがこの指標で勝負している気がする。   もっとも先にあげた「やりたい事ができる最低限」のバリエーションが多いため、マイクロプロセッサもバリエーション豊富。

「電力」一本勝負
  電力のためなら高くついてもかまわない!。という分野。   腕時計とかそういう用途なので、もはや汎用プロセッサでなくて専用ASIC作るのが正解な分野なのかな。あまり汎用プロセッサとして存在し得ない気がする。   汎用計算機/専用計算機の話を始めるとHPC分野含めていろいろ話が脱線するので割愛。でもLINPAK専用計算機なんて作ればTOP500的には(間違った意味で)面白いかもしれない(笑)。

  と、いろいろ見てきてなんか気づいたのだが、何が「必須」で何が「ベストエフォート」なのかが求めるプロセッサによって変わってきている気がする。

  近年組み込み機器のPC化が進んでいるが、性能がベストエフォートな世界って本当に組み込み分野なのだろうか???
  たとえばリアルタイムOSなんてのは、「時間内にやらなければいけない処理を確実にできるプロセッサ」の限界値を引き下げる技術である。スケジューリング理論を逆手にとって、「どんなアホなスケジューリングをしてもREADYタスクがあるのにSLEEPするなんてことさえしなければ、これだけパフォーマンスがあるプロセッサなら絶対に間に合う」というリミットが(多分)ある。
  逆に賢いスケジューラを搭載すれば、プロセッサに要求される加減値は下がる。下げれば下げるほど、コストなり電力なりのより良いプロセッサが選択可能になり、商品価値を上げる。
  これは「必要な性能」が、「ベストエフォート」ではなく「事前に計算された規定値」だからだ。だからこそ工夫すればするほど別軸でメリットが出る。
  対して、必要な性能」が「ベストエフォート」な分野って本当に組み込み分野なのか? ってのはまさに疑問である。PC化ってそういう意味でも見れるんじゃないかな?   我々組み込み屋はどこに行くのか...