h**x
发帖数: 34 | 1 麻烦想了解一下诸位在实际工作（比如，金融，生物，工程计算，等领域）中有需要解
决某 NP-complete 问题的吗？
如果有，能否说明一下具体是哪个 NPC problem，以及 problem size 有多大。
谢谢！ |
g*********e
发帖数: 14401 | 2 有啊 现在工作要对图进行优化，需要解决subgraph-isomorphism问题。
problem size很小啦，几百个节点以内吧。 |
h**x
发帖数: 34 | 3
那你们现在是怎么算的？我主要想了解 hardware 用多大的 cluster (多少个CPU), 一
般一个问题算多少天，或多少小时？
【在 g*********e 的大作中提到】
: 有啊 现在工作要对图进行优化，需要解决subgraph-isomorphism问题。
: problem size很小啦，几百个节点以内吧。
|
s********e
发帖数: 425 | 4 我感觉你想了解的问题可以归于科学计算范畴。科学计算在物理、机械工程，医学等多
个应用领域都需要。例如物理或天文里计算多个天体相互之间的作用力的问题(N-body
problem)，天体数量可以达到几万到几十万；又比如医学中有医学图像重构问题（比如
backprojection），需要把多幅机器拍摄的原始图像以某种组合方式重构成医生能看懂
的图像，图像像素数可以是几千乘几千。
虽然可能处理三五个数据所使用的算法极其简单，但是由于数据量巨大，算法复杂度随
着数据量的增长迅速增加，于是同样简单的算法就无法使如此庞大的数据量在可接受时
间内算完，于是就构成了NP-complete问题。
这些都是需要超级计算机（supercomputer）来运算，也就是cluster或multiprocessor
。根据问题所需数据量的大小，运算时间从几小时到几天都有，一两个月也有可能。
运算方法概括来说叫做并行计算。具体就是尽可能编出并行性（Parallelism）高的程
序，使得庞大数据能够并行处理，比如一万个天体分给八个cpu同时运算，每个cpu算
1250个；1024x1024的图像分给16个cpu，每个cpu处理64x1024(64列)图像。
当然具体实现没有这么简单，一般在不同cpu算完各自的部分以后，通常需要把数据综
合起来算不同cpu处理内容的边界上相互作用的结果。另外还要考虑数据传输延迟，因
为cpu算是算的快，但是把算好的数据从cpu传到存储器的过程会很慢和很堵塞，所以大
部分运算时间其实都花在数据传输上了。
我现在在做的是用FPGA代替CPU。FPGA也是一块芯片，可以像CPU一样连成cluster做并
行计算的。不同的是fpga是直接硬件实现并行性，比软件实现要快很多，而且也能设计
出并行性更强的应用在fpga上的“算法”。
大体情况就是这样吧。希望木有太啰嗦~
【在 h**x 的大作中提到】
:
: 那你们现在是怎么算的？我主要想了解 hardware 用多大的 cluster (多少个CPU), 一
: 般一个问题算多少天，或多少小时？
|
s*****t
发帖数: 987 | 5
body
multiprocessor
为啥不用asic呢，那岂不是比FPGA更好么?
【在 s********e 的大作中提到】
: 我感觉你想了解的问题可以归于科学计算范畴。科学计算在物理、机械工程，医学等多
: 个应用领域都需要。例如物理或天文里计算多个天体相互之间的作用力的问题(N-body
: problem)，天体数量可以达到几万到几十万；又比如医学中有医学图像重构问题（比如
: backprojection），需要把多幅机器拍摄的原始图像以某种组合方式重构成医生能看懂
: 的图像，图像像素数可以是几千乘几千。
: 虽然可能处理三五个数据所使用的算法极其简单，但是由于数据量巨大，算法复杂度随
: 着数据量的增长迅速增加，于是同样简单的算法就无法使如此庞大的数据量在可接受时
: 间内算完，于是就构成了NP-complete问题。
: 这些都是需要超级计算机（supercomputer）来运算，也就是cluster或multiprocessor
: 。根据问题所需数据量的大小，运算时间从几小时到几天都有，一两个月也有可能。
|
g*********e
发帖数: 14401 | 6
不好意思 我是做EDA的码农。。。不是科学家
【在 h**x 的大作中提到】
:
: 那你们现在是怎么算的？我主要想了解 hardware 用多大的 cluster (多少个CPU), 一
: 般一个问题算多少天，或多少小时？
|
g*********e
发帖数: 14401 | 7
大哥 ASIC要钱的
【在 s*****t 的大作中提到】
:
: body
: multiprocessor
: 为啥不用asic呢，那岂不是比FPGA更好么?
|
s********e
发帖数: 425 | 8 asic制造成本高，制造周期长。编完硬件结构还要做版图，拿去生产制成真正的芯片等
等。
fpga由于是可擦写的，所以买一块fpga芯片来了就可以随时轻松实现不同硬件结构。
【在 s*****t 的大作中提到】
:
: body
: multiprocessor
: 为啥不用asic呢，那岂不是比FPGA更好么?
|
