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)
|
|
