Formalization-thoughts.md

+# Formalisation of the MQuAT-SLAM-Demo
+
+- MQuAT = Multi Quality AutoTuning
+- PE = processing element
+- SLAM = Simultaneous Localization And Mapping
+
+## Auxiliary thoughts
+
+- actually two kinds of requests
+	- "work request" → execute computation
+		- no scheduling/optimization done
+	- "scheduling/optimization request" → change selection/mapping of system
+	- using RACR both requests can be sent at same time, because scheduling
+	  result is cached and can be re-used
+- benchmark resuts depend on actual hardware structure, because all qualities
+  are measured for one "complete run" (roboter driving from A to B) and
+  not for one single computation of Sample step
+- current hardware status must be taken into account for scheduling
+  to avoid to switch on and off too many times
+- actual result of scheduling should be observed after scheduling
+	- learn, how well was request scheduled
+	- adopt benchmark functions
+- possible approach: pattern matching for graphs
+	- one graph *S* describing software tasks with their dependencies
+	- second graph *H* describing hardware PEs and their communication possibilities
+	- find matching *m*, such that software- and request-requirements
+	  are fulfilled
+	- maybe find an optimizing approach to find a mapping, such that an
+	  objective found is minimized/maximized
+
+## Available static information
+
+- Benchmark results
+	- run-time, precision, energy = function of numParticles and workers¹
+
+¹workers is a description of workers used
+
+## Input
+
+- Request
+	- metaparameter(s) (required)
+	- opt. max response time (*default: no constraint*)
+	- opt. min precisicion = max deviation = max error (*default: no constraint*)
+	- opt. objective function, e.g. minimize response time (*default: minimize energy*)
+
+## Approach one (very simplistic)
+
+### Output
+
+- (near-) optimal solution for
+	- number of particles to compute
+	- **number of** workers to use for computation
+- such that
+	- no given constraint is violated
+	- optimality w.r.t. to given objective function
+
+### Hardware
+
+- only one kind of PE, i.e. cubieboards
+- don't explicitely model PEs, only number of active/maximum workers
+	
+## Approach two (hierachical, heterogeneous)
+
+### Output
+
+- (near-) optimal solution for
+	- number of particles to compute
+	- **selection of** workers to use for computation
+- such that
+	- no given constraint is violated
+	- optimality w.r.t. to given objective function
+
+### Hardware
+
+- like in racr-tune-demo (hierarchy of heregenous PEs)
+
+## Possible scheduling/optimization algorithms