We consider estimation of system order and parameters for ARX systems with martingale difference noise. The order estimation criterion used is the accumulated prediction error (or predictive least-square error) criterion which generates strongly consistent order estimates. High computational load and over- complex (when real data are processed) models are two glaring problems occurring in order estimation. We develop a fast and parallel algorithm for strongly consistent estimation of system order and parameters. This shows that order estimation by minimizing the APE cost function could be performed on-line. We also modify the APE criterion by adding a device for tradeoffs between model complexity and model accuracy. This modification helps to solve the over-complexity problem. Furthermore, we present a simulation study on order estimation to complement the theoretical analysis.