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

遺伝的アルゴリズムでカーネルチューニング 72

ストーリー by Oliver
ワークロードが一定なら最強? 部門より

Linuxカーネルを遺伝的アルゴリズムを使って動的にチューンするパッチをJake Moilanenがlkmlに投稿した。このパッチはanticipatory IOスケジューラと現在-mmでテストされているzaphod CPUスケジューラを改造し、遺伝的アルゴリズムを提供する新しいカーネルライブラリを使って動作中に特定のワークロードにあわせて常に自己を自動チューンするように改善した。まだ荒削りながら、UnixbenchおよびSpecJBBで1-3%の性能改善が見られたという。パッチはあくまで実験であり、特にキモである評価関数にまだまだ改善の余地があるそうだ。

遺伝的アルゴリズムは突然変異と自然淘汰による生命の進化をモデルにした手法で、このパッチではさまざまなスケジューラのパラメータの組合せを「子」として合成し、それぞれを一定時間、実際のシステムで動かした後に評価しする。そして、評価の悪かった半分を捨て、評価のよかった半分のパラメータを少し変異させた新しい子を作成し、評価のサイクルが繰り返される。理論上は時間と共に特定の環境に最適なパラメータに収束する。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • 実際のシステムで動的チューニングって使える物なのでしょうか?

    動作条件が明確になっているシステムの場合は, それに合わせて手で固定的なチューニングを施した方が安定した高性能を出すでしょう. 逆に動作条件が, 例えば時間帯や日付で変動するようなシステムの場合には動作条件の変動と共にチューンの効果が変わり, システム性能が一定しないなんてことにもなりかねません. そのため, 最善ではなくてもそこそこのチューニングにしておくことにより, 性能を安定化させるなんてことも多くあります.

    どうも私の個人的な感覚としては, 動的自動チューンって今だ技術的なお遊びの段階を抜け出ていないように思うのですが, いかがでしょう?

    • 一般的なチューニングに話を広げれば、まだ技術的なお遊びと
      言われる部分も多いだろうけど、パラメータをうまく選べば
      遺伝的アルゴリズムは結構使えるんじゃないかな。

      チューニングの対象によって全くの役立たずになる場合もある
      だろうけど、ナップサック問題や巡回セールスマン問題のよう
      な評価関数を設定可能なものであれば、かなり使えそうな予感。

      システムのチューニングを、単なる計算困難な問題という程度
      にまでモデル化できるのかどうかに興味あります。
      親コメント
    • by Anonymous Coward on 2005年01月08日 21時06分 (#675830)

      Linuxでsysctl -Aしたときに表示される

      • net.ipv4.tcp_rmem
      • net.ipv4.tcp_wmem
      • net.ipv4.tcp_mem
      の3つのベクトル値は、動的なチューニング値のためのパラメタ です。

      親コメント
    • by Anonymous Coward on 2005年01月09日 22時58分 (#676252)
      Javaや.NETを使ってる人はJITにお世話になってると思います。 有るのと無いのじゃ大違い。
      親コメント
  • by tablog (25618) on 2005年01月08日 21時15分 (#675837)
    1.評価関数
    2.個体数の確保

    適合度って何を基準に出しているのかしらん?処理時間?
    あと一つのPCで複数の個体を保持しているのかなぁ。

    1PC1個体にして、ネットワーク経由で交配、とか妄想してみたけど違うみたいですね。そうだったら正に「ネットは広大」という事でかなりアレゲなんですが。
    • by kuy (23721) on 2005年01月08日 21時39分 (#675843) ホームページ
      適合度は評価関数により算出されます。
      また個体は1台のPC内に複数保持しないと交配できないため、もちろんそのようになっています。

      「ネットワーク越しで交配」というのは本来の意味が失われてしまいます。
      なぜならばその「PC」という環境に適合するようにチューニングすることが目的であるのですから。
      ネットワーク上にはまったく同じ環境を持つPCのみが存在するようなシステムでは話は別かもしれませんが。
      親コメント
      • by tu_n (13924) on 2005年01月08日 21時57分 (#675847)
        環境はそれぞれ違うといっても、比較的似たものは
        きっとあるはず。

        なにがしかの値が変数として評価関数のなかに
        取り込まれるとして、似た環境の(つまり変数に入る
        なにがしかが近い)PCのパラメータ値を取り込んでくると、
        比較的有効な初期パラメータとして収束するまでの
        時間を短縮できるんじゃないかなぁと思ったりしました。
        親コメント
      • by yu-na (10754) on 2005年01月08日 22時02分 (#675849) 日記
        複数のコンピュータでネットワーク越しで交配するなら
        GA っぽいですが、 一つのコンピュータ上で進化するなら、
        Simulated Annealing [google.com] が 良いのでは?

        実際には、試してみないと分からないでしょうが。
        親コメント
        • おもしろいですね。

          ただ、連続・・・ですかね?
          パラメータの微小変化に対してその結果が連続的に変化するのかどうかです。
          コンピュータ内部事情には詳しくないので分かりませんが、
          単純に「スケジューリング問題」として捉えれば切った貼ったのGAが良いように思えます。

          もちろんおっしゃる通りやってみないことには分かりませんが、
          何というか心をくすぐられる話題ですね。
          親コメント
          • by kogekoge (20427) on 2005年01月08日 22時31分 (#675858) 日記
            言葉的に、SA の「収束」よりも GA の 「淘汰」の方に
            惹かれてしまふ。
            SA は局所解脱出方法だよなと考えてるので、システムの
            チューニングとに対してはどうだろうかという思いと、
            モデルをそのような式で表現できたらおもしろいなという
            思いが交錯しておりまする。

            いやいや、ほんとおもしろい話題だな。
            親コメント
            • by yu-na (10754) on 2005年01月08日 22時58分 (#675874) 日記
              GA だと世代ごとの個体数を増やすと
              パラメータ更新まで間隔が開きそうなんで、
              どうなんだろうと思ったのが大きいです。

              ただ、GA の方が各個体のテストを複数回行うことで
              誰もユーザーの使ってない状況に最適化しちゃうとか、
              状況依存には強かったりするのかな?

              なんて、無責任に妄想しております。
              親コメント
        • SAはGAの利用を含む探索問題の計算を早く収束させるための一手法だと認識しています。
          ですから、「GAよりもSAのほうが良い」というのは奇妙な感じです。
          --
          --kwbt
          親コメント
          • by yu-na (10754) on 2005年01月09日 3時31分 (#675982) 日記
            SA はパラメータを微少に変化させた場合に
            エネルギー関数が小さくなった場合には確率1 で、
            大きくなった場合には、確率 exp(-dE/T) で
            新しいパラメータを受理する。
            で、徐々に T を小さくする。
            T が 0 になれば、最適解になってる。

            っていうものじゃないでしょうか?
            親コメント
          • > SAはGAの利用を含む探索問題の計算を早く収束させるための一手法だと認識しています。

            SA(Simulated Annealing)とGA(Genetic Algorithm)は最適化問題を解くための
            まったく異なるアルゴリズムであり、互いに包含関係なんかはないです。

            SAよりもGAの方が局所解に陥りにくいってことで、SAからGAへって流行があったものだから
            「GAはSAの改良版」って感じでとらえられることが多いですけど
            親コメント
      • by tablog (25618) on 2005年01月08日 22時17分 (#675852)
        > 適合度は評価関数により算出されます。

        んな、当たり前でんがな。GAの適合度は普通、評価関数から算出しますし。

        tunedとはどう定義されてるのかなぁ、という事ですね。処理速度なのか?メモリ占有率なのか?安全性なんかもあるかもしれませんし。GAの良し悪しは大体、評価関数で決まりますから。

        > 「ネットワーク越しで交配」というのは本来の意味が失われてしまいます。

        おおっ、確かにそのとおりですね。

        > また個体は1台のPC内に複数保持しないと交配できないため、もちろんそのようになっています。

        プロセスが起動した度に個体が発生するか、同じプロセスが同時に動いているような感じでしょうか?
        元記事だけではちょっと理解できませんでした。
        親コメント
        • > んな、当たり前でんがな。GAの適合度は普通、評価関数から算出しますし。

          すみませんでした。

          リンク先のサイトを(ざっとですが)見てみたところ、あらかじめパラメータセットを大きなテーブルに用意しておいて、それを一つ一つ試して全てのパラメータセットを試し終わった後で適合度を計算し、・・・(以下一般的なGAの手順)という感じです。

          つまりスケジューリングプロセスは一つですね。

          #所々言い切っていますが、間違っていたらごめんなさい
          親コメント
          • by morioka (6528) on 2005年01月08日 22時40分 (#675862) 日記
            >> んな、当たり前でんがな。GAの適合度は普通、評価関数から算出しますし。
            >
            >すみませんでした。
            >
            >リンク先のサイトを(ざっとですが)見てみたところ、あらかじめパラメータセットを大きなテーブルに用意しておいて、それを一つ一つ試して全てのパラメータセットを試し終
            >わった後で適合度を計算し、・・・(以下一般的なGAの手順)という感じです。

            いや、疑問とされているのは、
            「評価に用いる適合度は、どういった要因をどう組み合わせて定義しているのでしょう?」
            ということですよね。それがGAのキモ。
            親コメント
      • by huixteng (22050) on 2005年01月09日 1時28分 (#675953)
        >「ネットワーク越しで交配」というのは本来の意味が
        > 失われてしまいます。
        > なぜならばその「PC」という環境に適合するように
        > チューニングすることが目的であるのですから。

        より広範囲で交配する種の方が多様性を持つため
        より生き残るんで良いのでは、という素人の疑問が・・・。

        ああそうか、その多様性ゆえに、使いにくい PC を
        「種」のためにがまんして使わなきゃいけないユーザが
        出ちゃうって事か。

        ということは、ひとつのPC という狭い範囲で交配し続けた
        遺伝的アルゴリズムカーネルは、なんらかの破壊的パラダイム
        シフトにきわめて脆弱になる・・Σ(゚Д゚
        --
        閾値は 0 で
        親コメント
        • それを回避するための評価関数パラメータの定期的入れ換えだと思いますし、カーネルの動作に与えるパラメータだけで収まってるので、心配するような状況は極めて限られるのではないかと。

          これが、実行コード(実マシンコード)の動的最適化迄進むと、「破壊的パラダイムシフトへの脆弱」と言う懸念が本当の物になると思うので慎重に進めないとまずいですが…

          親コメント
          • by huixteng (22050) on 2005年01月10日 12時06分 (#676439)
            > カーネルの動作に与えるパラメータだけで
            > 収まってるので、心配するような状況は極めて
            > 限られるのではないかと。

            実マシンコードとは独立した、
            ポータブルな進化結果なんですね。

            素人のたとえ話で申し訳ないですが、
            いいなぁ、象の鼻、と思ったら
            その遺伝子だけもらって組み換えちゃえば
            いいとかそんな感じかな。

            待てよ、そこで勘違いした一般消費者の
            遺伝子組み換え OS 反対運動が勃発して
            ・・・・・Σ(゚Д゚
            --
            閾値は 0 で
            親コメント
      • by G7 (3009) on 2005年01月09日 13時24分 (#676074)
        >ネットワーク上にはまったく同じ環境を持つPCのみが存在するようなシステム

        Linuxマシンを沢山沢山繋いで、「同じ(少なくとも対称な)」仕事をさせる、という最近よく聞く話の場合は、
        有効かも知れないってことですね。
        Grid(ってんだっけ)なLinuxスパコンが、自ら勝手にパフォチューしてくれる、みたいな?

        あ。でも、与える課題(走らせるプログラムとかデータ傾向とか)を変えるたびに
        天変地異になっちゃうわけですね。
        こりゃ、色々あるプログラムやデータを、どうやって「同じor違う」と見なすか、という問題に
        帰着するのかな。
        親コメント
  • by Anonymous Coward on 2005年01月10日 14時43分 (#676500)
    遺伝的アルゴリズムってたいそうな名前を冠してるけど,要するに組み合わせ問題における解空間の効率的な探索法の一つですよね.

    ヒューリスティックで,それゆえ簡単に使えちゃうんだけどあまり性能は良くない.
    吉野家コピペ風に言えば,”まぁ,お前らど素人は遺伝的アルゴリズムでも使ってな”というところでしょうか?
  • by Anonymous Coward on 2005年01月08日 17時23分 (#675764)
    嗚呼、ついにスカイネットが発動する.....
  • by Anonymous Coward on 2005年01月08日 17時42分 (#675773)
    コードをチューニングするんかとおもった。
  • by Anonymous Coward on 2005年01月08日 17時55分 (#675778)
    ちゃんとたれ込み読んでませんが、

    ある一定期間システムを見張っておいて、使ったmodule だけを組み込み、
    その他は絶対必要そうな物だけ入れる。
    また、proc を見て適切なパラメーターを自動で判断。

    とかして自動的にシンプルなカーネルを作ってくれるツールなら欲しい。
    • Re:module (スコア:0, 余計なもの)

      by Anonymous Coward
      一定期間システムを見張っておいて、使わないアプリがメニューから隠れたり、
      デスクトップ上の最近つかってないアイコンを消していいですかと聞いてきたりする
      システムを知ってますが、便利どころかむしろ鬱陶しかったりします。

      #自動的に、ってのはうまく働かない場合の方が多いと思いますよ。
      • by NAT33 (17123) on 2005年01月08日 18時51分 (#675792)
        聞いて来なかったら、さほど不便でもないかも。

        Windowsのスタートメニューなんか、そういうものじゃないの?

        #頻繁に使ってても省略されることも多いが
        親コメント
      • by Anonymous Coward
        この件は、どちらかというと自律コンピューティングのような話ですよね。 RDBMSのチューニングを半自動化するとか、JVMでGCのチューニングを自動化するとか、そういう例は多くなってきていますよ。
  • by Anonymous Coward on 2005年01月08日 19時09分 (#675794)
    • by tu_n (13924) on 2005年01月08日 19時45分 (#675802)
      大学の卒論でちょこっとだけかじりかけたのですが、コンピュータが試行錯誤するみたいに思えて、なんだか面白そうに思ったものです。そのときにはメカトロ系の解析問題でした。

      局所最適に陥ったり発散してしまったりという基本的な問題については、遺伝子(パラメータの組み合わせ)を複数持たせて定期的に入れ替えて回避しているみたいですね。
      あと気になるのは収束するまでの時間なのですが、利用できるリソースがどんどん大きくなっていることを考えれば、これからこういった利用方法は広がるのでしょうね。
      親コメント
      • by G7 (3009) on 2005年01月09日 13時06分 (#676066)
        >利用できるリソースがどんどん大きくなっている

        リソースとして、Internetってものも有るよなあ、と思い出しました。
        つまりNet上のLinuxマシン同士が(自動的に)優勢な遺伝子の情報をやり取りする、みたいな。

        あ。でも実際に世間のあちこちで使われるマシンたちは「交配」しないというか、しても意味がないですね。
        各個体は、使われる目的が同じじゃないので、同じ遺伝子セットを持ってきても、
        利益(この場合は「同じ遺伝子セットを優勢と見なすこと」)を共有したことにならない。

        同じ「種」(使われ方)であるかどうか?を識別する手段がないと、どうにもならないですね。
        プログラムごとのCPU消費や、Networkの(Portごとの?)トラフィック按配が、「似た傾向」のマシンは、
        交配可能と見なしましょうかねえ?

        まあそういう問題はさておくとすると(ぉぃ)、
        P2PとかSETI@homeとかみたいにして情報を自動的に鍛えていく感じ、いいなあ。

        あ。しまった。
        P2PとかSETI@homeとか言い出すと、また管理者に怒られてクビ切られちゃうか。(Linux鯖の?)
        親コメント
  • by Anonymous Coward on 2005年01月08日 20時26分 (#675814)
    パラメーターをいじるっていうと、なんかコマンド総当たりの方を思い出してしまうなあ。

    正解を評価さえできれば最適な映像エンコード設定を探してくれるソフトってのもできそう。一ヶ月ぐらいほっておくと綺麗で小さな映像が……
  • by Anonymous Coward on 2005年01月08日 22時07分 (#675850)
    > 理論上は時間と共に特定の環境に最適なパラメータに収束する。

    本当に?最適解への収束性が理論的に保証できるようなやさしい問題なら、そもそもGAなんてくだらない方法は使わない方がいいのに。

    保証できないような問題に使うからこそGAやニューラルネットワークのような黒魔術の存在価値があるわけで。

    まあ単にタレコミ人が無知なだけだろうけど、と思ったら書きおろしかよ…
    • Re:収束性 (スコア:3, 興味深い)

      by L.star (163) on 2005年01月08日 22時42分 (#675863) ホームページ
      同じGAの話をするなら、PostgreSQLはGEQOというGAを使ったオプティマイザを古くから持っています。これはプランの最適化に使うものですが、RDBMSの問い合わせプランは殆どのケースで最適解への収束が行われるでしょうから、あなたの言い分だとGEQOはくだらない方法になるでしょう。

      にもかかわらずGEQOを使うのは、大量のJOINを伴うようなプランの取りうる組み合わせが爆発した場合に時間がかかりすぎるからなのです。最適なプランを導くのが理論的に可能だとしても、それによって得られる恩恵以上に計算量が増えてしまえばなんの意味もないです。

      そういう意味ではそれなりの計算量である程度の効果が見込めるGAは有効になり得ます。まあ、最適値がみつかるかというと評価関数のばらつきとかがあるだろうから難しいんでしょうが・・・

      親コメント
    • by yu-na (10754) on 2005年01月08日 23時31分 (#675894) 日記
      >> 理論上は時間と共に特定の環境に最適なパラメータに収束する。
      >
      >本当に?
      "無限世代"or"無限の個体"とか極限での話なのかな?
      GA がどういう条件で巧くいくのか知らないので、
      詳しい人に聞いてみたい部分です。
      #そんなにやるなら、(連続問題でない限り)全探索と
      #同じだと思いますが。

      > ニューラルネットワークのような黒魔術
      そんなに、黒魔術ですかね?
      結構有名なニューラルネットの 多層パーセプトロン [google.com]
      の有名な学習方法バックプロパゲーション [google.com]も
      勾配法で二乗誤差を最小化してるだけだと思いますが。。。

      # もっとも"ニューラルネットワーク"じゃ何を指してるか分からない
      # ぐらい多種多様な"ニューラルネットワーク"があるわけですが
      親コメント
      • GAを使う時ってのは
        ・全探索すれば必ず最適なパラメータが見つかる問題である。
        ・計算量の問題があって全探索できない。
        てな場合です。
        突然変異があるので無限時間走らせれば全探索になります。
        実用的には突然変異の確率をだんだん下げていくし、交配やら突然変異やらによる解の改善があんまりなくなっちゃった所で止めてパラメータ固定しちゃうわけですが。

        まあ実用的な時間で「そこそこ近い」パラメータを出したい時に使う解法です。
        完全な最適解以外でも十分役に立つような場合にはぴったり。
        でも全探索できるような問題に使うのはただのムダですね。
        親コメント
typodupeerror

最初のバージョンは常に打ち捨てられる。

読み込み中...