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