We have reformulated the multi-reference configuration interaction algorithm for massively parallel architectures with distributed memory, such that the communication effort associated with the matrix element computation is independent of the number of units of the machine. Exploiting the special structure of the MRCI Hilbert space, this formulation allows the evaluation of all matrix elements in six distinct phases-independent of the number of electrons, the number of orbitals, the number of references and of the number of nodes of the computer used. Using an object-oriented approach, we have implemented and tested the a symmetry-adapted determinantal version of the algorithm in C++ on an IBM-SP2 computer. Our initial results for benchmark calculations on N-2 and O-3 for Hilbert spaces of up to 12 X 10(6) determinants indicate that the vector redistribution effort is negligible in actual calculations. The remaining difficulties to perform calculations for significantly larger Hilbert spaces are critically addressed.