Method for compiling high level programming languages into an integrated processor with reconfigurable logic

• US 5,966,534 A
• Filed: 06/27/1997
• Issued: 10/12/1999
• Est. Priority Date: 06/27/1997
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Chameleon Semiconductor
• Inventors: Wong, Dale, Phillips, Christopher E., Cooke, Laurence H.
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Chavis, John Q.
• Application Number:
  US08/884,377
• Time in Patent Office: 837 Days
• Field of Search: 395/709, 395/705
• US Class Current: 717/155
• CPC Class Codes: G06F 30/30 Circuit design
• CPC Class Codes: G06F 8/4441 Reducing the execution time required by the program code
• CPC Class Codes: G06F 8/447 Target code generation
• 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/30181 Instruction operation extension or modification

Abstract

A method is presented for automatically compiling a high level computer program down into an application specific integrated circuit coupled with a generic microprocessor. The original source code is written in a standard programming language such as ANSI C. Source code analysis is performed by our compiler to automatically determine which blocks of logic are most appropriate for the application specific integrated circuit and which for the generic microprocessor. The complete layout of the application specific integrated circuit is automatically generated by our compiler. Object code for the microprocessor, with custom instructions to invoke the application specific integrated circuit, is also automatically generated by our compiler.

Claims

1. A computer implemented method for the automatic compilation of a computer program written in a high level programming language into a program for execution by one or more application specific integrated circuits coupled with a microprocessor, the method comprising the steps of:

using a cost function, automatically determining a set of one or more code blocks, the functions of which are to be executed by said one or more application specific integrated circuits, that will result in a relative performance improvement for a given input computer program written for execution by the microprocessor;

scheduling usage of physical resources, including reconfiguration resources, of said one or more application specific integrated circuits among at least some of said functions with the objective of maximizing utilization of said physical resources; and

producing code for execution by the microprocessor, including instructions for loading and activating said functions.

2. The method of claim 1, further comprising:

grouping the code blocks into groups based on at least one of an area constraint and an execution timing constraint;

scheduling loading of said functions; and

scheduling activation of said functions.

3. The method of claim 2, comprising the further step of producing detailed integrated circuit layouts of said circuitry.

4. The method of claim 2, comprising the further step of producing configuration data for said functions.

5. The method of claim 1, wherein said instructions include special instructions to load, activate, invoke and/or release functions implemented on an application specific integrated circuit.

6. The method of claim 1, wherein grouping comprises calculating start and finish times for the selected blocks of code.

7. The method of claim 5, wherein the start and finish times are calculated assuming that the selected code blocks are implemented in parallel with a fixed overhead for each parallel operation.

8. The method of claim 6, wherein the fixed overhead is calculated as OV=I+A+L, where I is an average time required to invoke the application specific integrated circuit as a coprocessor instruction;

A is an average time required to issue an activate configuration instructions plus an average stall time for activation; and

L is an average time required to issue a load configuration instruction plus an average stall time for loading.

9. The method of claim 5, wherein grouping is performed such that a difference between the latest and earliest finish times within a group is minimized.

10. The method of claim 5, wherein grouping is performed such that for each group, circuitry for performing the functions of that group does not exceed a specified capacity of a block of an application integrated circuit.

11. The method of claim 5, wherein grouping further comprises:

opening a new group with a total assigned area of zero;

sorting and traversing the code blocks in a predetermined order;

for each code block, if the area of the block plus the group'"'"'s assigned area does not exceed a specified maximum area for a single group, adding the code block to the group and adding the area of the code block to the group'"'"'s assigned area;

otherwise, opening a new group, adding the code block to the new group and adding the area of the code block to the new group'"'"'s assigned area.

12. The method of claim 10, wherein said predetermined order is in increasing order of finish times as a primary key, and increasing order of start times as a secondary key.

13. The method of claim 11, wherein grouping comprises the further steps of:

traversing the code blocks in decreasing order of finish times;

for each code block, determining a start spread and finish spread of a group to which the code block belongs, wherein the start spread is the difference between the latest and earliest start times of all of the code blocks belonging to the same group, and the finish spread is the difference between the latest and earliest finish times of all of the code blocks belonging to the same group; and

reassigning the code block to a different group if the code block'"'"'s area plus the different group'"'"'s assigned area does not exceed the specified maximum area for a single group, and if reassigning the code block results in a net improvement in at least one of start spread and finish spread for the group to which the code block belongs and the different group.

14. The method of claim 1, wherein selecting comprises sampling the percentage of time spent in each block of code when the computer program is executed on a single microprocessor.

15. The method of claim 13, wherein selecting further comprises:

parsing the high level programming language into an intermediate data structure representing control and data dependencies of the computer program; and

analyzing the amount of implicit parallelism in the intermediate data structure.

16. The method of claim 14, wherein selecting further comprises, for at least some of the code blocks of the computer program, estimating the cost and benefit of implementing a code block using circuitry within an application specific integrated circuit.

17. The method of claim 15, wherein estimating the cost and benefit of implementing a code block comprises:

estimating a reduction in execution time if the code block is implemented as an application specific integrated circuit; and

estimating a layout area required if the code block is implemented as an application specific integrated circuit.

18. The method of claim 16, wherein selecting further comprises:

accepting a first runtime parameter representing a maximum area of a single block of an application specific integrated circuit and a second runtime parameter representing a maximum total area for all blocks to be considered for implementation as application specific integrated circuits; and

selecting a set of code blocks which satisfies the first and second runtime parameters and which maximizes a total estimated reduction in execution time.

19. The method of claim 17, wherein selecting a set of code blocks which satisfies the first and second runtime parameters and which maximizes a total estimated reduction in execution time comprises:

sorting and traversing the code blocks in decreasing order of reduction in execution time; and

for each code block;

if the reduction equals zero, terminate;

estimate the required layout area;

if the area exceeds the specified maximum area for a single block of an application specific integrated circuit, skip this code block;

multiplying the specified maximum total area for all blocks by a constant greater than one;

if a total area of previously selected code blocks plus an estimated required layout area for a current code block exceeds the specified maximum total multiplied by the constant, terminate;

otherwise, select the code block; and

using a knapsack algorithm and the maximum total area to perform a further selection on the selected code blocks.

20. The method of claim 16, wherein the reduction in execution time is estimated in accordance with the formula R=T(1-1/P) where T is a percentage of execution time spent in the code block and P is a number of paths which can be executed in parallel in the code block.

21. The method of claim 16, wherein the intermediate data structure is a tree structure containing nodes, and estimating the layout area comprises:

performing bottom-up traversal of the tree structure;

mapping each node in the tree to a cell from a library of circuit primitives;

calculating a total area of the mapped cells; and

calculating an additional area required for cell interconnections.

22. The method of claim 20, wherein mapping is performed in accordance with multiple predetermined mappings including at least one of the following:

scalar variables map to registers;

arrays map to register files;

addition and subtraction operators map to adders;

increment and decrement operators map to adders;

multiplications and division operators map to multipliers;

equality and inequality operators map to comparators;

+=, -= operators map to accumulators;

*=, /= operators map to multiply-accumulators, <

<

, >

>

operators map to shift registers;

&

, |, ˜

, , operators map to boolean gates, branches map to a state machine, and loops map to a state machine.

23. The method of claim 20, wherein mapping includes determining a number of significant bits required to support a data precision expected by the computer program.

24. The method of claim 20, wherein calculating an additional area required for interconnections is performed in accordance with the following formula:

area=max(0, (A-B)) where A is an estimate of total area required for interconnections and B is an estimate of area available within the mapped cells for use by interconnections.

25. The method of claim 23, wherein A is calculated as the product of a runtime parameter for the width of an interconnection, an average length of an interconnection calculated as a fraction times the square root of the number of mapped cells, and the total number of interconnections.

26. The method of claim 23, wherein B is calculated as the product of a runtime parameter for the fraction of cell area for interconnections and the total area of all of the mapped cells.

27. The method of claim 14, comprising the further step of estimating a reduction in execution time for each group.

28. The method of claim 26, wherein scheduling activation is performed such that overall execution time is minimized subject to at least one of an area constraint and an execution time constraint.

29. The method of claim 27, wherein scheduling activation is performed such that data and control dependencies of all code blocks within a group are not violated.

30. The method of claim 27, wherein scheduling activation is performed such that a specified number of simultaneous blocks of an application specific circuit is not exceeded.

31. The method of claim 27, wherein scheduling further comprises:

modeling each group as a separate task;

modeling as a processor each available block of reconfigurable logic on an application specific integrated circuit; and

running a modified multiprocessor scheduling algorithm.

32. The method of claim 30, wherein the intermediate data structure is a graph in which arcs represent dependencies, and wherein modeling each group as a separate task comprises:

for each group, adding a node to the graph;

for each code block assigned to a group, modifying the graph such that arcs that previously pointed to the code block point instead to a node representing the group;

determining a difference between a latest finish time and an earliest start time of code blocks assigned to the group; and

setting a required time of the group equal to said difference.

33. The method of claim 30, wherein running a modified multiprocessor scheduling algorithm comprises:

running a standard list scheduling multiprocessor scheduling algorithm;

during running of the algorithm, in the event no processor is available when a newly-ready task becomes ready;

calculating a stall time until a processor would become available;

create a list of contending tasks including the newly-ready task and tasks scheduled to be executing at a time the newly-ready task becomes ready; and

finding a contending task with a minimum estimated reduction in execution time.

34. The method of claim 32, wherein running the modified multiprocessor scheduling algorithm further comprises:

if the stall time is less than or equal to the minimum reduction, scheduling the newly-ready task to execute when a processor becomes available and continuing to run the multiprocessor scheduling algorithm.

35. The method of claim 33, wherein running the modified multiprocessor scheduling algorithm further comprises, if the stall time is greater than the minimum reduction, discarding the task with the minimum reduction and continuing to run the multiprocessor scheduling algorithm.

36. The method of claim 33, wherein running the modified multiprocessor scheduling algorithm further comprises, if the stall time is greater than the minimum reduction:

replacing the newly-ready task with two new tasks, a first new task containing code blocks of the newly-ready task having start times later than when a processor would become available, and a second new task containing other code blocks of the newly-ready task;

replacing respective tasks scheduled to be executing at a time the newly-ready task becomes ready with two new respective tasks, a first new task containing code blocks of the newly-ready task having start times later than when a processor would become available, and a second new task containing other code blocks of the newly-ready task.

37. The method of claim 35, wherein running the modified multiprocessor scheduling algorithm further comprises:

of the new tasks, finding a task with a minimum reduction in execution time; and

discarding the task with the minimum reduction.

38. The method of claim 26, wherein scheduling loading is performed such that overall execution time is minimized subject to at least one of an area constraint and an execution time constraint.

39. The method of claim 37, wherein scheduling loading is performed such that each function activation is preceded by loading.

40. The method of claim 37, wherein scheduling loading is performed such that a specified capacity for coexisting groups loaded for a block of an application specific circuit is not exceeded.

41. The method of claim 37, wherein the data structure includes a control flow graph, and wherein scheduling loading comprises:

modeling each group as a task and each available block of an application specific integrated circuit as a processor with a specified maximum number of simultaneous tasks;

for each group activation of which has been successfully scheduled, creating a new load_-- group task having a finish time equal to a finish time of a task representing the group and having a start time equal to a start time of the task representing the group minus a runtime parameter specifying a time required to load a group.

42. The method of claim 40, wherein scheduling loading further comprises, for each new load_-- group task, inserting a node into the control flow graph.

43. The method of claim 40, wherein scheduling loading further comprises:

finding a branching node in the control flow graph immediately preceding activation;

calculating a stall time of a load_-- group task as a finish time of the branching node minus the load_-- group task start time;

if the stall time is less than or equal to the estimated reduction in execution time for the group, creating a control flow arc from the branching node to the load_-- group task;

otherwise, discarding the load_-- group task and discarding the group.

44. The method of claim 41 or claim 42 wherein scheduling loading further comprises running a modified list processing multiprocessor scheduling algorithm.

45. The method of claim 43, wherein running a modified list processing multiprocessor scheduling algorithm comprises:

running a list scheduling multiprocessor scheduling algorithm with a specified maximum number of simultaneous tasks per processor;

during running of the algorithm, in the event no processor is available when a newly-ready task becomes ready;

calculating a stall time until a processor would become available;

create a list of contending tasks including the newly-ready task and tasks scheduled to be executing at a time the newly-ready task becomes ready; and

finding a contending task with a minimum estimated reduction in execution time.

46. The method of claim 41, wherein running the modified multiprocessor scheduling algorithm further comprises:

if the stall time is less than or equal to the minimum reduction, scheduling the newly-ready task to execute when a processor becomes available, adjusting the schedule for a corresponding group task and continuing to run the multiprocessor scheduling algorithm.

47. The method of claim 44, wherein running the modified multiprocessor scheduling algorithm further comprises, if the stall time is greater than the minimum reduction, discarding the task with the minimum reduction and its corresponding group and continuing to run the multiprocessor scheduling algorithm.

48. The method of claim 43, wherein running the modified multiprocessor scheduling algorithm further comprises, if in the control flow graph a branching node intervenes between a node representing a discarded load_-- group task and a node representing activation of the corresponding group:

finding a branching node in the control flow graph immediately preceding activation;

calculating a stall time of a load_-- group task as a finish time of the branching node minus the load_-- group task start time;

if the stall time is less than or equal to the estimated reduction in execution time for the group, creating a control flow arc from the branching node to the load_-- group task;

otherwise, discarding the load group task and discarding the group.

49. The method of claim 46, wherein running the modified multiprocessor scheduling algorithm further comprises, if the stall time is greater than the minimum reduction:

replacing the newly-ready task with two new tasks and corresponding groups, a first new group containing code blocks of the newly-ready task having start times later than when a processor would become available, and a second new group containing other code blocks of the newly-ready task;

replacing respective tasks scheduled to be executing at a time the newly-ready task becomes ready with two new respective tasks and corresponding groups, a first new group containing code blocks of the newly-ready task having start times later than when a processor would become available, and a second new group containing other code blocks of the newly-ready task.

50. The method of claim 48, wherein running the modified multiprocessor scheduling algorithm further comprises:

of the new tasks, finding a task with corresponding group having a minimum reduction in execution time; and

discarding the task with the corresponding partition having the minimum reduction.

51. The method of claim 49, wherein running the modified multiprocessor scheduling algorithm further comprises, if in the control flow graph a branching node intervenes between a node representing a discarded load_-- group task and a node representing activation of the corresponding group:

finding a branching node in the control flow graph immediately preceding activation;

calculating a stall time of a load_-- group task as a finish time of the branching node minus the load_-- group task start time;

if the stall time is less than or equal to the estimated reduction in execution time for the group, creating a control flow arc from the branching node to the load_-- group task;

otherwise, discarding the load group task and discarding the group.