Abstract: Sample based texture synthesis is a computation intensive process. To improve the efficiency of large scale texture synthesis by the powerful parallel computing capacity of GPU(graphic processing unit), this paper proposes a novel parallel algorithm for texture synthesis on GPU. The proposed algorithm integrates the patch based texture synthesis method and the global texture optimization method. The algorithm applies the synthesis and optimal procedure iteratively. Each synthesis procedure includes two stages: locating the undecided texture patch, and finding the best match texture patch in the sample texture. After each synthesis procedure, a optimize procedure is applied to refine the coarse texture. The experiments show that the proposed algorithm is efficient and easy to use, and it can synthesize fine large enough texture within a short time, and the algorithm could meet the demand of interactive texture synthesis application.