Accelerating multi-objective combinatorial optimization via GPUs for cyber-physical systems design

信息物理系统（CPS）正在改变我们与物理世界的互动方式。它们是结合机器、计算机、软件、数据和人类用户的复杂系统，例如自动驾驶汽车、飞机、医疗设备、工厂自动化和智能可再生能源电网。这种系统的设计越来越具有挑战性：它涉及大量的决策，例如在不同的传感器和执行器技术之间进行选择，决定不同的系统功能和处理算法，在不同的计算节点之间部署软件，以及决定通信和电源拓扑，所有这些都在众多的设计约束和目标下，例如成本，质量，计算性能，能耗，可靠性和安全性。这种约束和优化目标下的决策可以形式化为多目标组合优化（MOCO）。MOCO使计算机辅助设计方法能够大大加快和提高CPS整体设计过程的效率。然而，MOCO是一个计算困难的问题，目前的MOCO解决方案具有有限的可扩展性。该项目的总体目标是通过提高使用图形处理器单元（GPU）的MOCO的可扩展性来加速和提高CPS设计的效率。该研究将针对一系列基于约束和元启发式的MOCO算法，适用于汽车电气和电子系统以及航空电子系统的设计优化，并使用GPU平台加速它们。该项目将改进下一代智能汽车和飞机的设计，为gpu在CPS设计背景下开辟新的应用领域，并在算法设计、软件开发和CPS工程等对加拿大知识经济至关重要的领域培养10名高素质人才。

Cyber-physical systems (CPS) are transforming how we interact with the physical world. They are complex systems that combine machinery, computers, software, data, and human users, such as self-driving cars, airplanes, medical devices, factory automation, and smart renewable energy grids. The design of such systems is increasingly challenging: it involves a multitude of decisions, such as selecting among different sensor and actuator technologies, deciding on different system functions and processing algorithms, deploying software among different computing nodes, and deciding on the communication and power supply topology, all under a multitude of design constraints and objectives such as cost, mass, computing performance, energy consumption, reliability, and safety. Such decision making under constraints and optimization objectives can be formalized as multi-objective combinatorial optimization (MOCO). MOCO enables computer-aided design methods that can dramatically accelerate and improve the efficacy of the overall design process for CPS. However, MOCO is a computationally hard problem and current MOCO solutions have limited scalability.The overarching objective of this project is to accelerate and improve the efficacy of CPS design by improving the scalability of MOCO using Graphic Processor Units (GPU). The research will target a range of constraint-based and metaheuristic MOCO algorithms suitable for design optimization of automotive electric and electronic systems and avionic systems and accelerate them using the GPU platform. The project will improve design of the next generation of intelligent cars and airplanes, open new application areas for GPUs in the context of CPS design, and train ten highly-qualified personnel in algorithm design, software development and CPS engineering---areas that are vital to Canadian knowledge-based economy.