COMPUTATION OF ELEMENTWISE EXPRESSION IN PARALLEL

• US 20090144747A1
• Filed: 08/20/2007
• Published: 06/04/2009
• Est. Priority Date: 01/08/2007
• Status: Active Grant

• Current Assignee: The MathWorks, Inc.
• Original Assignee: The MathWorks, Inc.
• Inventors: BAKER, BRETT
• Granted Patent: US 8,769,503 B2
• Time in Patent Office: Days
• US Class Current: 718/107
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions

Abstract

An exemplary embodiment provides methods, systems and mediums for executing arithmetic expressions that represent elementwise operations. An exemplary embodiment provides a computing environment in which elementwise expressions may be executed in parallel by multiple execution units. In an exemplary embodiment, multiple execution units may reside on a network.

Claims

1. A computer-implemented method for accelerating an execution of an expression in a computing environment, the method comprising:

obtaining an expression including at least an array to which one of an elementwise operator and an elementwise function is applied;

weighting the elementwise operator or the elementwise function to determine whether the expression is to be executed in parallel; and

generating code for computing the expression in parallel, wherein the expression is computed with a subset of the elements of the array in parallel with one or more additional subsets of the elements of the array.

2. The method of claim 1, wherein the computing environment is a dynamically typed computing environment.

3. The method of claim 1, wherein the computing environment is an interpreted computing environment.

4. The method of claim 3, wherein the interpreted computing environment uses just-in-time compilation.

5. The method of claim 1, further comprising:

weighting the function based on performance profiles of the function.

6. The method of claim 5, wherein the performance profiles are generated dynamically during the execution of the expression.

7. The method of claim 5, wherein the performance profiles are generated prior to the execution of the expression.

8. The method of claim 1, further comprising:

determining whether the expression is to be executed in parallel based on a weight of the operator or function in the expression and a number of elements in the array.

9. The method of claim 1, wherein an execution of the expression with the subsets of the elements of the array are conducted in parallel by different threads.

10. The method of claim 1, further comprising:

executing portions of the code in parallel.

11. The method of claim 9, further comprising:

deploying the code to target hardware for execution.

12. A medium holding instructions executable in a computing device for accelerating an execution of an expression in a computing environment, the medium comprising:

instructions for obtaining an expression including at least an array to which an elementwise operator or elementwise function is applied;

instructions for weighting the elementwise operator or the elementwise function to determine whether the expression is to be executed in parallel and instructions for generating code for executing the expression in parallel, wherein the expression is computed with a subset of the elements of the array in parallel with one or more additional subsets of the elements of the array.

13. The medium of claim 12, wherein the computing environment is a dynamically typed computing environment.

14. The medium of claim 12, wherein the computing environment is an interpreted computing environment.

15. The medium of claim 14, wherein the interpreted computing environment uses just-in-time compilation.

16. The medium of claim 12, further comprising:

instructions for weighting the function based on performance profiles of the function.

17. The medium of claim 16, wherein the performance profiles are generated dynamically during the execution of the expression.

18. The medium of claim 16, wherein the performance profiles are generated prior to the execution of the expression.

19. The medium of claim 12, further comprising:

instructions for determining whether the expression is to be executed in parallel based on a weight of the operator or function in the expression and a number of elements in the array.

20. The medium of claim 12, wherein an execution of the expression with the subsets of the elements of the array are conducted in parallel by different threads.

21. The medium of claim 12, further comprising:

instructions for executing portions of the code in parallel.

22. The medium of claim 20, further comprising:

instructions for deploying the code to target hardware for execution.

23. A system for accelerating an execution of an expression in a computing environment, the method comprising:

an accelerator for obtaining an expression including at least an array to which an elementwise operator or elementwise function is applied;

an analyzer for weighting the elementwise operator or elementwise function to determine whether the expression is to be executed in parallel elementwise operator or elementwise function; and

code generator for generating code to compute the expression in parallel, wherein the expression is computed with a subset of the elements of the array in parallel with one or more additional subsets of the elements of the array.

24. The system of claim 23, wherein the computing environment is a dynamically typed computing environment.

25. The system of claim 23, wherein the computing environment is an interpreted computing environment.

26. The system of claim 25, wherein the computing environment comprises just-in-time compiler.

27. The system of claim 23, wherein the analyzer weights the function based on performance profiles of the function.

28. The system of claim 27, wherein the performance profiles are generated dynamically during the execution of the expression.

29. The system of claim 27, wherein the performance profiles are generated prior to the execution of the expression.

30. The system of claim 23, wherein the analyzer determines whether the expression is to be executed in parallel based on a weight of the operator or function in the expression and a number of elements in the array.

31. The system of claim 23, wherein an execution of the expression with the subsets of the elements of the array are conducted in parallel by different threads.

32. The system of claim 23, further comprising:

execution units for executing portions of the code in parallel.

33. The system of claim 31, wherein the code is deployed to target hardware for execution.

34. A computer-implemented method for accelerating an execution of an expression in a computing environment, the method comprising:

determining a weight of one of an operator and a function in an expression, wherein the expression includes at least an array to which the one of an elementwise operator and elementwise function is applied; and

computing the expression in parallel based on the weight.

35. The method of claim 34, further comprising:

determining the weight based on performance profiles of the operator and the function.

36. The method of claim 35, wherein the performance profiles are generated dynamically during execution of the expression.

37. The method of claim 35, wherein the performance profiles are generated prior to execution of the expression.

38. The method of claim 34, further comprising:

determining whether the expression is to be executed in parallel based on the weight and a number of elements in the array.

39. A medium holding instructions executable in a computing device for accelerating an execution of an expression in a computing environment, the medium comprising:

instructions for determining a weight of one of an operator and a function in an expression, wherein the expression includes at least an array to which the one of an elementwise operator and elementwise function is applied; and

instructions for computing the expression in parallel based on the weight.

40. A computer-readable medium comprising computer-executable instructions for performing a method for accelerating execution of an expression in a computing environment that uses just-in-time compilation, the medium comprising:

instructions for obtaining an expression including at least an array to which one of an elementwise operator and an elementwise function is applied; and

instructions for generating code for computing the expression in parallel, wherein the expression is computed with a subset of the elements of the array in parallel with one or more additional subsets of the elements of the array.