A Hierarchical Task Level Representation of Java Programs forParallelization
Antonio Magnaghi and Hidehiko Tanaka
The University of Tokyo

representation model. The hierarchy among classes
makes additional information available about program
structure that could be used in order to improve performance. This paper will not provide a formal speci cation of the concept of HTG for Java because ofspace limitations. Rather, we will proceed intuitively
through an example that will further be developed infollowing sections. Let m be a method de ned as follows:

1 Introduction
Extraction of parallelism from source programs is animportant and active area of research in the eld ofcompiler design. By actual trends, code parallelization is accredited as a key technology for an ecientutilization of computational resources. However, direct detection of parallelism is generally a diculttask, whose scope spans di erent conceptual levels [4].
In particular, there exists a strict mutual interdependency between the speci c type of parallelism to consider in automatic reconstruction and the target architecture. Therefore status-of-art architecture technology impacts on compiler design. The scenery is basically dominated by two major complementary strategies. On one hand, dedicated ad-hoc hardware components are produced and assembled into complex systems. The remarkable development costs in such acase are justi ed by the intent to aggressively utilizea precise form of parallelism. Numerical application
programs are one of the most relevant examples, also
for historical reasons due to the popularity of Fortranfor scienti c computations. However for most commercial applications it is not admissible such an investmentof capital on new components, yet advantages are relevant deriving from extraction of concurrency. In sucha stream, the employment of o -the-shelf components
has led to those kinds of architectures such as PCnetworks, cluster of workstation or hybrid con gurations. The new perspectives revealed by this approach
constitute the framework to our research project about
Java language.
2 Java and the Hierarchical Task Graph
Our research project aims at the development of proper
techniques to optimize programs written in Java. The
choice of Java can be motivated by the considerationthat it includes many of the most meaningful and advanced features of programming languages such as Cand C++. Java introduces new elements [3], in particular the thread paradigm for parallel program execution is part of the language speci cation. Nonetheless, also some important restrictions are imposed. The
most relevant ones do not allow memory address arithmetic, the goto statement and multiple inheritance.
Our approach consists in restructuring source programs, based on the introduction of the HierarchicalTask Graph (HTG). Previously the HTG was introduced only for C language [2]. As original contribution,
we aim at extending it to Java and analyzing how inheritance mechanism can impact on such a programvoid m(){ 1: obj_3.m_1(13);
2: obj_1.m_3();
3: obj_1.m_2();
4: for(...)
5:obj_1.m_1(17);
6: obj_2=obj_1; }The relationship between classes and methods is expressed by the taxonomy of gure(1). obj1 ; obj2 ; obj3
REM

&

YRLG P LQW L
YRLG P

REM
REM

&

&
YRLG P LQW L

YRLG P LQW L&YRLG P

Figure 1: Class Taxonomy
are instances of classes C1 ; C12 ; C11 respectively.
m1 ; m2 ; m3 are methods. The HTG of input programs
is built from control ow and data dependency. It
provides an intermediate representation which decomposes the program in constituents tasks of di erent
granularity. Let us focus on method m. We assume
the existence of a class containing a static variable v :v 2 use(m1 of C11 ); v 2 def (m3 of C1 ). Moreover
methods m1 ; m2 do not alter the internal state of theobject they use as input. The HTG of m is showed
in gure (2). The instructions of m have been represented by single nodes because they contains control
ow transfer due to method invocations, and each node
should be linked to the HTG of the associated method.
Solid arcs correspond to control ow and dotted ones
represent data dependency. In particular, in node 2,
m3 assigns a new value to variable v ; in node 5 thatvalue could be used, hence the dependency edge from 21

to 5 is required. Figure (2) shows that the HTG is obtained by merging control ow and data dependency
in a structured manner. Nodes 4 and 5 are grouped
together to form a loop-component, labeled 4-5, whose
granularity level is the same as nodes 1, 2, 3 and 6, if it
is considered as an atomic unit. On the other hand, if
we need to concentrate on ner grain parallelism, it ispossible to re ne the information associated to node 45, analyzing its inner structure. Hence we can conclude
that the represented task graph contains two distinct
levels, hierarchically related to each other. However inprevious considerations the taxonomy among classes
has not been properly utilized. Our investigation aims
at optimizing the information encapsulated in the HTG
of a Java program by detecting and consequently deleting potential dependency constraints that actually do
not subsist because of program semantics and inheritance structure.










Figure 2: HTG of method m
3 Optimizing the HTG
Object-oriented technology relies on the concept thatevery data type is de ned not only by its internal structure, but also by the operations we can perform on it.
And inheritance allows to represent the relationships
among instances of di erent classes. The taxonomy ofJava code provides additional information whose utilization can reveal insights about the program behavior. Let us consider the HTG of gure (2), and thedata dependency arc connecting nodes 2 and 5. It
imposes to delay the execution of instruction 5 until
instruction 2 has completed. The following analysis ofinheritance structure and program semantics will showthat such and arc can be safely suppressed improvingperformance. Let H=(C,E) be the tree of classes in
the program, where C is the set of classes and E theset of connecting edges. Let P (obj ) denote the collection of all classes that are descendants to the classwhich object obj is declared of, including the class ofobj . In our example, P (obj1 ) = fC1 ; C11 ; C12 ; C121 g;P (obj2 ) = fC12 ; C121 g; P (obj3 ) = fC11 g. The mechanism of dynamic binding allows an object pointer topoint also any other instances of inner classes in the inheritance taxonomy. Hence a generic instance obj canpoint to any element in P (obj ). However, being able
to reduce the cardinality of the pointed-to instance set

can make parallelism extraction more e ective. Let us
focus on object obj1 . In instruction 3 method m2 isinvoked, which is a member only of class C121. obj1
is never assigned a di erent object in m, therefore its
actual object instantiation can not change and it is restricted to C121. We can statically foresee that method
activation in instruction 5 will dynamically be linked tomethod m1 which class C121 inherits from its parent.
As previously assumed, m1 in C12 does not use variablev , hence the potential data dependency of node 5 fromnode 2 does not actually occur, and the correspondingarc can be safely deleted. This guarantees that node
5 (or loop-level node 4-5) can be executed before node
2. In particular, the restriction of possible pointed-toobjects in the case of obj1 propagates to obj2 also: instruction 6 assures that obj2 can identify only instancesof class C121 .
The discussed example underlines that in Java polymorphism and dynamic binding produce a situation
where inter-procedural optimizations are complex. Anobject can potentially point to several class types,
therefore a conservative approach causes the loss of important information. An analogy can be drawn withpointer handling in C language: the diculty of tracing pointed-to data by a pointer limits the extractionof parallelism. However Java couples each program toits taxonomy of classes, where data types are mergedwith their associated methods. Hence new information is made available to the compiler, that, as shown
above, can re ne the HTG topology.
4 Conclusions
Our research aims at introducing the concept of HTG
to Java programs, in order to identify di erent task
levels for concurrency extraction. The interest in Java
springs from its state-of-art language design features,among which portability is a key factor for softwaredevelopment. The interest in the concept of HTG ismotivated by its high exibility in dynamically tuning
the granularity of program concurrency: Java applications can be executed on a wide category of architectures and the HTG representation can properly address
optimizing reconstructions for such systems.
References[1] C. Brownhill, A. Nicolau, S. Novack, C. Polychronopoulos. Achieving Multi-level Parallelization. Proc. of International Symposium ISHPC'97
Japan. Springer, pp. 183-194, 1997.
[2] C. Polychronopoulos.

TheHierarchicalTask. Proc. ofthe 1991 International Conference on Supercomputing. ACM, pp. 252-263, 1991

Graph and its Use in Auto-Scheduling[3] P. van der Linden. Just Java and Beyond, thirdedition. The Sunsoft Press, 1997[4] H. Zima, B. Chapman. Supercompilers for Paralleland Vector Computers. ACM press, 1992