SPIRAL
  • Introduction
  • Getting Started
  • Examples
  • GAP3 Language
  • SPIRAL Objects and Data Types
  • SPIRAL Infrastructure
    • Breakdown Rules
    • Search
      • Dynamic Programming
        • Standard Dynamic Programming
        • Hashing and Custom Measure Functions
    • Rewriting
    • Compiler
  • Special Hardware
  • Debugger
  • Profiler
  • Getting Help with SPIRAL
  • Contributing to SPIRAL
  • Further Reading
SPIRAL
  • SPIRAL Infrastructure
  • Search
  • View page source

Search

Dynamic Programming

Standard Dynamic Programming

n := 15; k := -1;           # transform parameters
opts := SpiralDefaults;     # default options
opts.globalUnrolling := 16; # set smaller unrolling
t := DFT(n, k);             # transform
best := DP(t, rec(), opts); # run search
rt := best[1].ruletree;     # get best rule tree

Hashing and Custom Measure Functions

dpopts := rec(verbosity := 5, hashTable := HashTableDP());
dpopts.measureFunction := (rt, opts) ->
        let(c:= CodeRuleTree(rt, opts),    # generate code
                Length(Filtered(           # count flops in code
                        Collect(c, @(1,[add, sub, mul, neg])), i->i.t=TReal)));
best := DP(t, dpopts, opts);    # run search with flop minimization
#look what’s in the hash table
HashLookup(dpopts.hashTable, DFT(5, 1))[1].ruletree;
HashLookup(dpopts.hashTable, DFT(5,-1));

# now time the tree found through flop minimization
rt1 := HashLookup(dpopts.hashTable, DFT(15, 1))[1].ruletree;
DPMeasureRuleTree(rt1, opts);
Previous Next

© Copyright 2021, SPIRAL Team.

Built with Sphinx using a theme provided by Read the Docs.