iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 3
0
自我挑戰組

當傳統演算法遇到新的計算模型系列 第 3

Day 3: 隨機存取模型(二) Word RAM Model, Part 2

  • 分享至 

  • xImage
  •  

如果我們想要儲存的資料都「短短的」, 如同今天這篇也短短的 ,一個字組可以同時塞入很多資料,這麼一來,我們可以藉由 CPU 的能力幫助我們快速運算。一個常見的應用是我們可以將一個向量直接塞在一個字組裡面,如此一來,常見的一些運算就可以不用每個維度分開計算。今天的主題便是要與大家分享如何對(被塞在同一個字組裡面的)向量進行加減法!

向量加減法

如果向量 1 的值是 (A1, A2, …, Ak), 向量 2 的值是 (B1, B2, …, Bk) 那兩個向量的和就是 (A1+B1, A2+B2, …, Ak+Bk)。在保證沒有溢位的情況下,直接做字組的加減法,就相當於兩個向量的加減法。以下是這個方法的原型概念圖:

https://ithelp.ithome.com.tw/upload/images/20181018/20112376uDG1uhLoHs.png

但是直接地計算我們會遇到兩個小問題,在此列出他們可能的解法:

  • 處理溢位:這時候只要多墊一個保護位元就好,不要把資料塞得太滿,留一些空的 bit 當作溢位的地方使用,最後再用位元遮罩把它變成 0 就好。
  • 需要借位:而進行減法時可能需要借位。為了不影響其他維度的數值,在進行減法之前,要先讓被減數的保護位元設成 1,減數的保護位元設成 0 (然後他們就分裂了啊啊啊啊是為減數分裂)

最後圖畫起來會長這樣:

https://ithelp.ithome.com.tw/upload/images/20181018/20112376OzEg8kmpMF.png

這邊有個重要的小問題:我們要怎從原本的字組把裡面的資料變成空一格的樣子?答案是,除非有特別的硬體支援,否則我們沒辦法輕易作到「散開」這樣的動作。但是,其實我們可以換個方法想:把一個字組拆成兩個字組!留下間隔就好了呀~只需要花兩倍的時間就能達到原本的效果!

明天來介紹更多的向量計算,比方說內積(拖稿一下科科~)


上一篇
Day 2: 隨機存取模型(一) Word RAM Model, Part 1
下一篇
Day 4: 隨機存取模型(三) Word RAM Model, Part 3
系列文
當傳統演算法遇到新的計算模型21
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言