Library-based solutions for algorithms 
				with complex patterns of parallelism
				---------------------------------------------------
				With the arrival of multi-core processors and the reduction in the 
				growth rate of the processing power per core in each new generation, 
				parallelization is becoming increasingly critical to improve the 
				performance of every kind of application. Also, while simple 
				patterns of parallelism are well understood and supported, this 
				is not the case for complex and irregular patterns, whose 
				parallelization requires either low level tools that hurt 
				programmers' productivity or transactional based approaches that 
				need specific hardware or imply potentially large overheads. This 
				is becoming an increasingly important problem as the number of 
				applications that exhibit these latter patterns is steadily growing. 
				This thesis tries to better understand and support three kinds of 
				complex patterns through the identification of abstractions and 
				clear semantics that help bring structure to them and the 
				development of libraries based on our observations that facilitate 
				their parallelization in shared memory environments. The library 
				approach was chosen given its advantages for code reuse, reduced 
				compiler requirements, and relatively short learning curve. The 
				implementation language selected being C++ due to its good 
				performance and capability to express abstractions. The examples 
				and evaluations in this thesis show that our proposals allow to 
				elegantly express the applications that present these patterns, 
				improving their programmability while providing similar or even 
				better performance than existing approaches.
			

				Enhancing and Evaluating the Configuration 
				Capability of a Skeleton for Irregular Computations
				---------------------------------------------------
				Although skeletons largely facilitate the parallelization of 
				algorithms, they often provide little support for the work 
				decomposition. Also, while they have been widely applied to regular 
				computations, this has not been case for irregular algorithms that 
				can exploit amorphous data-parallelism, whose parallelization in 
				fact requires much more effort from programmers and thus benefits 
				more from a structured approach. In this paper we improve and 
				evaluate the configurability of a recently proposed skeleton that 
				allows to parallelize this latter kind of algorithms. Namely, the 
				skeleton allows to easily change critical details such as the data 
				structures, the work partitioning algorithm or the task granularity 
				to use. The simple procedures to choose among these possibilities 
				and their influence on performance are described and evaluated. We 
				conclude that the skeleton allows to conveniently explore different 
				possibilities for the parallelization of irregular applications, 
				which can result in substantial performance improvements.
			

				An Algorithm Template for Domain-Based Parallel Irregular Algorithms
				--------------------------------------------------------------------
				The parallelization of irregular algorithms has not been as widely 
				studied as the one of regular codes. In particular, while there are 
				many proposals of parallel skeletons and libraries very well suited 
				to regular algorithms, this is not the case for irregular ones. This 
				is probably due to the complexity of finding common patterns, 
				behaviors and semantics in these algorithms. This is unfortunate, as 
				the parallelization of irregular algorithms would benefit even more 
				than that of regular codes from the higher degree of abstraction 
				provided by skeletons. This work proposes to exploit the concept of 
				domain defined on some property of the elements to process in order 
				to enable the simple and effective parallelization of irregular 
				applications. Namely, we propose to use such domains both to decompose
				the computations in parallel tasks and to detect and avoid conflicts 
				between these tasks. A generic C++ library providing a skeleton for 
				multicore systems built on this idea is described and evaluated. Our 
				experimental results show that this library is a very practical tool 
				for the parallelization of irregular algorithms with little 
				programming effort.			
			

				An Algorithm Template for Domain-Based Parallel Irregular Algorithms
				--------------------------------------------------------------------
				The parallelization of irregular algorithms has not been as widely 
				studied as the one of regular codes. In particular, while there are 
				many proposals of parallel skeletons and libraries very well suited 
				to regular algorithms, this is not the case for irregular ones. This 
				is probably due to the complexity of finding common patterns, 
				behaviors and semantics in these algorithms. This is unfortunate, as 
				the parallelization of irregular algorithms would benefit even more 
				than that of regular codes from the higher degree of abstraction 
				provided by skeletons. This work proposes to exploit the concept of 
				domain defined on some property of the elements to process in order 
				to enable the simple and effective parallelization of irregular 
				applications. Namely, we propose to use suchs domain both to 
				decompose the computations in parallel tasks and to de- tect and 
				avoid conflicts between these tasks. A generic C++ library providing 
				a skeleton for multicore systems built on this idea is described and 
				evaluated. Our experimental results show that this library is a very 
				practical tool for the parallelization of irregular algorithms with 
				little programming effort.			
			

				A framework for argument-based task 
				synchronization with automatic detection of dependencies
				--------------------------------------------------------
				Synchronization in parallel applications can be achieved either 
				implicitly or explicitly. Implicit synchronization is typical of 
				programming environments that provide predefined, and often simple, 
				patterns of parallelism such as data-parallel libraries and languages 
				and skeletal operations. Nevertheless, more flexible approaches that 
				allow to express arbitrary task-level parallel computations without a 
				predefined structure request in turn that the user explicitly 
				specifies the synchronization needed among the parallel tasks.
				  In this paper we present a library-based approach that enables 
				arbitrary patterns of par- allelism with minimal effort for the user. 
				Our proposal is the first generic approach to express parallelism we 
				know of that requires neither explicit synchronizations nor a detail 
				of the dependencies of the parallel tasks. Our strategy relies on 
				expressing the parallel tasks as functions that convey their 
				dependencies implicitly by means of their arguments. These function 
				arguments are analyzed by our library, called DepSpawn, when a 
				parallel task is spawned in order to enforce its dependencies. Our 
				experiments indicate that Dep- Spawn is very competitive, both in 
				terms of performance and programmability, with respect to a widespread
				high-level approach like OpenMP.	
			

				A framework for argument-based task synchronization
				---------------------------------------------------
				Synchronization in parallel applications can be achieved implicitly or
				explicitly. For example, the semantics of data-parallel libraries and
				languages implicitly synchronize the parallel threads of textcution 
				after each parallel computation. Skeletal operations also define 
				implicitly the synchronization of the tasks defined by the used. On 
				the other hand, more flexible approaches that allow to express 
				arbitrary task-level computations without a defined structure always
				request in turn that the user specifies explicitly the synchronization
				needed among the parallel tasks.
				  In this paper we present an approach that enables arbitrary patterns 
				of parallelism without requiring explicit synchronizations. Our 
				strategy relies on expressing the parallel tasks as functions that 
				convey their dependences implicitly by means of their arguments. These
				arguments can be then analyzed when a parallel task is spawned in 
				order to enforce its dependences. A library-based prototype that 
				implements this approach is then evaluated.		
			

				An Algorithm Template for Parallel Irregular Algorithms
				-------------------------------------------------------
				There is plenty of work done on the area of parallelism regarding 
				regular algorithms and structures, which has led to the development 
				of tools to exploit it. On the other hand, there are other types of 
				algorithms, based on amorphous parallelism, that have not been covered 
				extensively. This work presents a C++ library that abstracts some 
				patterns found in irregular algorithms, easing the development of 
				parallel versions for multicore systems.
			

				A generic algorithm template for divide-and-conquer in multicore systems
				------------------------------------------------------------------------
				The divide-and-conquer pattern of parallelism has been well known for 
				years. Its recursive nature makes it a powerful approach to organize 
				parallelism on data structures and problems that are expressed 
				naturally in a recursive way. In fact, recent tools such as Intel 
				Threading Building Blocks (TBB), which has received much attention, 
				go further and make extensive usage of this pattern to parallelize 
				problems that other approaches parallelize following other strategies. 
				In this paper we discuss the limitations to express divide-and-conquer 
				parallelism with the algorithm templates provided by the TBB. Based on 
				our observations, we propose a new algorithm template implemented on 
				top of TBB that improves the programmability of many problems that fit 
				this pattern, while providing a similar performance. This is 
				demonstrated with a comparison both in terms of performance and 
				programmability.
			

				Una plantilla genérica para el patrón de paralelismo 
				de divide-y-vencerás en sistemas multinúcleo
				----------------------------------------------------
				El patrón divide-y-vencerás organiza de forma natural el paralelismo 
				en estructuras de datos y problemas que se expresan de forma recursiva. 
				Existen herramientas como las librerías Threading Building Blocks (TBB) 
				de Intel, que permiten paralelizar cierto tipo de problemas creando 
				una capa de abstracción sobre una implementación de este patrón. En 
				este artículo proponemos una plantilla que mejora la programabilidad 
				de estos problemas en sis- temas multinúcleo y la comparamos en 
				términos de programabilidad y rendimiento con la TBB.
			

				Numerical simulation of pollutant transport in a 
				shallow water system on the Cell heterogeneous processor
				--------------------------------------------------------
				This paper presents an implementation, optimized for the Cell 
				processor, of a parallel solver for 2D hyperbolic systems of 
				conservation laws with source terms. More precisely it focuses in a 
				pollutant transport problem. The solver consid- ers a well-balanced 
				first order finite volume numerical scheme for 2D shallow water systems 
				with pollutant transport. The potential data parallelism of this 
				algorithm is identified and the application of the scheme to one layer 
				shallow water systems with pollutant transport is implemented and 
				tested in a Cell processor-based architecture.
				  A description of the special architecture and programming required 
				by the Synergistic Processor Units (SPUs) of this processor motivates 
				the methodol- ogy to perform the optimized implementation, which 
				involves parallelization, data structure reorganization, explicit 
				transfers of data between the SPUs and the memory, and 
				Single Instruction Multiple Data (SIMD) vectorization. The performance 
				of our implementation is compared with an implementation of the solver 
				for a standard CPU. The results obtained show that the Cell processor 
				implementation can achieve speedups above 46x.
			

				Programación de alto rendimiento en el procesador Cell: 
				Aplicación a simulación de fluídos
				-------------------------------------------------------
				En el diseño de los procesadores modernos es cada vez más común 
				incorporar varios núcleos de procesamiento. En algunas arquitecturas 
				estos núcleos no son homogéneos, sino que están especializados en la 
				realización de funciones específicas. Uno de los procesadores de este 
				tipo más destacables es el Cell, creado por Sony, Toshiba e IBM, que 
				incorpora en un solo chip un núcleo PowerPC común y hasta 8 núcleos 
				aceleradores, llamados Synergistic Processing Elements, que alcanzan 
				una gran rendimiento en operaciones en punto flotante mediante 
				procesamiento vectorial. En este trabajo estudiaremos este procesador 
				y su rendimiento con aplicaciones científicas. Optimizaremos para el 
				procesador Cell una simulación de un sistema de aguas someras con 
				transporte de contaminantes utilizando un método de volúmenes finitos. 
				Ésta es una aplicación áltamente paralelizable, al tiempo que utiliza 
				operaciones sobre matrices y vectores de dimensión 4, con lo que se 
				adapta a la arquitectura de este procesador.