Design-Space Optimization of Streaming Applications
Date of Award
Winter 12-15-2013
Degree Name
Doctor of Philosophy (PhD)
Degree Type
Dissertation
Abstract
Many embedded and scientific applications are frequently pipelined
asynchronously and deployed on architecturally heterogeneous application-specific systems to meet performance requirements and resource constraints. We call such pipelined applications streaming applications. Typically, there are several design parameters in the algorithms and architectures used that, when customized, impact the tradeoff between different metrics of application performance as
well as resource utilization. Efficient optimal exploration of the space emanating from varying the design parameters is the goal of this research.
When using architecturally diverse systems to accelerate streaming
applications, the design search space is often complex. We present a global optimization framework comprising a novel domain-specific variation of branch-and-bound that reduces search complexity by exploiting the topology of the application's pipelining. We use queueing network models to embody the topological information. We exploit the topological information to discover decomposability through variable separability and to originate two novel decomposition techniques that we name convex decomposition and linear unchaining. We identify sufficient conditions for the use of the decomposition techniques and present formal proofs that the decomposition techniques preserve optimality.
Convex decomposition involves recognizing and
exploiting convex variables, preserving optimality even in the context of a non-convex optimization problem. The reduction in the search space from the convex decomposition is at minimum equal to the number of discrete values of the convex variable and potentially much higher. With linear unchaining, we show that we can partition constraints to reduce search complexity. We require only a feasible solution during unchaining because we expect to have already determined the value of the objective function. Thanks to unchaining, the number of configurations is linear rather than the product of the number of values of the variables associated with chaining.
The reduction in search complexity that we achieve for four real-world streaming applications is significant and ranges from about 107 to 10248. All four optimization problems are made solvable in reasonable time.
Language
English (en)
Chair
Roger D Chamberlain
Committee Members
Ron K Cytron, John W Lockwood, Paul Min
Comments
Permanent URL: https://doi.org/10.7936/K7D21VJJ