In this paper, we describe a block-based threshold modulation error diffusion algorithm to parallelize the halftone process without generating both block-boundary and diagonal artifacts. A novel scan path is used to pass the quantization error effectively between blocks and the input-dependent threshold modulation is applied during the inner-block processing. To obtain a suitable parameter set for the error weights and threshold modulation strength, a cost function is designed. Experimental results show that the proposed algorithm generates high quality halftone images which are visually similar to those generated by serial error diffusion algorithms. Our algorithm achieves better performance both in quality and parallelism compared to other halftoning approaches.