1. A method for encoding frames in a video, comprising: employing at least one hardware processor for: encoding two successive input frames of the video, a preceding input frame and a succeeding input frame, comprising: (a1) dividing the preceding input frame into slices, each slice characterizing a spatial region within the preceding input frame; (a2) dividing the succeeding input frame into slices, each slice characterizing a spatial region within the succeeding input frame; and in parallel: (a3) processing one or more slices in the preceding input frame by a multi-core processor; (a4) after the processing of one of said one or more slices in the preceding input frame has been completed, processing, by those cores of the multi-core processor that are available for processing, one or more slices in the succeeding input frame having locations corresponding to the one or more slices in the preceding input frame, comprising: for a slice of said one or more slices in the succeeding input frame for which a corresponding slice in the preceding input frame has been already processed: (i) performing motion estimation using all slices in a motion estimation window for the corresponding slice in the preceding input frame, provided said all slices in the motion estimation window in the preceding input frame have been processed; (ii) provided said all slices in the motion estimation window for the corresponding slice in the preceding input frame have not been processed, performing the motion estimation using only those slices in the motion estimation window in the preceding input frame that have been already processed; and (iii) provided none of the slices in the motion estimation window in the preceding input frame have been processed except for the corresponding slice, performing the motion estimation using the corresponding slice in the preceding input frame.