誤差を許容することで劇的な省電力を目指すコンピューティング 52
家電とかかな 部門より
大規模化するデータセンタや、より小型で高性能になるモバイル機など、コンピュータの省電力化は近年ますます重要になっている。こうしたデジタル計算機の動作にあたっては、常に正確な動作を得られるように十分なマージンを設けた電力を使っている。DRAM の内容が揮発しないような短いリフレッシュ間隔や、回路でタイミングエラーを発生させないための高い駆動電圧といったものだ。しかし、アプリケーションによってはそこまで正確な結果を要求しないものもある。
ワシントン大学の研究チームは、ある程度の誤差を許容することで劇的な省電力を目指すハードウェアと、それをソフトウェア面でサポートするための言語を提案している。本件は、米サンノゼで開催されている PLDI 2011 で発表される (Session 3a.“EnerJ: Approximate Data Types for Safe and General Low-Power Computation”) 。
たとえば MPEG-2 動画再生では、一瞬だけどこかのピクセルの色がおかしかったり、音声に少しノイズが乗ったところで視聴上の問題はほとんどない。仮に、そうした処理が 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, 参考になる)
今回のストーリーを見て思い出したのが、今は亡き「3DNow!」ですね。
これはIntelのSSEに対抗してAMDが出したSIMD命令セットですが、3DNow!では、
・テーブルを使った低精度算出命令
・低精度の数値を元に、ニュートン法で精度を向上させる命令
の2命令を使って逆数 [nifty.com]で平方根 [nifty.com]を求めるようになってました。
正しい値が欲しいときは2命令必要ですが、低精度で十分なら1命令で高速に算出できるという。
Re:AMDの3DNow! (スコア:2, 興味深い)
昔から平方根の計算自体適当な近似値からそうやって正確な値にする場合が多い。
直接計算科学の話から外れたところでも例えば1980年発行の「マイコン宇宙講座」で
PC-8001の平方根計算は単精度の有効桁しかないのでニュートン法を使って倍精度の
値を得る方法まで解説してます。思えばあれが計算科学に興味を持ったきっかけ。
Re: (スコア:0)
Re:AMDの3DNow! (スコア:1)
逆だよ、逆！！
x86では3DNow!が先で、IntelのSSEが後。
Re:AMDの3DNow! (スコア:1, 参考になる)
SSEに対抗したわけではなく（順序が逆なのは別のコメントがある通り）
浮動小数点レジスタを転用した整数演算であるMMXを拡張し浮動小数点
演算をできるようにして、少数演算の遅かったAMD CPUを救う対策でした。
ハードウェアでは昔からよく有る事 (スコア:2, おもしろおかしい)
それが表に出てくる事はほとんどありませんが、1994年のPentium FDIV命令の話は有名ですよね。
Re:ハードウェアでは昔からよく有る事 (スコア:3, 興味深い)
その時に教えられたテクニックの一つが計算精度を落とすコンパイルオプションでした．
致命的な計算エラーも起こらず，そこそこ高速化しました．
計算時間の短縮って意味では，省電力に貢献でした．
Re: (スコア:0)
gccにも-ffast-mathオプションとかある
Re:ハードウェアでは昔からよく有る事 (スコア:2, 参考になる)
もろもろの事情で浮動小数点演算ができない時には、固定小数点演算で計算する事があります。
固定小数点演算は早いのですが「合計を求める」など多数の数字を足し合わせる処理は苦手です。(オーバーフローの恐れがある)
それでも合計を求めたい場合は最下位ビットを切り捨てながら計算する場合があります。
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初めて使ったんですが負の数の右シフトは負の数になるんですね。ちょっと意外でした。
Re: (スコア:0)
Javaに限らず、C/C++でも大抵はそうなります。
算術シフトと論理シフト、記号はどっちも>>。
ただのこの区別って仕様化されてたか、未定義だけど大抵そう実装されてるって話だったかは忘れた。
Re: (スコア:0)
Javaには符号無し整数型が存在しないので、 >> が算術右シフト、>>> が論理右シフトであると定められています(JLSに書かれた仕様)。
C/C++に右シフトの演算子は >> の一種類しかありませんが、符号無し整数なら論理右シフトになることが保証されています(仕様)。負の符号付き整数を右シフトしたとき何が起きるかは処理系定義なので(仕様)算術右シフトになるかもしれませんし論理右シフトになるかもしれませんが、どちらなのかは処理系のマニュアルのどこかで文書化されているはずです(たとえばVC++の場合 [microsoft.com])。そもそも負数の内部表現が2の補数であるとは限りませんし。
Re: (スコア:0)
> 1994年のPentium FDIV命令の話は有名ですよね。
あれは性能や簡素化のためじゃなくて単なるバグだろ。
Re: (スコア:0)
バグというより数表の転記ミス
呼び方はどうであれ、速度も精度も稼ぐ設計でしたね、あれは。
Re: (スコア:0)
おもおかねらいなんだろうから、つっこんじゃらめぇ！
画像や音声関係？ (スコア:2)
画像処理や、音声処理には最適だと思います。
また、ゲームだったら、昔のインベーダーゲームみたいに時々適当に間違った方が楽しいかも。
原点回帰 (スコア:2)
計算尺使えってこった。
…使ってるとこは見たことしかないけど。
＃うちの親父の世代は、工業高校だと授業で習ったらしいが。
ダイザッパーとか (スコア:1)
だいたいあってる [nicovideo.jp]とか、こまけぇこたぁいいんだよ [paradisearmy.com]までいけるとよいかもしれない。
勤務先の (スコア:1, おもしろおかしい)
Re: (スコア:0)
とは限らないのに。
Re:勤務先の (スコア:1)
毎月交互に一桁増えて一桁減るとうれしい。
５桁くらい増えて、次の月は５桁へっても文句は言わない。
マーフィーの法則って知ってます？ (スコア:0)
Re: (スコア:0)
-- マーフィー
ゲーム (スコア:1)
マニアには起られるかも知れないが、
ゲームなんて、適当でいいのでは？
当る当らないは時の運とか。
あと、物流の最適配送探索なんて、どうせNP完全問題を近似解で解いてるのだから、
誤差あってもパフォーマンスは変わらないのでは？
気がつけば二次元ゲームに突入 (スコア:1, おもしろおかしい)
省電力を目指すゲーム、というのは良さそうだ。
プレイヤーがSecond Life [itmedia.co.jp]を5分間プレイしていたら、
だんだん画面がぼやけて、気がついたら
富士通ハビタット [impress.co.jp]の画面で、二次元アバターを操作している、
という設定も大丈夫。これで大幅に電力節約。なあに、三次元でも二次元でも、
ユーザは気にしないから。かえって楽しくなったりする。
Re:ゲーム (スコア:1)
ゲームだから、ゲームじゃないから、という分類は不適当かと。
たとえば物理演算を利用した娯楽用映像であれば、科学技術計算のものと比べ誤差許容範囲が大きくてもいいよね、とかいうのであればいいですけど、
対戦格闘ゲームのダメージ計算とかMMORPG（要はネットでやるリアルタイムRPG）でのダメージ計算とかで「適当」にしてしまうと……
厳密に解析されて、プログラマがどんだけ適当な仕様を組んだのかが周知されます:p
（ゲーム性という観点では問題にならない場合が大部分ですが）
関連ストーリー？ (スコア:0)
実用面での課題 (スコア:0)
Re:実用面での課題 (スコア:1, おもしろおかしい)
Re:実用面での課題 (スコア:1, すばらしい洞察)
誤差を許容できるか否か。どこまでなら、許容できるか。
このあたりの判断は、誤差を無いものと考える設計より、
一段上のレベルが必要。下手に使うと失敗する罠。
DRAMのリフレッシュ (スコア:0)
Re:DRAMのリフレッシュ (スコア:2)
そういや、90年代前半にDRAMのタイミング系を自作してたときに、1秒以上アクセスもリフレッシュしなくても記憶が残っていて驚いた。
Re:DRAMのリフレッシュ (スコア:2, 参考になる)
だそうです。
Re: (スコア:0)
32bit Windowsで余ったメモリをRAMディスクにするのが流行ったとき、RAMディスクにウォームスタート機能を付ける実験をしてみたことがあります。
大部分の内容は残っているのですが、ところどころ壊れているという状態なんでRAMディスクとしてはちょっと使い物になりませんでした。誤差を許容するような用途ならなにか使いみちがあるかもしれません。
Re: (スコア:0)
TEGでセル単体のテストをすれば、もっと良いホールド特性が得られることもある
Re: (スコア:0)
Re:DRAMのリフレッシュ (スコア:2)
リフレッシュが要らないのはアクセスした行だけ、基本的に破壊読み込みですぐに修復するから記憶が新しくなったんだったと思う。
Re:DRAMのリフレッシュ (スコア:1)
Re:DRAMのリフレッシュ (スコア:4, 参考になる)
「DRAMのリフレッシュって何をしてるの?」って人のためにもうちょっと解説しておくと、
DRAMは、コンデンサに電荷を貯めることで情報を記憶している分けですが、コンデンサに溜まった電荷は漏れ電流などによって徐々に抜けていきます。
そのため、定期的に充電しないと記憶内容が消えてしまいます。そういう「再充電処理」がリフレッシュ。
ところで、このDRAMでデータを記憶するコンデンサの「セル」の大きさは非常に微小であり、そのセルに至るまでの配線の方が長いので、
セルよりも、配線の寄生容量の方が、桁違いに静電容量が大きいです。
そのため、DRAMの読み出しでは、
セルに電荷が貯まっている時→セルに溜まった電荷が配線に流れ、セルは放電、配線容量というコンデンサは若干充電する形になり、ほんのちょっぴり配線の電圧が上がる
セルに電荷が貯まっていない時→配線容量に溜まった電荷がセルに流れ、セルは充電、配線容量というコンデンサは若干放電する形になり、ほんのちょっぴり配線の電圧が下がる
といった電気の流れになり、この「配線の電圧がほんのチョッピリ上がるか下がるか」を検出して1/0を出力します。
このとき、セルの電圧はほぼ配線の電圧になるまで充放電されてしまいますから、読み出し処理によって記憶内容は失われてしまいます。
そのため、DRAMでは、読み出し処理後には、読みとったデータを元に1行まるごと再度書き込み(セルの充放電)処理を行うようになっています。
このように、「DRAMの読み取り処理」には必ず「セルの再充電処理」がセットになっており、
リフレッシュとは「コンデンサの電荷が抜けきる前に定期的に空読み処理を行う」ものなわけです。
というわけで、そもそも「定期的に全セルに読みとり処理が行われる」ことが保証されているのであれば、リフレッシュは不要になるわけです。
アルゴリズム (スコア:0)
情報科学の分野では、近似アルゴリズムや乱択アルゴリズムなどがかなり研究されている。ほかにもヒューリスティクスを利用した方法も広く応用されている。
カーナビの経路探索や、暗号に必要な素数の生成など、誤差を許容することで劇的な高速化を実現しているものは、日常的に使われている。
Re:アルゴリズム (スコア:2)
それは特定のアプリケーションにおいて、利用する側も「（主に計算量的な要請から）近似的に得た解」と理解しているケースですよね。EnerJで提案されているのはもっと踏み込んだものです。
↓
↓
↓
たとえばタレコミにあるコード例でいえば、FloatSetのインスタンス s が近似値を扱っている場合は s.mean() は「コンパイラが自動的に」mean_APPROX() のほうを呼ぶようにするのです。
Re: (スコア:0)
そうではなくて、mean_APPROX()を使うと、それで得られる値は近似値としてしか扱えず、また、近似値の集合にはmean()を使うことはできないって事じゃないの？
自動的に呼ぶものを変えるんじゃなくて、暗黙の型変換は一方向しか認めないことを利用しているだけでしょ。
＃暗黙の型変換を一方向しか認めないことはC++でよくやるけど、汎用的なのは書いたことがない。テンプレートを使えばできそうな気もするが。
Re: (スコア:0)
全然違うよ。
まず話のカテゴリからして違う。
これはインターネット由来の文字列はdirtyビットを付けて区別しましょう、という類と同じカテゴリの話。
これからは非圧縮の時代 (スコア:0)
圧縮するから展開処理に電力を使うんであって、圧縮しなければ省電力になるんだよ！
Re:これからは非圧縮の時代 (スコア:1, おもしろおかしい)
転送プログラム(scpとか)なんかだと圧縮オプション普通にありますよ
・圧縮(転送サイズは小さくなるけどCPU食う)
・非圧縮(転送サイズは大きくなるけどCPU食わない)
圧縮処理に時間がかからない分、非圧縮のほうが転送時間短い場合もまれに良くある
モザイク (スコア:0)
詳細に描画すると複雑なため電力を消費するから
あれは省電力のためだったのか。
Re: (スコア:0)
劇的な次元圧縮 (スコア:0)
これからは2.5次元や2次元の時代ですよ。
並列化にも使おうぜ (スコア:0)
（元論文はまだ読んでませんが）このテの誤差を許容するコンピューティングは省電力だけでなく並列化にも劇的に効くことがあるので将来性はあると思う。実行順序制約を無視できる箇所に印を付けたりとか、同じPLDI2011にも幾つか出てるし。浮動小数点計算の結合則をガンガン使って精度を若干犠牲にしてループのパイプライニングを可能にするコンパイラは既にあるけど、それの延長みたいな。
Re: (スコア:0)
計算精度を指定できるライブラリが使えるのなら、処理深さが一定
になってスケジューリングが楽になるよね。
GPUやBLASとかの高速行列演算ライブラリは、すでに実装している
のかも知れないけど。
お役所♪ (スコア:0)
早期検知とリトライの仕組みが必要？