Predictive block motion estimation is accepted and recommended in current video coding standards to eliminate temporal redundancy in video sequences. This paper proposes a simple and efficient computation-aware framework including a sliding-window approach and a stopping-threshold mechanism for the predictive block motion estimation to distribute the available computing power of a codec to achieve higher output quality. Experimental results demonstrate that the output quality of the predictive block motion estimation can be uniformly improved by the proposed computation-aware framework.