In this paper, a new algorithm in the class of the AGE method based on the Brian variant (AGEB) of the ADI is developed to solve the heat equation in 3 space dimensions. The method is iterative, convergent, stable and second order accurate with respect to space and time. It is inherently explicit and is therefore well suited for parallel implementation on the PVM where data decomposition is run asynchronously and concurrently at every time level. Its performance is assessed in terms of speed-up, efficiency and effectiveness.