A parallel algorithm using the generalized pulse spec trum technique and multilevel grid method for solving reservoir structural parameter identification problems is discussed here. The algorithm can be used to iden tify the reservoir's absolute permeability distributions by matching the computed pressure values with mea sured historical pressure values obtained at observa tion wells (history matching). Use of a multilevel grid improves the quality of the identified permeability dis tributions significantly. The whole parameter identifica tion process is very computationally intensive since a group of coupled nonlinear partial differential equa tions (PDEs) and a regularized least square problem must be solved repeatedly with different parameter values. Several hundred megabyte memory is required for reservoir models involving thousands of grid points. The block SOR scheme with red and black or dering and a parallel Householder transformation scheme were used to solve the algebraic equations resulting from the discretization of the PDEs. High speedup has been achieved by exploring parallefisnl, refining the whole program, rather than just the hot- spots, and utilizing the high-speed cache memory effi ciently.