Case and EndCase, and two SDF galaxies to represent the bodies of the TRUE or FALSE branches. The dynamic constructs supported by the CGDDF scheduler are case, for, do-while, and recursion. The case construct is a generalization of the more familiar if-then-else construct. The topology of the galaxy is matched against a set of pre-determined topologies representing these dynamic constructs.Galaxy is a hierarchical block for structural representation of the program graph. When an APEG is generated from an SDF graph for parallel scheduling, galaxies are flattened. To handle a dynamic construct as a unit of parallel scheduling, we make a cluster, called a galaxy cluster, for each dynamic construct. The programmer should indicate the galaxies to be clustered by creating a galaxy parameter asFunc and setting its value to YES. For example, the galaxies associated with the TRUE and the FALSE branch of a case construct will have the asFunc parameter as well as the galaxy of the construct itself.
The type of the dynamic construct and the scheduling information related to the dynamic constructs are defined as galaxy parameters. We assume that the run-time behavior of each dynamic construct is known or can be approximated with a certain probability distribution. For example, the number of iterations of a for or do-while construct is such a variable; similarly, the depth of recursion is a variable of the recursion construct. The parameters to be defined are as follows:
STRING) Default =case, for, doWhile, or recur (case insensitive).
STRING) Default = geometric
Type of the distribution. Currently, we support geometric distribution, uniform distribution, and a general distribution specified by a table.
FLOAT) Default = 0.5
Geometric constant of a geometric distribution. Its value is effective only if the geometric distribution is selected by paramType. If constructType is case, this parameter indicates the probability of branch 1 (the TRUE branch) being taken. If there are more than two branches, use paramFile to specify the probabilities of taking each branch.
INT) default = 1
Minimum value of the uniform distribution, effective only when the uniform distribution is chosen.
INT) default = 10
Maximum value of the uniform distribution, effective only when the uniform distribution is chosen.
STRING) default = defParams
The name of a file that contains the information on the general distribution. If the construct is a case construct, each line contains the probability of taking a branch (numbered from 0). Otherwise, each line contains the integer index value and the probability for that index. The indices should be in increasing order.
Case and EndCase stars are used in the case, do-while, and recursion constructs, which differ from each other in the connection topology of these DDF stars and SDF galaxies. Therefore, if the user wants to use one of the above three dynamic constructs, there is no need to write a new DDF star. Like a DDF star, the Case star has dynamic output portholes as shown in the CGCCase.pl file. For example: outmulti {
name { output }
type { =input }
num { 0 }
}
The for construct consists of an UpSample type star and a DownSample type star, where UpSample and DownSample are not the star names but the types of the stars: if a star produces more than it consumes, it is called an UpSample star. In the preprocessor file, we define a method readTypeName, as shown below.method {
name { readTypeName }
access { public }
type { "const char *" }
code { return "UpSample"; }
}
Examples of UpSample type stars are Repeater and DownCounter. These stars have a data input and a control input. The number of output data tokens is the value of the integer control input, and is thus data-dependent. Conversely, we can design a DownSample star that has the following method:method {
name { readTypeName }
access { public }
type { "const char *" }
code { return "DownSample"; }
}
Examples of DownSample type stars are LastOfN, and SumOfN. These stars have a data input and a control input. The number of input tokens consumed per invocation is determined by the value of the control input.As explained above, all customized DDF-type stars for dynamic constructs will be either an UpSample type or a DownSample type. We do not expect that a casual user will need to write new DDF stars if we provide some representative UpSample and DownSample stars in the corresponding code generation domains. Currently, we have DDF stars in the CGC code generation domain only.
Copyright © 1990-1997, University of California. All rights reserved.