CAREER: Advancing Combinatorial Optimization Accelerataors with Compute in Memory Design Approach

职业：通过内存计算设计方法推进组合优化加速器

• 批准号: 2145236
• 负责人: Jaydeep Kulkarni
• 金额: $ 50万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-01-15 至 2026-12-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2145236&HistoricalAwards=false
• 关键词: CAREER; Advancing; Combinatorial; Optimization; Accelerataors

This award is funded in whole or in part under the American Rescue Plan Act of 2021 (Public Law 117-2).Combinatorial optimization problems find many real-world social and industrial data intensive compute applications. Examples include optimization of mRNA sequences for COVID-19 vaccines, semiconductor supply-chains, and financial index tracking, to name a few. Such optimization problems are computationally intensive, and a brute-force search method for finding the optimum solution becomes untenable as the problem size increases. An efficient way to solve an optimization problem is to let nature perform the exhaustive search in the physical world by mapping the problem onto an Ising model. The Ising model describes spin dynamics in a ferromagnet, wherein spins naturally orient to achieve the lowest energy state, representing the optimal solution to a given optimization problem. Performing such Ising computations using conventional methods requires numerous compute iterations. This results in frequent off-chip memory accesses and incur significant energy overheads. The goal of this project is to advance the development of energy-efficient as well as cost-efficient combinatorial optimization hardware accelerators to be integrated in modern integrated circuits for solving critical optimization problems as mentioned above. The research results from this project will be disseminated to the students in the form of course design case-studies. Reciprocally, some of the course projects will be aligned with Ising accelerator designs enabling tight research-teaching integration. The project also aims to engage with underrepresented and minority students in the form of undergraduate and graduate student mentoring and research experiences. This project proposes a unique analog compute-within-memory design approach performing the Ising computations by reconfiguring existing memory array circuitry. In contrast to prior near-memory, digital-arithmetic computing approaches, this compute-in-memory approach performs Ising Hamiltonian computations in the analog domain within a memory array with minimal circuit changes. It maps Hamiltonian computations on to available memory wordline and bitline circuitry, which has remained a key technical challenge so far. In addition, this project will investigate the ways to seamlessly map large Ising models across multiple memory banks, thereby scaling up the Ising spin count significantly. The project aims to demonstrate compute-in-memory Ising accelerator silicon prototypes, perform design-space exploration, and quantify the benefits over prior approaches. Furthermore, the project will explore the high-density memory needs for future complex combinatorial-optimization accelerators utilizing large-scale Ising models. This project will systematically investigate device-technology circuit co-design aspects of emerging monolithically integrated 3D memory technologies. This can potentially leapfrog the benefits of compute-in-memory based Ising accelerators for solving extreme-scale optimization problems. The tightly-integrated research, education, and outreach plan aims to establish a close industry relationship, integrate this research with a graduate course, deliver online courses, expand K-12 outreach, and train students in the area of memory devices, circuit designs, and combinatorial-optimization algorithms in service of furthering the creation of the STEM workforce.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

该奖项全部或部分由2021年美国救援计划法案（公法117-2）资助。组合优化问题发现了许多现实世界的社会和工业数据密集型计算应用。例如，优化COVID-19疫苗的mRNA序列、半导体供应链和金融指数跟踪等。这样的优化问题是计算密集型的，并且随着问题大小的增加，用于找到最优解的蛮力搜索方法变得站不住脚。解决优化问题的一个有效方法是让自然界通过将问题映射到伊辛模型上来进行物理世界中的穷举搜索。伊辛模型描述了铁磁体中的自旋动力学，其中自旋自然定向以实现最低能量状态，表示给定优化问题的最优解。使用常规方法执行这样的伊辛计算需要多次计算迭代。这导致频繁的片外存储器访问，并招致显著的能量开销。该项目的目标是推进高能效和高成本效益的组合优化硬件加速器的开发，这些硬件加速器将集成在现代集成电路中，用于解决上述关键优化问题。该项目的研究成果将以课程设计案例研究的形式传播给学生。反过来，一些课程项目将与Ising加速器设计保持一致，从而实现紧密的研究与教学整合。该项目还旨在以本科生和研究生指导和研究经验的形式与代表性不足和少数民族学生接触。 这个项目提出了一个独特的模拟计算内存设计方法执行伊辛计算重新配置现有的存储器阵列电路。与现有的近存储器、数字算术计算方法相比，这种存储器中计算方法以最小的电路改变在存储器阵列内的模拟域中执行伊辛哈密顿计算。它将哈密顿计算映射到可用的内存中，这仍然是一个关键的技术挑战。此外，该项目还将研究如何在多个内存库中无缝映射大型伊辛模型，从而显著增加伊辛自旋计数。该项目旨在展示内存计算伊辛加速器硅原型，进行设计空间探索，并量化与现有方法相比的优势。此外，该项目将探索未来复杂组合优化加速器利用大规模伊辛模型的高密度内存需求。该项目将系统地研究新兴单片集成3D存储器技术的器件技术电路协同设计方面。 这可能会超越基于内存计算的伊辛加速器解决极端规模优化问题的好处。紧密整合的研究，教育和推广计划旨在建立密切的行业关系，将这项研究与研究生课程相结合，提供在线课程，扩大K-12推广，并在存储设备，电路设计，和组合-该奖项反映了NSF的法定使命，并被认为是值得的。通过使用基金会的知识价值和更广泛的影响审查标准进行评估来提供支持。

项目成果

Ising-CIM: A Reconfigurable and Scalable Compute Within Memory Analog Ising Accelerator for Solving Combinatorial Optimization Problems

Ising-CIM：用于解决组合优化问题的可重新配置和可扩展的内存模拟 Ising 加速器

• DOI: 10.1109/jssc.2022.3176610
• 发表时间: 2022
• 期刊: IEEE Journal of Solid-State Circuits
• 影响因子: 5.4
• 作者: Xie, Shanshan;Raman, Siddhartha Raman;Ni, Can;Wang, Meizhi;Yang, Mengtian;Kulkarni, Jaydeep P.
• 通讯作者: Kulkarni, Jaydeep P.

29.2 Snap-SAT: A One-Shot Energy-Performance-Aware All-Digital Compute-in-Memory Solver for Large-Scale Hard Boolean Satisfiability Problems

29.2 Snap-SAT：一种解决大规模硬布尔可满足性问题的一次性能源性能感知全数字内存计算求解器

• DOI: 10.1109/isscc42615.2023.10067380
• 发表时间: 2023
• 期刊: IEEE
• 作者: Xie, Shanshan;Yang, Mengtian;Lanham, S. Andrew;Wang, Yipeng;Wang, Meizhi;Oruganti, Sirish;Kulkarni, Jaydeep P.
• 通讯作者: Kulkarni, Jaydeep P.