Suppr超能文献

必须有所取舍:通过生物智能体探索编码NP完全问题的物理网络来扩展组合计算。

Something has to give: scaling combinatorial computing by biological agents exploring physical networks encoding NP-complete problems.

作者信息

van Delft Falco C M J M, Ipolitti Giulia, Nicolau Dan V, Sudalaiyadum Perumal Ayyappasamy, Kašpar Ondřej, Kheireddine Sara, Wachsmann-Hogiu Sebastian, Nicolau Dan V

机构信息

Molecular Sense Ltd, Liverpool L36 8HT, UK.

Department of Bioengineering, McGill University, Montreal, Quebec, Canada H3A 0E9.

出版信息

Interface Focus. 2018 Dec 6;8(6):20180034. doi: 10.1098/rsfs.2018.0034. Epub 2018 Oct 19.

Abstract

On-chip network-based computation, using biological agents, is a new hardware-embedded approach which attempts to find solutions to combinatorial problems, in principle, in a shorter time than the fast, but sequential electronic computers. This analytical review starts by describing the underlying mathematical principles, presents several types of combinatorial (including NP-complete) problems and shows current implementations of proof of principle developments. Taking the subset sum problem as example for in-depth analysis, the review presents various options of computing agents, and compares several possible operation 'run modes' of network-based computer systems. Given the brute force approach of network-based systems for solving a problem of input size C, 2 solutions must be visited. As this exponentially increasing workload needs to be distributed in space, time, and per computing agent, this review identifies the scaling-related key technological challenges in terms of chip fabrication, readout reliability and energy efficiency. The estimated computing time of massively parallel or combinatorially operating biological agents is then compared to that of electronic computers. Among future developments which could considerably improve network-based computing, labelling agents 'on the fly' and the readout of their travel history at network exits could offer promising avenues for finding hardware-embedded solutions to combinatorial problems.

摘要

基于片上网络的计算,利用生物媒介,是一种新的硬件嵌入式方法,原则上它试图比快速但顺序执行的电子计算机在更短的时间内找到组合问题的解决方案。这篇分析性综述首先描述其潜在的数学原理,介绍几种类型的组合问题(包括NP完全问题),并展示原理验证开发的当前实现情况。以子集和问题为例进行深入分析,该综述介绍了计算媒介的各种选项,并比较了基于网络的计算机系统几种可能的操作“运行模式”。鉴于基于网络的系统采用暴力方法解决输入大小为C的问题时必须访问2个解决方案。由于这种呈指数级增长的工作量需要在空间、时间和每个计算媒介之间进行分配,本综述确定了在芯片制造、读出可靠性和能源效率方面与规模相关的关键技术挑战。然后将大规模并行或组合操作的生物媒介的估计计算时间与电子计算机的计算时间进行比较。在未来可能大幅改进基于网络的计算的发展方向中,“即时”标记媒介并在网络出口处读出它们的行程历史,可能为找到组合问题的硬件嵌入式解决方案提供有前景的途径。

https://cdn.ncbi.nlm.nih.gov/pmc/blobs/609a/6227808/0086ede16b49/rsfs20180034-g1.jpg

文献AI研究员

20分钟写一篇综述,助力文献阅读效率提升50倍。

立即体验

用中文搜PubMed

大模型驱动的PubMed中文搜索引擎

马上搜索

文档翻译

学术文献翻译模型,支持多种主流文档格式。

立即体验