Application execution time prediction is of key importance in making decisions about efficient usage of Grid resources. Grid services lack support of a generic application execution time prediction service due to environment specific solutions provided by the existing prediction techniques. To remedy this, we present a generic and comprehensive system to provide execution time predictions of applications on different Grid-sites. Our system is based on a two layered training phase to minimize the training effort, which is our first main contribution. The training phase is driven by a novel experimental design. We also introduce a mechanism of sharing performance measurements across the Grid, on the basis of soft benchmarks, which is our second contribution. Both of these phases support our prediction engine to serve robust predictions. Experiments from the prototype implementation are shown to demonstrate the effectiveness of our proposed system.