d/nova/nova/doc/.svn/text-base/partitionedbooleanquadric.html.svn-base


<html><head>
<meta http-equiv="content-type" content="text/html; charset=utf-8">
<meta content="text/javascript" http-equiv="content-script-type">
<title>nova.math.optimization.partitionedbooleanquadric</title>
<link rel="stylesheet" type="text/css" href="candydoc/style.css">
<!--[if lt IE 7]><link rel="stylesheet" type="text/css" href="candydoc/ie56hack.css"><![endif]-->
<script language="JavaScript" src="candydoc/util.js" type="text/javascript"></script>
<script language="JavaScript" src="candydoc/tree.js" type="text/javascript"></script>
<script language="JavaScript" src="candydoc/explorer.js" type="text/javascript"></script>
</head><body>
<div id="tabarea"></div><div id="explorerclient"></div>
<div id="content"><script>explorer.initialize("nova.math.optimization.partitionedbooleanquadric");</script>
    <table class="content">
        <tr><td id="docbody"><h1>nova.math.optimization.partitionedbooleanquadric</h1><!-- Generated by Ddoc from math\optimization\partitionedbooleanquadric.d -->
<b>Autors:</b><br>
Klaus Oberhofer
<br><br>
<b>License:</b><br>
zlib/libpng license
<br><br>
<b>ToDo:</b><br>
- more unit tests
<br><br>

<br><br>


<br><br>


<script>explorer.outline.incSymbolLevel();</script>
<dl>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">class 
<span class="currsymbol">PBQPSolver</span>
<script>explorer.outline.addDecl('PBQPSolver');</script>

;
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>Implementation of a partitioned binary quadric solver as described
	in papers by Eckstein et al. [SchEck02, SchEck03]
	The partitioned binary quadric problem is a mathematical optimization
	problem. Goal is to minimize a graph with minimal costs.
<br><br>
Eckstein maps compiler specific tasks like instruction selection
	and register allocation to the PBQ problem, passes it to the solver.
	The solution is then propagated back to the original problem and
	used to create an optimal instruction sequence.
<br><br>

  There is another paper in german which describes the implementation
	of an automatic code generator using a PBQP solver [Jaks04].

<br><br>
<b>References:</b><br>
[SchEck02] B. Scholz and E. Eckstein. Register allocation for
		           irregular architecture. In Proceedings of Languages,
							 Compilers, and Tools for Embedded Systems (LCTES'02)
							 and Software and Compilers for Embedded Systems (SCOPES'02),
							 Berlin, June 2002. ACM.
<br><br>

	  [SchEck03] E. Eckstein and B. Scholz. Address mode selection.
		           In Proceedings of the International Symposium of Code
							 Generation and Optimization (CGO'03),
							 San Francisco, March 2003. IEEE/ACM.
<br><br>

	  [Jaks04]   Hannes Jakschitsch. Befehlsauswahl auf SSA-Graphen.
		           Diplomarbeit am IPD Goos, Universität Karlsruhe, 2004
<br><br>

<br><br>


<br><br>


<script>explorer.outline.incSymbolLevel();</script>
<dl>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">insertNode</span>
<script>explorer.outline.addDecl('insertNode');</script>

(int <span class="funcparam">u</span>, Vector <span class="funcparam">costs</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>inserts node into the graph
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">addNodeCosts</span>
<script>explorer.outline.addDecl('addNodeCosts');</script>

(int <span class="funcparam">u</span>, Vector <span class="funcparam">costs</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>add <span class="funcparam">costs</span> to cost vector of a node
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">Vector 
<span class="currsymbol">getNodeCosts</span>
<script>explorer.outline.addDecl('getNodeCosts');</script>

(int <span class="funcparam">u</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>get node costs
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">addEdgeCost</span>
<script>explorer.outline.addDecl('addEdgeCost');</script>

(int <span class="funcparam">u</span>, int <span class="funcparam">v</span>, Matrix <span class="funcparam">costs</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>add edge <span class="funcparam">costs</span> (matrix)
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">removeBucket</span>
<script>explorer.outline.addDecl('removeBucket');</script>

(int <span class="funcparam">deg</span>, int <span class="funcparam">u</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>remove bucket from bucket list
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">reorderNode</span>
<script>explorer.outline.addDecl('reorderNode');</script>

(int <span class="funcparam">u</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>reorder node
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">reorderAdjNodes</span>
<script>explorer.outline.addDecl('reorderAdjNodes');</script>

(int <span class="funcparam">u</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>reorder adjacency nodes
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">insertEdge</span>
<script>explorer.outline.addDecl('insertEdge');</script>

(int <span class="funcparam">u</span>, int <span class="funcparam">v</span>, Matrix <span class="funcparam">costs</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>edge functions
 
<br><br>

<br><br>

    insert edge to graph
    (does not check whether edge exists in graph)
  
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">deleteEdge</span>
<script>explorer.outline.addDecl('deleteEdge');</script>

(int <span class="funcparam">u</span>, int <span class="funcparam">v</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>delete edge
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">createBucketList</span>
<script>explorer.outline.addDecl('createBucketList');</script>

();
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>create bucket list
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">int 
<span class="currsymbol">popNode</span>
<script>explorer.outline.addDecl('popNode');</script>

(int <span class="funcparam">degree</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>pop functions
 
<br><br>

 pop node of certain <span class="funcparam">degree</span>
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">int 
<span class="currsymbol">popMaxNode</span>
<script>explorer.outline.addDecl('popMaxNode');</script>

();
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>pop node with maximal degree 
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">disconnectTrivialNode</span>
<script>explorer.outline.addDecl('disconnectTrivialNode');</script>

(int <span class="funcparam">u</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>PBQP simplification for trivial nodes
   
<br><br>

 remove trivial node with cost vector length of one
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">eliminateTrivialNodes</span>
<script>explorer.outline.addDecl('eliminateTrivialNodes');</script>

();
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>find all trivial nodes and disconnect them
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">bool 
<span class="currsymbol">normalizeMatrix</span>
<script>explorer.outline.addDecl('normalizeMatrix');</script>

(Matrix <span class="funcparam">m</span>, Vector <span class="funcparam">u</span>, Vector <span class="funcparam">v</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>Normal form for PBQP
   
<br><br>

<br><br>

    simplify a cost matrix. If the matrix
    is independent, then simplify_matrix
    returns TRUE - otherwise FALSE. In
    vectors <span class="funcparam">u</span> and <span class="funcparam">v</span> the offset values of
    the decomposition are stored.
	
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">simplifyEdge</span>
<script>explorer.outline.addDecl('simplifyEdge');</script>

(int <span class="funcparam">u</span>, int <span class="funcparam">v</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>simplify single edge
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">eliminateIndependentEdges</span>
<script>explorer.outline.addDecl('eliminateIndependentEdges');</script>

();
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>normalize cost matrices and remove
    edges in PBQP if they ary independent,
    i.e. can be decomposed into two
    cost vectors.
	
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">apply_RI</span>
<script>explorer.outline.addDecl('apply_RI');</script>

(int <span class="funcparam">x</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>PBQP reduction rules
   
<br><br>

<br><br>

    RI reduction
    This reduction rule is applied for nodes
    of degree one.
	
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">apply_RII</span>
<script>explorer.outline.addDecl('apply_RII');</script>

(int <span class="funcparam">x</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>RII reduction
    This reduction rule is applied for nodes
    of degree two.
  
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">apply_RN</span>
<script>explorer.outline.addDecl('apply_RN');</script>

(int <span class="funcparam">x</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>RN reduction
    This reduction rule is applied for nodes
    of degree N.
	
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">reducePBQP</span>
<script>explorer.outline.addDecl('reducePBQP');</script>

();
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>PBQP graph parsing
   
<br><br>

 reduce pbqp problem (first phase)
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">determineSolution</span>
<script>explorer.outline.addDecl('determineSolution');</script>

(int <span class="funcparam">x</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>PBQP back propagation
   
<br><br>

<br><br>

    determine solution of a reduced node. Either
    RI or RII was applied for this node.
	
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">printSolution</span>
<script>explorer.outline.addDecl('printSolution');</script>

();
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>prints the solution
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">backPropagate</span>
<script>explorer.outline.addDecl('backPropagate');</script>

();
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>back popagation phase of PBQP
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">check</span>
<script>explorer.outline.addDecl('check');</script>

();
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>debug facilities
   
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">void 
<span class="currsymbol">solve</span>
<script>explorer.outline.addDecl('solve');</script>

();
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>PBQP 
<span class="currsymbol">solve</span>
<script>explorer.outline.addDecl('solve');</script>

 routines
   
<br><br>

 
<span class="currsymbol">solve</span>
<script>explorer.outline.addDecl('solve');</script>

 PBQP problem
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">double 
<span class="currsymbol">getMin</span>
<script>explorer.outline.addDecl('getMin');</script>

();
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>get minimum of PBQP
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">int 
<span class="currsymbol">getSolution</span>
<script>explorer.outline.addDecl('getSolution');</script>

(int <span class="funcparam">u</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>get solution of a node
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">int 
<span class="currsymbol">getNumNodes</span>
<script>explorer.outline.addDecl('getNumNodes');</script>

();
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>get number of nodes 
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">bool 
<span class="currsymbol">isOptimal</span>
<script>explorer.outline.addDecl('isOptimal');</script>

();
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>is solution optimal
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">protected void 
<span class="currsymbol">reinsertNode</span>
<script>explorer.outline.addDecl('reinsertNode');</script>

(int <span class="funcparam">u</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>node functions
 
<br><br>

 
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">protected void 
<span class="currsymbol">removeNode</span>
<script>explorer.outline.addDecl('removeNode');</script>

(int <span class="funcparam">u</span>);
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>remove node
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">protected bool 
<span class="currsymbol">solved</span>
<script>explorer.outline.addDecl('solved');</script>

;
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd><b>true</b> if 
<span class="currsymbol">solved</span>
<script>explorer.outline.addDecl('solved');</script>


<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">protected bool 
<span class="currsymbol">optimal</span>
<script>explorer.outline.addDecl('optimal');</script>

;
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd><b>true</b> if 
<span class="currsymbol">optimal</span>
<script>explorer.outline.addDecl('optimal');</script>


<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">protected WeightedGraph 
<span class="currsymbol">graph</span>
<script>explorer.outline.addDecl('graph');</script>

;
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>internal 
<span class="currsymbol">graph</span>
<script>explorer.outline.addDecl('graph');</script>

 representation
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">protected NodeList[] 
<span class="currsymbol">bucketList</span>
<script>explorer.outline.addDecl('bucketList');</script>

;
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>the bucketlist holds a list of nodes
      for every possible degree of a node (see createBucketList)
		
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">protected int[] 
<span class="currsymbol">nodeDegree</span>
<script>explorer.outline.addDecl('nodeDegree');</script>

;
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>used by reorder node to determine previous
      node degree
		
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">protected double 
<span class="currsymbol">minimum</span>
<script>explorer.outline.addDecl('minimum');</script>

;
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>current 
<span class="currsymbol">minimum</span>
<script>explorer.outline.addDecl('minimum');</script>


<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">protected int[int] 
<span class="currsymbol">solution</span>
<script>explorer.outline.addDecl('solution');</script>

;
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>order of node reduction
<br><br>

</dd>

<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl">protected int[] 
<span class="currsymbol">stack</span>
<script>explorer.outline.addDecl('stack');</script>

;
</span></dt>
<script>explorer.outline.writeEnabled = false;</script>


<dd>for backpropagation
<br><br>

</dd>
</dl>
<script>explorer.outline.decSymbolLevel();</script>


</dd>
</dl>
<script>explorer.outline.decSymbolLevel();</script>


</td></tr>
        <tr><td id="docfooter">
            Page was generated with
            <img src="candydoc/img/candydoc.gif" style="vertical-align:middle; position:relative; top:-1px">
            on Mon May 15 23:45:43 2006

        </td></tr>
    </table>
</div>
<script>
	explorer.packageExplorer.addModule("nova.ds.intrusive.aggregate");

	explorer.packageExplorer.addModule("nova.ds.intrusive.doublelink");

	explorer.packageExplorer.addModule("nova.ds.intrusive.doublelinkedlist");

	explorer.packageExplorer.addModule("nova.ds.intrusive.redblacktree");

	explorer.packageExplorer.addModule("nova.ds.intrusive.singlelinkedlist");

	explorer.packageExplorer.addModule("nova.math.matrix");

	explorer.packageExplorer.addModule("nova.math.optimization.partitionedbooleanquadric");

	explorer.packageExplorer.addModule("nova.ds.graph.weighted");
</script>
</body></html>

