Non-uniform distance loop dependences are a known obstacle to find parallel iterations. To find the outermost loop parallelism in these "irregular" loops, a novel method is presented based on recurrence chains. The scheme organizes non-uniformly dependent iterations into lexicographically ordered monotonic chains. While the initial and final iterations of monotonic chains form two parallel sets, the remaining iterations form an intermediate set that can be partitioned further When there is only one pair of coupled array references, the non-uniform dependences are represented by a single recurrence equation. In that case, the chains in the intermediate set do not bifurcate and each can be executed as a WHILE loop. The independent and the initial iterations of monotonic dependence chains constitute the outermost parallelism. The proposed approach compares favorably with other treatments of non-uniform dependences in the literature. When there are multiple recurrence equations, a dataflow parallel execution can be scheduled using the technique to find maximum loop parallelism.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Non-uniform dependences partitioned by recurrence chains


    Beteiligte:
    YU, YJ (Autor:in) / D'Hollander, Erik (Autor:in)

    Erscheinungsdatum :

    2004-01-01


    Anmerkungen:

    2004 INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING, PROCEEDINGS ; ISSN: 0190-3918



    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    629



    Partitioned refrigerator carriage

    SHEN ZHOU / LI DANQI | Europäisches Patentamt | 2022

    Freier Zugriff

    Partitioned network routing

    WU JOHN / RAMANUJAN RANGA S | Europäisches Patentamt | 2020

    Freier Zugriff

    Partitioned control cabinet

    LIU DEAN | Europäisches Patentamt | 2024

    Freier Zugriff

    Partitioned Fractal Interpolation

    Kok, Chi‐Wah / Tam, Wing‐Shan | Wiley | 2019


    Safety-Critical Partitioned Software Architecture: A Partitioned Software Architecture for Robotic

    Horvath, Greg / Chung, Seung H. / Cilloniz-Bicchi, Ferner | NTRS | 2011