Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • ログイン
    アイテム表示 
    •   ホーム
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports from UMIACS
    • アイテム表示
    •   ホーム
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports from UMIACS
    • アイテム表示
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Lazy Array Data-Flow Dependence Analysis

    Thumbnail
    閲覧/開く
    CS-TR-3110.ps (330.8Kb)
    No. of downloads: 198

    Auto-generated copy of CS-TR-3110.ps (365.1Kb)
    No. of downloads: 684

    日付
    1998-10-15
    著者
    Maslov, Vadim
    Metadata
    アイテムの詳細レコードを表示する
    抄録
    Automatic parallelization of real FORTRAN programs does not live up to users expectations yet, and dependence analysis algorithms which either produce too many false dependences or are too slow contribute significantly to this. In this paper we introduce data-flow dependence analysis algorithm which exactly computes value-based dependence relations for program fragments in which all subscripts, loop bounds and IF conditions are affine. Our algorithm also computes good affine approximations of dependence relations for non-affine program fragments. Actually, we do not know about any other algorithm which can compute better approximations. And our algorithm is efficient too, because it is lazy. When searching for write statements that supply values used by a given read statement, it starts with statements which are lexicographically close to the read statement in iteration space. Then if some of the read statement instances are not ``satisfied'' with these close writes, the algorithm broadens its search scope by looking into more distant writes. The search scope keeps broadening until all read instances are satisfied or no write candidates are left. We timed our algorithm on several benchmark programs and the timing results suggest that our algorithm is fast enough to be used in commercial compilers --- it usually takes 5 to 15 percent of f77 -O2 compilation time to analyze a program. Most programs in the 100-line range take less than 1 second to analyze on a SUN SparcStation IPX. (Also cross-referenced as UMIACS-TR-93-69)
    URI
    http://hdl.handle.net/1903/590
    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
     

     

    ブラウズ

    リポジトリ全体コミュニティ/コレクション公開日著者タイトル主題このコレクション公開日著者タイトル主題

    登録利用者

    ログイン登録
    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