|
|
# 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 |