Control flow and memory management optimization6064819Abstract 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 We claim: Description BACKGROUND OF THE INVENTION
______________________________________
(j:0..N - 1)::
begin
a[j] = .function.1(s[j]); node: 1
(k:O..P)::
begin
b[k][j] = .function.1(s[k + j]); node: 2
r[k][j + 1] = r[k][j] + INT16(a[j] * b[k][j]); node: 3
end;
end;
______________________________________
Referring to FIG. 12, the PDG (36) for this code is depicted (300). The three nodes are indicated in the Silage code and in FIG. 12 as 310, 320, 330. The affine functions f(x) on the graph edges are the result of mapping node spaces on their definition P.sub.def and operand spaces P.sub.opnd. Each of these polytopes--within its space--can be mathematically denoted by a set of inequalities Cx.gtoreq.c as shown in FIG. 13 for P.sub.opnd (342) and P.sub.def (344) of node 3. The relation between these two spaces is given by the affine function f.sub.33 (x) (340). The PDG (36) is input to the optimization step of generating a transformation script (119). This is necessary in order to relate back to a model of the original code to be optimized (16) and to extract the appropriate body-split transformation (142) (discussed below). The PDG (36) is analyzed (38) to produce an annotated PDG (39). This task is partitioned into two sub-tasks: quantitative and structural PDG analysis, and node domain splitting. Quantitative data such as: (a) the number of node domains; (b) number of arcs between nodes; (c) node domain structure; (d) dependency structure; and, (e) number of intra- and inter-domain dependencies are derived. The first two topics are explanatory. Node domain structure: An important observation is that the node domains of a single problem instance, between which there is a dependency, often have depending faces which are (nearly) identical, under an affine transformation with a limited unimodular transformation matrix for which -1.ltoreq.a.sub.ij .ltoreq.1. If node domains have a dependency but are of different dimensionality, then the smaller dimensionality node domain is generally (in the same limited unimodular way) identical to a face of the same dimension, to which it is dependent, of the larger dimensionality node domain. Dependency structure: The number of dependencies between a consuming node domains P.sub.e and a producing node domain is often directly proportional to the maximum of the dimension of P.sub.e and the dimension of its mapping on the operand space belonging to the signal corresponding to P.sub.p. This relation can be deduced from given dependency restrictions in combination with the node domain characteristics. Furthermore, more general dependency information, like dimensionality, uniformity, affinity, broadcasting and data dependent relations, is derived. This information is used in the placement optimization (section 3.4). Number of intra- and inter-domain dependencies: By default no exhaustive dependency count is performed because the intention of this approach is an algorithm parameter independent model and therefore also the optimization techniques that rely on it. Optionally an exact (but sometimes expensive in terms of run-time) dependency count can be performed. A dedicated algorithm based on Fourier-Motzkin elimination, for example may be used (see for example, F. Balasa, F. Catthoor, H. De Man, "Optimal Evaluation of Memory Area for Multi-dimensional Processing Systems", accepted for IEEE Int. Conf. Comp. Aided Design, Santa Clara Calif., November 1993). In principle every algorithm that counts integer points in a polytope can be used for this task. Note, PDG Analysis (38) can be limited or controlled by the user (34) (e.g., to skip or modify this step). Within the PDG analysis step (38), the goal of the node domain splitting task is to split node domains in the PDG (36) that do not allow a procedural ordering caused by their intra-dependency structure. Additionally, the search space for domains that in principle do allow a procedural ordering, but have intra-dependency cones with angles larger than 90 degrees can optionally be split. Domains are split in such a way that each of the resulting domains after splitting has an intra-dependency cone that is within a single orthant, i.e., the resulting maximal angle between dependencies is 90 degrees (pointed cone). More detailed information is found in Chapter 5 of van Swaaij as appended. The annotated PDG (39) is used in the placement optimization step (40) to produce a placed PDG (92) (described in detail below). The placed PDG (92) is used in the order optimization step (100) to produce an ordered PDG (118) (described in detail below). Memory directives (116) are also produced in the order optimization step (100). The placed PDG (92), ordered PDG (118), and the original PDG (36) are combined in step (119) to produce a transformation script (120). Here (119) various types of transformations (132, 136, 140, 144) are formed from the given input as described below with reference to FIG. 8. Referring to the flowchart of FIG. 9, the optimized code (150) is used, for example, in architecture synthesis (170, FIG. 1) and/or in a compiled code simulator (160). Target code (e.g., C) can be produced (162, 164) using the memory directives (116) generated by the optimization step (20). The target code (164) can be compiled (166) and, for example, executed or used in a standard chip solution for the original specification description (12). FIG. 4 is a top-level flowchart illustrating the placement or mapping optimization step (40) in FIG. 2. This step (40) places or maps all of the node space polytopes in the PDG (39) (i.e., P.sub.opnd and P.sub.def as shown in FIG. 12) in a single common node space (92) by performing a series of combinatorial optimization problems. Each separate problem concerns itself with the placement (50) of a single node domain (46). The placement (50) is performed by a transformation (86) applied to the node domain. Therefore, although the word "placement" or "mapping" is used, the shape and/or characteristics of the node domain (46) may be changed by such a transformation (50). Two sub-tasks are performed: node domain ordering (44) for individual placement and individual node domain placement (50). In one embodiment, node domain ordering is a statical method, because the placement ordering is determined once for all node domains and assumed to be fixed for all subsequent tasks in the placement optimization. Alternatively, placement ordering (44) may be a dynamic ordering. The annotated PDG model (39) containing all of the exact node domain dependencies is used to determine the node domain ordering (44). At least two aspects of each node domain in the annotated PDG model (39) influence the ordering (44): the node domain arc affine mapping function and the node domain arc direction (see FIG. 12). Also, the ordering of a subset of node domains in the annotated PDG (39) may influence the ordering of the remaining domains. In one embodiment, the ordering of the node domains (44) is performed using a breadth first search. Additionally, user interaction (34) is possible by respecifying different ordering weights for each of the node domains (42). The node domain arc affine mapping function in the annotated PDG (39) determines the dimensionality of the mapping P.sub.ab of a node domain P.sub.a on another node domain P.sub.b. It therefore determines the dimension of the convex set formed by those grid points of P.sub.b with corresponding signal instances used by P.sub.a. The maximum of the dimension of P.sub.a and its mapping P.sub.ab is a measure for the number of dependencies between P.sub.a and P.sub.b. The dimensionality of the mapping P.sub.ab also influences the size of the set of optimal solutions. For example, if P.sub.a has a single dependency on a grid point of P.sub.b (a 0-dimensional mapping) then there may be many transformations with very different node domain placements, for which the length of this dependency vector will have the same Manhatten length. If two node domains P.sup.1.sub.a, P.sup.2.sub.a have a dependency on the same node domain P.sub.b then the one with the largest mapping P.sup.1.sub.ab, P.sup.2.sub.ab will most likely have the most dependencies and thus the smallest search space of optimal transformations. This is a reason to transform this node domain first. Its placement will reduce the search space of optimal transformations for the other node domains. However, switching the transformation ordering for these node domains may lead to reducing the transformation space for the second node domain in such a way that all optimal transformations are lost. The node domain arc direction in the annotated PDG (39) gives a rather natural ordering of node domains for the target domain of optimization problems, i.e., if P.sub.a depends on P.sub.b which depends on P.sub.c, then P.sub.b should be placed somewhere between P.sub.a and P.sub.c. The main reason for this is that in solving the problem of finding an optimal transformation only the dependencies between node domains which the transformation is known or which the transformation is part of the optimization problem can be accounted for. These node domains are the polytope to be transformed and the already placed node domains. Transforming the node domains in an order different from the dependencies or inverse dependencies leads to unpredictable dependency costs between these node domains. Additionally, node domain ordering rules (43) can be employed to determine the node domain ordering (44) and the rules can be applied in various order. In one embodiment, leading to sequential placement of the node domains, each rule (43) selects, from a set of not yet transformed node domains in annotated PDG (39), a set of node domains which complies with the rule. Each rule selects its set of node domains from the set passed on by the previous rule. Note that rules involving arcs are bi-directional. These rules consider arcs as undirected edges between nodes. In this way, nodes other than sink or source nodes may be chosen as the first in the ordering. Alternate rule application procedures (e.g., nonsequential, heuristic application of the rule sets) may also be used for this step. The sequential placement rule (43), as used in one embodiment, is explained in more detail herein. When sequential placement of node domains is applied (44), placing one node domain at a time leads to a stepwise growing cluster of node domains in the common node space (92). Given the characteristics of the node domains and dependencies, this leads to a stepwise increasing inaccessibility of node domains by encapsulation. In other words, when the 10th node domain to be placed has a dependency to the first placed node domain then the chances are high that these dependencies will be long and that its placement will be constrained by other node domains than the ones on which it depends. Therefore, from the set of node domains passed on by the above rules, those should be placed first which have dependencies on the lowest order placed node domains. The rest of the ordering for the remaining node domains is directly based on their inter-dependerncies. That is, if P.sub.a depends on P.sub.b then P.sub.b is given priority in placement with respect to P.sub.a. If there are no dependencies between two node domains, the ordering is arbitrary. If there is a cycle then any one of all possible orderings may be best. In the preferred implementation one of all possible orderings is chosen, based on the study of practical examples. However, different orderings may be examined by providing a back-tracking mechanism in which each ordering is evaluated in the common node space (47). Another approach is to split the node domains into non cyclic parts, which must be possible if the initial PDG (39) is derived from an executable specification. Splitting would, however, lead to a possibly large number of sub-node domains because the cyclic dependencies can be uniformly spread over the node domains. In summary, the following steps may be applied for determining the node domain ordering step (44) using a static sequential rule: Select the node domain in the graph (39) which has the largest number of dependencies with others (incoming and outgoing). This node domain forms the initial set of ordered polytopes Op. Repeat until all node domains are ordered: 1. Select those node domains which are not in Op but which have dependencies to node domains in Op. These polytopes form set A. 2. Repeat until A is empty: (a) Remove those node domains from A which have a dependency with a node domain in Op with a maximum mapping-dimension for all node domains in A. These node domains form set B. The mapping-dimension of a dependency between a node domain P.sub.a and P.sub.b is the dimension of the node domain encapsulating all grid points of P.sub.b on which P.sub.a depends. (b) Repeat until B is empty: i. Remove those node domains from B which have a dependency with a node domain in Op with a minimal order for all node domains in B. These polytopes form set C. The order of a dependency is the order of the corresponding node domain in Op. If the corresponding arc in the graph is incident from the node domain to be placed then 1 is added to this order. ii. Give the node domains in C an initial order equal to their highest order dependency plus 1. iii. Order the node domains in C among themselves on their initial ordering and arc direction and add them to Op. Note: Optional re-specification of the node domain ordering by the user is also possible (34,42). FIG. 5 shows the flowchart of the individual node domain (46) placement step (50) is defined by the following optimization problem given constraint graph (52): minimize: ##EQU1## variables: Transformation matrix A, offset vector b and ordering vector .PI. constraints: A unimodular ##EQU2## In the present embodiment, the minimization factors are given in the default order of applicability. Also, dependency length overrules dependency variance M which overrules maximal angle .alpha. between dependencies. The maximal angle .alpha. between dependencies is directly related to the search space of the ordering vector .PI.. .PI. is optimized in the subsequent order optimization step (100) as discussed below. The set D contains selected dependencies between the polytope P to be placed (46) and the placed polytopes (47), and the factors w.sub.xy define the weight associated with the dependencies. The extreme points of P (46) are e .epsilon. E, which after transformation must lie within the bounds set by the set of linear constraints defined by C and c. Note that the ordering vector .PI. is a variable but does not appear in the cost function. .PI. is defined in the optimization problem to ensure the existence of a linear ordering vector. Determining an optimal ordering vector is not the objective of the placement optimization problem (50). .PI. is calculated in step (100). The sets D.sub.P and D.sub.O represent the rays of the cones that are convex hulls over the sets of dependencies within P (46) and within the collection of placed polytopes respectively (47). Only the rays have to be used since if an ordering vector exists for these dependencies then the same vector is valid for all dependencies in the cones. See, for example, G. L. Nemhauser, L. A. Wosley "Integer and Combinatorial Optimization", John Wiley & Sons, New York, N.Y., 1988. The variables of the optimization problem (50) that determine the placement of a single node domain (46) are the coefficients of an affine transformation expressed by a matrix notation: y=Ax+b (86). Each node domain (46) has its individual affine transformation (86) which maps it from its original node space to the common node space (92). In principle, A is an n.times.m integer matrix and b a n.times.1 integer vector, with n the dimension of the common node space (92) and m the dimension of a certain node space (46). However, in one embodiment, all node domains (46) which are to be placed in a single common node space (92) have already been extended in dimension, to fit the common node space (92) dimension, as a pre-processing step when the PDG is extracted (32). Therefore, all transformation matrices A (86) are square (m=n). Several cost functions are used in the placement optimization step (50). These functions are described below. More details can be found in Chapter 6 of van Swaaj, ibid, as appended hereto. A dependency angle is determined in a conventional manner (see Nemhauser, Ibid). A dependency variance is the number of distinct dependencies of a node (46). The computation of the number of dependencies and the dependency length is discussed here. If, for the transformation (86) of a single node domain P.sub.a, (46) all dependencies (as defined in the annotated PDG (39)) with certain grid points in the common node space (92) should be taken into account then for each grid point of P.sub.az, (46) with P.sub.z, an already placed polytope in the partially placed PDG (47), the Manhatten length of the outgoing dependency should be determined. The complexity of this operation is, independent of the type of dependencies, at least as high as that of counting all grid points in a polytope (P.sub.az) In order to make the optimization problem (50) computationally feasible, in one embodiment, only the dependencies on a selected set of grid points of P.sub.az are considered. Namely, the dependencies incident from the extreme points of P.sub.az. Using only these dependencies in the cost function has the effect of minimizing the distance between P.sub.a (46) and P.sub.az. According to the characteristics of the polytopes in the target domain of problems, the number of extreme points of P.sub.az is a measure for the dimension of the polytope and with that a measure for the number of grid points in the polytope. The same relation between dimension and polytope size were used in determining the order of transformation of node domains (44). Nevertheless, dependencies can be given a weight, which represents the actual number of dependencies between two node domains. To avoid counting grid points a different weighing measure is used. The weight of a dependency is equal to: w=2.sup.DM+n-rank(A.function.) with D.sub.M the dimension of the operation/operand space intersecting polytope belonging to the arc in the graph (39), n the dimension of the common node space (92) and rank(A.function.) the rank of the matrix A.function. of the original node space (46) to operand space mapping function associated with the arc. The reasoning behind this measure is that given the characteristics of the target problem domain, the actual number of single signal instance dependencies from a single node domain (46) for different arcs in the graph (39) relate approximately as h to the power of the dimension D.sub.arc of the polytope enclosing the operations that are involved in the dependency given by an arc. The constant differs from polytope to polytope. Because polytopes are placed one at a time, this constant may be set to a value larger than 1. The dimension D.sub.arc is given by the dimension of the operation/operand space intersecting polytope corrected possibly enlarged by a broadcast. The dimension of the broadcast is n-rank(A.function.). The set of extreme points P.sup.E.sub.az of the polytopes P.sub.az are constant in the optimization problem (50) because they are related to already placed polytopes (47). The set of corresponding grid points P.sup.E.sub.za in P.sub.a is identical to the set of extreme points P.sup.E.sub.a of P.sub.a. If p .epsilon. P.sup.E.sub.az corresponds to x .epsilon. P.sup.E.sub.a then the redefined optimization function is: minimize: ##EQU3## with y=Ax+b. If d.sub.i.sup.k =(p.sup.k -y.sup.k).sub.i then this function can be written as: minimize: ##EQU4## The max(d.sub.i.sup.k, -d.sub.i.sup.k) function replaces the absolute value function with, of course, the same result. The optimization function can be rewritten again by specifying m.sub.ki =max(d.sub.i.sup.k,-d.sub.i.sup.k) which leads to .SIGMA..sub.k .SIGMA..sub.i. w.sub.i.sup.k m.sub.ki The variable m.sub.ki can be expressed by linear inequalities of integer variables as follows: ##EQU5## The linear expressions are linked to the constraints in the following way: ##EQU6## Each individual node domain transformation has a constraint set. In one embodiment, a linear ordering constraint (54) is used within the placement optimization (50) to ensure the existence of executable code when completed. This is the linear ordering constraint, as known in systolic array design: .E-backward..PI.,.A-inverted.d .epsilon.D:.PI.d.gtoreq.0, with .PI. a row vector in the common node space (92) and D the set of all dependencies in that space. In one embodiment, constraints are also redefined for both single node domain transformations (86) as well as the relations between node domain to transformations. All constraints are expressed in terms of linear constraints (54) in order to arrive at a description suitable to be solved by standard Integer Linear Programming (ILP) techniques. Constraints are also imposed (54) on the transformation matrix (86). The characteristics of the node domains (46) and the optimal transformations (86) warrant the application of limited unimodular transformation matrices. First of all, the affine function f(x) is in practical cases bijective over Z.sup.n on the complete lattice, and not just over the node domains (46 in 39). This leads to the following advantages: 1. Each non redundant face and each extreme point of a node domain (46) are non redundant faces and extreme points after transformation (86). 2. The complexity of the constraints on f(x) is independent from any specific characteristics of the node domain (46) to be transformed. These type of transformations are called lattice invariant. The grid points of a node space N are given by the set {x .epsilon.Z.sup.n }, with n the dimension of the space. In general, the set L(B)={y .epsilon.R.sup.m : y=Bx,.times..epsilon.Z.sup.n }, where B is an m.times.n integer matrix, is called the lattice generated by the columns of B. The set of grid points of a node space is therefore the lattice generated by the columns of the identity matrix. If a transformation is given by an n.times.n integer matrix C, with .vertline.detC.vertline., then L(BC)=L(B), see Nemhauser, ibid. Matrices which comply with this constraint are called unimodular. The transformation matrix used is in practical cases also restricted as follows. The limitation for each coefficient a.sub.ij is that -1.ltoreq.a.sub.ij .ltoreq.1. The advantage of using this limitation is the restriction in the search space size. The search space size is also constrained (54). Given the similar depending faces of two node domains (46), the placement (50) of a node domain (46) is constrained by only a single face per placed node domain (47). The combination of these constraining faces form a polyhedral in which the transformed node domain (46) must lie. The problem is now how to extract a set of valid polyhedral constraints (54) from the faces of the already placed node domains (47). This is achieved by the initial constaint set extraction (54) and the constraint set update (84) steps. A set of constraints is valid if the polyhedral defined by this set is non empty. Two constraints are said to exclude each other if they do not form a valid set. In extracting valid sets of constraints (54), the following observations are made: 1. A set of constraints is valid if the resulting solution space, intersects with the span of each constraint. The span of a constraint is the face from which it is derived, extended perpendicularly outwards from the node domain. 2. A constraint overrules another constraint if the corresponding face-inequality of the first holds for all elements of the face of the second. All valid constraints (54) are derived from a constraint graph (52) G.sub.c =(V.sub.c, E.sub.c, E.sub.on). Constraint graph (52) is built stepwise as node domains (46) are placed in the common node space (47). Constraint graph (52) is a directed graph where each vertex represents a constraint given by a face of a node domain (46). Each vertex v .epsilon.V.sub.c is associated with: 1. A linear constraint -e.sub.i x.gtoreq.-b.sub.i if the corresponding face is defined by e.sub.i x.gtoreq.b.sub.i. 2. A subset P.sup.E.sub.i of the set P.sup.E containing all extreme points of the node domain (46), for which P.sup.E.sub.i ={y .epsilon. P.sup.E : e.sub.z y=b.sub.i } This set determines the span of the constraint. There is an arc (v,w) .epsilon. E.sub.c from v to w if and only if w does not exclude or overrule v. Each arc is labeled with a boolean indicating whether the arc is on or off. The boolean is on if the polyhedral formed by the two constraints has an inner point (node domain is not empty), otherwise the boolean is off. If an arc a is labeled on then a .epsilon. E.sub.on, which leads to E.sub.on .OR right.E.sub.c. Using this specification of a constraint graph G.sub.c (52), a valid set of constraints is extracted (54). A setV.OR right.V.sub.c. constitutes a valid polyhedral constraint if and only if: 1. V.sub..nu., w.epsilon.V, .nu..noteq.w: {(.nu.,w,), (w,.nu.)}.OR right.E.sub.on 2. There is no clique Q such that V.OR right.Q. The first item indicates that a valid polyhedral constraint consists of a subset of vertices of V.sub.c where each vertex has an arc to each vertex. Furthermore, each arc must be on. A valid polyhedral constraint can also be described as a clique in the graph G'.sub.c =(V, E.sub.on, 0). The second item says that the set of vertices representing the polyhedral constraint cannot be part of a larger clique in G.sub.c. Each polyhedral constraint is represented by a constraint matrix C and constraint vector c. If the set of extreme points of a node domain to be transformed P.sub.a (46) are P.sup.E.sub.a then the constraints can be specified as: x.epsilon.P.sup.E.sub.a : Cx.gtoreq.c. The actual solution of the optimization problem (50) formulated above for a single node domain (46) is now partitioned into solving two sub-problems: 1. Solving the coefficients (A and b in the transformation (86) Ax+b) by a branch-and-bound technique (72). An efficient technique to solve the placement optimization (50) problem makes use of the structure of the problem in its solution space search and will efficiently implement the constraint resolution and optimization function evaluation. The unimodularity constraint can not so easily or efficiently be implemented by linear constraints on integer variables. A general Integer Linear Programming (ILP) formulation is therefore not attractive. A branch-and-bound method (72) is more appropriate because the following essential branch-and-bound features are present in the problem: (a) A structured division of the search space. (b) An accurate and fast lower-bound calculation on the minimal reachable cost. (c) A dominance test between individual partial solutions. See generally P. H. Winston, "Artificial Intelligence", Addison-Wesley, Reading, 1984. Each single coefficient of a dependency vector adds to the overall cost of a solution. These coefficients correspond to the projection of a dependency on the orthonormal base vectors of the common node space (92). A natural division of the search space is therefore by base vector. Lower-bound calculations and dominance test are essential in making branch-and-bound more efficient than a simple enumeration of the search space. The lower-bound cost estimates cut out partial solutions whose costs increased by the lower-bound estimates on the remainder of the solution is higher than the to best solution found so far. The dominance relation test cuts out redundant paths in the search tree. See generally P. H. Winston, "Artificial Intelligence", Addison-Wesley, Reading, 1984. 2. Solving the b coefficients by an ILP formulation. ##EQU7## The absolute value function on the dependency lengths of the optimization problem (50) is expressed in linear programming terms by splitting each coefficient of each dependency vector d.sub.ki into a positive d.sub.i.sup.k+ and negative d.sub.i.sup.k- variable, whose values are always positive and whose sum gives the absolute value of their corresponding coefficient. The set E represents the set of extreme points of the polytope to be transformed (46). The matrix A is given as a result of the branch-and-bound algorithm (72). The set D represents those dependencies that are selected by the data routing estimation procedure (58). The resulting integer programming problem can be solved with a general ILP solver. The solution space search of the ILP-solver can be sped up substantially by providing a upper bound on the optimal cost. The cost of the initial guess as well as the costs of the best transformations so far are used for this. The general formulation and the principle solution approach are discussed above. Now, the different steps in the flowchart of FIG. 5 are explained in detail. The linear constraint sets extraction and ordering step (54) has input of a constraint graph of the common node space (52) and the set of extreme points mapped by the appropriate affine dependence functions to the already placed node domains in the common node space (47). This step (54) selects all valid polyhedral constraints by finding all maximal cliques. Finding the maximal clique is a problem that can be solved by standard algorithms that are generally available. Also a list of graph nodes is kept that are not involved in any correct constraint set. This list of nodes is excluded from future clique searches to increase the efficiency of the clique search. A collection of polyhedral constraints is output. Next, each of these constraint sets is considered one at a time in the order derived above (56). First, the data routing step (58) is performed for the given constraint set (56). The communication scheme between node domains (46) in the node space is described in the annotated PDG (39). This communication scheme can often be changed without changing the overall behavior of the code represented. Exploiting the broadcast of signal instances is one way of changing the communication scheme. If an operation needs a certain signals instance as operand then it may obtain this instance directly from the operation that generated it. This is represented by a dependency between the consuming and producing operations. These dependencies are represented in the annotated PDG (39). However, the same signal instance may be obtained from another operation that uses the same instance as operand. The idea is that an operand is passed on from operation to operation. This technique is explicitly used in "localization" for array synthesis. The localization technique is aimed at dependencies within node domains (46) and not between polytopes. Selection of a certain localization at node domain level is done as follows: 1. select for a node domain (46) only those dependencies from or to other node domains (46), which are already placed in a common node space (47). 2. select for the given constraint set (56) that node domain interconnection scheme for the selected dependencies for which the operand source points are closest to the constraining hyperplanes. The data routing step involves several calculations such as mapping the extremes (starting and ending points) of the polytopes in PDG (39); finding the minimal extreme dependencies; selecting an ordered collection of ending points; and computing an absolute lower bound dependency cost. Thus, the extremes are mapped for each arc in the PDG (39) from the node domain to be placed (46) to an already placed node domain in (47) by: 1. Selecting the extreme points of the intersection of operand space and operation space node domains (see FIG. 12) belonging to the given arc. 2. Mapping the extreme points back to the node space node domain of the node domain to be placed (46). Mapping the extremes points back to the already placed node domain (47). From this, dependency starting points and dependency ending points (points belonging to set of placed node domains(47)) are output. PDG arcs in (39) indicating, per dependency, from which arc it is derived is also output. Arc-information is used later to determine the direction of the dependency and the number of signal instances involved with it. The minimal extreme dependencies are then derived. Input is a set of dependency starting points belonging to the node domain to be placed (46), a set of dependency ending points belonging to a placed node domain (47), unplaced polytopes (39), and placed polytopes (47). A set of dependency ending points, which extends the given set by other possible ending points belonging to operations that use the same signal instance as an operand is derived by checking for each operand space, corresponding to a placed node domain (47), if the same signal instance(s) is (are) used. Each such operand space point is mapped back to the placed node domain in the common node space (47). This point is also added to the set of ending points. Next, an ordered collection of ending points is derived from a set of dependencies, a set of constraints, and an ordered collection of sets of dependency ending points. Select for each set of ending points that point p that has the minimal positive distance to one of the constraining hyperplanes. If a constraint is specified as, Cx.gtoreq.c, then the distance is expressed as c-Cp. If the original ending point has minimal distance then this point is preferred over others with the same minimal distance. Finally an absolute tight lower bound computation is made to reduce the search space. The input is: dependency starting points, dependency ending points, dependency weight sets, and the given constraint set (56). For each set a weighted total distance figure is calculated as dist.sup.k =A.sub.pk w.sup.k (1+c-Cp.sup.k), with w.sup.k the weight associated with the dependency. Only those distances are summed which are positive. The points p belong to the ending-point set for a specific constraint set. For each set of start and ending points a figure is calculated indicating the expected lowerbound cost related to shape-mismatch between start point and end points. For each point startpoint q.sup.k and corresponding end point p.sup.k the mismatch is calculated as mism.sup.k =w.sup.k .vertline.min.sub.i (p.sup.k.sub.i -p.sup.o.sub.i)-min.sub.i (q.sup.k.sub.i -q.sup.o.sub.i).vertline.. In this equation p.sup.o is a reference start point from the set and q.sup.o the corresponding reference end point. The maximum of dist.sup.k and mism.sup.k is the expected lowerbound dependency cost for the given constraint set with starting and ending points. It is then determined if this is the best reachable solution (60). Given the starting and ending dependency points with weights and a current minimum dependency length cost, a boolean indicating if the minimum is reachable is output. The row of the transformation matrix A at which minimum is exceeded is also output. For each pair of starting and ending points q.sup.k and p.sup.k the sum: .SIGMA..sub.i w.sup.k (1+.vertline.q.sup.o.sub.i -q.sup.k.sub.i- p.sup.o.sub.i+ p.sup.k.sub.i .vertline.) is calculated. This sum is row-wise, starting at the top row, calculated. As soon as the intermediate result exceeds the given minimum then false is returned with row=i. Thus, it is not needed to continue with this constraint set and the next constraint set is retrieved (56). This pruning step is very effective because otherwise, actual placement of the node domain would be performed which is very time consuming. Referring to the flowchart of FIG. 6, the actual placement (62) of a node domain (46) is performed by using an initialization step (64) and a branch and bound step (72). The branch-and-bound method needs an initial cost to start with. The initial (best so far) transformation matrix is the identity matrix (66). Solving the problem of finding the translation vector with minimum dependency length cost (68) will establish the best minimum dependency length cost and best maximum total cone angle so far. A constraint set (56), starting points and ending points, and a weight set (58) are used to derive the minimum dependency length cost so far with corresponding best transformation (70). Using a branch-and-bound technique (72) the search space of transformation matrices is enumerated in a row by column fashion (74). In the preferred embodiment, matrix coefficients are limited to {-1,0,1}. Enumeration can be represented by a tree, in which each node represents a chosen value of a coefficient and from which branches out in as many different parts as their are choices of for the next coefficient (3 in this case). Enumeration is limited to small sections of the search space by cutting of branches of the enumeration tree as close as possible to the initial node. The goal is to minimize the number of times to solve an ILP-problem (80) while retaining the optimal solution. Two different types of nodes can be distinguished in the enumeration tree. The first type branches to a coefficient in the same matrix row. The second type ends a row and branches to a coefficient of a next row (78). Branch cutting will be done at the second type of node. The cost function of the placement optimization (82) contains three optimization components: minimum dependency length, dependency variancy and minimum dependency angle (or search space). Given the current transformation with its dependency length, dependency variancy and dependency angle and the best transformation thus far with its dependency length, dependency variancy and dependency angle, the best transformation Ax+b is selected (82). Of all transformations for all constraint sets as derived by implicit enumeration, that one is chosen as best which minimizes the maximum total cone angle, or has an maximum total cone angle at least as small as any other transformation and the smallest total dependency length cost. User interaction (34) is also possible by overruling the above described default costs, by respecifying the weight of the three cost parameters. In each step of the branch and bound step (72), the transformation matrix A so far (84), the minimum dependency length cost so far (70), the row and column indicating the coefficient to be modified (74, 78), the constraint set (56), starting and ending points, weight set, (as calculated above) and the best transformation so far (82) serve as input to the ILP solver. The output is a row at which dependency length cost is exceeded (74) (if this row=n then cost has not been exceeded) and a new minimum dependency length cost so far with corresponding best transformation (82). Thus, the branch and bound step (72) is procedurally defined by: if all coefficients are set (row=n) then: If matrix A is unimodular and current minimum dependency cost is in reach then: Solve the ILP-problem of finding the translation vector b with minimum weighted dependency length cost (call to a general ILP solver) (80). If resulting cost is lower than current minimum then: Set new minimum cost, retain this transformation as best so far (82). Else, determine at which row, starting from the top, the minimum cost is exceeded. Return this row number. Else, return with row=row of matrix at which cost is exceeded, starting from the top row. Else: 1. Set coefficient A(row, column) to -1. Recursively call this function for next coefficient. If returned row is lower then this row then return that row, otherwise: 2. Set Coefficient A (row, column) to 0. If present row is not a null row then recursively call this function for next coefficient (only checked when column=n). If returned row is lower then this row then return that row, otherwise: 3. Set coefficient to 1. Recursively call this function for next coefficient. Return the returned row. Referring back to FIG. 5, after a node (46) is placed (62) the constraint set (52) is updated (63). A collection of constraint sets with starting and ending points, weight sets and the dependency cone of the total of the placed node domains (52) is input. A re-ordered collection of constraint sets is output (63, 52). First calculate for each constraint set (52) the expected resulting maximum angle in the total dependency cone after placement of the node domain (62). Each hyperplane vector of a set of constraints is added positively to the existing dependency cone if there exists a dependency indicating data flow from the placed node domains (47) to the polytope to be placed (46). Otherwise, these vectors are added negatively. If both type of dependencies exist, only the positive additions are made. For the resulting cone the maximum cone angle between any two dependencies in the cone is calculated. Two sets of constraints S.sub.a and S.sub.b, with order(S.sub.a)<order(S.sub.b), in the given ordering exchange their ordering position if either: 1. The expected lowerbound dependency cost S.sub.a is higher than that of S.sub.b, or: 2. The expected lowerbound dependency costs are equal, but the expected maximum cone angle for S.sub.a is larger than that of S.sub.b, or: 3. Both expected lowerbound dependency costs and expected maximum cone angles are equal, but the node domain to be placed is already complying to S.sub.b. Summarizing, the placement or mapping step (40) is the following: 1. Order node domains for placement (44). 2. Select next node domain in ordered set (46). 3. Extract constraint sets (54). 4. (a) Select next best constraint set (56). (b) Select for this constraint set (56), the `best` internode domain communication (58). (c) Calculate for the constraint set the expected lowerbound dependency cost and the maximum dependency cone angle (60). If the expected lowerbound dependency cost and the weighted ending point to constraining hyperplane dependency costs are lower or equal to the current minimum dependency cost, and the expected maximum dependency cone angle is lower or equal to the present best maximum cone angle then continue ("yes") to step 4(d) (62), else go to step 4a (56) ("no"). (d) Heuristically select an initial transformation matrix (66) and solve the ILP problem for the translation vector (68). This transformation sets a minimum dependency length cost and maximum cone angle (70). (e) Implicitly enumerate over transformation matrix search space, using current minimum dependency length cost as bound to reduce the search space (72) until all transformations have been tried out (84). Keep that transformation which has the smallest maximum dependency cone angle or a lower dependency length and a maximum cone angle at least as small as that of others (86). (f) Update the constraint set descriptions (63) and continue at step 4a (56) until all constraint sets are processed and until a best transformation matrix Ax+b has been found (61). 5. Continue at step 2 until all node domains are placed (46). Referring to FIG. 7, the order of the placed PDG (92) is optimized (100). An ordering vector .PI. maps a n-dimensional space (92) to a 1-dimensional ordering axis. This mapping or transformation (112) is based on the fact that the operations in the placed PDG (92) are represented by the lattice elements of bounded polyhedra. Because of this, .PI. can be decomposed into an ordered set of linearly independent row vectors {A.sub.1, A.sub.n } such that for each pair of points x, y from the common node space of the PDG (92) the following relation holds: if A.sub.i x<A.sub.i y then .PI.x<.PI.y. Furthermore, if x-y=.lambda.A.sub.i and x-z=.mu.A.sub.j with i>j then .PI.x<.PI.z. In other words, operations are first ordered along the direction of A.sub.n followed by A.sub.n-1 etc. In terms of procedural code, the direction of A.sub.n corresponds to the most inner loop of a body, while that of A.sub.1 corresponds to the most outer loop. The ordering vector .PI. can, therefore, be calculated by defining the order of directions in which the operations are best executed. The goal of order optimization problem (100) is to find an ordering vector .PI. that corresponds with a minimal signal storage requirement when executing the transformed specification description (150). The key idea is that whenever all dependencies have the same direction, then ordering the execution of operations in this direction minimizes the storage requirements. Therefore the problem is to find new base vectors (108) which correspond to an ordering that follows these maximum dependency directions. Thus, a dependency cone computation is made (102). This is a collection of all intra- and inter-dependency vectors of the placed PDG (92). All dependencies in the placed PDG (92) are projected (194) on the dependency cone rays (102). All dependency costs are accumulated to calculate a projection cost (104). For each dependency cone ray r.epsilon.C, calculate: ##EQU8## A dependency cost for each dependency cone ray is calculated and the maximum cost is derived (106). Rays are selected that are linearly independent by selecting the ray with the highest R(r) and adding linearly independent rays in order of highest R(r). The number of selected rays m is smaller or equal to n, the dimension of the common node space (92) in which the dependencies are defined. The m selected rays r.sub.i ; form the rows of the selected ray base X: ##EQU9## The base computation (108) computes the closest unimodular base transformation. The selected ray base (106), all dependencies from the placed PDG (92), and possibly user-defined constraints (110) are input and a unimodular base transformation is output (108). The problem is solved by a general ILP solver. The problem is formulated by the following optimization problem: ##EQU10## The ordering vector .PI. is calculated as: ##EQU11## The base vectors of A are derived from the rays of the cone of the dependencies, since the ordering vector must have a positive component along each dependency vector. The sum of the inner products of the dependencies on a ray gives a measure for the length and number of those dependencies that have a component in the direction of that ray. The base vectors are formed by linearly independent rays with the highest inner product sums. These base vectors may not set up the complete dimensional space, or may not form a unimodular matrix. Unimodularity is used here to preserve placed PDG (92) characteristics after transformation (112) of the PDG by A. The formulation of creating a unimodular A describes that the larger the weight for a base vector, the more important it is for the corresponding row of A to equal it. The unimodular base transformation matrix A (calculated in 108) is used to transform (112) all node domains of the placed PDG (92) to an ordered PDG (118), in which each dimension can be directly interpreted as a nested loop in a procedural code. .PI. is found as indicated above. Additionally, signal life times per signal, window per signal (size) and the maximal number of signals are calculated (114) for all signals in the ordered PDG (118). These characteristics of the ordered PDG (1 18) are used as memory directives (116) when compiling (164) the optimized code (150) into computer code for further compilation (166) into the target machine code (168). Basically, at all the extreme points of the ordered node domains located in a common node domain (118), the number of integer points within polytopes, that represent the difference of produced and consumed signals, are counted. An efficient algorithm based on Fourier-Motzkin elimination is used, see, for example, F. Balasa, F. Catthoor, H. De Man, "Optimal Evaluation of Memory Area for Multi-dimensional Processing Systems", accepted for IEEE Int. Conf. Comp. Aided Design, Santa Clara Calif., November 1993. The maximal number of signals over the complete time interval is also computed. Referring to FIG. 8, the transformation script (120) consists of transformations such as affine transformations (132), N-dim-body merge transformations (140), and total-body-split transformations (140) among other transformations (144). These transformations (described below) are applied to the selected code (16) in the transformation engine (130) according to transformation script (120) to produce optimized selected code (149). Optimized selected code (149) is then combined with the original code (12) to produce optimized code (150). Transformations are read (184) and applied to the selected code (16) until no more transformations exist (148) in the transformation script (120). The affine transformation (134) performs a unimodular affine transformation on the selected code (16). For example, given the initial Silage code: ##EQU12## with x=(ij).sup.T and A.sub.s x+b.sub.s, A.sub.T x+b.sub.T affine 2 dimensional index expressions. The correct Silage description of signal S is: S[A.sub.S.sbsb.11 i+A.sub.S.sbsb.12 j+b.sub.s.sbsb.1 ][A.sub.s.sbsb.21 i+A.sub.s.sbsb.22 j+b.sub.s.sbsb.2 ]= The factors n.sub.sk, v.sub.skl, n.sub.ck, V.sub.ckl are constants. Notice that the loop bounds can be described by two sets of inequalities: V.sub.s x.gtoreq.n.sub.s, V.sub.c x.ltoreq.n.sub.c with, for example, V.sub.s x.gtoreq.A.sub.s as: ##EQU13## The condition is expressed as Cx.gtoreq.c with C a m.times.n matrix, with m the number of conjunctive inequalities. The correct Silage syntax (for n=2) is: if (C.sub.11 i+C.sub.12 j.gtoreq.c.sub.1 & . . . & C.sub.n1 i+C.sub.n2j .gtoreq.c.sub.m) The affine unimodular transformation y=Ax+b is applied to the initial description (y=(i'j').sup.T and det(A)=.+-.1): ##EQU14## Note that the transformed index expressions can directly substitute the original ones. Less obvious is the derivation of the resulting syntax for the loop bounds. Loop boundary matrices have a special format, as shown in the first section. The resulting matrices V'.sub.s and V'.sub.e do not necessarily have this format (if they do, they can directly substitute the original expressions in the loop boundaries). Furthermore, there's the problem of optimizing the set of conditions (redundant condition removal, etc.). ##EQU15## The min and max functions return the minimum and maximum value that an iterator takes within the given conditions. The unimodularity of the transformation matrix ensures that each set of integer values for (i'j') that lies within the transformed set of conditions has one and only one equivalent point (ij) in the original construction. If the loop structure is unrolled, and the index expressions evaluated, the resulting set of assignments is identical to that which is found by unrolling the original Silage code construction. Although the index expressions have changed, the actual indexing remains unaltered. An example of a loop interchange transformation is given: ##EQU16## The description can be represented by the following matrixes ##EQU17## In this example the condition matrix does not exist. When we apply a loop interchange transformation the following transformation matrix is used: ##EQU18## After doing the matrix multiplications: ##EQU19## V.sub.E and V.sub.S have to be rewritten in diagonal form. The resulting Silage description is derived: ##EQU20## In a total-body-split transformation, all statements in the body of a loop are split. A body with N statements will result in N loops with one statement. This is done for all loops in the description. ##EQU21## An N-dim-body-merge transformation takes together two loops in one new loop. The two loops are allowed to be more dimensional (nested) loops. The bodies of the two original loops are taken together as one new body. Conditions are added to the original bodies such that it is executed only for original values. In case of merging two N dimensional loops the result will be one N dimensional loop containing the two bodies. Special care has to be taken to adjust the index names in the loop bodies. ##EQU22## Referring to the flowchart of FIG. 10, in one instantiation of the invention, the transformation engine (130) is embodied in a program called SynGuide which is run in batch mode (180) as it reads (184) the transformation script (120) and applies the transformations (132-148) to the description specification (16). The process shown in FIG. 10 can also be used in selecting (14) the code to be optimized (16), and for editing (196) the original specification description (12) in the specification environment (10). Actions are performed until no more actions are specified (200) by either the script (184) or the user (34), and the system exited (400). FIG. 11 illustrates one embodiment of an apparatus embodying the present optimizer invention shown in FIG. 1. Computing system (210) may variously contain a processor (214), memory (216), storage (217) unit, and user interface (34). Computing system (210) may be any conventional computer system, personal computer, or workstation. Processor (214) can be any conventional central processing unit (CPU), and may be connected to other processors in serial or parallel or via a conventional network. Processor (214) operates according to a conventional operating system of the computing system (214). Processor (214) is variously coupled to memory (216), and storage (217), for example, via a conventional bus system. Memory (216) and storage (217) may also be coupled via a conventional bus system. Memory (216) can be any conventional electronic memory device including any hierarchical memory structure including physical memory, virtual memory or swap disk memory, and/or mass storage. According to the invention, memory requirements (216) are significantly reduced, thus memory swapping (219) (from physical memory (216) closely associated with the processor (214)) to other types of memory (e.g., virtual memory, swap disk, etc.) is minimized and the application program execution time significantly decreased. Storage (217) may be any conventional storage device for storing electromagnetic signals such as a hard disk, mass storage unit, and/or possibly a swap disk for temporal storage of the internal memory (virtual memory) (219). Within the memory (217) and/or storage (216), resides the computer code for optimizer (20) and transformation engine (130), and data for the application to run. Optionally, simulator (160) and specification environment (10) may be co-located in the same computing system (210). User interface and user interface software (34) may variously comprise conventional user interface components such as a mouse, keyboard, batch files/computer code, touch screen, and/or monitor, and is connected to the computing system (210) via conventional input/output channels. The connections between the various modules (10, 20, 130, 160) in the embodiment of the invention illustrated in FIG. 11 are only representative. Actual data transfer and connection is preferably performed according to instructions issued from the processor (214) and uses memory (216) as an intermediate step. The specification code (14) is sent to the transformation engine (130). The code to be optimized (16) is sent to the optimizer (20). The optimizer produces a transformation script (120) which is used by the transformation engine (130) to produce optimized code (150). The optimizer (20) also produces memory directives (116) which are given to the simulator and/or compiler (160, 162). Memory directives (116) and optimized code (150) are used to generate optimized code in a target machine code language (162, 164). The latter contains instructions which are then executed on the processor (214) to simulate the application data. This data generally initially resides in storage (217), but are gradually entered into memory (216) to be processed (214) and returned to storage (217). One of the main purposes of the invention is to reduce the amount of data to transfer/exchange between the storage (217) to the memory (216), thereby reducing the swap time. Below is an example application of the present invention on a simplistic digital system design. The basic flow of the problem and solution is presented. The example scenario uses one embodiment of the invention which takes Silage code as input and has software components known as MASAI (the optimizer (20)), SynGuide (the transformation engine (130) and code selection (14)), and S2C (for software compilation (162)). The example herein is not intended to limit the scope of the claims in any way. First a conventional scenario using standard practices is described. The system application description is a simple basic subtask that could be part of a complex digital signal processing system design. The input is a two dimensional signal MATR which has N rows and M columns. N and M are parameters which should be instantiated before starting the simulation and optimization. The function to perform in the subtask is to sum up all the values appearing in a matrix row, and this for each row. Next, each of these row sums is accumulated to produce a final sum SUM[N]. The resulting value is also the output OUT of the subtask. Silage code (or any other data-flow specification language) could be written to represent behavior of a design with the above described functionality as depicted below.
______________________________________
01: func main (matr: fix<64,0>[N+1][M+1]) out: fix<64,0> =
02: begin
03: sum[0] = fix<64,0>(0);
04: (i : 1 . . . N) :: col[i][0] = fix<64,0>(0);
05: (i : 1 . . . N) ::
06: (j : 1 . . . M) ::
07: col[i][j] = col[i][j-1] + matr[i][j];
08: (k : 1 . . . N) ::
09: sum[k] = sum [k-1] + col[k][M];
10: out = sum[N];
11: end;
______________________________________
After instantiation for e.g. N=10000 and M=10, the code below is produced.
______________________________________
01: func main (matr: fix<64,0>[10000 +1][10 +1]) out: fix<64,0> =
02: begin
03: sum[0] = fix<64,0>(0);
04: (i : 1 . . . 10000 ) :: col[i][0] = fix<64,0>(0);
05: (i : 1 . . . 10000 ) ::
06: (j : 1 . . . 10 ) ::
07: col[i][j] = col[i][j-1] + matr[i][j];
08: (k : 1 . . . 10000 ) ::
09: sum[k] = sum[k-1] + col[k][10 ];
10: out = sum[10000 ];
11: end;
______________________________________
In order to be able to simulate the behavior of the initial Silage code on a workstation, the compiled code simulator S2C (162) is used. S2C generates a C program that has an equivalent behavior as intended by the Silage code with N=10000 and M=10. The produced C code is then compiled with a C compiler (166). The resulting program (executable) (168) is then executed in order to simulate the Silage code for a given set of input stimuli (not shown here). If S2C is invoked with the option -i (for inplace mapping), the multi-dimensional signal "col" requires 10000 storage locations as shown in the output below.
______________________________________
beluga 231 > s2c -fi matr.sub.-- sum
Parsing.
Signal Flow Graph Construction.
Manifest Bounds Calculation.
Type Deduction.
Conditional delay check.
Symbolic Simulation.
Checking of the delay's.
Inplace Reduction.
In function main there are 110011 scalar alive at startup.
Maximum needed scalars for this ordering = 10001
Nr. of scalars still alive (outputs) = 1
. . . in function main
Array col Max. Alive = 10000
Array sum is reduced to a scalar.
Process Partitioning.
______________________________________
In practice N may have been much larger. Generally, when N is increased, more signals need to be stored by the simulator, thus the required (physical) memory increases drastically. For very large values of N (typically above a few hundred thousand) this leads to an infeasible simulation run due to the lack of physical memory. The declaration of variables to store the content of the signals of the design is listed too:
______________________________________
Sig.sub.-- Type col.sub.-- 7[10001][11],
sum.sub.-- 9[10001];
______________________________________
An excerpt of the C program simulating the initial design without optimization is listed below:
__________________________________________________________________________
01: FixAssign (c11, sum.sub.-- 9[0]);
02: for (i.sub.-- 8=(1); i.sub.-- 8<=(10000); i.sub.-- 8++) {
03: FixAssign (c10, col.sub.-- 7[i.sub.-- 8][0]);
04: }
05: for (i.sub.-- 6=(1); i.sub.-- 6<=(10000); i.sub.-- 6++) {
06: for (j.sub.-- 5=(1); j.sub.-- 5<=(10); j.sub.-- 5++) {
07: FixPlus (col.sub.-- 7[i.sub.-- 6][j.sub.-- 5-1)], 64,0,matr.sub.--
2[i.sub.-- 6][j.sub.-- 5], 64,0,
08: col.sub.-- 7[i.sub.-- 6][j.sub.-- 5], 64,0);
09: }
10: }
11: for (k.sub.-- 4=(1); k.sub.-- 4<=(10000); k.sub.-- 4++) {
12: FixPlus (sum.sub.-- 9[(k.sub.-- 4-1)], 64,0, col.sub.-- 7[k.sub.--
4][10], 64,0, sum.sub.-- 9[k.sub.-- 4], 64,0);
13: }
14: FixAssign (sum.sub.-- 9[10000], (*p.sub.-- out.sub.-- 3));
__________________________________________________________________________
The order of the calculations in the code above is the same as that of the initial description. In other words, the order of execution is lexicographical, i.e., the order of definitions in the Silage description is the same as the order in the C code. However, if the order of execution is optimized by manipulating the control flow, memory requirements for simulation can be reduced. This is realized with the present invention as embodied in a combination of the optimization environment MASAI and the transformation environment SynGuide. First, the initial Silage description is giving as input to SynGuide. There, the relevant part of the code for optimization is selected. In this simple example it is assumed that this is the entire code. This selected Silage code is then sent to MASAI. Running MASAI will lead to the following output which is explained below.
______________________________________
> masai -T -P -v matr.sub.-- sum > x
Loading LIB (oprs-opns) from:
/usr/nfs/daphne.sub.-- users/vsdm/petroni/cathedral/LIBs/
mpLIB.sub.-- v0/bin/DECRISCbin/mpLIB.sub.-- v0.dat
Checking presence of predefined LIB operators.
Checking presence of predefined LIB operations.
Reading DSFG from: matr.sub.-- sum.sfg
Warning: input without stl: matr.sub.-- 2 inp typ=(int tc 64) ran=(10001
11 )
scp=(main);
Warning: output without stl: out.sub.-- 10 typ=(int tc 64) sik=out
Starting classification
Starting classification of Signal Indices
Starting atomizer
Starting signalization
EXTRACTING NODE SPACES FOR SPACE 0 WITH 4 ATOMS
4,3,2,1,
EXTRACTING OPERATION/OPERAND SPACES
4,3,2,1,
SPACE 0 HAS 3 SIGNIFICANT ATOMS.
GRAPH CONSTRUCTION
WRITING DSFG
WRITING PDG
WRITING DAG
NODE SPACE PLACEMENT
Procedural or Optimized placement ? (0/1) : 1
UPDATING NODE ORDERS
PLACE : 0-> Node: 1-> ORDER: 0
PLACE : 1-> Node: 0-> ORDER: 1
PLACE : 2-> Node: 2-> ORDER: 2
Do you want to modify the default node order? (y/n):n
placed: 3,.placed: 2,.placed: 1,
WRITING PLACEMENT RESULT IN CODE
WRITING PLACEMENT PDG
SELECTING PARTIAL ORDERING
WRITING ORDERED RESULT IN CODE
______________________________________
As one of the first steps, a pruning of scalar signals is performed (during the classification). This will lead to the identification of only 3 relevant multi-dimensional signals:
______________________________________
01: (i : 1 . . . 10000 ) :: col[i][0] = fix<64,0>(0);
02: (i : 1 . . . 10000 ) ::
03: (j : 1 . . . 10 ) ::
04: col[i][j] = col[i][j-1] + matr[i][j];
05: (k : 1 . . . 10000 ) ::
06: sum[k] = sum[k-1] + col[k][10 ];
______________________________________
Then the Polyhedral Dependency Graph (PDG) is extracted from this flow graph, leading to three definition domains, and three operand domain polytopes, and a number of affine dependence relations. These are combined in a PDG graph model during GRAPH CONSTRUCTION. The PDG contains 3 nodes. They are umbered from 0 to 2. Each PDG node is attributed with a node space, definition space(s) and operand space(s). The definition and operations spaces are only implicitly used to calculate the affine relation between the nodes. Node 0 is derived from line 01 in code above. The node is attributed with the following node space: ##EQU23## (where I is a two dimensional iteration vector) For clarity, the matrix formula is worked out to obtain the following set of inequalities: ##EQU24## The inequalities are mathematically equivalent to: i.sub.-- 0=0 and 1<=i.sub.-- 1 <=10000 Node 1 is derived from line 3 to 5 in the code above as: ##EQU25## Node 2 corresponds to line 5 to 6 in the code above and has as node space: ##EQU26## There are 4 arcs in the PDG numbered from 0 to 3. All arcs are attributed with an affine relation A*I+B. Arc 0 goes from node 1 to node 0. Attributed affine relation: ##EQU27## Arc 1 goes from node 1 to node 1. Attributed affine relation: ##EQU28## Arc 2 goes from node 2 to node 1. Attributed affine relation: ##EQU29## Arc 3 goes from node 2 to node 2. Attributed affine relation: ##EQU30## Finally, the optimization method is started, including both a polytope placement and a ordering step. The placement can be skipped by interpreting the original code in a "procedural" way or it can be "optimized". In the latter case, the way the polytopes are tackled (one by one) can be steered manually by entering other polytope (node) orderings. The output is shown below.
______________________________________
01: % masai -P -T -v matr.sub.-- sum > x
02: Loading LIB (oprs-opns) from:
03: /usr/nfs/daphne users/vsdm/petroni/cathedral/LIBs/
04: mpLIB.sub.-- v0/bin/DECRISCbin/mpLIB.sub.-- v0.dat
05: Checking presence of predefined LIB operators.
06: Checking presence of predefined LIB operations.
07: Reading DSFG from: matr.sub.-- sum.sfg
08: Warning: input without stl: matr.sub.-- 2 inp typ=(int tc 64)
ran=(10001 11 )
scp=(main);
09: Warning: output without stl: out.sub.-- 10 typ=(int tc 64) sik=out
10: Starting classification
11: Starting classification of Signal Indices
12: Starting atomizer
13: Starting signalization
11: EXTRACTING NODE SPACES FOR SPACE 0 WITH 4 ATOMS
11: 4,3,2,1,
11: EXTRACTING OPERATION/OPERAND SPACES
11: 4,3,2,1,
11: SPACE 0 HAS 3 SIGNIFICANT ATOMS.
11: GRAPH CONSTRUCTION
20:
21: WRITING DSFG
22: WRITING PDG
23: WRITING DAG
24: NODE SPACE PLACEMENT
25: Procedural or Optimized placement ? (0/1): 1
26: UPDATING NODE ORDERS
27:
28: PLACE: 0-> Node: 1-> ORDER: 0
29: PLACE: 1-> Node: 0-> ORDER: 1
30: PLACE: 2-> Node: 2-> ORDER: 2
31: Do you want to modify the default node order? (y/n) :y
32: This PDG contains 3 nodes.
33: Enter for each node number your order number.
34: After each update the dag-file is updated.
35:
36: Give Node number to modify [0 . . . 2]:2
37: Enter new order number for Node: 2:0
38: RE-UPDATING NODE ORDERS
39:
40: Do you want to modify an other node? (y/n):n
41: PLACE: 0-> Node: 2-> ORDER: 0
42: PLACE: 1-> Node: 1-> ORDER: 1
43. PLACE: 2-> Node: 0-> ORDER: 2
44: placed: 3, . . . placed: 2,.placed: 1,
45: WRITING PLACEMENT RESULT IN CODE
46: WRITING PLACEMENT PDG
47: SELECTING PARTIAL ORDERING
48: WRITING ORDERED RESULT IN CODE
______________________________________
As shown in the screen output above, at line 31 the question "Do you want to modify the default node order?" is answered affirmative. In line 36 and 37, one can see the designer specified that she/he wants to change the order of node 2 to 0. This means that node 2 will now be placed first. This is made clear in the updated ordering from line 41 to 43. MASAI generates a list with transformations that manipulate the control flow. This file is shown below:
______________________________________
01: Open("matr.sub.-- sum.sil","program","No")!
02: doselect("iterator","1")!
03: dotrans("total.sub.-- body.sub.-- split",0," ")!
04: doselect ("iterator","2")!
05: dotrans("affine",6,"1 0 0 1 0 0 ")!
06:
07: doselect ("iterator","1")!
08: dotrans("affine",6,"1 0 0 1 0 0 ")!
09:
10: doselect("iterator","3")!
11: dotrans("affine",6,"1 0 0 1 0 1 1 ")!
12:
13: doselect("iterator","2")!
14: dotrans("affine",6,"1 0 0 1 -1 0 ")!
15:
16: doselect("iterator","3")!
17: dotrans("affine",6,"1 0 0 1 -1 0 ")!
18:
19: doselect("iterator","1")!
20: dotrans("affine",6,"1 0 0 1 -1 0 ")!
21:
22: doselect("iterator","1")!
23: dotrans("total.sub.-- body.sub.-- merge",2,"2 3")!
24: Save.sub.-- as("Text","matr.sub.-- sum.sub.-- out.sil");
______________________________________
The transformations listed in above are sent to the tool SynGuide (transformation engine (130) and one by one executed by it. The resulting optimized Silage code is shown below:
______________________________________
01: func main(
02: matr:fix<64,0>[10001][11])
03: out:fix<64,0> =
04:
05: begin
06: sum[0]=fix<64,0>(0);
07: i : 0 . . . 9999)::
08: begin
09: (T0 : 0 . . . 11)::
11: begin
12: col[i + 1][0] = if (T0 == 0)
13: ->fix<64,0>(0)
14: fi;
15: col[i + 1][T0] = if ((10 >= T0) & (T0 >= 1))
16: ->col[i + 1][T0 + -1] + matr[i + 1][T0]
17: fi;
18: sum[i + 1] = if (T0 == 11)
19: ->sum[i] + col[i + 1][10]
21: fi;
22: end;
23: end;
24: out= sum[10000];
25: end;
______________________________________
The optimized Silage code above is translated to C with the simulator compiler S2C. The output of the translator is given below:
______________________________________
>s2c -fi matr.sub.-- sum
Parsing.
Signal Flow Graph Construction.
Manifest Bounds Calculation.
Type Deduction.
Conditional delay check.
Symbolic Simulation.
Checking of the delay's.
Inplace Reduction.
In function main there are 110011 scalar alive at startup.
Maximum needed scalars for this ordering = 2
Nr. of scalars still alive (outputs) = 1
. . . in function main
Array col is reduced to a scalar.
Array sum is reduced to a scalar.
Process Partitioning.
______________________________________
Within the resulting C file, the declaration statement for memory allocation looks like: Sig.sub.-- Type col.sub.-- 4, sum.sub.-- 7; Note, that instead of a declaration of a multidimensional signal of 10000 instances of Sig.sub.-- type, only a single variable instance (i.e., a scalar) is needed. An excerpt of the C code that executes the basic functionality of the initial Silage description is generated as:
______________________________________
01: FixAssign (c9, sum.sub.-- 7);
02: for (i.sub.-- 6=(0); i.sub.-- 6<=(9999); i.sub.-- 6++) {
03: for (T0.sub.-- 5=(0); T0.sub.-- 5<=(11); T0.sub.-- 5++) {
04: if ((T0.sub.-- 5==0)) {
05 FixAssign (c8, col.sub.-- 4);
06: }
07: if (((10>=T0.sub.-- 5))&&((T0.sub.-- 5>=1))) {
08: FixPlus (col.sub.-- 4,64,0,matr.sub.-- 2[(i.sub.-- 6+1)][T0.sub.--
5],64,0,col.sub.-- 4,64,0);
09: }
11: if ((T0.sub.-- 5==11)) {
12: FixPlus (sum.sub.-- 7,64,0,col.sub.-- 4,64,0,sum.sub.-- 7,64,0);
13: }
14: }
15: }
16: FixAssign (sum.sub.-- 7,(*p.sub.-- out.sub.-- 3));
______________________________________
MASAI also calculates relative lifetimes of all the signals. Based on these lifetimes, memory directives for the compiled code simulator S2C are generated by MASAI. For the initial Silage description, the following directives are generated. 01: INPLACE main col; 02: INPLACE main sum; With these directives, S2C can directly generate C code that requires significantly less memory than the unoptimized C code. For further detail see Ch. 5 and 6 of Michael Van Swaaij, "Data Flow Geometry; Exploiting Regularity in System-level Synthesis", Ph.D. thesis, Katholieke Universiteit, Leuven, Faculteit Toegepaste wetenschappen, December, 1992 as appended hereto.
|
Same subclass Same class Consider this | ||||||||||