Re: Automatic "code-pattern" recognition, in DSP codes

jle@ural.owlnet.rice.edu (Jason Lee Eckhardt)
11 Jul 2005 06:57:18 -0400

          From comp.compilers

Related articles
Automatic "code-pattern" recognition, in DSP codes Miguel.CasasSanchez@ucd.ie (=?ISO-8859-15?Q?Miguel_Cas=E1s-S=E1nchez?=) (2005-07-05)
Re: Automatic "code-pattern" recognition, in DSP codes jle@ural.owlnet.rice.edu (2005-07-11)
Re: Automatic "code-pattern" recognition, in DSP codes bsheff2@yahoo.com (Bob Sheff) (2005-07-11)
Re: Automatic "code-pattern" recognition, in DSP codes codeworker@free.fr (=?iso-8859-1?q?C=E9dric_LEMAIRE?=) (2005-07-11)
Re: Automatic "code-pattern" recognition, in DSP codes darius@raincode.com (Darius Blasband) (2005-07-11)
Re: Automatic "code-pattern" recognition, in DSP codes drizzle76@gmail.com (drizzle) (2005-07-11)
Re: Automatic "code-pattern" recognition, in DSP codes oliver@first.in-berlin.de (Oliver Bandel) (2005-07-11)
Re: Automatic "code-pattern" recognition, in DSP codes pohjalai@cc.helsinki.fi (A Pietu Pohjalainen) (2005-07-11)
| List of all articles for this month |

From: jle@ural.owlnet.rice.edu (Jason Lee Eckhardt)
Newsgroups: comp.compilers
Date: 11 Jul 2005 06:57:18 -0400
Organization: Rice University, Houston, TX
References: 05-07-024
Keywords: analysis, DSP

=?ISO-8859-15?Q?Miguel_Cas=E1s-S=E1nchez?= <Miguel.CasasSanchez@ucd.ie> wrote:
>I am researching in compilers and source to source code transformations,
>for Digital Signal Processors, in particular with the Texas Instruments
>Code Composer Studio 2.2 for the 55x family.
>
>I was wondering if somebody has ever heard about something like
>"automatic typical DSP-like kernel recognition", for example, as the
>compiler reads the program and sets up the data and control graphs,
>recognise that
>
>for(i=0, acc = 0; i < N; i++) {
> acc = h[n] * X[N-n];
>}
>
>can be a FIR filter, that may be substituted as a whole by a fir()
>library function call, most optimised.
>
>Can be also understood as pattern-search in the code control/data graphs?


    Some commercial parallelizing compilers and source-to-source
    systems recognize certain simple scientific kernels or recurrences
    ("idiom recognition") and either replace them by optimized library
    calls or utilize that knowledge to better optimize the code. A few
    systems that have done this in the past are the Cray and Convex compilers,
    the VAST source-to-source system, etc.


    A somewhat more ambitious approach is described in the book:
      R. Metzger and Z. Wen, "Automatic Algorithm Recognition and Replacement:
      A New Approach to Program Optimization", MIT press.


    In essence, they canonicalize the input program, and try to match
    kernels in the program to a database of known computational kernels,
    which may then be replaced by calls to optimized library routines.
    The problem is difficult, and my description hardly does justice,
    but the book gives an idea of the issues involved and is worth
    a read.


    Finally, there are many papers on the topic, often related to
    parallelizing compilers for scientific code. Searching with
    keywords such as "idiom recognition", "parallelizing compilers",
    "VAST", "pattern matching", etc. will turn up plenty.





Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.