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