Question about the time complexity.

[KevvinHoo]

Question about the time complexity.

[hangxu0304]

Hi,

I did some benchmarks in our own environment (2 nodes with one Nvidia v100 GPU, 100Gbps network, torch 1.3.1, ResNet20, Cifar10, batch_size=256). Here are the time of 1 epoch training for different compressors:

• NoneCompressor(allreduce): 11.03 s
• TopKCompressor(0.01)(allgather): 11.35 s
• QSGDCompressor(127)(allgather): 11.91 s
• YourCode(0.01)(allgather): 14.11 s

Looks like the time cost of your code is much higher than either of Topk and QSGD.
Then I add a simple loop in TopKCompressor and QSGDCompressor to simulate high computation overhead:

Number of loops	1	2	3	4
TopKCompressor(0.01)(allgather)	11.35	12.80	13.25	13.60
QSGDCompressor(127)(allgather)	11.91	15.32	18.87	22.46

The training time grows up linearly with computation overhead, and we can derive the computation cost for TopK and QSGD in this case, which are 0.45 s and 3.4 s for 1 epoch training. Then let's look back at the time cost of your code, it makes more sense now. I think the reason why single TopK or QSGD doesn't show high time cost is probably the benefit of less communication. As you increase the computation overhead, the communication benefits become negligible.

[KevvinHoo]

Thanks for your reply.

I also did some experiments on the GRACE(change the flag tensors_size_are_same in Compressor Init.), I found that the time cost is much higher when we turn the tensors_size_are_same to False. So I think it will bring us higher computational complexity when dealing with different sizes of the gradient tensor.

[hangxu0304]

Indeed. When tensors_size_are_same is set to False, GRACE needs an additional allgather for the size of the tensors, that's why it is slow.