Attribute reduction is a key problem in rough set theory. A novel algorithm of attribute reduction based on parallel particle swarm optimization is proposed, which can significantly reduce execution time for complex large-scale data sets. This algorithm constructs heuristic information from the viewpoint of information theory, combines genetic idea and tabu operators with particle swarm optimization (PSO), redefines the updating process of particle swarm, and introduces the parallel strategy based on master-slave model with coarse grain in constructing the parallel PSO architecture. It maintains diversity of particles, which avoids the premature problem and restrains the degeneration phenomenon, and enhances the efficiency of attribute reduction. The simulation results show that this algorithm is more feasible and efficient compared with current approaches.