Re: [問題] 多點到直線的距離

[FRAXIS (喔喔)]

: 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://www.ptt.cc/bbs/Prob_Solve/M.1431905639.A.9A6.html
→ firingmoon: 想請教一下 程式改成這樣的話不就抓不到最長距離了?
→ FRAXIS: 可以吧 要稍微修改一點
→ saladim: 不懂? 還是有比較阿?
→ FRAXIS: 你要先了解計算機結構，才會知道這樣有什麼差
→ saladim: 我是知道(在這邊不敢說了解 有老大哥在監視)..常見例子是
→ saladim: WB stage之前另外一條pipeline要取同變數的值 方法之一就
→ saladim: 有加入control logic讓資料可以just-in-time
→ saladim: 所以你這邊說的是不要跟dist馬上作比較?
→ saladim: control-logic(==>forwarding technique) 不過這在存取變
→ saladim: 數時有dependency時都可能發生...還是用profiling先?
→ saladim: 補充一下 不是專研計結 請老大哥別再出來幹醮惹 教學一下
→ saladim: 讓別人有所長好嗎....
→ FRAXIS: 你說的方法是靠硬體來減少 dependency 的 delay
→ FRAXIS: 我的方法是手動排除 dependency..