Abstrakt. Hastighetsskalning är en effekthanteringsteknik som innebär dynamisk förändring av hastigheten hos en processor. Detta ger upphov till dubbla objektiva schemaläggningsproblem, där operativsystemet både vill spara energi och optimera vissa Quality of Service (QoS) mått på det resulterande schemat. I den mest undersökta hastighetsskalning problem i litteraturen, QoS begränsning är deadline genomförbarhet, och målet är att minimera den energi som används. Standarden antagandet är att effektförbrukningen är hastigheten till viss konstant effekt α. Vi ger den första icke-triviala nedre gränsen, nämligen e α‐1 /α, om konkurrensförhållandet för detta problem. Detta kommer nära den bästa övre gränsen som är ca 2e α+1. Vi analyserar en naturlig klass av algoritmer som kallas qOA, där processorn när som helst arbetar på q ≥ 1 gånger den minsta hastighet som krävs för att säkerställa genomförbarhet förutsatt att inga nya jobb anländer. För CMOS-baserade processorer, och många andra typer av enheter, α = 3, det vill säga, de uppfyller kub-rot regeln. När α = 3, visar vi att qOA är 6.7-konkurrenskraftig, förbättra med den tidigare bästa garantin för 27 uppnås av algoritmen Optimal Tillgänglig (OA). Så när kubrotsregeln gäller minskar våra resultat intervallet för det optimala konkurrensförhållandet från [1.2, 27] till [2.4, 6.7]. Vi analyserar också qOA för allmän α och ger nästan matchande övre och nedre gränser.
Med andra ord är PEV-laddningsschemat ett mer allmänt problem än problemet med hastighetsskalning, vilket innebär att dess konkurrensförhållande inte är mindre än 2,39, dvs. det mest kända förhållandet för hastighetsskalning problem REF.
Improved bounds for speed scaling in devices obeying the cube-root rule
{'venue': 'In Automata, Languages and Programming', 'journal': None, 'mag_field_of_study': ['Computer Science']}