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的硬件体系结构。除了对拟议方法进行彻底的理论分析外，该项目还包括广泛的软件和硬件基准测试，以揭示实时DP在实践中的功效。为了弥合数值优化和硬件设计的最新进展之间的不断增长的差距，该项目还包括开发本科生和研究生课程，这些课程以该项目的垂直综合研究方法为基础，除了为夏季研究实习（REUS）提供介绍的年轻科学家，以开发一个既定的计划。非常大的比例集成（VLSI）体系结构，可为实时嵌入式系统提供DP。 所提出的DP算法依赖于各种算法转换，从基于半芬矿和基于无穷大的松弛到确切的可变分解方法和非凸近近似值。这些不同的方法在解决方案质量和硬件实施复杂性之间提供了广泛的权衡。该项目从理论和实践的角度研究了这些基本的权衡以及有限精确算术在VLSI中的影响。为了进行这项调查，将开发三个专用的VLSI架构，以利用所提出算法的固有平行性。这些体系结构是多 - 安德纳（MIMO）无线系统中的数据检测，这是下一代通信系统中的关键瓶颈，（ii）高光谱成像中的信号恢复问题，以及（iii）从X射线晶体学中的相位检索问题。通过调查各种条件和硬件配置的各种数值求解器的特定域性能和复杂性，该项目将揭示DP对本项目研究的实时应用程序的效力和限制。