Parallel factor analysis (PARAFAC) is a multi-way decomposition method which allows to find hidden factors from the raw tensor data with many potential applications in neuroscience, bioinformatics, chemometrics etc [1,2]. The Alternating Least Squares (ALS) algorithm can explain the raw tensor by a small number of rank-one tensors with a high fitness. However, for large scale data, due to necessity to compute Khatri-Rao products of long factors, and multiplication of large matrices, existing algorithms require high computational cost and large memory. Hence decomposition of large-scale tensor is still a challenging problem for PARAFAC. In this paper, we propose a new algorithm based on the ALS algorithm which computes Hadamard products and small matrices, instead of Khatri-Rao products. The new algorithm is able to process extremely large-scale tensor with billions of entries in parallel. Extensive experiments confirm the validity and high performance of the developed algorithm in comparison with other well-known algorithms.