For what it's worth, GNU Parallel seems to be fairly new; at work I have an ubuntu distro from this year and it's not in the package repo yet. xargs is POSIX so you can expect it everywhere, though no parallel option is specified (merely encouraged).