Advanced search
1 file | 196.18 KB Add to list
Author
Organization
Abstract
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.

Downloads

  • icpp2004.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 196.18 KB

Citation

Please use this url to cite or link to this publication:

MLA
YU, YJ, and Erik D’Hollander. “Non-uniform Dependences Partitioned by Recurrence Chains.” 2004 INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING, PROCEEDINGS. 2004. 100–107. Print.
APA
YU, Y., & D’Hollander, E. (2004). Non-uniform dependences partitioned by recurrence chains. 2004 INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING, PROCEEDINGS (pp. 100–107). Presented at the 33rd International Conference on Parallel Processing .
Chicago author-date
YU, YJ, and Erik D’Hollander. 2004. “Non-uniform Dependences Partitioned by Recurrence Chains.” In 2004 INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING, PROCEEDINGS, 100–107.
Chicago author-date (all authors)
YU, YJ, and Erik D’Hollander. 2004. “Non-uniform Dependences Partitioned by Recurrence Chains.” In 2004 INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING, PROCEEDINGS, 100–107.
Vancouver
1.
YU Y, D’Hollander E. Non-uniform dependences partitioned by recurrence chains. 2004 INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING, PROCEEDINGS. 2004. p. 100–7.
IEEE
[1]
Y. YU and E. D’Hollander, “Non-uniform dependences partitioned by recurrence chains,” in 2004 INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING, PROCEEDINGS, Montreal, CANADA , 2004, pp. 100–107.
@inproceedings{411966,
  abstract     = {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.},
  author       = {YU, YJ and D'Hollander, Erik},
  booktitle    = {2004 INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING, PROCEEDINGS},
  issn         = {0190-3918},
  language     = {eng},
  location     = {Montreal, CANADA },
  pages        = {100--107},
  title        = {Non-uniform dependences partitioned by recurrence chains},
  url          = {http://dx.doi.org/10.1109/ICPP.2004.1327909},
  year         = {2004},
}

Altmetric
View in Altmetric
Web of Science
Times cited: