plan API

パッケージ Luna-Flow/luna_thread/plan は @plan としてインポートされ、1 つのデータ並列操作を値として記述します。その種類、入力の要素型と長さ、実行ポリシー、省略可能なリダクションカーネル、順序の保証です。プランを v1 のサブセットに照らして検証します。何も実行せず、すべてのターゲットでビルドできます。

このパッケージの列挙型はパッケージの外では読み取り専用です。コンストラクタでパターンマッチはできますが、値は以下の関数で作ってください。

型

PlanKind

プランが記述できる 4 つの操作です。

pub enum PlanKind {
  Map
  Reduce
  Scan
  MapReduce
} derive(Eq, @debug.Debug)

Map はすべての要素に関数を適用し、Reduce はすべての要素をカーネルで結合し、Scan は途中までの結合（累積）を作り、MapReduce はマップしてからリデュースします。

ValueType

プランの入力の要素型です。

pub enum ValueType {
  I32
  I64
  F32
  F64
  Bytes
  Opaque(String)
} derive(Eq, @debug.Debug)

v1 でサポートされるのは I32 と I64 だけです。

ReductionKernel

リデュース、マップリデュース、スキャンで使う二項演算です。

pub enum ReductionKernel {
  Sum
  Min
  Max
  Custom(String)
} derive(Eq, @debug.Debug)

Custom(name) はランタイムが知らないカーネルを指します。v1 では決して検証を通りません。

DataDomain

プランの入力の要素型と長さです。

pub struct DataDomain {
  element_type : ValueType
  input_length : Int
} derive(Eq, @debug.Debug)
pub fn DataDomain::new(ValueType, Int) -> Self
pub fn DataDomain::element_type(Self) -> ValueType
pub fn DataDomain::input_length(Self) -> Int

DataDomain::new(t, n) は引数を検査せずに保存します。$n \le 0$ は validate が拒否します。

Plan

完全なプランです。

pub struct Plan {
  label : String
  kind : PlanKind
  domain : DataDomain
  policy : @shared.ExecutionPolicy
  reduction : ReductionKernel?
  ordering : @shared.OrderingGuarantee
} derive(Eq, @debug.Debug)
pub fn Plan::new(String, PlanKind, DataDomain, policy? : @shared.ExecutionPolicy, reduction? : ReductionKernel, ordering? : @shared.OrderingGuarantee) -> Self

Plan::new は引数を検査せずに保存します。policy の既定は @shared.native_policy()、reduction は None、ordering は PreserveInputOrder です。順序を緩めたスキャンのように、以下のビルダーでは作れない組み合わせに使います。

Plan::label、Plan::kind、Plan::domain、Plan::policy、Plan::reduction、Plan::ordering

プランの各フィールドを返します。

pub fn Plan::label(Self) -> String
pub fn Plan::kind(Self) -> PlanKind
pub fn Plan::domain(Self) -> DataDomain
pub fn Plan::policy(Self) -> @shared.ExecutionPolicy
pub fn Plan::reduction(Self) -> ReductionKernel?
pub fn Plan::ordering(Self) -> @shared.OrderingGuarantee

ValidationIssue

プランが v1 のサブセットから外れる理由の 1 つです。

pub enum ValidationIssue {
  EmptyInput
  ChunkSizeDoesNotFitInput(chunk_size~ : Int, input_length~ : Int)
  WorkerCountExceedsInput(worker_count~ : Int, input_length~ : Int)
  MissingReductionKernel
  ScanRequiresStableOrdering
  UnsupportedValueType
  UnsupportedReductionKernel
  UnsupportedBackend
  UnsupportedMode
  UnsupportedOrdering(kind~ : PlanKind, ordering~ : @shared.OrderingGuarantee)
} derive(Eq, @debug.Debug)

それぞれがいつ報告されるかは validate の項で説明しています。

T::equal

構造的な等価性で、このパッケージのすべての型 DataDomain、Plan、PlanKind、ReductionKernel、ValidationIssue、ValueType のメソッドとして昇格されています。== と != を使ってください。

pub fn Plan::equal(Self, Self) -> Bool

列挙型のコンストラクタ関数

map_plan_kind、reduce_plan_kind、scan_plan_kind、map_reduce_plan_kind

Map、Reduce、Scan、MapReduce を返します。

pub fn map_plan_kind() -> PlanKind
pub fn reduce_plan_kind() -> PlanKind
pub fn scan_plan_kind() -> PlanKind
pub fn map_reduce_plan_kind() -> PlanKind

i32_type、i64_type、f32_type、f64_type、bytes_type、opaque_type

I32、I64、F32、F64、Bytes、Opaque(name) を返します。

pub fn i32_type() -> ValueType
pub fn i64_type() -> ValueType
pub fn f32_type() -> ValueType
pub fn f64_type() -> ValueType
pub fn bytes_type() -> ValueType
pub fn opaque_type(String) -> ValueType

sum_reduction、min_reduction、max_reduction、custom_reduction

Sum、Min、Max、Custom(name) を返します。

pub fn sum_reduction() -> ReductionKernel
pub fn min_reduction() -> ReductionKernel
pub fn max_reduction() -> ReductionKernel
pub fn custom_reduction(String) -> ReductionKernel

test "enumeration constructors" {
  assert_true(@plan.scan_plan_kind() is @plan.Scan)
  debug_inspect(@plan.opaque_type("rgba"), content="Opaque(\"rgba\")")
  debug_inspect(@plan.custom_reduction("xor"), content="Custom(\"xor\")")
}

プランの作成

map

Map プランを作ります。

pub fn map(String, ValueType, Int, policy? : @shared.ExecutionPolicy, ordering? : @shared.OrderingGuarantee) -> Plan

引数はラベル、要素型、入力の長さです。policy の既定は @shared.native_policy()、ordering の既定は PreserveInputOrder です。リダクションは None です。

reduce

リダクションカーネルを持ち、順序が PreserveInputOrder の Reduce プランを作ります。

pub fn reduce(String, ValueType, Int, ReductionKernel, policy? : @shared.ExecutionPolicy) -> Plan

scan

順序が PreserveInputOrder で、リダクションカーネルを持たない Scan プランを作ります。

pub fn scan(String, ValueType, Int, policy? : @shared.ExecutionPolicy) -> Plan

ネイティブのスキャンカーネルは累積和なので、スキャンプランはカーネルを指定しません。

map_reduce

MapReduce プランを作ります。

pub fn map_reduce(String, ValueType, Int, ReductionKernel, policy? : @shared.ExecutionPolicy, ordering? : @shared.OrderingGuarantee) -> Plan

test "building plans" {
  let policy = @shared.make_execution_policy(worker_count=2, chunk_size=4).unwrap()
  let plan = @plan.reduce("min", @plan.i64_type(), 8, @plan.min_reduction(), policy~)
  assert_true(plan.kind() is @plan.Reduce)
  assert_eq(plan.domain().input_length(), 8)
  assert_eq(plan.reduction(), Some(@plan.min_reduction()))
}

検証

validate

プランのすべての問題を決まった順序で返します。なければ空の配列を返します。

pub fn validate(Plan) -> Array[ValidationIssue]

$n$ を入力の長さ、$w$ と $c$ をポリシーのワーカー数とチャンクサイズとすると、検査は次のとおりです。

問題	報告される条件
EmptyInput	$n \le 0$
UnsupportedValueType	要素型が I32 でも I64 でもない
ChunkSizeDoesNotFitInput	$c > n > 0$
WorkerCountExceedsInput	$w > n > 0$
UnsupportedBackend	ポリシーのバックエンドが Native でない
UnsupportedMode	ポリシーのモードが Synchronous でない
MissingReductionKernel	Reduce または MapReduce プランにカーネルがない
UnsupportedReductionKernel	Reduce または MapReduce プランのカーネルが Custom
UnsupportedOrdering と ScanRequiresStableOrdering	Scan プランの順序が RelaxedOrder。両方が報告される

validate は、ネイティブカーネルが追加で要求する被覆条件 $w \ge \lceil n / c \rceil$ を検査しません。

is_runnable

validate が問題を返さないとき true を返します。

pub fn is_runnable(Plan) -> Bool

value_type_is_supported_in_v1、reduction_kernel_is_supported_in_v1、ordering_is_valid_for_kind

validate が使う個々の v1 の規則です。

pub fn value_type_is_supported_in_v1(ValueType) -> Bool
pub fn reduction_kernel_is_supported_in_v1(ReductionKernel) -> Bool
pub fn ordering_is_valid_for_kind(PlanKind, @shared.OrderingGuarantee) -> Bool

1 つ目は I32 と I64 を、2 つ目は Sum、Min、Max を受け付けます。3 つ目は Scan に対する RelaxedOrder を除くすべての順序を受け付けます。

test "validation" {
  let relaxed = @plan.Plan::new(
    "prefix",
    @plan.scan_plan_kind(),
    @plan.DataDomain::new(@plan.i32_type(), 8),
    ordering=@shared.relaxed_order(),
  )
  let issues = @plan.validate(relaxed)
  assert_eq(issues.length(), 2)
  assert_true(issues[0] is @plan.UnsupportedOrdering(kind=@plan.Scan, ..))
  assert_true(issues[1] is @plan.ScanRequiresStableOrdering)
  assert_true(!@plan.is_runnable(relaxed))
  assert_true(!@plan.reduction_kernel_is_supported_in_v1(@plan.custom_reduction("xor")))
}

述語

is_map、is_reduce、is_scan、is_map_reduce

プランの種類を判定します。

pub fn is_map(Plan) -> Bool
pub fn is_reduce(Plan) -> Bool
pub fn is_scan(Plan) -> Bool
pub fn is_map_reduce(Plan) -> Bool

has_sum_reduction

プランのカーネルが Some(Sum) のとき true を返します。

pub fn has_sum_reduction(Plan) -> Bool

is_chunk_size_too_large、is_scan_requires_stable_ordering、is_unsupported_value_type、is_unsupported_reduction_kernel、is_unsupported_backend、is_unsupported_mode、is_unsupported_ordering

ValidationIssue がどの問題かを判定します。Array::any と組み合わせて使います。

pub fn is_chunk_size_too_large(ValidationIssue) -> Bool
pub fn is_scan_requires_stable_ordering(ValidationIssue) -> Bool
pub fn is_unsupported_value_type(ValidationIssue) -> Bool
pub fn is_unsupported_reduction_kernel(ValidationIssue) -> Bool
pub fn is_unsupported_backend(ValidationIssue) -> Bool
pub fn is_unsupported_mode(ValidationIssue) -> Bool
pub fn is_unsupported_ordering(ValidationIssue) -> Bool

is_chunk_size_too_large は ChunkSizeDoesNotFitInput に一致し、ほかは同名の問題に一致します。

test "issue predicates" {
  let policy = @shared.make_execution_policy(chunk_size=64).unwrap()
  let plan = @plan.map("small", @plan.i32_type(), 8, policy~)
  let issues = @plan.validate(plan)
  assert_true(issues.any(@plan.is_chunk_size_too_large))
  assert_true(@plan.is_map(plan) && !@plan.has_sum_reduction(plan))
}

パッケージ情報

package_name と default_backend_label

"plan" と、既定のバックエンドのラベル "native" を返します。

pub fn package_name() -> String
pub fn default_backend_label() -> String