Domain wall theory (DWT) has proved to be a powerful tool for the analysis of one-dimensional transport processes. A simple version of it was found very accurate for the Totally Asymmetric Simple Exclusion Process (TASEP) with random sequential update. However, a general implementation of DWT is still missing in the case of updates with less fluctuations, which are often more relevant for applications. Here we develop an exact DWT for TASEP with parallel update and deterministic (p=1) bulk motion. Remarkably, the dynamics of this system can be described by the motion of a domain wall not only on the coarse-grained level but also exactly on the microscopic scale for arbitrary system size. All properties of this TASEP, time-dependent and stationary, are shown to follow from the solution of a bivariate master equation whose variables are not only the position but also the velocity of the domain wall. In the continuum limit this exactly soluble model then allows us to perform a first principle derivation of a Fokker-Planck equation for the position of the wall. The diffusion constant appearing in this equation differs from the one obtained with the traditional `simple DWT.