| This dissertation maps various kernels and applications to a spectrum of programming models and architectures and also presents architecture-aware algorithms for different systems. Built on top of our experiences, we aim to provide feedback to system software researchers and computer architects.;The kernels and applications discussed in this dissertation have widely varying computational characteristics. For example, we consider both dense numerical computations---which are floating point intensive and have predictable data access patterns---and sparse graph algorithms---which are highly irregular and require intensive data synchronization. This dissertation also covers emerging applications from image processing, complex network analysis, and computational biology. JPEG2000 is the successor of JPEG and uses a mix of kernels with different computational requirements. To analyze large scale complex networks, we often need to process very large data to extract a network of interest. The structure of the extracted network often challenges modern hierarchical memory subsystems as well. We parallelize the COGNAC software package which reconstructs a phylogenetic tree using gene order data. The application has parallelism in multiple levels, and the degree of parallelism in each level varies widely.;We map these problems to diverse multicore processors (the Intel Harpertown and Nehalem architectures, the AMD Barcelona architecture, and the Sun UltraSparc architecture) and manycore accelerators (such as the IBM Cell Broadband Engine and NVIDIA GPUs). We also use new programming models---such as Transactional Memory, MapReduce, and Intel TBB---to address the performance and productivity challenges in the problems.;Our experiences highlight the importance of mapping applications to appropriate programming models and architectures. We also find several limitations of current system software and architectures and directions to improve those. The discussion focuses on system software and architectural support for nested irregular parallelism, Transactional Memory, and hybrid data transfer mechanisms. We believe that the complexity of parallel programming can be significantly reduced via collaborative efforts among researchers and practitioners from different domains. This dissertation participates in the efforts by providing benchmarks and suggestions to improve system software and architectures. |
