I hadn't considered OpenMP because I've had practically no exposure to it.

GCC doesn't have any intrinsics like the Intel and MS compilers have. I'll have to write that part in Assembly.