AitF: Fast and Accurate Memristor-Based Algorithms for Social Network Analysis

AitF：快速准确的基于忆阻器的社交网络分析算法

• 批准号: 1637559
• 负责人: Sucheta Soundarajan
• 金额: $ 56.08万
• 依托单位: Syracuse University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1637559&HistoricalAwards=false
• 关键词: AitF; Fast; Accurate; Memristor; Based

The area of computational social network analysis includes fundamental problems such as predicting the spread of information or disease, detecting communities in a population, and identifying missing links in an incomplete network. Common techniques for solving such problems require matrix-vector multiplications, a computationally-expensive mathematical operation. If performed at the software level, such multiplications can be prohibitively slow, particularly for the large-scale networks that are becoming increasingly prevalent in real applications. Instead, the PIs will perform these multiplications at the hardware level by using the memristor device, a newly invented chip component. In this project, the PIs will develop scalable, efficient, and effective memristor-based algorithms for problems in network analysis. Such algorithms will have a clear impact across scientific disciplines, as well as on tools used in practice. This project bridges the two areas of hardware and algorithms, and provides excellent topics for graduate student researchers, who the PIs will recruit from a diverse student body, including women and other underrepresented groups. Additionally, the research developed in this project will be incorporated into coursework taught by the PIs at Syracuse University. The project will investigate the use of memristors in developing effective, scalable algorithms for social network analysis, with potentially major effects both on research and practice. One can assemble memristors into a crossbar array, and by effectively setting and modifying the resistances of the memristors (which can be done in real-time), this array can represent a matrix. By applying proper voltages at the inputs of the array, one can perform extremely fast matrix-vector multiplication at the hardware level. The resistances can be set in parallel in O(N) time, and the matrix-vector multiplication itself can be done in O(1) time. Even for large matrices which must be partitioned to fit on the crossbar array hardware, one can expect running time reductions of multiple orders of magnitude, allowing for fast, potentially real-time, network analysis. The project will consider four major topics: (1) Eigenvalue and eigenvector finding, (2) Information spread in networks, (3) Pathfinding and prediction of missing links, and (4) Community detection. Using these topics as reference points, the PIs will develop a suite of algorithms, general techniques, and theoretical analyses with broad applicability both inside and outside of social network analysis. These devices can be potentially utilized for solving many critical problems and applications to achieve transformative accelerations in speed, enhancements in scalability, and reductions in computational complexity and power/energy consumption.

计算社会网络分析领域包括一些基本问题，如预测信息或疾病的传播，检测群体中的社区，以及识别不完整网络中的缺失链接。 解决这类问题的常用技术需要矩阵向量乘法，这是一种计算量很大的数学运算。 如果在软件级别执行，则这种乘法可能非常慢，特别是对于在真实的应用中变得越来越普遍的大规模网络。 相反，PI将通过使用忆阻器设备（一种新发明的芯片组件）在硬件级别执行这些乘法。 在这个项目中，PI将为网络分析中的问题开发可扩展的，高效的，有效的基于忆阻器的算法。 这种算法将对各个科学学科以及实践中使用的工具产生明显的影响。 该项目连接了硬件和算法这两个领域，并为研究生研究人员提供了优秀的课题，PI将从包括女性和其他代表性不足的群体在内的多元化学生中招募研究生。 此外，在这个项目中开发的研究将被纳入锡拉丘兹大学PI教授的课程。 该项目将研究忆阻器在开发有效的、可扩展的社交网络分析算法中的应用，对研究和实践都有潜在的重大影响。 人们可以将忆阻器组装成交叉阵列，并且通过有效地设置和修改忆阻器的电阻（这可以实时完成），该阵列可以表示矩阵。通过在阵列的输入端施加适当的电压，可以在硬件级别执行极快的矩阵向量乘法。 这两个电阻可以在O（N）时间内并行设置，而矩阵向量乘法本身可以在O（1）时间内完成。 即使对于必须划分以适合交叉开关阵列硬件的大型矩阵，也可以预期运行时间减少多个数量级，从而允许快速，潜在的实时网络分析。 该项目将考虑四个主要主题：（1）特征值和特征向量查找，（2）网络中的信息传播，（3）路径查找和缺失链接预测，以及（4）社区检测。 使用这些主题作为参考点，PI将开发一套算法，通用技术和理论分析，在社交网络分析内外都具有广泛的适用性。 这些设备可以潜在地用于解决许多关键问题和应用，以实现速度的变革性加速、可扩展性的增强以及计算复杂性和功耗/能耗的降低。

项目成果

Algorithm-hardware co-optimization of the memristor-based framework for solving SOCP and homogeneous QCQP problems

用于解决 SOCP 和同构 QCQP 问题的基于忆阻器的框架的算法-硬件协同优化

• DOI: 10.1109/aspdac.2017.7858420
• 发表时间: 2017
• 期刊: 2017 22nd Asia and South Pacific Design Automation Conference (ASP-DAC
• 作者: Ren, Ao;Liu, Sijia;Cai, Ruizhe;Wen, Wujie;Varshney, Pramod K.;Wang, Yanzhi
• 通讯作者: Wang, Yanzhi

TinyADC: Peripheral Circuit-aware Weight Pruning Framework for Mixed-signal DNN Accelerators

TinyADC：混合信号 DNN 加速器的外围电路感知权重修剪框架

• DOI: 10.23919/date51398.2021.9474235
• 发表时间: 2021
• 期刊: Automation & Test in Europe Conference & Exhibition (DATE
• 作者: Yuan, Geng;Behnam, Payman;Cai, Yuxuan;Shafiee, Ali;Fu, Jingyan;Liao, Zhiheng;Li, Zhengang;Ma, Xiaolong;Deng, Jieren;Wang, Jinhui
• 通讯作者: Wang, Jinhui

Tiny but Accurate: A Pruned, Quantized and Optimized Memristor Crossbar Framework for Ultra Efficient DNN Implementation

• DOI: 10.1109/asp-dac47756.2020.9045658
• 发表时间: 2019-08
• 期刊: 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC)
• 作者: Xiaolong Ma;Geng Yuan;Sheng Lin;Caiwen Ding;Fuxun Yu;Tao Liu;Wujie Wen;Xiang Chen;Yanzhi Wang

A low-computation-complexity, energy-efficient, and high-performance linear program solver based on primal–dual interior point method using memristor crossbars

一种基于使用忆阻器交叉开关的原始对偶内点法的低计算复杂度、节能且高性能的线性程序求解器

• DOI: 10.1016/j.nancom.2018.01.001
• 发表时间: 2018
• 期刊: Nano Communication Networks
• 影响因子: 2.9
• 作者: Cai, Ruizhe;Ren, Ao;Soundarajan, Sucheta;Wang, Yanzhi
• 通讯作者: Wang, Yanzhi

Ultra-fast robust compressive sensing based on memristor crossbars

• DOI: 10.1109/icassp.2017.7952333
• 发表时间: 2017-03
• 期刊: 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
• 作者: Sijia Liu;Ao Ren;Yanzhi Wang;P. Varshney