We implemented the search-frontier splitting scheme on Parix and PVM using the VLSI floorplan optimization problem and the 15-puzzle as application domains.