AitF: EXPL: Collaborative Research: Approximate Discrete Programming for Real-Time Systems

离散编程(DP)处理涉及范围在离散(例如，整数值)解空间上的变量的优化问题。DP是数字通信、运筹学、电网优化、计算机视觉等多种实际应用中的重要工具。虽然离散程序通常是使用功能强大的计算机通过复杂的软件离线解决的，但DP最近已成为嵌入式系统中要求实时处理的应用程序中的重要工具，这些应用程序具有严格的面积、成本和功率限制。由于现有的DP解算器在现有的嵌入式硬件上实现时会带来令人望而却步的复杂性和功耗，因此需要新的算法和硬件架构来释放DP在实时应用中的潜力。该项目融合了最优化理论、数值方法和电路设计，为嵌入式系统中的实时DP开发了快速算法和合适的硬件结构。除了对所提出的方法进行深入的理论分析外，该项目还包括广泛的软件和硬件基准测试，以揭示实时DP在实践中的有效性。为了弥合最近数值优化和硬件设计之间日益扩大的差距，除了提供暑期研究实习(REU)以向年轻科学家介绍离散编程领域外，该项目还包括开发基于该项目垂直集成研究方法的本科生和研究生课程。该项目开发了一套计算高效和硬件感知的算法和相应的专用超大规模集成(VLSI)架构，使DP能够用于实时嵌入式系统。所提出的DP算法依赖于各种算法变换，从半定和基于无穷范数的松弛到精确变量分裂方法和非凸近似。这些不同的方法在解决方案质量和硬件实施复杂性之间提供了广泛的折衷。该项目从理论和实践两个角度研究了这些基本权衡，以及有限精度算法在VLSI中的影响。为了进行这项研究，将开发三个专用的VLSI架构，以利用所提出算法的内在并行性。这些体系结构针对(I)多天线(MIMO)无线系统中的数据检测，这是下一代通信系统中的关键瓶颈，(Ii)高光谱成像中的信号恢复问题，以及(Iii)X射线晶体学中的相位恢复问题。通过研究各种数值求解器在不同条件和硬件配置下的特定领域的性能和复杂性，该项目将揭示DP在除本项目所研究的应用之外的广泛实时应用中的有效性和局限性。

Discrete programming (DP) deals with optimization problems involving variables that range over a discrete (e.g., integer-valued) solution space. DP is an important tool in a variety of practical applications including digital communications, operations research, power grid optimization, and computer vision. While discrete programs are typically solved offline by sophisticated software using powerful computers, DP has recently emerged as an important tool in applications requiring real-time processing in embedded systems with stringent area, cost, and power constraints. Since existing DP solvers entail prohibitive complexity and power consumption when implemented on existing embedded hardware, novel algorithms and hardware architectures are necessary to unlock the potential of DP in real-time applications. This project fuses optimization theory, numerical methods, and circuit design to develop fast algorithms and suitable hardware architectures for real-time DP in embedded systems. Besides a thorough theoretical analysis of the proposed methods, the project includes extensive software and hardware benchmarking to reveal the efficacy of real-time DP in practice. To bridge the ever-growing gap between recent advances in numerical optimization and hardware design, the project also includes the development of undergraduate and graduate courses that build upon the vertically-integrated research approach of this project, in addition to offering summer research internships (REUs) to introduce young scientists to the field of discrete programming.The project develops a set of computationally efficient and hardware-aware algorithms and corresponding dedicated very-large scale integration (VLSI) architectures that enable DP for real-time embedded systems. The proposed DP algorithms rely on a variety of algorithmic transformations, ranging from semidefinite and infinity-norm-based relaxations to exact variable-splitting methods and non-convex approximations. These disparate approaches offer a wide range of tradeoffs between solution quality and hardware implementation complexity. The project studies these fundamental tradeoffs, as well as the effects of finite-precision arithmetic in VLSI, from both a theoretical and practical perspective. To carry out this investigation, three dedicated VLSI architectures will be developed that exploit the inherent parallelism of the proposed algorithms. These architectures target (i) data detection in multi-antenna (MIMO) wireless systems that is the key bottleneck in next-generation communication systems, (ii) signal recovery problems in hyperspectral imaging, and (iii) phase retrieval problems from x-ray crystallography. By investigating the domain-specific performance and complexity of various numerical solvers in a variety of conditions and hardware configurations, the project will reveal the efficacy and limits of DP for a broad range of real-time applications beyond the ones studied in this project.