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

AitF：EXPL：协作研究：实时系统的近似离散编程

• 批准号: 1535897
• 负责人: Christoph Studer
• 金额: $ 20万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1535897&HistoricalAwards=false
• 关键词: AitF; EXPL; Collaborative; Research; Approximate

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.

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