Compiler optimization for complex exponential calculations

Patent metadata

Field	Value
Publication number	US-2016110171-A1
Application number	US-201314129438-A
Country	US
Kind code	A1
Filing date	Jun 14, 2013
Priority date	Jun 14, 2013
Publication date	Apr 21, 2016
Grant date	—

Abstract

Technologies for optimizing complex exponential calculations include a computing device with optimizing compiler. The compiler parses source code, optimizes the parsed representation of the source code, and generates output code. During optimization, the compiler identifies a loop in the source code including a call to the exponential function having an argument that is a loop-invariant complex number multiplied by the loop index variable. The compiler tiles the loop to generate a pair of nested loops. The compiler generates code to pre-compute the exponential function and store the resulting values in a pair of coefficient arrays. The size of each coefficient array may be equal to the square root of the number of loop iterations. The compiler applies rewrite rules to replace the exponential function call with a multiplicative expression of one element from each of the coefficient arrays. Other embodiments are described and claimed.

First claim

1 - 25 . (canceled)

26 . A computing device to optimize a source program, the computing device comprising:
a processor; source code having a code segment including a loop, the loop having a first number of iterations and including an exponential function call having an argument including a loop-invariant complex number multiplied by a loop index; and a memory having a compiler stored therein, wherein the compiler (i) a loop detect module to detect the code segment, (ii) a loop optimize module to optimize the code segment in response to detection of the code segment, and (iii) a code generator module to generate output code as a function of the optimized code segment, wherein the loop optimize module to: tile the loop to generate an outer loop having a second number of iterations and a nested inner loop having a third number of iterations; generate code to calculate a first coefficient array having a number of elements equal to the third number of iterations, wherein each element of the first coefficient array equals an exponential function of the loop-invariant complex number multiplied by a first coefficient array index; generate code to calculate a second coefficient array having a number of elements equal to the second number of iterations, wherein each element of the second coefficient array equals an exponential function of the loop-invariant complex number multiplied by the third number of iterations and a second coefficient array index; and replace the exponential function call with a multiplicative expression of an element of the first coefficient array at an inner loop index multiplied by an element of the second coefficient array at an outer loop index.

27 . The computing device of claim 26 , wherein the loop optimize module is further to generate a conditional statement to determine whether the first number of iterations exceeds a minimum loop size, the conditional statement to execute the optimized code segment in response to determining the first number of iterations exceeds the minimum loop size.

28 . The computing device of claim 27 , wherein to determine whether the first number of iterations exceeds the minimum loop size comprises to determine whether an iteration space of the loop exceeds a cache size of the computing device.

29 . The computing device of claim 26 , the loop optimize module is further to:
determine whether the first number of iterations exceeds a minimum loop size; wherein the loop optimize module is to optimize the code segment in response to a determination that the first number of iterations exceeds the minimum loop size.

30 . The computing device of claim 29 , wherein to determine whether the first number of iterations exceeds the minimum loop size comprises to determine whether an iteration space of the loop exceeds a cache size of a target computing device.

31 . The computing device of claim 26 , wherein the loop optimize module is further to:
determine one of: whether the second number of iterations exceeds a minimum loop size or the third number of iterations exceeds the minimum loop size; and optimize one of: the outer loop in response to a determination that the second number of iterations exceeds the minimum loop size, or the inner loop in response to a determination that the third number of iterations exceeds the minimum loop size.

32 . The computing device of claim 31 , wherein to determine whether the second number of iterations or the third number of iterations exceeds the minimum loop size comprises to determine whether an iteration space of the outer loop or an iteration space of the inner loop exceeds a cache size of a target computing device.

33 . The computing device of claim 26 , wherein the loop optimize module is further to optimize the multiplicative expression.

34 . The computing device of claim 33 , wherein to optimize the multiplicative expression comprises one of to: vectorize the multiplicative expression or parallelize the multiplicative expression.

35 . A method for optimizing a source program on a computing device comprising a processor and a memory, the method comprising:
detecting, by a compiler of the computing device, a code segment of the source program having a loop, the loop having a first number of iterations and including an exponential function call having an argument including a loop-invariant complex number multiplied by a loop index; and optimizing, by the compiler, the code segment to generate an optimized code segment in response to detecting the code segment, wherein optimizing the code segment comprises: (i) tiling the loop to generate an outer loop having a second number of iterations and a nested inner loop having a third number of iterations; (ii) generating code to calculate the first coefficient array having a number of elements equal to the third number of iterations, wherein each element of the first coefficient array equals the exponential function of the loop-invariant complex number multiplied by the first coefficient array index; (iii) generating code to calculate the second coefficient array having a number of elements equal to the second number of iterations, wherein each element of the second coefficient array equals the exponential function of the loop-invariant complex number multiplied by the third number of iterations and the second coefficient array index; (iv) replacing the exponential function call with a multiplicative expression of an element of the first coefficient array at an inner loop index multiplied by an element of the second coefficient array at an outer loop index.

36 . (canceled)

37 . The method of claim 35 , wherein optimizing the code segment further comprises:
generating a conditional statement to determine whether the first number of iterations exceeds a minimum loop size, the conditional statement to execute the optimized code segment in response to determining the first number of iterations exceeds the minimum loop size.

38 . The method of claim 35 , further comprising:
determining, by the compiler, whether the first number of iterations exceeds a minimum loop size; wherein optimizing the code segment comprises optimizing the code segment in response to determining the first number of iterations exceeds the minimum loop size.

39 . The method of claim 35 , further comprising:
determining, by the compiler, one of: whether the second number of iterations exceeds a minimum loop size or the third number of iterations exceeds the minimum loop size; and optimizing, by the compiler, one of: the outer loop in response to determining the second number of iterations exceeds the minimum loop size, or the inner loop in response to determining the third number of iterations exceeds the minimum loop size.

40 . The method of claim 35 , wherein optimizing the code segment further comprises optimizing the multiplicative expression.

41 . One or more non-transitory, machine readable storage media comprising a plurality of instructions that in response to being executed cause a computing device to:
detect, by a compiler, a code segment of a source program having a loop, the loop having a first number of iterations and including an exponential function call having an argument including a loop-invariant complex number multiplied by a loop index; and optimize, by the compiler, the code segment to generate an optimized code segment in response to detecting the code segment, wherein to optimize the code segment comprises to: (i) tile the loop to generate an outer loop having a second number of iterations and a nested inner loop having a thir

Assignees

• Intel Corp

Inventors

• Bikshandi Ganesh
• Kim Daehyun

Classifications

• G06F7/556

  Logarithmic or exponential functions · CPC title

• G06F8/443 Primary

  Optimisation · CPC title

• G06F7/4806

  Computations with complex numbers · CPC title

• G06F8/4434

  Reducing the memory space required by the program code · CPC title

• G06F8/452

  Loops · CPC title