Method for determining by optimization a multi-core architecture

Patent metadata

Field	Value
Publication number	US-9594863-B2
Application number	US-201514841782-A
Country	US
Kind code	B2
Filing date	Sep 1, 2015
Priority date	Sep 2, 2014
Publication date	Mar 14, 2017
Grant date	Mar 14, 2017

Abstract

The invention relates to a method for determining by optimization a multi-core architecture and a way of implementing an application on the architecture for a given application, the method comprising:
providing a parallelized application and candidate architectures comprising different hardware blocks, defining a first exploration space whose elements are the different ways of implementing the application on each of the candidate architectures, selecting, in the first exploration space, the elements verifying a criterion to obtain a second exploration space, determining, in the second exploration space, the elements verifying a criterion to obtain a third exploration space, computing the number of data exchanged between the hardware blocks for each of the elements of the third exploration space to obtain a fourth exploration space, and optimizing the elements of the fourth exploration space according to a criterion.

First claim

The invention claimed is:

1. A method for determining by optimization a multi-core architecture and a way of implementing an application on the architecture for a given application, the method comprising:
providing a parallelized application, a parallelized application being a set of tasks,
providing candidate architectures, each candidate architecture comprising different hardware blocks, a hardware block having a specific nature and being able to execute one or more tasks,
defining a first exploration space whose elements are the different ways of implementing the application on each of the candidate architectures,
selecting, in the first exploration space, the elements verifying a first criterion according to which each task of the application is suitable for being implemented on only one or several hardware blocks, to obtain a second exploration space comprising the elements of the first exploration space meeting the first criterion,
determining, in the second exploration space, the elements verifying a second criterion, the second criterion being different from the first criterion and requiring that the number of hardware blocks separating a first hardware block implementing a first task and a second hardware block implementing a second task different from the first task, is less than or equal to a value specific to the two tasks in question, to obtain a third exploration space comprising the elements of the second exploration space meeting the second criterion,
computing the number of data exchanged between the hardware blocks for each of the elements of the third exploration space and comparing each computed number to a threshold value, in order to obtain a fourth exploration space comprising the elements of the third exploration space whose number of exchanged data is less than or equal to the threshold value, and
optimizing the elements of the fourth exploration space according to a third criterion, the third criterion being different from the first criterion and from the second criterion.

2. The method according to claim 1 , wherein the selection step comprises the parsimonious decomposition of the elements of the first exploration space into a dictionary, the dictionary being a matrix whose elements meet the first criterion, the elements resulting from the parsimonious decomposition belonging to the second exploration space.

3. The method according to claim 1 , wherein the method further comprises the following steps:
determining, in the application, the tasks that can be performed at the same time by two separate hardware blocks of a same candidate architecture to obtain a diagram grouping all of the tasks performable in parallel,
evaluating the needs necessary to implement each of the tasks of the application on specific hardware blocks of the candidate architectures in order to obtain a table grouping the needs of each of the tasks of the application when the considered tasks are performed on said hardware blocks,
optimizing the application based on the table and the diagram to reduce the volume of the tasks or the volume of the data transferred between the tasks of the application.

4. The method according to claim 3 , wherein the first criterion is defined by a user based on the table and based on constraints specific to the candidate architectures and the application.

5. The method according to claim 1 , wherein the method further comprises the following steps:
storing, in a fifth exploration space, the elements of the first exploration space which does not meet the first criterion,
storing, in a sixth exploration space, the elements of the second exploration space which does not meet the second criterion,
the selection step further comprising the addition of the elements of the fifth exploration space into the second exploration space and the determining step further comprising the addition of the elements of the sixth exploration space into the third exploration space, the storage steps being carried out during the method only when the optimization of the elements of the fourth exploration space does not meet the third criterion.

6. The method according to claim 1 , wherein the threshold value of the computation step is below the constraints in terms of execution time of the user.

7. The method according to claim 1 , wherein the third criterion is defined by a function whose parameters comprise the size of the architecture, the number of data transferred between the different blocks of an architecture, the bandwidth and the size of the memories of the architecture, the bandwidth of the communicators of the architecture, the computing power of the different hardware blocks and the placement of the data and of the tasks).

8. The method according to claim 1 , wherein the natures of the hardware blocks are chosen from among processors, memories and communicators, the hardware blocks making up the candidate architectures having previously been optimized for one or more functionalities or specific tasks.

9. The method according to claim 1 , wherein the optimization step according to the third user criterion implements at least one evolutionary search algorithm, such as a genetic algorithm or a taboo search algorithm.

10. A non-transitory computer-readable storage medium including a computer program being able to be loaded on a data processing unit and determining by optimization a multi-core architecture and a way of implementing an application on the architecture for a given application, comprising:
an instruction for providing a parallelized application, a parallelized application being a set of tasks,
an instruction for providing candidate architectures, each candidate architecture comprising different hardware blocks, a hardware block having a specific nature and being able to execute one or more tasks,
an instruction for defining a first exploration space whose elements are the different ways of implementing the application on each of the candidate architectures,
an instruction for selecting, in the first exploration space, the elements verifying a first criterion according to which each task of the application is suitable for being implemented on only one or several hardware blocks, to obtain a second exploration space comprising the elements of the first exploration space meeting the first criterion,
an instruction for determining, in the second exploration space, the elements verifying a second criterion, the second criterion being different from the first criterion and requiring that the number of hardware blocks separating a first hardware block implementing a first task and a second hardware block implementing a second task different from the first task, is less than or equal to a value specific to the two tasks in question, to obtain a third exploration space comprising the elements of the second exploration space meeting the second criterion,
an instruction for computing the number of data exchanged between the hardware blocks for each of the elements of the third exploration space and comparing each computed number to a threshold value, in order to obtain a fourth exploration space comprising the elements of the third exploration space whose number of exchanged data is less than or equal to the threshold value, and
an instruction for optimizing the elements of the fourth exploration space according to a third criterion, the third criterion being different from the first criterion and from the second criterion.

Assignees

• Thales Sa
• Univ Nantes

Inventors

• Brillu Romain
• Millet Philippe
• Pillement Sébastien
• Lemonnier Fabrice

Classifications

• G06F30/34

  for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD] · CPC title

• G06F30/20

  Design optimisation, verification or simulation (optimisation, verification or simulation of circuit designs G06F30/30) · CPC title

• G06F30/30

  Circuit design · CPC title

• G06F9/5066 Primary

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title

• G06F17/5068 Primary

  Physics · mapped topic