Optimal design-space exploration of streaming applications

Many embedded and scientific applications are pipelined (i.e., streaming) and deployed on application-specific systems. Typically, there are several design parameters in the algorithms and architectures used that impact the tradeoff between different metrics of application performance as well as resource utilization. Efficient automatic exploration of this design space is the goal of our research. We present a global optimization framework comprising a domain-specific variation of branch-and-bound that reduces search complexity by exploiting the topology of the application's pipelining. We exploit the topological information to discover decomposability through the canonical Jordan block form. The reduction in search complexity for four real-world streaming applications (drawn from the literature) is significant, ranging from a million-fold reduction in search space size to a reduction factor of 10 billion. All four optimization problems are thereby solvable in reasonable time.