Make a sceenshot or photo of the dots then power off for 1 minute and start again.
Same dots of same pattern under same resolution and same picture mean BGA damage (balls under the chip got damaged by thermal or physical pressure). Reballing might help, but there is never ever guarantee unless its clean reballing on special machines.
Also check out if heatsinks of GPU or GPU memory are too hot. Let the machine run 5 minutes at idle desktop, power off, ground yourself, touch the heatsinks with fingers. If its burning 60 or up, thats the problem.
Chances are - you are using outdated kernel without DPM and the old behaviour was to set performance profile, causing GPU to overheat if its not correctly cooled (or fan goes beserk). Catalyst otherwise had DPM since ever, so it would clock down the card below thermal level, causing slowness.
Its possible that the card thermal paste is very old or components are not correctly set from factory, causing them overheat to GPU or memory.
If the card is still under warrantly, obviously replace it. Otherwise get either good self gluing thermal pads/heatsinks if its memory, or for GPU thermal glue (sink glued on from factory) or good thermal paste or even liquid metal (held via bolts or similar).