commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From l..@apache.org
Subject svn commit: r657744 - /commons/sandbox/nabla/trunk/src/site/xdoc/internals.xml
Date Mon, 19 May 2008 07:41:24 GMT
Author: luc
Date: Mon May 19 00:41:24 2008
New Revision: 657744

URL: http://svn.apache.org/viewvc?rev=657744&view=rev
Log:
explained the data flow analysis with marked data elements and changed instructions

Modified:
    commons/sandbox/nabla/trunk/src/site/xdoc/internals.xml

Modified: commons/sandbox/nabla/trunk/src/site/xdoc/internals.xml
URL: http://svn.apache.org/viewvc/commons/sandbox/nabla/trunk/src/site/xdoc/internals.xml?rev=657744&r1=657743&r2=657744&view=diff
==============================================================================
--- commons/sandbox/nabla/trunk/src/site/xdoc/internals.xml (original)
+++ commons/sandbox/nabla/trunk/src/site/xdoc/internals.xml Mon May 19 00:41:24 2008
@@ -37,7 +37,13 @@
           are elementary ones. Each elementary operation is then
           changed to compute both a value and a derivative. Nothing is
           changed to the control flow instructions (loops, branches,
-          operations scheduling).
+          operations scheduling). The entry point of this differentiation
+          process is the <a
+          href="apidocs/org/apache/commons/nabla/automatic/analysis/MethodDifferentiator.html#visitEnd">
+          visitEnd</a> method of the <code>MethodDifferentiator</code>
+          which is called from the <a href="apidocs/org/apache/commons/nabla/automatic/analysis/AutomaticDifferentiator.html">
+          AutomaticDifferentiator</a> class for processing the <code>f</code>
+          method of the user class.
         </p>
 
         <p>
@@ -156,13 +162,6 @@
         </p>
 
         <p>
-          The only methods from the <code>DifferentialPair</code> class that
-          are used by the automatic differentiator are the two arguments
-          constructor, the <code>getValue</code> method and the
-          <code>getFirstDerivative</code> method.
-        </p>
-
-        <p>
           For differentiable functions that call other differentiable functions,
           additional instances of <code>DifferentialPair</code> will be used.
           Some will be built in the caller to pass parameters to the callee, and
@@ -175,6 +174,17 @@
           and some intermediate arithmetic operations.
         </p>
 
+        <p>
+          The only methods from the <code>DifferentialPair</code> class that
+          are used by the automatic differentiator are the two arguments
+          constructor, the <code>getValue</code> method and the
+          <code>getFirstDerivative</code> method. As far as automatic
+          differentiation is concerned, all the other methods could be removed
+          from the class. In fact, they are only present for user convenience
+          if they wish to perform additional computation after a function has
+          been differentiated.
+        </p>
+
       </subsection>
 
       <subsection name="Data flow analysis">
@@ -184,18 +194,59 @@
           contains both immutable parts that must be preserved and
           parts belonging to what we will call the <em>computation path</em>
           from the <code>t</code> parameter to the result that must
-          be differentiated. The instructions that must be converted are
-          identified by a data flow analysis seeded with the <code>t</code>
-          parameter, which is changed from a primitive <code>double</code>
-          in the original method to a <code>DifferentialPair</code> in the
-          generated derivative, as explained in the <a
-          href="usage.html#Differential_pairs">Differential pairs</a> section
-          of the usage documentation.
+          be differentiated. The instructions that belong to the computation
+          path and hence that must be converted are identified by a data
+          flow analysis seeded with the <code>t</code> parameter.
+        </p>
+
+        <p>
+          The first step of this data flow analysis is to link each data element
+          (either stack cell or local variable, as explained in the <a
+          href="#Virtual_machine_execution_model">virtual machine execution
+          model</a> section) with the instructions that may produce it and the
+          instructions that may consume it. This task is realized by the <a
+          href="apidocs/org/apache/commons/nabla/automatic/analysis/TrackingInterpreter.html">
+          TrackingInterpreter</a> and <a
+          href="apidocs/org/apache/commons/nabla/automatic/analysis/TrackingValue.html">
+          TrackingValue</a> classes.
+        </p>
+ 
+        <p>
+          As explained in the <a href="usage.html#Differential_pairs">Differential
+          pairs</a> section of the usage documentation, the signature of
+          the <code>f</code> method is changed. The primitive <code>double</code>
+          <code>t</code> parameter in the original method is changed during
+          the differentiation process to a <code>DifferentialPair</code>
+          instance in the generated derivative. This instance is itself
+          expanded right from the start of the method into a pair of primitive
+          <code>double</code> local variables that can be used throughout the
+          method code.
         </p>
 
-        <p><strong>
-          TODO: explain analysis by "tainted" data and types propagation.
-        </strong></p>
+        <p>
+          All instructions that used the original primitive <code>double</code>
+          parameter must be changed to cope with the new pair of primitive
+          <code>double</code> local variables. In order to do this, the
+          representation of the <code>t</code> parameter in the bytecode is
+          marked as pending conversion from one primitive <code>double</code>
+          to a pair of primitive <code>doubles</code>. Once this data element
has
+          been marked, the data flow will propagate the mark to other data
+          elements (both variables and operand stack cells) thanks to the following
+          rules:
+          <ul>
+            <li>
+              each instruction that consumes a marked data element must be changed
+            </li>
+            <li>
+              each primitive <code>double</code> data element produced by a changed
+              instruction must be marked as pending conversion from one primitive
+              <code>double</code> to a pair of primitive <code>doubles</code>
+            </li>
+          </ul>
+          These rules propagate the changes for data and instructions throughout the
+          method code, affecting all instructions that need to be changed and leaving
+          other instructions alone, like the loop handling in the example above.
+        </p>
 
       </subsection>
 



Mime
View raw message