Formation by gravitational collapse of galaxies and the large-scale structure of the universe is a nonlinear, multi-scale, multi-component problem. This complex process involves dynamics of the gaseous baryons as well as of the gravitationally dominant dark matter. We discuss an implementation of a parallel, distributed memory, cosmological hydrodynamics code using MPI message passing; it is based on the Total-Variation-Diminishing (Harten 1983) serial code of Ryu et al. (1993). This parallel code follows the motion 1983) serial code of Ryu et al. (1993). This parallel code follows the motion of gas and dark matter simultaneously, combining a mesh based Eulerian hydrodynamics code and a Particle-Mesh N-body code. A new, flexible matrix transpose algorithm is used to interchange distributed and local dimensions of the mesh. Timing results from runs on an IBM SP2 supercomputer are given.