tune API

Luna-Flow/mare_mark/tune は自動チューニングのポリシー側を提供します。候補空間、予算とホールドアウト、頑健なスコア、実用的な閾値による選択、パレートフロント、シード付きの候補順序です。候補のビルドや実行は行いません。アプリケーションが候補を計測し（通常は runner を使って）、その数値をこれらの関数に渡します。tune の設計も参照してください。

ソース: src/tune/tune.mbt。

import {
  "Luna-Flow/mare_mark/tune",
}

候補

`CandidateSpace`

CandidateSpace はチューナーが試してよい構成を記述します。

pub struct CandidateSpace[Candidate] {
  enumerate : () -> Array[Candidate]
  candidate_id : (Candidate) -> String
  valid : (Candidate) -> Bool
  neighbors : (Candidate) -> Array[Candidate]
}
pub fn[Candidate] CandidateSpace::new(() -> Array[Candidate], (Candidate) -> String, (Candidate) -> Bool, (Candidate) -> Array[Candidate]) -> Self[Candidate]

enumerate は空間を決定的な順序で列挙し、candidate_id は一意で安定した ID を返し、valid は制約に違反する構成を計測前に却下し、neighbors は自分で書く局所探索のために近傍の構成を列挙します（このパッケージの関数はこれを使いません）。

`BuiltCandidate`

BuiltCandidate は候補 ID と、そのためにビルドされた実行可能な実装の組です。

pub struct BuiltCandidate[Prepared, Output, Context] {
  candidate_id : String
  implementation : @runner.Implementation[Prepared, Output, Context]
  kernel_id : String
}
pub fn[Prepared, Output, Context] BuiltCandidate::new(String, @runner.Implementation[Prepared, Output, Context], String) -> Self[Prepared, Output, Context]

`BuildEvent`

BuildEvent は候補が受理されたかどうかと、受理されなかった理由を記録します。

pub struct BuildEvent {
  candidate_id : String
  kernel_id : String
  accepted : Bool
  reason : String
}

reason は、受理された候補では ""、valid によって却下された候補では "constraint"、スコアが使えない候補では "measurement" です。

予算と目的

`TuningBudget`

TuningBudget はチューニングの実行に上限を設けます。

pub struct TuningBudget[Scale] {
  max_candidates : Int
  max_measurements : Int
  max_elapsed_us : Double?
  exploration_samples : Int
  confirmation_samples : Int
  finalists : Int
  holdout : HoldoutPlan[Scale]
}
pub fn[Scale] TuningBudget::new(Int, Int, Double?, Int, Int, Int, HoldoutPlan[Scale]) -> Self[Scale]

フィールドは 2 段階の探索を記述します。すべての候補を exploration_samples で探索し、上位の finalists を confirmation_samples で確認し、勝者を holdout で検査します。このレコードはチューニングループのためのデータであり、ここにある関数がそれを強制することはありません。

`HoldoutPlan`

HoldoutPlan は、勝者が汎化することを確かめるために取っておくデータを指定します。

pub(all) enum HoldoutPlan[Scale] {
  MeasurementHoldout(Int)
  DatasetHoldout(Array[Int])
  ShapeHoldout(Array[Scale])
  WorkloadHoldout(String)
  Combined(Array[HoldoutPlan[Scale]])
}

コンストラクタ	取っておくもの
`MeasurementHoldout(n)`	最後の `n` 個の計測
`DatasetHoldout(ids)`	これらのデータセット
`ShapeHoldout(scales)`	これらのスケールまたは形状
`WorkloadHoldout(name)`	名前付きのワークロード
`Combined(plans)`	列挙された上記のすべて

`TuningObjective`

TuningObjective は「最良」の意味を定めます。

pub struct TuningObjective {
  practical_delta_pct : Double
  max_workspace_bytes : UInt64?
  minimize_secondary : Bool
}
pub fn TuningObjective::new(Double, UInt64?, Bool) -> Self

最速のものから practical_delta_pct 以内の候補は同率とみなされます。同率の場合は副次的な指標を最小化または最大化して決着をつけます。

スコア

`CandidateScore`

CandidateScore は 1 つの候補の計測結果です。

pub struct CandidateScore {
  candidate_id : String
  primary : Double
  secondary : Double
  valid : Bool
}
pub fn CandidateScore::new(String, Double, Double, Bool) -> Self

primary は最小化するコスト（時間）、secondary は同率の決着に使う指標（メモリ、コードサイズ）です。スコアは valid が真で、両方の値が有限かつ非負のときに使用可能です。以下の関数はそれ以外のスコアを無視します。

`score_samples`

score_samples は計時サンプルをスコアに変換します。スコアは使用可能なサンプルの中央値です。

pub fn score_samples(String, Array[Double], Double) -> CandidateScore

NaN、無限大、負のサンプルは除外されます。何も残らない場合、または副次的な値が有限かつ非負でない場合、スコアは valid = false かつ primary = 0.0 になります。

test "median score" {
  let score = @tune.score_samples("64x64", [9.0, 1.0, 5.0, -1.0, 3.0], 4096.0)
  inspect(score.primary, content="4")
  inspect(score.valid, content="true")
}

`select_best`

select_best は使用可能なスコアの中から勝者を選びます。

pub fn select_best(Array[CandidateScore], Double, Bool) -> CandidateScore?

引数: スコア、パーセント単位の実用的な閾値 $t$ 、副次的な指標を最小化するかどうか。最小の主指標を $p_{\min}$ とすると、最終候補は $100\,(p - p_{\min})/p_{\min} \le t$ を満たすスコアです（ $p_{\min} = 0$ のときは $p = 0$ のもの）。その中から副次的な値が最良のもの、次に最小の ID を返します。NaN、無限大、負の閾値は 0 として扱われます。使用可能なスコアがない場合は None を返します。結果は入力の順序に依存しません。

test "fast enough, then small" {
  let scores = [
    @tune.CandidateScore::new("fastest", 100.0, 900.0, true),
    @tune.CandidateScore::new("lean", 103.0, 100.0, true),
    @tune.CandidateScore::new("leaner-but-slow", 110.0, 10.0, true),
  ]
  inspect(@tune.select_best(scores, 5.0, true).unwrap().candidate_id, content="lean")
  inspect(@tune.select_best(scores, 0.0, true).unwrap().candidate_id, content="fastest")
}

`pareto_frontier`

pareto_frontier は、他のどの使用可能なスコアにも支配されない使用可能なスコアを残します。

pub fn pareto_frontier(Array[CandidateScore]) -> Array[CandidateScore]

$o.p \le c.p$ かつ $o.s \le c.s$ で、そのうち一方が厳密な不等号のとき、スコア $o$ は $c$ を支配します（両方の指標は最小化されます）。結果は主指標、副次的指標、ID の順でソートされます。コスト: $O(n^2)$ 。

test "Pareto front" {
  let front = @tune.pareto_frontier([
    @tune.CandidateScore::new("a", 1.0, 9.0, true),
    @tune.CandidateScore::new("b", 2.0, 4.0, true),
    @tune.CandidateScore::new("c", 3.0, 5.0, true),
    @tune.CandidateScore::new("d", 4.0, 1.0, true),
  ])
  debug_inspect(front.map(s => s.candidate_id), content="[\"a\", \"b\", \"d\"]")
}

探索ヘルパー

`exhaustive_scores`

exhaustive_scores は候補空間の先頭部分をスコア付けし、使用可能な最速の候補を示します。

pub fn[Candidate] exhaustive_scores(CandidateSpace[Candidate], Int, (Candidate) -> CandidateScore) -> TuningResult

enumerate() の最初の $\min(\text{budget}, \lvert\text{space}\rvert)$ 個の候補を取ります。有効な候補はそれぞれコールバックでスコア付けされ、無効な候補はスコア付けされません。ポリシー文字列は、主指標が最小の使用可能なもの（同率の場合は最初のもの）の "global:<id>"、使用可能なものがない場合は "global:" です。

test "exhaustive search" {
  let space = @tune.CandidateSpace::new(
    () => [8, 16, 32, 64],
    n => "block-" + n.to_string(),
    n => n <= 32,
    _ => [],
  )
  let cost = [8.0, 5.0, 6.0, 1.0]
  let result = @tune.exhaustive_scores(space, 10, n => {
    let index = if n == 8 { 0 } else if n == 16 { 1 } else if n == 32 { 2 } else { 3 }
    @tune.CandidateScore::new("block-" + n.to_string(), cost[index], 0.0, true)
  })
  inspect(result.policy, content="global:block-16")
  inspect(result.build_events[3].reason, content="constraint")
}

`TuningResult`

TuningResult は exhaustive_scores の結果です。

pub struct TuningResult {
  scores : Array[CandidateScore]
  build_events : Array[BuildEvent]
  policy : String
}

scores は有効な候補のスコア（使用可能かどうかを問わない）を保持し、build_events は調べた候補ごとに 1 つのイベントを保持します。

`seeded_order`

seeded_order は、ID のシード付きハッシュによって候補を並べ替えます。

pub fn[Candidate] seeded_order(Array[Candidate], UInt64, (Candidate) -> String) -> Array[Candidate]

各 ID はシードを鍵とする FNV-1a でハッシュされ、候補はハッシュ、次に ID でソートされます。結果は ID の集合とシードに依存し、入力の順序には依存しません。その先頭部分を再現可能なランダム部分集合として使ってください。

test "seeded order is input-order independent" {
  let a = @tune.seeded_order(["x", "y", "z"], 9UL, s => s)
  let b = @tune.seeded_order(["z", "x", "y"], 9UL, s => s)
  inspect(a == b, content="true")
}

`confirmation_count`

confirmation_count は、計測された不確かさに応じて確認サンプルの数を増減させます。

pub fn confirmation_count(Int, Double, Int) -> Int

confirmation_count(base, u, budget) は、 $u \le 0.05$ 、 $0.05 < u \le 0.2$ 、 $u > 0.2$ に対してそれぞれ base の 1 倍、2 倍、3 倍で、 $[0, \text{budget}]$ に制限されます。u は任意に選んだ相対的な不確かさで、例えば IQR を中央値で割ったものです。

test "more samples when noisy" {
  inspect(@tune.confirmation_count(10, 0.01, 100), content="10")
  inspect(@tune.confirmation_count(10, 0.1, 100), content="20")
  inspect(@tune.confirmation_count(10, 0.5, 25), content="25")
}