片上集成的晶体管数目持续增长，而传统单核处理器的性能发展却难以持续，因为依靠指令级并行获得的收益越来越少，而功耗问题和散热问题也日益凸显出来。多核/众核处理器在单个芯片上集成了多个更为简单的处理器核，利用线程级并行获得了性能大幅提升，而且相对简单的小核结构有效地降低了功耗和散热，目前已经被学术界和产业界广泛接受，成为体系结构领域研究人员的关注热点。这产生了如下两个问题:第一，如何挖掘多核/众核平台的强大计算能力。因为程序的性能是许多因素综合作用的结果，所以优化程序性能是一项复杂的任务，而众核结构及其编程环境的复杂性使这一任务更为艰巨，因此有必要研究如何在众核平台上对一些重要且具有挑战性的应用核心进行优化，例如稠密矩阵向量乘和稀疏矩阵向量乘，一方面提高这些应用核心的性能，另一方面探讨基于众核平台进行算法优化的规律，例如基于众核平台的片上数据重用特点和自动调优特点。第二，何种众核体系结构特征更有利于提高算法性能。许多并行算法中的一些共同的基本操作（例如同步操作）往往要在并行程序中多次执行，而且对整个并行程序的性能影响非常大，这要求众核体系结构对这些基本操作加以有效支持。本文对上述两个问题进行了研究，得到了如下的研究成果:　　1)提出两种基于众核GPU优化稠密矩阵向量乘的算法。通过测试发现现有算法对于小矩阵或者胖矩阵（行数小于列数的矩阵）的性能不佳，原因是现有算法的线程并行度较低导致GPU占用率较低，针对这个问题提出了两种新算法来优化稠密矩阵向量乘。第一种算法是使用一个warp（即一组线程，而不是原来算法中的一个线程）来计算目标向量y的一个元素，从而提高了线程的并行度;第二种算法是基于第一种算法提出的一种适应众核结构的寄存器分块算法，从而进一步提高性能。实验结果表明，两种新算法与原有算法相比，对于小的方阵或者胖矩阵可以获得10倍以上的性能提升，并且对于大的方阵，寄存器分块算法仍然能够获得较好的性能。由于各个算法都不能对所有输入矩阵获得最好性能，我们提出了一个针对稠密矩阵向量乘的自动调优框架，从而对任意一个输入矩阵都能够自动选择一个最优的算法。　　2)提出一种新的稀疏矩阵存储格式HYB-R，用于在众核GPU平台上优化稀疏矩阵向量乘。通过对实验数据进行分析，我们发现NVIDIA提出的针对SpMV的最好算法（基于HYB格式的算法）并不能对于所有矩阵都能表现出最好的性能，这是因为有的矩阵在经过一次划分后仍然有大量的非零元素存在于速度较慢的COO部分。因此，我们提出了一种新的稀疏矩阵存储格式HYB-R，以充分挖掘众核GPU的结构特征。在HYB-R格式中，稀疏矩阵的COO部分被多次划分为ELL和COO两种格式，从而保证尽量多的非零元素存储为速度较快的ELL格式。如何划分矩阵对于HYB格式和HYB-R格式来说是一个重要问题，所以我们也对划分矩阵的参数进行了调优，以获取更高性能。实验结果表明，基于HYB-R格式的算法比基于HYB格式的算法在两个GPU平台上都获得了更高的性能，最好的情况下性能提高达到17％。　　3)提出一种基于众核GPU的高速缓存分块方法，用于优化稀疏矩阵向量乘。在众核GPU上运用高速缓存分块方法要受到众核平台特征的影响，需要研究在众核GPU上的高速缓存分块方法是否依然有效以及何种分块方式才能适应众核GPU的结构，因此提出了一种基于众核GPU的高速缓存分块方法来优化稀疏矩阵向量乘，稀疏矩阵被划分为许多子块，每一个子块都被存储为CSR格式。通过高速缓存分块的方法，源向量x的相应部分可以在GPU的片上高速缓存中得到重用，因此对于源向量x的访问时间可以大幅减少。实验结果表明，最好情况下，在GeForce GTX480上使用高速缓存分块方法的稀疏矩阵向量乘性能比不分块的CSR格式的性能快5倍。　　4)提出了两种片上众核硬件同步机制，研究了众核硬件同步机制对算法的支持。基于在众核结构上进行算法优化的经验，讨论了并行算法对众核体系结构提出的要求，探讨了何种众核结构特征更有利于提高算法性能;以同步机制为例研究体系结构的改进对算法性能的影响，提出了基于众核结构的集中式同步机制和分布式同步机制，并进行了实验评估，实验结果表明，与软件的同步机制相比，提出的两种硬件同步机制有效的提高了同步速度，而分布式同步机制比集中式同步机制的扩展性更好。