Performing criticality-based instruction scheduling in processor devices

A processor device, comprising:

• means for generating an initial schedule comprising a plurality of instructions;
• means for constructing a directed graph based on the initial schedule, wherein:
• each node of a first plurality of nodes of the directed graph corresponds to an instruction of the plurality of instructions;
• and
• each directed edge of one or more directed edges of the directed graph indicates an instruction dependency;
• means for calculating a plurality of criticality metrics corresponding to the first plurality of nodes;
• means for generating a max heap data structure comprising a second plurality of nodes based on the plurality of criticality metrics;
• means for determining an optimized schedule comprising the plurality of instructions by iteratively:
• identifying a root node of the max heap data structure as a node of the second plurality of nodes having a highest criticality metric;
• scheduling an instruction of the plurality of instructions corresponding to the root node;
• and
• removing the root node from the max heap data structure;
• and
• means for executing the plurality of instructions according to the optimized schedule.

A method for performing criticality-based instruction scheduling in processor devices, comprising:

• generating, by a compiler executing on a processor device, an initial schedule comprising a plurality of instructions;
• constructing, by the compiler, a directed graph based on the initial schedule, wherein:
• each node of a first plurality of nodes of the directed graph corresponds to an instruction of the plurality of instructions;
• and
• each directed edge of one or more directed edges of the directed graph indicates an instruction dependency;
• calculating, by the compiler, a plurality of criticality metrics corresponding to the first plurality of nodes;
• generating, by the compiler, a max heap data structure comprising a second plurality of nodes based on the plurality of criticality metrics;
• determining, by the compiler, an optimized schedule comprising the plurality of instructions by iteratively:
• identifying a root node of the max heap data structure as a node of the second plurality of nodes having a highest criticality metric;
• scheduling an instruction of the plurality of instructions corresponding to the root node;
• and
• removing the root node from the max heap data structure;
• and
• executing, by the processor device, the plurality of instructions according to the optimized schedule.

A non-transitory computer-readable medium, having stored thereon computer-executable instructions that, when executed by a processor device, cause a dependency identifier circuit of the processor device to:

• generate an initial schedule comprising a plurality of instructions;
• construct a directed graph based on the initial schedule, wherein:
• each node of a first plurality of nodes of the directed graph corresponds to an instruction of the plurality of instructions;
• and
• each directed edge of one or more directed edges of the directed graph indicates an instruction dependency;
• calculate a plurality of criticality metrics corresponding to the first plurality of nodes;
• generate a max heap data structure comprising a second plurality of nodes based on the plurality of criticality metrics;
• determine an optimized schedule comprising the plurality of instructions by causing the processor device to iteratively:
• identify a root node of the max heap data structure as a node of the second plurality of nodes having a highest criticality metric;
• schedule an instruction of the plurality of instructions corresponding to the root node;
• and
• remove the root node from the max heap data structure;
• and
• execute the plurality of instructions according to the optimized schedule.