System and method for preparing software for execution in a dynamically configurable hardware environment

• US 7,249,351 B1
• Filed: 08/30/2000
• Issued: 07/24/2007
• Est. Priority Date: 08/30/2000
• Status: Expired due to Term

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: French, Robert S., Eslick, Ian S., Songer, Christopher
• Primary Examiner(s): Vu; Tuan A
• Application Number:
  US09/651,425
• Time in Patent Office: 2,519 Days
• Field of Search: 712 10- 20, 712/4, 712 34- 43, 712203-241, 709311-327, 709/102, 709/246, 709/201, 709/1, 717106-108, 717127-135, 717/138, 717/140, 717/144, 717150-161, 717/153, 703 13- 27, 703/28, 703/100, 714 33- 47, 711/202, 711/219, 716/5, 716/7, 716 16- 17, 716/18, 716/1, 716/4, 718/105
• US Class Current: 717/158
• CPC Class Codes: G06F 8/451 Code distribution considering CPU load at run-time G06F9/505; load rebalancing G06F9/5083

Abstract

A system and method for creating run time executables in a configurable processing element array is disclosed. This system and method includes the step of partitioning a processing element array into a number of defined sets of hardware accelerators, which in one embodiment are processing elements called “bins”. The system and method then involves decomposing a program description in object code form into a plurality of “kernel sections”, where the kernel sections are defined as those sections of object code which are candidates for hardware acceleration. Next, mapping the identified kernel sections into a number of hardware dependent designs is performed. Finally, a matrix of the bins and the designs is formed for use by the run time system.

Claims

1. A method of creating run time executable code for a processing element array, the method comprising:

partitioning the processing element array into a plurality of hardware accelerators;

identifying a plurality of functions in a program source code based on one or more run-time attributes of the plurality of functions;

separating the identified plurality of functions from the program source code in a plurality of kernel sections;

producing the run time executable code including a plurality of hardware dependent executable code portions that correspond, respectively, with the identified plurality of functions;

mapping said plurality of hardware dependent executable code portions to the plurality of hardware accelerators;

identifying a plurality of hardware variants in the mapped plurality of hardware dependent executable code portions, wherein at least two of the hardware variants have different hardware configurations that are substantially functionally equivalent;

producing a matrix that defines different combinations of said plurality of hardware accelerators, said hardware variants and said hardware dependent executable code portions; and

referencing the mapped plurality of hardware executable code portions using the matrix during run time execution of the plurality of hardware executable code portions.

2. The method of claim 1, wherein said partitioning includes partitioning into digital signal processors.

3. The method of claim 1, wherein said partitioning includes partitioning into bins.

4. The method of claim 1, wherein said mapping includes mapping into multiple hardware contexts.

5. The method of claim 4, wherein said mapping into multiple hardware contexts includes mapping a first set of variants.

6. The method of claim 5, wherein said first set of variants are produced based upon resource usage.

7. The method of claim 5, wherein said mapping includes mapping a second set of variants configured to support multiple hardware configurations of one of a plurality of bins.

8. The method of claim 1, wherein said mapping is performed by a place and route.

9. The method of claim 1, wherein said separating is performed manually.

10. The method of claim 1, wherein said separating is performed by a software profiler.

11. The method of claim 10, wherein said separating includes executing code compiled from said program source code and monitoring timing of said executing.

12. The method of claim 11, wherein said executing utilizes a set of test data.

13. The method of claim 11, wherein said monitoring includes determining functions that consume a significant portion of said timing of said executing.

14. The method of claim 1, wherein said identifying includes identifying functions by identifying regular structures.

15. The method of claim 1, wherein said identifying includes identifying functions with a limited number of inputs and outputs.

16. The method of claim 1, wherein said identifying includes identifying functions with a limited number of branches.

17. The method of claim 1, further comprising identifying overhead sections of the source code.

18. The method of claim 1, wherein mapping includes creating microcode.

19. The method of claim 1, wherein said mapping includes creating context dependent configurations.

20. The method of claim 1, wherein said matrix is sparsely-populated.

21. The method of claim 1, wherein said matrix is fully populated.

22. A system for creating run time executable code for hardware execution, the system comprising:

a processing element array;

a plurality of hardware accelerators defined in the processing element array;

a plurality of kernel sections of a program source code, the kernel sections including functions identified based on one or more run-time attributes of the functions;

a plurality of hardware dependent executable code portions derived, respectively, from said kernel sections, the hardware executable code portions being adapted for mapping to and execution on said plurality of hardware accelerators;

a plurality of hardware variants included in the mapped plurality of hardware dependent executable code portions, wherein at least two of the hardware variants comprise different hardware configurations that are substantially functionally equivalent; and

a matrix defining different combinations of said hardware accelerators, said hardware variants and said hardware dependent executable code portions, wherein the matrix is used to reference the mapped plurality of hardware executable code portions during run time execution of the plurality of hardware executable code portions.

23. The system of claim 22, wherein said hardware accelerators include digital signal processors.

24. The system of claim 22, wherein said hardware accelerators include bins.

25. The system of claim 24, wherein said bins support multiple hardware contexts.

26. The system of claim 25, wherein said bins support a first set of variants configured to support said multiple hardware contexts.

27. The system of claim 26, wherein said first set of variants are produced based upon resource usage.

28. The system of claim 27, wherein a second set of variants is configured to support multiple hardware configurations of one of said bins.

29. The system of claim 22, wherein said mapping is performed by a place and route.

30. The system of claim 22, wherein said kernel sections are derived manually.

31. The system of claim 22, wherein said kernel sections are derived using a software profiler.

32. The system of claim 31, wherein said software profiler executes code compiled from said program source code, and monitors time consumed.

33. The system of claim 32, wherein said software profiler includes a set of test data.

34. The system of claim 32, wherein said software profiler determines functions that consume a significant portion of said time consumed.

35. The system of claim 31, wherein said software profiler is configured to identify kernel sections by identifying regular structures.

36. The system of claim 31, wherein said software profiler is configured to identify kernel sections by identifying sections with a limited number of inputs and outputs.

37. The system of claim 31, wherein said software profiler is configured to identify kernel sections by identifying sections with a limited number of branches.

38. The system of claim 31, wherein said profiler identifies overhead sections.

39. The system of claim 22, wherein said hardware dependent executable code includes microcode.

40. The system of claim 39, wherein said microcode includes context dependent configurations.

41. The system of claim 22, wherein said matrix is sparsely-populated.

42. The system of claim 22, wherein said matrix is fully populated.

43. A computer storage medium having stored thereon instructions for execution by a processing element array, which when executed by said processing element array perform the following:

partitioning the processing element array into a plurality of hardware accelerators;

identifying a plurality of functions in a program source code based on one or more run-time attributes of the plurality of functions;

separating the identified plurality of functions from the program source code in a plurality of kernel sections;

producing the run time executable code including a plurality of hardware dependent executable code portions that correspond, respectively, with the identified plurality of functions;

mapping said plurality of hardware dependent executable code portions to the plurality of hardware accelerators;

identifying a plurality of hardware variants in the mapped plurality of hardware dependent executable code portions, wherein at least two of the hardware variants have different hardware configurations that are substantially functionally equivalent;

producing a matrix that defines different combinations of said plurality of hardware accelerators, said hardware variants and said hardware dependent executable code portions; and

referencing the mapped plurality of hardware executable code portions using the matrix during run time execution of the plurality of hardware executable code portions.

44. A system configured to create run time executable code for hardware execution, the system comprising:

a processing element array;

means for partitioning the processing element array into a plurality of hardware accelerators;

means for identifying a plurality of functions in a program source code-based on one or more run-time attributes of the plurality of functions;

means for separating the identified plurality of functions from the program source code in a plurality of kernel sections;

means for producing the run time executable code including a plurality of hardware dependent executable code portions that correspond, respectively, with the identified plurality of functions;

means for mapping said plurality of hardware dependent executable code portions to the plurality of hardware accelerators;

means for identifying a plurality of hardware variants in the mapped plurality of hardware dependent executable code portions, wherein at least two of the hardware variants have different hardware configurations that are substantially functionally equivalent; and

means for producing a matrix that defines different combinations of said plurality of hardware accelerators, said hardware variants and said hardware dependent executable code portions; and

means for referencing the mapped plurality of hardware executable code portions using the matrix during run time execution of the plurality of hardware executable code portions.