Inona no fiantraikany amin'ny hafainganam-pandehan'ny programa C++ sy ny fomba hahatratrarana izany amin'ny kaody avo lenta? Ny mpamorona ny tranomboky CatBoost, Evgeny Petrov, dia namaly ireo fanontaniana ireo tamin'ny fampiasana ohatra sy fanoharana avy amin'ny traikefa niasa tamin'ny CatBoost ho an'ny x86_64.
Tatitra video
- Salama daholo. Manao fanatsarana CPU ho an'ny tranomboky fianarana milina CatBoost aho. Ny ampahany lehibe amin'ny tranomboky dia voasoratra amin'ny C ++. Androany aho dia hilaza aminao ny fomba tsotra hahatongavana amin'ny hafainganam-pandeha.
Mizara roa ny hafainganam-pandehan'ny kajy. Ny ampahany voalohany dia ny algorithm. Raha manao fahadisoana amin'ny safidin'ny algorithm isika, dia tsy afaka manao izany haingana ianao any aoriana. Ny ampahany faharoa dia ny fomba hanatsarana ny algorithm ho an'ny rafitra informatika ananantsika, miaraka amin'ny fahombiazany sy ny fampandehanana azy.
Misaraka, ny fifanakalozana angona sy ny kajikajy dia tsy maintsy raisina noho ny fahasamihafana lehibe amin'ny hafainganam-pandehany. Raha raisina ho toy ny hafainganam-pandehan'ny mpandeha an-tongotra ny hafainganam-pandehan'ny fitadidiana, ny hafaingan'ny kajy dia eo amin'ny hafainganam-pandehan'ny fiaramanidina mpandeha.
Mba hanamafisana an'io fahasamihafana io, ny maritrano dia manana ambaratonga caching maromaro. Ny haingana indrindra sy kely indrindra dia ny cache L1. Avy eo dia misy cache lehibe kokoa sy miadana kokoa, ny ambaratonga faharoa. Ary misy cache be dia be, izay mety ho megabytes am-polony, cache ambaratonga fahatelo, fa io no miadana indrindra.
Noho ny tsy fitovian'ny taham-panakalozana angon-drakitra momba ny kajy, ny kaody kajy dia mizara ho kilasy roa. Ny kilasy iray dia voafetra amin'ny bandwidth, izany hoe ny hafainganam-pandehan'ny fifanakalozana angona. Ny kilasy faharoa dia voafetra amin'ny hafainganam-pandehan'ny processeur. Ny sisin-tany misy eo amin'izy ireo dia apetraka arakaraka ny isan'ny asa atao amin'ny byte data iray. Matetika izany dia tsy miova ho an'ny code manokana.
Ny ankamaroan'ny kaody mavesatra amin'ny fikajiana dia nosoratana lava be, nohatsaraina tsara, ary misy trano famakiam-boky marobe, noho izany dia misy dikany raha mahita fikajiana mavesatra ao amin'ny codeo ianao, mitadiava tranomboky afaka manao izany ho anao.
Amin'ny ambiny, ny compiler dia tsy mahafantatra ny fomba hanaovana ny zava-drehetra, satria voafetra ihany ny isan-jaton'ny loharano ampiasaina amin'ny fampandrosoana. Iza amin'izy ireo no mivoatra kokoa na tsy dia mavitrika amin'izao fotoana izao, izany hoe manohana ny fenitra ary miezaka manaraka izany? Ity ny frontend EDG, izay ampiasaina amin'ny derivatives isan-karazany, ohatra, ny Intel compiler; LLVM; GNU sy Microsoft frontend.
Satria vitsy amin'izy ireo, ny compiler dia tsy manohana afa-tsy ny fomba fanaraha-maso matetika sy ny fiankinan'ny angona. Raha mijery ny fanaraha-maso isika dia fizarana linear sy tsingerina tsotra, izany hoe filaharan'ny toromarika sy ny famerimberenana. Mianatra ny fiankinan-doha matetika amin'ny angon-drakitra avy amin'ny fampihenana izy ireo, rehefa mamintina singa maro ho iray isika, mirodana ary manao hetsika isaky ny singa amin'ny array iray na maromaro.
Inona no sisa ho an'ny developer? Azo zaraina ho fizarana efatra izany. Ny voalohany dia ny maritrano ny fampiharana, ny compiler dia tsy afaka mamorona izany ho antsika.
Ny parallelization koa dia zavatra sarotra ho an'ny compiler. Miasa amin'ny fitadidiana - satria tena sarotra: mila mandinika ny maritrano, sy ny parallelization, ary ny rehetra miaraka. Ankoatra izany, ny compiler dia tsy mahafantatra ny fomba hanombanana araka ny tokony ho izy ny kalitaon'ny fanatsarana, ny hafainganam-pandehan'ny code. Izahay, mpamorona, dia tsy maintsy manao izany koa, mandray fanapahan-kevitra - hanatsara kokoa na hijanona.
Ao amin'ny ampahany amin'ny maritrano, hojerentsika ny fanamafisan'ny overhead, antso virtoaly, izay iorenan'ny maritrano amin'ny tranga maro.
Andao hiala amin'ny equation ny parallèle. Mikasika ny fampiasana ny fitadidiana: izany ihany koa, amin'ny lafiny iray, ny fihenam-bidy sy ny asa marina miaraka amin'ny angon-drakitra, ny fametrahana azy ireo amin'ny fitadidiana. Raha resaka fanombanana ny fahombiazany, andao hiresaka momba ny profiling sy ny fomba fitadiavana bottleneck amin'ny code.
Ny fampiasana interface sy karazana data abstract dia iray amin'ireo fomba famolavolana lehibe. Diniho ny code computational mitovy amin'ny fianarana milina. Kaody misy fepetra ity izay manavao ny vinavina amin'ny fomba gradient.
Raha mijery kely ny ao anatiny isika ary miezaka ny hahatakatra ny zava-mitranga ao anatiny, dia manana interface IDerCalcer isika amin'ny kajy ny derivatives amin'ny asa fatiantoka, ary ny fiasa izay manova ny vinavina (ny vinavinantsika) araka ny gradient amin'ny asa fatiantoka.
Eo amin'ny ilany havanana amin'ny slide dia hitanao ny dikan'izany amin'ny tranga 10D. Ary amin'ny fianarana milina, ny haben'ny vinavina dia tsy roa na telo, fa singa an-tapitrisany, am-polony tapitrisa. Andeha hojerentsika ny hatsaran'ity code ity ho an'ny vector misy singa XNUMX tapitrisa eo ho eo.
Andeha horaisintsika ho toy ny asa tanjona ny fivilian-dàlana manara-penitra ary handrefesana ny fomba fiasan'izy io, hatraiza no hampiova izany vinavina izany. Ny derivative an'io asa tanjona io dia aseho amin'ny slide. Ny fotoana fiasana amin'ny milina misy fepetra, izay mijanona ho raikitra avy eo, dia 40 ms.
Andeha hojerentsika izay tsy mety eto. Ny zavatra voalohany mahasarika ny saina dia antso virtoaly. Raha mijery ny profiler ianao dia afaka mahita fa, arakaraka ny isan'ny masontsivana, izany dia tokony ho dimy ka hatramin'ny folo toromarika. Ary raha toa ka, toy ny amin'ny tranga misy antsika, ny kajy ny derivative dia asa roa aritmetika fotsiny, dia mety hivadika ho ambony ambony izany. Ho an'ny vatana lehibe rehefa manao kajy ny derivatives dia eo ho eo izany. Ho an'ny vatana fohy izay manisa derivative - lazao, na dia 500 aza ny torolàlana, fa 20, 50 na latsaka - izany dia efa ho isan-jaton'ny fotoana. Ny hatao? Andeha isika hanandrana ny buffer ny antso virtoaly amin'ny alalan'ny fanovana ny interface tsara.
Tamin'ny voalohany, dia nikajy ny derivatives isaky ny teboka, ho an'ny singa tsirairay amin'ny vector misaraka. Andao handeha amin'ny fanodinana singa tsirairay mankany amin'ny fanodinana amin'ny alàlan'ny vectors. Andeha horaisintsika ny maodely C++ mahazatra, izay ahafahanao miasa miaraka amin'ny fomba fijery amin'ny vector. Na, raha tsy mahazaka ny fenitra farany ny mpanangona anao, dia azonao atao ny mampiasa kilasy tsotra vita an-trano izay mitazona tondro amin'ny angona sy ny habeny. Ahoana no hiova ny kaody? Tavela amin'ny antso iray izay manisa ny derivatives isika, ary avy eo dia tsy maintsy manampy loop iray izay hanavao ny vinavina.
Ho fanampin'ny fampidirana tsingerina dia mbola mila mijery ny angon-drakitra fanindroany isika, izany hoe, mamaky ny vinavina vinavina sy ny gradient vector izay vao nokajintsika fanindroany.
Handrefy indray isika amin'ny milina iray ihany ary hojerentsika izay niharatsy, nisy tsy nety. Andeha hojerentsika izay nitranga tamin'ny code.
Tsy misy dikany ny miahiahy momba ny tsingerin'ny zavatra iray, satria io dia mitovy amin'ny fomba fahita matetika izay fantatry ny mpamoron-kira sy manatsara tsara. Ny isan'ny asa isaky ny singa angon-drakitra dia ho kely noho ny vidin'ny antso virtoaly.
Fa ny famoronana vector lehibe sy ny faharoa mandalo azy - eto amin'ity toerana ity dia ilaina ny miahiahy olana. Mba hahatakarana ny antony maha-ratsy izany sy mitarika ho amin'ny fihemorana, dia mila maka sary an-tsaina ny zava-mitranga ao amin'ny fitadidiana rehefa mandeha ny kaody izay hitantsika eo amin'ny slide eo ankavanana.
Rehefa kajy ny vector derivatives dia tonga amin'ny tsingerina izay manova ny vinavina. Talohan'ity tsingerina ity dia ampahany kely amin'ny angona ihany no hijanona ao amin'ny cache LXNUMX haingana, izay mandeha amin'ny fatran'ny processeur. Eo amin'ny solaitrabe, maitso izy io amin'ny jiron'ny fifamoivoizana. Ny angon-drakitra sisa dia havoaka ao amin'ny cache ho fitadidiana, ary rehefa mandeha ny tadio hanavao ny faminaniana, dia tsy maintsy vakiana fanindroany avy ao amin'ny fitadidiana ny angona. Ary miasa ho antsika izany, amin'ny ankapobeny, miadana be, amin'ny hafainganam-pandehan'ny mpandeha an-tongotra.
Rehefa manavao ny vinavina isika dia tsy voatery mamaky ny derivative rehetra indray mandeha. Ampy ny manisa azy ireo amin'ny amboara lehibe mba hahazoana antso virtoaly. Noho izany dia misy dikany ny mizara ny kajy ny derivatives sy ny fanavaozana ny vinavina ho sakana kely ary mampifangaro ireo hetsika roa ireo. Inona no ho vokatr'izany raha mijery ny toerana hovakiana ny angon-drakitra ianao?
Izany dia hitarika amin'ny hoe haka angon-drakitra amin'ny fotoana rehetra isika, ary ny hoe hijanona ao amin'ny cache L1 ny angon-drakitra ary tsy hanam-potoana handehanana amin'ny fitadidiana miadana. Ary avy eo dia mila mahatakatra isika hoe iza no hilaza amintsika io haben'ny sakana io.
Lojika ny ankinina amin'ny kajy derivative, satria izy ihany no mahalala hoe ohatrinona ny cache ilainy. Manaraka, mila manoratra indray ny loop izay nojerentsika tamin'ny array ianao. Mila zaraina roa izany. Ny tadivavarana ivelany dia hamakivaky ireo sakana, ary ao anatiny dia handalo indroa ireo singa ao amin'ny sakana.
Eto izy, ivelany amin'ny sakana.
Ary eto ny singa anatiny amin'ny sakana.
Raisinay fa mety tsy feno ny sakana farany.
Andeha hojerentsika hoe inona avy izany. Hitanay fa naminavina tsara izahay, azonay tsara ny zava-nitranga, ary tamin'ny vidin'ny fiovana kely teo amin'ny fehezan-dalàna, dia nampihena valo isan-jato ny fotoana fiasana. Mbola afaka manao zavatra bebe kokoa anefa isika. Mila mandinika indray ny zavatra nosoratantsika isika. Jereo ny asa kajy ny derivatives ho antsika. Izy io dia mamerina antsika vector derivatives, ny fidirana amin'ireo singa izay hiadana amin'ny toe-javatra ratsy.
Misy antony roa. Voalohany, mizara vector amin'ny heap. Tsara ny mety hisian'ny famoronana sy hopotehina imbetsaka ity vector ity. Ny minus faharoa amin'ny resaka hafainganam-pandeha dia isaky ny mahazo fahatsiarovana isika, angamba amin'ny adiresy vaovao. Ity fahatsiarovana ity dia ho "mangatsiaka" amin'ny fomba fijerin'ny cache, izany hoe, alohan'ny hanoratana azy, ny processeur dia hanao vakiteny fanampiny mba hanombohana ny angona ao amin'ny cache.
Mba hanamafisana izany dia mila manaisotra ny fizarana avy amin'ny loop ianao. Mba hanaovana izany, dia tsy maintsy manova indray ny interface tsara isika, atsaharo ny famerenana ny vectors ary manomboka manoratra derivatives ao amin'ny fahatsiarovana izay azontsika avy amin'ny kaody fiantsoana.
Ity dia teknika manara-penitra - ny fanesorana ny fanodinkodinana rehetra misy loharanon-karena avy amin'ny bottlenecks ao amin'ny code computational. Andao ampiana paramètre iray hafa amin'ny fomba CalcDer, jereo ny vector izay tokony hianjeran'ny derivatives.
Ny kaody dia hiova amin'ny fomba mazava. Ny vector derivative dia ho iray, ivelan'ny tadivavarana rehetra, ary ampiana paramètre vaovao fotsiny amin'ny fomba.
Mijery izahay. Hita fa nahazo valo isan-jato teo ho eo isika raha oharina amin'ny dikan-teny teo aloha, ary raha oharina amin'ny dikan-teny fototra - efa 15%.
Mazava ho azy fa ny fanatsarana dia tsy voafetra amin'ny fampihenana ny vidin'ny overhead, fa misy karazana bottlenecks hafa.
Mba hanazavana ny fomba fitadiavana bottleneck dia mila fehezan-dalàna andrana tsotra iray hafa isika. Ohatra, naka ny transposition matrix aho. Manana matrix approx sy matrix approxByCol izay ilaintsika hametrahana ny angon-drakitra navadika. Ary akany tsotra misy tsingerina roa. Tsy misy antso virtoaly eto mba hamoronana vectors. Fandefasana data fotsiny izany. Ny loop dia mety ho an'ny compiler.
Andeha hojerentsika ny fomba fiasan'ity kaody ity amin'ny matrix lehibe sy amin'ny milina manokana.
Ohatra, nalaiko ny isan'ny andalana 1000, ny isan'ny tsanganana 100. Ny milina dia mpizara Intel, fototra iray. Ny fahatsiarovana dia mitovy amin'izany, zava-dehibe ho antsika izany, satria ny asa rehetra miaraka amin'ny fitadidiana sy ny hafainganam-pandeha dia miankina amin'ny hafainganan'ny fahatsiarovana. Nandrefy izahay ary nahazo 000 s. Be ve sa kely? Inona no azontsika atao mandritra io fotoana io?
Manana fotoana hamakiana 800 megabytes isika, tsy matrix transposed io, fa ilay tany am-boalohany. Ary koa mamaky sy manoratra 1,6 GB, ity dia efa matrix transposed. Ny processeur dia manao famakiana fanampiny alohan'ny hanoratana mba hanombohana ny angona ao anaty cache.
Andeha hokajintsika hoe ohatrinona ny bandwidth nampiasainay tamin'ny tombony. Hita fa 1,7 GB / s ny fatran'ny code.
Kajy ara-teorika izany. Avy eo ianao dia afaka maka profiler izay afaka mandrefy ny hafainganam-pandehan'ny miasa amin'ny fahatsiarovana. Naka VTune aho. Andeha hojerentsika izay asehony. Mampiseho tarehimarika mitovy - 1,8 GB. Amin'ny ankapobeny dia mifanaraka tsara izany, satria tamin'ny kajy nataonay dia tsy nihevitra izahay fa tsy maintsy mamaky ny adiresy andalana sy ny adiresy tsanganana. Fanampin'izany, ny VTune dia misoratra anarana amin'ny rafitra fiasana. Noho izany, ny modely ataontsika dia mifanaraka amin'ny zava-misy.
Mba hahatakarana raha be na kely ny 1,7 GB dia mila fantarinao hoe ohatrinona ny bandwidth ambony indrindra azonay.
Mba hanaovana izany, dia mila mamaky ny specs amin'ny processeur. Misy tranokala manokana ark.intel.com izay ahafahanao mahita ny zava-drehetra momba ny processeur rehetra. Raha mijery manokana ny mpizara isika dia hitantsika fa manana cores valo izy ary ho an'ny fahatsiarovana DDR3 haingana indrindra tohanany, dia mamindra amin'ny 60 GB / s amin'ny lalana iray.
Fa eto isika dia tsy maintsy mandinika fa tsy mampiasa afa-tsy fototra iray isika ary miadana kokoa ny fitadidiantsika, izany hoe mila manenjana ireo 60 GB ireo amin'ny toe-javatra misy antsika isika mifanaraka amin'ny isan'ny cores sy ny faharetan'ny fahatsiarovana.
Hita fa afaka mampiasa 5,3 GB ny kaodinay amin'ny fomba iray. Ary satria afaka mamaky sy manoratra amin'ny parallèle ianao, dia ny tsara indrindra, raha toa ka mandika ny angona avy amin'ny toerana mankany amin'ny toerana isika dia hahatratra 10,6. Koa satria manana vakiteny roa isika ary manoratra iray dia tokony ho 8 GB / s izany. Tsarovy fa nahazo 1,7 izahay. Izany hoe, manodidina ny 20% no nampiasanay tany ho any.
Nahoana no toy izany? Averina indray, mila miatrika ny maritrano ianao. Ny zava-misy dia ny angon-drakitra eo anelanelan'ny fahatsiarovana sy ny cache dia tsy afindra amin'ny fonosana tsy misy dikany, fa amin'ny 64 bytes marina, tsy mihoatra, tsy latsaky. Ity no fiheverana voalohany.
Ny fiheverana faharoa dia ny manoratra ny angon-drakitra navadika tsy misesy, fa kisendrasendra, satria ny andalana amin'ny matrix dia hita ao amin'ny fitadidiana amin'ny fomba tsy ampoizina.
Hita fa alohan'ny hanoratana isa tena izy dia tsy maintsy esorina ny angona 64 bytes. Raha manondro ny haben'ny matrix N, fa raha tokony ho ny fotoana tsara indrindra miasa (N / 5,3 + N / 10,6), dia mahazo (8 * N / 5,3 + N / 10,6). Any amin'ny toerana efatra ka hatramin'ny dimy heny, izay manazava io fahombiazan'ny 20%.
Inona no hatao amin'izany? Mila atsahatra ny fanoratana angona amin'ny tsanganana iray ianao ary manomboka manoratra tsanganana maro araka izay mety amin'ny andalana cache iray (64 bytes). Mba hanaovana izany, dia mizara ny tsingerina amin'ny tsanganana ho tsingerina eo amin'ny tsipika cache sy ny tadivavarana miompana amin'ny singa tsipika cache.
Eto izy ireo, famerimberenana amin'ny andalana cache.
Ary eto izy ireo, famerimberenana ao anatin'ny tsipika cache. Eto, ho an'ny fahatsorana, dia heverinay fa ny angon-drakitra dia mifanaraka amin'ny sisin'ny tsipika cache. Andeha hojerentsika amin'ny VTune izay mitranga.
Hitantsika izay nitranga teo akaikin'ny kajy valo gigabytes isan-tsegondra - 7,6. Saingy tsy mbola zava-misy fa ireo 7,6 rehetra ireo dia asa mahasoa. Angamba ny sasany amin'izy ireo dia ambony.
Mba hahatakarana ny tombotsoa azonay dia andao refesina ny fotoana fandehanana aorian'ny fanatsarana. Mipoitra 0,5 s amin'ny milina iray ihany. Ny throughput, izay kasaina amin'ny transposition mihitsy, dia lasa 4,8 GB / s. Hita taratra fa mbola misy margin tsy nofidiantsika, na izany aza, nahazo 20 isan-jato tamin’ny fahombiazana 60 isan-jato.
Miaraka amin'ny fanampian'ny profiler dia azonao fantarina ny antony tsy nahazoanay 80% na 95%.
Ny zava-misy dia mitahiry matrices ho toy ny véctor vectors isika, izany hoe mampiasa fidirana amin'ny fitadidiana miaraka amin'ny indirection roa.
Miaraka amin'ny VTune, azonao atao ny mahita izay torolalana novokarina mba hidirana amin'ny singa array. Asongadina amin'ny loko mavo eo ankavia ny toromarika manaisotra ny adiresin'ny tsanganana amin'ny matrix navadika. Ary ireo, voalohany, toromarika fanampiny, ary faharoa, famindrana angon-drakitra fanampiny. Saingy tsy hanao optimizer bebe kokoa izahay fa hijanona ary hamintina.
Inona no nolazaiko taminao androany? Ny toro-hevitra mahasoa amin'ny fiasana amin'ny kaody kajy dia ny fanodinana amin'ny blocs, amin'ny fandoavana ny saran'ny overhead izay mifandray, ohatra, amin'ny antso virtoaly. Fanampin'izany, noho ny fanakanana dia mihatsara ny toerana misy ny angona, ary mahazo hafainganam-pandeha ambony kokoa izahay.
Ny fanesorana ny famatsiam-bola amin'ny tavoahangy dia ny fitotongan'izy ireo ihany koa. Ary koa ny fampitomboana ny hafainganam-pandeha amin'ny alàlan'ny fanamboarana ireo buffer vonjimaika ao amin'ny fitadidiana.
Momba ny profiling. Voalohany, ny profiling dia teknika ilaina amin'ny fitadiavana bottlenecks "amin'ny tranga ankapobeny." Faharoa, ahafahantsika manombatombana ny fahombiazan'ny kaody, manapa-kevitra raha afa-po amin'ny hafainganam-pandeha na te hanatsara bebe kokoa, ary mampiseho ny lalana tokony haleha.
Izay ihany no ahy. Raha mampiasa CatBoost ianao na sambany vao nahare momba izany ary te hahafantatra hoe inona izany, dia vakio tongava mitsidika anay , manorata amin'ny . Misaotra indrindra amin'ny fifantohana.
Source: www.habr.com
