Memory access optimisation using per-layer computational mapping and memory allocation for CNN application

1. A method of configuring a multi-processing-unit System-on-Chip (SoC) to execute a Convolutional Neural Network (CNN) process comprising a plurality of CNN layers, the method comprising the steps of:

receiving a plurality of predetermined schedules each specifying an order of processing steps for processing input feature maps (input FMs) input to a CNN layer of the CNN process executing on the multi-processing-unit SoC and for processing output feature maps (output FMs) output from the CNN layer of the CNN process executing on the multi-processing-unit SoC, wherein processing input FMs and processing output FMs are performed by processing units of the multi-processing-unit SoC;

for each predetermined schedule of the plurality of predetermined schedules:

determining memory access amount information describing how many memory accesses are required to process the input FMs and the output FMs of the CNN layer of the CNN process executing on the multi-processing-unit SoC;

expressing the determined memory access amount information as one or more relationships describing an extent to which data can be reused by the processing steps of the predetermined schedule without requiring additional memory accesses;

combining the one or more relationships with a cost of writing to an external memory and a cost of reading from the external memory, to form memory access information describing a total external memory access cost required to implement the predetermined schedule;

determining a first memory allocation for an on-chip memory of the SoC for the input FMs and the output FMs dependent upon the determined memory access amount information and a size of the on-chip memory of the SoC;

determining, dependent upon the determined memory access amount information and the first memory allocation determined for the on-chip memory of the SoC for each predetermined schedule of the plurality of predetermined schedules;

a predetermined schedule from the plurality of predetermined schedules which minimises the memory access amount information of the external memory access for the CNN layer of the CNN process executing on the multi-processing-unit SoC; and

a first memory allocation associated with the predetermined schedule; and

applying the predetermined schedule and the first memory allocation associated with the predetermined schedule to the CNN layer of the CNN process executing on the multi-processing-unit SoC.

2. A method according to claim 1 , wherein the processing steps in the plurality of predetermined schedules comprise nested processing loops and the step of determining the memory access amount information is dependent upon an order of the nested processing loops.

3. A method according to claim 1 , wherein the cost of writing to the external memory and the cost of reading from the external memory is dependent upon the multi-processing-unit SoC.

4. A method according to claim 3 , further comprising the step of, if a second memory allocation is not different to the first memory allocation, using the first memory allocation as the second memory allocation.

5. A method according to claim 1 , wherein the step of determining the first memory allocation for the on-chip memory of the SoC comprises, in relation to a specific CNN layer of the CNN process executing on the multi-processing-unit SoC and a specific schedule, formulating the memory access amount information as a linear memory access relationship dependent upon a weighted value of the number of input FMs required to be in the on-chip memory of the SoC, and a weighted value of the number of output FMs required to be in the on-chip memory of the SoC.

6. A method according to claim 5 , further comprising the steps of:

determining a constraint for the on-chip memory of the SoC with respect to (i) a number of input FMs required to be in the on-chip memory of the SoC, (ii) a number of output FMs required to be in the on-chip memory of the SoC, and (iii) a minimum buffer size required by the specific schedule;

combining the linear memory access relationship and the constraint for the on-chip memory of the SoC to determine two on-chip memory allocation combinations of (i) the number of input FMs required to be in the on-chip memory of the SoC and (ii) the number of output FMs required to be in the on-chip memory of the SoC; and

selecting an on-chip memory allocation combination which has the lower memory access amount information to thereby determine the first memory allocation for the on-chip memory of the SoC.

7. A method according to claim 5 , wherein the weighted value of the number of input FMs is dependent upon a size of the input FMs, a number of output FMs produced by processing the input FMs, and a read cost per byte to read from the external memory.

8. A method according to claim 5 , wherein the weighted value of the number of output FMs is dependent upon a size of the output FMs and a write cost per byte to write to the external memory.

9. A method according to claim 1 , wherein the step of determining, dependent upon the determined memory access amount information and the first memory allocation determined for the on-chip memory of the SoC for each predetermined schedule of the plurality of predetermined schedules, the predetermined schedule from the plurality of predetermined schedules which minimises the memory access amount information of the external memory access for the CNN layer of the CNN process executing on the multi-processing-unit SoC, and the first memory allocation associated with the predetermined schedule comprises the steps of:

selecting, for each of the plurality of predetermined schedules, a corresponding best memory allocation dependent upon parameters of the CNN layer of the CNN process executing on the multi-processing-unit SoC;

determining a number of external memory accesses for each of the plurality of predetermined schedules depending upon the memory access amount information and the corresponding best memory allocation; and

selecting the predetermined schedule from the plurality of predetermined schedules with the lowest determined number of external memory accesses and the corresponding best memory allocation for the predetermined schedule from the plurality of predetermined schedules and the CNN layer of the CNN process executing on the multi-processing-unit SoC.

10. A method according to claim 1 , wherein the memory access amount information is dependent upon a read cost per byte to read from the external memory and a write cost per byte to write to the external memory.

11. A method according to claim 1 , wherein the first memory allocation for the on-chip memory of the SoC assigns, during performance of the method for a specified CNN layer of the CNN process executing on the multi-processing-unit SoC, a weight buffer for storing values of CNN kernel weights used in CNN convolutions, an input FM buffer to store input FMs, and an output FM buffer to store output FMs.

12. A system for configuring a multi-processing-unit System-on-Chip (SoC) to execute a Convolutional Neural Network (CNN) process comprising a plurality of CNN layers, the system comprising:

one or more memories storing executable computer readable code; and

one or more processors executing the executable computer readable code in order to perform the steps of:

receiving a plurality of predetermined schedules each specifying an order of processing steps for processing input feature maps (input FMs) input to a CNN layer of the CNN process executing on the multi-processing-unit SoC and for processing output feature maps (output FMs) output from the CNN layer of the CNN process executing on the multi-processing-unit SoC, wherein processing input FMs and processing output FMs are performed by processing units of the multi-processing-unit SoC;

for each predetermined schedule of the plurality of predetermined schedules:

determining memory access amount information describing how many memory accesses are required to process the input FMs and the output FMs of the CNN layer of the CNN process executing on the multi-processing-unit SoC;

expressing the determined memory access amount information as one or more relationships describing an extent to which data can be reused by the processing steps of the predetermined schedule without requiring additional memory accesses;

combining the one or more relationships with a cost of writing to an external memory and a cost of reading from the external memory, to form memory access information describing a total external memory access cost required to implement the predetermined schedule;

determining a first memory allocation for an on-chip memory of the SoC for the input FMs and the output FMs dependent upon the determined memory access amount information and a size of the on-chip memory of the SoC;

determining, dependent upon the determined memory access amount information and the first memory allocation determined for the on-chip memory of the SoC for each predetermined schedule of the plurality of predetermined schedules;

a predetermined schedule from the plurality of predetermined schedules which minimises the memory access amount information of the external memory access for the CNN layer of the CNN process executing on the multi-processing-unit SoC; and

a first memory allocation associated with the predetermined schedule; and

applying the predetermined schedule and the first memory allocation associated with the predetermined schedule to the CNN layer of the CNN process executing on the multi-processing-unit SoC.

13. A non-transitory computer readable medium comprising one or more memories storing executable computer readable code for directing one or more processors to configure a multi-processing-unit System-on-Chip (SoC) to execute a Convolutional Neural Network (CNN) process comprising a plurality of CNN layers, by performing a method comprising the steps of:

receiving a plurality of predetermined schedules each specifying an order of processing steps for processing input feature maps (input FMs) input to a CNN layer of the CNN process executing on the multi-processing-unit SoC and for processing output feature maps (output FMs) output from the CNN layer of the CNN process executing on the multi-processing-unit SoC, wherein processing input FMs and processing output FMs are performed by processing units of the multi-processing-unit SoC;

for each predetermined schedule of the plurality of predetermined schedules:

determining memory access amount information describing how many memory accesses are required to process the input FMs and the output FMs of the CNN layer of the CNN process executing on the multi-processing-unit SoC;

expressing the determined memory access amount information as one or more relationships describing an extent to which data can be reused by the processing steps of the predetermined schedule without requiring additional memory accesses;

combining the one or more relationships with a cost of writing to an external memory and a cost of reading from the external memory, to form memory access information describing a total external memory access cost required to implement the predetermined schedule;

determining a first memory allocation for an on-chip memory of the SoC for the input FMs and the output FMs dependent upon the determined memory access amount information and a size of the on-chip memory of the SoC;

determining, dependent upon the determined memory access amount information and the first memory allocation determined for the on-chip memory of the SoC for each predetermined schedule of the plurality of predetermined schedules;

a predetermined schedule from the plurality of predetermined schedules which minimises the memory access amount information of the external memory access for the CNN layer of the CNN process executing on the multi-processing-unit SoC; and

a first memory allocation associated with the predetermined schedule; and

applying the predetermined schedule and the first memory allocation associated with the predetermined schedule to the CNN layer of the CNN process executing on the multi-processing-unit SoC.

14. A method of configuring a memory for storing input and output feature maps for a layer of a Convolutional Neural Network (CNN) process executing on a multi-processing-unit System-on-Chip (SoC), the method comprising the steps of:

determining, for the layer of the CNN process executing on the multi-processing-unit SoC, a best schedule from a plurality of predetermined schedules, wherein each predetermined schedule of the plurality of predetermined schedules describes an order of processing input and output feature maps of the layer of the CNN process executing on the multi-processing-unit SoC, and wherein the best schedule is a predetermined schedule of the plurality of predetermined schedules with the lowest amount of external memory access for the layer of the CNN process executing on the multi-processing-unit SoC;

for each predetermined schedule of the plurality of predetermined schedules:

determining an estimation model for an amount of external memory access required to implement the predetermined schedule, wherein the determined estimation model for the amount of external memory access is based on weights for the input and output feature maps of the layer of the CNN process executing on the multi-processing-unit SoC, and the order of processing the input and output feature maps of the layer of the CNN process executing on the multi-processing-unit SoC; and

determining a memory allocation for the input and output feature maps of the layer of the CNN process executing on the multi-processing-unit SoC according to the determined estimation model for the amount of external memory access and a size of an on-chip memory of the multi-processing-unit SoC; and

applying the best schedule of the plurality of predetermined schedules to the layer of the CNN process executing on the multi-processing-unit SoC, wherein the best schedule of the plurality of predetermined schedules is selected according to the determined memory allocation for the input and output feature maps of the layer of the CNN process executing on the multi-processing-unit SoC.

15. An apparatus for configuring a memory for storing input and output feature maps for a layer of a Convolutional Neural Network (CNN) process executing on a multi-processing-unit System-on-Chip (SoC), the apparatus comprising:

a processor; and

a non-transitory computer readable medium storing a computer executable program for directing the processor to perform a method comprising the steps of:

determining, for the layer of the CNN process executing on the multi-processing-unit SoC, a best schedule from a plurality of predetermined schedules, wherein each predetermined schedule of the plurality of predetermined schedules describes an order of processing input and output feature maps of the layer of the CNN process executing on the multi-processing-unit SoC, and wherein the best schedule is a predetermined schedule of the plurality of predetermined schedules with the lowest amount of external memory access for the layer of the CNN process executing on the multi-processing-unit SoC;

for each predetermined schedule of the plurality of predetermined schedules:

determining an estimation model for an amount of external memory access required to implement the predetermined schedule, wherein the determined estimation model for the amount of external memory access is based on weights for the input and output feature maps of the layer of the CNN process executing on the multi-processing-unit SoC, and the order of processing the input and output feature maps of the layer of the CNN process executing on the multi-processing-unit SoC; and

determining a memory allocation for the input and output feature maps of the layer of the CNN process executing on the multi-processing-unit SoC according to the determined estimation model for the amount of external memory access and a size of an on-chip memory of the multi-processing-unit SoC; and

applying the best schedule of the plurality of predetermined schedules to the layer of the CNN process executing on the multi-processing-unit SoC, wherein the best schedule of the plurality of predetermined schedules is selected according to the determined memory allocation for the input and output feature maps of the layer of the CNN process executing on the multi-processing-unit SoC.

16. A non-transitory computer readable medium storing a computer executable program for directing a processor to perform a method for configuring a memory for storing input and output feature maps for a layer of a Convolutional Neural Network (CNN) process executing on a multi-processing-unit System-on-Chip (SoC), the method comprising the steps of:

determining, for the layer of the CNN process executing on the multi-processing-unit SoC, a best schedule from a plurality of predetermined schedules, wherein each predetermined schedule of the plurality of predetermined schedules describes an order of processing input and output feature maps of the layer of the CNN process executing on the multi-processing-unit SoC, and wherein the best schedule is a predetermined schedule of the plurality of predetermined schedules with the lowest amount of external memory access for the layer of the CNN process executing on the multi-processing-unit SoC;

for each predetermined schedule of the plurality of predetermined schedules:

determining an estimation model for an amount of external memory access required to implement the predetermined schedule, wherein the determined estimation model for the amount of external memory access is based on weights for the input and output feature maps of the layer of the CNN process executing on the multi-processing-unit SoC, and the order of processing the input and output feature maps of the layer of the CNN process executing on the multi-processing-unit SoC; and

determining a memory allocation for the input and output feature maps of the layer of the CNN process executing on the multi-processing-unit SoC according to the determined estimation model for the amount of external memory access and a size of an on-chip memory of the multi-processing-unit SoC; and

applying the best schedule of the plurality of predetermined schedules to the layer of the CNN process executing on the multi-processing-unit SoC, wherein the best schedule of the plurality of predetermined schedules is selected according to the determined memory allocation for the input and output feature maps of the layer of the CNN process executing on the multi-processing-unit SoC.