Optimizing and
parallelizing compilers rely
upon accurate static disambiguation of memory references, i.e.
determining at compiling time if two given memory references always
access disjoint memory locations. Unfortunately thre presence of alias
in pointer-based codes makes memory disambiguation a non-trivial issue.
An alias arises in a a program when there are two or more disitnc ways
to refer to the same memory location. Program constructs that introduce
aliases are arrays, pointers and pointer-based dynamic data structures.
Over the past twenty years
powerful data
dependence analysis have been developed to resolve the problem of array
aliases. The problem of calculating pointer-induced aliases, called pointer analysis,
has also
received significant attention over the past few years.
Pointer
analysis can be divided into two distinct subproblems: stack-directed
analysis and heap-directed
analysis. We focus
our
research in the later, which deals with objects dynamically allocated
in
the heap. An important body of work has been conducted lately on this
kind of analysis. A promising approach to deal with
dinamically
allocated strucutres consists in explicitly abstracting the dynamic
store in the form of a bounded graph. In other words, the
heap is
represented as a storage shape graph and the analysis try to
estimate some shape properties of the heap data structures. This type
of
analysis is called shape
analysis.
A powerful shape
analysis framework has been developed in our research group.
Basically, the goal of our
research is to use
our shape analysis framework to develop advanced compiling techniques
for parallelism detection and exploiting locality in programs
that
operate with pointer-based data structures.
Faculty:
Graduate
Students:
- Rafael
Gutiérrez, Ph.D.
student.
- Adrián
Tineo, Ph.D. student.
- Rosa
Castillo, Ph.D. student.
- A. Tineo, F. Corbera, A. Navarro, R. Asenjo. "On the Automatic
Detection of Heap-induced Data Dependences with Interprocedural Shape
Analysis". 3rd International Workshop on Advanced Distributed and
Parallel Network Applications (ADPNA'2009), at IEEE ICPP'2009
Conference. Viena, Austria, September 22-25, 2009.
- A. Navarro, R. Castillo, F. Corbera, R. Asenjo, E.L. Zapata.
"Conflict Analysis for Heap-based Data Dependence Detection". International
Conference on Parallel Computing (ParCo'2009). Lyon, France,
September 1-4, 2009. Also published in Parallel Computing: From Multicores and GPU's to Petascale, B. Chapman et al. (Eds.), vol. 19, pp. 351-358, IOS Press, 2010
- R. Castillo, F. Corbera, A. Navarro, R. Asenjo, and E.L.
Zapata. "Complete
DefUse-Analysis in recursive programs with dynamic data structures".
Workshop on
Productivity and Performance (PROPER 2008) Tools for HPC Application
Development, at EuroPar'2008 Conference, Las Palmas
de Gran Canaria, Spain, August 2008. Also published in Lecture Notes in Computer Science, E. Luque et al. (Eds.), vol. 5415,
pp. 265-274, 2009.
- R. Asenjo, R. Castillo, F. Corbera, A. Navarro, A. Tineo
and E.L.
Zapata, "Parallelizing
Irregular C codes assisted by Interprocedural Shape Analysis",
22nd IEEE
International Parallel and Distributed Processing Symposium (IPDPS'2008),
Miami, Florida,
USA, April
14-18, 2008.
- A. Tineo, F. Corbera, A. Navarro, R. Asenjo and E.L.
Zapata, "Tracing
Recursive Flow Paths for Interprocedural Shape Analysis", 20th International Workshop on
Languages
and Compilers for
Parallel Computing (LCPC'2007), Urbana, Illinois,
USA, October
11-13, 2007.
- J.J. Segura, R. Asenjo, F. Corbera, A. Navarro and E.L.
Zapata, " Interfaz para
la captura de estructuras de datos dinámicas en
códigos C", XVIII
Jornadas de Paralelismo,
Zaragoza, Spain, September 11-14, 2007, pp. 867-874.
- A. Tineo, F. Corbera, A. Navarro, R. Asenjo and E.L.
Zapata, "A Compiler
Framework for Automatic Parallelization of Pointer-based Codes",
3rd International
Summer School on Advanced Computer Architecture and Compilation for
Embedded Systems (ACACES 2007),
L'Aquila, Italy, July 15-20, 2007.
- R. Castillo, F. Corbera, A. Navarro, R. Asenjo and E.L.
Zapata, "Interprocedural
Def-Use Chains for Pointer-based Codes Optimizations", 3rd International Summer School
on Advanced Computer Architecture and Compilation for Embedded Systems
(ACACES 2007),
L'Aquila, Italy, July 15-20, 2007.
- R. Castillo , F. Corbera, A. Navarro, R. Asenjo and E.L.
Zapata, "Parallelization
of Dynamic Data Structures in Pointer-based Programs", Transnational Access Meeting, HPC
EUROPA EVENT, Bologna, Italy, June 2007.
- A. Navarro, F. Corbera, A. Tineo, R. Asenjo and E.L.
Zapata, "Detecting
Loop-Carried Dependences in
Programs with Dynamic Data Structures", Journal of Parallel and
Distributed
Computing, vo. 67, issue 1, January 2007, pp. 47-62.
- R. Castillo, F. Corbera, A. Navarro, R. Asenjo and E.L.
Zapata, "Pointer
Analysis Techniques
targeted to accelerate Shape Analysis", XVII Jornadas de Paralelismo,
Albacete, Spain, September 18-20, 2006, pp. 603-608.
- R. Castillo, A. Tineo, F. Corbera, A. Navarro, R. Asenjo
and E.L.
Zapata, "Towards a
Versatile Pointer
Analysis Framework", European
Conference on Parallel
Computing
(Euro-Par'2006),
Dresden, Germany, 29th August - 1st September, 2006. Also published in Lecture Notes in Computer Science,
W.E. Nagel et al. (Eds.), vol. 4128, 2006,
pp.
323-333.
- A. Tineo, F. Corbera, A. Navarro, R. Asenjo and
E.L.
Zapata, "Shape Analysis
for Dynamic
Data Structures based on Coexistent Links Sets",
13th
International Workshop on Compilers for Parallel Computers (CPC'2006),
A Coruña, Spain, January 9-11, 2006.
- A. Tineo, F. Corbera, A. Navarro, R. Asenjo and E.L.
Zapata, "A new Strategy
for Shape Analysis based on
Coexistent Links Sets", Parallel
Computing
(ParCo'2005),
Univ. of Malaga, Spain, September 13-16, 2005. Also published in Parallel Computig:
Current &
Future Issues of High-End Computing, G.R.
Joubert et al.
(Eds.), vol. 33, 2005, pp.557-564.
- O. Plata, R. Asenjo, E. Gutiérrez, F. Corbera,
A. Navarro
and
E. L. Zapata, "On the
Parallelization
of Irregular and Dynamic Programs", Parallel
Computing,
vol. 31, issue 6, June 2005, pp. 544-562.
- A. Tineo, F. Corbera, A. Navarro, R. Asenjo and E.L.
Zapata, "A novel
Approach for Detecting Heap-based
Loop-carried Dependences", IEEE
International Conference on Parallel Processing (ICPP'2005), Univ.
of Oslo,
Norway, June 14-17, 2005, pp. 99-106.
- A. Navarro, F. Corbera, R. Asenjo, A. Tineo, O. Plata and
E.L.
Zapata, "A new
Dependence Test Based
on Shape Analysis for Pointer-based Codes", 17th International Workshop on
Languages
and Compilers for
Parallel Computing (LCPC'2004), West Lafayette, Indiana,
USA,
September 22-25, 2004. Also published in Lecture Notes in Computer Science,
vol. 3602, 2005, pp. 394-408.
- F. Corbera, A. Navarro, R. Asenjo, A. Tineo and E.L.
Zapata, "A new
Loop-carried Dependence Detection
Approach for Pointer-based Codes", XV Jornadas de Paralelismo,
Almeria,
Spain, September 15-17, 2004, pp. 432-437.
- A. Navarro, R.G. Valderrama, F. Corbera, E.
Gutiérrez, R.
Asenjo, O. Plata and E.L. Zapata, "Exploiting
Locality and Parallelism in Pointer-based Programs", 11th
International Workshop on Compilers for Parallel Computers (CPC'2004),
Chiemsee,
Germany, July 7-9, 2004.
- R. Asenjo, F. Corbera, E. Gutiérrez, A.
Navarro, O. Plata
and E.L. Zapata, "Optimization Techniques for Irregular and
Pointer-based Programs", 12-th Euromicro Conference
on Parallel,
Distributed and Network based Processing (PDP'2004), La
Coruña, Spain, February, 11-13, 2004.
- O. Plata, R. Asenjo, E. Gutiérrez, F. Corbera,
A. Navarro
and E.L. Zapata, "On the Parallelization of Irregular and
Dynamic
Programs", 10th International Workshop on Compilers
for Parallel
Computers
(CPC'2003), Amsterdam, The Netherlands, January 8-10, 2003.
Back