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

Michigan Technological University, Houghton MI

Investigators

Abstract

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.