PACE: A dynamic programming algorithm for hardware/software partitioning

Peter Voigt Knudsen, Jan Madsen

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    401 Downloads (Pure)

    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·𝒜) and the space-complexity is O(n·𝒜) where 𝒜 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 languageEnglish
    Title of host publicationProceedings. Fourth International Workshop on Hardware/Software Co-Design (Code/CASHE `96)
    PublisherIEEE
    Publication date1996
    Pages85-92
    ISBN (Print)0-8186-7243-9
    DOIs
    Publication statusPublished - 1996
    EventFourth International Workshop on Hardware/Software Co-Design (Code/CASHE `96) - Pittsburgh, Pennsylvania, USA
    Duration: 1 Jan 1996 → …

    Conference

    ConferenceFourth International Workshop on Hardware/Software Co-Design (Code/CASHE `96)
    CityPittsburgh, Pennsylvania, USA
    Period01/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

    Cite this