how to make NCCL deterministic for different size for the same thing?

[kingder]

hi,

first of all, It's not a bug!

we've found that NCCL seems non deterministic when we combine the reduced arrays first then split after reduced. check the below code snippet.

even I turned off the LL code path by setting NCCL_LL_THRESHOLD=0, the diff is small, but it also suggest that we can't do it this way when we want exactly the same results for those two scenarios.

did I miss something or is this by design, if it's the latter, is there any way to make it deterministic?

NCCL Version: 2.1.15
Torch Version: 0.4.1

import numpy as np
import random
import torch
import os
import torch.distributed as dist
from torch.multiprocessing import Process

def run(rank, size):
    num_gpus = torch.cuda.device_count()
    torch.cuda.set_device(rank % num_gpus)
    seed = rank
    random.seed(0)
    np.random.seed(seed)
    torch.manual_seed(seed)
    torch.cuda.manual_seed(seed)

    total = 100
    rand_sizes = [random.randint(1, 10000) for i in range(total)]
    rand_tensors = [torch.rand(rand_sizes[i]).cuda() for i in range(total)]
    rand_tensors_fuse_sync = [a.clone() for a in rand_tensors]

    # pure sync
    for a in rand_tensors:
        dist.all_reduce(a)

    # fuse sync
    cur = 0
    while cur < total:
        fus = torch.cat((rand_tensors_fuse_sync[cur], rand_tensors_fuse_sync[cur+1]))
        dist.all_reduce(fus)
        rand_tensors_fuse_sync[cur], rand_tensors_fuse_sync[cur+1] = torch.split(
            fus, (rand_sizes[cur], rand_sizes[cur+1]))
        cur += 2

    if rank == 0:
        for i in range(total):
            x1 = rand_tensors[i].mean()
            x2 = rand_tensors_fuse_sync[i].mean()
            if x1 != x2:
                d12 = torch.max(torch.abs(rand_tensors[i] - rand_tensors_fuse_sync[i]))
                print('found difference {}: {} vs {}; diffmax {}'.format(i, x1, x2, d12))

    all_tensors = torch.cat(rand_tensors)
    all_tensors_fuse_sync = torch.cat(rand_tensors_fuse_sync)
    print('[rank {}] mean {} vs {}'.format(
        rank, 
        torch.mean(all_tensors).item(), 
        torch.mean(all_tensors_fuse_sync).item()))

def init_processes(rank, size, fn, backend='nccl'):
    """ Initialize the distributed environment. """
    os.environ['MASTER_ADDR'] = '127.0.0.1'
    os.environ['MASTER_PORT'] = '29500'
    os.environ['NCCL_LL_THRESHOLD'] = '0'
    dist.init_process_group(backend, rank=rank, world_size=size)
    fn(rank, size)

if __name__ == "__main__":
    size = 4
    processes = []
    for rank in range(size):
        p = Process(target=init_processes, args=(rank, size, run))
        p.start()
        processes.append(p)

    for p in processes:
        p.join()

[rank 2] mean 2.000257730484009 vs 2.000257730484009
[rank 1] mean 2.000257730484009 vs 2.000257730484009
[rank 3] mean 2.000257730484009 vs 2.000257730484009
found difference 1: 2.0115139484405518 vs 2.0115137100219727; diffmax 4.76837158203125e-07
found difference 5: 2.0040056705474854 vs 2.0040054321289062; diffmax 4.76837158203125e-07
found difference 27: 1.9824261665344238 vs 1.9824262857437134; diffmax 4.76837158203125e-07
found difference 28: 2.0100297927856445 vs 2.0100300312042236; diffmax 4.76837158203125e-07
found difference 46: 2.001265287399292 vs 2.001265048980713; diffmax 4.76837158203125e-07
found difference 59: 1.9912501573562622 vs 1.9912502765655518; diffmax 4.76837158203125e-07
found difference 70: 2.0031909942626953 vs 2.003190755844116; diffmax 4.76837158203125e-07
found difference 77: 2.0027735233306885 vs 2.0027732849121094; diffmax 4.76837158203125e-07
found difference 89: 2.0007925033569336 vs 2.0007927417755127; diffmax 4.76837158203125e-07
[rank 0] mean 2.000257730484009 vs 2.000257730484009

[sjeaugey]

Hi, this is indeed expected. Floating point addition is not an associative operation. Therefore, depending on which rank starts the computation you get a different result.
For example, if 0 starts, you get :
sum = ((..((a0 + a1) + a2) + ... )+ an-1)
and if 3 starts, you get :
sum = ((..((a3 + a4) + a5) + ... )+ an-1 + a0 + a1) + a2)

Note there is no good answer, there are n different possible results each with different rounding errors at each step of the addition.

Having each rank start the sum at different offsets is better to ensure we use all links all the time, so this is needed to get best performance.

If you want all results to be the same, you can use reduce + broadcast to a fixed root. This way, the reductions will always be done in the same order for all offsets, although performance might be slightly lower.

[kingder]

Thank you for your quick reply!

I get that how the rounding works here, but the confusion here is the fusion part.

As you said, if the precision totally depends on which rank starts the computation first, we should observe totally different result each time, even for the no fusion part, but I actually found the output always the same among different runs (see below), it seems deterministic to me for fixed sizes.

If we fuse the array a little bit (like the one I give above), the only thing changes is the reduced array size, which will impact the offset for each rank, but it has no impact to the computation order, right?

first run:

[rank 7] mean 4.000885963439941 vs 4.000885486602783
[rank 2] mean 4.000885963439941 vs 4.000885486602783
[rank 5] mean 4.000885963439941 vs 4.000885486602783
[rank 3] mean 4.000885963439941 vs 4.000885486602783
[rank 1] mean 4.000885963439941 vs 4.000885486602783
[rank 6] mean 4.000885963439941 vs 4.000885486602783
[rank 4] mean 4.000885963439941 vs 4.000885486602783
found difference 1: 4.005516529083252 vs 4.00551700592041; diffmax 9.5367431640625e-07
found difference 6: 3.9873623847961426 vs 3.9873626232147217; diffmax 9.5367431640625e-07
found difference 8: 3.9974846839904785 vs 3.9974849224090576; diffmax 9.5367431640625e-07
found difference 17: 3.995753049850464 vs 3.995753526687622; diffmax 9.5367431640625e-07
found difference 24: 4.008672714233398 vs 4.008673191070557; diffmax 9.5367431640625e-07
found difference 37: 3.974834442138672 vs 3.974834680557251; diffmax 9.5367431640625e-07
found difference 39: 4.0255446434021 vs 4.025545120239258; diffmax 9.5367431640625e-07
found difference 48: 4.003605842590332 vs 4.00360631942749; diffmax 9.5367431640625e-07
found difference 60: 3.9945504665374756 vs 3.994550943374634; diffmax 9.5367431640625e-07
found difference 70: 4.004161357879639 vs 4.0041608810424805; diffmax 9.5367431640625e-07
found difference 98: 4.004231929779053 vs 4.0042314529418945; diffmax 9.5367431640625e-07
[rank 0] mean 4.000885963439941 vs 4.000885486602783

second run:

[rank 6] mean 4.000885963439941 vs 4.000885486602783
[rank 5] mean 4.000885963439941 vs 4.000885486602783
[rank 1] mean 4.000885963439941 vs 4.000885486602783
[rank 4] mean 4.000885963439941 vs 4.000885486602783
[rank 7] mean 4.000885963439941 vs 4.000885486602783
[rank 3] mean 4.000885963439941 vs 4.000885486602783
[rank 2] mean 4.000885963439941 vs 4.000885486602783
found difference 1: 4.005516529083252 vs 4.00551700592041; diffmax 9.5367431640625e-07
found difference 6: 3.9873623847961426 vs 3.9873626232147217; diffmax 9.5367431640625e-07
found difference 8: 3.9974846839904785 vs 3.9974849224090576; diffmax 9.5367431640625e-07
found difference 17: 3.995753049850464 vs 3.995753526687622; diffmax 9.5367431640625e-07
found difference 24: 4.008672714233398 vs 4.008673191070557; diffmax 9.5367431640625e-07
found difference 37: 3.974834442138672 vs 3.974834680557251; diffmax 9.5367431640625e-07
found difference 39: 4.0255446434021 vs 4.025545120239258; diffmax 9.5367431640625e-07
found difference 48: 4.003605842590332 vs 4.00360631942749; diffmax 9.5367431640625e-07
found difference 60: 3.9945504665374756 vs 3.994550943374634; diffmax 9.5367431640625e-07
found difference 70: 4.004161357879639 vs 4.0041608810424805; diffmax 9.5367431640625e-07
found difference 98: 4.004231929779053 vs 4.0042314529418945; diffmax 9.5367431640625e-07
[rank 0] mean 4.000885963439941 vs 4.000885486602783

[sjeaugey]

Actually which ranks starts the sum at which offset is deterministic, and it depends on the buffer size as well. Basically, NCCL works like this (not considering LL) :

• We use a single chunk of data up to a certain size (usually nthreads*16 = 4K). So, up to that size, all data will be reduced in the same order.
• Then we increase the number of chunks until we have nranks chunks.
• Then we increase the chunk size until we reach the maximum chunk size (1M).

Here is an example with 4 ranks and min/max chunk sizes of 4K/1M :

As sizes increases from 16K to 4M, a value at offset 16K-1 will start from 3, then 2, then 1, then 0 (not well illustrated since we're not at scale).

[kingder]

Thank you so much, very clear and detailed explanation!