---

type: slide
slideOptions:
theme: white

---

<style type="text/css">
.reveal p {
text-align: left;
}
.reveal ul {
display: block;
}
.reveal ol {
display: block;
}
.reveal h1 { text-align: left; font-size: 150%; text-transform: none; }
.reveal h2 { text-align: left; font-size: 125%; text-transform: none; }
.reveal h3 { text-align: left; font-size: 112%; text-transform: none; }
.reveal h4 { text-align: left; font-size: 100%; text-transform: none; }
.reveal h5 { text-align: left; font-size: 100%; text-transform: none; }
.reveal h6 { text-align: left; font-size: 100%; text-transform: none; }
</style>

# Snoop benchmark dependency analysis

---

## Benchmark has models

These models are called *Aggregated* and have *submodels*.

(Micheline pasing/unparsing benchmarks have multiple models.)

---

## The submodel to determine a cost function

"Model for codegen":

(* ex. Lsl_bytes *)
N_ILsl_bytes_const 
+ N_ILsl_bytes_bytes * size1
+ N_ILsl_bytes_shift * size2

(This code for `Lsl_bytes` turned to be incorrect.)

The most benchmark has another submodel for `Timer_latency`.

---

## Benchmark performs auxiliary computations

Their times must be subtracted to infer the parameters for the codegen:

* `Timer_latency`: cost of execute a function
* `amplification_loop_iteration`: cost of a loop execution
* `N_IHalt_const`: cost of `HALT` opcode

---

## Benchmark free variables

* Variables in the model for codegen
* `N_ILsl_bytes_*`, etc
* Variables for the auxiliary computations
* `Timer_latency`, `amplification_loop_iteration`, `N_IHalt_const`, etc

---

## Benchmark dependency analysis

### Provided vs dependent

A variables of a benchmark must be either

* *Provided*: the benchmark fixes its value
* otherwise, *Dependent*: provided by another benchmark

Provided vs dependent is determined with with some heuristics. See `Dep_graph.Solver.solve`.

(We have clear idea about which variables are to be provided or dependent, but Snoop does not.)

---

## Benchmark dependency analysis

Topological sort of benchmarks

Benchmark $b$ is dependent on benchmark $b'$, when some dependent variables of $b$ are provided by $b'$.

---

## Inference

For each benchmark, the values of the provided variables are inferred from:

* The workload data of the benchmark
* The values of the dependent variables inferred by the inference of the benchmarks providing them.

---

## Ambiguities

Variable is *ambiguous* when provided by more than 1 benchmarks.

Ambiguities are resolved by heuristics.
But the resolution is sometimes different from our intention.

### Proposal

Ambiguities should be rejected.
Benchmarks and models should be fixed.

---

## Intercept cases

Michelson opcode often has 2 benchmarks:

* Intercept case: determines the interecept
* Non-intercept case: determines the coefficients

(Why we need this?)

The 2 benchmarks have the same base models:

(* ex Add_int *)
N_IAdd_int_const + N_IAdd_int_coeff * max size1 size2

---

## Typical ambiguities #1

Provided/dependent analysis *after the application of workload*. For intercept case, the sizes are fixed to `0` and the above formula is simplified to:

(* ex Add_int, intercept case *)
N_IAdd_int_const

This makes the dependency unambigous:

* Intercept case provides `N_IAdd_int_const`
* Non-intercept case depends on `N_IAdd_int_const` and provides `N_IAdd_int_coeff`

---

## Typical ambiguities #2

Model formula is complex and variables are not optimized out for intercept cases:

(* ex Mul_int *)
let a = size1 + size2 in 
N_IMul_int_coeff * a * log2 (1 + a)
+ N_IMul_int_const

At the intercept, `size1=0` and `size2=0` but the formula is not optimized enough to optimize the coeff variable out:

let a = 0 in 
N_IMul_int_coeff * a * log2 (1 + a)
+ N_IMul_int_const

3 problems:

* Both variables are provided by the intercept case.
* The coeff variable can be arbitrarily inferred.
* Non-intercept and intercept cases become ambiguous. One is chosen arbitrarily.

Possible fix:

* Implement `let` expansion at the constant folding when the bound value is a constant.

---

## Typical ambiguities #3

Intercept origin is **not at 0**, which does not coeff variables optimized away:

(* ex. Lsl_bytes *)
N_ILsl_bytes_const 
+ N_ILsl_bytes_bytes * size1
+ N_ILsl_bytes_shift * size2

The intercept point is fixed at `size1=0` and `size2=1`. After the workload application, the intercept model becomes:

N_ILsl_bytes_const + N_ILsl_bytes_shift

3 problems:

* Both variables are provided by the intercept case.
* They are arbitrary inferred.
* Non-intercept and intercept cases become ambiguous. One is chosen arbitrarily.

See 

Possible fix:

* Move the intercept point to 0:

  (* ex. Lsl_bytes *)
  N_ILsl_bytes_const 
  + N_ILsl_bytes_bytes * size1
  + N_ILsl_bytes_shift * (sat_sub size2 - int 1)

The graph becomes: 

---

## Other ambiguities

Some others out of the above examples. Not checked why they are ambiguous yet.

* ISapling_verify_update
* N_KMap_enter_body
* N_IMap_map
* N_KMap_enter_body_singleton
* N_KMap_exit_body

But all are with `interpreter` local model names.

---

## Conclusion

* Benchmark dependency analysis currently accepts ambiguities.
* Ambiguities are heuristically resolved (but with a bug at inference).
* Ambiguousity may lead to arbitrary inference of parameters including 0 values, which must be avoided.

Tentative fix

* Ambiguousity should be rejected.
* Many ambiguousity can be resolved by fixing the models and benchmakrs.
* Few still remain unchecked.