Design for ADG System based on classification according to least program behavior
by
Walls Ch. Qiang
LASG, Institute of Atmospheric Physics (IAP), Chinese Academia Sinica, Box 9804, Beijing, P.R.China, 100029
Coauthors: Bin Wang

Abstract How to efficiently seek the adjoint model for a considered project is one of the most challenging topics in automatic differentiation literature. In this paper initial design for a new tool in AD family, Adjoint Code Generator (ADG) is introduced and through which, several key techniques aiming to model adjointisation are discussed. Those techniques contribute to such topics including data dependence detecting, hybrid of data access and code duplication method, least program behavior based classification, top-to-bottom adjointisation strategy, etc. The novel idea that based on functional modular classification according to least program behavior, the input object which is generally a procedure or function, is analyzed not only takes advantage of less data accessing and less code propagation, but makes the output code optimized to some extend. By this way, the code complexity is O(an) and the data complexity is far less than in the case which based on sentence-to-sentence analytical strategy. Another important topic is how to assure the reliability of produced adjoint code and how to evaluate the proficiency of such a class of AD tools. Here with some numerical experimental results from the adjointisation for GPS/MET Rayshootingm model, several major evaluation factors are analytically introduced.

Keywords automatic differentiation, model adjointisation, least program behavior Score years ago, Phil Wolfe disclose that the lower bound of the ratio between the differentiation model and its original model is 1.5. To close this desire result nowadays, more and more automatic differentiation systems have been created to meet with various assignments from different fields. Among these assignments, model adjointisation is currently a hot topic in automatic differentiation field because of its abroad applications and its NP property. Generally, the implementation of such AD tools is based on such basic fact that any procedure or function defined by its independent and dependent argument variables, can be classified into a sequence of program cells based on statement or functional modular class. By successively using the chain rule, the first- and higher- order differentiation of every composition can be formally produced. Through combining these results in nature way and their adjoints in reverse way, the differentiation model and the adjoint model can be obtained respectively. Here based on a novel classification to object model according to least program behavior, another efficient tool using to produce adjoint model is independently created. Model adjointisation either based on original model or TL model is mathematically transposition of Jacobi matrix, but it is often very sophisticated in such cases as nonlinear numerical computational statement and iterative blocks, in which the value of basic state with regard to active variables is required. So the key technical problems lies: i) classification for least program behavior, ii£©insertion for basic state in case of nonlinear statement£¬iii£©data accessing in case of recomputation statement, iv£©recognition and adjointisation for case of iteration block. A group of program statements is defined as a least program behavior if it is contended with all of following conditions: i) it cannot be null statement, ii) a rigid time sequential relation exists between any two closed least program behavior, in other word, every least program behavior can be executed no more than one time during a procedure or function running, iii) it cannot be classified as combination of several least program behaviors, iv) it does not include a statement that can terminate the current running.

Generally, circulation block, iterative block and even an independent numerical computational statement are least program behaviors. In this paper, the structure of adjoint model is initially described. According to functional modular classification, there are sequentially four main parts: variable definition, data preparation, resetting for disturbance of medium active variables, and construction for adjoint code. To insert basic state under case of nonlinear statement, there are generally two ways: data accessing and code duplication. If any of a method is taken, it cannot produce efficient adjoint code. To illustrate this, a procedure is given which has n statements and m recomputed active variables, and the number of least program behaviors is s, generally s<<n, and assumed complex enough and in code adjointisation nearly every statement requires to recompute the value for basic states. If code duplication method is separately taken, the code complexity is O(1/2n*n), and if only data accessing method is taken, the data complexity is O(nm). In this paper, a hybrid way based least program behavior classification is taken only to reach lower code complexity and data complexity, respectively O(an) and O(sm) where a is a statistical constant. The other key techniques will be presented in detail in the following sections.

The design of ADG system is based on following considerations. It takes the original model as its input object, and automatically adopt the optimum adjointisation strategy according to analysis for object complexity. It also adopts top-to-bottom analytical method in the whole the procedure or function while bottom-to-top adjointisation strategy in every least program behavior. Additionally, it takes advantage of hybrid method of data accessing and code duplication. Currently this system is under its perfection, and our goal is firstly, based on considerable numerical experiments to establish basic framework of model adjointisation theory and, to discuss some hot topics in this field. Secondly, it can accurately produce efficient adjoint computing code to special projects and reach lower code complexity and data complexity. Thirdly, based on object-oriented design methodology, ADG system is generally used to some extend in special applications, and characterized with merits of fine maintainability£¬easy-to-use property. Finally, it can accept any source code written in various versions from Fortran 77 to Fortran 90. Another important topic in automatic differentiation is how to evaluate the result code produced by a class of AD tools. Although different applications are followed by different requirements, such key factors as reliability of adjoint code£¬time and storage cost are of top importance. In this paper an evaluation way based statistical accurate rate is introduced to testify the dependency and efficiency of such a class of AD tools.

Generally, lower time and storage cost is not difficult to obtain in seeking first or higher order differentiation for a project model, but it is far more challenging in case of adjointisation for the same object. In the latter case, how to combine data access technique and code duplication method significantly takes effect to above evaluation factors referred. To a practical object model, however, legibility and elegance for result code, together with maintainability and normalization, are also required. In this field as long, the most challenging problem is not from those in technical implementation and methodology which are acquainted or known, but we are always lost in this case that there is "nothing" to do in practice by the so-called "NP" problem stemming from abundance of program language. As a result, any individual and any individual group£¬will never create an automatic differentiation system as perfect as any of program compilers. So as one of the fellows of AD field, I wish there is a center in which most top scientists in this field are gathered to do some basic research work, only to jointly bite this hard nut.

Date received: March 10, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caev-02.