並列化ド素人の自分だが
Aspiration searchの真ん中の値で二分すれば
単純に二倍速くなりそうという感じは受ける。
ちょっと試せないので分からないけど。

ボナンザも歩の交換値２つぶんでAspiration searchをやってるらしいので。。

やっぱり問題はその次からの一回の探索を分ける方法だねえ。