You are here

Memory allocation

General approaches

For now more than two years, we apply optimization techniques to solve some of the memory allocation problem arisen in compilation of source code (for electronic design applications). Our work was first oriented to the graph coloring problem and then to the k-weighted graph coloring problem. Now we try to handle the dynamic aspect of the memory allocation problem.

An early version of the problem is the static memory allocation problem refereed as MemExplorer. Solution approaches and results are published in Journal of Heuristics. you can access our work under the reference below.

M. Soto, A. Rossi, and M. Sevaux. A mathematical model and a metaheuristic approach for a memory allocation problem. Journal of Heuristics, 18(1):149-167, 2012. http://dx.doi.org/10.1007/s10732-011-9165-3.

@article{soto-11,
  author = {M. Soto and A. Rossi and M. Sevaux},
  title = {A mathematical model and a metaheuristic approach for a memory allocation problem},
  journal = {Journal of Heuristics},
  year = {2012},
  abstract = {Memory allocation in embedded systems is one of the main challenges that electronic designers have to face. This part, rather difficult to handle is often left to the compiler with which automatic rules are applied. Nevertheless, an optimal allocation of data to memory banks may lead to great savings in terms of running time and energy consumption. This paper introduces an exact approach and a vns-based metaheuristic for addressing a memory allocation problem. Numerical experiments have been conducted on real instances from the electronic community and on dimacs instances expanded for our specific problem.},
  volume = {18},
  number = {1},
  pages = {149-167},
  url = {http://dx.doi.org/10.1007/s10732-011-9165-3},
}

Recent work

Electronic embedded systems designers aim at finding a trade-off between cost and power consumption. As cache memory management has been shown to have a significant impact on power consumption, we address dynamic memory allocation for embedded systems with a special emphasis on time performance. In this work, time is split into time intervals, into which the application to be implemented by the embedded system requires accessing to data structures. The proposed iterative metaheuristics aim at determining which data structure should be stored in cache memory at each time interval in order to minimize reallocation and conflict costs. These approaches take advantage of metaheuristics previously designed for a static memory allocation problem version.

Benchmark instances

Instances of the MemExplorer problem can be downloaded under the name INSTANCES_MAP_STA.zip.

The latest version of the problem concerns the dynamic memory allocation problem. A set of instances with the description of the instance is available under the name INSTANCES_MAP_DYN.zip.

Related presentations

Evocop Presentation

The OR-Group was represented by María Soto at the Evo* conference (The main European events on Evolutionary Computation) that took place in Torino, Italy on 27-29 April 2011. Featuring the latest in theoretical and applied research, evo* topics include recent genetic programming challenges, evolutionary and other meta-heuristic approaches for combinatorial optimization, evolutionary algorithms, machine learning and data mining techniques in the biosciences, in numerical optimization, in music and art domains, in image analysis and signal processing, in hardware optimization and in a wide range of applications to scientific, industrial, financial and other real-world problems. María Soto presented in the stream "Evocop".

María Soto presented at the french OR meeting (ROADeF'2011)

María Soto is about to complete her PhD. She gave a presentation at the french OR meeting ROADeF'2011 in Saint-Etienne. The presentation was given in the session "RO et micro-électronique". The presentation can be downloaded here.