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更好么?
|