並列化のキーワードは網羅って聞いたことがあるような。
例えばソートだと、順列(全パターン)を作ってそれが並んでいるか調べるだけでいい。

現在の手法は今までのアルゴリズムを並列化しようとしているからロックとかで問題になっているんでしょ？
アルゴリズムを根本から変えれば良いと思うけど。