LINK-TIME RESOURCE ALLOCATION FOR A MULTI-THREADED PROCESSOR ARCHITECTURE

• US 20110131558A1
• Filed: 05/11/2009
• Published: 06/02/2011
• Est. Priority Date: 05/12/2008
• Status: Active Grant

• Current Assignee: XMOS Ltd.
• Original Assignee: XMOS Ltd.
• Inventors: Watt, Douglas, Osborne, Richard, Young, Martin
• Granted Patent: US 8,578,354 B2
• Time in Patent Office: Days
• US Class Current: 717/145
• CPC Class Codes: G06F 8/314 Parallel programming languages G06F8/313 takes precedence
• CPC Class Codes: G06F 8/54 Link editing before load time

Abstract

A method comprising: independently compiling a plurality of modules of source code to generate a plurality of respective object modules comprising a plurality of respective parallel threads explicitly designated by a user to be executed in parallel on a target platform; in each of the object modules, inserting at least one symbol indicative of a usage of a resource of the target platform associated with the respective thread; executing a linker to perform a linking process for linking the object modules, wherein the linking process comprises assessing the symbols in conjunction with one another, and based on the assessment generating an indication relating to a usage of the resource required for execution of the threads in parallel.

Claims

1. A method comprising:

independently compiling a plurality of modules of source code to generate a plurality of respective object modules comprising a plurality of respective parallel threads explicitly designated by a user to be executed in parallel on a target platform;

in each of the object modules, inserting at least one symbol indicative of a usage of a resource of the target platform associated with the respective thread;

executing a linker to perform a linking process for linking the object modules, wherein the linking process comprises assessing the symbols in conjunction with one another, and based on the assessment generating an indication relating to a usage of the resource required for execution of said threads in parallel.

2. The method of claim 1, wherein:

the target platform comprises an arrangement of interconnected processors;

said assessment comprises determining an allocation of the threads to different processors of the arrangement in dependence on the threads'"'"' associated resource usage, said indication comprising an indication of said allocation; and

the linking process comprises linking the object modules using said indication to generate a computer program in which said threads are to be executed in parallel on the allocated processors.

3. The method of claim 1, wherein said assessment comprises determining whether the total resource usage required by the threads exceeds a maximum limit, said indication comprising an indication of whether the total resource usage exceeds said limit.

4. The method of claim 3, wherein the method comprises halting the linking process on the condition that said indication indicates that the total usage does exceed the limit.

5. The method of claim 3, wherein said generation of the indication comprises generating an error message to a user.

6. The method of claim 3, wherein the method comprises, on the condition that said indication indicates that the total usage does exceed the limit:

modifying one or more of the modules of source code to avoid the exceeding of the limit;

re-compiling the one or more source code modules to re-generate the object modules; and

following the modification and re-compilation, re-executing the linker to link the object modules to generate a computer program in which said threads are to be executed in parallel.

7. The method of any of claims 3, wherein the maximum limit is the total available of the resource on the target platform.

8. The method of claim 1, wherein said insertion of a symbol indicative of a resource usage in each object module comprises inserting a symbol indicative of an amount of memory required by the respective thread, said indication comprising an indication relating to a memory usage required for execution of said threads in parallel.

9. The method of claim 1, wherein said insertion of a symbol indicative of a resource usage in each object module comprises inserting a symbol indicative of the number of ports required by the respective thread, said indication comprising an indication relating to a usage of ports required for execution of said threads in parallel.

10. The method of claim 1, wherein said insertion of a symbol indicative of a resource usage in each object module comprises inserting a symbol indicative of the number of timers required by the respective thread, said indication comprising an indication relating to a usage of timers required for execution of said threads in parallel.

11. The method of claim 1, wherein and said insertion of a symbol indicative of a resource usage in each object module comprises inserting a symbol indicative of a number of channel ends required by the respective thread, the channel ends being a resource of the target platform for communicating between threads, and said indication comprising an indication relating to a usage of channel ends required for execution of said threads in parallel.

12. The method of claim 1, wherein and said insertion of a symbol indicative of a resource usage in each object module comprises inserting a symbol indicative of a number of parallel threads of other object modules whose execution is to be initiated by a procedure of the respective thread, and said indication comprising an indication of a number of threads required to be executed in parallel as a result of that procedure.

13. The method of claim 1, wherein said assessment comprises determining an allocation of an amount of the resource for execution of the threads in parallel, said indication comprising an indication of the allocated amount;

and

the linking process comprises linking the object files using said indication to generate a computer program in which said threads are to be executed in parallel using the allocated amount of the resource.

14. The method of claim 13, wherein said insertion of a symbol indicative of a resource usage in each object module comprises inserting a symbol indicative of a stack requirement for the respective thread, said indication comprising an indication relating to a stack allocation for execution of said threads in parallel.

15. The method of claim 14, wherein the stack allocation comprises a stack size.

16. The method of claim 14, wherein the stack allocation comprises a stack offset.

17. The method of claim 1, wherein:

said insertion of a symbol in at least one of the object modules comprises defining that symbol as an expression by including in the object module an indication of an operation and at least one operand; and

said assessment comprises evaluating the expression to determine the resource usage required by execution of the threads in parallel.

18. The method of claim 17, wherein one or more of said operands comprises an indication of another symbol of another object module, thus defining the symbol as a function of those one or more other symbols.

19. The method of claim 18, wherein the expression comprises an expression to determine the sum of the resources required by the parallel threads.

20. The method of claim 18, wherein the expression comprises an expression to determine the maximum of the resources required by two or more of the respective threads.

21. The method of claim 3 or any claim dependent thereon, wherein the method comprises:

in at least one of the object modules, inserting an error message associated with the respective symbol; and

outputting the error message to a user on the condition of finding that the total usage exceeds said limit.

22. The method of claim 21, wherein the error message is inserted as a string associated with the respective symbol.

23. The method of claim 1, wherein the threads are explicitly designated in one or more of the source code modules to be executed in parallel.

24. The method of claim 1, wherein each of said threads comprises at least one procedure and at least one of said threads comprises a plurality of procedures, wherein said insertion of a symbol in each object module indicative of a resource usage required by the respective thread comprises inserting a symbol indicative of a resource usage required by a procedure of the respective thread, and said assessment comprises determining whether the total resource usage required by parallel execution of procedures exceeds a maximum limit.

25. A tool-chain comprising:

first code for individually compiling and assembling a plurality of modules of source code, wherein the first code comprises code which when executed on a computer will generate a plurality of respective object modules comprising a plurality of respective threads, and insert in each of the object modules at least one symbol indicative of a usage of a resource of the target platform associated with the respective thread, the threads being explicitly designated by a user to be executed in parallel on a target platform;

second code for linking the object modules, the second code comprising code which when executed on a computer will assess the symbols in conjunction with one another, and based on the assessment generate an indication relating to a usage of the resource required by execution of said threads in parallel.

26. The tool-chain of claim 25, wherein:

the target platform comprises an arrangement of interconnected processors;

said assessment comprises determining an allocation of the threads to different processors of the arrangement in dependence on the threads'"'"' associated resource usage, said indication comprising an indication of said allocation; and

the linking process comprises linking the object modules using said indication to generate a computer program in which said threads are to be executed in parallel on the allocated processors.

27. The tool-chain of claim 25, wherein said assessment comprises determining whether the total resource usage required by the threads exceeds a maximum limit, said indication comprising an indication of whether the total resource usage exceeds said limit.

28. The tool-chain of claim 27, wherein the second code comprises code which when executed on a computer will halt the linking process on the condition that said indication indicates that the total usage does exceed the limit.

29. The tool-chain of claim 27, wherein said generation of the indication comprises generating an error message to a user.

30. The tool-chain of claim 27, wherein the second code comprises code for, on the condition that said indication indicates that the total usage does exceed the limit:

following the modification of one or more of the modules of source code to avoid the exceeding of the limit and re-compilation of the one or more source code modules to re-generate the object modules, linking the object modules to generate a computer program in which said threads are to be executed in parallel.

31. The tool-chain of claim 27, wherein the maximum limit is the total available of the resource on the target platform.

32. The tool-chain of claim 25, wherein said insertion of a symbol indicative of a resource usage in each object module comprises inserting a symbol indicative of an amount of memory required by the respective thread, said indication comprising an indication relating to a memory usage required for execution of said threads in parallel.

33. The tool-chain of claim 25, wherein said insertion of a symbol indicative of a resource usage in each object module comprises inserting a symbol indicative of the number of ports required by the respective thread, said indication comprising an indication relating to a usage of ports required for execution of said threads in parallel.

34. The tool-chain of claim 25, wherein said insertion of a symbol indicative of a resource usage in each object module comprises inserting a symbol indicative of the number of timers required by the respective thread, said indication comprising an indication relating to a usage of timers required for execution of said threads in parallel.

35. The tool-chain of claim 25, wherein and said insertion of a symbol indicative of a resource usage in each object module comprises inserting a symbol indicative of a number of channel ends required by the respective thread, the channel ends being a resource of the target platform for communicating between threads, and said indication comprising an indication relating to a usage of channel ends required for execution of said threads in parallel.

36. The tool-chain of claim 25, wherein and said insertion of a symbol indicative of a resource usage in each object module comprises inserting a symbol indicative of a number of parallel threads of other object modules whose execution is to be initiated by a procedure of the respective thread, and said indication comprising an indication of a number of threads required to be executed in parallel as a result of that procedure.

37. The tool-chain of claim 25, wherein said assessment comprises determining an allocation of an amount of the resource for execution of the threads in parallel, said indication comprising an indication of the allocated amount;

and

the second code comprises code which when executed on a computer will link the object files using said indication to generate a computer program in which said threads are to be executed in parallel using the allocated amount of the resource.

38. The tool-chain of claim 37, wherein said insertion of a symbol indicative of a resource usage in each object module comprises inserting a symbol indicative of a stack requirement for the respective thread, said indication comprising an indication relating to a stack allocation for execution of said threads in parallel.

39. The tool-chain of claim 38, wherein the stack allocation comprises a stack size.

40. The tool-chain of claim 38, wherein the stack allocation comprises a stack offset.

41. The tool-chain of claim 25, wherein:

said insertion of a symbol in at least one of the object modules comprises defining that symbol as an expression by including in the object module an indication of an operation and at least one operand; and

said assessment comprises evaluating the expression to determine the resource usage required by execution of the threads in parallel.

42. The tool-chain of claim 41, wherein one or more of said operands comprises an indication of another symbol of another object module, thus defining the symbol as a function of those one or more other symbols.

43. The tool-chain of claim 42, wherein the expression comprises an expression to determine the sum of the resources required by the parallel threads.

44. The tool-chain of claim 42, wherein the expression comprises an expression to determine the maximum of the resources required by two or more of the respective threads.

45. The tool-chain of claim 27 or any claim dependent thereon, wherein:

the first code comprises code which when executed on a computer will insert an error message associated with the respective symbol in at least one of the object modules; and

the second code comprises code which when executed on a computer will output the error message to a user on the condition of finding that the total usage exceeds said limit.

46. The tool-chain of claim 45, wherein the error message is inserted as a string associated with the respective symbol.

47. The tool-chain of claim 25, wherein the threads are explicitly designated in one or more of the source code modules to be executed in parallel.

48. The tool-chain of claim 25, wherein each of said threads comprises at least one procedure and at least one of said threads comprises a plurality of procedures, wherein said insertion of a symbol in each object module indicative of a resource usage required by the respective thread comprises inserting a symbol indicative of a resource usage required by a procedure of the respective thread, and said assessment comprises determining whether the total resource usage required by parallel execution of procedures exceeds a maximum limit.

49. A compiler and assembler product for individually compiling and assembling a plurality of modules of source code, wherein the product comprises code which when executed on a computer performs the steps of:

generating a plurality of respective object modules comprising a plurality of respective threads explicitly designated by a user to be executed in parallel on a target platform; and

in the compilation of each object modules, inserting at least one symbol for use by a linker indicative of a usage of a resource of the target platform associated with the respective thread.

50. A linker for linking a plurality of object modules comprising a plurality of respective threads explicitly designated by a user to be executed in parallel, each object module comprising at least one symbol indicative of a usage of a resource of the target platform associated with the respective thread, wherein the linker comprises code which when executed on a computer performs the steps of:

assessing the symbols in conjunction with one another, and based on the assessment generating an indication relating to a usage of the resource required by execution of said threads in parallel; and

linking the object modules to generate a computer program in which said threads are to be executed in parallel.