Unchaining in Design-space Optimization of Streaming Applications

Abstract—Data-streaming applications are frequently pipelined and deployed on hybrid systems to meet performance requirements and resource constraints. With freedom in the design of algorithms and architectures, the search complexity can explode. A popular approach to reducing search complexity is to decompose the search space while preserving optimality. We present a novel decomposition technique called unchaining that partitions the problem such that the resulting subprob-lems are less complex. Thanks to unchaining, the number of subproblems from the decomposition is linear in the number of chained blocks in the variable-constraint matrix (instead of being their product). Finally, we present a queueing network model and the quantitative search space reduction for a real-world implementation of a biosequence search application called BLASTN. Keywords-design-space exploration; domain-specific branch and bound; decomposition of queueing networks I