Method for mapping applications on a multiprocessor platform/system

Abstract

In one aspect, there is a formalized method for mapping applications on a multiprocessor system. In particular re-use possibilities are explored, e.g. focus on data transfer and memory access issues, with the aim of obtaining low-power and low-energy mappings and/or to overcome memory performance or energy bottlenecks.

What is claimed is: 
     
       1. A method of determining an optimal mapping of application code, enabling efficient execution of the code on a digital system comprising a plurality of computation units and a plurality of memories arranged in a hierarchy connected by a network, the method comprising:
 loading a representation of application code, describing the functionality of the application, wherein the code comprises data access instructions on array signals, the representation of the code being partitioned in a plurality of code threads and the representation comprising information on data access dependencies between the code threads; 
 determining for at least one array signal and for at least one data access instruction on the array signal a graph having a plurality of data groupings, the data groupings comprising portions of the array signals that are copied from one layer of memory to a lower layer of memory within the hierarchy of memories, the one layer of memory consumes more power than the lower layer of memory, and the graph indicating for each data grouping of the plurality of data groupings, whether the data grouping is assignable to more than one of the code threads; 
 evaluating combinations of the data groupings using an evaluation criterion; and 
 selecting the combination of the data groupings with an optimum evaluation criterion within a pre-determined tolerance, and 
 wherein the selection defines the optimal mapping of data groupings within the hierarchy of memories, the selection is based on a tradeoff between size of a data grouping and energy costs for copying the data grouping from one layer of memory to a lower layer of memory, while taking into account inter-thread data access dependencies and cost of inter-thread synchronization when a data grouping is assignable to more than one of the code threads, the selection resulting in a memory reuse that reduces power consumption of the digital system. 
 
     
     
       2. The method of  claim 1 , wherein the evaluation criterion comprises energy consumption for executing data accesses to the memories. 
     
     
       3. The method of  claim 1 , wherein the evaluation criterion comprises energy consumption of data transfers needed for inter-thread synchronization. 
     
     
       4. The method of  claim 1 , wherein the hierarchy of memories comprise a set of first memories, each of the first memories assigned to a computation unit, and at least one second memory, assigned to at least two of the computation units, the data accesses comprising data transfers between the first memories and the computation units and data transfers between the first memories and the second memory, wherein the set of first memories and the second memory are at different memory layers within the memory hierarchy, wherein each of the set of first memories is smaller than the second memory, and wherein the second memory is functionally more distant from the processor than the set of first memories and consumes more power than each of the first set of memories. 
     
     
       5. The method of  claim 1 , wherein the selecting comprises performing life-time analysis of the arrays taking into account accesses on the array by at least two of the threads. 
     
     
       6. The method of  claim 1 , wherein the selecting comprises performing an array-level dependency analysis. 
     
     
       7. The method of  claim 1 , wherein the representation comprises a geometric model. 
     
     
       8. The method of  claim 1 , wherein the determining comprises determining at least two data grouping access timing possibilities to the data groupings within the hierarchy of memories, wherein the evaluating comprises evaluating the data access timing possibilities and the selecting comprises selecting one of the data grouping access timing possibilities. 
     
     
       9. The method of  claim 8 , wherein the data access timing possibilities comprise at least one timing before the data access is required by a code thread. 
     
     
       10. A method of modifying application code enabling efficient execution of the code on an essentially digital system comprising a plurality of computation units and a plurality of memories arranged in a hierarchy, connected by a network, the method comprising:
 applying the method of  claim 1 ; and 
 modifying the application code based on the selected combination of the data groupings within the hierarchy of memories such that the modified application code comprises data accesses to the selected data groupings within the hierarchy of memories while preventing occurrence of violations of the data access dependencies between the code threads in case the data groupings within the hierarchy of memories are assignable to more than one code thread. 
 
     
     
       11. The method of  claim 10 , wherein the preventing of occurrence of data access dependency violations is performed by providing synchronization instructions within the modified code. 
     
     
       12. The method of  claim 10 , wherein the modifying of the code comprises imposing the data accesses to the data groupings within the hierarchy of memories at a selected data access timing. 
     
     
       13. A non-transitory computer-readable medium having stored therein a computer program which, when executed on a processor, performs the method of  claim 10 . 
     
     
       14. A non-transitory computer-readable medium having stored therein a computer program which, when executed on a processor, performs the method of  claim 1 . 
     
     
       15. An automated code mapping system for determining an optimal mapping of application code, enabling efficient execution of the code on a digital system comprising a plurality of computation units and a plurality of memories arranged in a hierarchy connected by a network, the automated code mapping system comprising:
 a memory module configured to store a representation of application code, describing the functionality of the application, wherein the code comprises data access instructions on array signals, the representation of the code being partitioned in a plurality of code threads and the representation comprising information on data access dependencies between the code threads; 
 a first computing device configured to determine for at least one array signal and for at least one data access instruction on the array signal a graph having a plurality of data groupings, the data groupings comprising portions of the array signals that are copied from one layer of memory to a lower layer of memory within the hierarchy of memories, the one layer of memory consumes more power than the lower layer of memory, and the graph indicating, for each data grouping of the plurality of data groupings, whether the data grouping is assignable to more than one of the code threads; 
 a second computing device configured to evaluate combinations of the data groupings within the hierarchy of memories using an evaluation criterion; and 
 a third computing device configured to select the combination of the data groupings within the hierarchy of memories with an optimum evaluation criterion within a pre-determined tolerance, wherein the selection defines the optimal mapping of data groupings within the hierarchy of memories, the selection is based on a tradeoff between size of a data grouping and energy costs for copying the data grouping from one layer of memory to a lower layer of memory, while taking into account inter-thread data access dependencies and cost of inter-thread synchronization when a data grouping is assignable to more than one of the code threads, the selection resulting in memory reuse that reduces power consumption of the digital system. 
 
     
     
       16. The automated code mapping system of  claim 15 , wherein the hierarchy of memories comprise a set of first memories, each of the first memories assigned to a computation unit, and at least one second memory, assigned to at least two of the computation units, the data accesses comprising data transfers between the first memories and the computation units and data transfers between the first memories and the second memory, wherein the set of first memories and the second memory are at different memory layers within the memory hierarchy, wherein each of the set of first memories is smaller than the second memory, and wherein the second memory is functionally more distant from the processor than the set of first memories and consumes more power than each of the first set of memories. 
     
     
       17. An automated code modification system for modifying application code enabling efficient execution of the code on an essentially digital system comprising a plurality of computation units and a plurality of memories arranged in a hierarchy, connected by a network, the automated code modification system comprising:
 a memory module configured to store a representation of application code, describing the functionality of the application, wherein the code comprises data access instructions on array signals, the representation of the code being partitioned in a plurality of code threads and the representation comprising information on data access dependencies between the code threads; 
 a first computation device configured to determine for at least one array signal and for at least one data access instruction on the array signal a graph having a plurality of data groupings, the data groupings comprising portions of the array signals that are copied from one layer of memory to a lower layer of memory within the hierarchy of memories, the one layer of memory consumes more power than the lower layer of memory, and the graph indicating, for each data grouping of the plurality of data groupings, whether the data grouping is assignable to more than one of the code threads; 
 a second computation device configured to evaluate combinations of the data groupings using an evaluation criterion; 
 a third computation device configured to select the combination of the data groupings within the hierarchy of memories with an optimum evaluation criterion within a pre-determined tolerance, wherein the selection defines an optimal mapping of data groupings within the hierarchy of memories, the selection is based on a tradeoff between size of a data grouping and energy costs for copying the data grouping from one layer of memory to a lower layer of memory, while taking into account inter-thread data access dependencies and cost of inter-thread synchronization when a data grouping is assignable to more than one of the code threads, the selection resulting in memory reuse that reduces power consumption of the digital system, and 
 a programming device configured to modify the application code based on the selected combination of the data groupings within the hierarchy of memories such that the modified application code comprises data accesses to the selected data groupings while preventing occurrence of violations of the data access dependencies between the code threads in case the data groupings within the hierarchy of memories are assignable to more than one code thread.