Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports from UMIACS
    • View Item
    •   DRUM
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports from UMIACS
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Cycle-Breaking Techniques for Scheduling Synchronous Dataflow Graphs

    Thumbnail
    View/Open
    hsu2007x2.pdf (207.3Kb)
    No. of downloads: 770

    Date
    2007-02
    Author
    Hsu, C.
    Bhattacharyya, S. S.
    Metadata
    Show full item record
    Abstract
    System-level modeling, simulation, and synthesis using the synchronous dataflow (SDF) model of computation is widespread in design automation for communication and digital signal processing (DSP) systems. SDF scheduling has a large impact on the performance and memory requirements of implementations. One of the major problems in scheduling SDF graphs is that the existence of cycles in the targeted systems prevents or greatly restricts application of many useful optimization techniques that are available for acyclic SDF graphs. The loose interdependence algorithms framework (LIAF) has been developed to decompose cycles in SDF graphs into hierarchies of acyclic subgraphs whenever possible. However, LIAF does not specify any specific algorithm to break cycles, but rather it specifies the constraints that such an algorithm must satisfy. In this report, we present a low-complexity (linear-time) cycle-breaking algorithm for decomposing and breaking cycles in SDF graphs so that subsequent acyclic scheduling techniques can be easily applied. We also present a technique for computing buffer bounds on edges that are removed during the cycle-breaking process so that buffer sizes can be computed for such edges. We have implemented our cycle-breaking algorithm and buffer size computation technique in the state-of-art simulation-oriented scheduler, and our results demonstrate the effectiveness of these techniques.
    URI
    http://hdl.handle.net/1903/4328
    Collections
    • Technical Reports from UMIACS
    • Technical Reports of the Computer Science Department

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility