Method of scheduling loops for processor having a plurality of functional units

Patent metadata

Field	Value
Publication number	US-9292287-B2
Application number	US-201414330675-A
Country	US
Kind code	B2
Filing date	Jul 14, 2014
Priority date	Nov 25, 2013
Publication date	Mar 22, 2016
Grant date	Mar 22, 2016

Abstract

Provided is a loop scheduling method including scheduling a first loop using execution units, and scheduling a second loop using execution units available as a result of the scheduling of the first loop. An n-th loop (n>2) may be scheduled using a result of scheduling an (n−1)-th loop, similar to the (n−1)-th loop. The first loop may be a higher priority loop than the second loop.

First claim

What is claimed is:

1. A loop scheduling method comprising:
scheduling, using a processor, a higher priority loop using execution units;
scheduling, using the processor, a lower priority loop using execution units available as a result of the scheduling of the higher priority loop;
unrolling, using the processor, a result of the scheduling of the higher priority loop in response to the lower priority loop not being scheduled using the available execution units as a result of the scheduling of the higher priority loop; and
scheduling, using the processor, the lower priority loop using execution units available as the unrolled result of the scheduling of the higher priority loop.

2. The loop scheduling method of claim 1 , wherein the scheduling of the higher priority loop comprises scheduling a highest priority loop using the execution units.

3. The loop scheduling method of claim 1 , wherein the scheduling of the lower priority loop comprises scheduling at least a portion of the lower priority loop using execution units yet to be assigned to the higher priority loop, in cycles for which the higher priority loop is scheduled.

4. The loop scheduling method of claim 1 , wherein the scheduling of the higher priority loop comprises:
selecting independent loops from among loops included in source code; and
determining priorities of the selected independent loops.

5. The loop scheduling method of claim 1 , wherein a priority of the higher priority loop is higher than a priority of the lower priority loop, and a priority of a loop is calculated based on at least one of an iteration count of the loop and a number of cycles for a single iteration of the loop.

6. The loop scheduling method of claim 1 , wherein the scheduling of the lower priority loop comprises assigning instructions to the available execution units in cycles for which the higher priority loop is scheduled, based on a data dependency among the instructions included in the lower priority loop.

7. The loop scheduling method of claim 1 , wherein the scheduling of the lower priority loop comprises:
determining an execution unit to be used to schedule the lower priority loop; and
verifying whether the determined execution unit is available in a cycle for which the higher priority loop is scheduled.

8. The loop scheduling method of claim 1 , wherein the scheduling of the higher priority loop comprises assigning instructions to the execution units in cycles, based on a data dependency among the instructions included in a highest priority loop.

9. The loop scheduling method of claim 1 , wherein the unrolling comprises determining whether the result of the scheduling of the higher priority loop is to be unrolled, based on at least one of a threshold value for an unrolling count and a threshold value for a number of cycles of the unrolled result of the scheduling of the higher priority loop.

10. The loop scheduling method of claim 1 , wherein the scheduling of the lower priority loop comprises restricting, using predication guarding, an execution of the lower priority loop after the lower priority loop is iterated in response to an iteration count of the higher priority loop being greater than an iteration count of the lower priority loop.

11. The loop scheduling method of claim 1 , further comprising:
scheduling, using the processor, the lower priority loop to iterate a remaining portion of the lower priority loop after the higher priority loop is iterated in response to an iteration count of the higher priority loop being less than an iteration count of the lower priority loop.

12. The loop scheduling method of claim 11 , further comprising:
scheduling, using the processor, an instruction to store intermediate data of the lower priority loop after the higher priority loop is iterated.

13. The loop scheduling method of claim 1 , wherein the execution units are included in a coarse-grained reconfigurable array (CGRA) processor or a very long instruction word (VLIW) processor.

14. The loop scheduling method of claim 1 , wherein the execution units comprise:
a scalar functional unit (FU) configured to process a scalar data operation;
a pack/unpack FU configured to process a conversion between scalar data and vector data;
a vector load/store FU configured to process loading and storing of vector data; and
a vector FU configured to process an operation on vector data.

15. A non-transitory computer-readable storage medium storing a program for loop scheduling, the program comprising instructions configured to cause a computer to perform the loop scheduling method of claim 1 .

16. A loop scheduling method comprising:
scheduling, using a processor, a first loop using execution units; and
scheduling, using the processor, a second loop using execution units available as a result of the scheduling of the first loop,
wherein the scheduling of the second loop comprises restricting, using predication guarding, an execution of the second loop after the second loop is iterated in response to an iteration count of the first loop being greater than an iteration count of the second loop.

17. The loop scheduling method of claim 16 , wherein the scheduling of the second loop comprises scheduling at least a portion of the second loop using execution units yet to be assigned to the first loop in cycles for which the first loop is scheduled.

18. The loop scheduling method of claim 16 , further comprising:
selecting, using the processor, two independent loops from among loops included in source code; and
determining, using the processor, a selected loop that enables a number of the available execution units to increase to be the first loop, and determining, using the processor, a remaining selected loop to be the second loop.

19. The loop scheduling method of claim 16 , wherein a priority of the first loop is higher than a priority of the second loop, and a priority of a loop is calculated based on at least one of an iteration count of the loop and a number of cycles for a single iteration of the loop.

20. The loop scheduling method of claim 16 , wherein the scheduling of the second loop comprises assigning instructions to the available execution units in cycles for which the first loop is scheduled, based on a data dependency among the instructions included in the second loop.

21. The loop scheduling method of claim 16 , wherein the scheduling of the second loop comprises:
determining an execution unit to be used to schedule the second loop; and
verifying whether the determined execution unit is available in a cycle for which the second loop is scheduled.

22. The loop scheduling method of claim 16 , wherein the scheduling of the first loop comprises assigning instructions to the execution units in cycles, based on a data dependency among the instructions included in the first loop.

23. The loop scheduling method of claim 16 , further comprising:
unrolling, using the processor, a result of the scheduling of the first loop in response to the second loop not being scheduled using the available execution units as a result of the scheduling of the first loop; and
scheduling, using the processor, the second loop using execution units available as the unrolled result of the scheduling of the first loop.

24. The loop scheduling method of claim 23 , wherein the unrolling comprises determining whether the result of the scheduling of the first loop is to be unrolled, based on at least one of a t

Assignees

• Samsung Electronics Co Ltd

Inventors

• Lee Yeon Bok
• Park Young Hwan
• Yang Ho
• Prasad Keshava

Classifications

• G06F9/3836

  Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution · CPC title

• G06F9/30065 Primary

  Loop control instructions; iterative instructions, e.g. LOOP, REPEAT · CPC title

• G06F8/4452 Primary

  Software pipelining · CPC title

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• Y02D10/00

  Energy efficient computing, e.g. low power processors, power management or thermal management · CPC title