基于GPU的四色Ramsey數(shù)算法的研究.pdf

1、近幾年來(lái)，隨著GPU技術(shù)的飛速發(fā)展，利用GPU進(jìn)行通用計(jì)算已逐漸成為國(guó)內(nèi)外研究熱點(diǎn)。由于早期的GPU程序利用圖形API編程接口進(jìn)行開發(fā)，所以開發(fā)成本高、周期長(zhǎng)、難度大，且不易于代碼的調(diào)試和維護(hù)。NVIDIA公司推出的CUDA(Compute Unified Device Architecture)是一種利用GPU進(jìn)行通用計(jì)算的編程技術(shù)，該技術(shù)為開發(fā)人員提供了類似C語(yǔ)言的編程環(huán)境，使得開發(fā)人員可以較方便地利用GPU的并行計(jì)算資源。

2、　　圖的Ramsey數(shù)在信息論和理論計(jì)算機(jī)科學(xué)中有重要的應(yīng)用，但是確定它的準(zhǔn)確值是非常困難的。在研究圖的Ramsey數(shù)特別是多色Ramsey數(shù)時(shí)，由于著色時(shí)細(xì)分的情形太多，所以很難單純用數(shù)學(xué)方法證明。同時(shí)，著色數(shù)的增加又會(huì)使計(jì)算量急劇增大，使得利用計(jì)算機(jī)求解的難度也大大增加。因此本文對(duì)GPU并行計(jì)算技術(shù)在多色Ramsey數(shù)求解算法中的應(yīng)用進(jìn)行了研究。
　　文章中首先對(duì)CUDA的編程模型、CUDA線程和CUDA內(nèi)存進(jìn)行了詳細(xì)介紹，并