Mapping DAGs on Heterogeneous Platforms Using Logic-Based Benders Decomposition

被引：2

作者：

Emeretlis, A. ^{[1
]}

Theodoridis, G. ^{[1
]}

Alaingis, P. ^{[2
]}

Voros, N. ^{[2
]}

机构：

[1] Univ Patras, Dept Elect & Comp Engn, Patras, Greece

[2] TEI Western Greece, Dept Comp & Informat Engn, Antirio, Greece

来源：

2015 IEEE COMPUTER SOCIETY ANNUAL SYMPOSIUM ON VLSI | 2015年

关键词：

Multicore architectures; DAGs mapping; Benders decomposition; ILP - CP optimization;

D O I：

10.1109/ISVLSI.2015.98

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Efficient mapping of DAGs on heterogeneous multicore platforms is a key component for modern embedded applications. An approach based on the Benders decomposition principle that uses a heuristic pre-solver and Integer Linear and Constraint Programming methods to find proven-optimal solutions is introduced. We present multiple cuts generation schemes, that improve the performance of the solution process, and extensive experimental results, that show significant speedups compared to the pure ILP-based method.

引用

收藏

页码：119 / 124

页数：6

相关论文

共 18 条

[1] Optimal resource allocation and scheduling for the CELL BE platform [J].

Benini, Luca ;

Lombardi, Michele ;

Milano, Michela ;

Ruggiero, Martino .

ANNALS OF OPERATIONS RESEARCH, 2011, 184 (01) :51-77

[2] DAG Scheduling Using a Lookahead Variant of the Heterogeneous Earliest Finish Time Algorithm [J].

Bittencourt, Luiz F. ;

Sakellariou, Rizos ;

Madeira, Edmundo R. M. .

PROCEEDINGS OF THE 18TH EUROMICRO CONFERENCE ON PARALLEL, DISTRIBUTED AND NETWORK-BASED PROCESSING, 2010, :27-34

[3] Comparative evaluation of the robustness of dag scheduling heuristics [J].

Canon, Louis-Claude ;

Jeannot, Emmanuel ;

Sakellariou, Rizos ;

Zheng, Wei .

GRID COMPUTING: ACHIEVEMENTS AND PROSPECTS, 2008, :73-+

[4]

Gupta Sachi, 2010, Proceedings of the 2nd International Conference on Machine Learning and Computing (ICMLC 2010), P267, DOI 10.1109/ICMLC.2010.50

[5] Logic-based Benders decomposition [J].

Hooker, JN ;

Ottosson, G .

MATHEMATICAL PROGRAMMING, 2003, 96 (01) :33-60

[6]

Hooker JohnN., 2011, Integrated Methods for Optimization, V2nd

[7] Distinctive image features from scale-invariant keypoints [J].

Lowe, DG .

INTERNATIONAL JOURNAL OF COMPUTER VISION, 2004, 60 (02) :91-110

[8] A decomposition framework for the scheduling of single- and multi-stage processes [J].

Maravelias, CT .

COMPUTERS & CHEMICAL ENGINEERING, 2006, 30 (03) :407-420

[9] Constraint Programming Approach to Reconfigurable Processor Extension Generation and Application Compilation [J].

Martin, Kevin ;

Wolinski, Christophe ;

Kuchcinski, Krzysztof ;

Floch, Antoine ;

Charot, Francois .

ACM TRANSACTIONS ON RECONFIGURABLE TECHNOLOGY AND SYSTEMS, 2012, 5 (02)

[10]

Milano M, 2011, SPRINGER SER OPTIM A, V45, P1, DOI 10.1007/978-1-4419-1644-0_1