That looks like it could potentially be a faulty GPU, but here are some things you can try first of all.
How is the GPU connected to the monitor? Try using a different display cable and a different display connection on the graphics card.
Try a different power supply. Perhaps yours is failing when put under heavy load but working fine under lighter loads, LoL, CS:GO etc.
Try underclocking the core and memory to see if that reduces the artifacts.
Download DDU, extract it and run it. Follow the prompt to restart in safe mode and then click Clean and Restart. You can download DDU here.
Try reverting to Catalyst 15.11.1 Beta.
The GPU is connected to the monitor over HDMI. I have also tried to connect it with DVI but I had the same results. I can't really test another PSU but I bought this PSU with the GPU so it is around 1-2 weeks old. Catalyst also didn't fix the problem. It's artifacting less than when I tried the card for the first time. The artifacting seems lower on ultra and low settings but gets worse if I set it to high/medium. When V-Sync is turned on the artifacting is happening less frequently aswell.