Control flow and memory management optimization

• US 6,064,819 A
• Filed: 04/02/1997
• Issued: 05/16/2000
• Est. Priority Date: 12/08/1993
• Status: Expired due to Term

• Current Assignee: IMEC International
• Original Assignee: IMEC International
• Inventors: Nachtergaele, Lode, van Swaaij, Michael, Samsom, Hans, Franssen, Frank, Catthoor, Francky, De Man, Hugo
• Primary Examiner(s): Voetz, Emanuel T.
• Assistant Examiner(s): CORCORAN, PETER JOSEPH
• Application Number:
  US08/827,883
• Time in Patent Office: 1,140 Days
• Field of Search: 395/705, 395/707, 395/709
• US Class Current: 717/156
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

Selected code is modeled in a polyhedral dependency graph (PDG). A placement optimizer maps each element of the PDG to an optimally placed PDG. An ordering optimizer maps the placed PDG to an optimally ordered PDG. The PDG, place PDG, and ordered PDG are combined to produce a transformation script. The transformation script is applied to the selected specification description to produce optimized selected code. Optimized selected code is combined with original code to generate a control-flow optimized code. In addition, memory directives are derived from the ordered PDG model. The memory directives and optimized code are used to generate target code for simulation or software compilation.

Claims

1. A processor-implemented method for optimizing code, including operations on multi-dimensional signals, said method comprising the steps of:

generating from said code a polyhedral dependency graph description wherein a first code portion, a second code portion, and their associated dependencies are represented, said graph having nodes and arcs, said arcs representing said dependencies, said nodes comprising node domains and representing said first and said second code portions; and

mapping each code portion representation to a common representation according to an associated function, wherein a first substep of ordering said node domains for individual mapping and a second substep of placing the ordered node domains are included, said second substep being executed in a non-static way based on the ordering being determined in said first substep.

2. The optimization method of claim 1 wherein the code comprises a signal processing specification.

3. The optimization method of claim 1 wherein the code comprises a numerical processing specification.

4. The optimization method of claim 1 wherein the code portion representation comprises a node domain.

5. The optimization method of claim 1 wherein the code portion representation comprises one or more operand domains.

6. The optimization method of claim 1 wherein the code portion representation comprises one or more definition domains.

7. The optimization method of claim 1 wherein the function varies according to the dependencies of the code portion representation.

8. The optimization method of claim 1 wherein the function varies according to a dependency angle of the code portion representation.

9. The optimization method of claim 1 wherein the function varies according to a dependency variance of the code portion representation.

10. The optimization method of claim 1 wherein the function varies according to a dependency length of the code portion representation.

11. The optimization method of claim 1 wherein the function varies according to the number of dependencies in the code portion representation.

12. The optimization method of claim 1 wherein the function comprises an affine transformation function represented by Ax+b.

13. The optimization method of claim 1 wherein the function comprises a unimodular transformation matrix.

14. The optimization method of claim 1 wherein the function comprises a matrix entry that is determined by solving an optimization function.

15. The optimization method of claim 14 wherein the matrix entry is further determined by solving a constraint function.

16. The optimization method of claim 15 wherein the matrix entry is determined by using a branch-and-bound technique.

17. The optimization method of claim 16 wherein the matrix entry is determined by using a tight lower bound to reduce the search space.

18. The optimization method of claim 1 wherein the function comprises an offset coefficient that is determined by solving an optimization function.

19. The optimization method of claim 18 wherein the the offset coefficient is further determined by solving a constraint function.

20. The optimization method of claim 19 wherein the offset coefficient is determined by using an integer linear programming formulation.

21. The optimization method of claim 1 wherein the mapping step is constrained by a constraint function.

22. The optimization method of claim 21 wherein the constraint function varies according to constraints imposed by code portion representations in the common representation.

23. The optimization method of claim 21 wherein the constraint function varies according to a linear ordering of the code portion representations in the common representation.

24. The optimization method of claim 21 wherein the constraint function varies according to data routing information between a code portion representation and a code portion representation in the common representation.

25. The optimization method of claim 21 wherein the constraint function varies according to a restricted search space.

26. The optimization method of claim 21 wherein the constraint function varies according to user-defined mapping constraints.

27. The optimization method of claim 1 further comprising the step of:

creating an ordered common representation wherein an ordering vector maps the common representation onto an ordering axis.

28. The method of claim 27 further comprising the step of:

creating an optimized code based on the common representation and the ordered common representation.

29. The method of claim 27 wherein the ordering axis comprises a 1-dimensional ordering axis.

30. The optimization method of claim 27 wherein the ordering step further comprises the steps of:

collecting all intra- and inter-dependency vectors in the common representation into a plurality of dependency cone rays;

projecting all dependencies in the common representation on the dependency cone rays;

calculating a dependency cost for each dependency cone ray;

selecting a set of maximal cost dependency cone rays;

forming a ray base from the set of selected maximal cost dependency cone rays;

computing a base transformation of the ray base; and

applying the base transformation to the common representation to create a ordered common representation.

31. The optimization method of claim 30 wherein the computing step is constrained by user-defined constraints.

32. The optimization method of claim 27 further comprising the step of:

determining certain characteristics of the ordered common representation.

33. The optimization method of claim 32 wherein a lifetime of a signal in the ordered common representation is determined.

34. The optimization method of claim 32 wherein a size of a signal in the ordered common representation is determined.

35. The optimization method of claim 32 wherein a maximum number of life signals simultaneously alive is determined for the ordered common representation.

36. The optimization method of claim 32 wherein the number of integer points within polytopes contained in the ordered common representation at the extreme points of the ordered common representation is determined.

37. The optimization method of claim 1 wherein the generating step further comprises a first step of:

selecting a portion of a code, wherein the selected portion of code comprises multi-dimensional signals.

38. The optimization method of claim 1 wherein the generating step further comprises a first step of:

generating a signal flow description from a code, wherein the signal flow description is based on the syntactical structure of the code.

39. The optimization method of claim 38 further comprising the step of:

pruning the signal flow description, wherein multi-dimensional signals are included in the pruned signal flow description.

40. The optimization method of claim 38 further comprising the step of:

abstracting signals in the signal flow description.

41. The optimization method of claim 38 further comprising the step of:

abstracting operations in the signal flow description.

42. The optimization method of claim 1, following the generating step, further comprising the step of:

modifying the dependency description wherein dependencies within a code portion representation are split.

43. The optimization method of claim 27, further comprising the step of:

generating a script wherein the script is based on the code portion representation functions and the ordered common representation.

44. The optimization method of claim 43 wherein the script comprises an affine transformation wherein a unimodular affine transformation is performed when applied to the code.

45. The optimization method of claim 43 wherein the script contains a total-body-split transformation wherein all statements in a body of a loop are split when the transformation is applied to the code.

46. The optimization method of claim 43 wherein the script contains a Ndim-body-merge transformation wherein two loops are merged into one loop when the transformation is applied to the code.

47. The optimization method of claim 43, further comprising the step of:

creating an optimized code by applying the script to the code.

48. The optimization method of claim 47, further comprising the step of:

generating target code based on the optimized code.

49. The method as recited in claim 1, wherein said first and said second substep are executed substantially simultaneously thereby achieving a dynamic mapping.

50. The method as recited in claim 1, wherein said step of mapping each code portion representation further comprises a substep of splitting said node domains where after said first and said second substep are executed.

51. The method as recited in claim 50, wherein said step of splitting said node domains is executed in such a way that the resulting domains having an intra-dependency cone that is within a single orthant.

52. A computing system for optimizing a code including operations on multi-dimensional signals, the system comprising:

a processor for executing programmed instructions and for storing and retrieving data;

a memory unit coupled to the processor for storing program instruction steps and data for execution by the processor;

a dependency description generator coupled to the processor for generating a polyhedral dependency graph description in which a first code portion, a second code portion, and their associated dependencies are represented, said graph having nodes and arcs said arcs representing said dependencies, said nodes comprising node domains and representing said first and said second code portions; and

an optimizer coupled to the processor for optimizing the placement of each code portion representation in a common representation in which the placement of each code portion representation in the common representation is described by a mapping function, wherein a first substep of ordering said node domain for individual mapping and a second substep of placing the ordered node domains are included, said second substep being executed in a non-static way based on the ordering being determined in said first substep.

53. The computing system of claim 52 further comprising:

a specification environment coupled to the processor for producing the code.

54. The computing system of claim 52 further comprising:

an order optimizer coupled to the processor for ordering the common representation wherein an ordering vector maps the common representation onto an ordering axis to create an ordered common representation and a set of memory directives.

55. The computing system of claim 54 further comprising:

a code generator coupled to the processor for generating a target code based on the set of memory directives.

56. The computing system of claim 54 further comprising:

a transformation engine coupled to the processor for transforming the code into optimized code wherein transformations based on the common representation and the ordered common representation are applied to the code.

57. The computing system of claim 56 further comprising:

a code generator coupled to the processor for generating a target code based on the optimized code.

58. The computing system of claim 52 wherein the polyhedral dependency graph description comprises nodes and arcs, the nodes comprising node domains representing definition domains and operand domains.

59. The system as recited in claim 52, wherein said first and said second substep are executed substantially simultaneously thereby achieving a dynamic mapping.

60. The system as recited in claim 52, wherein said mapping function further comprises a substep of splitting said node domains where after said first and said second substep are executed.

61. The system as recited in claim 60, wherein said substep of splitting said node domains is executed in such a way that the resulting domains having an intra-dependency cone that is within a single orthant.

62. In a computing system having a processor for executing programmed instructions, an optimized code generated by the processor in accordance with the method comprising:

generating from a code a polyhedral dependency graph description in which a first code portion, a second code portion, and their associated dependencies are represented, wherein the code includes operations on multi-dimensional signals;

mapping each code portion representation to a common representation according to an associated function;

creating an ordered common representation wherein an ordering vector maps the common representation onto an ordering axis; and

generating the optimized code based on the common representation and the ordered common representation.

63. The computing system of claim 62 wherein the polyhedral dependency graph description comprises nodes and arcs, the nodes comprising node domains representing definition domains and operand domains.

64. The computing system of claim 62, further comprising the optimization step of determining certain characteristics of the ordered common representation prior to generating the optimized code.

65. A processor-implemented method for optimizing a code, the method comprising the steps of:

generating from the code a polyhedral dependency graph description in which a first code portion, a second code portion, and their associated dependencies are represented, wherein the code includes operations on multi-dimensional signals;

modifying the polyhedral dependency graph description wherein dependencies within a code portion representation are split;

mapping each code portion representation to a common representation according to an associated function;

mapping each code portion representation to an ordered common representation wherein an ordering vector maps the common representation onto an ordering axis; and

creating an optimized code based on the common representation and the ordered common representation.

66. The optimization method of claim 65 wherein the polyhedral dependency graph description comprises nodes and arcs, the nodes comprising node domains representing definition domains and operand domains.

67. The optimization method of claim 65 wherein the generating from the code a polyhedral dependency graph description step comprises the steps of:

selecting a portion of a code, wherein the selected portion of code comprises multi-dimensional signals;

generating a signal flow description from a code, wherein the signal flow description is based on the syntactical structure of the code;

pruning the signal flow description, wherein multi-dimensional signals are included in the pruned signal flow description; and

abstracting signals and operations in the signal flow description.

68. The optimization method of claim 65 where the mapping to the ordered common representation step comprises the steps of:

collecting all intra- and inter-dependency vectors in the common representation into a plurality of dependency cone rays;

projecting all dependencies in the common representation on the dependency cone rays;

calculating a dependency cost for each dependency cone ray;

selecting a set of maximal cost dependency cone rays;

forming a ray base from the set of selected maximal cost dependency cone rays;

computing a base transformation of the ray base;

applying the base transformation to the common representation to create an ordered common representation.

69. A processor-implemented method for optimizing code, including operations on multi-dimensional signals, said method comprising the steps of:

generating from said code a polyhedral dependency graph description wherein a first code portion, a second code portion, and their associated dependencies are represented, said graph having nodes and arcs, said arcs representing said dependencies, said nodes comprising node domains and representing said first and said second code portions; and

mapping each code portion representation to a common representation according to an associated function, wherein a first substep of ordering said node domains for individual mapping and a second substep of placing the ordered node domains are included, said second substep being executed in a non-sequential way based on the ordering being determined in said first substep.

70. The method as recited in claim 69, wherein said first and said second substep are executed substantially simultaneously thereby achieving a dynamic mapping.

71. The method as recited in claim 69, wherein said step of mapping each code portion representation further comprises a substep of splitting said node domains where after said first and said second substep are executed.

72. The method as recited in claim 71, wherein said step of splitting said node domains is executed in such a way that the resulting domains having an intra-dependency cone that is within a single orthant.

73. A processor-implemented method for optimizing code, including operations on multi-dimensional signals, said method comprising the steps of:

generating from said code a polyhedral dependency graph description wherein a first code portion, a second code portion, and their associated dependencies are represented, said graph having nodes and arcs, said arcs representing said dependencies, said nodes comprising node domains and representing said first and said second code portions; and

mapping each code portion representation to a common representation according to an associated function in a non-heuristic way using a non-linear solver.

74. A computing system for optimizing a code including operations on multi-dimensional signals, the system comprising:

a processor for executing programmed instructions and for storing and retrieving data;

a memory unit coupled to the processor for storing program instruction steps and data for execution by the processor;

a dependency description generator coupled to the processor for generating a polyhedral dependency graph description in which a first code portion, a second code portion, and their associated dependencies are represented, said graph having nodes and arcs, said arcs representing said dependencies, said nodes comprising node domains and representing said first and said second code portions; and

an optimizer coupled to the processor for optimizing the placement of each code portion representation in a common representation in which the placement of each code portion representation in the common representation is described by a mapping function, wherein a first substep of ordering said node domain for individual mapping and a second substep of placing the ordered node domains are included, said second substep being executed in a non-sequential way based on the ordering being determined in said first substep.

75. The method as recited in claim 74, wherein said first and said second substep are executed substantially simultaneously thereby achieving a dynamic mapping.

76. The method as recited in claim 74, wherein said step of mapping each code portion representation further comprises a substep of splitting said node domains where after said first and said second substep are executed.

77. The method as recited in claim 76, wherein said step of splitting said node domains is executed in such a way that the resulting domains having an intra-dependency cone that is within a single orthant.

78. A computing system for optimizing a code including operations on multi-dimensional signals, the system comprising:

a processor for executing programmed instructions and for storing and retrieving data;

a memory unit coupled to the processor for storing program instruction steps and data for execution by the processor;

a dependency description generator coupled to the processor for generating a polyhedral dependency graph description in which a first code portion, a second code portion, and their associated dependencies are represented, said graph having nodes and arcs, said arcs representing said dependencies, said nodes comprising node domains and representing said first and said second code portions; and

an optimizer coupled to the processor for optimizing the placement of each code portion representation in a common representation in which the placement of each code portion representation in the common representation is described by a mapping function, wherein the mapping function is executed in a non-heuristic way using a non-linear solver.