27. The Loci Rule-Based Programming Framework

The framework used for the development of Stream is called Loci [Luk99] which is programming framework designed to reduce the complexity of assembling large-scale finite-volume applications as well as the integration of multiple applications in a multidisciplinary environment. Unlike traditional procedural programming systems (C, FORTRAN) in which one writes code with subroutines, or object-oriented systems (C++, Java) in which objects are the major program components, Loci uses a rule-based framework for application design. Users of Loci write applications using a collection of “rules” and provide an implementation for each of the rules in the form of a C++ class. In addition, the user must create a database of “facts” which describe the particular knowns of the problem, such as boundary conditions. Once the rules and facts are provided, a query is made to have the system construct a solution. One of the powerful features of Loci is its ability to automatically determine the scheduling of events of the program to produce the answer to the desired query, as well as to test the consistency of the input to determine whether a solution is possible given the specified information. The other major advantage of Loci to the application developer is its automatic handling of domain decomposition and distribution of the problem to multiple processors.

In this section we provide a basic overview of the Loci programming system[Luk99] and describe how it is used to implement unstructured grid solvers. For more complete details on the Loci system, the reader should consult the Loci tutorial[Luk02] which is available with the Loci distribution. Following this overview, we will discuss some of the distinguishing features of Loci.

27.1. Loci: An Overview

Programs written in the Loci framework consist of the following three general components:

Fact Database: This database which is maintained by Loci contains all information which is known about the problem being solved. For finite-volume programs for fluid-flow and heat transfer, this information usually consists of items such as boundary conditions, initial conditions, material properties, and the combustion mechanism among other things. The fact database is usually constructed during the input section of the user’s program. For example, the user may have a function called readBoundaryConditions() inside which the boundary conditions associated with the problem would be read and entered into the fact database.

Rules: Rules can be thought of as the components of the finite-volume algorithm which are used to compute the desired solution from the known facts. Each rule can be represented in symbolic form by a “rule signature”. For example, a rule to compute the centroid of the triangles in a 2-D unstructured grid can be represented by the following rule signature:

triangleCentroid<-triangleNodes->position

This rule can be translated to read “the centroid of each triangle is computed from the position property of the triangle’s nodes”. The <− operator signifies the output of a rule, while the −> operator signifies that we are using the position property of the triangle nodes in the calculation process. This rule signature is really only a symbolic representation of what the rule is doing. For each rule signature, the programmer must supply a C++ class which actually implements the functions of the rule. An example of this is given later.

Query: Once the facts and rules are specified, one obtains the solution by executing a “query” to the fact database for a desired solution. At this point Loci attempts to order all the rules into an execution schedule which can produce the solution. If Loci finds that it is not possible to arrive at a solution given the known facts and list of rules, it will inform the user. A skeleton main function for a finite volume code is shown below.

int main(int argc,char *argv[]){

// Initialize the LOCI system.
Loci::Init(&argc,&argv) ;

// Setup the fact database and read known facts. Grid and boundary conditions
// are inserted into the fact database.
fact_db factDatabase ;
readGrid(factDatabase) ; readBoundaryConditions(factDatabase) ; ...

// Add all previously registered rules which define the finite-volume
// program to the rule database. Each rule is specified as a C++ class and
// registered in the global rule list in a separate implementation file.
rule_db ruleDatabase ; ruleDatabase.add_rules(global_rule_list) ;

// Distribute the rules and facts to the various processors.
int numProcesses=Loci::MPI_processes,myID=Loci::MPI_rank ;
std::vector<entitySet> partition=Loci::generate_distribution(factDatabase,ruleDatabase) ;
Loci::distribute_facts(partition,factDatabase,ruleDatabase) ;

// Specify the 'query' and set up an execution schedule to satisfy it. Here
// we are asking for the solution, which also happens to be a rule.
string query("solution") ;
executeP schedule=create_execution_schedule(ruleDatabase,factDatabase,query) ;

// Execute the schedule to produce the solution.
schedule->execute(factDatabase) ;

// Finalize the LOCI system.
Loci::Finalize() ;
}

27.2. Basic Data Structures of Loci

In order to provide some foundation for understanding the implementation files for the rules which compose any finite-volume program constructed using the Loci system, we present some of the basic data structures used in Loci. Only the data structures required for understanding the following material are provided here.

Entity:

This data type is used to identify objects in Loci (e.g. triangles, edges, etc.). In Loci, each entity is given an integer number for identification. For example, a list of triangle entities can be created by the following statement, where numTriangle has been previously defined (maybe by reading a grid file):

Entity triangles(numTriangle) ;

The triangle entities in this list are numbered sequentially from 0 to (numTriangle-1).

Store:

The data type is essentially an array which holds a number of values. Stores are usually associated with a collection of entities. The store then holds a single value for each entity. For example, we may have a store to hold the centroid value for a collection of triangles as follows:

store<vector2d<double>> triangleCentroid ;

MapVec:

This data structure is used to map one collection of entities to another. For example, to hold the triangle-to-node connectivity information in a 2-D finite-volume code we would have the following:

MapVec<3> triangleNodes ;

Thus, for each triangle, we hold the three global node numbers which define the triangle.

27.3. Implementation of Rules in Loci

In Loci, each rule that composes the program is implemented in the form of a C++ class, which provides the functionality associated with the rule.

Each rule class provides three basic functions:

1. A constructor, which essentially registers the data used and produced by the rule with LOCI

2. A calculation method which specifies the procedure for computing the output for a single entity.

3. A compute method which calls calculate() for a sequence of entities. This method is implemented in LOCI as a template function, which allows LOCI to avoid calling the virtual method calculate() at the loop level, which would significantly decrease the calculation efficiency.

In addition to the rule implementation class, one also creates a global register_rule<> object which allows the rule to be registered with the global rule list which is maintained by LOCI.

A sample implementation for the triangle centroid rule discussed previously is shown below.

class triangleCentroid : public pointwise_rule {
  private:
    const_store<vector2d<double> > position ;
    const_MapVec<3> triangleNodes ;
    store<vector2d<double> triangleCentroid ;

  public:
    // Constructor to provide symbolic names for the data used in this rule and to define the input and output quantities.
    triangleCentroid() {
      name_store("position",position) ;
      name_store("triangleNodes",triangleNodes) ;
      name_store("triangleCentroid",triangleCentroid) ;
      input("triangleNodes->position") ;
      output("triangleCentroid") ;
    }

    // Method which performs the calculation for a single Entity.
    void calculate(Entity e) {
      triangleCentroid[e]=(position[triangleNodes[e][0]]+
      position[triangleNodes[e][1]] + position[triangleNodes[e][2]]) / 3.0;
    }

    //Template function to call calculate method for sequence of entities.
    virtual void compute(const sequence &sequence) {
      do_loop(sequence,this) ;
    }
} ;

// Create a global object that will register this rule in the global rule list.
register_rule<triangleCentroid> registerTriangleCentroid ;

27.4. Distinguishing Features of the Loci Programming Framework

In using any new system for writing finite-volume applications, the general hope is that one will spend less time on the actual mechanics of writing code, and thus more time concentrating on improving other aspects of the solver, such as the implementation of additional turbulence models or the integration with other solvers to handle multi-disciplinary physics. After all, scientists/engineers are not in the business of writing code for fun ─ usually there is a physical problem that needs to be solved. In this regard, there are two major benefits in using Loci, rather than other modern coding techniques such as standard object-oriented programming in C++, namely:

1. Loci is designed with multi-disciplinary problems in mind

2. Loci automatically handles the partitioning of the unstructured problem in the distributed-memory environment.

27.5. Seamless Integration of Multi-Disciplinary Physics

With the rapid development of computer hardware, complex problems involving multi-disciplinary physics can now be routinely solved. For example, one may solve a fluid flow/heat transfer problem in some combustion device, where one not only computes the fluid flow using a finite-volume solver, but also solves the heat-transfer and stress problem in the solid section of the device simultaneously. One approach commonly used is to solve each section (fluid or solid) independently and iterate several times until a converged solution is obtained in both regions. In this approach, the fluid and solid solution procedures are said to be loosely coupled, and in fact most often are obtained using different solvers which have no knowledge of each other. This approach works fine but is usually a very slow process due to the loose nature of the coupling between the two domains.

A better approach to the multidisciplinary problem involves the so-called tight coupling between the components, in which the different solvers operate in a more closely coordinated manner. In such a fashion, each of the solvers has some knowledge of the other, and the interface between the components allows data to be exchanged at a much higher frequency, usually at the inner iteration level. In the most extreme case of tight coupling, all components (fluid/heat- transfer/stress) are solved together simultaneously at every iteration. In this case, there is really only one solver.

One of the major strengths of Loci is its ability to handle all approaches, from loosely-coupled to tightly-coupled. When writing applications in Loci, it is not necessary that all components of the application be entirely written within the rule-based framework. Applications can exist as independent modular components which can be linked to other components written entirely in Loci by encapsulating the component as a rule. For example, Loci has an interface to the PETSc[BBG+03] linear algebra library. In both the loosely- and tightly-coupled approaches, a significant advantage of Loci is its ability to check the internal consistency of a program. Often times, components of a multidisciplinary application may be written by different developers, who may not have detailed knowledge of all system components. When all components are used to solve a given problem, Loci guarantees that a program schedule is generated which ensures that information between the components is computed at the appropriate time and all information required by each component is available when it is needed. If the components cannot be linked together due to an insufficient specification of the interface between them, Loci informs the user that a schedule cannot be generated and terminates execution. This feature completely eliminates errors associated with inter-component coordination, which become more common in complex codes written in a multidisciplinary environment.

27.6. Grid Partitioning for Distributed-Memory Environment

Regarding the second issue, one can see from the main program example in that it is very simple to create programs which can run in a distributed memory environment. Loci handles all partitioning of the problem, including the grid, the rule database and the fact database. This feature of Loci is a major advantage over other approaches such as standard object-oriented C++, where the programmer must entirely code and debug a separate layer of the program devoted to partitioning of the problem. For scientists/engineers inexperienced in the area of message-passing (e.g. MPI), the use of Loci entirely eliminates the need for this extra complexity.

Fig. 27.6.1 Demonstration of parallel scalability of Stream: measured speed-up on 3 different mesh sizes for flow over a prolate spheroid at incidence (this case was run on the AFRL HP XC Opteron system).

stream is routinely run on high-performance computers with parallel architectures – it maintains excellent parallel scalability for grids involving a few million to hundreds of million cells. The plots shown above involve a turbulent flow past a prolate spheroid at an angle of incidence. This case was run on the AFRL HP XC Opteron system (Falcon) at Naval Surface Warfare Center, Panama City, FL (courtesy: Richard Smith). Three different meshes were employed, the finest comprising 15 million nodes. It can be seen that, in this example, stream demonstrates linear scalability up to 1000 processors for the finest mesh.

This appendix provides only the conceptual bridge needed by the theory guide. Detailed Loci syntax, rule-writing patterns, scheduling behavior, debugging workflows, and Stream-specific naming conventions are maintained in the repository’s developer documentation under documentation/loci/.

27.7. References

[BBG+03]

S. Balay, K. Buschelman, W. Gropp, D. Kaushik, M. Knepley, L. McInnes, B. Smith, and H. Zhang. Petsc user's manual. Technical Report, Argonne National Laboratory, 2003.

[Luk99] (1,2)

E.A. Luke. Loci: a deductive framework for graph-based algorithms. In S. Matsuoka, R. Oldehoeft, and M. Tholburn, editors, Third International Symposium on Computing in Object-Oriented Parallel Environments, volume 1732 of Lecture Notes in Computer Science, 142–153. Springer-Verlag, Dec. 1999.

[Luk02]

E.A. Luke. Loci: a tutorial. Technical Report, Mississippi State University, 2002.