I wouldn't do it exactly this way, but for a CPU implementation I would consider a blocked rotate that decomposes the image into square tiles of about [cache-li

I wouldn't do it exactly this way, but for a CPU implementation I would consider a blocked rotate that decomposes the image into square tiles of about [cache-line x cache-line] in size (e.g., 8x8 for RGBA8 data with a 32 byte cache line). Then cycle sets of four tiles and rotate within them in the process. E.g., cycle and rotate the four A tiles, cycle and rotate the four B tiles, etc: A B C D M I E A E F G H N J F B I J K L O K G C M N O P P L H D D H L P P O N M C G K O L K J I B F J N H G F E A E I M D C B A With the right tile sizes and memory alignment you could parallelize these steps without false sharing.