Loop fission and fusion

From Wikipedia, the free encyclopedia
  (Redirected from Loop fusion)
Jump to navigation Jump to search

In computer science, loop fission (or loop distribution) is a compiler optimization in which a loop is broken into multiple loops over the same index range with each taking only a part of the original loop's body.[1] The goal is to break down a large loop body into smaller ones to achieve better utilization of locality of reference. This optimization is most efficient in multi-core processors that can split a task into multiple tasks for each processor.

Conversely, loop fusion (or loop jamming) is a compiler optimization and loop transformation which replaces multiple loops with a single one.[1] It is possible when two loops iterate over the same range and do not reference each other's data. Loop fusion does not always improve run-time speed. On some architectures, two loops may actually perform better than one loop because, for example, there is increased data locality within each loop.

Fission

Example in C

 int i, a[100], b[100];
 for (i = 0; i < 100; i++) {
   a[i] = 1; 
   b[i] = 2;
 }

is equivalent to

 int i, a[100], b[100];
 for (i = 0; i < 100; i++) {
   a[i] = 1;                     
 }
 for (i = 0; i < 100; i++) {
   b[i] = 2;
 }

Fusion

Example in C

  int i, a[100], b[100];
  for (i = 0; i < 100; i++)
    a[i] = 1;                     
  for (i = 0; i < 100; i++)
    b[i] = 2;

is equivalent to:

  int i, a[100], b[100];
  for (i = 0; i < 100; i++)
  {
    a[i] = 1; 
    b[i] = 2;
  }

See also

References

  1. ^ a b Kennedy, Ken & Allen, Randy. (2001). Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann. ISBN 1-55860-286-0. 
  • Loop fission
Retrieved from "https://en.wikipedia.org/w/index.php?title=Loop_fission_and_fusion&oldid=823604465"
This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/Loop_fusion
This page is based on the copyrighted Wikipedia article "Loop fission and fusion"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA