MODULO SCHEDULING OF MULTIPLE INSTRUCTION CHAINS

摘要

Instructions of a loop are related in instruction chains represented by a da ta dependency graph with multiple first nodes for the instruction chains (either in a backward or forward direction). These instructions are modulo scheduled for execution by a processor. Execution parameters for each instruction denote execution relationships with previous instructions including latencies from execution of previous instructions and processor resources used by the instruction for execution. The instructions are ordered for scheduling according to a priority value for ea ch instruction, which may be determined in a number of ways. Ordering starts with all instructions tha t have the highest priority value. Ordering continues with instructions related to instructions that have already been ordered; those instructions that are related and have a given priority value for the unordered instructions. After all instructions have been ordered they are modulo scheduled. Instructions are scheduled according to the previously determined order on the basis of latencies of previous related instructions, resources used by the instruction for execution and resources available in time cycles in the schedule.