Nondeterministic behaviour in SpatialMaxPooling

[mys007]

I have encountered nondeterministic behavior in the backpropagation step of SpatialMaxPooling when kW~=dW or kH~=dH (i.e. atomicmaxgradinput kernel is run). I suspect the issue being caused by atomicAdd() and general non-associativity of floats. Thus, I'm fairly sure that this is a feature of parallelism but somehow I wanted to make you aware of it (it's scary)...

The following code works on my machine (GTX Titan, CUDA 346.46) when the GPU is under some load. If I let the computation run on CPU wit FloatTensors, it's deterministic.

local inp = torch.CudaTensor(1,18,18):zero()
inp[1][3][3] = 1 --will force adding up 3 numbers

fw = torch.CudaTensor(1,8,8):fill(0)
fw[1][2][1] = -0.00055786536540836
fw[1][2][2] = 0.00075417151674628
fw[1][1][2] = -0.00029314149287529

local model = nn.SpatialMaxPooling(3, 3, 2, 2):cuda()    
model:forward(inp)
local bw = model:backward(inp, fw):clone()

for i=1,100 do
    local diff = bw - model:backward(inp, fw)
    print(diff:sum()) --sometimes, the input is not zero!
end

Note further that

local a = (-0.00055786536540836 + 0.00075417151674628) -0.00029314149287529
local b = 0.00075417151674628 + (-0.00029314149287529 -0.00055786536540836)
print(a-b)  -- not zero

On a slightly related note, is there any reason for calling atomicmaxgradinput instead of maxgradinput on SpatialMaxPooling.cu:320?

[soumith]

This is expected. Its Extremely hard to write a max pooling kernel that is deterministic when kW > dW or kH > dH. cunn, cudnn, caffe, all of these are non-deterministic maxpoolings for that case.

when kW <= dW, the kernel can be made deterministic with some effort (I think it is deterministic, but I haven't verified).
The atomic adds were done at some point for just handling the case of kW != dW, for correctness, and they are needed. Otherwise two threads might race.

[mys007]

Looking at the code in Caffe (https://github.com/BVLC/caffe/blob/master/src/caffe/layers/pooling_layer.cu), I believe their backward passes are deterministic: for each bottom element, all possible top elements that could contribute to it are scanned in a single thread, the summing order thus being deterministic. As another benefit, they don't need atomics.

[mys007]

So after empirical testing, I can say that all other implementations (caffe, cudnn V2, convnet2) behave deterministically. Therefore, I would like to reopen the issue. If this is not going to be fixed, it should be at least documented, similarly to the "Reproducibility" chapter in cudnn user guide. It would be also interesting to document how the convolution modules behave.

[soumith]

@wickedfoo investigated this, and this is not what he found. He found that cudnn's max pooling is clearly non-deterministic. @wickedfoo comments?

[mys007]

The behavior of cudnn's maxpool seems to have changed: while experimentally non-deterministic in V2R2, it appears to be ok in V2.

[soumith]

oh I see. Good to know that. The last investigation was indeed probably done in V1 or V2Rxx

[mys007]

I don't put my hand in fire for that, though:).
UPDATE: Actually, now I believe that cudnn.SpatialMaxPooling is not deterministic in V2 either. Sorry for confusion. But Caffe's maxpooling definitely is.

[fmassa]

I think this has been addressed in dc77610