Optimization Methodology For Dynamic Applications Utilizing Tree Data Structures In Embedded Systems

Abstract

Applications that were previously executed in High Performance Computers (HPC) systems are increasingly implemented in embedded devices. Modern embedded systems are now capable of executing complex and demanding applications that are usually based on large dynamic data structures. The design of the critical data structures of the applications, in a large extent, determines the performance and the memory requirements of the whole system. The work of selecting the correct data structure for an application is not an easy or obvious one. Depending on the platform of interest, different requirements may need to be satisfied. The Dynamic Data Structure Refinement methodology was originally developped to help the designer evaluate different data structure selections in an effective and automatic manner. It provides optimizations, mainly in list and array data structures, which are based on the application’s features and access patterns. In this work, various aspects of the methodology are extended: first, we integrate radix tree optimizations to enrich the existing collection and make the methodology compatible with a larger group of modern applications. Then, we provide a set of platform-aware data structure implementations, for performing optimizations based on the hardware features. The extended methodology is evaluated using a wide set of synthetic and real-world benchmarks on the Myriad and Freescale platforms, in which we achieved a performance and memory trade-offs up to 30%. Additionally, Pareto optimal data structure implementations that were not available by the previous methodology, are now identified with the extended one.