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

=?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.

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