Collaborative Research: ACI-CDS&E: Highly Parallel Algorithms and Architectures for Convex Optimization for Realtime Embedded Systems (CORES)

合作研究：ACI-CDS

• 批准号: 1708299
• 负责人: Glen Archer
• 金额: $ 35万
• 依托单位: Michigan Technological University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-01 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1708299&HistoricalAwards=false
• 关键词: Collaborative; Research; ACI; CDS& Highly

Embedded processors are ubiquitous, from toasters and microwave ovens, to automobiles, planes, drones and robots and are typically very small processors that are compute and memory constrained. Real-time embedded systems have the additional requirement of completing tasks within a certain time period to accurately and safely control appliances and devices like automobiles, planes, robots, etc. Convex optimization has emerged as an important mathematical tool for automatic control and robotics and other areas of science and engineering disciplines including machine learning and statistical information processing. In many fields, convex optimization is used by the human designers as optimization tool where it is nearly always constrained to problems solved in a few hours, minutes or seconds. Highly Parallel Algorithms and Architectures for Convex Optimization for Realtime Embedded Systems (CORES) project takes advantage of the recent advances in embedded hardware and optimization techniques to explore opportunities for real-time convex optimization on the low-cost embedded systems in these disciplines in milli- and micro-seconds. The development of novel algorithms and their high-performance implementations for the real-time solution of practical engineering and scientific optimization problems on the embedded system will open new opportunities in the area of emerging computational science and engineering for cyber physical systems on low-cost platforms. Equally important is the CORES contributions to the education of the next generation of researchers and creators of future infrastructure for realtime computational systems for problems involving engineering optimization. Foremost, CORES will provide undergraduate and graduate level educational opportunities with a multidisciplinary breadth spanning areas as diverse as optimization theory, parallel algorithms for numerical optimization, embedded computer systems, and heterogeneous computing architectures. Interactions with the control engineering and auto industries in the State of Michigan confirms the need for the development of expertise in this area for present and future engineering research and development. The results from CORES research will have an impact in the fields of engineering optimization and computing infrastructure for cyber physical systems.The current algorithms for realtime convex optimization can only solve the problem with about a hundred unknowns in the Karush Kuhn Tucker (KKT) convex optimization matrices. This is because the realtime solution enforces a strict time limit on the linear solver (e.g., in microseconds) and the current algorithms are not designed to fully utilize the limited compute power of the embedded system (e.g., a few CPU cores, plus a GPU). The CORES project will analyze the structure of complex multi-dimensional convex optimization algorithms and replaces the existing sequential implementations, which are the current performance bottleneck, with implementations of new tracking algorithms. Efficient implementations of the algorithms that can effectively leverage the compute power of the scalable heterogeneous system architecture (SHSA) of the embedded system will be developed. The goal is to speed up the solution process and scale up the size of the optimization problems by orders of magnitude for realtime embedded applications such as control of complex cyber-physical systems (CPS). Specifically, CORES will focus on: (1) Development of high performance linear solvers that exploit the structures of the KKT matrices and leverage the compute power of SHSA and (2) Development of automatic code generation and analysis tools that analyze the structure of the convex optimization problem from a high level modeling language like MATLAB or PYTHON, perform a mapping to a decomposed parallel algorithm, and generate a hybridized multicore CPU and GPU code in OpenCL/CUDA format. Tools that CORES aims to develop come with hierarchical parallel-feature extraction, targeted for various computing elements of SHSA e.g. CPUs and GPU) in a way that eliminates the inefficiencies of inter-processors data sharing. Emerging SHSA combines general-purpose low-latency CPU cores with programmable high-bandwidth vector processing engines on a single platform, connected through a high speed data transfer engines that could still become the performance bottleneck. This feature creates unique opportunities for CORES, and others, to develop sophisticated and specialized computational algorithms and tools for engineering applications such as machine learning and autonomous vehicles that can exploit such architectures for significantly enhancing performance and scaling up the problem size, while reducing the cost.This project is supported by the Office of Advanced Cyberinfrastructure in the Directorate for Computer & Information Science & Engineering and the Division of Mathematical Sciences in the Directorate of Mathematical and Physical Sciences.

嵌入式处理器无处不在，从烤面包机和微波炉，到汽车、飞机、无人机和机器人，通常是非常小的处理器，受计算和内存的限制。实时嵌入式系统具有在一定时间内完成任务的额外要求，以准确安全地控制汽车，飞机，机器人等电器和设备。凸优化已成为自动控制和机器人以及其他科学和工程学科领域（包括机器学习和统计信息处理）的重要数学工具。在许多领域，凸优化被人类设计师用作优化工具，它几乎总是被限制在几小时、几分钟或几秒钟内解决问题。实时嵌入式系统凸优化的高度并行算法和架构（内核）项目利用嵌入式硬件和优化技术的最新进展，探索在这些学科中以毫秒和微秒为单位在低成本嵌入式系统上进行实时凸优化的机会。新型算法及其高性能实现在嵌入式系统上实时解决实际工程和科学优化问题的发展，将为低成本平台上的网络物理系统的新兴计算科学和工程领域开辟新的机遇。同样重要的是，核心对教育下一代研究人员和未来基础设施的创建者的贡献，这些基础设施用于解决涉及工程优化的问题的实时计算系统。最重要的是，CORES将提供本科和研究生水平的教育机会，涉及多学科领域，如优化理论、数值优化并行算法、嵌入式计算机系统和异构计算架构等。与密歇根州的控制工程和汽车工业的互动证实了在当前和未来的工程研究和开发中需要发展这一领域的专业知识。核心研究的结果将对网络物理系统的工程优化和计算基础设施领域产生影响。目前的实时凸优化算法只能解决KKT （Karush Kuhn Tucker）凸优化矩阵中大约100个未知数的问题。这是因为实时解决方案对线性求解器施加了严格的时间限制（例如，以微秒为单位），而当前的算法并没有被设计成充分利用嵌入式系统有限的计算能力（例如，几个CPU核心，加上一个GPU）。CORES项目将分析复杂的多维凸优化算法的结构，并用新的跟踪算法的实现取代现有的顺序实现，这是当前的性能瓶颈。将开发有效利用嵌入式系统可扩展异构系统架构（SHSA）计算能力的算法的有效实现。目标是加快解决过程，并按数量级扩大优化问题的规模，用于实时嵌入式应用，如复杂网络物理系统（CPS）的控制。具体而言，CORES将专注于：(1)开发利用KKT矩阵结构并利用SHSA计算能力的高性能线性求解器；(2)开发自动代码生成和分析工具，从MATLAB或PYTHON等高级建模语言分析凸优化问题的结构，执行到分解并行算法的映射，并生成OpenCL/CUDA格式的混合多核CPU和GPU代码。core旨在开发的工具具有分层并行特征提取，针对SHSA的各种计算元素（例如cpu和GPU），以消除处理器间数据共享的低效率。新兴的SHSA将通用的低延迟CPU内核与可编程的高带宽矢量处理引擎结合在一个平台上，通过高速数据传输引擎连接，这仍然可能成为性能瓶颈。这一特性为core和其他公司创造了独特的机会，为机器学习和自动驾驶汽车等工程应用开发复杂而专业的计算算法和工具，这些应用可以利用这种架构来显著提高性能，扩大问题规模，同时降低成本。该项目由计算机与信息科学与工程理事会的先进网络基础设施办公室和数学与物理科学理事会的数学科学部提供支持。

项目成果

Structure-Aware Linear Solver for Realtime Convex Optimization for Embedded Systems

用于嵌入式系统实时凸优化的结构感知线性求解器

• DOI: 10.1109/les.2017.2700401
• 发表时间: 2017
• 期刊: IEEE Embedded Systems Letters
• 影响因子: 1.6
• 作者: Yamazaki, Ichitaro;Nooshabadi, Saeid;Tomov, Stanimire;Dongarra, Jack
• 通讯作者: Dongarra, Jack

Exploiting Block Structures of KKT Matrices for Efficient Solution of Convex Optimization Problems

利用 KKT 矩阵的块结构有效解决凸优化问题

• DOI: 10.1109/access.2021.3106054
• 发表时间: 2021
• 期刊: IEEE Access
• 影响因子: 3.9
• 作者: Iqbal, Zafar;Nooshabadi, Saeid;Yamazaki, Ichitaro;Tomov, Stanimire;Dongarra, Jack
• 通讯作者: Dongarra, Jack