パスワードを忘れた? アカウント作成
333069 submission
プログラミング

誤差を許容することで劇的な省電力を目指すコンピューティング 52

タレコミ by TarZ
TarZ 曰く、

大規模化するデータセンタや、より小型で高性能になるモバイル機など、コンピュータの省電力化は近年ますます重要になっている。こうしたデジタル計算機の動作にあたっては、常に正確な動作を得られるように十分なマージンを設けた電力を使っている。DRAMの内容が揮発しないような短いリフレッシュ間隔や、回路でタイミングエラーを発生させないための高い駆動電圧といったものだ。しかし、アプリケーションによってはそこまで正確な結果を要求しないものもある。

ワシントン大学の研究チームは、ある程度の誤差を許容することで劇的な省電力を目指すハードウェアと、それをソフトウェア面でサポートするための言語を提案している。本件は、米サンノゼで開催されている PLDI 2011 で発表される。(Session 3a.“EnerJ: Approximate Data Types for Safe and General Low-Power Computation”)

. . . .

たとえばMPEG2動画再生では、一瞬だけどこかのピクセルの色がおかしかったり、音声に少しノイズが乗ったところで視聴上の問題はほとんどない。仮に、そうした処理が1秒あたり10^-9の確率でメモリのビット化けを許容できるなら、DRAMのリフレッシュレートを今よりも下げて消費電力を17%削減できる。同様に、回路のタイミングエラーをある程度許容したり(駆動電圧を下げられる)、浮動小数点演算の仮数部の有効ビット数を減らすことでも省電力化を図れる。
このようなエラーや誤差を許容した「近似的な」プログラミングを行うために、EnerJと呼ばれるJavaの拡張が提案されている。これは、近似的でもよいデータをプログラム上で区別し、安全に取り扱えるようにしたものだ。以下は、EnerJによる近似的な変数の例である。

    int p;                // デフォルトでは、従来と同様に正確な値を保持する変数になる
    @Approx int a = ...;  // 正確さが要求されない変数には、近似を示すアノテーション @Approx を付ける
 
    p = a;                // こうした代入は許されない
    p = endorse(a);       // 近似的なデータを正確な変数に代入する必要がある場合は明示的に変換する

こうすることでEnerJランタイムは、近似的でも構わないデータや演算は省電力の(ただしエラー確率の高い)ハードに、正確性が求められる処理では通常のハードに割り当てて実行できるようになる。
おもしろいことに、近似的に扱う対象はプリミティブなデータ型やその演算に限らず、クラスやその振る舞いにも適用可能だ。つまり、本件はハードだけによる省電力アプローチではない。以下は、float配列の平均値を返す「近似的に」正しいコードの例である。

  @Approximable class FloatSet {         // 近似的なインスタンスを許容するクラス
    @Context float[] nums = ...;
    float mean() {                        // 配列の平均値を返す(通常版)
      float total = 0.0f;
      for (int i = 0; i < nums.length; ++i)
        total += nums[i];
      return total / nums.length;
    }
    @Approx float mean_APPROX() {         // 配列の平均値を返す(近似版)
      @Approx float total = 0.0f;
      for (int i = 0; i < nums.length; i += 2)
        total += nums[i];
      return 2 * total / nums.length;
    }
  }

このようなコードは従来のプログラミング言語でも可能だが、EnerJではシステム側が近似的なデータや処理を把握できるため、プログラマはより安全にコードを書けるようになる。たとえば、ハッシュ関数のような処理に対して近似データを渡してしまうようなコーディング上の誤りを防ぐことができる。
ビット化けやタイミングエラーを許容するようなハードウェアについては専用のものが必要であり、実現に向けての提案や設計を行っている段階だが、近似的アルゴリズムといったソフトウェア面での対応だけであれば現在のハード上でも実行できる。見積もりでは、ソフトウェア側の対応で30~50%、ハードウェア側の対応があればさらに20~25%(アプリケーションによっては50%)の省電力化が見込めるという。研究チームは近々、EnerJ をオープンソースで公開する意向とのことだ。

近似的プログラムはどのような局面で有効になるのか。/.J諸氏は何か良いアイディアをお持ちだろうか。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • AMDの3DNow! (スコア:3, 参考になる)

    by taka2 (14791) on 2011年06月07日 12時07分 (#1966037) ホームページ 日記

    今回のストーリーを見て思い出したのが、今は亡き「3DNow!」ですね。

    これはIntelのSSEに対抗してAMDが出したSIMD命令セットですが、3DNow!では、
    ・テーブルを使った低精度算出命令
    ・低精度の数値を元に、ニュートン法で精度を向上させる命令
    の2命令を使って逆数 [nifty.com]で平方根 [nifty.com]を求めるようになってました。

    正しい値が欲しいときは2命令必要ですが、低精度で十分なら1命令で高速に算出できるという。

    • Re:AMDの3DNow! (スコア:2, 興味深い)

      by Anonymous Coward on 2011年06月07日 14時18分 (#1966177)
      平方根をニュートン法で精度を上げるというのは計算科学の世界では初歩の初歩。
      昔から平方根の計算自体適当な近似値からそうやって正確な値にする場合が多い。

      直接計算科学の話から外れたところでも例えば1980年発行の「マイコン宇宙講座」で
      PC-8001の平方根計算は単精度の有効桁しかないのでニュートン法を使って倍精度の
      値を得る方法まで解説してます。思えばあれが計算科学に興味を持ったきっかけ。
      親コメント
      • by Anonymous Coward
        おじさん、なにいってんの
    • by syn2aki (38297) on 2011年06月07日 12時20分 (#1966051)
      > IntelのSSEに対抗してAMDが出したSIMD命令セット

      逆だよ、逆!!
      x86では3DNow!が先で、IntelのSSEが後。
      親コメント
    • Re:AMDの3DNow! (スコア:1, 参考になる)

      by Anonymous Coward on 2011年06月07日 12時35分 (#1966068)

      SSEに対抗したわけではなく(順序が逆なのは別のコメントがある通り)
      浮動小数点レジスタを転用した整数演算であるMMXを拡張し浮動小数点
      演算をできるようにして、少数演算の遅かったAMD CPUを救う対策でした。

      親コメント
  • by haf2 (42495) on 2011年06月06日 20時58分 (#1965761) 日記
    ハードウェアの世界では精度を犠牲にして回路を簡素化する事は良くあります。
    それが表に出てくる事はほとんどありませんが、1994年のPentium FDIV命令の話は有名ですよね。
    • 今は無きDEC Alphaを使っていたころ,プログラムの高速化の相談をDECのエンジニアにしました.
      その時に教えられたテクニックの一つが計算精度を落とすコンパイルオプションでした.
      致命的な計算エラーも起こらず,そこそこ高速化しました.
      計算時間の短縮って意味では,省電力に貢献でした.
      親コメント
      • by Anonymous Coward

        gccにも-ffast-mathオプションとかある

    • by haf2 (42495) on 2011年06月07日 20時30分 (#1966395) 日記
      冗談も言えないんじゃ真面目な話するしかないよね、と言う事で真面目な話。

      もろもろの事情で浮動小数点演算ができない時には、固定小数点演算で計算する事があります。
      固定小数点演算は早いのですが「合計を求める」など多数の数字を足し合わせる処理は苦手です。(オーバーフローの恐れがある)
      それでも合計を求めたい場合は最下位ビットを切り捨てながら計算する場合があります。

         int step;
         for (int i = 1;i < nums.length; i *= 2 ){          //加算をツリー状に行う
            step = i<<1;
            for (int j = 0; j < nums.length; j += step)
              nums[j]=(nums[j]+nums[j+i])>>1;            //加算して最下位ビットを切り捨て
         }

      ここでnumsは整数型、配列サイズは2のべき乗、符号付の場合は言語によって検討が必要です。
      頭から加算するんではなくツリー状に加算を行うのがポイント。

      合計がプラスかマイナスかなど精度の必要ない時に使います。
      配列サイズなど検討する必要がありますが、ベースバンド処理とかでたまに見かけます。

      JAVA初めて使ったんですが負の数の右シフトは負の数になるんですね。ちょっと意外でした。
      親コメント
      • by Anonymous Coward

        Javaに限らず、C/C++でも大抵はそうなります。
        算術シフトと論理シフト、記号はどっちも>>。
        ただのこの区別って仕様化されてたか、未定義だけど大抵そう実装されてるって話だったかは忘れた。

        • by Anonymous Coward

          Javaには符号無し整数型が存在しないので、 >> が算術右シフト、>>> が論理右シフトであると定められています(JLSに書かれた仕様)。
          C/C++に右シフトの演算子は >> の一種類しかありませんが、符号無し整数なら論理右シフトになることが保証されています(仕様)。負の符号付き整数を右シフトしたとき何が起きるかは処理系定義なので(仕様)算術右シフトになるかもしれませんし論理右シフトになるかもしれませんが、どちらなのかは処理系のマニュアルのどこかで文書化されているはずです(たとえばVC++の場合 [microsoft.com])。そもそも負数の内部表現が2の補数であるとは限りませんし。

    • by Anonymous Coward

      > 1994年のPentium FDIV命令の話は有名ですよね。
      あれは性能や簡素化のためじゃなくて単なるバグだろ。

      • by Anonymous Coward

        バグというより数表の転記ミス
        呼び方はどうであれ、速度も精度も稼ぐ設計でしたね、あれは。

      • by Anonymous Coward

        おもおかねらいなんだろうから、つっこんじゃらめぇ!

  • by reininn (35924) on 2011年06月07日 13時29分 (#1966130)
    そもそも、Mpeg や Jpeg などの非復元圧縮をすでに採用している
    画像処理や、音声処理には最適だと思います。
    また、ゲームだったら、昔のインベーダーゲームみたいに時々適当に間違った方が楽しいかも。
  • by siva-jp (18925) on 2011年06月08日 13時00分 (#1966789)

    計算尺使えってこった。
    …使ってるとこは見たことしかないけど。

    #うちの親父の世代は、工業高校だと授業で習ったらしいが。

  • by d5 (42418) on 2011年06月07日 11時49分 (#1966021)

    だいたいあってる [nicovideo.jp]とか、こまけぇこたぁいいんだよ [paradisearmy.com]までいけるとよいかもしれない。

  • 勤務先の (スコア:1, おもしろおかしい)

    by Anonymous Coward on 2011年06月07日 12時18分 (#1966047)
    給与計算システムに採用されない事を切に願う。
  • by USH (8040) on 2011年06月07日 14時02分 (#1966168) 日記

    マニアには起られるかも知れないが、
    ゲームなんて、適当でいいのでは?
    当る当らないは時の運とか。

    あと、物流の最適配送探索なんて、どうせNP完全問題を近似解で解いてるのだから、
    誤差あってもパフォーマンスは変わらないのでは?

    • by Anonymous Coward on 2011年06月07日 18時20分 (#1966322)

      省電力を目指すゲーム、というのは良さそうだ。
      プレイヤーがSecond Life [itmedia.co.jp]を5分間プレイしていたら、
      だんだん画面がぼやけて、気がついたら
      富士通ハビタット [impress.co.jp]の画面で、二次元アバターを操作している、
      という設定も大丈夫。これで大幅に電力節約。なあに、三次元でも二次元でも、
      ユーザは気にしないから。かえって楽しくなったりする。

      親コメント
    • by digoh (17917) on 2011年06月08日 10時36分 (#1966654) 日記

      ゲームだから、ゲームじゃないから、という分類は不適当かと。
      たとえば物理演算を利用した娯楽用映像であれば、科学技術計算のものと比べ誤差許容範囲が大きくてもいいよね、とかいうのであればいいですけど、
      対戦格闘ゲームのダメージ計算とかMMORPG(要はネットでやるリアルタイムRPG)でのダメージ計算とかで「適当」にしてしまうと……

      厳密に解析されて、プログラマがどんだけ適当な仕様を組んだのかが周知されます:p
      (ゲーム性という観点では問題にならない場合が大部分ですが)

      親コメント
  • by Anonymous Coward on 2011年06月06日 14時40分 (#1965560)
  • by Anonymous Coward on 2011年06月07日 11時28分 (#1965998)
    誤差を許容しないのはコンピュータではなく人間のほうだという点をどう克服するか。
    • Re:実用面での課題 (スコア:1, おもしろおかしい)

      by Anonymous Coward on 2011年06月07日 11時31分 (#1966001)
      ゆとり教育する
      親コメント
      • Re:実用面での課題 (スコア:1, すばらしい洞察)

        by Anonymous Coward on 2011年06月07日 16時19分 (#1966244)
        野暮を承知でコメントすると、
        誤差を許容できるか否か。どこまでなら、許容できるか。
        このあたりの判断は、誤差を無いものと考える設計より、
        一段上のレベルが必要。下手に使うと失敗する罠。
        親コメント
  • by Anonymous Coward on 2011年06月07日 11時35分 (#1966006)
    継続的にくり返し読み書きするDRAMは、読み書き自体がリフレッシュになるんで リフレッシュサイクルはまったく実行しないのが昔からのハードウエア実装方法です。
    • by chocopa (14067) on 2011年06月07日 12時24分 (#1966057)

      そういや、90年代前半にDRAMのタイミング系を自作してたときに、1秒以上アクセスもリフレッシュしなくても記憶が残っていて驚いた。

      親コメント
      • by dokodokodon (19060) on 2011年06月07日 14時38分 (#1966193) 日記
        「プロセッサを支える技術」310ページ曰く、

        実は、DRAMの大部分の記憶セルは、1秒くらい経っても正しく情報を読み出すことができます。
        [省略]
        (製造のばらつきを考慮して)規格としては64msという安全ラインが設定されているわけです。

        だそうです。

        親コメント
        • by Anonymous Coward

          32bit Windowsで余ったメモリをRAMディスクにするのが流行ったとき、RAMディスクにウォームスタート機能を付ける実験をしてみたことがあります。
          大部分の内容は残っているのですが、ところどころ壊れているという状態なんでRAMディスクとしてはちょっと使い物になりませんでした。誤差を許容するような用途ならなにか使いみちがあるかもしれません。

        • by Anonymous Coward
          リーク電流は温度等のパラメータ変動によって指数関数的に増大することもあるので、桁がいくつも違うくらいの十分なマージンが必要
          TEGでセル単体のテストをすれば、もっと良いホールド特性が得られることもある
    • by Anonymous Coward
      そうか、リフレッシュ・コントローラは不要だったのか!!!
      • by chocopa (14067) on 2011年06月07日 12時33分 (#1966066)

        リフレッシュが要らないのはアクセスした行だけ、基本的に破壊読み込みですぐに修復するから記憶が新しくなったんだったと思う。

        親コメント
      • by gedo (7079) on 2011年06月07日 15時21分 (#1966214) 日記
        補足しておくと、VRAMのように常に定期的に全Rowアクセスされる部分は、あえてリフレッシュ用の回路を省略したり、また割り込みか何かで定期的にソフト的に空読みする前提でリフレッシュ回路省略というのを聞いたことがあります。
        親コメント
        • by taka2 (14791) on 2011年06月07日 17時49分 (#1966302) ホームページ 日記

          「DRAMのリフレッシュって何をしてるの?」って人のためにもうちょっと解説しておくと、

          DRAMは、コンデンサに電荷を貯めることで情報を記憶している分けですが、コンデンサに溜まった電荷は漏れ電流などによって徐々に抜けていきます。
          そのため、定期的に充電しないと記憶内容が消えてしまいます。そういう「再充電処理」がリフレッシュ。

          ところで、このDRAMでデータを記憶するコンデンサの「セル」の大きさは非常に微小であり、そのセルに至るまでの配線の方が長いので、
          セルよりも、配線の寄生容量の方が、桁違いに静電容量が大きいです。

          そのため、DRAMの読み出しでは、

          セルに電荷が貯まっている時→セルに溜まった電荷が配線に流れ、セルは放電、配線容量というコンデンサは若干充電する形になり、ほんのちょっぴり配線の電圧が上がる

          セルに電荷が貯まっていない時→配線容量に溜まった電荷がセルに流れ、セルは充電、配線容量というコンデンサは若干放電する形になり、ほんのちょっぴり配線の電圧が下がる

          といった電気の流れになり、この「配線の電圧がほんのチョッピリ上がるか下がるか」を検出して1/0を出力します。

          このとき、セルの電圧はほぼ配線の電圧になるまで充放電されてしまいますから、読み出し処理によって記憶内容は失われてしまいます。
          そのため、DRAMでは、読み出し処理後には、読みとったデータを元に1行まるごと再度書き込み(セルの充放電)処理を行うようになっています。

          このように、「DRAMの読み取り処理」には必ず「セルの再充電処理」がセットになっており、
          リフレッシュとは「コンデンサの電荷が抜けきる前に定期的に空読み処理を行う」ものなわけです。

          というわけで、そもそも「定期的に全セルに読みとり処理が行われる」ことが保証されているのであれば、リフレッシュは不要になるわけです。

          親コメント
  • by Anonymous Coward on 2011年06月07日 12時25分 (#1966058)

    情報科学の分野では、近似アルゴリズムや乱択アルゴリズムなどがかなり研究されている。ほかにもヒューリスティクスを利用した方法も広く応用されている。
    カーナビの経路探索や、暗号に必要な素数の生成など、誤差を許容することで劇的な高速化を実現しているものは、日常的に使われている。

    • by TarZ (28055) on 2011年06月07日 13時52分 (#1966155) 日記

      それは特定のアプリケーションにおいて、利用する側も「(主に計算量的な要請から)近似的に得た解」と理解しているケースですよね。EnerJで提案されているのはもっと踏み込んだものです。

      • 半導体の進歩ペースがそろそろ厳しくなっているし、なんでもかんでも厳密性・正確性を求めていたら電力面が厳しい。
      • 日本人の平均身長出すのになにも1億件のデータを集計しないでもいいわけだし、日常的な処理でももっともっと近似的な処理を取り入れていくしかないんじゃない?
      • それをプログラマが便利に、かつ安全に扱うにはどうすればいいだろう?
      • 言語に近似的なデータ型を導入して、静的に型を評価して…ほら、コード上で一緒に扱っても勝手に混ざることがないので安全だし、とっても便利!

      たとえばタレコミにあるコード例でいえば、FloatSetのインスタンス s が近似値を扱っている場合は s.mean() は「コンパイラが自動的に」mean_APPROX() のほうを呼ぶようにするのです。

      親コメント
      • by Anonymous Coward

        たとえばタレコミにあるコード例でいえば、FloatSetのインスタンス s が近似値を扱っている場合は s.mean() は「コンパイラが自動的に」mean_APPROX() のほうを呼ぶようにするのです。

        そうではなくて、mean_APPROX()を使うと、それで得られる値は近似値としてしか扱えず、また、近似値の集合にはmean()を使うことはできないって事じゃないの?

        自動的に呼ぶものを変えるんじゃなくて、暗黙の型変換は一方向しか認めないことを利用しているだけでしょ。

        #暗黙の型変換を一方向しか認めないことはC++でよくやるけど、汎用的なのは書いたことがない。テンプレートを使えばできそうな気もするが。

    • by Anonymous Coward

      全然違うよ。
      まず話のカテゴリからして違う。
      これはインターネット由来の文字列はdirtyビットを付けて区別しましょう、という類と同じカテゴリの話。

  • by Anonymous Coward on 2011年06月07日 13時06分 (#1966098)

    圧縮するから展開処理に電力を使うんであって、圧縮しなければ省電力になるんだよ!

    • by Anonymous Coward on 2011年06月07日 13時34分 (#1966136)

      転送プログラム(scpとか)なんかだと圧縮オプション普通にありますよ
      ・圧縮(転送サイズは小さくなるけどCPU食う)
      ・非圧縮(転送サイズは大きくなるけどCPU食わない)

      圧縮処理に時間がかからない分、非圧縮のほうが転送時間短い場合もまれに良くある

      親コメント
  • by Anonymous Coward on 2011年06月07日 13時33分 (#1966133)

    詳細に描画すると複雑なため電力を消費するから
    あれは省電力のためだったのか。

    • by Anonymous Coward
      俺ぐらいになるとPCを立ち上げなくてもいけるぜ!
  • by Anonymous Coward on 2011年06月07日 14時35分 (#1966189)

    これからは2.5次元や2次元の時代ですよ。

  • by Anonymous Coward on 2011年06月07日 16時43分 (#1966258)

    (元論文はまだ読んでませんが)このテの誤差を許容するコンピューティングは省電力だけでなく並列化にも劇的に効くことがあるので将来性はあると思う。実行順序制約を無視できる箇所に印を付けたりとか、同じPLDI2011にも幾つか出てるし。浮動小数点計算の結合則をガンガン使って精度を若干犠牲にしてループのパイプライニングを可能にするコンパイラは既にあるけど、それの延長みたいな。

    • by Anonymous Coward

      計算精度を指定できるライブラリが使えるのなら、処理深さが一定
      になってスケジューリングが楽になるよね。

      GPUやBLASとかの高速行列演算ライブラリは、すでに実装している
      のかも知れないけど。

  • by Anonymous Coward on 2011年06月07日 19時08分 (#1966350)
    彼らが自らのエラーを認められるようになれば何かが変わるだろうか?
    早期検知とリトライの仕組みが必要?
typodupeerror

人生unstable -- あるハッカー

読み込み中...