Array Basic (Unit - I ) DS

Abstract

Precise modeling of the program heap is fundamental for understanding the behavior of a program, and is thus of significant interest for many optimization applications. One of the fundamental properties of the heap that can be used in a range of optimization techniques is the sharing relationships between the elements in an
array or collection. If an analysis can determine that the memory locations pointed to by different entries of an array (or collection) are disjoint, then in many cases loops that traverse the array can be vectorized or transformed into a thread-parallel version. This paper introduces several novel sharing properties over the concrete heap and corresponding abstractions to represent them. In conjunction with an existing shape analysis technique, these abstractions allow us to precisely resolve the sharing relations in a wide range of heap structures (arrays, collections, recursive data structures, composite heap structures) in a computationally efficient manner. The effectiveness of the approach is evaluated on a set of challenge problems
from the JOlden and SPECjvm98 suites. Sharing information obtained from the analysis is used to achieve substantial thread-level parallel speedups.

Introduction

The transformation of foreach style traversals on arrays/collections of scalars via vectorization and scheduling optimizations has had a major impact in improving the performance of optimized programs,
and thread–level parallelization of these loops is becoming increasingly important with the proliferation of multi–core processors. The ability to apply these transformations in modern object-oriented
programs that make heavy use of pointer structures and where arrays/collections often contain references to other heap structures (instead of scalar values) is severely limited by the difficulty of reasoning precisely about the structure of the program heap and the sharing relations between the pointers stored in these collections.
A significant amount of work has been devoted to the problem of shape analysis, which strives to provide precise information about the connectivity/reachability properties of the heap. A major
focus of this work has been on accurately modeling the construction and update of recursive data structures such as lists or trees [2, 11, 14, 15, 17, 18], while recent work explored how these recursive
structures are connected to form composite heap structures [2, 14]. These results are important steps in the development of a generalpurpose heap analysis technique and allow for the parallelization
of recursive data structure traversals, but they do not adequatel capture the sharing (or lack thereof) between the entries in a given
array or collection.
Take the simple program segment shown in Figure 1, which manipulates arrays of Data objects, each containing a single integer
field val. The first loop fills the array AU with a number of fresh
Data objects, and thus there is no aliasing between the entries in
the array. The second loop fills the array AS with objects selected
from the first array via some indexing function f(i), which we
assume cannot be understood by the analysis (e.g., f is a complex
non–linear transform or uses some form of randomization). Therefore, each entry in AS may potentially alias with another entry in
the array.

Base Heap Model

To analyze a program we first transform the Java 1.4 source into
a core sequential imperative language called MIL (Mid-level Intermediate Language). The MIL language is statically typed, has method invocations, conditional constructs (if, switch), exception handling (try-throw-catch) and the standard looping statements (for, do, while). The state modification and expressions cover the standard range of program operations: load, store, and assignment along with logical, arithmetic, and comparison operators. This mid-level language allows us to support the majority
of the Java 1.4 language while substantially simplifying the analysis. During this transformation step we also load in our specialized
standard library implementations, so we can analyze programs that use classes from java.util, java.lang or java.io. The semantics of the language is defined in the usual way,
using an environment mapping variables into values, and a store, mapping addresses into values. We refer to the environment and the store together as the concrete heap. We model the concrete heap as a labeled, directed multi-graph (N;E) where each node n 2 N is an object in the store or a variable in the environment,  and each labeled directed edge e 2 E represents a reference (a pointer between objects or a variable reference). Each edge is given a label that is either an identifier from the program or an integer i 2 N (the
integers label the pointers stored in the arrays/collections). For an edge (a; b) 2 E labeled with p, the notation a p ! b indicates that the object/variable a points to b via the field name or identifier p . A region of the heap  is a subset of the objects, with all the  pointers that connect these objects and all the cross-region pointers
that start or end at an object in this region .

Basic Properties

Our base abstract heap domain  is a directed graph in which each node represents a region of the heap or a variable, and each edge represents a set of pointers or a variable target. The nodes and edges are augmented with additional instrumentation properties: Types. Each non–variable node in the graph represents a region of
the heap (which may contain objects of many types). To track the types of these objects we use a set of type names as part of the label of each node. This set contains the type of any object that may be in the region of the heap that is abstracted by the given node.


Linearity. To model the number of objects abstracted by a given node (or pointers by an edge) we use a linearity property which has two possible values: 1, which indicates that the node (edge)
concretizes to either 0 or 1 objects (pointers), and the value w, which indicates that the node (edge) concretizes to any number of objects (pointers) in the range.

Abstract Layout. To approximate the shape of the region a node abstracts, the analysis uses the abstract layout properties f(S)ingleton, (L)ist, (T)ree, (M)ultiPath, (C)ycleg. The (S)ingleton
property states that there are no pointers between any of the objects abstracted by the node. The (L)ist property states that each object has at most one pointer to another object in the region. The other
properties correspond to the standard definitions for trees, DAGs, and cycles.
Pictorially, we represent abstract heaps as labeled, directed multi-graphs. The variable nodes are labeled with the name of the variable they represent. Nodes abstracting concrete regions are denoted as [id, type, linearity, layout]; the first field (id) contains a unique identifier, while the rest correspond to the predicates described above. The abstract edges, which approximate sets of pointers, are represented in the figures as records [id, offset, linearity].
The offset component indicates the label of the references that are abstracted by the edge: a field identifier, a variable name when the edge connects a variable and a node, or the special label ? denoting
the summary field for all the elements in an array or a collection object .

Abstract Sharing

To model the concrete properties just defined, we introduce two instrumentation predicates, one to track relations between references which are abstracted by different edges in the model (connectivity),
and one to track the relations between references which are abstracted by the same edge in the model (interference).
Connectivity. Given the relation predicates in the concrete regions
we can define a series of connectivity properties, connectivity = fshare; connected; disjointg, on the edges in the abstract domain. The concrete region  and the sets of references R, R
0 are a valid concretization of the edges e and e 0 To represent the connectivity property in the figures we extend the label of every edge e with a list of the identifiers of the other edges in the graph that it has a share or connected relation with. If an edge identifier e 0 in this list is prefixed with a “!” then
share(e; e 0 ) holds, while if there is no prefix then they are related by the connected predicate; if an edge identifier e 0 does not appear in the list, we will assume that disjoint(e; e 0 ) is true.



Interference. The interference property is closely related to the concept of connectivity. While the latter tracks relation predicates between references that are abstracted by different graphedges, the interference property tracks relation predicates between references that are abstracted by the same graph edge. Given
the definitions for the relation predicates in the concrete regions we can define a series of interference predicates, interference = faliasing(ap);interfering(ip); non–interfering(np)g, on the edges in
the abstract domain. The concrete region  and the set of references R are a valid concretization of edge e.



A recursive algorithm calls itself which usually passes the return value as a parameter to the algorithm again. This parameter is the input while the return value is the output.


Recursive algorithm is a method of simplification that divides the problem into sub-problems of the same nature. The result of one recursion is the input for the next recursion. The repletion is in the self-similar fashion. The algorithm calls itself with smaller input values and obtains the results by simply performing the operations on these smaller values. Generation of factorial, Fibonacci number series are the examples of recursive algorithms.


 Tail Recursion: It is a situation where a single recursive call is consisted by a function, and it is the final statement to be executed. It can be replaced by iteration.

Recursive functions

Many mathematical functions can be defined recursively:

• factorial
• Fibonacci
• Euclid's GCD (greatest common denominator)
• Fourier Transform

Many problems can be solved recursively, eg games of all types from simple ones like the Towers of Hanoi problem to complex ones like chess. In games, the recursive solutions are particularly convenient because, having solved the problem by a series of recursive calls, you want to find out how you got to the solution. By keeping track of the move chosen at any point, the program call stack does this housekeeping for you! This is explained in more detail later.


Example: Factorial

One of the simplest examples of a recursive definition is that for the factorial function:

factorial( n ) = if ( n = 0 ) then 1
                 else n * factorial( n-1 )

A natural way to calculate factorials is to write a recursive function which matches this definition:

function fact( int n )
 {
 if ( n == 0 ) return 1;
 else return n*fact(n-1);
 }

Note how this function calls itself to evaluate the next term. Eventually it will reach the termination condition and exit. However, before it reaches the termination condition, it will have pushed n stack frames onto the program's run-time stack.

The termination condition is obviously extremely important when dealing with recursive functions. If it is omitted, then the function will continue to call itself until the program runs out of stack space - usually with moderately unpleasant results!

Failure to include a correct termination condition in a recursive function is a recipe for disaster!

Another commonly used (and abused!) example of a recursive function is the calculation of Fibonacci numbers. Following the definition:

fib( n ) = if ( n = 0 ) then 1
           if ( n = 1 ) then 1
           else fib( n-1 ) + fib( n-2 )

one can write:

function fib( int n )
 {
 if ( (n == 0) || (n == 1) ) return 1;
 else return fib(n-1) + fib(n-2);
 }

Short and elegant, it uses recursion to provide a neat solution - that is actually a disaster! We shall re-visit this and show why it is such a disaster later.

Data structures also may be recursively defined. One of the most important class of structure - trees - allows recursive definitions which lead to simple (and efficient) recursive functions for manipulating them.

But in order to see why trees are valuable structures, let's first examine the problem of searching.

       
                                                            Backtracking

Backtracking is a general algotith for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.

The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight queens on a standard chessboard so that no queen attacks any other. In the common backtracking approach, the partial candidates are arrangements of k queens in the first k rows of the board, all in different rows and columns. Any partial solution that contains two mutually attacking queens can be abandoned, since it cannot possibly be completed to a valid solution.

Backtracking can be applied only for problems which admit the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a valid solution. It is useless, for example, for locating a given value in an unordered table. When it is applicable, however, backtracking is often much faster than brute force enumeration of all complete candidates, since it can eliminate a large number of candidates with a single test.

Backtracking is an important tool for solving constraint satisfaction problems , such as crosswords, verbal arithmetic, Sudoku, and many other puzzles. It is often the most convenient (if not the most efficient technique for parsing, for the knapsack  and other combinatorial optimization problems. It is also the basis of the so-called logic programming languages such as Icon, Planner and Prolog. Backtracking is also utilized in the (diff) difference engine .

Backtracking depends on user-given "black box procedures" that define the problem to be solved, the nature of the partial candidates, and how they are extended into complete candidates. It is therefore a metaheuristic rather than a specific algorithm — although, unlike many other meta-heuristics, it is guaranteed to find all solutions to a finite problem in a bounded amount of time.