A processor includes a plurality of execution units. At least one of the execution units is configured to execute a complex instruction that requires multiple instruction cycles to execute, and to enforce atomic execution of the complex instruction during a first-portion of the multiple instruction cycles required to execute the complex instruction. The at least one of the execution units is further configured to enable execution of the complex instruction to be interrupted for execution of a different instruction by the at least one execution unit during execution of a second portion of the multiple instruction cycles. The first portion and the second portion are non-overlapping.