パスワードを忘れた? アカウント作成
59089 story

確率的コンピューティングでパフォーマンスをブースト 86

ストーリー by soara
円周率はだいたい3 部門より

capra 曰く、

本家「Sacrificing Accuracy For Speed and Efficiency In Processors 」より

現代のコンピューティングは正確さが重要視されているが、米ヒューストンのライス大学のKrishna Palem教授は将来のアプリケーションは「確率的コンピューティング」によって大きく変わるかもしれないと考えている。米国時間15日、Palem教授はサンフランシスコでのコンピュータサイエンスの会合にて確率的コンピュータチップの実験結果を発表するとのことだが、ランダムエラーによってパフォーマンスを向上させているこのチップは最先端のチップよりも1/30の電力で7倍のスピードで稼動するという。
現在のチップは高密度なトランジスタによりバックグラウンドノイズが発生するため、回路への電圧を高め、ノイズを抑え、正確な演算を確実にしている。しかしPalem教授は演算のクオリティをどれだけわずかに落とせばスピードの向上と省エネを実現できるかという観点で考えているそうだ。
情報の重要さには差があり、例えば銀行の残高の「$13,000.81」を算出するには「13」を正しく導き出す方が「.81」を導き出すよりも大事であり、「$13,000.57」という計算結果は、「$57,000.81」と導き出されるよりもずっと正解に近い。Palem教授の開発しているチップは火星へのミッションで必要となる演算を行うには適さないかもしれないが、携帯端末の音楽や動画ストリーミングには展開できるかもしれないとのこと。

銀行の残高の例は極端かもしれないが、本家のコメントにあるよう「選択的な正確さ」というのには道があるのではないだろうか。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by tmiura (6268) on 2009年02月11日 17時02分 (#1511329) 日記

    タレコミ文を見る限りでは、

    • デジタル回路の0/1判定境界をノイズフロアに近づけ(余裕をなくし)て 駆動電圧(消費電力に二乗で効く)を下げる
    • 複数の信号の間の伝播遅延のばらつきや個々の信号のスイッチング前後のばたつきを吸収するための待ち時間の余裕を削ってクロックを上げる

    という、従来デジタル回路の「前提」だった一線を踏み越えちゃっても許される範囲を探る発想のように見えます。 この場合、起きる事象は、アルゴリズム上の演算精度を下げるというよりは、ときどきビットが化けるということになります。

    回路全体をそのようにすると上のビットも下のビットも均等に化けやすくなってしまうので、下の方の桁だけ選択的に低電圧駆動するなり、上の方のビットに冗長ビットを追加して誤り訂正するなり、またアルゴリズム上ゲートディレイが長くなるパスと重要度の低いパスが一致するように回路設計を頑張る(できるのかそんなこと)など、対策を打った上で全体としてどれだけメリットが出るかというのが評価ポイントかと思います。

    ただ、ビット位置による重要度の偏りの有無は結局はアルゴリズムと切り離せないので、計算の基本アルゴリズムに重要度指示ビットを追加して許容ノイズレベルを動的制御するとか、回路の部分によってクロックまで変えちゃうならいっそ非同期論理(値と一緒にクロックを持って歩く方の)で全体を組み直したりなど、相当なハード量の増加とセットでプログラムの書き方の転換が必要でもあり、それはそれで面白そうではあるけど、入っていくのに結構敷居の高い世界なような気がします。

    アレゲ的にはこのようにルールが見えてきたらシミュレータ作って遊んでみるとその先の世界の片鱗が見えてきて面白いのでしょうけど。

    • by glasstic (32934) on 2009年02月11日 20時19分 (#1511472) 日記

      これまでの設計の主流は、回路内のばらつきを考慮した最悪値に対して、余裕のあるクロックや駆動電圧を設定するものでした。
      しかし、近年の微細化による駆動電圧の低下で余裕が無くなり、そんな最悪値を考慮してたらとても設計できないという状況になりつつあります。

      これを受けて、回路内のばらつきを統計的に考えて、製造後に何%のチップが何MHzのクロックで動作するといった設計ができるツールが研究されています。
      適当な推測ですが、タレコミの用途にもこれらは応用できないでしょうか。

      親コメント
    • もとの論文ではどの辺りを狙っていたのでしょうね。
      回路に論理的な冗長性を持たせる代わりに、消費電力を下げるようにイミュニティを調整する という技は普通の方法として実用化されてもおかしくないと思います。ISSCCの季節ですし。
      微細化の恩恵を生かすためにいい方法じゃないでしょうか。ゲート数を増やして消費電力を下げる。

      一部のサーバでは、常にパリティを計算するという方法は取られているので、多少エラーすることを前提に設計するということだけならそれほど目新しい気はしません。

      計算機の汎用的な部分に使って、ユーザに見えるレベルでエラーが残るのはちょっとやりすぎかも。まともにプログラムが動くとは思えない。特定の用途の回路に絞って、たとえばデジタルテレビで、ちょっと画面がちらつく、色調がなんとなく変 という程度ならありかも。
      親コメント
  • 演算結果の正確さと引き換えに計算コストの(大幅な)削減を実現する、というアイデア自体は、例えば
    • 巡回セールスマン問題のように厳密な最適解を求めるのが難しい(時間がかかる)最適化問題について、近似解を高速に求めるアルゴリズム
    • 素数性判定問題のように(判定したい数が巨大だと)時間がかかる判定問題について、ある程度の確率で間違った答えを返す代わりに短時間で終了する確率的アルゴリズム

    のように、アルゴリズム/ソフトウェアのレベルでは既に主要な研究分野として認められるほどよく知られたものです。
    なので、今回の研究の目新しい点は、そのような工夫をハードウェア(チップ)レベルで実現しようという発想にあるのだと思われます。

    ただ、私もハードウェアや数値計算の分野には明るくないので素人考えになってしまいますが、累積誤差の問題や、最終的な演算結果の精度保証などはどのように解決するつもりなのでしょう?仮に大雑把な計算結果で充分な場面であっても、あまりにも大雑把すぎる計算結果ではやはり使い物にならないでしょうし。
    あと、演算速度はともかく省エネという観点からは、件のチップを追加搭載するのに要するエネルギーを上回る省エネ計算を実現しないとトータルで省エネにならないわけで、その壁を突破できるかどうかも興味深いところです。

    • >累積誤差の問題や、最終的な演算結果の精度保証などはどのように解決するつもりなのでしょう?

      応用例に出されているように、音声や動画の再生ならば、定期的にキーフレームが出現するので、累積誤差はリセットされます。
      また、もし精度が保たれなかったとしても、画像が乱れたりノイズが入るだけで、動作そのものに大きな影響は出ません。

      あと、ゲームの3D表示とかも、フレーム毎の計算ですから誤差の累積は心配ありませんし、多少の誤差が出てても動いてりゃ気になりません。

      親コメント
      • 音楽や動画の再生とひとくちに言っても、実際のプログラムを書くときには誤差が生じては困るところがありますよね。たとえば動画ファイルのx byte目を再生中にxに誤差(たとえば1byteとなりから読みこんでしまう)があると、フォーマットに沿ってデータを解釈することができずに重大な問題になります。

        つまり、ひとつのプログラム中で「正確であることが必要な部分」と「誤差があっても能率を優先してよい部分」をどうにか分ける必要があると思います。プログラミングのノウハウも変えるのか、何らかの方法で自動的に分けることができるのか、興味深いと思います。

        誤差を認めるのは浮動小数点演算に限るとか、あるいはプログラミング言語としてroughly{ ... }キーワードを作って、くくったところだけ誤差を認めるとか思いついたのですが、どうでしょうね。
        --
        人生は七転び八起き、一日は早寝早起き
        親コメント
        • MMXとかSSEみたいに、専用命令持てばいいのでは?

          あと、動画再生に特化するなら、CPUとは別にデコーダー専用のチップとして載せるんでは?
          今の携帯電話とかって、H264とか再生できますけど、あれはCPUでデコードしてるわけじゃないだろうし。

          親コメント
    • わたしも近似アルゴリズムの端っこを齧ったことがあります.
      今回のコレにインスピレーションを受けて,
      「計算結果に確率的に誤りを含むオラクル(計算機)」を使った計算量クラス
      というのが考えられそうで面白そうですね.

      #既にあったりして・・・

      親コメント
  • by matma (34555) on 2009年02月11日 13時46分 (#1511200)

    本当に1/30の消費電力で7倍の速度っていうなら、
    3つセット(とか、奇数)にして演算させて、
    多数決理論で補強すればけっこう魅力的に思えなくもない。
    それでも1/10程度の消費電力と7倍の速度ってことになるし。

    #2つはダメだ。3つにするんだ。

    マルチコアを確率的コンピューティングのポリシーで設計して、
    求められる精度に合わせて何個のコアで多数決させるかを動的に調整しながら動かす、
    なんてのは、精度よりもスピードが要求される分野では面白かもしれない。

  • by superfox (31908) on 2009年02月11日 12時35分 (#1511153)

    ・生き残れないよ派

    「件のチップを使っていかに正確に計算させるか」という分野が立ち上がるかもしれないが、そのようなコストをかけるくらいなら普通のチップを使った方が良い(速度のメリットが生きない)

    確率的に計算することでパフォーマンスを稼いでも、通常チップ陣営がそのパフォーマンスに到達したら意味を失う

    ・生き残れるよ派

    「コストが安い」の一点で特定分野で生き残れるかも(DSP とか)

    # 自分は前者かな…

    • by ogino (1668) on 2009年02月11日 13時17分 (#1511180) 日記
      ソフトウェア環境がうまく立ち上がれれば生き残れるように思います。

      「確率的」というとキワモノという印象が強いですが、高速・低消費電力・精度が低い、と考えれば何でも倍精度が必要というわけではありませんから演算コプロセッサ的としてハマる使い道があるのではないでしょうか。

      例えば、厳密さよりも時間的な縛りの方が優先される分野:
      ・計算による気象予測など:「厳密に計算できるがメッシュが荒い」と「確率的に計算するがメッシュが細かい」との比較で後者に勝ち目があるかも知れない。
      ・組み込み系:音声認識、画像認識、自動車の衝突予測など、厳密さがさほど意味をなさず、かつ高速応答・低消費電力が要求される分野
      ・ゲーム:演算が高速になって消費電力 96%カットなら物理現象シミュレーションなどで重宝しそうです。チェス、将棋、囲碁のようなゲームで計算しきれない分野にも良いかもしれません。

      自然現象相手や人間相手だと処理するデータが厳密でない or 厳密である意味が少ないので、相性が良い気がしてきましたが、どうでしょう。
      親コメント
      • あるシステムの特性を、さっとシミュレーションしたいときとか
        携帯デバイスで、色とか音の再現性は大体でいいので動画をサクサク見たいときに使えそうかも。
        # シミュレーションの方は精度を落とせってツッコミは無しで:p

        元コメでは『確率的』とあるが、それを『選択的』と解釈すれば
        我々もまた、日ごろからミーティングなどで精度を犠牲にして概算することを
        しているわけだし、なんら不思議はないと思う。

        で、最初捨てた精度を後で補間することができるなら、かなり使ってみたい。
        円周率を3で最後まで計算しておいて、後で3.14とするみたいに。
        これが出来れば、前述の動画なんかだとサクサク見れる限界の精度が選択出来ることになるよね。
        # もちろん再計算のオーバヘッドが課題になるが。

        親コメント
  • by Lurch (10536) on 2009年02月11日 12時39分 (#1511154)
    って話じゃないのか
    --

    ------------
    惑星ケイロンまであと何マイル?
    • by T.Sawamoto (4142) on 2009年02月11日 13時58分 (#1511209)

      先生っ。
      西軽井沢 [nishikaru.com]辺りでは的中率90%を誇るらしい私のお天気占いプログラムには、クオリティを落とす余地がありません!

      #include <stdio.h>
       
      int main(void) {
          char date[256];
          printf("日付を入力してください> ");
          if (scanf("%255s", date) == 1) {
              printf("%sの天気は「晴れ」です。\n", date);
          }
          return 0;
      }

      親コメント
  • by phenix (31258) on 2009年02月11日 13時16分 (#1511179)

    これでもう疑似乱数使う必要ありませんね!

  • by ttm (8278) on 2009年02月11日 15時51分 (#1511285)

    ソフトウェアが潜在的に持つバグに比べて統計的に無視できる程度の信頼性の低下ならば実用上は問題ない「筈」だし、
    真面目なソフト屋ならばバグ曲線ぐらいわかっているだろうから、システム全体としての品質にも問題ないと理解できる「筈」なんだけど、
    ソフト屋にもハード屋にも受け入れられないだろうね。

    人間って、自分の失敗は許容することを平気で要求しながら他人の失敗は許せない、という性質を持ってるから。

    • アプリを作るときに、「統計的に無視できる」かどうかを見積もってから作ってやらないといけない工程が増えるのではないかと思います。作成者側としては面倒な作業がふえるなぁと思いますね。「誤差が積もっても問題ないことを確認するためのストレステスト」なんて工程が増えるのかな。

      「全体としては品質に問題はありません」と説明したとして、お客さんにとってはブラックボックスに見えるわけですし、信用してもらえるかどうか…… そういうところでは使わないということかもしれませんが。
      --
      人生は七転び八起き、一日は早寝早起き
      親コメント
    • > 人間って、自分の失敗は許容することを平気で要求しながら他人の失敗は許せない、という性質を持ってるから。

      某社の「仕様です」はけっこう許容してます。

      # いや、許容以外の選択肢がないんですけど。
      --
      # yes, fly. no, fry.
      親コメント
  • ポインタの下位数ビットが不安定にふらふらされたら illegal stomping が起こりまくるじゃないか。

    一方で、浮動小数点でも仮数部の下位数ビットがふらついてもいいのは、指数部がほとんど変化しないときだけだ。指数部が増えたり減ったりする場合に仮数部の下位数ビットがふらつくと、指数部がたまたま大きな値だった場合にはとても大きな影響になる。影響がコントロールできないので数値計算にも怖くて使えない。

    というわけで、使えるのは固定小数点演算の場合だけでしょうが…数値計算を固定小数点でやるか? わざわざポインタ計算用の整数演算回路とは別に不安定な回路を組み込んでまで…???

    というわけで、これは「判っているようでわかっていない人の妄想」って奴じゃないのか??!?? という気がしてならないのですが。

    --
    fjの教祖様
  • by Elbereth (17793) on 2009年02月11日 19時23分 (#1511436)
    > 情報の重要さには差があり、例えば銀行の残高の「$13,000.81」を
    > 算出するには「13」を正しく導き出す方が「.81」を導き出すよりも大事であり

    銀行でそれはありえない。残高の数字は全部間違えずに出す必要があるだろ。

    俺は預金なんてないけどな!
  •  dodongaです。

    #タレこみ文がほぼ抄訳だたのでリンク先は斜め読みでしゅ^^。
    ##実験結果がでるまでは眉唾ぽいなぁ…w
    #ハードウェアやチップ方面は詳しくないので、電力の件はご容赦ください;;

     ぱっとの印象で申し訳ないのですが、誤差を気にしなくて良くなるのかなぁ。

     物理・数学では"数値計算"は誤差との闘いです。それが、"確率"で"保障"されるの
     なら、すっごく大変な誤差計算を気にしなくて済む。

     数値計算での殆どは誤差評価です。元々のコンピュ~タの計算結果があてにならな
     からです。
    #あっていないものを、さも解答として出してきますからね、CPU/MPUは;;。

     物理・数学での数値計算は
     ・このときはこの値を超えない。
     ・このときはこの値をしたまわらない。
     ・このときはこの範囲に納まる。
     で、計算しますから。

     誤差範囲が予想内なら数値計算のプログラムが大分楽になりますね。

     誤解無きよう。コンピュ~タで計算できない物は多数あります。
    #等式はその最たる物であたりして^^。

     誤差が確率で決まっているならば、有用な技術になるかと。

    #整数計算が誤差? そなもの間違えるなら頭丸めてでなおしてらしゃい!!w

     そな、希望をもっていいのでしょか^^

    #やぱり、実験結果とやらがでるまでは眉唾ぽいなぁ…w
    --
    閑話休題
    • 精度保証付き数値計算 [google.com]をやってくれるソフトウェアならそこここに見つかるのに、確率に頼る必要は無いでしょう。

      親コメント
      •  dodongaです。

         その、精度保証付き数値計算って、"ソフト"でやっているのでしょうから、
         内部でCPU/MPUに対して誤差計算をすっごくやっていますでしょう。

         CPU/MPUは正確な値を出してくれませんから数値計算は、ほぼ全てが誤差評価です。
         これ、ソフトでやるのはすごく大変です;;。

         私が期待したのは、出力の"誤差"がチップ内での評価から"確率的"に出てくれるの
         かなぁ~です。出力は計算結果でも同じです。

         出力の誤差が確率的に解っているのならば、その後の評価は楽になります。

        #私、どこか読み違えてるかなぁ;; 

        #やぱり、実験結果とやらがでるまでは眉唾ぽいなぁ…w
        --
        閑話休題
        親コメント
  • そのビット以下をを計算していないのとあんまり違わない。となればそもそもその分を計算しなければその分の消費電力は0。
    信用できない計算をさせるくらいならその回路の電源を切った方が良くないか?残りのビットだけなら高速&省電力で計算できるんだし。

  • 確率といえば (スコア:0, オフトピック)

    by n_ayase (36873) on 2009年02月11日 11時47分 (#1511133) ホームページ 日記

    最近はそうでもないですが、昔のWindowsだと「一定の確率で」画面が青くなって、再起動までの時間に休憩をとれるような機能が搭載されていましたね。

    という冗談は置いとくとして、これって実装するとしたらどんな感じになるんでしょう。
    普通のプロセッサ以外に「精度は低いけど速いプロセッサ」も搭載して、用途によって使い分ける感じなんでしょうかね?

    --
    神社でC#.NET
    • by Anonymous Coward
      まあ、考え方としては倍精度と単精度のどちらを選ぶ?に、もうひとつ選択肢が増えた感じかと。
      ただし、もうちょっと煮詰まってくれないとどんな用途に使えるのか?の判断は難しいですね。
      リアルタイム系には使いやすそうだ、くらいは見えますが。

      プログラムは変えないけどハードで精度・速度が変わるという視点は面白いと思います。
      今までだとハード変えても出る差というのは価格的になだらかだったので、
      それがもっと急になるなら、この手のプロセッサのメリットは生まれますね。

      #逆を言えば、価格差がそんなに無ければ出る幕は無い。
  • by Anonymous Coward on 2009年02月11日 11時58分 (#1511138)

    整数型が狂ったら流石にまともに動かないだろうし
    ……不同小数点数の導入ですね!

    ヨタはさておき、浮動小数点数の精度なんて使い切ってない事が多々あるわけで
    頭から数桁が高確率で合ってればそんなに支障は無いのかも

    ファジーな音感とかいって音楽用PCに受けるぜ?

  • by Anonymous Coward on 2009年02月11日 12時14分 (#1511143)
    数学関数や実数演算にアナログ計算機が組み込まれるのか
    数表が入っていて適当に補完するのかどっち?
  • by Anonymous Coward on 2009年02月11日 12時27分 (#1511149)

    現状、精度は低くていいが大量に計算したいときはSSE等、ビット数が少ないものを集めて一回で計算するような
    仕組みがあるようですがそれより有望なんですかね?
    素人考えだと誤差有り倍精度を2倍周波数で演算するよりは誤差無し単精度を通常クロック(但し1クロックに2個計算できる)で計算した方が計算結果に安心感があるのですが詳しい人解説お願いします。

    MPEG2あたりのまでの動画形式だと丸め誤差の積み重ねで画がおかしくなることがあったっけ。

    • Re:ビット長 (スコア:2, すばらしい洞察)

      by little( (31297) on 2009年02月11日 12時59分 (#1511169) ホームページ 日記

      >1/30の電力で7倍のスピード

      これなら、GPUに応用してほしい。
      ゲームの3D描画なんて多少の誤差出ても良いから、省電力と低価格化は魅力的。

      特に、携帯ゲーム機とか、携帯電話にとって、省電力は重要かもしれない。

      親コメント
    • by L.Entis (21733) on 2009年02月11日 13時27分 (#1511191) 日記
      SSEでは単精度演算だけでなく、有効桁数が単精度の半分の逆数、平方逆数の近似計算を行う命令がありますね。
      実際、演算精度がそれほど必要でないシーンでは重宝します。

      が、プログラミングする側が演算精度に神経を尖らせる必要があります。
      親コメント
  • by Anonymous Coward on 2009年02月11日 12時29分 (#1511150)

    >携帯端末の音楽や動画ストリーミングには展開できるかも
    なんか、どこに使うと良いのか思いつかないけど、AD 変換とかを 考えているのかなぁ。

typodupeerror

開いた括弧は必ず閉じる -- あるプログラマー

読み込み中...