In this work UEGO, a new stochastic optimization technique for accelerating and/or parallelizing existing search methods is described and parallelized. The skeleton of the algorithm is a parallel hillclimber. The separate hillclimbers work in restricted search regions (or clusters) of the search space. The volume of the clusters decreases as the search proceeds which results in a cooling effect similar to simulated annealing. Вesides this, UEGO can be effectively parallelized because the amount of information exchanged among clusters (communication) is minimal. The purpose of this communication is to ensure that a hill is explored only by one hillclimber. UEGO makes periodic attempts to find new hills to climb. Two parallel algorithms of UEGO have been implemented and empirical results are also presented including an analysis of speedup.