diku-dk / futhark

:boom::computer::boom: A data-parallel functional programming language
http://futhark-lang.org
ISC License
2.4k stars 166 forks source link

futhark c and multicore are giving different results #2119

Closed naufraghi closed 8 months ago

naufraghi commented 8 months ago

Hi, I just started testing Futhark, so my code may be "wrong" in many ways, but I think that the output of the c and multicore executable should match or not compile.

Here is the code of minmax.fut and the output:

def minmax [n] (pts: [n]f32) : (f32, f32) =
  let decorated_pts = (map (\(num) -> (num, 0)) pts)
  let (min, max) = reduce (\(amin, amax) (num, _) -> (f32.min amin num, f32.max amax num))
                          (f32.highest, f32.lowest) decorated_pts
  in (min, max)

entry main (pts: []f32) : (f32, f32) =
  minmax pts
[nix-shell:~/Documents/src/prove_futhark]$ futhark --version
Futhark 0.26.0 (prerelease - include info below when reporting bugs)
git: ef0aaddb027eaaae3cbc72f6a1ebf5675e55eddc
Copyright (C) DIKU, University of Copenhagen, released under the ISC license.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

[nix-shell:~/Documents/src/prove_futhark]$ futhark c minmax.fut 

[nix-shell:~/Documents/src/prove_futhark]$ time cat path.repr | ./minmax 
0.000149f32
99.999992f32

real    0m0.451s
user    0m0.442s
sys     0m0.026s

[nix-shell:~/Documents/src/prove_futhark]$ futhark multicore minmax.fut 

[nix-shell:~/Documents/src/prove_futhark]$ time cat path.repr | ./minmax 
0.000149f32
0.000414f32

real    0m0.753s
user    0m0.740s
sys     0m0.039s

The input is the repr of a big Python array, generated with:

import random

path = []
for i in range(1000000):
    path.append(random.random()*100)

open("path.repr", "w+").write(repr(path))
FluxusMagna commented 8 months ago

Your operator is not associative. It will function in the sequential backend because the neutral element is never given as the first argument to the operator, but has to be compatible with this.

ne `op` a == a
a`op` ne == a
(a `op` b) `op` c  == a `op` (b `op` c)

To correct your code you can write

def minmax [n] (pts: [n]f32) : (f32, f32) =
  let decorated_pts = (map (\(num) -> (num, num)) pts)
  let (min, max) = reduce (\(amin, amax) (bmin, bmax) -> (f32.min amin bmin, f32.max amax bmax))
                          (f32.highest, f32.lowest) decorated_pts
  in (min, max)
athas commented 8 months ago

FluxusMagna is correct. There is a bit more information here: https://futhark-lang.org/examples/scan-reduce.html

And here: https://futhark-lang.org/examples/no-neutral-element.html

It is deceptively easy to think of reduce as foldl, but that is not what it is.

naufraghi commented 8 months ago

Thanks, I'll digest it :)