Method for mapping applications on a multiprocessor platform/system

• US 20070174829A1
• Filed: 07/14/2006
• Published: 07/26/2007
• Est. Priority Date: 07/15/2005
• Status: Active Grant

• Current Assignee: IMEC International
• Original Assignee: Interuniversitair Micro-Electronica Centrum VZW (IMEC International)
• Inventors: Brockmeyer, Erik, Achteren, Tanja
• Granted Patent: US 8,473,934 B2
• Time in Patent Office: Days
• US Class Current: 717/151
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
• CPC Class Codes: G06F 8/453 Data distribution

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.

Claims

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 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 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 and indicating whether the data grouping is assignable to either one or more of the code threads;

evaluating for combinations of the data groupings an evaluation criterion; and

selecting the combination of the data groupings with an optimum evaluation criterion within a pre-determined tolerance, while taking into account the data dependencies when the data groupings are assignable to more than one code thread, the selection defining the optimal mapping.

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 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.

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, 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, 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 such that the modified application code comprises data accesses to the selected data groupings while preventing occurrence of data dependency violations in case the data groupings are assignable to more than one code thread.

11. The method of claim 10, wherein the preventing of occurrence of data 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 at the selected data access timing.

13. A computer program product configured to perform the method of claim 1 in the form of an executable computer program and stored on a computer readable medium.

17. A computer program product configured to perform the method of claim 10 in the form of an executable computer program and stored on a computer readable medium.

14. 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 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 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 and indicating whether the data grouping is assignable to either one or more of the code threads;

a second computing device configured to evaluate for combinations of the data groupings an evaluation criterion; and

a third computing device configured to select the combination of the data groupings with an optimum evaluation criterion within a pre-determined tolerance, while taking into account the data dependencies when the data groupings are assignable to more than one code thread, the selection defining the optimal mapping.

15. The automated code mapping system of claim 14, wherein the 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.

16. 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, 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 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 and indicating whether the data grouping is assignable to either one or more of the code threads;

a second computation device configured to evaluate for combinations of the data groupings an evaluation criterion;

a third computation device configured to select the combination of the data groupings with an optimum evaluation criterion within a pre-determined tolerance, while taking into account the data dependencies when the data groupings are assignable to more than one code thread, the selection defining the optimal mapping, and

a programming device configured to modify the application code based on the selected combination of the data groupings such that the modified application code comprises data accesses to the selected data groupings while preventing occurrence of data dependency violations in case the data groupings are assignable to more than one code thread.