A processor having a dependency matrix comprises a first array comprising a plurality of cells arranged in a plurality of columns and a plurality of rows. Each row represents an instruction in a processor execution queue and each cell in the first array represents a dependency relationship between two instructions in the processor execution queue. A clear port couples to the first array and clears a column of the first array. A producer status module couples to the clear port and the first array and determines an execution status of a producer instruction, wherein the producer instruction is an instruction in the processor execution queue. An available-status port couples to the first array and the producer status module and sets a read wordline column corresponding to the producer instruction based on the execution status of the producer instruction. The available-status port deasserts the read wordline column in response to a selection of the producer for execution. The available-status port reasserts the read wordline column in the event the producer status module determines the producer instruction has been rejected. The clear port clears the column of the first array corresponding to the producer instruction in the event the producer status module determines the producer instruction has been executed.