A Polynomial Algorithm for Partitioning Problems

被引：12

作者：

Tahaee, Seyed-Abdoreza ^{[1
]}

Jahangir, Amir Hossein ^{[1
]}

机构：

[1] Sharif Univ Technol, Dept Comp Engn, Tehran, Iran

来源：

ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS | 2010年 / 9卷 / 04期

关键词：

Algorithms; Design; Partitioning problem; hardware/software codesign; maximum flow minimum cut problem; NP-hard problems;

D O I：

10.1145/1721695.1721700

中图分类号：

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

学科分类号：

0812 ;

摘要：

This article takes a theoretical approach to focus on the algorithmic properties of hardware/software partitioning. It proposes a method with polynomial complexity to find the global optimum of an NP-hard model partitioning problem for 75% of occurrences under some practical conditions. The global optimum is approached with a lower bound distance for the remaining 25%. Furthermore, this approach ensures finding the 2-approximate of the global optimum partition in 97% of instances where technical assumptions exist. The strategy is based on intelligently changing the parameters of the polynomial model of the partitioning problem to force it to produce (or approach) the exact solution to the NP-hard model.

引用

页数：38

共 26 条

[1] Algorithmic aspects of hardware/software partitioning
Arató, P
Mann, ZA
Orbán, A
[J]. ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS, 2005, 10 (01) : 136 - 156
[2] Arató P, 2003, I S INTELL SIG PR, P197
[3] Banerjee S, 2004, INTERNATIONAL CONFERENCE ON HARDWARE/SOFTWARE CODESIGN AND SYSTEM SYNTHESIS, P122
[4] Binh NN, 1996, DES AUT CON, P527
[5] Chatha KS, 2001, PROCEEDINGS OF THE NINTH INTERNATIONAL SYMPOSIUM ON HARDWARE/SOFTWARE CODESIGN, P42, DOI 10.1109/HSC.2001.924648
[6] Dick RP, 1997, 1997 IEEE/ACM INTERNATIONAL CONFERENCE ON COMPUTER-AIDED DESIGN - DIGEST OF TECHNICAL PAPERS, P522, DOI 10.1109/ICCAD.1997.643589
[7] EDWARDS S, 2002, P IEEE, V85, P86
[8] Hardware/software partitioning of VHDL system specifications
Eles, P
Peng, Z
Kuchcinski, K
Doboli, A
[J]. EURO-DAC '96 - EUROPEAN DESIGN AUTOMATION CONFERENCE WITH EURO-VHDL '96 AND EXHIBITION, PROCEEDINGS, 1996, : 434 - 439
[9] A NEW APPROACH TO THE MAXIMUM-FLOW PROBLEM
GOLDBERG, AV
TARJAN, RE
[J]. JOURNAL OF THE ACM, 1988, 35 (04) : 921 - 940
[10] MiBench: A free, commercially representative embedded benchmark suite
Guthaus, MR
Ringenberg, JS
Ernst, D
Austin, TM
Mudge, T
Brown, RB
[J]. WWC-4: IEEE INTERNATIONAL WORKSHOP ON WORKLOAD CHARACTERIZATION, 2001, : 3 - 14

← 1 2 3 →