The decomposition of a binary morphological structuring element is a well-known problem in pattern recognition that has often been addressed in the l iterature. Generally, only deterministic solutions have been considered, each relying on different assumptions. A different solution, with no such constraints, has been proposed by Anelli, Broggi and Destri: it is based on a stochastic evolutionary technique which is obviously computationally demanding. This work presents its parallel implementation aimed to the improvement of both the qualitative and quantitative performance of this approach.