Multi-Precision Optimization and Methods with Inaccurate Functions and Derivatives

多精度优化以及不精确函数和导数的方法

• 批准号: RGPIN-2020-06535
• 负责人: Orban, Dominique
• 金额: $ 3.5万
• 依托单位: École Polytechnique de Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=741298
• 关键词: Multi; Precision; Optimization; Methods; Inaccurate

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.

最优化是在所有满足期望性质的候选者中寻找问题的最佳解决方案。大量的优化问题在计算机上常规地解决，以规划航线，预测天气，设计空气动力学结构，提供用户建议，管理水库，发电厂，以及更多加拿大人日常依赖的任务。解决这些问题消耗大量的能量。本提案的主题是设计更好的方法，利用问题结构，现代计算机体系结构。其主要目标是减少解决此类问题时所消耗的计算工作量和能量。现代计算机，包括笔记本电脑、电子手表、智能手机和超级计算机，其特征在于混合了处理单元，每个处理单元都被设计成以指定的精度执行某些类型的计算。随着单元的精度能力的增加，执行类似计算所花费的能量增加了大约四倍。通常，问题以中间精度解决，称为双精度。某些类型的问题，例如推荐系统，只需要低精度，例如，在系统生物学中，其他的解决方案需要达到如此高的精度，称为四倍精度，需要专门的硬件或软件。在本提案中，我们描述了在低精度和高精度单元之间动态交替的解决方案方法的设计，目的是以廉价，节能的低精度执行尽可能多的工作。这样做，我们仍然可以达到用户或应用程序所要求的精度水平。我们将根据流体力学等应用中所使用的方法所启发的原理设计多精度优化策略。我们的方法自动发现并利用问题结构和运行它们的计算机上可用的计算单元。虽然典型的双精度方法只能依赖于这么多的问题信息，但我们的方法受益于额外的低精度信息，这比高精度信息更便宜，并允许他们在解决方案的过程中做出更明智的决策。我们的方法的优点是：1）更快的解决，由于更多的计算发生在低精度2）更少的数据移动之间的慢速和快速内存3）绿色计算，由于节省能源消耗在解决过程中。在我们最近的研究中，简单的策略显示出从2到5的一个因子的能量节省。本文提出的一些方法的初步实验表明，节省高达95%，以解决问题，而不会在最终解决方案的质量显着差异。这项研究将导致高效的开放软件和更快的计算方法，适用于大型应用程序。加拿大的直接好处是更有效和更环保的决策过程。