Abstract:

It is a research hotspot to minimize the number of bankselection instructions in the partitioned memory architecture. Analyzing the features of this problem, we construct a graph partition model for bank selection and propose a twostage heuristic search algorithm. This algorithm uses the size of nodes and partition capacity to get an initial solution quickly, and then uses the edge weights between nodes and the weighs between partitions as the heuristic parameters to search for the better solution. Experiments on MiBench benchmark and a real embedded system validate the effectiveness of the proposed model and algorithm.  Compared to the VPAB algorithm, the proposal can achieve an average optimization rate of 37.99%, which is slightly better than the mature commercial compiler PICC, and can reduce the number of bank selection instructions largely.

Key words: partitioned memory;graph model;heuristic search;embedded system