Loop fission and fusion

  (Redirected from Loop fission)

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][2] 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.[3][2] 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.

FusionEdit

Example in CEdit

  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 alsoEdit

ReferencesEdit

  1. ^ Y.N. Srikant; Priti Shankar (3 October 2018). The Compiler Design Handbook: Optimizations and Machine Code Generation, Second Edition. CRC Press. ISBN 978-1-4200-4383-9.
  2. ^ a b Kennedy, Ken & Allen, Randy. (2001). Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann. ISBN 1-55860-286-0.
  3. ^ Steven Muchnick; Muchnick and Associates (15 August 1997). Advanced Compiler Design Implementation. Morgan Kaufmann. ISBN 978-1-55860-320-2. loop fusion.