PROGRAMMING A MULTI-PROCESSOR SYSTEM

• US 20070226686A1
• Filed: 03/27/2007
• Published: 09/27/2007
• Est. Priority Date: 03/27/2006
• Status: Active Grant

• Current Assignee: Coherent Logix, Incorporated
• Original Assignee: Coherent Logix, Incorporated
• Inventors: Beardslee, John, Doerr, Michael, Eng, Tommy
• Granted Patent: US 8,826,228 B2
• Time in Patent Office: Days
• US Class Current: 717/109
• CPC Class Codes: G06F 8/30 Creation or generation of source code
• CPC Class Codes: G06F 8/41 Compilation
• CPC Class Codes: G06F 8/451 Code distribution considering CPU load at run-time G06F9/505; load rebalancing G06F9/5083
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/54 Interprogram communication
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

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.

Claims

1. A computer-implemented method for creating a program for a multi-processor system, wherein the multi-processor system comprises a plurality of processors and a plurality of memories coupled to the processors, wherein each of the processors is coupled to at least one other processor, wherein there are multiple communication mechanisms between the respective processors, the method comprising:

storing source code in response to user input, wherein the source code specifies first functionality, wherein the source code is intended to execute on the multi-processor system, wherein the source code specifies a plurality of tasks and communication of data among the plurality of tasks, wherein the source code further does not specify which communication mechanism to use among the plurality of tasks;

creating machine language instructions based on the source code, wherein the machine language instructions are designed to execute on the plurality of processors,

selecting communication mechanisms between the processors based on location of the respective processors and required communication of data;

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 selected communication mechanisms to implement the first functionality.

2. The method of claim 1

wherein the communication mechanisms comprise messages passed between respective ones of the processors and shared variables between respective ones of the processors;

wherein said selecting communication mechanisms between the processors comprises selecting one of shared variables or message passing.

3. The method of claim 1, further comprising:

the method further comprising allocating local variables to memories proximate to the processors executing tasks that own the local variables.

4. The method of claim 3,

wherein said allocating local variables to memories is performed based on data size and resource availability within the memories.

5. The method of claim 1,

wherein the multi-processor system comprises a plurality of communication units coupled to the processors, wherein each of the communication units comprises a memory and routing logic;

the method further comprising allocating local variables to memories in respective communication units proximate to the processors executing tasks that own the local variables;

wherein said allocating local variables is performed based on data size and resource availability within the communication units.

6. The method of claim 1,

wherein said selecting communication mechanisms between the processors comprises selecting shared variables for at least a subset of the tasks;

the method further comprising allocating tasks using common shared variables to neighboring processors which share access to the same memories.

7. The method of claim 1, further comprising:

allocating tasks using common shared variables prior to allocating tasks that do not have common shared variables.

8. The method of claim 1, further comprising:

creating a performance model based on the source code, wherein the performance model is designed to optimize for one or more of latency, throughput, and power;

wherein said selecting communication mechanisms between the tasks or processors comprises selecting communication mechanisms based on the performance model.

9. The method of claim 1, further comprising:

for each of one or more respective communications, determining a data location of sending and receiving blocks of the respective communication;

creating a performance model for the respective communication;

wherein said selecting communication mechanisms between the tasks or processors comprises selecting communication mechanisms based on the performance model.

10. The method of claim 1, wherein the source code specifies communication in symbolic form.

11. The method of claim 1,

wherein the source code specifies a first message, at least one message send command for the first message, at least one message receive command for the first message, source information for the first message, and destination information for the first message;

wherein the source information and the destination information are expressed in symbolic terms, wherein the source information and the destination information do not specify a location of a processor to execute the at least one message send command and the at least one message receive command;

the method further comprising allocating tasks sending and/or receiving messages to specific processors.

12. The method of claim 1,

wherein the multi-processor system comprises a plurality of memory units coupled to the processors, wherein each of the memory units comprises a memory and routing logic;

the method further comprising synthesizing communication links between processors by binding communication requirements in the source code to the routing logic.

13. The method of claim 12,

wherein said binding is performed based on maximum utilization of available routing resources to minimize performance-robbing communication congestion and collision and to reduce the potential of fatal communication deadlocks.

14. The method of claim 1, further comprising:

creating a communication dependency graph for all communication channels supporting multiple message passing;

determining if a dependency exists between communications using the same channel;

if a dependency exists between communications using the same channel, automatically reassigning the routing channel so that conflicting communications occur on different physical routes.

15. The method of claim 14, further comprising:

if re-assignment is not feasible, automatically explicitly scheduling the communication channel to prevent a deadlock from occurring.

16. The method of claim 1,

wherein said creating machine language instructions comprises breaking up the source code into multiple conventional serial programs for each processor in the multi-processor system;

and

executing conventional compilers designed for single processor systems to compile each of the multiple conventional serial programs.

17. The method of claim 1, further comprising:

the multi-processor system executing the machine language instructions using the selected communication mechanisms to implement the first functionality; and

displaying a graphical user interface that visually depicts the multiprocessor system, wherein the graphical user interface is updated during said executing to visually indicate operations being performed.

18. The method of claim 17,

wherein the graphical user interface visually depicts at least a subset of the plurality of processors and at least a subset of the plurality of memories;

wherein said displaying the graphical user interface comprises displaying a visual indication on respective processors to indicate the state of the respective processors.

19. The method of claim 18,

wherein the visual indication comprises color.

20. The method of claim 18,

wherein the state of the respective processors comprises one or more of not started, running, stopped, stalled and waiting.

21. The method of claim 18,

wherein said displaying the graphical user interface comprises displaying respective tasks executing in the multi-processor system.

22. The method of claim 21,

wherein a plurality of tasks are assigned to run on a first processor;

wherein each of the plurality of tasks is iconically illustrated on the graphical user interface;

wherein said displaying the graphical user interface comprises displaying a visual indication on a respective task icon which indicates which task of the plurality of tasks is being executed.

23. The method of claim 18,

wherein said displaying the graphical user interface comprises displaying synchronization behavior of tasks executing on the plurality of processors.

24. The method of claim 18,

wherein said displaying the graphical user interface comprises displaying stalling behavior of tasks executing on the plurality of processors.

25. The method of claim 18,

wherein said displaying the graphical user interface comprises displaying a visual indication indicating severity of routing resource conflicts in the multi-processors system.

26. A memory medium comprising program instructions for creating a program for a multi-processor system, wherein the multi-processor system comprises a plurality 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:

access source code from memory, wherein the source code specifies first functionality, wherein the source code is intended to execute on the multi-processor system, wherein the source code specifies a plurality of tasks and communication of data among the plurality of tasks, wherein the source code does not explicitly specify which physical processor executes each task, and wherein the source code further does not specify which communication mechanism to use among the plurality of tasks;

create machine language instructions based on the source code, wherein the machine language instructions are designed to execute on the plurality of processors,

assign tasks for execution on respective processors, wherein said assigning comprises storing machine code associated with the tasks on memories connected to the respective processors that will execute the tasks;

select communication mechanisms between the processors based on location of the respective processors and required communication of data;

wherein the machine language instructions are executable on the multi-processor system to implement the first functionality.