[talks] J Huang general exam

[Melissa Lawson]

Jialu Huang will present her research seminar/general exam on Tuesday May 12 at 2PM in 
room 402.   The members of her committee are:  David August, advisor, Brian Kernighan, 
and Andrew Appel.  Everyone is invited to attend her talk, and those faculty wishing to
remain 
for the oral exam following are welcome to do so.  Her abstract and reading list follow
below.

============================================
General abstract:

While multi-core systems have become prevalent, using them efficiently
remains an unsolved problem. DOALL is a highly efficient parallelization
technique, however, cross-iteration dependences limit DOALL's
applicability. Decoupled software pipelining (DSWP) partitions the code
into stages with dependences flowing unidirectionally from earlier
stages to later stages. DSWP is more generally applicable than DOALL,
but its scalability is limited by the number of stages and by the
workload in each stage. Parallel stage decoupled software pipelining
(PS-DSWP) addresses this problem by enabling DOALL parallelization to
some stages of a DSWP pipeline in loops where DOALL wasn't originally
applicable.  Inspired by the idea that DSWP can make DOALL more
applicable, this work proposes other parallelization techniques can
become more broadly applicable through the use of DSWP. LOCALWRITE,
which requires each thread to only update the data belonging only to
itself, if applied alone, suffers from redundant computations.
Introducing LOCALWRITE into a DSWP framework, removes this limitation,
by having a separate DOALL stage produce the iteration state to the
LOCALWRITE stages. Experiments show combining all three parallelizations
(DOALL, LOCALWRITE, DSWP) yields performance superior to applying any of
these techniques alone.

Reading List:

Books:
[1] Modern Compiler Implementation in ML, by A. W. Appel, Cambridge
University Press, 1998. Chapter 1~13, 17~21.
[2] Compilers: Principles, Techniques, and Tools by Alfred V. Aho, Ravi
Sethi, and Jeffrey D. Ullman, Addison Wesley, 2001. Chapter 9, 10.

Papers:
[1] Raman, E., Ottoni, G., Raman, A., Bridges, M. J., and August, D. I.
2008. Parallel-stage decoupled software pipelining. In Proceedings of
the Sixth Annual IEEE/ACM international Symposium on Code Generation and
Optimization (Boston, MA, USA, April 05 - 09, 2008). CGO '08. ACM, New
York, NY, 114-123. DOI= http://doi.acm.org/10.1145/1356058.1356074
[2]  Guilherme Ottoni, Ram Rangan, Adam Stoler, and David I. August.
Automatic Thread Extraction with Decoupled Software Pipelining. In
Proceedings of the 38th IEEE/ACM International Symposium on
Microarchitecture (MICRO), November 2005.
[3] Matthew J. Bridges, Neil Vachharajani, Yun Zhang, Thomas Jablin,
David I. August, "Revisiting the Sequential Programming Model for the
Multicore Era," IEEE Micro, vol. 28, no. 1, pp. 12-20, Jan./Feb. 2008,
doi:10.1109/MM.2008.13.
[4] Vachharajani, N., Rangan, R., Raman, E., Bridges, M. J., Ottoni, G.,
and August, D. I. 2007. Speculative Decoupled Software Pipelining. In
Proceedings of the 16th international Conference on Parallel
Architecture and Compilation Techniques (September 15 - 19, 2007). PACT.
IEEE Computer Society, Washington, DC, 49-59. DOI=
http://dx.doi.org/10.1109/PACT.2007.66.
[5] Singh, D. E., Martin, M. J., and Rivera, F. F. 2005. Runtime
characterisation of irregular accesses applied to parallelisation of
irregular reductions. Int. J. Comput. Sci. Eng. 1, 1 (Feb. 2005), 1-14.
DOI= http://dx.doi.org/10.1504/IJCSE.2005.008906.
[6] Gutiérrez, E., Plata, O. G., and Zapata, E. L. 1999. On Automatic
Parallelization of Irregular Reductions on Scalable Shared Memory
Systems. In Proceedings of the 5th international Euro-Par Conference on
Parallel Processing (August 31 - September 03, 1999). P. Amestoy, P.
Berger, M. J. Daydé, I. S. Duff, V. Frayssé, L. Giraud, and D. Ruiz,
Eds. Lecture Notes In Computer Science, vol. 1685. Springer-Verlag,
London, 422-429.
[7] Eladio Gutiérrez, Oscar Plata, Emilio L. Zapata, "Improving Parallel
Irregular Reductions Using Partial Array Expansion," sc,pp.56, ACM/IEEE
SC 2001 Conference (SC 2001), 2001.
[8] Saltz, J. H., Mirchandaney, R., and Crowley, K. 1989. The doconsider
loop. In Proceedings of the 3rd international Conference on
Supercomputing (Crete, Greece, June 05 - 09, 1989). ICS '89. ACM, New
York, NY, 29-40. DOI= http://doi.acm.org/10.1145/318789.318794.
[9] Y. Lin and D. Padua. On the Automatic Parallelization of Sparse and
Irregular Fortran Programs. Scientific Programming, 7(1999), pp.
231-246. ISSN 1058-9244, IOS Press.
[10] Y. Lin and D. Padua. Analysis of Irregular Single-indexed Arrays
and Its Applications in Compiler Optimizations. In Proceedings of the
9th International Conference on Compiler Construction. Berlin, Germany,
March 2000.