Waxaan ku dhejiyay Github .
Waa miis xashiisheed fudud oo GPU ah oo awood u leh inuu farsameeyo boqollaal milyan oo wax la gelinayo ilbiriqsikii. Laptop-kayga NVIDIA GTX 1060, koodhka waxa uu geliyaa 64 milyan oo lammaane qiimo leh oo si aan kala sooc lahayn u soo saaray qiyaastii 210 ms wuxuuna ka saarayaa 32 milyan oo lammaane qiyaastii 64 ms.
Taasi waa, xawaaraha laptop-ku waa ku dhawaad ββ300 milyan gelin / sek iyo 500 milyan tirtirid/sek.
Jadwalku wuxuu ku qoran yahay CUDA, inkastoo isla farsamada lagu dabaqi karo HLSL ama GLSL. Hirgelintu waxay leedahay dhawr xaddidaad si loo hubiyo waxqabadka sare ee kaadhka fiidiyowga:
- Kaliya furayaasha 32-bit iyo qiyam isku mid ah ayaa la farsameeyaa.
- Miiska xashiishka wuxuu leeyahay cabbir go'an.
- Oo cabbirkani waa inuu la mid yahay laba awoodda.
Furayaasha iyo qiyamka, waxaad u baahan tahay inaad kaydsato calaamade fudud (code code kani waa 0xffffffff).
miiska xashiishka oo aan lahayn quful
Shaxda xashiishku waxay isticmaashaa ciwaanka furan oo leh , taas oo ah, waa si fudud tiro ka mid ah lammaane-qiimaha muhiimka ah oo lagu kaydiyo xusuusta oo leh waxqabadka kaydinta sare. Isla sidaas oo kale looma odhan karo silsiladaynta, taas oo ku lug leh raadinta tilmaame ku jira liis isku xidhan. Miiska xashiishku waa hab fudud oo lagu kaydiyo walxaha KeyValue:
struct KeyValue
{
uint32_t key;
uint32_t value;
};
Baaxadda miisku waa awood laba ah, ma aha nambarka ugu horreeya, sababtoo ah hal tilmaam oo degdeg ah ayaa ku filan in lagu dabaqo maaskarada pow2/AND, laakiin hawlwadeenka modulesku aad ayuu u gaabiyaa. Tani waxay muhiim u tahay kiiska baaritaanka tooska ah, maadaama miis toosan lagu eegayo tusmada booska waa in lagu duuduubo boos kasta. Natiijo ahaan, kharashka hawlgalka waxaa lagu daraa modulo kasta.
Jaantusku waxa uu kaydiyaa furaha iyo qiimaha shay kasta, ma aha xadhkaha furaha. Maadaama miiska uu kaydiyo furayaasha 32-bit oo keliya, xashiishku si degdeg ah ayaa loo xisaabiyaa. Koodhka sare waxa uu isticmaalaa xashiishka Murmur3, kaas oo qabta dhawr wareeg oo kaliya, XORs iyo isku dhufasho.
Miiska xashiishka wuxuu isticmaalaa farsamooyinka ilaalinta qufulka ee ka madax banaan nidaamka xusuusta. Xitaa haddii qaar ay qoraan hawlgallada ay carqaladeeyaan nidaamka hawlgallada kale, miiska xashiishka ayaa weli ilaalin doona xaaladda saxda ah. Hoos ayaan uga hadli doonaa arrintan. Farsamadu waxay si weyn ugu shaqeysaa kaarar fiidiyoow ah oo ku shaqeeya kumanaan dun oo isku mar ah.
Furayaasha iyo qiyamka miiska xashiishka waxaa loo bilaabay inay faaruqiyaan.
Koodhka waxaa loo bedeli karaa si loo xakameeyo furayaasha 64-bit iyo sidoo kale qiyamka. Furayaashu waxay u baahan yihiin wax-akhrinta, qorista, iyo isbar-bardhigga iyo hawlgallada is-beddelka. Qiimayaashuna waxay u baahan yihiin hawlo akhris iyo qorrid atomic ah. Nasiib wanaag, gudaha CUDA, hawlgallada wax-akhriska ee 32- iyo 64-bit ee qiyamka waa atomic haddii ay si dabiici ah isku mid yihiin (eeg hoos). ), iyo kaadhadhka fiidiyowga casriga ah waxay taageeraan hawlgallada isbarbardhigga iyo is-weydaarsiga 64-bit ee atomiga. Dabcan, markaad u guurto 64-bits, wax-qabadku wax yar ayuu hoos u dhacayaa.
Miiska xashiishka
Lammaane kasta oo qiimaha muhiimka ah ee ku jira miiska xashiishka waxay yeelan karaan mid ka mid ah afarta gobol:
- Furaha iyo qiimaha waa madhan. Xaaladdan, miiska xashiishka waa la bilaabay.
- Furaha waa la qoray, laakiin qiimaha weli lama qorin. Haddii dunta kale hadda akhrinayso xogta, waxay soo noqonaysaa faaruq. Tani waa wax iska caadi ah, wax la mid ah ayaa dhici lahaa haddii dunta kale ee fulinta ay shaqayn lahayd wax yar ka hor, waxaanan ka hadlaynaa qaab-dhismeedka xogta isku midka ah.
- Furaha iyo qiimaha labadaba waa la duubay.
- Qiimaha ayaa diyaar u ah mawduucyada kale ee fulinta, laakiin furuhu weli ma jiro. Tani waxay dhici kartaa sababtoo ah qaabka barnaamijka CUDA wuxuu leeyahay qaab xusuusta dabacsan oo la dalbaday. Tani waa caadi; xaalad kasta, furuhu weli waa madhan yahay, xitaa haddii qiimihiisu aanu sidaas ahayn.
Nuance muhiim ah ayaa ah in marka furaha lagu qoro booska, uusan dhaqaaqin - xitaa haddii furaha la tirtiro, waxaan kaga hadli doonaa tan hoos.
Koodhka miiska xashiishka xitaa wuxuu la shaqeeyaa moodooyinka xusuusta ee dabacsan ee la dalbado kaasoo aan la garanayn sida ay u kala horreeyaan xusuusta loo akhriyo loona qoro. Markaan eegno gelinta, ka-fiirinta, iyo tirtiridda miiska xashiishka, xusuusnow in lammaane kasta oo-qiimihiisu yahay mid ka mid ah afarta gobol ee kor lagu sharraxay.
Gelida miiska xashiishka
Shaqada CUDA ee gelisa lammaaneyaasha qiimaha muhiimka ah miiska xashiishka waxay u egtahay sidan:
void gpu_hashtable_insert(KeyValue* hashtable, uint32_t key, uint32_t value)
{
uint32_t slot = hash(key);
while (true)
{
uint32_t prev = atomicCAS(&hashtable[slot].key, kEmpty, key);
if (prev == kEmpty || prev == key)
{
hashtable[slot].value = value;
break;
}
slot = (slot + 1) & (kHashTableCapacity-1);
}
}
Si aad furaha u geliso, koodku waxa uu ku celcelinayaa shaxda miiska xashiishka oo ka bilaabmaya xadhkaha furaha la geliyey. Meel kasta oo ka mid ah shaxanka waxay fulisaa hawl isbarbardhigga atomiiga-iyo-is-beddelka kaas oo isbarbar dhigaya furaha booskaas iyo faaruq. Haddii la ogaado is-maandhaaf la'aan, furaha booska waxaa lagu cusboonaysiiyaa furaha la geliyo, ka dibna furaha booska asalka ah ayaa la soo celinayaa. Haddii furaha asalka ahi uu madhan yahay ama uu la mid yahay furaha la geliyey, markaas koodhka ayaa helay boos ku habboon gelinta oo wuxuu geliyaa qiimaha la geliyey booska.
Haddii hal kernel wac gpu_hashtable_insert() Waxaa jira walxo badan oo leh fure isku mid ah, ka dibna mid kasta oo ka mid ah qiyamkooda ayaa lagu qori karaa booska furaha. Tan waxaa loo arkaa mid caadi ah: mid ka mid ah qiimaha muhiimka ah ayaa qoraya inta lagu jiro wicitaanku wuu guuleysan doonaa, laakiin maadaama ay waxaas oo dhami ku dhacaan si isku mid ah dhowr qaybood oo fulin ah, ma saadaalin karno xusuusta qorista ayaa noqon doonta tan ugu dambeysa.
Miiska xashiishka
Koodhka raadinta furayaasha:
uint32_t gpu_hashtable_lookup(KeyValue* hashtable, uint32_t key)
{
uint32_t slot = hash(key);
while (true)
{
if (hashtable[slot].key == key)
{
return hashtable[slot].value;
}
if (hashtable[slot].key == kEmpty)
{
return kEmpty;
}
slot = (slot + 1) & (kHashTableCapacity - 1);
}
}
Si loo helo qiimaha furaha ku kaydsan miiska, waxaanu ku celcelinaynaa habka isku xidhka ee ka bilaabmaya xadhkaha furaha aanu raadinayno. Mid kasta oo ka mid ah boosaska, waxaan ku hubineynaa haddii furuhu yahay kan aan raadineyno, haddii ay sidaas tahay, waxaan soo celineynaa qiimihiisii. Waxaan sidoo kale hubinaa haddii furuhu madhan yahay, haddii ay sidaas tahay, waxaan joojineynaa raadinta.
Haddii aynaan heli karin furaha, koodka wuxuu soo celinayaa qiimo madhan.
Dhammaan hawlgalladan goobidda waxa lagu samayn karaa si isku mid ah iyada oo la gelinayo ama la tirtirayo. Lammaane kasta oo shaxda ku jira waxay yeelan doonaan mid ka mid ah afarta gobol ee kor lagu tilmaamay socodka.
Ku tirtirida miiska xashiishka
Koodhka tirtirida furayaasha:
void gpu_hashtable_delete(KeyValue* hashtable, uint32_t key, uint32_t value)
{
uint32_t slot = hash(key);
while (true)
{
if (hashtable[slot].key == key)
{
hashtable[slot].value = kEmpty;
return;
}
if (hashtable[slot].key == kEmpty)
{
return;
}
slot = (slot + 1) & (kHashTableCapacity - 1);
}
}
Tirtiridda furaha waxaa loo sameeyaa si aan caadi ahayn: waxaan ka tagnay furaha miiska oo aan calaamadeyno qiimahiisa (maaha furaha laftiisa) mid madhan. Koodhkani aad buu ula mid yahay lookup(), marka laga reebo in taranka marka laga helo furaha, uu qiimihiisu madhan yahay.
Sida kor ku xusan, mar furaha lagu qoro booska, mar dambe lama dhaqaajiyo. Xataa marka element laga saaro miiska, furuhu waa uu sii jiraa, qiimihiisu si fudud ayuu u madhan yahay. Tani waxay ka dhigan tahay in aan loo baahnayn in aan u isticmaalno hawlgalka qorista atomiga qiimaha booska, sababtoo ah dhib ma laha in qiimaha hadda uu faaruq yahay iyo in kale - weli way madhnaan doontaa.
Dib u habeynta miiska xashiishka
Waxaad bedeli kartaa cabbirka miiska xashiishka adiga oo abuuraya miis ka weyn oo aad geliso walxaha aan faaruqin ee miiska hore. Ma aanan hirgelin shaqadan sababtoo ah waxaan rabay inaan ka dhigo koodhka muunada mid fudud. Intaa waxaa dheer, barnaamijyada CUDA, qoondaynta xusuusta waxaa badanaa lagu sameeyaa koodhka martida loo yahay halkii laga heli lahaa CUDA kernel.
Maqaalka qeexayaa sida wax looga beddelo qaabka xogta la ilaaliyo ee qufulka ah.
Tartanka
Qodobada koodhka shaqada ee kor ku xusan gpu_hashtable_insert(), _lookup() ΠΈ _delete() hal mar marba hal lamaane oo qiimo leh. Oo ka hooseeya gpu_hashtable_insert(), _lookup() ΠΈ _delete() u habeeyaan lamaanayaal kala duwan oo is barbar socda, lamaane kasta oo ku jira dunta fulinta GPU gaar ah:
// CPU code to invoke the CUDA kernel on the GPU
uint32_t threadblocksize = 1024;
uint32_t gridsize = (numkvs + threadblocksize - 1) / threadblocksize;
gpu_hashtable_insert_kernel<<<gridsize, threadblocksize>>>(hashtable, kvs, numkvs);
// GPU code to process numkvs key/values in parallel
void gpu_hashtable_insert_kernel(KeyValue* hashtable, const KeyValue* kvs, unsigned int numkvs)
{
unsigned int threadid = blockIdx.x*blockDim.x + threadIdx.x;
if (threadid < numkvs)
{
gpu_hashtable_insert(hashtable, kvs[threadid].key, kvs[threadid].value);
}
}
Miiska xashiishka u adkaysta ee qufulka u adkaysta waxa uu taageeraa gelinta, baadhista, iyo tirtirka isku xidhan. Sababtoo ah lammaane-qiimaha muhiimka ah ayaa had iyo jeer ku jira mid ka mid ah afar gobol oo furayaashuna ma guuraan, miiska ayaa dammaanad qaadaya saxnaanta xitaa marka noocyada kala duwan ee hawlgallada la isticmaalo isku mar.
Si kastaba ha ahaatee, haddii aan u habaynno qayb gelinta iyo tirtiridda si is barbar socda, iyo haddii soo gelinta lammaanaha ay ka kooban yihiin furayaal nuqul ah, markaa ma awoodi doonno inaan saadaaliyo lammaanaha "guuleysan doona" -waxaa lagu qori doonaa miiska xashiishka ugu dambeeya. Aynu nidhaahno waxa aanu ugu yeedhnay koodka gelinta oo leh isku xidhka lammaane A/0 B/1 A/2 C/3 A/4. Markuu koodku dhammeeyo, lammaane B/1 ΠΈ C/3 waa la dammaanad qaaday inay joogaan miiska, laakiin isla markaa mid ka mid ah lamaanaha ayaa ka soo muuqan doona A/0, A/2 ama A/4. Tani waxay noqon kartaa ama ma noqon kartaa dhibaato - waxay dhammaan ku xiran tahay codsiga. Waxaa laga yaabaa inaad horay u sii ogaatid in aysan jirin furayaal nuqul ah oo ku jira habka wax gelinta, ama waxaa laga yaabaa inaadan dan ka lahayn qiimaha la qoray ee u dambeeyay.
Haddii ay tani dhibaato kugu tahay, waxaad u baahan tahay inaad u kala saarto lammaanaha nuqulka ah wicitaannada nidaamka CUDA ee kala duwan. CUDA, qalliin kasta oo soo wacaya kernel had iyo jeer wuu dhammeeyaa ka hor inta aan la soo wicin kernel-ka xiga (ugu yaraan hal dun dhexdooda. Tusaalaha kore, haddii aad hal kernel la wacdo A/0 B/1 A/2 C/3, iyo tan kale oo leh A/4, ka dibna furaha A heli doona qiimaha 4.
Hadda aan ka hadalno haddii ay hawluhu tahay lookup() ΠΈ delete() isticmaal tilmaan cad ama mid kacsan si aad u raacdo lammaane kala duwan oo ku dhex jira miiska xashiishka. Wuxuu sheegay in:
Isku-dubariduhu waxa uu dooran karaa in uu wanaajiyo wax-akhrinta iyo u qorista xusuusta caalamiga ah ama la wadaago.
volatile: ... Tixraac kasta oo ku saabsan doorsoomahan waxa lagu soo ururiyey xusuusta dhabta ah ee akhri ama qorista.
Tixgelinta saxda ah uma baahna codsi volatile. Haddii dunta fulinta adeegsato qiime kaydsan oo laga soo qaatay hawlgal hore loo akhriyey, markaas waxa la isticmaalayaa xog yar oo duug ah. Laakin wali, tani waa macluumaadka laga helay xaalada saxda ah ee miiska xashiishka wakhti go'an oo ah wicitaanka kernel-ka. Haddii aad u baahan tahay inaad isticmaasho macluumaadkii ugu dambeeyay, waxaad isticmaali kartaa tusaha volatile, laakiin markaa wax qabadku wax yar ayuu hoos u dhacayaa: marka loo eego imtixaanadayda, marka la tirtirayo 32 milyan oo walxood, xawaaruhu wuxuu hoos u dhacay 500 milyan oo tirtirid / ilbiriqsi ilaa 450 milyan oo tirtirid / ilbiriqsi.
Wax-soo-saarka
Imtixaanka gelinta 64 milyan oo walxood oo la tirtiro 32 milyan oo iyaga ka mid ah, tartan u dhexeeya std::unordered_map oo runtii ma jiro miiska xashiishka ee GPU-ga:
std::unordered_map waxay ku bixisay 70 ms gelinta iyo ka saarista canaasiirta ka dibna sii dayntooda unordered_map (ka takhalusida malaayiin walxood waxay qaadataa waqti badan, sababtoo ah gudaha unordered_map meelo badan oo xusuusta ah ayaa la sameeyaa). Si daacad ah, std:unordered_map xayiraad gebi ahaanba kala duwan. Waa hal xadhig oo CPU ah oo fulin ah, waxay taageertaa qiyamka muhiimka ah ee cabbir kasta, waxay si fiican u qabataa heerarka isticmaalka sare, waxayna muujisaa waxqabadka xasilloon ka dib tirtirid badan.
Muddada miiska xashiishka ee GPU-ga iyo isgaadhsiinta barnaamijyada dhexdooda waxay ahayd 984 ms. Tan waxa ka mid ah wakhtiga lagu qaatay in miiska la dhigo xusuusta oo la tirtiro (la qoondeeyo 1 GB oo xusuusta ah hal mar, taas oo wakhti ku qaadanaysa CUDA), gelinta iyo tirtirida walxaha, iyo ku celcelinta iyaga. Dhammaan nuqullada ku jira iyo ka soo baxa xusuusta kaadhka fiidiyowga ayaa sidoo kale la tixgeliyaa.
Miiska xashiishka laftiisu wuxuu qaatay 271 ms inuu dhammaystiro. Tan waxa ku jira wakhtiga uu ku qaatay kaadhka fiidyowga gelinta iyo tirtirida walxaha, oo aan xisaabta ku darsanayn wakhtiga lagu koobiyaynayo xusuusta iyo ku celcelinta miiska natiijada. Haddii miiska GPU uu noolaado wakhti dheer, ama haddii miiska xashiishka uu ku jiro gebi ahaanba xusuusta kaarka fiidiyowga (tusaale ahaan, si loo abuuro miiska xashiishka kaas oo loo isticmaali doono code GPU kale oo aan ahayn processor-ka dhexe), markaa natiijada imtixaanku waa mid khusaysa.
Miiska xashiishka ee kaadhka fiidiyowga ayaa muujinaya waxqabadka sare sababtoo ah wax soo saarka sare iyo isbarbardhigga firfircoon.
Dhibaatooyin
Nashqada miiska xashiishka ayaa leh dhowr arrimood oo ay tahay in laga digtoonaado:
- Baaritaanka tooska ah waxaa caqabad ku ah isugeynta, taasoo sababta furayaasha miiska in la dhigo wax ka yar sidii saxda ahayd.
- Furayaasha lagama saaro shaqada
deleteoo wakhti ka dib waxay isku buuqaan miiska.
Natiijo ahaan, waxqabadka miiska xashiishka ayaa si tartiib tartiib ah hoos u dhigi kara, gaar ahaan haddii uu jiro waqti dheer oo uu leeyahay waxyaabo badan oo la geliyo oo tirtiro. Hal dariiqo oo lagu yareeyo khasaarooyinkan ayaa ah in dib loo geliyo miis cusub oo leh qiime ka faa'iidaysi hooseeya oo la shaandheeyo furayaasha la saaray inta lagu jiro dib u habeynta.
Si aan u qeexo arrimaha lagu sharraxay, waxaan isticmaali doonaa koodhka sare si aan u abuuro miis leh 128 milyan oo curiye iyo loop dhex mara 4 milyan oo curiye ilaa aan ka buuxiyo 124 milyan boosas (heerka isticmaalka ee ku saabsan 0,96). Waa kan shaxda natiijada, saf kastaa waa wicitaanka CUDA kernel si loo geliyo 4 milyan oo walxood oo cusub hal miis xashiish ah:
Heerka isticmaalka
Muddada gelinka 4 curiye
0,00
11,608448 ms (361,314798 milyan furayaal/sek.)
0,03
11,751424 ms (356,918799 milyan furayaal/sek.)
0,06
11,942592 ms (351,205515 milyan furayaal/sek.)
0,09
12,081120 ms (347,178429 milyan furayaal/sek.)
0,12
12,242560 ms (342,600233 milyan furayaal/sek.)
0,16
12,396448 ms (338,347235 milyan furayaal/sek.)
0,19
12,533024 ms (334,660176 milyan furayaal/sek.)
0,22
12,703328 ms (330,173626 milyan furayaal/sek.)
0,25
12,884512 ms (325,530693 milyan furayaal/sek.)
0,28
13,033472 ms (321,810182 milyan furayaal/sek.)
0,31
13,239296 ms (316,807174 milyan furayaal/sek.)
0,34
13,392448 ms (313,184256 milyan furayaal/sek.)
0,37
13,624000 ms (307,861434 milyan furayaal/sek.)
0,41
13,875520 ms (302,280855 milyan furayaal/sek.)
0,44
14,126528 ms (296,909756 milyan furayaal/sek.)
0,47
14,399328 ms (291,284699 milyan furayaal/sek.)
0,50
14,690304 ms (285,515123 milyan furayaal/sek.)
0,53
15,039136 ms (278,892623 milyan furayaal/sek.)
0,56
15,478656 ms (270,973402 milyan furayaal/sek.)
0,59
15,985664 ms (262,379092 milyan furayaal/sek.)
0,62
16,668673 ms (251,627968 milyan furayaal/sek.)
0,66
17,587200 ms (238,486174 milyan furayaal/sek.)
0,69
18,690048 ms (224,413765 milyan furayaal/sek.)
0,72
20,278816 ms (206,831789 milyan furayaal/sek.)
0,75
22,545408 ms (186,038058 milyan furayaal/sek.)
0,78
26,053312 ms (160,989275 milyan furayaal/sek.)
0,81
31,895008 ms (131,503463 milyan furayaal/sek.)
0,84
42,103294 ms (99,619378 milyan furayaal/sek.)
0,87
61,849056 ms (67,815164 milyan furayaal/sek.)
0,90
105,695999 ms (39,682713 milyan furayaal/sek.)
0,94
240,204636 ms (17,461378 milyan furayaal/sek.)
Marka ka faa'iidaysigu kordho, waxqabadku wuu yaraanayaa. Tani maahan mid la jecel yahay inta badan kiisaska. Haddi codsi geliyo curaarta miis ka dibna tuuro (tusaale, marka ereyada buug lagu tirinayo), markaa tani dhib maaha. Laakiin haddii codsigu isticmaalo miis xashiish ah oo cimri dheer (tusaale ahaan, tifaftiraha sawirada si uu u kaydiyo qaybaha aan faaruqin ee sawirada halkaas oo isticmaaluhu inta badan galiyo oo tirtiro macluumaadka), markaa dhaqankani wuxuu noqon karaa dhibaato.
Oo waxay cabbireen qoto-dheeraanta miis-xashiistaha ka dib 64 milyan oo la geliyo (cutubka isticmaalka 0,5). Celceliska qoto dheer wuxuu ahaa 0,4774, markaa furayaasha intooda badani waxay ahaayeen booska ugu fiican ee suurtogalka ah ama hal boos oo ka fog booska ugu fiican. Qoto dheer ee dhawaaqa ugu badnaan wuxuu ahaa 60.
Waxaan markaas cabiray qoto-dheeraanta baadhista ee miis ay ku jiraan 124 milyan oo la geliyo (cutubka isticmaalka 0,97). Celceliska qoto dheer wuxuu horey u ahaa 10,1757, iyo ugu badnaan - 6474 (!!). Waxqabadka dareenka tooska ah ayaa si weyn hoos ugu dhacaya heerarka isticmaalka sare.
Way fiicantahay in hoos loo dhigo heerka isticmaalka miiska xashiishka. Laakiin markaa waxaan kordhineynaa waxqabadka kharashka isticmaalka xusuusta. Nasiib wanaag, marka laga hadlayo furayaasha 32-bit iyo qiyamka, tani waa la caddayn karaa. Haddii tusaale ahaan kor ku xusan, miis leh 128 milyan oo walxood, waxaan ku haynaa saamiga isticmaalka ee 0,25, ka dibna waxaan ku dhejin karnaa wax ka badan 32 milyan oo walxood, 96 milyan ee soo harayna waa la lumin doonaa - 8 bytes ee lammaane kasta , 768 MB oo xusuusta luntay.
Fadlan ogow in aan ka hadlayno luminta xusuusta kaadhka fiidiyowga, taas oo ah kheyraad ka qiimo badan marka loo eego nidaamka xusuusta. Inkasta oo inta badan kaararka casriga casriga ah ee taageera CUDA ay leeyihiin ugu yaraan 4 GB ee xusuusta (waqtiga qorista, NVIDIA 2080 Ti wuxuu leeyahay 11 GB), weli ma noqon doonto go'aanka ugu xigmadda badan ee lagu lumiyo qaddarkaas.
Ka dib waxaan wax badan ka qori doonaa samaynta miisaska xashiishka ee kaararka fiidyowga ah ee aan lahayn dhibaatooyinka qoto dheer ee baaritaanka, iyo sidoo kale siyaabaha dib loogu isticmaalo boosaska la tirtiray.
Qiyaasta qoto dheer ee sanqadha
Si loo go'aamiyo qoto dheeraanta baaritaanka furaha, waxaan ka soo saari karnaa xashiishka furaha (tusmada miiskeeda ku habboon) tusmihiisa dhabta ah:
// get_key_index() -> index of key in hash table
uint32_t probelength = (get_key_index(key) - hash(key)) & (hashtablecapacity-1);
Sababtoo ah sixirka laba-labo-labo ee tirooyinka binary-ga ah iyo xaqiiqda ah in awoodda miiska xashiishka ay tahay laba awoodda laba, habkani wuxuu shaqeyn doonaa xitaa marka tusaha muhiimka ah loo wareejiyo bilawga miiska. Aynu soo qaadano furaha 1, laakiin la geliyo booska 3. Kadibna miis leh 4 waxaan heleynaa (3 β 1) & 3, oo u dhiganta 2.
gunaanad
Haddii aad hayso su'aalo ama faallooyin, fadlan iigu soo dir emailka ama mawduuc cusub ka fur.
Xeerkan waxa lagu qoray dhiirigelin ka timid maqaallo aad u wanaagsan:
Mustaqbalka, waxaan sii wadi doonaa inaan wax ka qoro fulinta miiska xashiishka ee kaararka fiidiyowga iyo falanqaynta waxqabadkooda. Qorshayaashaydu waxa ka mid ah silsiladaynta, Robin Hood hashing, iyo xashiishta cuckoo iyadoo la isticmaalayo hawlgallada atomiga ee qaab-dhismeedka xogta ee saaxiibtinimo ee GPU.
Source: www.habr.com