Motivation

Probably, in a near future, even personal computer in a domestic domain will be based on a parallel architecture with more than ten logic processors. Nowadays, dual-core and multi-threading processors are widespread used, and soon, we will see processors in which a great deal of threads can be executed in parallel.

However, the majority of the programs and current applications (numeric or symbolic) are not designed to exploit all the possibilities of these multicore/multithread processors. To manually parallelize the existent or future software applications is a tough, non-productive and inefficient job. So, in practice, new parallel languages, libraries, tools and compilers will be necessary in order to generate applications able to take advantage of the potentiality of parallel architectures.

Antecedents

Our research group has been researching for more than a decade on techniques and technologies related to automatic parallelization and optimization of codes. We have visited and collaborated with pioneer research groups, like Polaris (led by Prof. David Padua) or Apart (led by Prof. Michael Gerndt). From this work, several contributions arised in the field of automatic parallelization/optimization of Fortran codes, easier to tackle due to the lack of pointers and dynamic data structures.

More recently, and based on the accumulated experience, we have extended the sphere of activity of our techniques to let them face codes written with more evolved languages: C, C++ or Java. All these languages have in common the possibility of using complex data structures based on pointers and dynamic memory allocation. However, there is still a lack of compiler techniques to deal with the automatic optimization of such codes. The main limitation of these compilers is that they are not able to automatically extract from the source code the necessary information to exploit parallelism, locality, etc. To solve this, we basically need a description of the memory locations read and written at each code statement. More precisely, the topology and properties of the data structures used in the code must be automatically captured via static analysis.

During the last years, we have developed a shape analyzer which precisely capture the properties and topology of the data structures used in pointer-based codes. This previous work was carried out by F. Corbera for his Ph.D. [1-6,8,9]. Later on, we have used this first implementation of the shape analyzer to develop a dependence test able to successfully detect parallel loops [3,15,16,23]. We have also explored the applicability of the shape analysis in oder to exploit locality and parallelism in pointer-based codes [7, 10-12,14,17]. Using Java, NetBeans, CVS, several GUI libraries, and extending the Cetus compiler infrastructure, we have reformulated the shape analysis using "Coexistent Links Sets" [18-19], reducing the amount of memory required during the analysis and increasing the precision in the description of the data structures captured in dynamic codes. We have validated this new shape analysis approach with several codes in which the used data structures are successfully identified. Besides, we are researching strategies aimed at reducing the complexity of such analysis [20,34]. For his Ph.D. [35], Adrian Tineo has added interprocedural support to deal with recursive codes [25,32,33] and a data dependence test that successfully detect loop-carried dependences in loops and recursive functions that traverse recursive data structures. We are currently working in reducing the complexity of such dependence test.

Current Work and Main Goals

Current steps are directed towards four main projects:

• Wave-front TBB template

Based on the experience we have acquired developing and analyzing TBB implementations of parallel codes based on the pipeline paradigm, we are working in developing work-stealing solutions for wave-front algorithms in which automatic load balancing can have a great impact.


• New parallel languages: Chapel

In collaboration with Brad Chamberlain, from Cray Inc., we want to contribute to the Chapelproject, mainly related with data redistribution, the sparse and irregular data structures distribution problem, parallel Input/Output, and with work stealing and task parallelism.


• Load balance for heterogeneous architectures

We are also dealing with the problem of automatically balance the workload in heterogeneous architectures (in principle, multicores + GPGPUs, but we'll like to consider FPGAs too).

Publications

1. UMA-DAC-99/08 -- Abstract
   F. Corbera, R. Asenjo and E.L. Zapata,
   New Shape Analysis Techniques for Automatic Parallelization of C Codes,
   ACM Int'l. Conf. on Supercomputing (ICS'99),
   Rhodes, Greece, June 20-25, 1999.

2. UMA-DAC-00/32 -- Abstract
   F. Corbera, R. Asenjo and E.L. Zapata,
   Un Paso en el Proceso de Paralelización Automática de Códigos C,
   XI Jornadas de Paralelismo,
   Granada, Spain, September 11-13, 2000.

3. UMA-DAC-00/33 -- Abstract
   F. Corbera, R. Asenjo and E.L. Zapata,
   Accurate Shape Analysis for Recursive Data Structures,
   13th Int'l. Workshop on Languages and Compilers for Parallel Computing (LCPC'2000),
   IBM T.J. Watson Res. Ctr., Yorktown Heights, New York, NY, August 10-12, 2000.
   (published by Springer-Verlag, Berlin, Germany, S.P. Midkiff, J.E. Moreira, M. Gupta, S. Chatterjee, J. Ferrante, J. Prins, W. Pugh and C.-W. Tseng, Eds., LNCS no. 2017).

4. UMA-DAC-01/09 -- Abstract
   F. Corbera, R. Asenjo and E.L. Zapata,
   Progressive Shape Analysis for Real C Codes,
   IEEE Int'l. Conf. on Parallel Processing (ICPP'2001),
   Valencia, Spain, September 3-7, 2001.

5. UMA-DAC-01/24
   Francisco J. Corbera Peña,
   Detección Automática de Estructuras de Datos Basadas en Punteros,
   PhD Thesis,
   Dept. Computer Architecture, University of Málaga, September 2001.

6. UMA-DAC-02/04
   F. Corbera, R. Asenjo and E.L. Zapata,
   New Shape Analysis and Interprocedural Techniques for Automatic Parallelization of Codes,
   Int'l J. of Parallel Programming,
   vol. 30, no. 1, February 2002, pp. 37-63.

7. UMA-DAC-02/10
   O. Plata, R. Asenjo, E. Gutiérrez, F. Corbera and E.L. Zapata,
   Locality Analysis of Irregular and Dynamic Codes,
   NATO Advanced Research Workshop on High Performance Computing: Technology and Applications,
   Cetraro, Italy, June 24-27, 2002.

8. UMA-DAC-02/13 -- Abstract
   F. Corbera, R. Asenjo and E. Zapata,
   Towards Compiler Optimization of Codes Based on Arrays of Pointers,
   15th Int'l Workshop on Languages and Compilers for Parallel Computing (LCPC'02),
   College Park, Maryland, July 25-27, 2002.

9. UMA-DAC-04/16
   F. Corbera, R. Asenjo and E.L. Zapata,
   A Framework to Capture Dynamic Data Structures in Pointer-Based Codes,
   IEEE Trans. on Parallel and Distributed Systems,
   vol. 15, no. 2, February 2004, pp. 151-166.

10. UMA-DAC-03/01
    O. Plata, R. Asenjo, E. Gutiérrez, F. Corbera, A. Navarro and E.L. Zapata,
    On the Parallelization of Irregular and Dynamic Programs,
    10ht Workshop on Compilers for Parallel Computers (CPC'2003),
    Amsterdam, The Netherlands, January 8-10, 2003.

11. UMA-DAC-04/03
    R. Asenjo, F. Corbera, E. Gutiérrez, A. Navarro, O. Plata and E.L. Zapata,
    Optimization Techniques for Irregular and Pointer-based Programs (Invited Talk),
    12-th Euromicro Conference on Parallel, Distributed and Network based Processing (PDP'2004),
    La Coruña, Spain, February, 11-13, 2004.

12. UMA-DAC-04/08
    A. Navarro, F. Corbera, R. Asenjo, E. Gutiérrez, R.G. Valderrama, O. Plata and E.L. Zapata,
    Exploiting Locality and Parallelism in Pointer-based Programs,
    11ht Workshop on Compilers for Parallel Computers (CPC'2004),
    Seeon Monastery, Chiemsee, Germany, July 7-9, 2004.

13. UMA-DAC-04/11
    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,
    17ht Int'l Workshop on Languages and Compilers for Parallel Computing (LCPC'2004),
    West Lafayette, Indiana, USA, September 22-25, 2004.(LNCS 2005, v. 3602 pp.394-408)

14. UMA-DAC-04/12
    O. Plata and R. Asenjo,
    Exploitation of Locality and Parallelism in Pointer-based Programs (Tutorial),
    Int'l. Conf. on Parallel Architectures and Compilation Techniques (PACT'04),
    Antibes Juan-les-Pins, France, September 29 - October 3, 2004.

15. UMA-DAC-04/20
    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
    pp 432 - 437. Almería 15-17 Sept. 2004

16. UMA-DAC-05/02
    A. Tineo, F. Corbera, A. Navarro, R. Asenjo and E.L. Zapata,
    A novel Approach for Detecting Heap-based Loop-carried Dependences,
    IEEE Int'l. Conf. on Parallel Processing (ICPP'2005),
    Univ. of Oslo, Norway, June 14-17, 2005.

17. UMA-DAC-05/05
    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.
18. UMA-DAC-05/09
    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.
19. UMA-DAC-06/01
    A. Tineo, F. Corbera, A. Navarro, R. Asenjo and E.L. Zapata,
    Shape Analysis for Dynamic Data Structures based on Coexistent Links Sets,
    12th Workshop on Compilers for Parallel Computing (CPC'2006),
    A Coruña, Spain, January 9-11, 2006.
20. UMA-DAC-06/08. DOI Link
    R. Castillo, A. Tineo, F. Corbera, A. Navarro, R. Asenjo and E.L. Zapata,
    Towards a Versatile Pointer Analysis Framework,
    In European Conference on Parallel Computing (EURO-PAR)
    29th August - 1st September 2006. Dresden. Germany.
21. UMA-DAC-06/09
    R. Castillo, F. Corbera, A. Navarro, R. Asenjo and E.L. Zapata,
    Pointer analysis techniques targeted to accelerate shape analysis,
    XVII Jornadas de Paralelismo
    18-20 September 2006. Albacete. Spain.
22. UMA-DAC-06/07
    R. Castillo, A. Tineo, F. Corbera, A. Navarro, R. Asenjo and E.L. Zapata,
    Experimental results in shape analysis,
    Technical Report,
    March 2006
23. UMA-DAC-07/01. DOI Link
    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,
    Volume 67, Issue 1 , January 2007, Pages 47-62
24. UMA-DAC-07/02
    A. Navarro, F. Corbera, R. Asenjo, A. Tineo and E.L. Zapata,
    Complexity Study of the Shape Analisys based on CLSs,
    Technical Report,
    February 2007
25. UMA-DAC-07/03
    A. Tineo, F. Corbera, A. Navarro, R. Asenjo and E.L. Zapata,
    A new Abstraction of the Activation Record Stack for Interprocedural Shape Analysis,
    Technical Report,
    February 2007
26. UMA-DAC-07/04
    A. Tineo, D.R. Llanos and M. Cintra,
    Speculative Parallelization of Pointer-Based Applications,
    Transnational Access Meeting, HPC EUROPA EVENT,
    Bologna, June 2007
27. UMA-DAC-07/05
    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, June 2007
28. UMA-DAC-07/06
    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),
    July 15 - 20, 2007, L'Aquila, Italy
29. UMA-DAC-07/07
    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),
    July 15 - 20, 2007, L'Aquila, Italy
30. UMA-DAC-07/08
    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, JP'2007,
    Sep 11 - 14, 2007, Zaragoza, Spain
31. UMA-DAC-07/09
    F. Corbera, A. Navarro, R. Asenjo, A. Tineo and E.L. Zapata,
    A formal presentation of shape analysis graphs and operations,
    Technical Report. Dept. Comp. Architecture. Univ. of Malaga,
    July 2007
32. UMA-DAC-07/10
    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'07)
    Urbana, Illinois, October 11-13, 2007
33. UMA-DAC-08/1
    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 & Distributed Processing Symposium (IPDPS'08)
    Miami, Florida USA. April 14-18, 2008
34. UMA-DAC-08/2, doi
    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.
35. UMA-DAC-09/01
    Adrian Tineo
    Compilation Techniques Based on Shape Analysis for Pointer-Based Programs,
    Ph.D Report. Dept. Comp. Architecture. Univ. of Malaga,
    January 2009
36. UMA-DAC-09/2
    A. Navarro, R. Asenjo, S. Tabik and C. Cascaval,
    Load balancing using work-stealing for pipeline parallelism in emerging applications,
    ACM 23rd International Conference on Supercomputing
    IBM T.J. Watson Research Center, Yorktown Heights, NY, USA. June 8-12, 2009
37. UMA-DAC-09/3
    A. Navarro, R. Asenjo, S. Tabik and C. Cascaval,
    Load balancing using work-stealing for pipeline parallelism in emerging applications,
    IBM Research Technical Paper RC24732.
    IBM T.J. Watson Research Center, Yorktown Heights, NY, USA. 2009
38. UMA-DAC-09/4
    A. Navarro, R. Asenjo, S. Tabik and C. Cascaval,
    Analytical Modeling of Pipeline Parallelism,
    ACM-IEEE International Conference on Parallel Architectures and Compilation Techniques (PACT)
    Raleigh, North Carolina. September 12-16, 2009
    
39. UMA-DAC-09/5
    R. Castillo, F. Corbera, A. Navarro, R. Asenjo, E.L. Zapata
    Conflict Analysis for heap-based Data Dependence Detection,
    Parallel Computing: From Multicores and GPU's to Petascale,
    ISBN: 978-1-60750-529-7, Vol. 19, pp. 351-358, IOS Press BV, Amsterdam, 2010.
    

40. UMA-DAC-09/6
    A. Tineo, F. Corbera, A. Navarro, R. Asenjo, E.L. Zapata
    On the automatic detection of heap-induced data dependences with interprocedural shape analysis,
    International Workshop on Advanced Distributed and Parallel Network Applications (ADPNA-2009). In conjunction with ICPP 2009.
    Vienna, Austria, September 22-25, 2009
    
41. UMA-DAC-10/1. Also available: doi
    A.J. Dios, R. Asenjo, A. Navarro, F. Corbera, E.L. Zapata
    Evaluation of the Task Programmin Model in the Parallelization of Wavefront Problems,
    The 12th IEEE Intl. Conf. on High Performance Computing and Communications (HPCC-2010).
    Melbourne, Australia, September 1-3, 2010
    
42. UMA-DAC-10/2
    A. Sanz, J. López, A. Navarro, R. Asenjo
    Tridiagonal Systems in Chapel. Case study: The parallel cyclic reduction algorithm,
    III Congreso Español de Informática, Jornadas de Paralelismo 2010 (JP2010).
    Valencia, España, Septiembre 7-10, 2010
    
43. UMA-DAC-10/3
    Rafael Larrosa, A. Navarro, R. Asenjo, E.L. Zapata
    Implementing a Chapel library for parallel I/O,
    III Congreso Español de Informática, Jornadas de Paralelismo 2010 (JP2010).
    Valencia, España, Septiembre 7-10, 2010
    
44. UMA-DAC-10/4
    A.J. Dios, R. Asenjo, A. Navarro, F. Corbera, E.L. Zapata
    Evaluation of the Task Programming Model in the Parallelization of Wavefront Problems,
    III Congreso Español de Informática, Jornadas de Paralelismo 2010 (JP2010).
    Valencia, España, Septiembre 7-10, 2010
    
45. UMA-DAC-11/01
    A. Dios, R. Asenjo, A. Navarro, F. Corbera, E.L. Zapata
    Wavefront template implementation based on the task programming model,
    Technical Report. Dept. Comp. Architecture. Univ. of Malaga,
    March 2011
46. UMA-DAC-11/02
    A. Dios, R. Asenjo, A. Navarro, F. Corbera, E.L. Zapata
    A case study of the task-based parallel wavefront pattern,
    Technical Report. Dept. Comp. Architecture. Univ. of Malaga,
    July 2011
47. UMA-DAC-11/03
    A. Dios, R. Asenjo, A. Navarro, F. Corbera, E.L. Zapata
    A case study of the task-based parallel wavefront pattern,
    Advances in Parallel Computing: Applications, Tools and Techniques on the Road to Exascale Computing,
    ISBN: 978-1-61499-040-6, Vol. 22, pp. 65-72, IOS Press BV, Amsterdam,2012

48. UMA-DAC-11/04
    R. Larrosa, R. Asenjo, A. Navarro, B.L. Chamberlain
    A First Implementation of Parallel IO in Chapel for Block Data Distribution,
    Advances in Parallel Computing: Applications, Tools and Techniques on the Road to Exascale Computing,
    ISBN: 978-1-61499-040-6, Vol. 22, pp. 447-454, IOS Press BV, Amsterdam, 2012

49. UMA-DAC-11/05
    A. Dios, R. Asenjo, A. Navarro, F. Corbera, E.L. Zapata
    Wavefront template for the task-based programming model,
    The 24th International Workshop on Languages and Compilers for Parallel Computing (LCPC 2011),
    Colorado State University, Fort Collins, Colorado, September 8-10, 2011
50. UMA-DAC-11/06, doi
    A. Dios, R. Asenjo, A. Navarro, F. Corbera, E.L. Zapata
    High-level template for the task-based parallel wavefront pattern,
    The 18th annual IEEE International Conference on High Performance Computing (HiPC 2011),
    Bengaluru (Bangalore), India, December 18-21, 2011
51. UMA-DAC-11/07
    Bradford L. Chamberlain, Sung-Eun Choi, Steven J. Deitz and Angeles Navarro
    Composable Parallel Iterators in Chapel,
    5th Partitioned Global Address Space Conference (PGAS'11),
    Galveston Island, Texas, USA,October 15 - 18, 2011
52. UMA-DAC-12/01. doi
    A. Navarro, F. Corbera, R. Asenjo, R. Castillo and E.L. Zapata,
    A Data Dependence Test based on the Projection of Paths over Shape Graphs,
    Journal of Parallel and Distributed Computing,
    Volume 72, Issue 12, December 2012, Pages 1547-1564.
    DOI: 10.1016/j.jpdc.2012.08.004
    
53. UMA-DAC-12/02. Long version: UMA-DAC-12/02 [Slides]
    Alberto Sanz, Rafael Asenjo, Juan López, Rafael Larrosa, Angeles Navarro, Vassily Litvinov, Sung-Eun Choi, Bradford L. Chamberlain,
    Global data re-allocation via communication aggregation in Chapel,
    2012 IEEE 24th International Symposium on Computer Architecture and High Performance Computing,
    New York City, NY, USA. October 24-26, 2012. DOI 10.1109/SBAC-PAD.2012.18
    
54. UMA-DAC-12/03. Invited Talk.
    Rafael Asenjo
    Main benefits of Task Parallel Framworks,
    HPC Advisory Council Spain Conference 2012,
    Málaga, Spain. September 13, 2012.
    

Collaborations 

• Project Chapel led by Dr. Brad Chamberlain, from Cray, Inc.
• María Jesús Garzarán y David Padua, Computer Science Department, University of Illinois

Previous collaborations 

• Project Parallel Programming and PGAS languages of the Parallel Programming Models and Tools for Scalable Systems at IBM T.J. Watson Research Center led by Dr. Calin Cascaval
• Project Cetus of the ParaMount Group led by Prof. Rudolf Eigenmann
• Project Vespa led by Dr. Marcelo Cintra
• Project Galois led by Prof. Keshav Pingali
• Adrián Tineo Cabello (Swiss National Supercomputing Centre, CSCS)

---

Rafael Asenjo Plaza

Last modified: Wed Nov 7 18:24:22 CET 2012