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

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

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.