PACE: A dynamic programming algorithm for hardware/software partitioning

Peter Voigt Knudsen; Jan Madsen

doi:10.1109/HCS.1996.492230

PACE: A dynamic programming algorithm for hardware/software partitioning

Peter Voigt Knudsen
, Jan Madsen

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

796 Downloads (Orbit)

Abstract

This paper presents the PACE partitioning algorithm which is used in the LYCOS co-synthesis system for partitioning control/dataflow graphs into hardware and software parts. The algorithm is a dynamic programming algorithm which solves both the problem of minimizing system execution time with a hardware area constraint and the problem of minimizing hardware area with a system execution time constraint. The target architecture consists of a single microprocessor and a single hardware chip (ASIC, FPGA, etc.) which are connected by a communication channel. The algorithm incorporates a realistic communication model and thus attempts to minimize communication overhead. The time-complexity of the algorithm is O(n2·&Ascr;) and the space-complexity is O(n·&Ascr;) where &Ascr; is the total area of the hardware chip and n the number of code fragments which may be placed in either hardware or software

Original language	English
Title of host publication	Proceedings. Fourth International Workshop on Hardware/Software Co-Design (Code/CASHE `96)
Publisher	IEEE
Publication date	1996
Pages	85-92
ISBN (Print)	0-8186-7243-9
DOIs	https://doi.org/10.1109/HCS.1996.492230
Publication status	Published - 1996
Event	Fourth International Workshop on Hardware/Software Co-Design (Code/CASHE `96) - Pittsburgh, Pennsylvania, USA Duration: 1 Jan 1996 → …

Conference

Conference	Fourth International Workshop on Hardware/Software Co-Design (Code/CASHE `96)
City	Pittsburgh, Pennsylvania, USA
Period	01/01/1996 → …

Bibliographical note

Copyright: 1996 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE

Access to Document

10.1109/HCS.1996.492230

KnudsenFinal published version, 797 KB

OpenUrl availability

Check availability in DTU Findit

Cite this

@inproceedings{0b1dae722a8444d482d8b8e23faea993,

title = "PACE: A dynamic programming algorithm for hardware/software partitioning",

abstract = "This paper presents the PACE partitioning algorithm which is used in the LYCOS co-synthesis system for partitioning control/dataflow graphs into hardware and software parts. The algorithm is a dynamic programming algorithm which solves both the problem of minimizing system execution time with a hardware area constraint and the problem of minimizing hardware area with a system execution time constraint. The target architecture consists of a single microprocessor and a single hardware chip (ASIC, FPGA, etc.) which are connected by a communication channel. The algorithm incorporates a realistic communication model and thus attempts to minimize communication overhead. The time-complexity of the algorithm is O(n2·\&Ascr;) and the space-complexity is O(n·\&Ascr;) where \&Ascr; is the total area of the hardware chip and n the number of code fragments which may be placed in either hardware or software",

author = "Knudsen, \{Peter Voigt\} and Jan Madsen",

note = "Copyright: 1996 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE; Fourth International Workshop on Hardware/Software Co-Design (Code/CASHE `96) ; Conference date: 01-01-1996",

year = "1996",

doi = "10.1109/HCS.1996.492230",

language = "English",

isbn = "0-8186-7243-9",

pages = "85--92",

booktitle = "Proceedings. Fourth International Workshop on Hardware/Software Co-Design (Code/CASHE `96)",

publisher = "IEEE",

address = "United States",

}

Knudsen, PV & Madsen, J 1996, PACE: A dynamic programming algorithm for hardware/software partitioning. in Proceedings. Fourth International Workshop on Hardware/Software Co-Design (Code/CASHE `96). IEEE, pp. 85-92, Fourth International Workshop on Hardware/Software Co-Design (Code/CASHE `96), Pittsburgh, Pennsylvania, USA, 01/01/1996. https://doi.org/10.1109/HCS.1996.492230

TY - GEN

T1 - PACE: A dynamic programming algorithm for hardware/software partitioning

AU - Knudsen, Peter Voigt

AU - Madsen, Jan

N1 - Copyright: 1996 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE

PY - 1996

Y1 - 1996

N2 - This paper presents the PACE partitioning algorithm which is used in the LYCOS co-synthesis system for partitioning control/dataflow graphs into hardware and software parts. The algorithm is a dynamic programming algorithm which solves both the problem of minimizing system execution time with a hardware area constraint and the problem of minimizing hardware area with a system execution time constraint. The target architecture consists of a single microprocessor and a single hardware chip (ASIC, FPGA, etc.) which are connected by a communication channel. The algorithm incorporates a realistic communication model and thus attempts to minimize communication overhead. The time-complexity of the algorithm is O(n2·&Ascr;) and the space-complexity is O(n·&Ascr;) where &Ascr; is the total area of the hardware chip and n the number of code fragments which may be placed in either hardware or software

AB - This paper presents the PACE partitioning algorithm which is used in the LYCOS co-synthesis system for partitioning control/dataflow graphs into hardware and software parts. The algorithm is a dynamic programming algorithm which solves both the problem of minimizing system execution time with a hardware area constraint and the problem of minimizing hardware area with a system execution time constraint. The target architecture consists of a single microprocessor and a single hardware chip (ASIC, FPGA, etc.) which are connected by a communication channel. The algorithm incorporates a realistic communication model and thus attempts to minimize communication overhead. The time-complexity of the algorithm is O(n2·&Ascr;) and the space-complexity is O(n·&Ascr;) where &Ascr; is the total area of the hardware chip and n the number of code fragments which may be placed in either hardware or software

U2 - 10.1109/HCS.1996.492230

DO - 10.1109/HCS.1996.492230

M3 - Article in proceedings

SN - 0-8186-7243-9

SP - 85

EP - 92

BT - Proceedings. Fourth International Workshop on Hardware/Software Co-Design (Code/CASHE `96)

PB - IEEE

T2 - Fourth International Workshop on Hardware/Software Co-Design (Code/CASHE `96)

Y2 - 1 January 1996

ER -

PACE: A dynamic programming algorithm for hardware/software partitioning

Abstract

Conference

Bibliographical note

Access to Document

OpenUrl availability

Fingerprint

Cite this