The paper concerns parallel methods for Extremal Optimization (EO) applied for processor load balancing for distributed programs. In these methods the EO approach is used which is parallelized and extended by a guided search of next solution state. EO detects the best strategy of tasks migration leading to a reduction in program execution time. We assume a parallel improvement of the EO algorithm with guided state changes which provides a parallel search for a solution based on two step stochastic selection during the solution improvement based on two fitness functions. The load balancing improvements based on EO aim at better convergence of the algorithm and better quality of program execution in terms of the execution time. The proposed load balancing algorithm is evaluated by experiments with simulated parallelized load balancing of distributed program graphs.