Memory Allocation Problems in Embedded Systems

Embedded systems are strongly present in the contemporary society, they are sup- posed to make our lives more comfortable. In the industry, embedded systems are used to manage and control complex systems (e.g nuclear power plants, telecommunica- tion, flight control, etc.); they are also taking an important place in our daily activities (e.g., smartphones, security alarms, traffic lights, etc.).
The significant development in embedded systems is mainly due to advances in nano-technology. These continuous advances have made possible the design of minia- turized electronic chips, leading to drastically extend the features supported by embed- ded systems. Smartphones that can surf the WEB and process HD images are a typical example. In addition to market pressure, this context has favored the development of Computer Assisted Design CAD software, which bring a deep change in the designers' line of work. While technology offers more and more opportunities, the design of em- bedded systems becomes more and more complex. Indeed, the design of an integrated circuit, whose size is calculated in billions of transistors, thousands of memories, etc., requires the use of competitive computer tools. These tools have to solve optimization problems to ensure a low cost in terms of area and time, and they must meet some standards in electronics.
Currently, in the electronics industry, the problems are often addressed using either ad-hoc methods based on the designer expertise or general methods (typically genetic algorithms). But both solving methods do not work well in large scale industrial problems.

On the other hand, computer-aided design software like Gaut [Gau93, COU 06] have been developed to generate the architecture of a chip (circuit) from its specifi- cations. While the design process is significantly faster with these types of software, the generated layouts are considered to be poor on power consumption and surface compared to human expert designed circuits. This is a major drawback as embedded products have to feature low-power consumption. In the design of embedded systems, memory allocation and data assignment are among the main challenges that electronic designers have to face. Indeed, they deeply impact the main cost metrics (power consumption, performance and area) in elec- tronic devices [WUY 96]. Thus designers of embedded system have to carefully pay attention to minimize memory requirements, improving memory throughput and lim- iting the power consumption by the system's memory. Electronic designers attempt to minimize memory requirements with the aim of lowering the overall system costs.

Moreover, the need for optimization of the allocation of data structures is expected to become even more stringent in the future, as embedded systems will run heavy com- putations. As an example, some cell phones already support multi threading operating systems.
For these reasons, we are interested in the allocation of data structures into memory banks. This problem 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. As it has often been observed in microelectronics, this complex problem is poorly or not modeled. The proposed solutions are based on a lower modeling level that often only considers one objective at a time. Also, the optimization of methods is little (or not) quantified, only the running time is available and assessed. Thus, the models and data are not analyzed much. In this work we model this problem and propose optimization methods from oper- ations research for addressing it.

II. Unconstrained memory allocation problem
III. Memory allocation with constraint on the number of memory banks
IV. General memory allocation problem
V. Dynamic memory allocation problem
VI. Conclus