Compiler-directed code restructuring for operating with compressed arrays

Memory system utilization is an important issue for many embedded systems that operate under tight memory limitations. This is a strong motivation for recent research on reducing the number of banks required during execution of a given application. Reducing memory space requirements of an application can bring three potential benefits. First, if we are to design a customized memory system for a given embedded application, reducing its memory requirements can cut the overall cost. Second, if we are to execute our application in a multi-programmed environment, the saved memory space can be used by other applications, thereby increasing the degree of multi-programming. Third, it is also possible to reduce the energy consumption in a banked memory system by reducing the amount of memory space occupied by application data and placing the unused banks into low-power operating modes. This paper proposes a novel memory saving strategy for array-dominated embedded applications. The idea is to exploit the value locality in array data (e.g., those from the multi-media domain) by storing arrays in a compressed form to save memory space. Based on the compressed forms of the input arrays, our compiler-based approach automatically determines the compressed forms of the intermediate and output arrays and also automatically restructures the application code so that we can also reduce execution time (by exploiting value locality). Our experimental results show that this scheme is very effective in practice and reduces the memory space requirements of the applications tested by 19% on average. The experimental results also show that the proposed approach reduces the execution cycles of the original codes by 14% on average.