The purpose of this project is to experimentally validate a proposed approach for improving the performance of the MUSIC planning based adaptation middleware using socalled memoization techniques. Adaptation planning in the MUSIC middleware relies on predicting the QoS of software components depending on contextual situation of a mobile device using socalled QoS predictor functions. Many QoS predictors perform redundant calculations. Within a single run of the planning algorithm the same predictor will be invoked with exactly the same arguments (in our case the same context elements) several times, or, over the course of time in a system run, a predictor may be invoked by different components or routines with the same or similar inputs. This observation leads to the obvious conclusion that in some cases it is beneficial to store the previously calculated values and only perform a calculation in situations that have not been seen previously. This technique is called memoization, and the "manual" version of this generally involves building lookup tables. The term "memoization" refers to the process of tabulating results in order to prevent wasted calculations.
The work will be done in the context of the European project MUSIC using the MUSIC development and run-time platform. The following tasks may be part of the project:
- design of memozation as an integrated part of the MUSIC planning based middleware
- implementation of memoization in the MUSIC middleware platform based on the above design
- validation of memoization by performance mesurements.
Some comments on validation:
In most cases, memoization is a time vs. memory trade-off. In some cases, where a frequently repeated function generates large structures or a lot of garbage, memoization may actually save memory by simply reusing the previously created structures. However, in most cases you sacrifice space in order to gain speed. These trade-offs should be evaluated carefully to avoid consuming large amounts of memory with little speedup. Several sensors can assist in this process, reporting on how many times a memorised function was called, broken down by whether those calls resulted in new calculations or previous results being returned from the hash table. Tuning tools can allow the developer to execute forms in a context where certain predictors are temporarily memorised. These tools can also run a body of code three times: unmemorised, memorised but with an empty cache, and memorised with the values of the previous run, returning time and space information for each run. The time vs. memory evaluation can then be used to decide whether a particular property predictor has to be memorised, as well as the expected life-span of such a memoization.
There may be an opportunity to combine this project with a job as part time scientific programmer in the MUSIC project.
Links:
- http://heim.ifi.uio.no/~frank/D1.3.pdf (look at chapter 2 and 8.6.2 in particular)
- http://www.ifi.uio.no/forskning/grupper/nd/projects/2006/music/ (MUSIC project)
- http://ist-music.berlios.de/ (MUSIC official web site)
Program
Informatikk