Scheduling for locality of reference to memory
A technique for scheduling instructions includes obtaining a set of instructions that operate on memory objects, and determining the dependencies of the memory objects. The memory objects are then sorted into a sequence of memory objects based on the dependencies of the memory objects, and the set of instructions are scheduled into a sequence of instructions according to the sequence of memory objects. Sorting memory objects allows instructions that operate on the same memory object to be kept together. This helps minimize spilling conditions because intervening instructions that do not operate on the same memory object can be avoided.
1. A computing system comprising:
one or more processors; and
a memory coupled to the one or more processors and storing computer readable code, which when executed by the one or more processors, cause the computing system to perform operations including:
obtaining a set of instructions for a neural network that operates on tensors represented as memory objects;
generating a representation of a memory flow graph by:
for each of the memory objects:
determining a first instruction that performs a first write operation into the memory object, and a second instruction subsequent to the first instruction in the set of instructions that performs a read operation from the memory object and a second write operation into a dependent memory object, wherein the first write operation and the read operation are performed on an overlapping region of the memory object; and
generating a flow dependency edge between the memory object and the dependent memory object in the memory flow graph to indicate that the dependent memory object depends on the memory object;
sorting the memory objects into a sequence of memory objects based on the dependencies of the memory objects; and
scheduling the set of instructions according to the sequence of memory objects, wherein instructions that write to an earlier memory object in the sequence of memory objects are scheduled to be executed before instructions that write to a subsequent memory object in the sequence of memory objects.
2. The computing system computer-implemented method of claim 1 , wherein the first write operation writes into a first portion of the first memory object, and the read operation reads from a second potion of the first memory object that is different than the first portion, wherein the first portion and the second portion overlap with each other in a section of the first memory object.
3. The computing system of claim 1 , wherein sorting the memory objects includes:
selecting a first memory object that does not depend on another memory object to be an initial memory object of the sequence of memory objects;
arranging a second memory object that depends on the first memory object to follow the initial memory object in the sequence of memory objects; and
arranging a third memory object that depends on the second memory object to follow the second memory object in the sequence of memory objects.
4. The computing system of claim 3 , wherein scheduling the set of instructions includes arranging instructions that write to the second memory object to be before instructions that write to the third memory object in the sequence of instructions.
5. The computing system of claim 1 , wherein the sequence of memory objects is provided to an allocator to assign memory addresses to each memory object.
6. The computing system of claim 5 , wherein the memory addresses assigned to a memory object span a rectangular section of memory in a memory array.
7. The computing system of claim 5 , wherein the memory addresses assigned to a memory object include ranges of memory addresses that are non-contiguous.
8. The computing system of claim 5 , wherein the memory addresses assigned to a memory object correspond to a section of a state buffer that stores inputs to a systolic array.
9. The computing system of claim 5 , wherein the memory addresses assigned to a memory object correspond to a section of a result buffer that stores outputs of a systolic array.
10. A non-transitory computer readable medium having stored therein instructions that, when executed by one or more processors, cause the one or more processors to execute a compiler, the compiler configured to perform operations including:
receiving a set of instructions for a neural network that operates on tensors represented as memory objects;
generating a representation of a memory flow graph by:
for each of the memory objects:
determining a first instruction that performs a first write operation into the memory object, and a second instruction subsequent to the first instruction in the set of instructions that performs a read operation from the memory object and a second write operation into a dependent memory object, wherein the first write operation and the read operation are performed on an overlapping region of the memory object; and
generating a flow dependency edge between the memory object and the dependent memory object in the memory flow graph to indicate that the dependent memory object depends on the memory object;
sorting the memory objects into a sequence of memory objects based on the dependencies of the memory objects; and
scheduling the set of instructions according to the sequence of memory objects, wherein instructions that write to an earlier memory object in the sequence of memory objects are scheduled to be executed before instructions that write to a subsequent memory object in the sequence of memory objects.
11. The non-transitory computer readable medium of claim 10 , wherein the operations include:
selecting a first memory object that does not depend on another memory object to be an initial memory object of the sequence of memory objects;
arranging a second memory object that depends on the first memory object to follow the initial memory object in the sequence of memory objects; and arranging a third memory object that depends on the second memory object to follow the second memory object in the sequence of memory objects.
12. The non-transitory computer readable medium of claim 11 , wherein scheduling the set of instructions includes arranging instructions that write to the second memory object to be before instructions that write to the third memory object in the sequence of instructions.
13. The non-transitory computer readable medium of claim 10 , wherein the memory objects correspond to memory regions in a neural network accelerator.
14. A computer-implemented method for scheduling a set of instructions, the computer-implemented method comprising:
receiving the set of instructions for a neural network that operates on tensors represented as memory objects;
generating a representation of a memory flow graph by:
for each of the memory objects:
determining a first instruction that performs a first write into the memory object, and a second instruction subsequent to the first instruction in the set of instructions that performs a read from the memory object and a second write into a dependent memory object, wherein the first write and the read are performed on an overlapping region of the memory object; and
generating a flow dependency edge between the memory object and the dependent memory object in the memory flow graph to indicate that the dependent memory object depends on the memory object;
sorting the memory objects into a sequence of memory objects according to their dependencies in the memory flow graph; and
scheduling the set of instructions according to the sequence of memory objects, wherein instructions that write to an earlier memory object in the sequence of memory objects are scheduled to be executed before instructions that write to a subsequent memory object in the sequence of memory objects.
15. The computer-implemented method of claim 14 , wherein the sequence of memory objects is provided to an allocator to assign physical memory addresses to each memory object.
16. The computer-implemented method of claim 15 , wherein the physical memory addresses assigned to a memory object span a rectangular section of memory in a memory array.
17. The computer-implemented method of claim 15 , wherein the scheduled set of instructions is provided to a post-scheduler to rearrange the instructions.
18. The computer-implemented method of claim 15 , wherein the physical memory addresses assigned to a memory object include ranges of memory addresses that are non-contiguous.
19. The computer-implemented method of claim 15 , wherein the physical memory addresses assigned to a memory object correspond to a section of a state buffer that stores inputs to a systolic array.
20. The computer-implemented method of claim 15 , wherein the physical memory addresses assigned to a memory object correspond to a section of a result buffer that stores outputs of a systolic array.