Clouds enable novel execution modes often supported by advanced capabilities such as autonomic schedulers. These capabilities are predicated upon an accurate estimation and calculation of runtimes on a given infrastructure. Using a well understood high-performance computing workload, we find strong fluctuations from the mean performance on EC2 and Eucalyptus-based cloud systems. Our analysis eliminates variations in IO and computational times as possible causes, we find that variations in communication times account for the bulk of the experiment-to-experiment fluctuations of the performance.