1、面向異構(gòu)體系結(jié)構(gòu)的稀疏矩陣算法已經(jīng)成為高性能計(jì)算領(lǐng)域的關(guān)鍵問(wèn)題之一。稀疏矩陣算法是自然科學(xué)和社會(huì)科學(xué)中許多領(lǐng)域進(jìn)行數(shù)值模擬計(jì)算時(shí)的關(guān)鍵技術(shù)和性能瓶頸，為了提高稀疏矩陣算法的計(jì)算性能，需要提高相應(yīng)算法在特定平臺(tái)上的計(jì)算效率。然而，一方面，稀疏矩陣算法的計(jì)算與訪存行為與矩陣的稀疏結(jié)構(gòu)相關(guān)，是典型的不規(guī)則類(lèi)算法，很難發(fā)掘時(shí)間與空間的局部性；另一方面，隨著包含算法加速器的異構(gòu)并行體系結(jié)構(gòu)成為高性能計(jì)算機(jī)體系結(jié)構(gòu)的主流，并行程序執(zhí)行效率的影響因素

2、日益復(fù)雜多樣，傳統(tǒng)的面向具體平臺(tái)的程序并行與優(yōu)化方法已經(jīng)無(wú)法滿(mǎn)足高效率并行程序的開(kāi)發(fā)需求。本研究主要內(nèi)容包括：
　　⑴提出了面向CPU-GPU異構(gòu)平臺(tái)的搜索方向優(yōu)化的寬度優(yōu)先搜索算法。實(shí)現(xiàn)了基于GPU的自底向上的寬度優(yōu)先搜索算法，提高了GPU線程訪存的連續(xù)性并降低了線程間負(fù)載的不均衡，并進(jìn)一步實(shí)現(xiàn)了CPU-GPU協(xié)同的自底向上的寬度優(yōu)先搜索算法，充分利用了CPU-GPU異構(gòu)并行計(jì)算平臺(tái)上所有的計(jì)算資源，并有效提高了寬度優(yōu)先搜索算法

3、對(duì)大規(guī)模節(jié)點(diǎn)前沿的處理速度。在此基礎(chǔ)上，設(shè)計(jì)了面向CPU-GPU異構(gòu)體系結(jié)構(gòu)的優(yōu)化搜索方向的寬度優(yōu)先搜索算法，通過(guò)結(jié)合基于多核CPU的自頂向下的串行寬度優(yōu)先搜索算法、自頂向下的并行寬度優(yōu)先搜索算法以及CPU-GPU協(xié)同的自底向上的寬度優(yōu)先搜索算法，提高了寬度優(yōu)先搜索算法對(duì)不同規(guī)模節(jié)點(diǎn)前沿的適應(yīng)性。
　?、铺岢隽嗣嫦駽PU-GPU異構(gòu)平臺(tái)的稀疏矩陣向量乘算法。提出了基于索引信息壓縮的稀疏矩陣分塊存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)，通過(guò)合并位置相近的同行非

4、零元，減少了矩陣非零元素對(duì)應(yīng)的索引信息的數(shù)據(jù)量，從而一方面提高了稀疏矩陣訪存的規(guī)則性和局部性，另一方面控制了填零元所引入的額外的計(jì)算和訪存開(kāi)銷(xiāo)，并通過(guò)采用二級(jí)混合存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)提高了對(duì)于矩陣不同稀疏結(jié)構(gòu)的適應(yīng)性。在此基礎(chǔ)上，實(shí)現(xiàn)了基于計(jì)算訪存量的負(fù)載均衡算法，分別設(shè)計(jì)了針對(duì)多核CPU和GPU的優(yōu)化的SpMV算法，有效的提高了稀疏矩陣向量乘算法的計(jì)算效率，并進(jìn)一步實(shí)現(xiàn)了CPU-GPU協(xié)同的稀疏矩陣向量乘算法，充分發(fā)掘了異構(gòu)體系結(jié)構(gòu)計(jì)算平臺(tái)的

5、計(jì)算能力。
　?、翘岢隽嗣嫦虍悩?gòu)平臺(tái)的基于超節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)的稀疏矩陣分解算法。以稀疏矩陣Cholesky分解算法為研究對(duì)象，在數(shù)據(jù)組織方面，改進(jìn)了稀疏矩陣超節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)，通過(guò)超節(jié)點(diǎn)合并和分塊控制計(jì)算粒度；在計(jì)算調(diào)度方面，將分解過(guò)程映射為一系列的數(shù)據(jù)塊任務(wù)，并設(shè)計(jì)了相應(yīng)的任務(wù)生成與調(diào)度算法，在滿(mǎn)足數(shù)據(jù)依賴(lài)性的前提下提高任務(wù)的并行性，從而顯著提高了稀疏矩陣Cholesky分解算法在GPU上的實(shí)現(xiàn)效率。通過(guò)將控制任務(wù)和計(jì)算任務(wù)分別映射到C

6、PU和GPU上，有效提高了CPU-GPU異構(gòu)平臺(tái)上稀疏矩陣分解算法的計(jì)算性能。
　?、忍岢隽嗣嫦駽PU-GPU異構(gòu)平臺(tái)的稀疏三角方程組求解算法。提出了面向稀疏結(jié)構(gòu)的分塊處理策略，根據(jù)稀疏三角矩陣非零元密度的不同將計(jì)算過(guò)程分解，并設(shè)計(jì)了基于分塊數(shù)據(jù)結(jié)構(gòu)的稀疏三角方程組求解算法。在此基礎(chǔ)上，設(shè)計(jì)了面向負(fù)載均衡的線程映射算法，并針對(duì)GPU設(shè)計(jì)了基于線程warp的計(jì)算組織策略，降低了GPU線程的控制分支所造成的性能損失，并進(jìn)一步實(shí)現(xiàn)了CP