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

Cornell University, Ithaca NY

Investigators

Abstract

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.