Cellular automata models require simulations on both large grids, to avoid border effects, and on a large number of realizations, to study the system properties under stationarity. Implementing the cellular automata codes on parallel computers would appear as an ideal solution. Unfortunately, the cellular automata models which are appropriate for earthquakes can only be partially parallelized because they have an intrinsically sequential component. Under extensive modeling using MPI on CRAY T3 and Origin 8300 supercomputers we show that a substantial speed-up can nevertheless be achieved by coarsening the system and making a few mild assumptions on the logical flow of the interactions among macro-cells.