Processors comprising a plurality of pipelines are disclosed, each pipeline having a plurality of pipeline stages (142, 146) for executing an instruction on successive clock cycles. The processors include distributed stall control circuitry (148, 150, 152, 154) which allow an instruction in one pipeline to become temporarily out of step with an instruction in another pipeline. This may allow time for a global signal, such as a global stall signal, to be distributed.