That is one of the comon EDA questions: What are the benefits vs. the caveats of high level decisions compare to an algorithm working on a global detailed design description.. Early partitioning costs some optimization potential and requires guestimates at the boundaries, but frees up computational ressources that can used to obtain better results within the partitions in the same tool run time. What is better is not easy to say beforehand.
While currently not at the top of the crowd, partitioning based placers still perform pretty well. They were introduced without parallization in mind so partitioning isn't all bad. Another example of this type of tradeoff (albeit no related to parallel algorithms) are all approaches that use clustering. They lose detail to make the overall problem more manageable.
I do not know about Altera, but Xilinx has to do partial partitioning anyway to place flip-flops connected to regional clocks. (well, actually this is floorplanning not partitioning, but it has similar effects on the placement)
Kolja Sulimma