[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