Nuvarande dynamiska spänningsskalningsmetoder gör det möjligt att ställa in processorers hastighet dynamiskt för att spara energiförbrukningen, vilket är ett stort problem för mikroprocessorns konstruktion. En teoretisk modell för min-energi jobbplanering föreslogs först för ett decennium sedan, och det visades att för alla konvex energifunktion, min-energi schema för en uppsättning n jobb har en unik karakterisering och kan beräknas i O(n 3 ) tid. Denna algoritm har förblivit den mest effektiva kända trots många undersökningar av denna modell. I detta papper ger vi en ny algoritm med körtid O(n 2 log n) för att hitta min-energi schema. I motsats till den tidigare algoritmen som ger optimala hastighetsnivåer från hög till låg iterativt är den nya algoritmen baserad på att hitta successiva approximationer till det optimala schemat. Kärnan i approximationen är en effektiv uppdelning av arbetet i undergrupper med hög och låg hastighet, oavsett hastighetströskel, utan att beräkna den exakta hastighetsfunktionen.
Senare förbättras körtiden till O(n 2 log n) av Li et al. Hoppa över det.
Discrete and Continuous Min-Energy Schedules for Variable Voltage Processors ∗
{'venue': 'Proceedings of the National Academy of Sciences of the United States of America', 'journal': 'Proceedings of the National Academy of Sciences of the United States of America', 'mag_field_of_study': ['Computer Science', 'Medicine']}