Static Analysis: GRANLOG

Static analysis consists of inferring useful information about a program at compile-time. There are several kinds of static analysis. Among them we can mention:

• Abstract Interpretation [34]: obtaining useful information of a program such as predicate modes, argument types, flow and variable dependencies through a simulation of the program execution using an abstract domain. This abstract domain preserves the general form of the program execution allowing for analysis of data flow and prediction of the dynamic program behaviour.

• Complexity Analysis: obtaining information about computational time and space complexity of programs.

• Granularity Analysis: obtaining grain size of goals and clauses for parallel execution.

In our work we concentrated on these three kinds of analysis and developed four main tools that were integrated to produce useful information to guide program execution and scheduling decisions.

• GRANLOG (GRanularity ANalyzer for LOGic programming): GRANLOG [14,102,9,13] does automatic granularity analysis of Prolog programs generating an annotated program. It uses several advanced static analysis techniques such as Global Analysis [11] via Abstract Interpretation, Granularity Analysis [10] and Complexity Analysis [12];

• PARTY (Parallel Types Analyzer): PARTY [26,27] is a compile-time tool that infers argument types in Prolog programs using abstract interpretation. It can utilise intervals to determine argument types.

• ORCA (OR Complexity Analyzer): ORCA [12] does complexity analysis of Prolog programs. It generates simplified information that can be utilised for determining or-complexity [12].

• MODA (Mode and Dependency Analyzer): MODA [4] does abstract interpretation of Prolog programs in order to obtain predicate modes and dependencies.

These modules were integrated on a unique module so-called GRANLOG.

The GRANLOG system is composed of three modules:

• Global Analysis [11]: This module infers predicate modes, argument types, argument, goals and clauses sizes and dependencies in Prolog programs. PARTY and MODA are integrated in this module [5,4]. The global analysis module accepts a Prolog program as input and generates an annotated program with predicate modes, argument types, argument, goals and clauses sizes, as well as goal dependencies.

• Granularity Analysis [10]: This module is responsible for inferring grain sizes of goals and clauses that are useful to exploit parallelism and distribute work among the processors. The sizes are inferred based on the dependency information generated by the global analysis module. The granularity analysis module accepts a Prolog program and information generated by the global analysis module as input and generates an annotated program with a description of the grain sizes existing in the program.

• Complexity Analysis [12,100]: This module does the complexity analysis of Prolog programs. In this module we can find two integrated sub-modules: ORCA [12] and CASLOG [69]. ORCA is responsible for generating simplified information that can be used in the and-analysis or in the or-analysis [12]. CASLOG makes a very sophisticated static analysis of Prolog programs generating complexity information that can be as complex as a recurrent equation [12]. The complexity analysis module accepts an annotated program as input (output of the granularity analysis module) and generates an annotated program with information about complexity based on the granularity information [14].

In order to prove the usefulness of the information provided by the GRANLOG subsystem, we implemented scheduling strategies based on the granularity and complexity analysis generated by the GRANLOG subsystem [65,49,50].