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

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

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.