作者FRAXIS (喔喔)
看板Prob_Solve
标题Re: [问题] 多点到直线的距离
时间Mon May 18 07:33:56 2015
: let ax+b-y = 0
: for (i=1,i<10000,i++)
: {
: dis = abs(a*xpoint[i]+b-ypoint[i])
: if (dis>dismax)
: {
: dismax = dis
: point = i <-------这是我的目的 想要找哪一个点
: }
我假设你已经测试过了，这部份是 bottleneck，而且这些计算是必须的。
已经有人建议用平行化了，我这边提供用单 CPU 的稍微加快的技巧。
dis 计算其实就只是 dot product + abs，这两个指令应该可以直接由
硬体支援，你可以编译成 assembly 检查一下。
读取 point 的时候是循序读的，所以可以使用 prefetch，或许可以减少存取时间。
计算完 dis 之後立刻作 comparison 会造成 data hazard，pipeline就堵死了。
你可以改成类似这样
dis = abs(a*xpoint[i]+b-ypoint[i]);
if (pre_dis > dismax) ....
pre_dis = dis;
这些技巧有没有用，取决於你的机器和资料，而且就算变快效果应该也很有限。
又因为你没有提供 profiling 的资讯，我也很难猜测到底是慢在哪个指令上，
只能凭我的经验去猜而已。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 50.133.134.181
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1431905639.A.9A6.html
1F：→ firingmoon: 想请教一下 程式改成这样的话不就抓不到最长距离了? 05/18 10:41
2F：→ FRAXIS: 可以吧 要稍微修改一点 05/19 00:06
3F：→ saladim: 不懂? 还是有比较阿? 05/23 13:28
4F：→ FRAXIS: 你要先了解计算机结构，才会知道这样有什麽差 05/23 19:24
5F：→ saladim: 我是知道(在这边不敢说了解 有老大哥在监视)..常见例子是 05/23 22:58
6F：→ saladim: WB stage之前另外一条pipeline要取同变数的值 方法之一就 05/23 23:01
7F：→ saladim: 有加入control logic让资料可以just-in-time 05/23 23:02
8F：→ saladim: 所以你这边说的是不要跟dist马上作比较? 05/23 23:03
9F：→ saladim: control-logic(==>forwarding technique) 不过这在存取变 05/23 23:07
10F：→ saladim: 数时有dependency时都可能发生...还是用profiling先? 05/23 23:08
11F：→ saladim: 补充一下 不是专研计结 请老大哥别再出来干醮惹 教学一下 05/23 23:40
12F：→ saladim: 让别人有所长好吗.... 05/23 23:40
13F：→ FRAXIS: 你说的方法是靠硬体来减少 dependency 的 delay 05/24 20:44
14F：→ FRAXIS: 我的方法是手动排除 dependency.. 05/24 20:44