TY - GEN
T1 - Compiling dynamic data structures in python to enable the use of multi-core and many-core libraries
AU - Ren, Bin
AU - Agrawal, Gagan
PY - 2011
Y1 - 2011
N2 - Programmer productivity considerations are increasing the popularity of interpreted languages like Python. At the same time, for applications where performance is important, these languages clearly lack even on uniprocessors. In addition, the use of dynamic data structures in a language like Python makes it very hard to use emerging libraries for enabling the execution on multi-core and many-core architectures. This paper presents a framework for compiling Python to use multi-core and many-core libraries. The key component of our framework involves a suite of algorithms for replacing dynamic and/or nested data structures by arrays, while minimizing unnecessary data copying costs. This involves a novel use of an existing partial redundancy elimination algorithm, development of a new demand-driven interprocedural partial redundancy algorithm, a data flow formulation for determining that the contents of the data structure are of the same type, and a linearization algorithm. We have evaluated our framework using data mining and two linear algebra applications written in pure Python. The key observations were: 1) the code generated by our framework is only 10% to 20% slower compared to the hand-written C code that invokes the same libraries, 2) our optimizations turn out to be significant for improving the performance in most cases, and 3) we outperform interpreted Python and the C++ code generated by an existing tool by one to two orders of magnitude.
AB - Programmer productivity considerations are increasing the popularity of interpreted languages like Python. At the same time, for applications where performance is important, these languages clearly lack even on uniprocessors. In addition, the use of dynamic data structures in a language like Python makes it very hard to use emerging libraries for enabling the execution on multi-core and many-core architectures. This paper presents a framework for compiling Python to use multi-core and many-core libraries. The key component of our framework involves a suite of algorithms for replacing dynamic and/or nested data structures by arrays, while minimizing unnecessary data copying costs. This involves a novel use of an existing partial redundancy elimination algorithm, development of a new demand-driven interprocedural partial redundancy algorithm, a data flow formulation for determining that the contents of the data structure are of the same type, and a linearization algorithm. We have evaluated our framework using data mining and two linear algebra applications written in pure Python. The key observations were: 1) the code generated by our framework is only 10% to 20% slower compared to the hand-written C code that invokes the same libraries, 2) our optimizations turn out to be significant for improving the performance in most cases, and 3) we outperform interpreted Python and the C++ code generated by an existing tool by one to two orders of magnitude.
KW - Compilation for multi-core and many-core
KW - Python
KW - Redundancy elimination
UR - http://www.scopus.com/inward/record.url?scp=84856518340&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84856518340&partnerID=8YFLogxK
U2 - 10.1109/PACT.2011.13
DO - 10.1109/PACT.2011.13
M3 - Conference contribution
AN - SCOPUS:84856518340
SN - 9780769545660
T3 - Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT
SP - 68
EP - 77
BT - Proceedings - 2011 International Conference on Parallel Architectures and Compilation Techniques, PACT 2011
T2 - 20th International Conference on Parallel Architectures and Compilation Techniques, PACT 2011
Y2 - 10 October 2011 through 14 October 2011
ER -