[LLVMdev] Live range splitting with Ising models

Jakob Stoklund Olesen stoklund at 2pi.dk
Thu Aug 8 10:45:53 PDT 2013


On Aug 8, 2013, at 10:46 AM, David Tweed <david.tweed at arm.com> wrote:

> | I believe that 2-state Ising models can be reduced to max-flow/min-cut (eg, Finding ground states in random-field Ising ferromagnets by F Barahona)
> 
> I hadn't been following D-Wave; upon looking I see that they're using problem reductions to Ising models which aren't ferromagnet models (sign is different), and those problems are known to be NP-hard. Haven't thought about what kind of models LLVM is using.

I hadn’t noticed that either. Anyway, LLVM’s models are ferromagnetic, the interactions are sums of expected basic block frequencies which are always non-negative numbers.

Thanks,
/jakob





More information about the llvm-dev mailing list