Grant: Discovery Grants Program - Individual
École Polytechnique de Montréal
$48,000.00
Multi-Precision Optimization and Methods with Inaccurate Functions and Derivatives
EF 2021-22
Résumé
Optimization is concerned with the search for a best solution to a problem among all candidates satisfying desirable properties. Large numbers of optimization problems are solved routinely on computers to plan air routes, forecast weather, design aerodynamic structures, provide user recommendations, manage water reservoirs, power plants, and many more tasks that Canadians rely on daily. Solving those problems consumes large amounts of energy. The theme of this proposal is the design of better methods that take advantage of problem structure and modern computer architectures. The main objective is to decrease the computational effort and energy expended in solving such problems. Modern computers, including laptops, e-watches and smart phones and supercomputers, feature a mixture of processing units, each designed to perform certain types of computations to a specified accuracy. As the accuracy capacity of a unit increases, the energy expended to perform a similar calculation increases approximately fourfold. Commonly, problems are solved with intermediate accuracy, known as double precision. Certain types of problems, such as recommendation systems, only require low accuracy, e.g., half precision. Others, in systems biology, require solutions to such high accuracy, called quadruple precision, that specialized hardware or software is required. In this proposal, we describe the design of solution methods that alternate between low and high-accuracy units dynamically with the objective of performing as much work as possible in cheap, energy-efficient low accuracy. In doing so, we still attain the accuracy level requested by the user or demanded by the application. We will devise multi-precision optimization strategies based on principles inspired from methods used in applications such as fluid dynamics. Our methods automatically discover and capitalize on the problem structure and on the computational units available on the computer on which they run. Whereas typical double-precision methods can only afford to rely on so much problem information, our methods benefit from additional low-accuracy information, which is cheaper to obtain than high accuracy information, and allows them to make better-informed decisions on the way to a solution. The advantages of our approach are: 1) Faster solves due to more computation occurring in low precision 2) Less data movement between slow and fast memory 3) Greener computation due to savings in energy expended during the solves. Simple strategies in our recent research showed energy savings of a factor from 2 to 5. Preliminary experiments with some of the methods proposed here suggest savings up to 95% to solve problems without noticeable difference in the quality of the final solution. This research will result in efficient open software and faster computational methods that apply to large classes of applications. The immediate benefits to Canada are more efficient and greener decision processes.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2020-06535
Name nom
Orban, Dominique
Department département
Mathématiques et génie industriel
Organization id
64
Institution établissement
École Polytechnique de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2021
Competition year année de concours
2020
Award amount
48000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
306
Area of application group en
Energy resources
Area of application group fr
Ressources d'énergie
Area of application en
Energy efficiency
Area of application fr
Efficacité énergétique
Research subject code
2956
Research subject group en
Applied mathematics
Research subject group fr
Mathématiques appliquées
Research subject en
Optimisation and optimal control theory
Research subject fr
Optimisation et théories de commande optimale
Installment
inst:2
Partie
1
Nb partie
5
Application title
Multi-Precision Optimization and Methods with Inaccurate Functions and Derivatives
Keyword
NSERC
Application summary
Optimization is concerned with the search for a best solution to a problem among all candidates satisfying desirable properties. Large numbers of optimization problems are solved routinely on computers to plan air routes, forecast weather, design aerodynamic structures, provide user recommendations, manage water reservoirs, power plants, and many more tasks that Canadians rely on daily. Solving those problems consumes large amounts of energy. The theme of this proposal is the design of better methods that take advantage of problem structure and modern computer architectures. The main objective is to decrease the computational effort and energy expended in solving such problems. Modern computers, including laptops, e-watches and smart phones and supercomputers, feature a mixture of processing units, each designed to perform certain types of computations to a specified accuracy. As the accuracy capacity of a unit increases, the energy expended to perform a similar calculation increases approximately fourfold. Commonly, problems are solved with intermediate accuracy, known as double precision. Certain types of problems, such as recommendation systems, only require low accuracy, e.g., half precision. Others, in systems biology, require solutions to such high accuracy, called quadruple precision, that specialized hardware or software is required. In this proposal, we describe the design of solution methods that alternate between low and high-accuracy units dynamically with the objective of performing as much work as possible in cheap, energy-efficient low accuracy. In doing so, we still attain the accuracy level requested by the user or demanded by the application. We will devise multi-precision optimization strategies based on principles inspired from methods used in applications such as fluid dynamics. Our methods automatically discover and capitalize on the problem structure and on the computational units available on the computer on which they run. Whereas typical double-precision methods can only afford to rely on so much problem information, our methods benefit from additional low-accuracy information, which is cheaper to obtain than high accuracy information, and allows them to make better-informed decisions on the way to a solution. The advantages of our approach are: 1) Faster solves due to more computation occurring in low precision 2) Less data movement between slow and fast memory 3) Greener computation due to savings in energy expended during the solves. Simple strategies in our recent research showed energy savings of a factor from 2 to 5. Preliminary experiments with some of the methods proposed here suggest savings up to 95% to solve problems without noticeable difference in the quality of the final solution. This research will result in efficient open software and faster computational methods that apply to large classes of applications. The immediate benefits to Canada are more efficient and greener decision processes.