1. очень хреново параллелится (это поможет только от щёлканья одной задачи параллельно на GPU, но не поможет от того, чтобы запустить их тысячу параллельно),
По первому пункту большой вопрос - а существует ли такой?
Очень хотелось бы чтобы он был. Однако особенность PoW в том, что нужно большое время в работе и очень маленькое время при проверке. Поэтому в обычном понимании "плохо распараллеливаемые алгоритмы" нам не подходят. Например, такой алгоритм PoW как расчет хэша SHA-256 я думаю, что тоже не распараллеливаемый алгоритм, но его просто запускают параллельно с разными параметрами nonce.