High-Precision Performance Estimation for the Design Space Exploration of Dynamic Dataflow Programs

Abstract

The implementation and optimization of dynamic dataflow programs on multi/many-core platforms require solving a very difficult problem: how to partition and schedule the processing elements and dimension their interconnecting buffers according to given optimization functions in terms of throughput, memory usage, and energy consumption. This problem is NP-hard even for two cores. Thus, finding a close-to-optimal solution consists of exploring the design space by appropriate heuristics identifying those design points that maximize or minimize the desired (multiple) objective functions subject to a set of constraints. In general, exploring the design space efficiently is a challenging task due to the massive number of admissible design points. Efficient estimation methodologies are necessary to support an effective search of the design space by reducing to a minimum the cost and the number of measurements on the physical platform. This paper presents a new methodology that provides high-precision estimations of dynamic dataflow programs performances on multi/many-core platforms for any set of design configurations. The estimations rely on the execution trace post-processing obtained by a single execution of the program. The paper describes the estimation methodology, implementation tools, and the information that is obtained from many/multi-core dataflow executions and used to drive the optimization heuristics.