Många moderna tillämpningar (t.ex. multimediabehandling, maskininlärning och stordataanalys) uppvisar en inneboende avvägning mellan prestanda och noggrannheten hos de producerade resultaten. Dessa applikationer tillåter oss att undersöka nya, mer aggressiva programoptimeringar. Vi presenterar en ny approximativ optimeringsram baserad på precisionsmedvetna programomvandlingar. Dessa omvandlingar minskar beräkningsnoggrannheten i utbyte mot förbättrad prestanda, energieffektivitet och/eller motståndskraft. Optimeringsramverket innehåller programanalyser som karakteriserar exaktheten hos transformerade program, och söktekniker som navigerar det kompromissutrymme som orsakas av transformationer för att hitta ungefärliga program med lönsamma kompromisser. Vår forskning visar att detta tillvägagångssätt kan avsevärt förbättra programmets prestanda samtidigt som det ger acceptabelt korrekta resultat. Traditionellt har utvecklare av ungefärliga applikationer manuellt konstruerat algoritmer som kan handla noggrannhet av programmets resultat för minskad genomförandetid eller energiförbrukning. På senare tid har forskare börjat utforska kompletterande system-nivå approximation metoder som öppnar nya punkter i den underliggande noggrannhet kontra prestanda tradeoff utrymme. Detta omfattar ungefärliga hårdvarukomponenter (t.ex. ungefärliga acceleratorer, ALU eller minnen, t.ex. [6, 7, 10, 11, 17] ) och programmeringssystem (t.ex. språk, kontrollsystem, körtidssystem och kompilatorer, t.ex. [1–4, 8, 18, 21, 22]). Accuracy-aware program transformationer är kompilator-nivå optimeringar som automatiskt genererar ungefärliga versioner av program. De avviker därför från det traditionella tillvägagångssättet till programoptimering där omvandlingarna alltid bevarar programsemantik. Prestandaorienterade transformationer minskar mängden arbete som ett program gör [5, 8, 12, 14, 16, 19, 21, 23, 24]. Till exempel kan loopperforering [16, 23] instruera en loop av formen för (int i = 0; i < n; i++) {...} att utföra färre iterationer. För att endast utföra hälften av loopens iterationer kan loopperforering ändra induktionsvariabelt steg från i++ till i+=2. Energiorienterade omvandlingar instruerar ett program för att använda hårdvarukomponenter som aggressivt sparar energi genom att tillåta fel i sina resultat [4, 13, 22]. Resiliensorienterade omvandlingar gör det möjligt för ett program att fortsätta genomförandet efter annars dödliga fel och producera åtminstone en del av det ursprungliga resultatet [9, 20]. Automatiskt optimera ungefärliga program med hjälp av precisionsmedvetna transformationer ger en ny möjlighet att minska teknisk ansträngning och resursförbrukning och öka programmets motståndskraft. Men, denna möjlighet kommer till ett pris, eftersom omvandlingarna inför osäkerhet i programmets utförande och de resultat den producerar. Denna framväxande osäkerhet väcker ett antal nya forskningsfrågor, inklusive 1) hur man identifierar delar av ett program som är bra kandidater för precisionsmedvetna transformationer; 2) hur man karakteriserar effekterna av en transformation på programmets utförande, särskilt resultatets noggrannhet; och 3) hur man automatiskt upptäcker transformationer som ger maximala prestandavinster för godtagbara noggrannhetsförluster. För att möta dessa utmaningar presenterar vår forskning två konceptuella metoder för programanalys och optimering: Testing-Based Approach. För att hitta lönsamma kompromisser, dessa tekniker först generera ett transformerat program och sedan dynamiskt validera att dess utföranden uppfyller utvecklarens noggrannhetskrav [8, 14, 16, 23]. Vanligtvis, valideringsförfarandena kör det transformerade programmet på en uppsättning utvecklare-tillhandahållna representativa ingångar, jämföra noggrannheten av resultaten med den som produceras av det ursprungliga programmet, och kontrollera om exekvationerna uppvisade några oönskade beteende via dynamisk analys (och eventuellt lätt statisk analys). Även om sådana tekniker fungerar för godtyckliga program och effektivt kan navigera kompromissutrymmet, ger de inte garantier för programmets beteende bortom de testade representativa indata. Analysbaserad metod. För att hitta lönsamma kompromisser, dessa tekniker använder statiska programanalys för att minska problemet med att tillämpa noggrannhet-medvetna program transformationer till standard numeriska optimeringsproblem [13, 15, 24]. Specifikt börjar optimeringsramen med att utföra probabilistisk statisk analys som kvantifierar sannolikheten för oacceptabla produktionsavvikelser orsakade av kandidatomvandlingar. De uttryck som genereras av den statiska analysen utgör begränsningarna i det numeriska optimeringsproblemet. Programanalys ger också en uppskattning av prestanda/energibesparingar, vilket utgör optimeringsproblemets objektiva funktion. Ramen kan sedan avkalla en off-the-shelf lösare för att hitta den uppsättning omvandlingar som ska tillämpas. I motsats till det testbaserade tillvägagångssättet kan det analysbaserade tillvägagångssättet ge garantier för alla relevanta indata (och inte bara de testade indata) och kan utforska mer komplexa avräkningsytor. För närvarande kan den dock endast ge garantier för de beräkningar som har en specifik struktur (t.ex. beräkningar med statiskt avgränsade slingor eller sekvenser av kartor och minska operatörerna). Tillsammans lägger dessa metoder grunden för programoptimering med precisionsmedvetna transformationer. Medan noggrannhetsoptimering avgår från den traditionella synen att omvandlingar måste bevara program semantik, har det visat att det kan avsevärt förbättra prestanda och energieffektivitet av ungefärliga program samtidigt som utvecklarens noggrannhetskrav. Tackar. Forskningen om exakthet-medvetna transformationer är resultatet av många forskares grupparbete, inklusive viktiga bidrag från
De föreslår också kompilator-nivå, noggrannhet-medvetna transformationer som automatiskt genererar ungefärliga versioner av program REF.
Accuracy-aware optimization of approximate programs
{'venue': "CASES '15", 'journal': None, 'mag_field_of_study': ['Computer Science']}