TY - GEN
T1 - Unchaining in design-space optimization of streaming applications
AU - Padmanabhan, Shobana
AU - Chen, Yixin
AU - Chamberlain, Roger D.
N1 - Publisher Copyright:
© 2013 IEEE.
PY - 2014/10/8
Y1 - 2014/10/8
N2 - 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 sub problems are less complex. Thanks to unchaining, the number of sub problems 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 bio sequence search application called BLASTN.
AB - 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 sub problems are less complex. Thanks to unchaining, the number of sub problems 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 bio sequence search application called BLASTN.
KW - decomposition of queueing networks
KW - design-space exploration
KW - domain-specific branch and bound
UR - http://www.scopus.com/inward/record.url?scp=84909993438&partnerID=8YFLogxK
U2 - 10.1109/DFM.2013.16
DO - 10.1109/DFM.2013.16
M3 - Conference contribution
AN - SCOPUS:84909993438
T3 - Proceedings - 2013 3rd Workshop on Data-Flow Execution Models for Extreme Scale Computing, DFM 2013
SP - 63
EP - 70
BT - Proceedings - 2013 3rd Workshop on Data-Flow Execution Models for Extreme Scale Computing, DFM 2013
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2013 3rd Workshop on Data-Flow Execution Models for Extreme Scale Computing, DFM 2013
Y2 - 8 September 2013 through 8 September 2013
ER -