# US 2018/0321980 A1 · Execution time prediction for energy-efficient computer systems > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2018/0321980 A1 - Document ID: US20180321980A1 - Status: Published application - Kind: A1 - Application number: 15/781,339 - Filed: 2016-12-04 - Published: 2018-11-08 - Earliest claimed: 2015-12-04 - Assignees: Cornell University - Applicants: Cornell University - Inventors: Daniel Lo; Tao Chen; Edward G. Suh; Taejoon Song - Web page: https://patentgrep.com/patent/US20180321980A1 ## CPC - G06F 9/5038: {considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups)} - G06F 9/4887: {involving deadlines, e.g. rate based, periodic} - G06F 9/5088: {involving task migration} - G06F 11/3419: {by assessing time} - G06F 11/3644: {by instrumenting at runtime} - G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks - G06F 2209/5019: Workload prediction - Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS - Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE ## Abstract Methods, systems, and devices of using prediction-guided resource allocation technologies for software applications are disclosed, comprising generating a plurality of program features that impact execution time of a plurality of program tasks; predicting execution time of the plurality of program tasks on one or more computing cores using the plurality of program features, wherein each of the plurality of program features is mapped to an execution time estimate on a selected computing core; and controlling resources for the one or more computing cores based on a predicted execution time of the plurality of program tasks. ## Claims ### Claim 1 A computer-implemented method of using prediction-guided resource allocation technologies to improve energy efficiency while meeting response-time requirement for software applications, comprising: generating a plurality of program features that impact execution time of a plurality of program tasks; predicting execution time of the plurality of program tasks on one or more computing cores using the plurality of program features, wherein each of the plurality of program features is mapped to an execution time estimate on a selected computing core; and controlling resources for the one or more computing cores based on a predicted execution time of the plurality of program tasks. ### Claim 2 (depends on 1) The method of claim 1, further comprising: instrumenting source code of the plurality of program tasks for identifying values of the plurality of program features; and producing code fragments that, when executed, compute the values of the plurality of program features, wherein the code fragments are capable of computing the values of the plurality of program features faster than the source code. ### Claim 3 (depends on 1) The method of claim 1, further comprising: training and fitting a mathematical model to map the plurality of program features to the corresponding execution time estimates. ### Claim 4 (depends on 3) The method of claim 3, wherein the training and fitting the mathematical model place more weight on avoiding exceeding the time budget of the program tasks than on conserving energy usage by the computing core. ### Claim 5 (depends on 3) The method of claim 3, wherein the training and fitting the mathematical model is conducted offline by feeding a set of training data consisting of the plurality of program features and corresponding execution times to the mathematical model. ### Claim 6 (depends on 3) The method of claim 3, wherein the training and fitting the mathematical model further comprises: feeding the plurality of program features and corresponding execution times at runtime to the mathematical model; monitoring an error margin to ensure that the mathematical model reaches stability to provide accurate predictions. ### Claim 7 (depends on 6) The method of claim 6, wherein the training and fitting the mathematical model further comprises: detecting runtime changes to retrain the mathematical model or to switch to a second mathematical model. ### Claim 8 (depends on 1) The method of claim 1, further comprising: switching, when the predicted execution time of a subset of the plurality of program tasks exceeds the time budget on a first computing core running at its maximal frequency, the subset of the plurality of program tasks to a second computing core that is different from the first computing core. ### Claim 9 (depends on 1) The method of claim 1, further comprising: switching a subset of the plurality of program tasks to a second computing core that is different from the first computing core when a first estimated power consumption of the subset of the plurality of program tasks on the first computing core exceeds a second estimated power consumption of the subset of the plurality of program tasks on the second computing core, wherein the predicted execution time of the subset of the plurality of program tasks is within the time budget on the first computing core running at its maximal frequency. ### Claim 10 (depends on 1) The method of claim 1, wherein the resources include a clock frequency, a voltage, an amount of memory, an amount of cache space, an interconnection bandwidth, or a memory bandwidth. ### Claim 11 A computer program product comprising a computer-readable non-transitory program medium having code stored thereon, the code, when executed, causing a processor to implement a method of using prediction-guided resource allocation technologies to improve energy efficiency while meeting response-time requirement for software applications, the method comprising: generating a plurality of program features that impact execution time of a plurality of program tasks; predicting execution time of the plurality of program tasks on one or more computing cores using the plurality of program features, wherein each of the plurality of program feature is mapped to an execution time estimate on a selected computing core; and controlling resources for the one or more computing cores based on a predicted execution time of the plurality of program tasks. ### Claim 12 (depends on 11) The computer program product of claim 11, wherein the method further comprises: instrumenting source code of the plurality of program tasks for identifying values of the plurality of program features; and producing code fragments that, when executed, compute the values of the plurality of program features, wherein the code fragments are capable of computing the values of the plurality of program features faster than the source code. ### Claim 13 (depends on 11) The computer program product of claim 11, wherein the method further comprises: training and fitting a mathematical model to map the plurality of program features to the corresponding execution time estimates. ### Claim 14 (depends on 13) The computer program product of claim 13, wherein the training and fitting the mathematical model place more weight on avoiding exceeding the time budget of the program tasks than on conserving energy usage by the computing core. ### Claim 15 (depends on 13) The computer program product of claim 13, wherein the training and fitting the mathematical model is conducted offline by feeding a set of training data consisting of the plurality of program features and corresponding execution times to the mathematical model. ### Claim 16 (depends on 13) The computer program product of claim 13, wherein the training and fitting the mathematical model further comprises: feeding the plurality of program features and corresponding execution times at runtime to the mathematical model; and monitoring an error margin to ensure that the mathematical model reaches stability to provide accurate predictions. ### Claim 17 (depends on 13) The computer program product of claim 13, wherein the training and fitting the mathematical model further comprises: detecting runtime changes to retrain the mathematical model or to switch to a second mathematical model. ### Claim 18 (depends on 11) The computer program product of claim 11, wherein the method further comprises: switching, when the predicted execution time of a subset of the plurality of program tasks exceeds the time budget on a first computing core running at its maximal frequency, the subset of the plurality of program tasks to a second computing core that is different from the first computing core. ### Claim 19 (depends on 11) The computer program product of claim 11, wherein the method further comprises: switching a subset of the plurality of program tasks to a second computing core that is different from the first computing core when a first estimated power consumption of the subset of the plurality of program tasks on the first computing core exceeds a second estimated power consumption of the subset of the plurality of program tasks on the second computing core, wherein the predicted execution time of the subset of the plurality of program tasks are within the time budget on the first computing core running at its maximal frequency. ### Claim 20 (depends on 11) The computer program product of claim 11, wherein the resources include a clock frequency, a voltage, an amount of memory, an amount of cache space, an interconnection bandwidth, or a memory bandwidth. ### Claim 21 An apparatus using prediction-guided resource allocation technologies to improve energy efficiency while meeting response-time requirement for computer hardware systems, comprising: a logic module including a control unit, comprising one or more finite state machines (FSMs), for handling input requests and output responses and generating control signals, and a data-path module for performing computation on input requests to generate output data and signals; one or more computing cores; and a prediction controller that records execution time of a plurality of features during training runs by Register Transfer Level (RTL) instrumentation and analysis, wherein the plurality of features impact execution time of a task associated with a deadline; predicts execution time of the task on the one or more computing cores using the plurality of features, wherein each of the plurality of feature is mapped to an execution time estimate on a selected computing core based on data from the training runs; and controls resources for the one or more computing core based on a predicted execution time of the task. ### Claim 22 (depends on 21) The apparatus of claim 21, wherein the prediction controller further performs: training and fitting a mathematical model to map the plurality of features to the corresponding execution time estimates. ### Claim 23 (depends on 22) The apparatus of claim 22, wherein the training and fitting the mathematical model place more weight on avoiding missing the deadline of the task than on conserving energy usage by the one or more computing cores. ### Claim 24 (depends on 22) The apparatus of claim 22, wherein the training and fitting the mathematical model is conducted offline by feeding the mathematical model with data from the training runs consisting of the plurality of features and corresponding execution times. ### Claim 25 (depends on 22) The apparatus of claim 22, wherein the training and fitting the mathematical model further comprises: feeding the plurality of features and corresponding execution times at runtime to the mathematical model; and monitoring an error margin to ensure that the mathematical model reaches stability to provide accurate predictions. ### Claim 26 (depends on 21) The apparatus of claim 21, wherein the resources include a clock frequency, a voltage, an amount of memory, an amount of cache space, an interconnection bandwidth, or a memory bandwidth. ### Claim 27 (depends on 21) The apparatus of claim 21, wherein the prediction controller switches the task to a second computing core, different from the first computing core, when the predicted execution time of the task miss the deadline on a first computing core running at its maximal frequency.