tag:blogger.com,1999:blog-5822805028291837738.post7276942816563988669..comments2020-05-29T23:29:35.466-04:00Comments on Various Consequences: NALPAL: Not A Livermore Physics Applications LanguageJoshua Stultshttp://www.blogger.com/profile/03506970399027046387noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-5822805028291837738.post-931688637154934352012-08-05T12:54:34.454-04:002012-08-05T12:54:34.454-04:00Fixed link: A Fast Fourier Transform CompilerFixed link: <a href="http://www1.cs.columbia.edu/~aho/cs6998/lectures/11-10-25_Le_FFTW.pdf" rel="nofollow">A Fast Fourier Transform Compiler</a>Joshua Stultshttps://www.blogger.com/profile/03506970399027046387noreply@blogger.comtag:blogger.com,1999:blog-5822805028291837738.post-87239527423493631622012-08-05T12:52:03.662-04:002012-08-05T12:52:03.662-04:00FFTW
"Simplification":
- Simplifier tr...FFTW <br />"Simplification":<br /><i><br />- Simplifier traverses dag bottom-up and applies series of "improvements" at every node <br />- Common well-known optimizations [<a href="http://www.google.com/search?q=aho+Compilers%2C+principles%2C+techniques%2C+and+tools" rel="nofollow">Aho86</a>]<br /> - <b>Algebraic Transformations</b>: constant folding and simplify multiplication by 0,1,-1 and addition by 0<br /> - <b>Common-Subexpression Elimination</b> (CSE): simplifier implemented in monadic style [<a href="http://www.google.com/search?q=wadler+How+to+declare+an+imperative" rel="nofollow">Wad97</a>] in which <b>monad</b> performs CSE. <br />- DFT specific <br /> - Eliminate negative constants Constants generally appear as pairs in a DFT dag ; C compiler would store values in program text and then load both constants into a register at runtime. Thus, making all constants positive reduces load by factor of two, speeding up generated codelets by 10-15%<br />- Network transposition. Based on fact that network is a dag that computes a linear function [<a href="https://www.google.com/search?q=Crochiere+Analysis+of+linear+digital+networks" rel="nofollow">Cro75</a>]<br /></i><br /><br />"Some Conclusions to Draw": <br /><i><br /><b>Optimal Performance:</b> main goal of project achieved since up-to-date benchmarks show FFTW's performance still ahead of other competing FFTs<br /><b>Correctness:</b> In words of authoer: "surprisingly easy." Since DFT algorithms in <b>genfft</b> were encoded using a straight-forward, high-level language (OCaml), <b>simplification</b> phase of the compiler transforms algorithms into optimized code via application of simple algebraic rules which are easy to verify<br /><b>Rapid Turnaround:</b> Just 15 minutes (back in 1999) to regenerate FFTW from scratch<br /><b>Domain-specific code enhancements:</b> Topological sort in <b>scheduling</b> phase is effective only for DFT <b>dags</b> [directed acyclic graphs] and perform poorly for other computations while <b>simplification</b> performs certain improvements which rely on DFT being a <b>linear</b> transformation<br /></i><br /><a href="www1.cs.columbia.edu/~aho/cs6998/.../11-10-25_Le_FFTW.pdf" rel="nofollow">A Fast Fourier Transform Compiler</a>Joshua Stultshttps://www.blogger.com/profile/03506970399027046387noreply@blogger.comtag:blogger.com,1999:blog-5822805028291837738.post-46407881362854780712011-05-28T12:59:56.182-04:002011-05-28T12:59:56.182-04:00I got a CD full of ALPAL stuff yesterday in the ma...<a href="http://www.math.utexas.edu/pipermail/maxima/2011/025226.html" rel="nofollow">I got a CD full of ALPAL stuff</a> yesterday in the mail from my FOIA request (thanks Jeff!). <a href="https://sites.google.com/site/variousconsequences/alpal_docs/doc_282.pdf?attredirects=0&d=1" rel="nofollow">doc_282.pdf</a> has a pretty good lit review of related approaches to these types of tools (which was sort of what I was attempting with this post). You can see everything else <a href="https://sites.google.com/site/variousconsequences/alpal_docs" rel="nofollow">here</a> (lots of code), suggest you read the doc_xxx.pdf's first since those describe the purpose and design.Joshua Stultshttps://www.blogger.com/profile/03506970399027046387noreply@blogger.comtag:blogger.com,1999:blog-5822805028291837738.post-47358750283133554362011-03-08T10:58:07.360-05:002011-03-08T10:58:07.360-05:00Recent activity on the list about generating C fro...Recent activity on the list about generating C from Maxima:<br /> - <a href="http://www.math.utexas.edu/pipermail/maxima/2011/024011.html" rel="nofollow">grinding, etc.</a><br /> - <a href="http://www.math.utexas.edu/pipermail/maxima/2011/024035.html" rel="nofollow">http://www.math.utexas.edu/pipermail/maxima/2011/024035.html</a><br /> - <a href="http://www.math.utexas.edu/pipermail/maxima/2011/024404.html" rel="nofollow">Outputting C code from maxima</a><br /> - <a href="http://www.math.utexas.edu/pipermail/maxima/2011/024503.html" rel="nofollow">grinding to C, colnew</a>Joshua Stultshttps://www.blogger.com/profile/03506970399027046387noreply@blogger.comtag:blogger.com,1999:blog-5822805028291837738.post-36978479086858716722010-11-16T16:41:24.160-05:002010-11-16T16:41:24.160-05:00Informative comment on the Maxima list about diffe...<a href="http://www.math.utexas.edu/pipermail/maxima/2010/023180.html" rel="nofollow">Informative comment</a> on the Maxima list about differential operators.Joshua Stultshttps://www.blogger.com/profile/03506970399027046387noreply@blogger.comtag:blogger.com,1999:blog-5822805028291837738.post-77518076358845458012010-10-27T12:15:42.171-04:002010-10-27T12:15:42.171-04:00I'm addicted to FOSS; thanks for the editorial...I'm addicted to FOSS; thanks for the editorial review ; )<br /><br />All typos are shallow with enough eye-balls...Joshua Stultshttps://www.blogger.com/profile/03506970399027046387noreply@blogger.comtag:blogger.com,1999:blog-5822805028291837738.post-86542787630161844002010-10-27T12:09:12.218-04:002010-10-27T12:09:12.218-04:00Hi Josh,
A couple of malformed and broken links.
R...Hi Josh,<br />A couple of malformed and broken links.<br />Reference [10] goes nowhere... and slowly. The inline link seems to hit a blogspot bug as well.<br /><br />s/Touring/Turing/<br /><br />Joy pointed me at the blog and I'll work my way through it here shortly. Glad to see the FOSS advocacy.shallow monkeyhttps://www.blogger.com/profile/13034168320000048613noreply@blogger.comtag:blogger.com,1999:blog-5822805028291837738.post-6291417220831283592010-10-26T20:08:26.234-04:002010-10-26T20:08:26.234-04:00Jeff, thanks for your comment. You are right.
Ac...Jeff, thanks for your comment. You are right.<br /><br />Actually, I'm struggling a bit with that right now. The grid transform example in the post doesn't include second and cross derivative terms; with those included the brute force approach involves symbolically inverting a 9x9, which is still a pain even on modern hardware.Joshua Stultshttps://www.blogger.com/profile/03506970399027046387noreply@blogger.comtag:blogger.com,1999:blog-5822805028291837738.post-89529614546885193722010-10-26T19:59:44.486-04:002010-10-26T19:59:44.486-04:00As a former contributor to ALPAL, I'd like to ...As a former contributor to ALPAL, I'd like to point out that massive expressions are not just a problem at the code generation stage. They generally lead to massive amounts of code that get executed, and that takes time. To this day, speed is critical in scientific computing.<br /><br />Anyway, there's a lot to be said for the toolbox approach, if well designed.Jeffrey F. Painternoreply@blogger.comtag:blogger.com,1999:blog-5822805028291837738.post-88873782639519428762010-10-22T22:19:34.093-04:002010-10-22T22:19:34.093-04:00Hi Daniel,
Thanks for the comment and the link; t...Hi Daniel,<br /><br />Thanks for the comment and the link; that's pretty neat. <br /><br />I've never actually solved a PDE in Maxima. I've just used it to generate Fortran and the forcing functions to verify implementations. <br /><br />One of the reasons I was initially interested in ALPAL isn't so much that I want finite difference solutions (that's kind of old-fashioned right?), but that a few iterations of SSOR based on low order finite differences is a useful preconditioner. <br /><br />I like your site. Congrats on the new baby; real life has this funny way of interfering with the blogging...Joshua Stultshttps://www.blogger.com/profile/03506970399027046387noreply@blogger.comtag:blogger.com,1999:blog-5822805028291837738.post-66148661233811088622010-10-22T13:03:01.762-04:002010-10-22T13:03:01.762-04:00In almost all cases that I've used Maxima to s...In almost all cases that I've used Maxima to solve PDEs I've decided to use some kind of series approximation for the function rather than finite difference or finite element methods. <br /><br />In particular, for regular domains, fourier/sine/cosine series or for irregular domains radial basis functions. Also I usually wind up with nonlinear PDEs so I solve them by iterative methods at collocation points.<br /><br />For an example of how I did this for a laplace equation problem (steady state heat conduction) on an irregular grid you can see my blog post:<br /><br />http://models.street-artists.org/?p=398Daniel Lakelandhttp://models.street-artists.org/noreply@blogger.comtag:blogger.com,1999:blog-5822805028291837738.post-31182490192629092162010-10-20T13:49:29.211-04:002010-10-20T13:49:29.211-04:00[15] Akers, R., Kant, E., Randall, C., Steinberg, ...[15] Akers, R., Kant, E., Randall, C., Steinberg, S., and Young, R., “<a href="http://scholar.google.com/scholar?cluster=7572632894099458625&hl=en&as_sdt=100000000000" rel="nofollow">SciNapse: a problem-solving environment for partial differential equations</a>,” Computational Science & Engineering, IEEE, Vol. 4, No. 3, Jul-Sep 1997, pp. 32 – 42.Joshua Stultshttps://www.blogger.com/profile/03506970399027046387noreply@blogger.com