Krafthantering och konkurrenskraft Problemsättning: I ett allmänt scenario får vi en anordning som alltid finns i en av flera stater. I översiktsartiklar utöver det aktiva tillståndet kan det till exempel finnas standby-, suspensions-, sömn- och full-off-tillstånd. Dessa stater har individuella strömförbrukningsnivåer. Den energi som uppstår vid övergången från en högre makt till ett lägre makttillstånd är vanligtvis försumbar. En uppströmsdrift förbrukar dock en betydande mängd energi. Med tiden upplever enheten en alternerande sekvens av aktiva och inaktiva perioder. Under aktiva perioder måste systemet vistas i aktivt läge för att utföra de uppgifter som krävs. Under inaktiva perioder kan systemet flyttas till lägre effekttillstånd. En algoritm måste bestämma när övergången ska utföras och till vilka stater den ska flyttas. Målet är att minimera den totala energiförbrukningen. Eftersom energiförbrukningen under de aktiva perioderna är fast, förutsatt att föreskrivna uppgifter måste utföras, fokuserar vi på energiminimering i de inaktiva intervallerna. I själva verket fokuserar vi på alla sysslolösa perioder och optimerar energiförbrukningen i alla sådana tidsramar. Detta power management problem är ett online problem, det vill säga när som helst en enhet inte är medveten om framtida händelser. Mer specifikt, i en sysslolös period, systemet har ingen information när perioden slutar. Är det värt att flytta till en lägre makt och dra nytta av den minskade energiförbrukningen, med tanke på att systemet äntligen måste drivas upp igen till en kostnad för det aktiva läget? Prestandaanalys: Trots att det är svårt att inte känna till framtiden, bör en onlinestrategi uppnå ett tydligt bra resultat. Här använder sig algoritmerna av konkurrensanalys, där en online-algoritm ALG jämförs med en optimal offline-algoritm OPT. 38 OPT är en allvetande strategi som känner till hela framtiden och kan beräkna en statlig övergångsplan för minsta totala energi. Online-algoritm ALG kallas c-konkurrenskraft om för varje ingång, t.ex. för varje tomgångsperiod, den totala energiförbrukningen för ALG är högst c gånger den för OPT. Konkurrenskraftig analys ger en stark prestandagaranti i värsta fall. En online-strategi måste fungera bra på alla ingångar (idle perioder) som till och med kan genereras av en motståndare. Detta kontradiktoriska scenario kan verka pessimistiskt men det är förenligt med klassisk algoritmanalys som utvärderar strategier i termer av deras värsta-fall resurser, typiskt körtid eller minne krav. I detta avsnitt kommer vi främst att studera algoritmer med hjälp av konkurrensanalys men kommer också att överväga prestanda på indata som genereras enligt sannolikhetsfördelningar. I det följande kommer vi först att studera system som endast består av två stater. Då kommer vi att ta itu med system med flera stater. Vi betonar att vi överväger att minimera energin. Vi bortser från den försening som uppstår när ett system övergår från en lägre makt till ett högre makttillstånd. Överväga ett tvåstatssystem som kan vistas i ett aktivt tillstånd eller i ett viloläge. Låt r vara strömförbrukningen, mätt i energienheter per tidsenhet, i aktivt tillstånd. Energiförbrukningen i viloläge antas vara 0. Resultaten vi presenterar i följande generalisera till en godtycklig konsumtion i viloläge. Låt b energienheter, där b > 0, krävas för att omvandla systemet från vilotillståndet till det aktiva tillståndet. Vi antar att energin i övergången från det aktiva till sömntillståndet är 0. Om så inte är fallet kan vi helt enkelt vika den motsvarande energin till kostnaden b som uppstår i nästa power-up drift. Systemet upplever en tomgångsperiod vars längd T till en början är okänd. En optimal offline-algoritm OPT, som känner till T i förväg, är enkel att formulera. Vi jämför värdet av rT, vilket är den totala energi som förbrukas under tomgången när du bor i det aktiva läget, med power-up kostnaden för b. Om rT < b, förblir OPT i aktivt tillstånd under hela den inaktiva perioden eftersom övergången mellan de aktiva och vilolägen kostar mer. Om rT 3 b, med hjälp av viloläge är fördelaktigt. I detta fall övergår OPT till sömntillståndet redan i början av den tomgångsperiod och krafter fram till den aktiva staten i slutet av perioden. Följande deterministiska online-algoritm efterliknar beteendet hos OPT, som använder viloläge på tomgång perioder av längd minst b/r. Energin har blivit en ledande konstruktionsbegränsning för datorutrustning. maskinvaruingenjörer och systemdesigners utforskar nya riktningar för att minska energiförbrukningen av sina produkter. Överväga ett system med l stater s 1,..., s l. Låta r i vara strömförbrukning av s i. Vi numrerar staterna i ordning av minskande hastigheter, såsom r 1 >... > r l. Därför är s 1 den aktiva staten och s l representerar staten med lägsta energiförbrukning. Låt b i vara den energi som krävs för att övergången systemet från s i till det aktiva tillståndet s 1. Eftersom övergångar från lägre makt stater är dyrare har vi b 1 £... £ b l. Dessutom naturligtvis b 1 = 0. Vi antar återigen att övergångar från högre makt till lägre makt stater ådrar sig 0 kostnad eftersom motsvarande energi är vanligtvis försumbar. Målet är att skapa ett övergångsschema som minimerar den totala energiförbrukningen under en tomgång. Irani m.fl. 24 presenterade online och offline algoritmer. De antar att övergångsenergierna är additiva, såsom, övergång från en lägre makt tillstånd s j till en högre makt tillstånd s i, där i < j, ådrar sig en kostnad av b j − b i. En algoritm aLG-d: I en tomgångsperiod återstår först i det aktiva tillståndet. Efter b/r tidsenheter, om perioden ännu inte har avslutats, övergång till vilotillstånd. Det är lätt att bevisa att ALG-D är 2-konkurrenskraftigt. Vi behöver bara överväga två fall. Om rT < b, förbrukar ALG-D rT-enheter energi under tomgångsintervallet och detta är i själva verket lika med förbrukningen av OPT. Om rT 3 b, då ALG-D först förbrukar r. b/r = b energienheter för att förbli i aktivt tillstånd. En extra power-up-kostnad på b uppstår vid slutet av tomgångsintervallet. Därför är ALG-D:s totala kostnad 2b, medan OPT ådrar sig en kostnad på b för uppeffektdriften vid slutet av tomgångsperioden. Det är också lätt att verifiera att ingen deterministisk online-algoritm kan uppnå ett konkurrensförhållande mindre än 2. Om en algoritm övergår till vilotillståndet efter exakt t-tidsenheter, då i en tomgång period av längd t det ådrar sig en kostnad av tr + b medan OPT betalar min{rt, b} endast. Vi konstaterar att maktstyrning i tvåstatssystem motsvarar det berömda problemet med skidhyra, ett grundläggande problem i teorin om online-algoritmer, se till exempel Irani och Karlin. 26 Intressant nog är det möjligt att slå konkurrenskraften av 2 med hjälp av randomisering. En randomiserad algoritm övergår till vilotillståndet enligt en sannolikhetsdensitetsfunktion p(t). Sannolikheten för att systemet slår ner under de första t 0-tidsenheterna under en tomgångsperiod är ò 0 t 0 p(t)dt. Karlin m.fl. 28 bestämde den bästa sannolikhetsfördelningen. Den densitet funktion är den exponentiella funktionen e rt/b, multiplicerad med faktorn för att säkerställa att p(t) integrerad över hela tidshorisonten är 1, det vill säga, systemet är definitivt drivs ner någon gång. Algoritm alLG-r: Övergång till viloläge enligt sannolikhetstäthetsfunktionen ALG-R uppnår en avsevärt förbättrad konkurrenskraft, jämfört med deterministiska strategier. Resultat av Karlin et al. 28 innebär att ALG-R uppnår ett konkurrenskraftigt förhållande, Där e » 2.71 är det eulerska numret. Mer exakt är den förväntade energiförbrukningen för ALG-R inte mer än gånger den för OPT under någon tomgångsperiod. Återigen, är det bästa konkurrensförhållandet en randomiserad strategi kan få. Ur praktisk synvinkel är det också lärorikt att studera stokastiska inställningar där längden på tomgångsperioder styrs av sannolikhetsfördelningar. I praktiken kan korta perioder förekomma oftare. Sannolikhetsfördelning kan också modellera specifika situationer där antingen mycket korta eller mycket långa tomgångsperioder är mer benägna att inträffa, jämfört med perioder med medellång längd. Naturligtvis är en sådan sannolikhetsfördelning kanske inte känd i förväg men kan läras med tiden. I det följande antar vi att distributionen är känd. Låt Q = (q(T) ) 0£T <∞ vara en fast sannolikhetsfördelning på längden T av tomgångsperioder. För alla t 3 0, beakta den deterministiska algoritm ALG t som alltid driver ner efter exakt t tid enheter. Om tomgångsperioden slutar innan ALG t slår ner, t.ex. om T < t, förblir algoritmen i aktivt tillstånd under tomgångsintervallets varaktighet och använder en rT-energi. Om tomgångsperioden ännu inte har avslutats när ALG t slår ut, såsom, om T 3 t, då algoritmen ådrar sig en fast energi av rt + b eftersom en energi av rt förbrukas innan systemet i drivs ner och en kostnad b uppstår för övergången tillbaka till det aktiva läget. För att bestämma den förväntade kostnaden för ALG t, Vi måste integrera över alla möjligheter för längden T av overksam period med hjälp av sannolikhetsfördelningen Q. De två begreppen nedan representerar de två fallen. Observera att sannolikheten för att overksamhetsperioden ännu inte har avslutats när ALG t driver ner är (1) Karlin et al. 28 föreslog följande strategi som, med tanke på Q, helt enkelt använder den bästa algoritmen ALG t. algoritm alG-P: Med tanke på en fast Q, låt A Q * vara den deterministiska algoritm ALG t som minimerar ekvation 1. Karlin m.fl. visade att för alla Q, den förväntade energiförbrukningen av Intressant, för variabel T den optimala kostnaden har en enkel grafisk representation, se figur 1. Om vi anser att alla linjära funktioner f i (t) = r i t + b i, som representerar den totala energiförbrukningen med hjälp av tillstånd s i, då den optimala energiförbrukningen ges av den nedre delen av arrangemanget av linjer. Man kan använda denna lägre kuvert för att styra en online-algoritm för att välja vilket tillstånd som ska användas när som helst. Låt S OPT (t) betecknar det tillstånd som används av OPT i en tomgång period av total längd t, såsom, S OPT (t), det vill säga lösningen på ekvationen Här antar vi att stater vars funktioner inte förekommer på den lägre kuvert, när som helst, kastas. Vi noterar att algoritmen är en generalisering av ALG-D för tvåstatssystem. Irani m.fl. 24 bevisade att Lower-Envelope är 2-konkurrenskraftig. Detta är den bästa konkurrenskraften en deterministisk algoritm kan uppnå i godtyckliga statliga system. Irani m.fl. 24 studerade också den inställning där längden av tomgångsperioder genereras av en sannolikhetsfördelning Q = (q(T) ) 0£T <∞. De bestämmer tiden t i när en online-strategi bör gå från stat s i-1 till s i, 2 £ i £ l. I detta syfte överväga den deterministiska online-algoritm ALG t som övergår till lägre makt tillstånd efter exakt t tid enheter. Vi bestämmer den förväntade kostnaden för ALG t i en tomgång period vars längd T genereras enligt Q, förutsatt att endast tillstånd s i-1 och s i är tillgängliga. Till en början bor ALG t i staten s i−1. Om tomgångsperioden slutar innan ALG t övergår till lågeffekttillståndet, som t.ex. om T < t, är energiförbrukningen r i‐1 T. Om tomgångsperioden inte har avslutats ännu när ALG t övergår till lågeffekttillståndet, t.ex. om T 3 t, ådrar sig algoritmen en energi r i‐1 t medan den är bosatt i s i‐1 under de första t-tidenheterna och en ytterligare energi av r i (T − t) när den är i tillstånd i under de återstående T − t-tidsenheterna. Vid slutet av den tomgångsperiod, en power-up kostnad b i − b i‐1 betalas för övergången från s i tillbaka till s i‐1. Därför, i detta fall ALG t ådrar sig en total energi av r i‐1 t Den förväntade kostnaden för ALG t, förutsatt att endast s i‐1 och s i är tillgängliga, är Låta t i vara den tid t som minimerar ovanstående uttryck. Irani m.fl. 24 föreslog följande algoritm. Algoritm ALG-P(l): Ändra tillstånd vid övergångstiderna t 2,...,t l definieras ovan. ALG-P(l) är en generalisering av ALG-P för tvåstatssystem. Irani m.fl. bevisade att för varje fast sannolikhetsfördelning Q är den förväntade energiförbrukningen för ALG-P(l) inte mer än gånger den förväntade optimala förbrukningen. Dessutom Irani et al. presenterade en metod för att lära sig en till en början okänd Q. De kombinerade metoden med ALG-P(l) och utförde experimentella tester för en IBM mobil hårddisk med fyra power states. Det visar att det kombinerade systemet uppnår låg energiförbrukning nära den optimala och vanligtvis överträffar många enstaka värdeförutsägelsealgoritmer. Augustine m.fl. 5 undersöka generaliserade flerstatssystem där statsövergångsenergierna kan ta godtyckliga värden. Låt b ij 3 0 vara den energi som krävs för övergången från s i till s j, 1 £ i, j £ l. Augustine et al. visa att LowerEnvelope kan generaliseras och uppnå en konkurrenskraft på 3 + 2Ö2  på 5,8. Detta förhållande gäller för alla tillståndssystem. Bättre gränser är möjliga för specifika system. Augustine m.fl. Utforma en strategi som, för ett givet system S, uppnår ett konkurrensförhållande som är godtyckligt nära den bästa möjliga konkurrenskraften för S. Slutligen överväger författarna stokastiska inställningar och utvecklar optimala övergångstider. Många moderna mikroprocessorer kan köras med variabel hastighet. Exempel är Intel SpeedStep och AMD-processorn PowerNow. Höga hastigheter resulterar i högre prestanda men också hög energiförbrukning. Lägre hastigheter sparar energi men prestanda försämras. Den välkända kub-rot regel för CMOS-enheter anger att hastigheten s av en enhet är proportionell mot kub-roten av kraften eller, motsvarande, kraften är proportionell till s 3. Algoritmlitteraturen överväger en generalisering av denna regel. Om en processor körs i hastighet S, då den erforderliga effekten är s a, där en > 1 är en konstant. Det är uppenbart att energiförbrukningen är integrerad med tiden. Målet är att dynamiskt ställa in hastigheten på en processor för att minimera energiförbrukningen, samtidigt som den ger en önskad servicekvalitet. Dynamisk hastighetsskalning leder till många utmanande schemaläggningsproblem. När som helst måste en schemaläggare bestämma inte bara vilket jobb att utföra utan också vilken hastighet som ska användas. Följaktligen har det funnits ett stort forskningsintresse för utformning och analys av effektiva schemaläggningsalgoritmer. I detta avsnitt granskas de viktigaste resultaten från de senaste åren. Vi tar först upp schemaläggningsproblem med hårda jobbdeadlines. Sedan tänker vi på minimeringen av svarstider och andra mål. I allmänhet är två scenarier av intresse. I offline-inställningen är alla jobb som ska bearbetas kända i förväg. I online-miljö, jobb anländer över tid, och en algoritm, när som helst, måste fatta schemaläggning beslut utan kunskap om framtida jobb. Online-strategier utvärderas igen med hjälp av konkurrensanalys. Onlinealgoritm ALG är c-kompetitiv om, för varje insats, det objektiva funktionsvärdet (vanligtvis energiförbrukningen) för ALG ligger inom c gånger värdet av en optimal lösning. I en seminal tidning, initierar den algoritmiska studien av hastighetsskalning, Yao et al. 40 undersökte ett schemaläggningsproblem med strikta tidsgränser. Vid denna punkt är detta ramverk den överlägset mest studerade algoritmiska hastighetsskalning problem. Betrakta n jobb J 1,..., J n som måste bearbetas på en processor med variabel hastighet. Varje jobb J i anges av en release tid r i, en deadline d i, och en bearbetning volym w i. Frisläppningstiden och deadline markerar det tidsintervall under vilket jobbet måste utföras. Bearbetningsvolymen är den mängd arbete som måste göras för att slutföra arbetet. Intuitivt kan bearbetningsvolymen ses som antalet CPU cykler som krävs för att avsluta jobbet. Handläggningstiden för ett jobb beror på hastigheten. Om J i utförs med konstant hastighet s, det tar w i / s tid enheter för att slutföra jobbet. Företräde för arbetstillfällen är tillåtet, dvs. behandlingen av ett arbete kan avbrytas och återupptas senare. Målet är att skapa en genomförbar tidsplan som minimerar den totala energiförbrukningen. Ramverket av Yao et al. förutsätter att det inte finns någon övre gräns för den maximala processorns hastighet. Därför finns det alltid en genomförbar tidsplan som uppfyller alla tidsgränser. Dessutom antas ett kontinuerligt hastighetsspektrum finnas tillgängligt. Vi kommer senare att diskutera hur vi kan lätta på dessa antaganden. Grundläggande algoritmer: Yao et al. 40 först studera offline-inställningen och utveckla en algoritm för att beräkna optimala lösningar, minimera total energiförbrukning. Strategin kallas YDS som hänvisar till upphovsmännens initialer. Algoritmen fortsätter i en rad iterationer. I varje iteration identifieras ett tidsintervall med maximal densitet och ett motsvarande delschema konstrueras. Löst taget, densiteten i ett intervall I är den minsta genomsnittliga hastighet som krävs för att slutföra alla jobb som måste schemaläggas i I. En hög densitet kräver hög hastighet. Formellt är densiteten D I för ett tidsintervall I = [t, t ¢] det totala arbete som ska slutföras i I dividerat med längden på I. Mer exakt, låt S I vara den uppsättning av jobb J i som måste bearbetas i I eftersom deras release tid och deadline är i I, såsom Algorithm YDS upprepade gånger bestämmer intervallet I av maximal densitet. I ett sådant intervall I schemalägger algoritmen jobben för S I i hastighet D Jag använder Earliest Deadline First (EDF) policy. Denna välkända politik utför alltid jobbet med den tidigaste deadline, bland de tillgängliga oavslutade jobben. Efter detta uppdrag, YDS tar bort set S I samt tidsintervall jag från problem instans. Mer specifikt, för alla ledig jobb J i vars deadline är i intervallet I, den nya deadline är satt till början av I eftersom tidsfönstret jag inte är tillgänglig längre för behandling av J i. Formellt, för alla J i med d i I, den nya deadline tiden är inställd på d i := t. På samma sätt, för alla oplanerade J i vars releasetid är i I, den nya releasetiden är inställd på slutet av I. Återigen, formellt för alla J i med r i I, är den nya release tiden r i := t ¢. Tidsintervall Jag är kasserad. Denna process upprepas tills det inte finns fler lediga jobb. Vi ger en sammanfattning av algoritmen i pseudokod. granska artiklar den horisontella axeln. I den första iteration YDS identifierar I 1 = [3, 8] som intervall av maximal densitet, tillsammans med uppsättning S I 1 = { J 2, J 3 }. I I 1, det röda jobbet J 2 är föreslagen vid tidpunkten 5 för att ge företräde till orange jobb J 3 med en tidigare deadline. I den andra iterationen I 2 = [13, 20] är det maximala densitetsintervallet. De mörkgröna och ljusgröna jobben är planerade; företrädet används igen en gång. I den tredje iterationen är det återstående jobbet J 3 schemalagt i de tillgängliga ankomst- och avgångstiderna. När man identifierar intervaller av maximal densitet behöver YDS bara beakta intervaller vars gränser är lika med releasetider och tidsgränser för jobben. En enkel implementering av algoritmen har en körtid på O(n 3 ). Löjtnant m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m för m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m. 34 visade att tiden kan minskas till O(n 2 log n). Ytterligare förbättringar är möjliga om arbetsintervallen bildar en trädstruktur. Om det inte är möjligt att genomföra en viss arbetsuppgift, är situationen mer känslig. I detta fall är det omöjligt att slutföra alla arbetstillfällen. Målet är att designa algoritmer som uppnår bra genomströmning, vilket är den totala bearbetningsvolymen av jobb som slutförs vid sin deadline, och samtidigt optimera energiförbrukningen. Papper 7, 17 presenterar algoritmer som även fungerar på nätet. Vid varje tidpunkt som strategierna upprätthåller en pool av jobb som de har för avsikt att slutföra. Nyanlända jobb kan komma in i poolen. Om poolen innehåller för stor bearbetning volym, arbetstillfällen utvisas så att genomströmningen inte minskas avsevärt. Algoritmen av Bansal et al. 7 är 4 konkurrenskraftiga när det gäller genomströmning och konstant konkurrenskraft i fråga om energiförbrukning. Temperaturminimering: Höga processorhastigheter leder till höga temperaturer, vilket försämrar en processors tillförlitlighet och livslängd. Bansal m.fl. 9 överväga minimering av den maximala temperatur som uppstår under bearbetning. De utgår från att kylningen följer Newtons lag, som säger att en kropps kylningshastighet står i proportion till temperaturskillnaden mellan kroppen och miljön. Bansal m.fl. 9 visar att algoritmer YDS och BKP har gynnsamma egenskaper. För alla jobb sekvens, är den maximala temperaturen inom en konstant faktor för minsta möjliga optimal schema för de nuvarande tillgängliga oavslutade jobb. Bansal m.fl. 9 gav en omfattande analys av ovanstående algoritm och visade att konkurrensförhållandet är exakt en. När det gäller konkurrenskraften är därför Optimal Tillgängligt bättre än genomsnittet. Bansal m.fl. 9 presenterade också en ny online-algoritm, kallad BKP enligt författarnas initialer, som kan ses som en approximering av de optimala hastigheterna för YDS på ett online sätt. Återigen, algoritmen tar hänsyn till intervalltätheter. För tider t, t 1, och t 2 med t 1 < t £ t 2, låt w(t, t 1, t 2 ) vara den totala bearbetningsvolymen av jobb som har anlänt med tid t, har en releasetid på minst t 1 och en deadline på högst t 2. Sedan, intuitivt, max t 1, t 2 w(t, t 1, t 2 )/(t 2 − t 1 ) är en uppskattning av den hastighet som används av YDS, baserat på kunskap om jobb som har anlänt med tiden t. Den nya algoritmen BKP approximerar denna hastighet genom att överväga specifika tidsfönster [et − (e − 1) t¢, t¢], för t¢ > t, av längd e(t¢ − t). Motsvarande nödvändiga hastighet multipliceras sedan med en faktor av e. algoritm BKP: När som helst t använda en hastighet av e. s(t), där tillgängliga oavslutade jobb bearbetas med EDF. Bansal m.fl. 9 visade att BKP uppnår ett konkurrenskraftigt förhållande av, vilket är bättre än konkurrenskraften för Optimal Tillgänglig för stora värden av a. Alla ovanstående online-algoritmer uppnår konstanta konkurrensförhållanden som beror på en och inga andra problemparameter. Beroendet av a är exponentiellt. För små värden av a, som förekommer i praktiken, är konkurrensförhållandena relativt små. Ett resultat av Bansal et al. 9 innebär att det exponentiella beroendet av a är en naturlig del av problemet. Varje randomiserad onlinealgoritm har en konkurrenskraft på minst W (4/3) a ). förfining-Bounded hastighet: Den problem inställning som anses hittills förutsätter en kontinuerlig, obegränsad spektrum av hastigheter. I praktiken är dock endast en begränsad uppsättning av diskreta hastighetsnivåer s 1 < s 2 <... < s d tillgängliga. De 23 undersöker en utökad problematik där en processor med variabel hastighet kan övergå till ett vilotillstånd. I viloläget, är energiförbrukningen 0 medan i aktivt tillstånd även vid hastighet 0 viss icke-negativ mängd energi förbrukas. Därför Irani et al. 23 kombinerar hastighetsskalning med power-down-mekanismer. I standardinställningen utan viloläge, algoritmer tenderar att använda låg hastighet nivåer som omfattas av release tid och deadline begränsningar. Däremot kan det i viloläge vara fördelaktigt att påskynda ett arbete för att generera inaktiva tider då processorn kan övergå till viloläge. Irani m.fl. 23 utveckla online- och offlinealgoritmer för denna utökade inställning. Baptiste m.fl. 11 och Demaine m.fl. 21 också studera schemaläggning problem där en processor kan ställas in sömn, om än i en inställning utan hastighetsskalning. Minimera Svarstid Ett klassiskt mål i schemaläggningen är minimeringen av svarstiderna. En användare som släpper en uppgift till ett system vill få feedback, säger resultatet av en beräkning, så snabbt som möjligt. Användarnöjdhet beror ofta på hur snabbt en enhet reagerar. Tyvärr, svarstid minimering och energiminimering strider mot målen. För att uppnå snabba svarstider måste ett system vanligtvis använda höga processorer hastigheter, vilket leder till hög energiförbrukning. För att spara energi bör däremot låga hastigheter användas, vilket leder till höga svarstider. Därför måste man hitta sätt att integrera båda målen. Betrakta n jobb J 1,..., J n som måste schemaläggas på en processor med variabel hastighet. Varje jobb J i anges av en release tid r i och en bearbetning volym w i. När ett arbete anländer är dess bearbetningsvolym känd. Företräde av 37 studera en problematik där en fast energi volym E ges och målet är att minimera den totala flödestiden för jobben. Författarna antar att alla jobb har samma bearbetningsvolym. Genom att skala, kan vi anta att alla jobb har enheter. Pruhs och Al. 37 överväga offline scenariot där alla jobb är kända i förväg och visa att optimala scheman kan beräknas i polynom tid. Inom detta ramverk med en begränsad energivolym är det dock svårt att konstruera bra online-algoritmer. Om framtida arbetstillfällen är okända är det oklart hur mycket energi som ska investeras för de uppgifter som för närvarande finns tillgängliga. energi plus flödestider: Albers och Fujiwara 2 föreslog ett annat tillvägagångssätt för att integrera energi och flödestidsminimering. De betraktar en kombinerad objektiv funktion som helt enkelt lägger till de två kostnaderna. Låt E betecknar energiförbrukningen i ett schema. Vi vill minimera. Genom att multiplicera energi eller flödestid med en skalar kan vi också överväga en viktad kombination av de två kostnaderna, vilket uttrycker det relativa värdet av de två termerna i den totala kostnaden. Albers och Fujiwara koncentrerar sig på jobb i enhetsstorlek och visar att optimala offlinescheman kan konstrueras i polynomtid med hjälp av en dynamisk programmeringsmetod. I själva verket algoritmen kan också användas för att minimera den totala flödestiden för jobb med tanke på en fast energivolym. Bansal m.fl. och Lam et al. 7, 32 föreslå algoritmer för inställningen att det finns en övre gräns på den maximala processorn hastighet. Alla ovanstående resultat antar att när ett arbete anländer, dess bearbetning volym är känd. Papper 18, 32 undersöker det svårare fallet att denna information inte är tillgänglig. De resultat som presenterats hittills gäller arkitekturer med en processor. Energiförbrukning är dock också ett stort problem i multiprocessormiljöer. För närvarande är relativt få resultat kända. Albers m.fl. 3 undersöka deadline-baserad schemaläggning för m identiska parallella processorer. Målet är att minimera den totala energin på alla maskiner. Författarna löser först komplexiteten i offline-problemet genom att visa att datorer optimala scheman är NP-hårda, även för enhet storlek jobb. Om inte P = NP kan optimala lösningar därför inte beräknas på ett effektivt sätt. Albers m.fl. 3 sedan utveckla polynom tid offline algoritmer som uppnår konstant faktor approximationer, såsom, för varje inmatning den förbrukade energin ligger inom en konstant faktor för den sanna optimal. De utformar också online-algoritmer som uppnår konstanta konkurrensförhållanden. Lam m.fl. 30 studiedeadlinebaserad schemaläggning på två hastighetsbegränsade processorer. De presenterar en strategi som är konstant konkurrenskraftig i termer av throughput maximization och energiminimering. Bunde 15 undersöker flödestidsminimering i multiprocessormiljöer, givet en fast energivolym. Han presenterar hårdhet resultat samt approximation garantier för enhet storlek jobb. Lam m.fl. 31 överväga den objektiva funktionen att minimera energi plus flödestider. De designar online-algoritmer som uppnår konstanta konkurrensförhållanden. Makespan minimization: En annan grundläggande objektiv funktion i schemaläggning är makespan minimization, det vill säga minimiseringen av den punkt i tiden när hela schemat slutar. Bunde 15 förutsätter att jobb anländer över tid och utvecklar algoritmer för enkel- och multiprocessormiljöer. Pruhs och Al. 36 överväga uppgifter som har företräde begränsningar som definieras mellan dem. De utformar algoritmer för parallella processorer med en fast energivolym. Trådlösa nätverk som ad hoc-nät och sensornätverk har fått stor uppmärksamhet under de senaste åren. Framträdande tillämpningar av sådana nätverk är observation av livsmiljöer, miljöövervakning och prognoser. Nätverksnoder har vanligtvis mycket begränsad batterikapacitet så att effektiva energihanteringsstrategier är nödvändiga för att förbättra ett näts livslängd. I den här undersökningen fokuserar vi på två algoritmiska problem som har fått stort intresse för forskarsamhället på senare tid. Dessutom kan dessa problem betraktas som planeringsproblem och är därmed relaterade till de ämnen som behandlas i de föregående avsnitten. nättopologier Trådlöst ad hoc-nätverk har ingen fast infrastruktur. Nätverket består i princip av en samling radiostationer med antenner för att sända och ta emot signaler. Under överföringen en station s måste välja en transmissionseffekt P s, med hänsyn till att signalstyrkan minskar över avstånd. Signalen tas emot med framgång av en station t endast om P s/dist(s,t) a > g. Här betecknar dist(s,t) avståndet mellan s och t, koefficienten a > 1 är dämpningshastigheten och g > 0 är en överföringskvalitetsparameter. I praktiken är dämpningshastigheten mellan 2 och 5. Utan förlust av allmängiltighet kan vi anta g = 1. Vid dataöverföring sänds en mycket grundläggande operation, där en viss källa nod vill skicka en bit information till alla andra noder i nätverket. Vi studerar problemet med att utforma topologier som möjliggör energieffektiv sändningsverksamhet i trådlösa nät. Överväg en uppsättning V av n noder som ligger i det verkliga planet R 2. En källa nod s V måste sprida ett meddelande till alla andra noder i nätverket. Men s behöver inte informera alla v ί V direkt. I stället kan noder fungera som relästationer. Om v tar emot meddelandet och överför det till w 1,..., w k, sedan v måste använda en effekt av P v = max 1 £ j k dist( v, w j ) a. Målet är att hitta en topologi, det vill säga ett överföringsschema som minimerar den totala effekten/energin E = S v V P v uppstår av alla noderna. Observera att ett sådant schema motsvarar ett träd T som är rotat på s och innehåller alla noder av V. Barnen i en nod v är noderna som v överför meddelandet. Clementi m.fl. 19 visade att beräkningen av optimala scheman är NP-hård. Därför tillgriper man approximationer. En algoritm ALG uppnår en c-uppskattning om för varje ingång, t.ex. för varje nodmängd V, den lösning som ALG beräknar medför en energiförbrukning på högst c gånger det optimala värdet. Wan m.fl. 39 undersöka olika algoritmer när det gäller deras approximativa garantier. Den mest studerade strategin är MST. För en given noduppsättning V beräknar MST en standard minsta spännvidd T, t.ex. ett träd med minsta totala kantlängd som innehåller alla hörn av V (se t.ex. Cormen et al. Europaparlamentets och rådets förordning (EU, Euratom) nr 966/2012 av den 25 oktober 2012 om finansiella regler för unionens allmänna budget och om upphävande av rådets förordning (EG, Euratom) nr 1605/2002 (EUT L 298, 26.10.2012, s. 1). Trädet är rotat vid källnoden s. Dataöverföring utförs längs kanterna på T, det vill säga varje nod sänder ett mottaget meddelande till alla sina barn i trädet. Intuitivt är denna algoritm förnuftig eftersom den lilla totala kantlängden på ett minsta spännträd bör leda till en liten total energiförbrukning. Algoritm MsT: För en given V, beräkna en minsta spännvidd träd rotad på s. Varje nod v överför ett givet meddelande till alla sina barn i T. Många och Wan et al. 39 innebär att approximationsgraden c av BIP uppfyller 13/3 £ c £ 6. Det skulle vara intressant att utveckla snäva gränser för denna algoritm. Som nämnts ovan används sensornätverk vanligtvis för att övervaka en miljö, mäta t.ex. temperatur eller ett kemiskt värde. Uppgifterna måste överföras till en utsedd diskbänksnod som kan utföra ytterligare åtgärder. Becchetti m.fl. 13 och Korteweg m.fl. utveckla energieffektiva protokoll för dataaggregation. Antag att överföringstopologin ges av ett träd T rotat vid diskhon s. Data som samlats in vid ett nätverk nod v överförs längs vägen från v till s i T. Nätverk noder har förmågan att kombinera data. Om två eller flera datapaket samtidigt befinner sig på en nod v, kan v sammanfoga dessa paket till en översiktsartiklar enstaka en och överföra den till den ursprungliga noden, i riktning mot s. Energin som uppstår av en nätverk nod är proportionell mot antalet paket som skickas. Becchetti m.fl. 13 anta att dataposter anländer över tid. Varje post i anges av noden v i där objektet uppstår, en ankomsttid r i och en deadline d i där uppgifterna måste nå diskbänken. Målet är att hitta ett genomförbart överföringsschema som minimerar den maximala energi som krävs vid någon nod. Becchetti m.fl. visa att offline problemet är NP-hård och presentera en 2- approximation algoritm. De utvecklar också distribuerade online-algoritmer för synkrona samt asynkrona kommunikationsmodeller. Korteweg m.fl. 29 studera en problemvariant där dataobjekten inte har tidsfrister men bör nå diskbänken med låg latens. De presenterar algoritmer som samtidigt approximerar energiförbrukning och latens, med tanke på återigen olika kommunikationsmodeller. I den här undersökningen har vi granskat algoritmiska lösningar för att spara energi. En annan undersökning om algoritmiska problem i makthantering skrevs av Irani och Pruhs. 27 Under de senaste månaderna har ett stort antal artiklar publicerats, och vi förväntar oss att energibevarande ur algoritmisk synvinkel kommer att fortsätta att vara ett aktivt forskningsämne. Det finns många vägar till framtida forskning. När det gäller t.ex. effektnedsättningsmekanismer skulle det vara intressant att utforma strategier som tar hänsyn till den latens som uppstår när ett system övergår från ett sömntillstånd till ett aktivt tillstånd. Dessutom behöver vi en bättre förståelse för hastighetsskalningsteknik i multiprocessormiljöer eftersom flerkärnig arkitektur blir allt vanligare inte bara på servrar utan även på stationära datorer och bärbara datorer. Dessutom förtjänar optimeringsproblem i nätverk ytterligare algoritmiska undersökningar. Här skulle det vara intressant att studera energieffektiva punkt-till-punkt-kommunikationer som kompletterar det befintliga arbetet med sändnings- och dataaggregateringsprotokoll. Sist men inte minst, de algoritmer som presenterats hittills måste analyseras i termer av deras genomförande och utförande kostnad: hur mycket extra energi uppstår vid genomförandet av algoritmer i realistiska miljöer. Susanne Albers är professor vid institutionen för datavetenskap vid Humboldt universitet, Berlin, Tyskland.
En färsk undersökning av analytiskt arbete med fokus på energieffektivitet i allmänhet är REF.
Energy-efficient algorithms
{'venue': 'CACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}