This paper discusses our experiences in implementing a data parallel explicit self-starting finite element procedure on the Connection Machine (CM-5) for linear/non-linear computational structural dynamic applications involving structured and unstructured grids. The parallel implementation criteria that influence the efficiency of an algorithm include the amount of communication, communication routing, and load balancing. In this study, we have implemented a simple and effective self-starting explicit time integration procedure for linear and nonlinear structural dynamic applications for both structures and unstructured finite element meshes. The implementation of the present self-starting formulations for linear and elasto-plastic applications on serial and data parallel machines is discussed. Numerical test models for a linear and non-linear one-dimensional applications and a two-dimensional unstructured finite element mesh are discussed. Further, performance studies are discussed in detail.