How do different block sizes affect the throughput of GPU implementations of AES? I am confused about the effect of different block sizes on AES performance. As you can see here, there is a huge gap between the throughput of different block sizes. As far as I know, every 16 bytes must be encrypted separately, but I don't know what would happen if the block sizes would be increased.

How would 16 bytes of a 1024 byte block be encrypted? Indeed, I can't understand the effect of block size to throughput!
Remember, a GPU consists of a large number of computational engines, all controlled by the same instruction stream.  That is, there might be 64k processors, and all those processors can work on different pieces of data, but they must all do the same thing to all of them.  We refer to this as SIMD parallelism.

With that in mind, how can they encrypt and decrypt a large amount of data quickly?  That depends on the mode they use.

If they use ECB mode, well, ECB mode applies the AES transformation to each 16 byte section independently.  So, given a 1 Megabyte plaintext, then hand off each 16 byte section to a separate computational engine, and then have all the engines perform the AES encrypt operation on the 16 bytes they were given.

A similar trick works for CBC mode decryption.  In that case, the transform is doing an AES decryption on each 16 byte block, and then exclusive-or'ing the result with the previous ciphertext block.  Similar to the ECB mode case, all that can be done in parallel by the GPU computational engines.

However, if you're asking about CBC mode encryption, well, that can't be parallelized.  There, to encrypt block N, you first exclusive-or in the ciphertext of block N-1, and (unlike the decryption case) you don't have that until the computation of block N-1 is completed.  Hence (as mentioned on the web page), you can't parallelize it, and the web page doesn't give any results there (because the GPU is actually slower than just having the main CPU do the computation).