Source: https://patents.google.com/patent/US8799871B2/en
Timestamp: 2018-11-17 18:37:33
Document Index: 722951718

Matched Legal Cases: ['art+1', 'art+1', 'art+1', 'art+1', 'art+1', 'Application No. 08713057']

US8799871B2 - Computation of elementwise expression in parallel - Google Patents
US8799871B2
US8799871B2 US11651119 US65111907A US8799871B2 US 8799871 B2 US8799871 B2 US 8799871B2 US 11651119 US11651119 US 11651119 US 65111907 A US65111907 A US 65111907A US 8799871 B2 US8799871 B2 US 8799871B2
US11651119
US20080178165A1 (en )
[a1a2]+b=[a1+b a2+b]
cos [a1 a2]=[ cos(a1)cos(a2)]
a=[a 11 a 12 ;a 21 a 22]
b=[b 11 b 12 ;b 21 b 22]
a([12],1)+b([12],2)=[a 11 +b 12 ;a 21 +b 22]
FIG. 1 depicts an environment 100 suitable for practicing an exemplary embodiment. Computing device 102 may include execution units 104, memory 106, keyboard 110, pointing device 112 and network interface 118. Execution units 104 may include hardware or software based logic to execute instructions on behalf of computing device 102. For example, in one implementation execution units 104 may include one or more processors, such as a microprocessor. In one implementation, the execution unit 104 may include single or multiple cores 105 for executing software stored in the memory 106, or other programs for controlling the computing device 102. In another implementation, execution units 104 may include hardware 116, such as a digital signal processor (DSP), a graphics processing unit (GPU), a field programmable gate array (FPGA), an application specific integrated circuit (ASIC), etc., on which at least a part of applications can be executed. In another implementation, execution units 104 may include virtual machine (VM) 117 for executing the code loaded in the memory 106. Multiple VMs 117 may be resident on a single execution unit 104.
Function Weight (Number of Chunks)
An exemplary embodiment is described below with reference to the expression, Z=sqrt(X)+Y, where X and Y are vectors of length n. The code generator 226 may evaluate the expression, Z=sqrt(X)+Y, with chunk_size. The chunk_size is the number of elements of each array in the expression that are assigned to the same chunk for execution of the elementwise expression. Exemplary code evaluating the expression, Z=sqrt(X)+Y, with chunk-size is provided as follows where T1 is a temporary vector of length, chunk_size.
for i = 1 to n / chunk_size
start = (i−1)*chunk_size + 1;
T1[1, 2 , ..., chunk_size] = sqrt(X[start, start+1, ...,
start+chunk_size−1]);
Z[start, start+1, ..., start+chunk_size−1] = T1[1, 2, ..., chunk_size] +
Y[start, start+1, ..., start+chunk_size−1];
The code generator 226 may generate code that can be executed in parallel on multiple execution units. To execute the expression in parallel, the computing environment 120 may determine the number of threads (num_threads) and the identification of each thread (thread_id). For example, values of thread_id may range from 0 to num_threads−1. The number of threads may be determined by a user or by the computing environment 120 based on the number of execution units on which the expression is executed in parallel.
for i = 1 to n / chunk_size / num_threads
start = (i−1)*chunk_size*thread_id + 1;
Tj[1, 2 , ..., chunk_size] = sqrt(X[start, start+1, ...,
Z[start, start+1, ..., start+chunk_size−1] = Tj[1, 2, ..., chunk_size] +
obtaining an expression including at least an array to which one of an elementwise operator or an elementwise function is applied;
starting execution of the expression in a computing environment;
weighting the elementwise operator or the elementwise function based on a performance profile,
the performance profile pre-computed by measuring a performance of a sample elementwise operator or function on specific hardware prior to the execution of the expression;
determining, during the execution of the expression, that a portion of the expression is to be executed in parallel,
the determining is based on the weighting and a number of elements in the array; and
continuing the execution of the expression in the computing environment by executing a subset of the elements of the array in parallel with one or more additional subsets of the elements of the array.
5. The method of claim 1, wherein the execution of the expression with the subsets of the elements of the array are is conducted in parallel by different threads.
execute portions of code in parallel, the code associated with the expression.
8. A non-transitory computer-readable medium holding instructions that, when executed at least one computing device, cause the at least one computing device to:
obtain an expression including at least an array to which one of an elementwise operator or elementwise function is applied;
start execution of the expression in a computing environment;
weight the elementwise operator or the elementwise function based on a performance profile,
determine, during the execution of the expression, that a portion of the expression is to be executed in parallel,
continue the execution of the expression in the computing environment by executing a subset of the elements of the array in parallel with one or more additional subsets of the elements of the array.
9. The medium of claim 8, wherein the computing environment is a dynamically typed computing environment.
10. The medium of claim 8, wherein the computing environment is an interpreted computing environment.
11. The medium of claim 10, wherein the interpreted computing environment uses just-in-time compilation.
12. The medium of claim 8, wherein the execution of the expression with the subsets of the elements of the array is conducted in parallel by different threads.
13. The medium of claim 8, further storing one or more instructions that, when executed by the at least one computing device, cause the at least one computing device to:
14. The medium of claim 13, further storing one or more instructions that, when executed by the at least one computing device, cause the at least one computing device to:
deploy the code to target hardware for execution.
obtaining an expression including at least an array to which an elementwise operator or an elementwise function is applied,
starting execution of the expression in a computing environment,
weighting the elementwise operator or elementwise function based on a performance profile,
the performance profile pre-computed by measuring a performance of a sample elementwise operator or function on specific hardware prior execution of the expression,
the determining is based on the weighting and a number of elements in the array, and
16. The system of claim 15, wherein the computing environment is a dynamically typed computing environment.
17. The system of claim 15, wherein the computing environment is an interpreted computing environment.
18. The system of claim 17, wherein the computing environment comprises a just-in-time compiler.
19. The system of claim 15, wherein the execution of the expression with the subsets of the elements of the array is conducted in parallel by different threads.
20. The system of claim 19, wherein the code is deployed to target hardware for execution.
21. The system of claim 15, wherein the processor is further configured to execute instructions for:
executing portions of code in parallel, the code associated with the expression.
US11651119 2007-01-08 2007-01-08 Computation of elementwise expression in parallel Active 2032-03-29 US8799871B2 (en)
US11651119 US8799871B2 (en) 2007-01-08 2007-01-08 Computation of elementwise expression in parallel
US11842087 US8769503B2 (en) 2007-01-08 2007-08-20 Computation of elementwise expression in parallel
PCT/US2008/000274 WO2008085977A3 (en) 2007-01-08 2008-01-08 Computation of elementwise expression in parallel
EP20080713057 EP2102746B1 (en) 2007-01-08 2008-01-08 Computation of elementwise expression in parallel
US11842087 Continuation US8769503B2 (en) 2007-01-08 2007-08-20 Computation of elementwise expression in parallel
US20080178165A1 true US20080178165A1 (en) 2008-07-24
US8799871B2 true US8799871B2 (en) 2014-08-05
US11651119 Active 2032-03-29 US8799871B2 (en) 2007-01-08 2007-01-08 Computation of elementwise expression in parallel
US11842087 Active 2031-06-19 US8769503B2 (en) 2007-01-08 2007-08-20 Computation of elementwise expression in parallel
WO (1) WO2008085977A3 (en)
CA2262277A1 (en) 1999-02-22 2000-08-22 Sudarsan Tandri A system and method for optimizing program execution in a computer system
US20040194077A1 (en) 2003-03-28 2004-09-30 Jayashankar Bharadwaj Methods and apparatus to collect profile information
US20040221270A1 (en) 1999-12-29 2004-11-04 Emmett Witchel Method for determining the degree to which changed code has been exercised
US20070234309A1 (en) 2006-03-31 2007-10-04 Microsoft Corporation Centralized code coverage data collection
US7908591B1 (en) 2006-07-17 2011-03-15 The Mathworks, Inc. Memory profiling
Clemens Grelck and Sven-Bodo Scholz; SAC-A Funtional Array Language for Efficient Multi-threaded Execution; 2006; retrieved online on May 1, 2014; pp. 383-427; Retrieved from the Internet . *
Clemens Grelck and Sven-Bodo Scholz; SAC—A Funtional Array Language for Efficient Multi-threaded Execution; 2006; retrieved online on May 1, 2014; pp. 383-427; Retrieved from the Internet <URL: http://www.sac-home.org/publications/GrelScholJPP06.pdf>. *
Diana Villa et al.; A Framework for Profiling Multiprocessor Memory Performance; IEEE; 2004; retrieved online on Jan. 23, 2014; pp. 1-9; Retrieved from the Internet: . *
Diana Villa et al.; A Framework for Profiling Multiprocessor Memory Performance; IEEE; 2004; retrieved online on Jan. 23, 2014; pp. 1-9; Retrieved from the Internet: <URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1316135>. *
European Office Action for Application No. 08713057.1, dated Oct. 21, 2009.
Gaurav, S. K.C. et al., "Countering Code-Injection Attacks With Instruction-Set Randomization," CCS '03, Proceedings of the 10th ACM Conference on Computer and Communication Security, pp. 272-280 (2003).
International Search Report for Application No. PCT/US2008/000274, dated Jul. 9, 2008.
Lin, Jin et al., "A Compiler Framework for Recovery Code Generation in General Speculative Optimizations," Proceedings of the 13th International Conference on Parallel Architecture and Compilation Techniques PACT'04), 12 pages (2004).
Markus Weinhardt et al.; Using Function Folding to Improve Sillicon Efficiency of Reconfigurable Arothmetic Arrays; 2004; IEEE; retrieved online on May 1, 2014; pp. 239-246. Retrieved from the Internet . *
Markus Weinhardt et al.; Using Function Folding to Improve Sillicon Efficiency of Reconfigurable Arothmetic Arrays; 2004; IEEE; retrieved online on May 1, 2014; pp. 239-246. Retrieved from the Internet <URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1393274>. *
Phitchaya Mangpo Phothilimthana et al.; Portable Performance on Hetergeneous Architectures; ACM; 2013; retrieved online on Jan. 23, 2014; pp. 431-443; Retrieved from the Internet: . *
Phitchaya Mangpo Phothilimthana et al.; Portable Performance on Hetergeneous Architectures; ACM; 2013; retrieved online on Jan. 23, 2014; pp. 431-443; Retrieved from the Internet: <URL: http://delivery.acm.org/10.1145/2460000/2451162/p431-phothilimthana.pdf?>. *
Rong-Guey Chang et al.; Support and optimization for parallel sparse programs with array intrinsics of Fortran 90; Published by Elsevier B.V.; 2004; retrieved online on Jan. 23, 2014; pp. 527-550; Retrieved from the Internet: . *
Rong-Guey Chang et al.; Support and optimization for parallel sparse programs with array intrinsics of Fortran 90; Published by Elsevier B.V.; 2004; retrieved online on Jan. 23, 2014; pp. 527-550; Retrieved from the Internet: <URL: http://www.iis.sinica.edu.tw/˜trc/public/publications/pc04/pc04ChangChuangLee.pdf>. *
Shende, Sameer et al., "Protable Profiling and Tracing for Parallel, Scientific Applications using C++," Proceedings of SPDT'98: ACM Sigmetrics Symposium on Parallel and Distributed Tools, pp. 134-145 (1998).
Tobias Lauer et al.; Exploring Graphics Processing Units as Parallel Coprocssors for Online Aggregation; 2010; ACM; retrieved online on May 1, 2014; pp. 77-84; Retrieved from the Internet . *
Tobias Lauer et al.; Exploring Graphics Processing Units as Parallel Coprocssors for Online Aggregation; 2010; ACM; retrieved online on May 1, 2014; pp. 77-84; Retrieved from the Internet <URL: http://delivery.acm.org/10.1145/1880000/1871958/p77-lauer.pdf?>. *
WO2008085977A3 (en) 2008-09-04 application
EP2102746A2 (en) 2009-09-23 application
EP2102746B1 (en) 2018-06-13 grant
WO2008085977A2 (en) 2008-07-17 application
US20080178165A1 (en) 2008-07-24 application
US20090144747A1 (en) 2009-06-04 application
US8769503B2 (en) 2014-07-01 grant
Harding et al. 2007 Fast genetic programming on GPUs
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:BAKER, BRETT;REEL/FRAME:019139/0574
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:BAKER, BRETT;REEL/FRAME:019144/0147