Mis mõjutab C++ programmidest sõltuvat töökiirus ja kuidas saavutada seda kõrge kooditaseme juures? CatBoosti raamatukogu juhtiv arendaja Jevgeni Petrov vastas nendele küsimustele CatBoosti x86_64 arenduse näidete ja illustreerimise kaudu.
Ettekande video
— Tere kõigile. Tegelema optimeerimisega CatBoosti masinaõppe raamatukogus CPU jaoks. Enamik meie raamatukogust on kirjutatud C++ keeles. Täna räägin lihtsatest viisidest, kuidas saavutame kiirus.
Arvutuste kiirus koosneb kahest osast. Esimene osa on algoritm. Kui me teeme valiku algoritmi osas vale, siis ei saa me seda hiljem kiiresti tööle panna. Teine osa on see, kui hästi on meie algoritm optimeeritud arvutisüsteemile, mis meil on, koos selle jõudluse ja läbilaskevõimega.
Andmevahetuse ja arvutuste eraldi arvestamine tuleneb nende kiirusvahe suurest erinevusest. Kui võtta mälu kiirus jalakäija kiirusena, siis arvutuste kiirus on umbes reisilennuki kruiisikiirus.
Selle erinevuse tasandamiseks on arhitektuuris mitmeid vahemälu tasemeid. Kiireim ja väikseim on L1-vahemälu. Seejärel on suurem ja aeglasem teise taseme vahemälu. Ja on ka täielikult suur vahemälu, mis võib ulatuda kümnete megabaitideni, kolmanda taseme vahemälu, kuid see on kõige aeglasem.
Kuna andmeedastuskiirus varieerub, jaguneb arvutuslik kood kaheks klassiks. Üks klass on piiratud läbilaskevõimega, st andmeedastuskiirus. Teine klass on piiratud protsessori töökiirusest. Piir nende vahel seab, sõltuvalt operatsioonide arvust, mis viiakse läbi ühe andmabytega. See on tavaliselt konkreetse koodi jaoks konstant.
Enamik raskest arvutuslikust koodist on ammu kirjutatud, väga hästi optimeeritud ning olemas on suur hulk raamatukogusid, seega on mõistlik, kui näete oma koodis raskesti arvutusi, otsida raamatukogu, mis võiks need teie eest teha.
Kuna allesjäänud kompilaatorid ei tarvitse kõike, sest nende arendamiseks kulutatakse väga piiratud protsent ressursse. Millised neist on täna enam-vähem aktiivsed, st toetavad standardeid ja püüavad nende jälgimisega tegeleda? See on frontend EDG, mida kasutatakse erinevates variatsioonides, näiteks Intel'i kompilaator; LLVM; GNU ja Microsofti frontend.
Kuna neid on vähe, toetavad kompilaatorid vaid sagedusmustrid juhtimise ja andmete sõltuvuse osas. Kui vaatame juhitavust, siis need on lineaarsed lõigud ja lihtsad tsüklid, st soovituste järjestus ja kordamine. Sagedusandmete sõltuvusi saavad nad tuvastada vähendamise teel, kui me näiteks liidame palju elemente üheks, kokkuvõtteks ja teeme elemendi-põhiseid toiminguid ühe või mitme massiiviga.
Mis jääb arendajatele? Seda võib tinglikult jagada neljaks osaks. Esimene on rakenduse arhitektuur, kompilaatorid lihtsalt ei suuda seda meie eest välja mõelda.
Paralleelisus on ka kompilaatorite jaoks keeruline teema. Mäluga töötamine on tõeliselt keeruline: tuleb arvesse võtta nii arhitektuuri kui ka paralleelisust ning kõike koos. Peale selle ei oska kompilaatorid õigesti hinnata optimeerimise kvaliteeti, kui kiireks kood muutub. Selle otsuse peame langetama meie, arendajad — kas optimeerida veel või lõpetada.
Arhitektuuri osas vaatame üle kulude amorteerimise, virtuaalsed kutsed, millele arhitektuur paljuski toetub.
Paralleelisuse jätame kõrvale. Mälukasutuse osas: see on ka mingis mõttes amorteerimine ja andmetega õigesti töötamine, nende õige paigutamine mällu. Tõhususe hindamise osas räägime profiilimisest ja sellest, kuidas leida koodis kitsaskohti.
Liideste ja abstraktsete andmetüüpide kasutamine on üks peamisi projekteerimismeetodeid. Vaatame sarnast arvutuslikku koodi masinõppest. See on tingimuslik kood, mis värskendab prognoosi gradientmeetodi kaudu.
Kui vaadata veidi sisse ja püüda mõista, mis seal toimub, siis meil on IDerCalcer liides, et arvutada kaotusfunktsiooni derivatiive ja funktsioon, mis nihutab prognoosi (meie ennustust) vastavalt kaotusfunktsiooni gradientidele.
Paremal slaidil näete, mida see tähendab kahemõõtmelises juhtumis. Masinõppes ei ole prognoosi suurus kaks või kolm, vaid miljoneid, kümneid miljoneid elemente. Vaatame, kui hea see kood on 10 miljoni elemendi vektori jaoks.
Võtame sihtfunktsiooniks keskmise ruutspoondi ja mõõdame, kui kiiresti see prognoosi nihutab. Selle sihtfunktsiooni derivaat on slaidil. Ajavahemik fikseeritud tingimustes, mis jääb edaspidi muutumatuks, on 40 ms.
Proovime aru saada, mis siin ikkagi valesti on. Esimene asi, mis silma torkab, on virtuaalsed kutsed. Profilatsiooni vaadates on näha, et sõltuvalt parameetrite arvust on see umbes viis kuni kümme käsku. Ja kui, nagu meie puhul, tuletamise arvutamine on vaid kaks aritmeetilist tehet, siis võib see kergesti osutuda märkimisväärseks ülejääkideks. Suure objekti korral tuletiste arvutamisel on see okei. Lühikese objekti puhul, mis tuletab — öeldes, isegi mitte 500 käsku, vaid 20, 50 või isegi vähem, — on see juba märkimisväärne protsent ajast. Mida siis teha? Proovime virtuaalse funktsiooni kutsumise amortiseerida, muutes liidese.
Alguses arvutasime tuletised punkt-punkt järgi, iga vektori elemendi kohta eraldi. Liigume elementide töötlemisest vektorite töötlemisele. Vaatame standardset C++ malli, mis võimaldab töötada vektori vaatega. Kui teie kompilaator ei toeta viimast standardit, siis võite kasutada lihtsat isetehtud klassi, kus hoitakse andmete pointerit ja suurust. Kuidas kood muutub? Meil jääb alles üks kutse, mis arvutab tuletised, ja siis peame lisama tsükli, mis tegelikult uuendab prognoosi.
Lisaks sellele, et lisandub tsükkel, peame me veel kord vaatama andmeid, st teist korda lugema prognooside vektorit ja gradiente, mille just arvutasime.
Katsume taas samal masinal ja näeme, et tulemus on halvenenud, midagi on valesti. Hakkame uurima, mis sünteesis juhtus.
Pole mõtet kahtlustada tsüklit, kuna see on just see sagedusmuster, mille kompilaatorid tuvastavad ja hästi optimeerivad. Andmete ühe elemendi operatsioone on seal vähem kui virtuaalse kutse hind.
Siin on koha, kus võiks kahtlustada probleemi, kui luuakse suur vektor ja sellele tehakse korduv läbimine. Et mõista, miks see on halb ja viib aeglustumiseni, peaksime ette kujutama, mis toimub mälus, kui töötab kood, mida näeme paremal slaidil.
Kui tuletatakse derivatiivide vektor, jõuab asi tsüklisse, mis nihutab prognoosi. Enne seda tsüklit jääb kiircache'i esimese taseme, mis töötab protsessori sagedusel, ainult väga väike osa andmetest. Slaidil on see rohelise värviga valgusfooris. Ülejäänud andmed tõugatakse cache'ist välja mällu ja kui tsükkel hakkab prognoose uuendama, tuleb andmed teist korda lugeda mälust. Ja meie mälu töötab, üldiselt, üsna aeglaselt, jalakäija kiirusest.
Kui me prognoose uuendame, ei ole meil tingimata vaja lugeda kõiki derivatiive korraga. Piisab neist lugemisest suurte pakkidena, et amortiseerida virtuaalseid kutsunge. Seetõttu on mõistlik jagada derivatiivide arvutamine ja prognoosi uuendamine väikesteks plokkideks ning segada neid kahte toimingut. Kuhu see viib, kui vaatame, kust andmed loetakse?
See to, et me kogu aeg andmeid võtame, ja et andmed jäävad L1-vahemälusse ega jõua aeglasesse mällu. Edasi peame aru saama, kes siis ütleb meile selle ploki suuruse.
On loogiline usaldada see ülesanne diferentseerimise arvutajale, kuna ainult tema teab, kui palju vahemälu tal on vaja. Edasi tuleb ümber kirjutada tsükkel, mis meil massiivi läbi vaatas. Tuleb jagada see kaheks. Väline tsükkel läheb plokkide kaupa, samal ajal kui sees kaks korda läheme ploki elemente läbi.
Siin on, väline plokkide kaupa.
Ja siin on seesmine plokkide elementide kaupa.
Me arvestame, et viimane plokk võib olla mittetäielik.
Vaatame, mis sellest välja tuleb. Näeme, et me arvasime õigesti, mõistsime, mis asi on, ja üsna väikeste muudatuste hinnaga vähendasime töötamise aega kaheksa protsendi võrra. Kuid me saame veel rohkem teha. Tuleb veel kord kriitiliselt vaadata sellele, mis me kirjutasime. Vaadata funktsiooni, mis arvutab meile tuletisi. See tagastab meile tuletiste vektori, millele ligipääs, ebasoodsates olukordades, on aeglane.
Siin on kaks põhjust. Esiteks, vektori asukoht „virnas“. Suur osa tõenäosusest on, et see vektor luuakse ja hävitatakse mitu korda. Teine kiiruselanguse probleem on see, et iga kord saame mälu ilmselt uuel aadressil. See mälu on „külm“ vahemälu seisukohalt, see tähendab, et enne selle kirjutamist peab protsessor tõenäoliselt tegema abitegevuse lugemist, et andmed vahemälus initsialiseerida.
Selle parandamiseks tuleb eraldamine tsüklist välja viia. Selleks peame veelkord liidest muutma, lõpetama vektoreid tagastamise ja hakkama tuletisi mälu salvestama, mille saame kutsuva koodi käest.
See on standardlahendus — kõik ressursside manipuleerimised tuleb välja viia kitsaskohtadest arvutuslikus koodis. Lisame CalcDer meetodile veel ühe parameetri, viidates vektorile, kuhu tuletised peavad sattuma.
Kood muutub ka ilmselgelt. Tuletiste vektor saab olema üks, väljaspool kõiki silmusid, ja meetodile lisandub lihtsalt uus parameeter.
Vaatame. Tundub, et võitsime eelnevaga võrreldes veel kuskil kaheksa protsenti, ja põhipunktiga võrreldes — juba 15%.
On selge, et optimeerimine ei piirdu ainult kulude amordiga, kitsaskohad võivad olla ka teistsuguseid.
Kitsaskohtade otsimise illustreerimiseks vajame veel ühte lihtsat katsekoodi. Näiteks võtsin maatriksi transpositsiooni. Meil on maatriks approx ja maatriks approxByCol, kuhu peame paigutama transpositsioonitud andmed. Ja lihtne pesa kahest tsüklist. Siin pole mingeid virtuaalseid kutsungite, vektorite loomist. See on lihtsalt andmete ümberpaigutamine. Tsükkel on kompilaatorile suhteliselt mugav.
Mõõdame, kuidas see kood töötab piisavalt suure maatriksi ja konkreetse masinaga.
Näiteks valisin ma 1000 rida ja 100 000 veergu. Masin on Intel server, ühesüdamikuline. Mälumaa on selline, see on meile oluline, sest kogu mäluga seotud töö ja kiirus sõltuvad mälutöötamise kiirest. Määrasime ja saime 1,4 s. Kas see on palju või vähe? Mida me selle ajaga ära teeme?
Me jõuame lugeda 800 megabaiti, see ei ole transponeeritud maatriks, vaid algne. Samuti suudame lugeda ja kirjutada 1,6 GB, see on juba transponeeritud maatriks. Protsessor sooritab abistava lugemise enne kirjutamist, et andmed vahemälus initsialiseerida.
Arvutame, kui palju läbilaskevust oleme kasulikult kasutanud. Meie koodi läbilaskvus on 1,7 GB/s.
See oli teoreetiline arvutus. Järgmise sammuna võime kasutada profiilerit, mis on võimeline mõõtma mälu kasutamise kiirus. Kasutasin VTune'i. Vaatame, mida ta näitab. Tulemuseks on sarnane number — 1,8 GB. Ükski see ei ole halb, sest meie arvutuses ei olnud arvesse võetud, et tuleb lugeda ridu ja veergude aadresse. Lisaks registreerib VTune ka operatsioonisüsteemi taustategevuse. Seega on meie mudel kooskõlas tegelikkusega.
Kuna 1,7 GB on palju või vähe, tuleb välja selgitada, milline on meie maksimaalne ligipääsetav läbilaskvus.
Selleks tuleb lugeda protsessori spetsifikatsioone. Loodus võib kõik üksikasjad leida spetsiaalselt veebilehelt ark.intel.com. Kui vaatame konkreetselt meie serverit, siis näeme, et sellel on kaheksa tuuma ning kiireim DDR3 mälu, mida ta toetab, tagab andmete edastamise kiirusena umbes 60 GB/s ühes suunas.
Kuid peab arvestama, et kasutame ainult ühte tuuma ja meie mälu on aeglasem, seega tuleb neid 60 GB meie tingimustes proportsionaalselt tuumade arvu ja mälufrektsiooniga skaleerida.
Tulemuseks on, et meie kood võiks kasutada 5,3 GB ühes suunas. Kuna samaaegselt saab lugeda ja kirjutada, siis ideaaljuhul, kui me lihtsalt kopeeriksime andmeid ühest kohast teise, saavutaksime 10,6. Arvestades, et meil on kaks lugemist ja üks kirjutamine, peaks olema umbes 8 GB/s. Meie tulemus on 1,7. See tähendab, et oleme kasutanud umbes 20%.
Kuidas see nii kujuneb? Taas tuleb vaatama hakata arhitektuuri. Asjaolu on see, et andmed edastatakse mälu ja vahemälu vahel mitte suvaliste paketidena, vaid täpselt 64 байтовä. See on esimene mõte.
Teine kaalumise aspekt: me salvestame transponeeritud andmeid mitte järjest, vaid suvaliselt, kuna maatriksi read asuvad mälus ettearvamatul viisil.
Selgub, et enne ühe reaalarvu salvestamist peame lugema 64 baidi andmeid. Kui määrata maatriksi suurus N, siis optimaalse tööaja (N/5,3 + N/10,6) asemel saame (8*N/5,3 + N/10,6). See on kuskil neli-viis korda rohkem, mis seletab 20% efektiivsust.
Mida sellega teha? Tuleb lõpetada andmete salvestamine ühiselt ühte veergu ja alustada salvestamist nii palju veerge kui mahub ühte vahemäluliini (64 baidi). Selleks jagame veergude tsükli vahemäluliinide tsükliks ja sisemise tsükliks vahemäluliini elementide jaoks.
Siin nad on, vahemäluliinide iteratsioonid.
Ja siin nad on, iteratsioonid vahemäluliinis. Siin arvame lihtsuse huvides, et andmed on joondatud vahemäluliini piirile. Nüüd kontrollime VTune'i abil, mis juhtub.
Näeme, et saavutame ligikaudu arvutatud kaheksa gigabaiti sekundis — 7,6. Kuid pole veel kindel, et kõik need 7,6 on kasulik töö. Võib-olla osa neist on lisakulud.
Kuna mõista, kui palju kasu me saavutasime, mõõdame tööaega pärast optimeerimist. See on 0,5 s samal masinal. Läbivus, mis on seotud transpoonimisega, tõusis 4,8 GB/s. On selgelt näha, et meil on veel reservi, mida me ei kasutanud, kuid hoolimata sellest, saime 20-protsendilisest efektiivsusest 60-protsendilise.
Profilers võivad aidata mõista, miks me ei saavutanud 80% või 95%.
Probleem on selles, et me hoiame maatrikseid vektorite vektorina, st kasutame mälule juurdepääsu kahekordse tasemega.
VTune abil on näha, millised käsklused on genereeritud massiivi elementide juurde pääsemiseks. Vasakul on kollase värvusega esile tõstetud käsklused, mis loevad transpoonitud maatriksi veergude aadresse. Esmalt on need lisakäsklused ja teiseks lisanduvad andmeedastused. Aga suurematel optimiseerimistööl me ei peatu, lõpetame ja teeme kokkuvõtte.
Mille tänapäeval rääkisin? Kasulik nõuanne arvutuskoodeksiga töötamiseks on töötlemine plokkidena, et maandada kulusid, mis on seotud näiteks virtuaalsete kutsetega. Plokkide kasutamine parandab ka andmete lokaliteeti, pakkudes meile kõrgemat ligipääsu kiirus.
Allocatsioonide eemaldamine kitsaskohtadest on samuti nende amortiseerimine. See suurendab ligipääsu kiirus, lukustades ajutised puhvered mälus.
Profiilimise osas. Esiteks on profiilimine kasulik meetod tuvastada kitsaskohad 'üldiselt'. Teiseks võimaldab see hinnata koodi efektiivsust, otsustada, kas oleme kiirusest rahul või soovime rohkem optimeerida, ning näitab, millises suunas liikuda.
Sellega olen lõpetanud. Kui kasutate CatBoosti või kuulete sellest esmakordselt ja soovite teada, mis see on, – lugege , tulge meie juurde , kirjutage meile . Suur tänu tähelepanu eest.
Allikas: habr.com
