Compute-intensive simulations are currently good candidates for being executed on distributed computers and Grids, in particular for applications with a large number of input data whose values change throughout the simulation time and where the communications are not a critical factor. Although the number of computations usually depends on the bulk of input data, there are applications in which the computational load depends on the particular values of some input data. We propose a general methodology to deal with the problem of improving load balance in these cases. It is divided into two main stages. The first one is an exhaustive study of the parallel code structure, using performance tools, with the aim of establishing a relationship between the values of the input data and the computational effort. The next stage uses this information and provides a mechanism to distribute the load of any particular simulating situation among the computational nodes. A load balancing strategy for the particular case of STEM-II, a compute-intensive application that simulates the behavior of pollutant factors in the air, has been developed, obtaining an important improvement in execution time.