This chapter concludes the book. First, we summarize the different versions of the memory allocation problem and discuss the diversification and intensification of metaheuristics designed for these versions. Then, we present the main conclusions and perspectives emerging from this work.
In this book, we have introduced four versions of the memory allocation problem. The general objective of these problems is focused either on the memory management or on the data assignment in embedded systems because both have a significant impact on the main cost metrics, such as cost, area, performance and power consumption. These cost metrics are the main features taken into account by designers in industry and by customers, requiring the integration of an increasing number of functionalities.
The first version of the memory allocation problem is concerned with hardware optimization; it is focused on the memory architecture (the memory architecture can be composed of memory banks, an external memory, scratchpads, etc.) of the application. The three remaining problems are related to the data binding; it searches for an optimal memory allocation of data structures to a fixed memory architecture. Table 7.1 summarizes the main characteristics, constraints and objective function of these problems as well as metaheuristics designed for them.
All versions of the memory allocation problem are NP-hard problems. For each version, the number of constraints increases, and the objective function and the characteristics of the memory allocation problems change. Thus, for each version, the complexity in the memory allocation problem increases. Differences between the first version problem and the last two versions are noticeable.
The first problem searches for the minimum number of memory banks for which all non-auto-conflict are closed and this problem can be modeled as the vertex coloring problem. In the second problem, the number of memory banks is fixed and we search for an optimal memory allocation of data structures to memory banks to minimize the cost produced by the open conflicts; this problem is equivalent to the k-weighted graph coloring problem. In the third problem, in addition to a fixed number of memory banks, the capacity of memory banks is limited. The memory architecture has an external memory, which has enough capacity to store all data structures, but the access to this external memory is p ms slower than to memory banks. Moreover, the size of the data structures and the number of accesses are taken into account. The main difference between the last problem and the general problem is that the time is split into time intervals. Allocation of data structures can change at each time interval, so we must consider the cost for moving them. Thus, we search for a memory allocation for each time interval to minimize the total time by accessing and moving data structures.
As the complexity of the version problems increases, we use more sophisticated methods. These methods have reached good results. The following section analyzes these approaches in terms of intensification and diversification.
For addressing the remaining three problem versions, we have proposed exact mathematical models and metaheuristic approaches. These metaheuristics are inspired by the methods originally designed for the vertex coloring problems. In this section, we examine the proposed approaches in terms of intensification and diversification.
We have proposed two metaheuristics to tackle this problem. The first metaheuristic is a tabu search method called Tabu-Allocation and the second metaheuristic is an evolutionary algorithm called Evo-Allocation.
The diversification in this method is due to the presence of the tabu list and mainly due to the dynamic size of this tabu list, it is relative to Reactive Tabu Search [BAT 94]. This allows us to explore new neighborhoods and escape from local optimum. For example, using a static size of the tabu list, the instance mpeg2enc reaches a cost of 33.22 ms, and using a dynamic size the method reaches a cost of 32.09 ms, that is the method improves the solution by 3.4% by using a dynamic size of tabu list.
Table 7.1. Summary of the memory allocation problem versions
The method intensifies the search by accepting an enhanced solution as initial one; thus, its neighborhood is explored to find a better solution.
Three motives guarantee the diversification in the population of this approach. The first motive is because the algorithm accepts an offspring (new solution) if the distance to its parents is greater than a fixed threshold. The objective is to avoid having too many solutions with similar characteristics. The second reason is the random selection of several parents to the crossover; thus, it allows us to cross good and bad parents to produce offsprings with new characteristics. The last reason is the criterion of statistical variance of solution costs to update the population; this allows refreshing the population. For example, the method reaches the cost of 762 ms for the instance r125.5 without the statistic variance condition, and it reaches the cost of 734 ms with this criterion, that is the solution is improved by 3.7% using the statistical variance for updating the population.
The intensification of Evo-Allocation is due to three reasons. The first reason is the crossover function, as it takes the best allocations of data structures from each solution to produce a new one; so the good characteristics of parents solutions are kept in the population. The second reason is the tabu search (with a dynamic size of tabu list) used to improve the quality of the offspring. The last reason is presented in the way of updating the population that replaces the worst solutions with new solutions.
For this problem, we have proposed a variable neighborhood search based approach hybridized with a tabu search inspired method, that is Vns-Ts-MemExplorer.
There are three main motives that assure the diversification in this method. The current solution is perturbed, so this forces us to explore new neighborhoods and to find new good solutions. Another important subject to diversification is the second neighborhood N1, which allows the method to explore prohibited neighborhoods. Thus, the method explores neighborhoods beyond the usual ones and it allows the method to escape easily from local optimums. The last motive is the combination of the two neighborhoods. This combination leads to a better cover of the search space. If we use a single neighborhood, either N0 or N1, the objective value is on average degraded by 56% to 21%, respectively.
The intensification is guaranteed by admitting enhanced solutions and by using the tabu search with a dynamic size of the tabu list to explore the neighborhoods. The characteristics of intensification and diversification of this tabu search are also presented in Vns-Ts-MemExplorer. If this approach uses a classic tabu search for the computational test, the solution cost is degraded by 35% on average.
Two approaches have been proposed for this problem. As the long-term and the short-term approaches take advantage of metaheuristics designed for the previous memory allocation problem, its diversification and intensification are inherited from Vns-Ts-MemExplorer.
We summarize the main results of this chapter.
Addressing the first memory allocation problem has allowed us to introduce three new upper bounds on the chromatic number. These upper bounds do not make any assumption on the graph structure. From the theoretical and computational assessment, we have demonstrated the superiority of our bounds over the well-known bounds from the literature.
These upper bounds are easily computable even for large graphs. Indeed, there exist advanced bounds on the chromatic number, but they required a computational time longer than 20 minutes. It is far too long for the electronic chip designers, who must solve repeatedly the first version problem to do “what if” studies.
Evo-Allocation returns the best results for the second version of the memory allocation problem. This is due to its rigorous control of population diversity and a multi-parent crossover, as well as the variable size of the tabu list. Vns-Ts-MemExplorer reaches excellent results for the general memory allocation problem due to its two neighborhoods and the local search method (TabuMemex). The long-term approach achieves good results in a reasonable amount of time for the dynamic memory allocation problem. This is due to the approach taking into account the application requirements for the current and future time intervals.
We have shown that the results produced by our metaheuristics are better in terms of an objective function and running time than the results returned by the ILP and local search solvers. The success of metaheuristics designed for the memory allocation problems is due to their well-balanced search in terms of intensification and diversification.
The exact approach is suitable for today’s applications; it is clearly not for tomorrow’s needs. The proposed metaheuristics appear to be suitable for the needs of today and tomorrow. Moreover, the very modest CPU time compared to the exact method is an additional asset for integrating them to CAD tools, letting designers test different options in a reasonable amount of time.
The methods inspired by graph coloring problems can be successfully extended to more complex allocation problems for embedded systems, thereby assessing the gains made by using these methods to specific cases in terms of energy consumption. Moreover, the approaches designed for the version of memory allocation give promising perspectives for using metaheuristics in the field of electronic design. Thus, this shows that operations research can bring significant contributions to electronics.
The following theoretical and practical perspectives can be drawn from this chapter.
We can use more information on graph topology for producing competitive upper bounds for the chromatic number. Indeed, we have proposed three upper bounds based on the degree of saturation of vertices and on the number of vertices and edges. For example, we might consider the graph density to generate new upper bounds.
The general and dynamic memory allocation problems can be seen as a mix of the vertex coloring and the bin packing problems. The bin packing problem consists of packing a set of objects into a finite number of bins of limited capacity so as to minimize the number of bins used. In the memory allocation problem, the data structures represent the objects and the memory banks represent the bins. Hence, it could be interesting to adapt algorithms dedicated to the bin packing problem to our memory allocation problems.
A good perspective is the implementation of an algorithm based on the greedy algorithm proposed by Dantzig [DAN 57] to solve the unbounded knapsack problem. The knapsack problem is given a set of items, each with a weight and a value, determining which items to include in a knapsack such that the total weight is less than or equal to a given limit and the total value of the knapsack is maximized. The idea is to compute a ratio for each data structure that is equal to the number of accesses divided by the size of the data structure. Then, there is the allocation of data structures sorted by a decreasing ratio. Thus, the small data structures that are accessed more often by the processor are more likely to be allocated to memory banks, and the remaining data structures can be allocated to the external memory. In this way, the total access cost may be minimized.
Sometimes, the long-term approach is outperformed by the short-term approach, because the long-term approach ignores the potential for updating the solution at each iteration. Consequently, future work should concentrate on a mid-term approach to combine the benefits of both approaches. The main idea is weighting the requirements of each time interval; thus, future requirements are less and less weighted as they are far away from the current time interval. This allows the mid-term approach to move easily the data structure at the time intervals by taking into account the future needs of the application. In this approach, the first step is determining the appropriate weight coefficients at each time interval. The mid-term approach is similar to the long-term approach; it builds the interval solution from the parent solution, which is selected among two candidate solutions. The first solution is the parent solution for the previous interval and the second solution is the solution found by MemExplorer solved with the weighted requirements to the current interval to the last one. The solution associated with the minimum cost is selected as the parent solution.
Based on the characteristics of previous algorithms, we might design a global approach for the dynamic memory allocation problem that builds a solution for all time intervals or implement other sophisticated metaheuristics, for example the honey bee algorithm [TOV 04], which is inspired by the behavior of a honey bee colony involved in nectar collection; the ant colony algorithm [COL 91], which is based on the behavior of ants seeking a path between their colony and a source of food; the scatter search and path relinking [GLO 98, GLO 00], which are the evolutionary methods based on joining a solution based on generalized path constructions.
For the larger instances of the memory allocation problems, it is not possible to solve the ILP with the current solvers. However, the limit of metaheuristics is that they do not guarantee optimal solutions. Thus, it seems a good idea to design matheuristics [MAN 09, HAN 09] to address these problems because they combine metaheuristics and mathematical programming techniques.
The success of our approaches gives promising perspectives for using metaheuristics in the field of electronic design. For example, in the memory allocation problem with a small granularity, data structures are split into words and the objective is to allocate them to memory banks so as to minimize the total access time [CAT 98b]. Another interesting problem, where our approaches can be adapted, is the case of multi-port memories, and the conflict graph that extends with loops and hyperedges [CAT 98b]. Here, the conflicts can be between two or more data structures.
These metaheuristics can be suitable for the register allocation problem, where the goal is to find an allocation of scalars to registers which takes into account the conflicts between scalars and minimizes the number of registers. They can be adapted to scratchpad optimization, for determining which instructions can be located in the scrachtpad for a rapid access.
Our approaches might be successfully extended to the data binding problems discussed in Chapter 1, for example, in the memory partition problem for low energy, which consists of partitioning data structures into a fixed number of memory banks so as to minimize the interferences between data structures. Also, it can be extended to the problems where the capacity of memory banks is limited, and to problems that use an external memory to store data structures.