n******7 发帖数: 12463 | 1 【 以下文字转载自 Programming 讨论区 】
发信人: nowhere7 (折腾), 信区: Programming
标 题: 并行可以降低计算复杂度??
发信站: BBS 未名空间站 (Mon May 4 17:53:30 2015, 美东)
最近看一篇文章,GPU计算的
用的deep learning
其中提到NN的计算复杂度是O(MN+LN^2)
M是输入的unit,N是所有layer的hidden unit,L是layer数
然后用GPU并行之后,就是M,N的linear时间复杂度了?
说原因是,计算两个N dimension vector的内积,用CPU是O(N)的,用GPU是O(1)
这是鬼扯吧?
我怀疑实际原因是,他们的GPU平台有近3K个core,计算中M在2000左右,N在几千数量级
所以他们是用core的数量K 抵消的一个N的复杂度
大家看是不是这样? | k*******2 发帖数: 4163 | 2 这是算法课没及格的说法吧。
并行再牛,也不能改变计算复杂度,因为计算复杂度是以N->无穷的极限情况来讨论的
。这种情况下任何有限的core都可以忽略不计。
唯一能改变计算复杂度的是发明一个新的更高效的算法。
【在 n******7 的大作中提到】 : 【 以下文字转载自 Programming 讨论区 】 : 发信人: nowhere7 (折腾), 信区: Programming : 标 题: 并行可以降低计算复杂度?? : 发信站: BBS 未名空间站 (Mon May 4 17:53:30 2015, 美东) : 最近看一篇文章,GPU计算的 : 用的deep learning : 其中提到NN的计算复杂度是O(MN+LN^2) : M是输入的unit,N是所有layer的hidden unit,L是layer数 : 然后用GPU并行之后,就是M,N的linear时间复杂度了? : 说原因是,计算两个N dimension vector的内积,用CPU是O(N)的,用GPU是O(1)
|
|