[發(fā)明專利]圖形處理單元中的3D加速結(jié)構(gòu)的完全并行適當(dāng)?shù)貥?gòu)造

無效

• 申請(qǐng)?zhí)枺?/td>: 201310076982.8
• 申請(qǐng)日: 2013-03-11
• 公開（公告）號(hào): CN103440238A
• 公開（公告）日: 2013-12-11
• 發(fā)明（設(shè)計(jì)）人: 泰羅·卡拉斯
• 申請(qǐng)（專利權(quán)）人: 輝達(dá)公司
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 北京市磐華律師事務(wù)所 11336
• 代理人: 董巍;徐丁峰

相關(guān)申請(qǐng)的交叉引用

本申請(qǐng)是2012年3月9日提交的、名為“FULLY?PARALLEL?IN-PLACE?CONSTRUCTION?OF3D?ACCELERATION?STRUCTURES?ON?A?GPU”的臨時(shí)專利申請(qǐng)61/609,156的變換并要求其優(yōu)先權(quán)和權(quán)益，本文在此通過援引的方式對(duì)其全文加以合并。

背景技術(shù)

近些年來，通用計(jì)算產(chǎn)生了一些用于構(gòu)造層次包圍盒（BVH）、八叉樹以及k-d樹的方法用于數(shù)百萬的實(shí)時(shí)的基元。一些方法目標(biāo)在于使用表面積啟發(fā)式（surface?area?heuristic）最大化結(jié)果樹的質(zhì)量，而其他方法選擇用增加的構(gòu)造的速度換取樹的質(zhì)量。

正確的質(zhì)量與速度的權(quán)衡特別依靠于應(yīng)用。樹的質(zhì)量在經(jīng)常重新使用相同加速結(jié)構(gòu)用于數(shù)百萬的射線的射線追蹤中通常是優(yōu)選的。實(shí)時(shí)物理中的寬階段（Broad-phase）碰撞檢測(cè)和粒子交互表示其他極端，其中構(gòu)造速度是首要重要的—必須在每個(gè)時(shí)間步長上重新構(gòu)造加速結(jié)構(gòu)，并且詢問的數(shù)目通常相當(dāng)小。此外，某些應(yīng)用，諸如基于體素（voxel）的全局照明和表面重新構(gòu)造，具體依靠規(guī)則的八叉樹和k-d樹，其中樹的質(zhì)量是固定的。

目標(biāo)在于最大化構(gòu)造速度的現(xiàn)有方法的主要缺點(diǎn)是其以順序方式生成節(jié)點(diǎn)層次，通常一次一級(jí)，因?yàn)楸仨氃谙乱粋€(gè)可以開始之前完成每輪處理。這限制了其在樹的頂級(jí)可達(dá)到的并行度的量，并可導(dǎo)致并行核心的嚴(yán)重的未充分利用。順序處理具有小工作負(fù)載，已是當(dāng)前GPU的瓶頸，當(dāng)前GPU要求數(shù)萬獨(dú)立的并行線程以完全利用其計(jì)算能力。可預(yù)計(jì)在將來隨著并行核心的數(shù)目持續(xù)增加，問題甚至?xí)@著。順序處理的另一個(gè)含義是現(xiàn)有方法以寬度優(yōu)先（breadth-first）的次序輸出層次，雖然考慮到數(shù)據(jù)所在位置和高速緩存命中率，深度優(yōu)先的次序?qū)⑼ǔＪ莾?yōu)選的。

發(fā)明內(nèi)容

一種用于最大化諸如層次包圍體（BVH）、八叉樹以及k-d樹的層次樹的構(gòu)造中的平行度的計(jì)算機(jī)實(shí)現(xiàn)的方法和系統(tǒng)。本發(fā)明的實(shí)施例提供用于構(gòu)造BVH、八叉樹以及k-d樹的快速的方法，以便整體性能與可用核心的數(shù)目成線性比例，并且作為結(jié)果的數(shù)據(jù)結(jié)構(gòu)總是按照嚴(yán)格的深度優(yōu)先的次序。新穎的方法包括以完全數(shù)據(jù)并行的方式構(gòu)造二叉基數(shù)樹。二叉基數(shù)樹隨后用作用于有效地構(gòu)造其他類型的樹的構(gòu)建塊。

在一個(gè)實(shí)施例中，公開了具有用于使計(jì)算機(jī)系統(tǒng)執(zhí)行方法的計(jì)算機(jī)可執(zhí)行指令的非暫時(shí)性計(jì)算機(jī)可讀存儲(chǔ)介質(zhì)。方法包括確定包括被索引化的基元節(jié)點(diǎn)的總數(shù)的多個(gè)基元，其中多個(gè)基元與層次樹的葉節(jié)點(diǎn)相對(duì)應(yīng)。方法包括將多個(gè)基元排序。方法包括以至多要求關(guān)于基元節(jié)點(diǎn)的總數(shù)成線性數(shù)量的臨時(shí)存儲(chǔ)的方式構(gòu)建層次樹。方法還包括與層次樹的內(nèi)部節(jié)點(diǎn)的祖先節(jié)點(diǎn)的一個(gè)或多個(gè)并行地構(gòu)建該內(nèi)部節(jié)點(diǎn)。也就是說，與層次樹的一個(gè)或多個(gè)內(nèi)部節(jié)點(diǎn)的各自的祖先節(jié)點(diǎn)的一個(gè)或多個(gè)并行地構(gòu)建該內(nèi)部節(jié)點(diǎn)。

在另一個(gè)實(shí)施例中，公開了計(jì)算機(jī)系統(tǒng)，包括處理器，以及耦連到該處理器并具有存儲(chǔ)在其中的指令的存儲(chǔ)器，該指令如果由計(jì)算機(jī)系統(tǒng)所執(zhí)行，那么使計(jì)算機(jī)系統(tǒng)執(zhí)行方法。方法包括確定包括被索引化的基元節(jié)點(diǎn)的總數(shù)的多個(gè)基元，其中多個(gè)基元與層次樹的葉節(jié)點(diǎn)相對(duì)應(yīng)。方法包括將多個(gè)基元排序。方法包括以至多要求關(guān)于基元節(jié)點(diǎn)的總數(shù)成線性數(shù)量的臨時(shí)存儲(chǔ)的方式構(gòu)建層次樹。方法還包括與層次樹的內(nèi)部節(jié)點(diǎn)的祖先節(jié)點(diǎn)的一個(gè)或多個(gè)并行地構(gòu)建該內(nèi)部節(jié)點(diǎn)。也就是說，與層次樹的一個(gè)或多個(gè)內(nèi)部節(jié)點(diǎn)的各自的祖先節(jié)點(diǎn)的一個(gè)或多個(gè)并行地構(gòu)建該內(nèi)部節(jié)點(diǎn)。

在又一個(gè)實(shí)施例中，公開了包括用于為多個(gè)基元指派莫頓碼的裝置的系統(tǒng)，所述多個(gè)基元包括被索引化的基元節(jié)點(diǎn)的總數(shù)，其中多個(gè)基元與層次樹的葉節(jié)點(diǎn)相對(duì)應(yīng)。系統(tǒng)包括用于將多個(gè)基元排序的裝置。系統(tǒng)包括用于以至多要求關(guān)于基元節(jié)點(diǎn)的總數(shù)成線性數(shù)量的臨時(shí)存儲(chǔ)的方式構(gòu)建層次樹的裝置。系統(tǒng)還包括用于與層次樹的內(nèi)部節(jié)點(diǎn)的祖先節(jié)點(diǎn)的一個(gè)或多個(gè)并行地構(gòu)建該內(nèi)部節(jié)點(diǎn)的裝置。也就是說，與層次樹的一個(gè)或多個(gè)內(nèi)部節(jié)點(diǎn)的各自的祖先節(jié)點(diǎn)一個(gè)或多個(gè)并行地構(gòu)建該內(nèi)部節(jié)點(diǎn)。

在一個(gè)實(shí)施例中，公開了具有用于使計(jì)算機(jī)系統(tǒng)執(zhí)行用于根據(jù)二叉樹構(gòu)造層次包圍體的方法的計(jì)算機(jī)可執(zhí)行指令的非暫時(shí)性計(jì)算機(jī)可讀存儲(chǔ)介質(zhì)。方法包括提供二叉樹，該二叉樹包括多個(gè)葉節(jié)點(diǎn)和多個(gè)內(nèi)部節(jié)點(diǎn)。多個(gè)內(nèi)部節(jié)點(diǎn)的每個(gè)唯一地與2個(gè)子節(jié)點(diǎn)相關(guān)聯(lián)，其中每個(gè)子節(jié)點(diǎn)包括內(nèi)部節(jié)點(diǎn)或葉節(jié)點(diǎn)。方法還包括通過從多個(gè)葉節(jié)點(diǎn)朝向根節(jié)點(diǎn)向上遍歷二叉樹，確定多個(gè)包圍體用于二叉樹中的節(jié)點(diǎn)，其中每個(gè)父節(jié)點(diǎn)由稍后到達(dá)的相對(duì)應(yīng)的子節(jié)點(diǎn)處理一次。