遺伝的アルゴリズムでカーネルチューニング 72
ストーリー by Oliver
ワークロードが一定なら最強? 部門より
ワークロードが一定なら最強? 部門より
Linuxカーネルを遺伝的アルゴリズムを使って動的にチューンするパッチをJake Moilanenがlkmlに投稿した。このパッチはanticipatory IOスケジューラと現在-mmでテストされているzaphod CPUスケジューラを改造し、遺伝的アルゴリズムを提供する新しいカーネルライブラリを使って動作中に特定のワークロードにあわせて常に自己を自動チューンするように改善した。まだ荒削りながら、UnixbenchおよびSpecJBBで1-3%の性能改善が見られたという。パッチはあくまで実験であり、特にキモである評価関数にまだまだ改善の余地があるそうだ。
遺伝的アルゴリズムは突然変異と自然淘汰による生命の進化をモデルにした手法で、このパッチではさまざまなスケジューラのパラメータの組合せを「子」として合成し、それぞれを一定時間、実際のシステムで動かした後に評価しする。そして、評価の悪かった半分を捨て、評価のよかった半分のパラメータを少し変異させた新しい子を作成し、評価のサイクルが繰り返される。理論上は時間と共に特定の環境に最適なパラメータに収束する。
動的チューニングの有効性 (スコア:1)
実際のシステムで動的チューニングって使える物なのでしょうか?
動作条件が明確になっているシステムの場合は, それに合わせて手で固定的なチューニングを施した方が安定した高性能を出すでしょう. 逆に動作条件が, 例えば時間帯や日付で変動するようなシステムの場合には動作条件の変動と共にチューンの効果が変わり, システム性能が一定しないなんてことにもなりかねません. そのため, 最善ではなくてもそこそこのチューニングにしておくことにより, 性能を安定化させるなんてことも多くあります.
どうも私の個人的な感覚としては, 動的自動チューンって今だ技術的なお遊びの段階を抜け出ていないように思うのですが, いかがでしょう?
Re:動的チューニングの有効性 (スコア:1)
言われる部分も多いだろうけど、パラメータをうまく選べば
遺伝的アルゴリズムは結構使えるんじゃないかな。
チューニングの対象によって全くの役立たずになる場合もある
だろうけど、ナップサック問題や巡回セールスマン問題のよう
な評価関数を設定可能なものであれば、かなり使えそうな予感。
システムのチューニングを、単なる計算困難な問題という程度
にまでモデル化できるのかどうかに興味あります。
Re:動的チューニングの有効性 (スコア:1, 興味深い)
Linuxでsysctl -Aしたときに表示される
- net.ipv4.tcp_rmem
- net.ipv4.tcp_wmem
- net.ipv4.tcp_mem
の3つのベクトル値は、動的なチューニング値のためのパラメタ です。Re:動的チューニングの有効性 (スコア:1, 興味深い)
気になるところ (スコア:1)
２．個体数の確保
適合度って何を基準に出しているのかしらん？処理時間？
あと一つのPCで複数の個体を保持しているのかなぁ。
１PC１個体にして、ネットワーク経由で交配、とか妄想してみたけど違うみたいですね。そうだったら正に「ネットは広大」という事でかなりアレゲなんですが。
Re:気になるところ (スコア:1, 余計なもの)
また個体は１台のPC内に複数保持しないと交配できないため、もちろんそのようになっています。
「ネットワーク越しで交配」というのは本来の意味が失われてしまいます。
なぜならばその「PC」という環境に適合するようにチューニングすることが目的であるのですから。
ネットワーク上にはまったく同じ環境を持つPCのみが存在するようなシステムでは話は別かもしれませんが。
Re:気になるところ (スコア:1)
きっとあるはず。
なにがしかの値が変数として評価関数のなかに
取り込まれるとして、似た環境の（つまり変数に入る
なにがしかが近い）PCのパラメータ値を取り込んでくると、
比較的有効な初期パラメータとして収束するまでの
時間を短縮できるんじゃないかなぁと思ったりしました。
Re:気になるところ (スコア:1)
GA っぽいですが、 一つのコンピュータ上で進化するなら、
Simulated Annealing [google.com] が 良いのでは？
実際には、試してみないと分からないでしょうが。
Re:気になるところ (スコア:1)
ただ、連続・・・ですかね？
パラメータの微小変化に対してその結果が連続的に変化するのかどうかです。
コンピュータ内部事情には詳しくないので分かりませんが、
単純に「スケジューリング問題」として捉えれば切った貼ったのGAが良いように思えます。
もちろんおっしゃる通りやってみないことには分かりませんが、
何というか心をくすぐられる話題ですね。
Re:気になるところ (スコア:1)
惹かれてしまふ。
SA は局所解脱出方法だよなと考えてるので、システムの
チューニングとに対してはどうだろうかという思いと、
モデルをそのような式で表現できたらおもしろいなという
思いが交錯しておりまする。
いやいや、ほんとおもしろい話題だな。
Re:気になるところ (スコア:1)
パラメータ更新まで間隔が開きそうなんで、
どうなんだろうと思ったのが大きいです。
ただ、GA の方が各個体のテストを複数回行うことで
誰もユーザーの使ってない状況に最適化しちゃうとか、
状況依存には強かったりするのかな？
なんて、無責任に妄想しております。
Re:気になるところ (スコア:1)
ですから、「GAよりもSAのほうが良い」というのは奇妙な感じです。
--kwbt
Re:気になるところ (スコア:1)
エネルギー関数が小さくなった場合には確率1 で、
大きくなった場合には、確率 exp(-dE/T) で
新しいパラメータを受理する。
で、徐々に T を小さくする。
T が 0 になれば、最適解になってる。
っていうものじゃないでしょうか？
Re:気になるところ (スコア:1)
最小化(評価関数なら普通は最適化＝最大化かも)
のアルゴリズムです。
>> T が 0 になれば、最適解になってる。
> divided by zero が気になるのですが、
実際に 0にすると言う意味ではなくて、
T-> 0 の極限で最適解になると言う意味です。
>> 大きくなった場合には、確率 exp(-dE/T) で
上では書いてませんでしたが、 dE はパラメータ
を変化させた場合の E の増分です。
T が大きい(無限大)と、
dE にかかわらず、 確率は 1(=exp(0)) になりますので
基本的にはランダムウォークするけれども、
T が小さくなってくると E が大きくなる方向へは、
移動しにくくなります(0≒exp(-∞))。
で、T が十分に小さくなっていれば、E が最小となるところ
に落ち着くと言う感じです。
T は時間経過とともに徐々に小さくするようにします。
このスケジューリングの仕方は知りません。(^-^;
Re:気になるところ (スコア:1)
SA(Simulated Annealing)とGA(Genetic Algorithm)は最適化問題を解くための
まったく異なるアルゴリズムであり、互いに包含関係なんかはないです。
SAよりもGAの方が局所解に陥りにくいってことで、SAからGAへって流行があったものだから
「GAはSAの改良版」って感じでとらえられることが多いですけど
Re:気になるところ (スコア:1)
んな、当たり前でんがな。GAの適合度は普通、評価関数から算出しますし。
tunedとはどう定義されてるのかなぁ、という事ですね。処理速度なのか？メモリ占有率なのか？安全性なんかもあるかもしれませんし。GAの良し悪しは大体、評価関数で決まりますから。
> 「ネットワーク越しで交配」というのは本来の意味が失われてしまいます。
おおっ、確かにそのとおりですね。
> また個体は１台のPC内に複数保持しないと交配できないため、もちろんそのようになっています。
プロセスが起動した度に個体が発生するか、同じプロセスが同時に動いているような感じでしょうか？
元記事だけではちょっと理解できませんでした。
Re:気になるところ (スコア:1)
すみませんでした。
リンク先のサイトを(ざっとですが)見てみたところ、あらかじめパラメータセットを大きなテーブルに用意しておいて、それを一つ一つ試して全てのパラメータセットを試し終わった後で適合度を計算し、・・・(以下一般的なGAの手順)という感じです。
つまりスケジューリングプロセスは一つですね。
＃所々言い切っていますが、間違っていたらごめんなさい
Re:気になるところ (スコア:1)
>
>すみませんでした。
>
>リンク先のサイトを(ざっとですが)見てみたところ、あらかじめパラメータセットを大きなテーブルに用意しておいて、それを一つ一つ試して全てのパラメータセットを試し終
>わった後で適合度を計算し、・・・(以下一般的なGAの手順)という感じです。
いや、疑問とされているのは、
「評価に用いる適合度は、どういった要因をどう組み合わせて定義しているのでしょう?」
ということですよね。それがGAのキモ。
Re:気になるところ (スコア:1)
> 失われてしまいます。
> なぜならばその「PC」という環境に適合するように
> チューニングすることが目的であるのですから。
より広範囲で交配する種の方が多様性を持つため
より生き残るんで良いのでは、という素人の疑問が・・・。
ああそうか、その多様性ゆえに、使いにくい PC を
「種」のためにがまんして使わなきゃいけないユーザが
出ちゃうって事か。
ということは、ひとつのPC という狭い範囲で交配し続けた
遺伝的アルゴリズムカーネルは、なんらかの破壊的パラダイム
シフトにきわめて脆弱になる・・Σ(ﾟДﾟ
閾値は 0 で
Re:気になるところ (スコア:1)
これが、実行コード（実マシンコード）の動的最適化迄進むと、「破壊的パラダイムシフトへの脆弱」と言う懸念が本当の物になると思うので慎重に進めないとまずいですが…
Re:気になるところ (スコア:1)
> 収まってるので、心配するような状況は極めて
> 限られるのではないかと。
実マシンコードとは独立した、
ポータブルな進化結果なんですね。
素人のたとえ話で申し訳ないですが、
いいなぁ、象の鼻、と思ったら
その遺伝子だけもらって組み換えちゃえば
いいとかそんな感じかな。
待てよ、そこで勘違いした一般消費者の
遺伝子組み換え OS 反対運動が勃発して
・・・・・Σ(ﾟДﾟ
閾値は 0 で
Re:気になるところ (スコア:1)
Linuxマシンを沢山沢山繋いで、「同じ(少なくとも対称な)」仕事をさせる、という最近よく聞く話の場合は、
有効かも知れないってことですね。
Grid(ってんだっけ)なLinuxスパコンが、自ら勝手にパフォチューしてくれる、みたいな？
あ。でも、与える課題(走らせるプログラムとかデータ傾向とか)を変えるたびに
天変地異になっちゃうわけですね。
こりゃ、色々あるプログラムやデータを、どうやって「同じor違う」と見なすか、という問題に
帰着するのかな。
解空間の効率的な探索法 (スコア:1, 興味深い)
ヒューリスティックで，それゆえ簡単に使えちゃうんだけどあまり性能は良くない．
吉野家コピペ風に言えば，”まぁ，お前らど素人は遺伝的アルゴリズムでも使ってな”というところでしょうか？
Re:解空間の効率的な探索法 (スコア:2, 参考になる)
典型的なヒューリスティクスでしょう。
> ヒューリスティックアルゴリズムの対極に位置するのが
> 遺伝的アルゴリズムですよ。
「対極」ってのが何を意味してるのか今いち不明ですが、探索空間を完全に探索しつくすのではなく、確率的に「適当」に大局的近似解を探すのは、ヒューリスティスクス以外の何物でもありません。確率的な要素(突然変異など)を除いてしまうと、局所解に簡単につかまってしまい、最適解を求めることができなくなります。
> マシンパワーにまかせて探索するわけで。
適当なところでカットオフを持たせて計算を終了させるのでヒューリスティクスになるのですが、仮にカットオフをなくして完全に探索させようとしても、確率的な要素があるために完全性を保証できません。この点から言ってもヒューリスティックです。
α-βみたいなものだけがヒューリスティクス、という誤解でもしてるのかな。
Re:解空間の効率的な探索法 (スコア:1)
GAは一般に組み合わせ問題なんかを解くためのスキームです。
α-βみたいなものがヒューリスティクスなわけですが、GAやSAといった手法はそれよりももう一段階汎用です。
Re:解空間の効率的な探索法 (スコア:2, 参考になる)
アルゴリズムってのはその正当性の証明と効率性の理論的な解析が必要なんだよね．
遺伝的アルゴリズムはそのような考察が非常に難しくて，実験的にしか正当性と性能を検証できない．
さらに実際問題への適用に際して，設計指針ともいえる方法が示されていない，つまり評価関数と変数の選び方が経験によるところが多い手法といえる．
そのためヒューリスティック（発見的）アルゴリズムと呼び区別される．
＞＞ あと、解けるのは組み合わせ問題だけではありません。
一見組み合わせ問題に見えなくても，組み合わせ最適化問題に帰着できます．
余計なもの(-32768) (スコア:0)
Re:余計なもの(-32768) (スコア:1)
H/Wだけど、こっちを思い浮かべた・・・
Re:余計なもの(-32768) (スコア:1)
Re:余計なもの(-32768) (スコア:0)
ってっきり (スコア:0)
module (スコア:0)
ある一定期間システムを見張っておいて、使ったmodule だけを組み込み、
その他は絶対必要そうな物だけ入れる。
また、proc を見て適切なパラメーターを自動で判断。
とかして自動的にシンプルなカーネルを作ってくれるツールなら欲しい。
Re:module (スコア:0, 余計なもの)
デスクトップ上の最近つかってないアイコンを消していいですかと聞いてきたりする
システムを知ってますが、便利どころかむしろ鬱陶しかったりします。
#自動的に、ってのはうまく働かない場合の方が多いと思いますよ。
Re:module (スコア:1)
Windowsのスタートメニューなんか、そういうものじゃないの?
#頻繁に使ってても省略されることも多いが
Re:module (スコア:1)
更に一歩進んで(ほんとに進んでるかどうかという議論はさておき)、
「パッケージのガベージコレクション」という概念が有ってもいいのではないか、と
ちょっと考えたことがあります。
＃たしかaptitudeを使うと、どういう順序でInstallを要求したかを覚えておいてくれる
＃(あとでuninstallのときに芋蔓式に消してくれる)のでしたよね？
＃それの延長として、ガベコレみたいなものが有ってもいいんじゃないの？と思いました。
まず安易に、「どのパッケージからも参照されてないパッケージ」はガベコレする、と考えました。
が、これだと、当然ですがトップレベル(?)のプログラムが全滅しちまいます。
いわゆるアプリは全滅。viも消えちゃう。言語系も全滅しかねん。使い物にならん。
次に、普通のプログラム言語内でのガベコレと、上記のガベコレとの間で、何が違うのか？と考えました。
すると、「トップレベルな奴の必要性を、システムにどうやって教えてあげるか？」の方式の問題なんだ、
と気付きました。
で、とりあえず、「ユーザが明示的に寄越せと言ったもの」はageることにする、ってのを考えました。
あと、「ユーザが実際使ったもの」もageましょう。
＃Debianでは、パッケージを擬似的(?)かつ動的にでっち上げるという事をやってる部分が、
＃(galternativesみたいに)有るわけですよね。
＃アゲを実現する原理は、それと同じで良いのだろうと思います。
ただこれだと、今度は「最近全然使わないんだけどユーザがその存在自体を忘れちゃったもの」は
いつまでも残ることになる。
となると、 WeakReferenceや時限つきReferenceの仕組みを導入して「弱く固定」する、
という考え方をするといいんだろうな、と思いました。
要するに、上の人とかが言ってるのと(見た目は)同じっす。
で…やっぱり鬱陶しいですかね(^^;
自動的ならばいいんですかね。
じゃあ、一定期間使われなかった奴は、自動でuninstall(パッケージファイル以外消す)するっすかね。
逆にいえば、「久々に呼ばれた奴」は、自動で再Installしてもいいかも。
上記でパッケージファイルを残しておけば、Network死んでても再Installできるよね。
自動uninstallしたときは、(コマンドならば)コマンドの代わりに簡単なScriptを残しておき、
そいつが再Install手順にユーザを誘導する、みたいな感じ？
＃Debian初心者なのでG7
＃ところで、何らかのソースパッケージを取ってくると、
＃該当する言語のコンパイラも「依存性」に基づいてgetされるんでしょうか？
Re:module (スコア:0)
遺伝的アルゴリズム (スコア:0)
Re:遺伝的アルゴリズム (スコア:1)
局所最適に陥ったり発散してしまったりという基本的な問題については、遺伝子（パラメータの組み合わせ）を複数持たせて定期的に入れ替えて回避しているみたいですね。
あと気になるのは収束するまでの時間なのですが、利用できるリソースがどんどん大きくなっていることを考えれば、これからこういった利用方法は広がるのでしょうね。
Re:遺伝的アルゴリズム (スコア:1)
リソースとして、Internetってものも有るよなあ、と思い出しました。
つまりNet上のLinuxマシン同士が(自動的に)優勢な遺伝子の情報をやり取りする、みたいな。
あ。でも実際に世間のあちこちで使われるマシンたちは「交配」しないというか、しても意味がないですね。
各個体は、使われる目的が同じじゃないので、同じ遺伝子セットを持ってきても、
利益(この場合は「同じ遺伝子セットを優勢と見なすこと」)を共有したことにならない。
同じ「種」(使われ方)であるかどうか？を識別する手段がないと、どうにもならないですね。
プログラムごとのCPU消費や、Networkの(Portごとの？)トラフィック按配が、「似た傾向」のマシンは、
交配可能と見なしましょうかねえ？
まあそういう問題はさておくとすると(ぉぃ)、
P2PとかSETI@homeとかみたいにして情報を自動的に鍛えていく感じ、いいなあ。
あ。しまった。
P2PとかSETI@homeとか言い出すと、また管理者に怒られてクビ切られちゃうか。(Linux鯖の？)
遺伝子的……というより (スコア:0)
正解を評価さえできれば最適な映像エンコード設定を探してくれるソフトってのもできそう。一ヶ月ぐらいほっておくと綺麗で小さな映像が……
収束性 (スコア:0)
本当に？最適解への収束性が理論的に保証できるようなやさしい問題なら、そもそもGAなんてくだらない方法は使わない方がいいのに。
保証できないような問題に使うからこそGAやニューラルネットワークのような黒魔術の存在価値があるわけで。
まあ単にタレコミ人が無知なだけだろうけど、と思ったら書きおろしかよ…
Re:収束性 (スコア:3, 興味深い)
にもかかわらずGEQOを使うのは、大量のJOINを伴うようなプランの取りうる組み合わせが爆発した場合に時間がかかりすぎるからなのです。最適なプランを導くのが理論的に可能だとしても、それによって得られる恩恵以上に計算量が増えてしまえばなんの意味もないです。
そういう意味ではそれなりの計算量である程度の効果が見込めるGAは有効になり得ます。まあ、最適値がみつかるかというと評価関数のばらつきとかがあるだろうから難しいんでしょうが・・・
Re:収束性 (スコア:1)
Re:収束性 (スコア:1, すばらしい洞察)
いや、だからそこが問題なんだって指摘されてるんですけど、わかりませんか？
ここで問題になってるのは「理論的に最適解への収束を保証できる問題にGAを適用することの意味」です。そこへいきなりあなたが「理論的な最適解への収束保証」のない事例を持ち出してきたから、的がはずれてるのです。他の人も指摘してますが、あなたが出してきた例では、GAによって得られるのはあくまで近似解(最適解の保証なし)で、もちろん最適解への収束保証もありません。
理論的な最適解への収束保証ができない場合にGAを使うことについて、馬鹿らしいなどと言ってる人は誰もいませんよ。そう言ってる人間がいるとあなたが思い込んでるだけで。もうちょっと落ち着いて、他の人のコメントを読むようにしたらいいと思います。
それから、最適解と近似解の違いや、収束保証の意味も勉強された方がいいですね。基本がまるで理解できていないようですから。
Re:収束性 (スコア:1)
もちろん評価関数の問題で、それが現実には最適解じゃない可能性もありますが:D
Re:収束性 (スコア:1)
はっきり言っておくと、DBの問い合わせプランは順列組み合わせ問題に近く、テーブルのJOINやインデックスの選択肢が少ない殆どのケースでプラン数が数個～数十個しかなく、通常全件調査してもコスト場問題ない、と書けば満足ですか？
あなたが数学に詳しくても実世界の適用例に詳しくない上、言葉遣いは最悪で自分の言いたいことをここの方々にまともに説明できてないこともわかりましたから。Re:収束性 (スコア:1)
>
>本当に？
"無限世代"or"無限の個体"とか極限での話なのかな？
GA がどういう条件で巧くいくのか知らないので、
詳しい人に聞いてみたい部分です。
#そんなにやるなら、(連続問題でない限り)全探索と
#同じだと思いますが。
> ニューラルネットワークのような黒魔術
そんなに、黒魔術ですかね？
結構有名なニューラルネットの 多層パーセプトロン [google.com]
の有名な学習方法バックプロパゲーション [google.com]も
勾配法で二乗誤差を最小化してるだけだと思いますが。。。
# もっとも"ニューラルネットワーク"じゃ何を指してるか分からない
# ぐらい多種多様な"ニューラルネットワーク"があるわけですが
Re:収束性 (スコア:1)
・全探索すれば必ず最適なパラメータが見つかる問題である。
・計算量の問題があって全探索できない。
てな場合です。
突然変異があるので無限時間走らせれば全探索になります。
実用的には突然変異の確率をだんだん下げていくし、交配やら突然変異やらによる解の改善があんまりなくなっちゃった所で止めてパラメータ固定しちゃうわけですが。
まあ実用的な時間で「そこそこ近い」パラメータを出したい時に使う解法です。
完全な最適解以外でも十分役に立つような場合にはぴったり。
でも全探索できるような問題に使うのはただのムダですね。
Re:収束性 (スコア:1)
NP困難 (NP-hard) というキーワードもつけておきます。
GAは多項式オーダー(時間)で解けない問題の近似解を求めるのに
よく使われます。
Re:収束性 (スコア:2)
ただ実際問題として，スケジューリングなど多くの問題では
最適解でなくとも最適に近い解が得られればそれで十分なので
GAのようなアルゴリズムが利用できるわけです．