Convexity in Non-convex Optimizations of Streaming Applications

Streaming data applications are frequently pipelined and deployed on application-specific systems to meet performance requirements and resource constraints. Typically, there are several design parameters in the algorithms and architectures used that impact the application performance as well as resource utilization. Efficient exploration of this design space is the goal of this research. When using architecturally diverse systems to accelerate streaming applications, the design search space is often complex. The search complexity can be reduced by recognizing and exploiting convex variables to perform convex decomposition, preserving optimality even in the context of a non-convex optimization problem. This paper presents a formal treatment of convex variables and convex decomposition, including a proof that the technique preserves optimality. It also quantifies the reduction in the search space that is realized, at minimum equal to the number of distinct values of the convex variable and potentially much higher.