LEDA is a famous C++ graphs and general data structures library. We have used it since many years, and we can safely say that it is better than other existing C++ graph and data structures libraries that we experimented (BOOST, STL, etc.). LEDA is a high level library greatly helping to implement complex algorithms in a quick, robust and modular way. According to our deep experience, a C++ code using LEDA looks like a high level algorithm, allowing to easily debug it without suffering from programming details. Furthermore, LEDA offers the largest set of implementation of well known algorithms in graph theory and data structures: these are very helpful in optimising compilation, especially for instruction level parallelism problems such as instruction scheduling and register allocation. LEDA is well suited for academic research.
and 
latencies). Also, the hardware latencies of operations are implemented too, which may distinct from the latencies of the edges.
and 
functions become general integers). This is an important aspect if we would like to model optimal scheduling problems for VLIW/EPIC architectures. Consequently, some DDG algorithms have been slightly modified to include this aspect (such as critical cycle computation, longest and shortest paths, etc.)
in our library is a directed acyclic graph (from top to bottom) that represents the data dependences between a set of statements and any other serial constraints. The DAG is defined by its set of nodes (statements) 
, its set of edges (data dependences and serial constraints) 
, and such that 
is the latency of the edge 
(in terms of processor clock cycles for instance). While the latencies are non-negative in general (this assumption is important for many standard graph algorithms), we allow in the DDG library to have non-positive latencies in order to model some VLIW and EPIC characteristics. We consider a target RISC-style architecture. We differentiate between statements and precedence constraints, based on whether they refer to values to be stored in registers or not.
is the set of statements (operations) which define values of type 
to be stored in registers of type . We simply call them values.
is the set of data flow dependence edges through registers of type . 
(as those usually used in lattices and orders algebra):
successors of 
in the graph 
. They are also called the children of .
predecessors of in the graph ;.They are also called the parents of .
. and 
are called endpoints;
. This relationship is reflexive: 
.
;
. and are said to be parallel ;
. and are said to be comparable ;
's ascendants including . In other terms, a node is an ascendant of a node iff there exists a path from to .
's descendants including . In other terms, a node is a descendant of a node iff there exists a path from to .
is an antichain iff all nodes belonging to 
are parallel. Formally, is an antichain in 
iff 
;
is a maximal antichain iff its size in terms of number of nodes is maximal. Formally, is a maximal antichain 
;
.
is a chain iff all nodes belonging to 
are compatable. Simply, all nodes of a chain belongs to the same path in the DAG. Formally, is a chain in iff 
;
is a chain partition of if any 
is a chain and: ![$ \forall u \in V, \exists !i \in [0,p-1]: u \in C_i $](form_100.png)
.
is minimal if its indice 
is minimal. Such minimal indice is noted 
.
, and each maximal antichain is equivalent to a minimal chain decomposition (and vice-versa).
, such that: is the set of the statements in the loop.
is the set of precedence constraints (flow dependences, or other serial constraints). Any edge has the form 
, where 
is the latency of the edge (in terms of processor clock cycles for instance) and 
is the distance of the edge in terms of number of iterations. Both and may be non-positive. However, valid loops DDGs have always cycles with summed non-negative distances, that is: 
.We consider a target RISC-style architecture and we distinguish between statements and precedence constraints, depending upon whether they refer to values to be stored in registers or not.
is the set of statements that produce values to be stored in registers of type . We simply call them values. is the set of flow dependence edges through registers of type . The set of consumers (readers through registers) of a value 
is therefore the set 
and in which
The writing cycle of 
into a register is delayed by 
clock cycles after the issue (schedule) date of . 
is the hardware latency of the instruction (it may be distinct from the latencies of the data dependence edges). Also, we define:
The reading cycle of from a register is delayed by 
clock cycles after the issue (schedule) date of .
According to the semantics of superscalar processors (sequential semantics) and EPIC/IA64, and 
are equal to zero. Also, there are many VLIW processors with zero reading/writing delays. But some VLIW processors such that Trimedia have non-zero reading/writing delays.
<arch version='1'>
<regtype type='BR' number='2'>
<register name='br0'>
<register name='br1'>
</regtype>
<regtype type='GR' number='61'>
</regtype>
<instruction opcode='nop' latency='0' delta_r='0'>
</instruction>
<instruction opcode='inst_2' latency='1' delta_r='2'>
<write regtype='GR' delta_w='1'/>
<write regtype='GR' delta_w='0'/>
</instruction>
<semantic type='UAL'/>
</arch>
For now, only version 1 is supported, so the version attribute must be set to 1. For each register type, the type name and the number of registers must be provided. The type name has to be unique. Optionally, register names can be specified. For each instruction, a unique opcode must be provided, as well as the latency and read delay of the instruction. If the instruction writes into one or several registers, the register types and write delay must be provided for each one. The semantic can also be specified (once in the file). If the type attribute is 'UAL', then UAL semantic is assumed. Else, or if the semantic is not specified, NUAL is assumed. The current DDG release contains examples of XML files describing some architectures.
<ddg version='1'> <operation type='inst_1' id='1'/> <operation type='inst_2' id='2'/> <operation type='nop' id='3' description='Idle'/> <edge src='1' dst='2' latency='3' distance='0' typedep='flowdep_reg' regtype='GR'/> <edge src='1' dst='3' latency='0' distance='1' typedep='serial'/> <edge src='2' dst='3' latency='0' distance='1' typedep='antidep_reg' regtype='BR'/> </ddg>
The current DDG release contains examples of XML files describing DDG provided from STmicroelectronics.
DDG.GRAPH 1.1 #number_of_nodes opcode_id_node_1 opcode_id_node_2 ... . opcode_id_node_n #number_of_edges source_id dest_id latency distance edge_type ... .
Note that the latency of an edge may be distinct from the latency of the source instruction. edge_type is a string describing the type of the data dependence ("flowdep_reg", "serial", "antidep_reg", "outputdep_reg", etc.). "" do not belong to the strings.
2 4 1 0
. It is an old problem in graph theory studied initially by Dantzing in 1966. Such circuit is assumed in general to have 
and 
. However, our DDG library adds the special case of null circuits, i.e.,, those defined with 
and 
. is valued by the couple 
.Some other screenshots can be found here .
you can execute these programs on the DDG and ISA samples we provide inside the DDG release.
LEDAROOT environment variable to the path of LEDA installation directory and use the include directory -I$LEDAROOT/incl in the command line argument of g++.
Furthermore, we highly recommend to use the -fno-inline option of your C++ compiler.
libDDG.a is created. This library has to be linked with the user applications using the DDG features. Furthermore, the LEDA library should be present (make sure that the LEDAROOT environment variable is correctly set), especially libG.a and libL.a. The user should then link its application with all these libraries by using the following link option for g++ line command libDDG.a -L$LEDAROOT -lG -lL. Note that the order of these linker options is important. Starting from LEDA version 6.0, the linking options -lG -lL become obsolete, they have been replaced by -lleda.new_node, new_edges, etc.). If the user wishes, he can implement his own import method from other graph formats. Here is a simple hello world program to show that it is very simple to handle data dependence graphs using our library. Detailed information could be found in the definitions of DAG and LOOP classes, and in the other code examples.
#include "DDG.h" // the header file of the DDG library. To be included by the user. #include <iostream> #include <cstdlib> using namespace std; using namespace DDG; // the namespace of the DDG library. int main(int argc, char *argv[]) { int i; int c; // for getopt // some strings for file names ARCHITECTURE isa_arch; char *ddg_filename=NULL, *arch_filename=NULL; //declare a DDG of a loop (cyclic data dependence graph) DDG::LOOP loop; LEDA::node n,u; LEDA::edge e; while ((c = getopt (argc, argv, "i:a:")) != -1){ switch(c){ case 'a': arch_filename=optarg; break; case 'i': ddg_filename =optarg; break; case '?': cout<<"usage:"<< argv[0] <<" -i ddg_filename.xml [-a isa_desc.xml] "<<endl; return EXIT_FAILURE; } } if (arch_filename!=NULL) { isa_arch.read_from_xml(arch_filename); if(isa_arch.check()){ loop=LOOP(isa_example); //build an empty DDG loop with a user defined architcural (ISA) description } else return EXIT_FAILURE; } //---- The user can read a DDG from an xml format defined by the DDG library if (ddg_filename != NULL){ i=loop.read_from_xml(ddg_filename); // reads the DDG loop from an xml file if(i==-1) return EXIT_FAILURE; } else{ cout<<"usage:"<< argv[0] <<" -i ddg_filename.xml [-a isa_desc.xml] "<<endl; return EXIT_FAILURE; } cout<< "DDG example : " <<ddg_filename<<endl; // Null circuits are accepted inside the DDG and detected cout<<"Critical Cycle of "<< ddg_filename<<" = "<<loop.CRITICAL_CYCLE(el)<<endl; cout<<"Edges belonging the the critical cycle"<<endl; forall(e, el){ ie=loop[e]; cout<< loop.source_id(e)<< " -> "<< loop.target_id(e); cout<<" : "<< ie<<endl; } return EXIT_SUCCESS; }
