|
v****s
发帖数: 1112 | 2 【 以下文字转载自 CS 讨论区 】
发信人: vicfcs (ML+CV), 信区: CS
标 题: 多线程优化求助！
发信站: BBS 未名空间站 (Sat Sep 11 08:49:35 2010, 美东)
最近赶deadline，一个巨大无比的运算，已经吃掉我supercomputer account上的 5000
core hour了。。。。
不是很复杂，就是运算量太大了，如附图。
每个步骤（一共要算大概500，000次）：
table 1 and table 2已经load到内存了，他们的长度各自是M, N. M,N can be upto 1
million. 要计算那个result table的每个cell，每个cell只要取对应位置的table1[i
,:], table2[j,:], 然后计算出resulttable[i,j].
现在我做的优化是把所有data都load到内存，然后搞2个for loop去sequentially
compute，但是这样太不efficient了，估计下周都没法搞完。。。大牛给出出主意，怎
么设计multi thread来加速！谢谢 |
|
g*****y
发帖数: 7271 | 3 哦，哪不对了？ 加两个一千多位的数，不得是（1000×常数）左右的运算量？ |
|
f*******a
发帖数: 663 | 4 不矛盾啊，呵呵。
临时数组的变化如下：
[1 6 11]
[2 6 11]
...
[5 6 11]
刚才数组长度不一致忘说了，结束了就置一个NULL或者减少临时数组长度都可以
[6 11]
[7 11]
...
[10 11]
只剩一个的时候直接导入即可
[11]
基本思路而已，运算量不大。欢迎讨论 |
|
f*******a
发帖数: 663 | 5 整体型的处理思路，很有意思。简而言之，不断的把单个数组插入至待输出的数组中。
个人感觉：随着数组数量的增加，这种算法的效率会随着长度的增加而降低。
另：关于我的算法的比较次数，好像有点问题。满打满算，15个元素，每次进入临时数
组，比较的就3个元素，只要比两次，最大15×2+第一次排序时的比较，不会超过40.如
果考虑数组被清空以及最后一个数组的情况，比较次数会更少。大致估计，这个算法的
运算量是O(logN * 总元素量)
~~~~有序插入
比较; |
|
X****r
发帖数: 3557 | 6 1.只看见循环，没看见递归。
2.你确定瓶颈在这个式子？每个循环你的delay就要不少时间吧？ |
|
l*******c
发帖数: 523 | 7 sorry，因为是DAC的关系，所以应该没有递归。Vb和Va分别是已知calibration table
里的值，look-up table就可以找到了。
你说的没错，那些delay time是由CPU的时间所决定的，这些瓶颈我没办法改。
我只是想知道，对于指数函数开平方的运算，有没有什么简单的算法，可以加快运算速度。 |
|
N***m
发帖数: 4460 | 8 你确定程序的瓶颈在指数开平方？
table
速度。 |
|
y***d
发帖数: 2330 | 9 if either kt or T is const, you can save the exp of them. |
|
b***i
发帖数: 3043 | 10 你难道不能提前算好,甚至利用编译器算好?
table
速度。 |
|
|
l*******c
发帖数: 523 | 12 本来是算好了，时间都满足spec.
可是现在客户改了标准，需要更快的时间内完成。不想改硬件，从新做板子了，看算法
上有没有什么可以提高的。 |
|
|
V********n
发帖数: 3061 | 14 我觉得公式的计算部分消耗的时间微乎其微，
倒是你这个output和delay很有可能是拖后腿的。
如果不需要每计算一次就output和delay的话，
那么把下面这两句尽量移到循环体外做：
DAC_Output(DAC_Set_Value, Dir);
Delay_us(DelayTime);
尤其是那个output，到底是去做了什么操作了？
不能先把结果放到一个数组里，全部算完了再输出吗？ |
|
l*******c
发帖数: 523 | 15 那个output和delay有特别的用途。为了抵消step response function 产生的ringing. |
|
V********n
发帖数: 3061 | 16 那你把下面三步合为一步，可以减少两次生成中间变量并寻址的动作，对减少时间有帮
助：
Data1 = Va * Va;
Data2 = deltaDAC * (1-exp(k/20));
DAC_Set_Value = sqrt(Data1 + Data2);
改成：
DAC_Set_Value = sqrt(Va * Va + deltaDAC * (1-exp(k/20)));
说实在的，现在的编程上很少会需要去考虑这么细微的区别。如果你真的对时间抠到纳
秒的地步，这么做也许会有点帮助。
ringing. |
|
|
b***i
发帖数: 3043 | 18 提前算好，就是利用编译器把运算结果放进数组，这样当然不用重新做板子，只是一个
代码的改变而以。象你这种就20个不同浮点数，放到数组里就是最好的方法。 |
|
|
l*******c
发帖数: 523 | 20 是这样的，客人随时可能给一个命令去任意一个channel (或者说voltage),而我这里为
了消除每次step response function 带来的震荡，每次从当前的voltage去到客户要求
的voltage，我都必须分20步走完。
打个比方说，从channel 1 到 channel 88, 客户可以从channel X 到任意一个channel
Y.这里面的组合太多了。所以说，我没法把每个情况都用array做，因为CPU internal
的flash memory是有限的。 |
|
c******e
发帖数: 545 | 21 Delay_us就空耗CPU时间？完全可以做点别的啊。也就是说，你在等DAC settle的这段
时间里，至少可以完成下个数值的一部分运算了 |
|
b***i
发帖数: 3043 | 22 把Data1的计算放循环外面，把1-e^kt这20个数放到数组里面提前算好，在循环中直接取数，少个指数运算。然后是否可以根据运算所花费的时间调整下一次等待时间？
另外你确信cache打开了？ |
|
d*1
发帖数: 24 | 23 这段code为什么要用if else? 不直接用绝对值？ |
|
N***m
发帖数: 4460 | 24 这个不会节省什么时间，而且Va Vb未必是大于0。
不过十有八九是正的。 |
|
t****t
发帖数: 6806 | 25 他这个显然是firmware, 跟一般的软件不同, 就是需要比较精确的时间和速度控制 |
|
|
t****t
发帖数: 6806 | 27 我理解你每一步输出需要延时, 但是你说的"需要更快时间内完成"是指减短这个延时的
时间吗?
如果不是, 那是指什么时间呢?
如果是, 那你可以缩短Delay_us(DelayTime)吗?
ringing. |
|
b***i
发帖数: 3043 | 28 假设他原来准备计算需要10微秒，每次输出之后等待20微秒。
他说客户改变了要求，结果每次计算需要40微秒，结果不等待都无法在规定时间内完成
任务了，所以需要优化。
解决方案很简单，把所有可以提前算好的算好，不要在循环里面计算。还有，单片机的
设置要正确，很多人cache没有打开，结果把时钟改快10倍都不够。很多情况，编译器
有问题，表达式的一种写法可以比另一种快10倍以上。多试试就好了。说必定他已经改
好了，所以不来了。 |
|
l*******c
发帖数: 523 | 29 “需要更快时间内完成” 并不是指的减短这个输出需要的延时，这个输出需要的延时
是精心计算和对每个器件都测试的，目的是为了消除震荡的ringing。这个延时跟器件
本身的震荡周期有直接关系。
我这里指的“需要更快时间内完成”是指器件对客户的响应。
比如说，客户需要2ms内器件就要有正确的反应。这个时间包含了器件recieve command
, check look-up table, 所有运算和计算，以及送出command. |
|
l*******c
发帖数: 523 | 30 我还没弄好呢。今天忙娃忙了一天。
明天回去公司查查看cache。 现在用的是atmel的MCU.时钟是40MHz。 |
|
l*******c
发帖数: 523 | 31 是这样的，如果说器件的震荡周期是T,那倘若我能在这1个T内走越多的步数越好（现在
是20步），当步数趋于无穷是，所有的ringing将被抵消。但由于CPU的限制，1个T内所
走的步数是有限的，而如果步数不够多的话，器件产生的ringing是没法消得很干净的
。所以我现在用的是3个T的时间。换句话说，我用震荡周期的整数倍的时间来换取走的
步数变多。
如果我能减少循环体内的时间，delay_us()的时间是可以减少的（例如从3个减少到1个
T）。
当然循环体外的时间能减少也是对客户的响应时间有帮助的。
了. |
|
l*******c
发帖数: 523 | 32 你总结的是对的。我开始想错了，总想着在不改变delay_us()的时候，尽量加快运算速
度。 |
|
t****t
发帖数: 6806 | 33 除了减少delay_us之外, 能做的就是common subexpression elimination了, 如果编译
器比较原始的话可能需要自己做, 所以你做的式子是
dac_set_value = sqrt(va*va + deltadac*(1-exp(k/20))) (有没有exp(k/20*T)?)
= sqrt(va*va + deltadac - deltadac*exp(k/20))
= sqrt(G - deltadac*exp(k/20))
其中G=va*va + deltadac, 另外如果内存够的话, exp(k/20)也可以查表, 一般内存会
比exp快一些. 也可以考虑一些近似的算法计算exp. 前提是你的20或者whatever步数是
个常数. |
|
t****t
发帖数: 6806 | 34 在本版混的都知道, 问问题的往往问的不是他们的本意. 最好不要替他们解释:) |
|
|
b***i
发帖数: 3043 | 36 一样的，如果1-exp(k/20)放表里面，乘法，加法，开方
G的计算反正是循环外面的。
还是楼主自己自己才能说清楚，每次等待的时间改了就行了 |
|
a****l
发帖数: 8211 | 37 比如说,如果现在的电压是0V,目标是跳到10V,你现在就让输出20步,每步上升0.5V,这样
的做法和你的做法会有什么样的不同? |
|
t****t
发帖数: 6806 | 38 我觉得线性变化的电压, 从频谱上来看通常不是件好事. |
|
t********e
发帖数: 1169 | 39 1) 不要用matlab写400b的loop...
2）20m lines完全可以全部放入内存，用hash都行了, 40m的运算量 |
|
c*********e
发帖数: 16335 | 40 godaddy.com?
app。
learning |
|
|
g*****g
发帖数: 34805 | 42 啥写的？看看Google AppEngine？
app。
learning |
|
l*******s
发帖数: 1258 | 43 还没写好。
用java
数据库有可能用mysql，或者干脆不用数据库。 |
|
|
|
d****n
发帖数: 1637 | 46 server 只管数据，
运算用javascript.消耗用户的资源。算完了发给server.
就看你有没有勇气用js写ML了。
缺点，open source, 慢 |
|
l*******s
发帖数: 1258 | 47 没有勇气。
不管啥语言 就算是c实现的ML模型 在load进model文件时 至少要几秒 更不用说js了
这个时候 客户手机基本就停止响应了 |
|
w***g
发帖数: 5958 | 48 找个colocation data center，自己攒好机器后放过去就行。也是几十块钱一个月。我
用的是这家http://www.nexcess.net/. 需求跟你完全一样.
我很好奇双CPU+64G内存怎么样<$1000能搞定。
app。
learning |
|
|
|
