Elkostnaden är en dominerande och snabbt växande kostnad i datacenter. Tyvärr slösas mycket av den förbrukade energin bort eftersom servrar är inaktiva under längre tidsperioder. Vi studerar ett kapacitetshanteringsproblem som dynamiskt högerstorlekar ett datacenter, som matchar antalet aktiva servrar med den varierande efterfrågan på datorkapacitet. Vi tar till ett optimeringsproblem för datacenter som infördes av Lin, Wierman, Andrew och Thereska [17, 19] som över en tidshorisont minimerar en kombinerad objektiv funktion som består av driftskostnader, modelleras av en sekvens av konvexa funktioner, och server växlingskostnader. Allt föregående arbete tar upp en kontinuerlig inställning där antalet aktiva servrar, när som helst, kan ta ett fraktionerat värde. I detta papper undersöker vi för första gången det diskreta datacenteroptimering problemet där antalet aktiva servrar, när som helst, måste heltal värderas. Därmed söker vi verkligt genomförbara lösningar. Först visar vi att problemet offline kan lösas i polynom tid. Vår algoritm bygger på en ny, men ändå intuitiv grafteoretisk modell av optimeringsproblem och utför binär sökning i en lagergrafik. För det andra studerar vi online-problemet och utökar algoritmen Lazy Capacity provisioning (LCP) av Lin et al. [17, 19] till den diskreta inställningen. Vi bevisar att LCP är 3-konkurrent. Dessutom visar vi att ingen deterministisk online-algoritm kan uppnå ett konkurrensförhållande mindre än 3. Även om LCP inte uppnår optimal konkurrenskraft i den kontinuerliga miljön, gör den det i det diskreta problem som undersöks här. Vi bevisar att den nedre gränsen på 3 också har en problemvariant med mer begränsade driftkostnader funktioner, som infördes av Lin et al. [17].................................................................. Slutligen tar vi itu med den kontinuerliga inställningen och ger en lägre gräns på 2 på den bästa konkurrenskraft online algoritmer. Detta matchar en övre gräns vid Bansal et al. [5]............................................................... En nedre gräns på 2 visades också nyligen av Antoniadis och Schewior [3]. Vi utvecklar ett oberoende bevis som sträcker sig till scenariot med mer begränsade driftskostnader.
Nyligen visar REF att samma konkurrensförhållande kan upprätthållas i den diskreta miljön under korrekt avrundning.
Optimal Algorithms for Right-Sizing Data Centers
{'venue': "SPAA '18", 'journal': None, 'mag_field_of_study': ['Computer Science']}