Programming a multi-processor system

Patent metadata

Field	Value
Publication number	US-9965258-B2
Application number	US-201514972815-A
Country	US
Kind code	B2
Filing date	Dec 17, 2015
Priority date	Mar 27, 2006
Publication date	May 8, 2018
Grant date	May 8, 2018

Abstract

A computer-implemented method for creating a program for a multi-processor system comprising a plurality of interspersed processors and memories. A user may specify or create source code using a programming language. The source code specifies a plurality of tasks and communication of data among the plurality of tasks. However, the source code may not (and preferably is not required to) 1) explicitly specify which physical processor will execute each task and 2) explicitly specify which communication mechanism to use among the plurality of tasks. The method then creates machine language instructions based on the source code, wherein the machine language instructions are designed to execute on the plurality of processors. Creation of the machine language instructions comprises assigning tasks for execution on respective processors and selecting communication mechanisms between the processors based on location of the respective processors and required data communication to satisfy system requirements.

First claim

The invention claimed is:

1. A computer-implemented method, comprising:
creating a program for a multi-processor system, wherein the multi-processor system comprises an array of processors and a plurality of memories coupled to the processors, wherein the plurality of memories are interspersed among the plurality of processors within an apparatus, wherein each of the processors is coupled to at least one other processor, and wherein the creating includes:
creating machine language instructions based on source code, wherein the machine language instructions are designed to execute on the array of processors, wherein the source code specifies first functionality, and wherein the source code specifies a plurality of tasks and communication of data among the plurality of tasks;
selecting communication mechanisms between tasks to perform at least a portion of the specified communication of data, wherein the communication mechanisms include shared local variables and message passing pathways, wherein the message passing pathways are via a plurality of communications units coupled to processors in the array of processors;
using dependency information to detect potential conflicts for communication resources between messages;
selecting or adjusting the message passing pathways to send potentially conflicting messages using different hardware routing resources, thereby avoiding conflicts for communication resources;
determining an assignment of tasks to respective processors in the multi-processor system based on the selected communication mechanisms, including assigning tasks that use one or more shared local variables to different first and second processors that neighbor a shared memory and are both configured to access the shared memory, wherein the shared memory is selected to store the one or more shared local variables; and
storing the machine language instructions in various ones of the plurality of memories, wherein the multi-processor system is operable to execute the machine language instructions using the local variables and the message passing pathways to implement the first functionality.

2. The computer-implemented method of claim 1 , further comprising:
selecting communication mechanisms between tasks to perform a second portion of the specified communication of data wherein the selecting for the second portion is performed based on locations of tasks associated with the second portion.

3. The computer-implemented method of claim 1 , further comprising synthesizing the message passing pathways between processors by binding communication requirements in the source code to routing logic.

4. The computer-implemented method of claim 1 , further comprising: allocating local variables to memories based on data size and resource availability within the memories.

5. The computer-implemented method of claim 1 , wherein each of the communication units comprises a memory and routing logic.

6. The computer-implemented method of claim 1 , wherein the determining an assignment of tasks includes assigning tasks that use common shared variables prior to allocating tasks that do not have common shared variables.

7. The computer-implemented method of claim 1 , wherein the source code specifies communication in symbolic form.

8. The computer-implemented method of claim 1 , further comprising:
generating a performance model for the multi-processor system based on locations of sending and receiving processing elements for the message passing pathways.

9. The computer-implemented method of claim 8 , further comprising:
adjusting the selection of communication mechanisms and the assignment of tasks based on the performance model and a parameter associated with at least one of: latency, throughput, or power consumption.

10. The computer-implemented method of claim 1 , wherein the determining the assignment of tasks further includes assigning tasks for serial execution to the same processing element.

11. A non-transitory computer readable memory medium comprising:
program instructions for creating a program for a multi-processor system, wherein the multi-processor system comprises an array of processors, wherein each of the processors is coupled to at least one other processor, wherein there are multiple communication mechanisms between the respective processors, wherein the program instructions are executable to:
create machine language instructions based on source code, wherein the machine language instructions are designed to execute on the array of processors, wherein the source code specifies first functionality, and wherein the source code specifies a plurality of tasks and communication of data among the plurality of tasks;
select communication mechanisms between tasks to perform at least a portion of the specified communication of data, wherein the communication mechanisms include shared local variables and message passing pathways, wherein the message passing pathways are via a plurality of communications units coupled to processors in the array of processors;
use dependency information to detect potential conflicts for communication resources between messages;
select or adjust the message passing pathways to send potentially conflicting messages using different hardware routing resources, thereby avoiding conflicts for communication resources;
determine an assignment of tasks to respective processors in the multi-processor system based on the selected communication mechanisms, including to assign tasks that use one or more shared local variables to different first and second processors that neighbor a shared memory and are both configured to access the shared memory, wherein the shared memory is selected to store the one or more shared local variables; and
store the machine language instructions in various ones of a plurality of memories of the multi-processor system, wherein the multi-processor system is operable to execute the machine language instructions using the local variables and the message passing pathways to implement the first functionality.

12. The non-transitory computer readable memory medium of claim 11 , wherein the program instructions are further executable to:
select communication mechanisms between tasks to perform a second portion of the specified communication of data, wherein the communication mechanisms include shared local variables and message passing pathways, and wherein the selection for the second portion is performed based on locations of tasks associated with the second portion.

13. The non-transitory computer readable memory medium of claim 11 , wherein the program instructions are further executable to:
synthesize the message passing pathways between processors by binding communication requirements in the source code to routing logic.

14. The non-transitory computer readable memory medium of claim 11 , wherein allocation of local variables to memories is based on data size and resource availability within the memories.

15. The non-transitory computer readable memory medium of claim 11 , wherein the determination of the assignment of tasks includes assigning tasks that use common shared variables prior to allocating tasks that do not have common shared variables.

16. The non-transitory computer readable memory medium of claim 11 , wherein the program instructions are further executable to:
generate a performance model for the multi-processor system based on locations of sending and receiving processing elements for the message passing pathways.

17. The non-transitory computer readable memory medium of claim 11 , wherein the determi

Assignees

• Coherent Logix Inc

Inventors

• Beardslee John Mark
• Doerr Michael B
• Eng Tommy K

Classifications

• G06F8/451 Primary

  Code distribution (considering CPU load at run-time G06F9/505; load rebalancing G06F9/5083) · CPC title

• G06F8/30

  Creation or generation of source code · CPC title

• G06F9/52

  Program synchronisation; Mutual exclusion, e.g. by means of semaphores · CPC title

• G06F9/54

  Interprogram communication · CPC title

• G06F9/546

  Message passing systems or structures, e.g. queues · CPC title