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

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

• 批准号: 1535902
• 负责人: Thomas Goldstein
• 金额: $ 20万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1535902&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在实践中的有效性。为了弥合最近数值优化和硬件设计之间日益增长的差距，该项目还包括开发基于该项目垂直集成研究方法的本科和研究生课程，此外还提供暑期研究实习（reu），将年轻科学家引入离散编程领域。该项目开发了一套计算效率高、硬件感知的算法和相应的专用超大规模集成（VLSI）架构，使DP能够用于实时嵌入式系统。所提出的DP算法依赖于各种算法转换，从半定和无限范数松弛到精确变量分裂方法和非凸近似。这些不同的方法在解决方案质量和硬件实现复杂性之间提供了广泛的权衡。该项目从理论和实践的角度研究了这些基本的权衡，以及VLSI中有限精度算法的影响。为了进行这项研究，将开发三个专用的VLSI架构，利用所提出算法的固有并行性。这些架构的目标是(1)多天线（MIMO）无线系统中的数据检测，这是下一代通信系统的关键瓶颈；(2)高光谱成像中的信号恢复问题；(3)x射线晶体学中的相位恢复问题。通过在各种条件和硬件配置下研究各种数值求解器的特定领域性能和复杂性，该项目将揭示DP在本项目研究之外的广泛实时应用中的有效性和局限性。