Previous Up Next

Chapter 4  Detailed Instructions

4.1  Command Line Interface

Spark can be invoked on the command-line by the command:
spark [command-line flags] filename.c

filename.c is the name of the input file with the behavioral code to be synthesized. We can also specify multiple files on the command-line.

Some of the important command-line flags are:
Flag Purpose
-h Prints help
-hs Schedule Design
-hvf Generate RTL VHDL (output file is ./output/filename_spark_rtl.vhd)
-hb Do all Resource Binding (operation to functional unit and variable to registers)
-hec Some statistics about states, path lengths are printed into the backend VHDL file
-hcc Generate output C file of scheduled design (output file is ./output/filename_sparkout.c)
-hch Chain operations across Conditional Boundaries
-hcp Do Copy and Constant Propagation
-hdc Do Dead Code Elimination
-hcs Do Common Sub-Expression Elimination
-hli Do Loop Invariant Code Motion
-hg Generate graphs (output files are in directory ./output).
  Graphs are generated by default if scheduling is done, as: filename_sched.dotty
-hcg Generate function call graph (./output/CG_filename.dotty)
-hq Run quietly; no debug messages
Spark writes out several files such as the output graphs (see next section) and the backend VHDL and C files. All these files are written out to the subdirectory ``output'' of the directory from which Spark is invoked. This directory has to be created before executing Spark.

Some useful EDG command-line flags are given below. These flags are useful when the style of C does not completely conform to ANSI-C.
Flag Purpose
-m For old style C (see below)
-c99 For C conforming to the C99 specification
For example, use the ``-m'' command-line flag for input code in which functions are specified in the following format:
void myfunction(variableA, variableB)
     int variableA;
     int variableB;
{
..
}

4.2  Viewing Output Graphs

The format that Spark uses for the output graphs is that of AT&T’s Graphviz tool [17]. Output graphs are created for each function in the ``C'' input file. The output graphs generated are listed in Table ??. The key to the nomenclature used in naming the graphs is given in Table ??
Graphs representing the original input file Graphs representing the scheduled design
CFG_filename_c_functionName.dotty CFG_filename_c_functionName_sched.dotty
HTG_filename_c_functionName.dotty HTG_filename_c_functionName_sched.dotty
DFG_filename_c_functionName.dotty DFG_filename_c_functionName_sched.dotty
CDFG_filename_c_functionName.dotty CDFG_filename_c_functionName_sched.dotty
CG_filename_c_functionName.dotty -
CG_DFG_filename_c_functionName.dotty -

Table 4.1: Output Dotty graphs generated by Spark

Abbreviation Explanation
CFG Control Flow Graph: Basic blocks with control flow between them
HTG Hierarchical Task Graph: Hierarchical structure of basic blocks
DFG Data Flow Graph: data flow between operations
CDFG Control-Data Flow Graph: Resource-utilization based view of the CFG
CG Call Graph showing control flow between functions
CG_DFG Call Graph with data dependencies and control flow between functions
filename The name of ``C'' input file
functionName The name of the function in input file

Table 4.2: Key to abbreviations used in Dotty graph naming

To view these output graphs, we use the Graphviz command line tool dotty, as follows:
dotty output/graphfilename.dotty

4.3  Hardware Description File Format: default.spark

Spark requires as input a hardware description file that has information on timing, range of the various data types, and the list of resources allocated to schedule the design (resource library). This file has to be named ``filename.spark'', where filename.c is name of the ``C'' input file. If a filename.spark does not exist, then the Spark executable looks for ``default.spark''. One of these files has to exist for Spark to execute.

The various have sections in the .spark files are described in the next few sections. Note that, comments can be included in the .spark files by preceding them with ``//''.

4.3.1  Timing Information

The timing section of the .spark file has the following format:
// ClockPeriod  NumOfCycles  TimeConstrained   Pipelined
[GeneralInfo]
     10              0            0                 0



Of these parameters, only the clock period is used by the scheduler to schedule the design. The rest of the parameters have been included for future development and are not used currently. They correspond to the number of cycles to schedule the design in (timing constraint), whether the design should be scheduled by a time constrained scheduling heuristic, and whether the design should be pipelined.

4.3.2  Data Type Information

Each data type used in the ``C'' input file has to have an entry in the ``[TypeInfo]'' section of the .spark file, as shown below:
//typeName           lowerRange      upperRange
//or variableName    lowerRange      upperRange
[TypeInfo]
      int              -32767          32768
      myVar              0               16



This section specifies the range of the various data types that can be specified in a C description (such as int, char, float, unsigned int, signed int, long, double et cetera). The format is data type, lower bound range, and upper bound range. Also, the data value range of specific variables from the input C description can be specified in this section, as variable name, lower range, upper range. This is shown in the table above my the example of a variable ``myVar'' whose range is from 0 to 16.

4.3.3  Hardware Resource Information

This section parameterizes each resource allocated to schedule the design as shown by the example below:
//name  type   inpsType  inputs  outputs number  cost  cycles  ns
[Resources]     
CMP    ==,<,!=    i        2       1       1      10     1     10



The example given in the first line above is: 112 A resource called CMP (comparator). The operations ==, <, != can be mapped to this resource. It handles inputs of type integer (i). It has 2 inputs. It has 1 output. There is one CMP allocated to schedule the design. Its cost is 10. The cost, although not used currently, can be integrated into module selection heuristics while selecting a resource for scheduling from among multiple resources. The CMP resource executes in 1 cycle. It takes 10 nanoseconds to execute.

We can define resources of every type supported by the ``C'' language in the [Resources] section of the hardware description file. A detailed example is given in Appendix A24Sample default.spark Hardware Description fileappendix.A. Note that although we allow specifying multi-cycle resources in the resource description section, we do not currently support structurally pipelined resources.

A list of all basic operators/resources recognized by Spark is given in Table ??. The columns in this table list the resource type as specified in the .spark file, the corresponding operator in C, the operation name, and the number of inputs this resource accepts (number of outputs is currently one for all the resources). Complex resources can be made using these basic operators as shown in the example above for the ``CMP'' resource.

If the Spark executable reports an error that says ``All ss in StatementNum are not scheduled'', then look at the operators in the expressions reported after this error and add them to the hardware description file (.spark file).

Note that: The order of resources in the [Resources] section is the order in which operations from the input code will be mapped to the resources. So, if there are two resources that do additions:
//name  type   inpsType  inputs  outputs number  cost  cycles  ns
[Resources]     
ALU      +,-      i        2       1       1      10     1     10
ADD       +       i        2       1       1      10     1     10



Then, the scheduler will first try to schedule addition operations to the ALU resource and then try to schedule to the ADD resource.

Resource Operator Operation Number of
Type in C   Inputs
+ + add 2
- - subtract 2
* * multiply 2
/ / divide 2
!= != compare 2
== == compare 2
> > compare 2
< < compare 2
>= >= compare 2
<= <= compare 2
<< << shift 2
>> >> shift 2
[] [] array access 1
~ ~ complement 1
! ! logical not 1
&& && logical and 2
|| || logical or 2
b& & Boolean and 2
b| | Boolean or 2
call - function call -

Figure 4.1: List of all resource types, corresponding C operators, operation name, and number of inputs

4.3.4  Specifying Function Calls as Resources in the Hardware Description File

A hardware resource has to be specified for each function call in the code. Hence, for a function call with the name ``myfunction'', we have to declare a hardware resource as follows:
//name     type   inpsType  inputs  outputs number cost cycles ns
[Resources]     
myfunction call     i          0       0       2    10    1    10



This line specifies a function call with name ``myfunction'' with integer input types that takes 1 cycle and 10 ns to execute. The number of inputs and outputs is determined by Spark from the declaration of the function in the input code. If the function ``myfunction'' is defined in the input code, Spark performs an analysis of the function and determines the actual execution cycles and time of the function and uses this information for scheduling the calling function.

To generate correct and synthesizable VHDL, you have to specify a resource specifically for each function call. The number of components instantiated for function calls to the same function is determined by the number of resources specified above. Hence, in the example for ``myfunction'', we specified two resources; thus, there will be two component instantiations in the VHDL code.

The keyword ``ALLCALLS'' is used to match all function calls in the input code as follows:
//name     type   inpsType  inputs  outputs number cost cycles ns
[Resources]     
ALLCALLS   call     i          0       0       1    10    1    10



This may be useful to capture calls to functions such as printf that may have been used in the C code. Note that: the ALLCALLS resource should be put at the end of the [Resources] section, otherwise all the function calls will be mapped to this resource.

4.3.5  Loop Unrolling and Pipelining Parameters


// variable maxNumUnrolls maxNumShifts  percentageThreshold ThruputCycles
[RDLPParams]
* 0 0 70 0
i 0 2 70 0



This section presents the parameters for loop unrolling and loop pipelining. 112 Variable is the loop index variable to operate on (``*'' means all loops) The second parameter specifies the number of times to unroll the loop. Number of times the loop should be shifted by the loop pipelining heuristic. Percentage threshold and throughput cycles are parameters used by the resource-directed loop pipelining (RDLP) heuristic implemented in our system.

The example in the second line of the ``[RDLPParams]'' section shown above says that the loop with loop index variable ``i'' should be shifted twice. To fully unroll a loop, specify number of loop unrolls to be equal to or more than the maximum number of iterations of the loop.

4.3.6  Other Sections in .spark files

The other sections in the .spark files are:

112 [RDLPMetrics]: Controls the various parameters of the resource-directed loop pipelining (RDLP) heuristic. [SchedulerRules]: The file that Spark should read to get the scheduling scripts (rules and parameters). Default is: Priority.rules. [SchedulerScript]: The scheduling script to use: different scheduling heuristics can be employed by changing this entry. Default is ``genericSchedulerScript''. [Verification]: Specifies the number of test vectors that should be generated for functional verification of output C with input C. [OutputVHDLRules]: Specifies the VHDL generation rules; this is covered in more detail in Section 4.419VHDL Output Generated by Sparksection.4.4.

4.4  VHDL Output Generated by Spark

Spark generates synthesizable register-transfer level VHDL code (by specifying the -hvf command-line flag). If the -hb command-line flag is also given, then the VHDL code is generated after operation and variable binding [5]. In resource-bound code, an entity-architecture pair is generated for each resource in the hardware description file (.spark file) and a component is instantiated for each instance of the resource (as specified by the number of resources in the .spark file). Processes are created to generate multiplexers at the input of each functional unit/resource and variables are bound to registers that are explicitly declared.

In contrast, when the resource binding flag (-hb) is not specified, then only operation expressions are generated in the VHDL code. This code looks more like: a <= b + c and so on. Hence, the unbound code is easier to read and understand and also, has clearer relation with input C code since variables from the input code are used in the VHDL. However, from a logic synthesis point of view, unbound VHDL code allows the logic synthesis tool to decide the number of resources and registers that are allocated to the synthesize the final netlist.

The following is an example of the same VHDL code in the data path process for the bound and unbound case respectively.
 if CURRENT_STATE(0) = '1' then
   regNum0 <= res_ALU_1_out;
   regNum5 <= 0;
 elsif CURRENT_STATE(1) = '1' then
   regNum1 <= res_ALU_0_out;
   regNum2 <= res_ALU_1_out;
   hT0 <= res_CMP_2_out;
  
 if CURRENT_STATE(0) = '1' then
   hT5  <=  (x + 2);
   col  <=  0;
 elsif CURRENT_STATE(1) = '1' then
   hT14  <=  (col + bytes);
   hT15  <=  (col - x);
   hT0  <=  (col < 10);

            (a)                         (b)
Figure 4.2: (a) Bound VHDL code (b) Corresponding unbound VHDL code

Note that, from release version 1.1 on, the output VHDL file generated by Spark has the extension ``.vhd'' versus the earlier ``.vhdl''. This is for compatibility with Windows based tools such as Xilinx XST that look for .vhd VHDL files by default.

4.4.1  Generating VHDL bound to Synopsys DesignWare Foundation Libraries

The default.spark (or filename.spark) file contains a section for controlling the type of VHDL output generated by Spark. This is shown below: 


[OutputVHDLRules]
PrintSynopsysVHDL=true



By setting the ``PrintSynopsysVHDL'' to true in the ``[OutputVHDLRules]'' section of the default.spark (or filename.spark) file, we can generate VHDL that is Synopsys specific. This means that the VHDL code generated by Spark is synthesizable by Synopsys logic synthesis tools (Design Compiler). Hence, the VHDL code uses Synopsys libraries and components from the Synopsys DesignWare Foundation library (specifically for the multiplier and divider).

The VHDL code also generates a SPARK package and stores this package in a SPARK library and this library is then used in the code. Hence, this SPARK library has to be mapped to your work directory. For Synopsys tools, this is done using the .synopsys_vss.setup file.

4.4.2  Generating VHDL Synthesizable by Other Logic Synthesis tools

If you are using logic synthesis tools from another vendor (besides Synopsys), then set the ``PrintSynopsysVHDL'' to false in the ``[OutputVHDLRules]'' section of the default.spark (or filename.spark). This can be done as follows:


[OutputVHDLRules]
PrintSynopsysVHDL=false



Also, the VHDL uses the SPARK package (use work.spark_pkg.all;) that is stored in the SPARK library. Thus, you have to edit your setup files to map the SPARK library to the work directory. Additionally, You will have to explicitly instantiate multi-cycle components such as the multiplier and divider from the standard cell library of your technology vendor. This has to be done in the architecture description of res_MUL and res_DIV in the VHDL code.

From release version 1.1 on, when the ``PrintSynopsysVHDL'' is false, Spark resets the conditional variables in the data path process (DP: Process) rather than the SYNC process. This is for ensuring synthesizability by Xilinx XST.
18cm
//line format: functiontype=functionvalue
[SchedulerFunctions]
CandidateValidatorFunction=candidateValidatorPriority // Candidate Validation Algorithm
CandidateMoverFunction=TbzMover // Use Trailblazing for code motions
CandidateRegionWalkerFunction=topDownGlobal // Design traversal for candidate operations
ScheduleRegionWalkerFunction=topDownBasicBlock // Design traversal for scheduling
PreSchedulingFunction=initPriorities // Calculate priorities of operations before scheduling
PriorityType=max // Calculate priority as max or sum of dependent
    operations data dependencies
PostSchedulingStepFunction=postSchedulingPriority // Reverse speculate all unscheduled operations at each
    time step of scheduling
PreSchedulingStepFunction=preSchedPriority // Do early condition execution before each time step
    of scheduling
LoopSchedulingFunction=RDLP // Loop unrolling is done by RDLP
PreLoopSchedulingFunction=prepareForRDLP // Initialization functions for loops
PostLoopSchedulingFunction=constantPropagation // Optional post loop scheduling pass
ReDoHTGsForDupUp=false // Whether to reschedule HTGs for possible
    duplication-up true or false
ReassignPriorityForCS=true // Reassign priorities to favor operations
    within basic blocks
RestrictDupUpType=targetBBUnsched // Restrict duplication-up
DynamicCSE=true // Whether Dynamic CSE is enabled or not
BranchBalancingDuringCMs=true // Enable branch balancing during code motions
BranchBalancingDuringTraversal=true // Enable branch balancing during design traversal

Figure 4.3: The scheduler functions section in a sample Priority.rules file.

4.5  Scripting Options for Controlling Transformations and Heuristics: Priority.rules

Spark allows the designer to control the transformations applied to the design description by way of synthesis scripts. In this section, we discuss the scripting options available to the designer.

The scripting options can be specified in the file given by the ``[SchedulerRules]'' section of the .spark file (see previous section). The default script file Spark looks for is ``Priority.Rules''. This file has three main sections: the scheduler functions, the list of allowed code motions (code motion rules) and the cost of code motions. We discuss each of these in the next three sections. Note that in this file, "//" denotes that the rest of the line is a comment.

4.5.1  Scheduler Functions

An example of the scheduler functions section from a sample Priority.rules file is given in Figure ??. An entry in this section is of type ``FunctionType=FunctionName''. We have given explanations for each function type in comments on each line in this figure.

Of these we use the following flags for the experiments presented in this thesis: DynamicCSE, PriorityType, BranchBalancingDuringCMs and BranchBalancingDuringTraversal.

4.5.2  List of Allowed Code Motion

This section of the ``Priority.rules'' file has the list of code motions that can be employed by the scheduler. Each code motion can be enabled or disabled by setting the flag corresponding to it to ``true'' or ``false''. An example of the list of allowed code motions sections is as given below.


// all the following can take values true or false
[CodeMotionRules]
RenamingAllowed=true            // Variable Renaming allowed or not 
AcrossHTGCodeMotionAllowed=true // Across HTG code motion allowed or not 
SpeculationAllowed=true         // Speculation allowed allowed or not 
ReverseSpeculationAllowed=true  // Reverse Speculation allowed or not 
EarlyCondExecAllowed=true       // Early Condition Execution allowed or not 
ConditionalSpeculationAllowed=true // Condition Speculation allowed or not

4.5.3  Cost of Code Motions

This section was developed to experiment with incorporating costs of code motions into the cost function based on which the operation to schedule is chosen. An example of this section is given below. Here all the code motions are assigned a cost of 1.


[CodeMotionCosts]
WithinBB               1
AcrossHTGCodeMotion    1
Speculation            1
DuplicationUp          1



The total cost of scheduling an operation is determined as:
Total Cost = - Basic Cost of operation * Cost Of Each Code Motion required to schedule the operation
where basic cost of the operation is the priority of the operation [2] and cost of each code motion is as given in the ``[CodeMotionCosts]'' section of the Priority.rules file. Since this function generates a negative total cost, the operation with the lowest cost is chosen as the operation to be scheduled.



Previous Up Next