誰也不能阻擋我想亂寫的心: 2014

2014年12月30日星期二

Error-correcting codes 錯誤更正碼，ECC，BCH

A想傳送"1"給B，但是怕bit-flip，這時候就是 Error-correcting codes (ECC) 登場的機會啦。

首先，先把"1"(稱作message)用 coding 加以保護 (方法有很多種，先用 Repetition Coding 當範例)，經 Repetition Coding 之後 "1" 變成 "111" (稱為codewords) ，這樣當B收到101，就會猜想中間的"0"應該是bit-flip。

如果運氣很差，剛好flip兩個bits (變成100) 怎麼辦? 那就沒救了，將會判斷成收到 0's。
想要這種出錯率降底的話，就把"1" 變成 "1111111111111.....11111111"
越多越爽，但傳輸率(效能)就爛到哭。

總之，是有tradeoff的，Repetition Coding 很鳥，用來當範例方便而以。有機會(or never)再介紹其他比較威風的 ECC，像是BCH或是LDPC。

腦補-------------------------------------

A BCH code with a higher error-correcting capability (and higher overhead) is the [8360, 8192, 12] code, which can correct 5 errors or detect 11 errors.

8360是codewords
8192是message
所以redundancy的部份就是 8360 - 8192 = 168
多了這168 bits，傳輸變成原本的 8192/8360 = 0.979倍

小迪買了一個很醜的kitty包
配色就很有問題、裝了一堆極少用的東西，重翻了
背帶還只有一公分細…超難揹…

除了他是kitty的之外，想不出來有什麼值得買的地方
QQ

但這可不能說~~~ 呵呵

2014年12月26日星期五

國科會計劃到尾聲
用心寫的時候真的學到很多
怎麼看待這件事決定成果的品質
有些時刻居然能沈浸在過程

合作也是開心的，看著大家邊學邊產出
猜想他們應該也有些成就感吧呵…

2014年12月10日星期三

馬來西亞day1

已經不知道，倒底是真有點無聊，還是行程排的不好…
第一天心得:
1 靠以為小小的地方，拉車都還要40~60分鐘

2 交通差…塞車塞的好飽
3 東西甜+鹹，好下飯

4 hilton雙樹飯店wifi龜毛死了…去你媽的last name+room number...
對老人們真的太不方便了
5 導遊好吵…，不知道是我的個性還是怎樣…聽到一直重複，一直沒內容，質很低的談話就會有點煩…好想叫他停一停，或是講重點…或是多介紹窗外事物就好

2014年12月9日星期二

ad sense

前不久，無聊想把自己的blog加ad sense，哈哈實驗看看
結果他說我的blog內容不夠豐富，都是垃圾不給過…
原來…他有認真看的blog耶!!!

原來，不是隨便伸請都會過喔哈哈

2014年12月2日星期二

與教授們的meeting，腦子真的要很清楚
明明不難的東西，但不給你思考的時間，咻一下就過去…

解法: 平常就該多思考~~ 多準備~~

2014年10月29日星期三

痛痛快快的打了四場
先給自己打75分，滿意
內野手套的感覺不錯，傳球也有穩下來了

打擊好壞就差有點多，要穩定揮擊真的不容易
可能是腳不夠穩吧我猜

氣氛不錯，大家有想贏，多虧有mars這隊強度不錯他們向心力也夠…

多多保重身體，持續進步

能跟兄弟喝一杯，聊聊天
十分充實又滿足
可以暢所欲言的place，的人，棒

當一直碰到上鎖的門人是會累的

兄弟看似沒那麼美滿，但最後真的就是這樣了嗎
不能自己投降啊

2014年10月21日星期二

情況1:

原本板子上有SPI interface可以用，但因為某些原因，被佔用去，
所以解法就是『用GPIO模擬SPI』。
要先K一下SPI的spec，然後按他的規則，使用GPIO去『下cmd，丟data』等…
例如: 先丟 xxx，過 20 ns之後才能丟 ooo

情況2:

承上，板子上沒支援 nanosecond等級的timer，但又必需要用。
解法就是: 先用cpu frequency去推出 1ns可以做幾個instruction （假設CPI為1）
假設算出來是 1 inst/ ns，那當我想要有20ns的delay，我就用loop去做20道指令。

ps1: nanosecond timer，linux某個POSIX版本之後好像有support，但猜測是library沒porting上板子，所以才用此替代方案…，而且也還沒成功 XDDD。

第三次產檢

車上安胎中

羊水不夠你還敢笑

hahaha，照照囉

哥以一個外行的身份就發覺羊水好像有點少…
fq....swim的空間不夠啊

就像是電流急急棒一樣…生個小孩

一關一關過，中途忽然gg就會gg

----
開心，尤其是看到他/她的存在的那一刻，聽到他心跳的那一刻…
雖然中途被很像賣藥的護士小姐推銷產檢，一度把08的喜稅弄掉一點…
但最後她有補上恭喜兩個字，才有稍稍回神

----
呼…人生她媽的又進階了…

每當快沒有生活，重心，目標
硬是看部電影總能帶給我新的東西，想法，感觸
不確定是電影劇情，還是有個地方讓人從現實生活逃進去

我相信是前者啦!! 我要他是前者! 哈哈

2014年9月2日星期二

vCacheShare: Automated Server Flash Cache Space Management in a Virtualization Environment

當多個vm要share一個ssd cache時，平均分配cache space不是一個好方法，因為每個vm上的workload特性可能差很遠。

這篇，自動detect特性(1) reuse distance (2) read intensity，然後弄一個cache utility model (i.e., 給你x的空間，你可以得到y的好處)。
然後利用這個model去找到最佳的空間分配比例。

qNVRAM: quasi Non-Volatile RAM for Low Overhead Persistency Enforcement in Smartphones

為了persistency，有些技術會造成額外的IO(e.g., logging, double write)，原因是從RAM寫到primary storage時會出事。

作者認為…手機都有電池，所以覺得『電池+DRAM』就可以變成"假的"NVRAM。有了NV的特性，就可以砍掉一些為了persistency而生的手段(e.g., data不用先寫到log area)

後記:
最後的Q&A，很多人關心"電池沒電的問題"，"電池整個沒電會不會系統爆掉…"，他一來是說可能是個issue，又說現在人的手機不太會沒電…

2014年8月29日星期五

free_irq
request_irq

2014年7月29日星期二

3gpp supplementary service 閱讀順序

分享一下最近看 3gpp spec的心得(最主要是閱讀的順序)
一句話: top-down。

以supplementary service中的 communication waiting (TS24.615)為例:

1 先看最後面的signaling flow。先了解全貌，top-down。例如下圖2a，你才會知道AS會做的事是: 『查看approaching NDUB，然後用猜的大概是: 『看看這通call會不會被擋，而進入call waiting狀態(例如: callee正在講電話)』。
再例如 6a. 你會知道有插播進來的時候，可能會做的事，e.g., 按下保留(HOLD)，要不就是掛掉目前這通電話，然後接插播的這一通。
『approaching NDUB』這個暫時不知道怎麼做沒關系，再往下查就好。

2 整個整個全貌之後，再往前對應，像是下面這個case，是在說『接到插播時該怎麼辦』
2a stop timer → 話機不需要一直叫…
2b 停掉CW indication → 話機不需要一直叫…
2c 看你怎麼處置插播。

2014年7月20日星期日

IMS, 3GPP, VoLTE 徵友

-----------
最近在搞的東西關鍵字如下: IMS, VoLTE，3GPP、precondition、sip forking process、IMS supplementary service。

PO此文的一個目的有一個是想找可以一起討論的同好(或是同樣陷入spec地獄的人哈)
如果你看到此文，有興趣可以聯絡我。

明天計劃: 搞定 SIP precondition。最後四天就有一個大報告囉，東西真的很多呢…
以為綽綽有餘，結果居然有點吃緊…，沒有再最一開始就弄清整個份量，真是一個失誤。

2014年6月26日星期四

paper sharing

1 這是很好的conference喔
2 motivation: ECC要花點時間，他發現如果SSD是cache，好像可以不用每次都用那麼強的ECC (越強越慢)，因為就算要讀的page整個壞，也可以去下一層拿 (i.e., primary storage)
3 solution: "有時候" 用弱ECC

FlexECC: Partially Relaxing ECC of MLC SSD for Better Cache Performance
https://www.usenix.org/system/files/conference/atc14/atc14-paper-huang.pdf

2014年6月22日星期日

Adaptive Paired Page Prebackup Scheme for MLC NAND Flash Memory

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 33, NO. 7, JULY 2014

problem: 有時寫 MSB page會弄壞 LSB page (同cell)
proposed: backup LSB page

2014年5月16日星期五

C程式面試題目整理

面試考題

1 explain #error

ref1
ref2

簡單地說: compiler看到它就會停掉啦~
為什麼要停掉? ref3

2. explain "struct" and "union"

struct → 所佔記憶體空間為 member 相加
union → 所佔記憶體空間由最大size member決定

note: 所以union的member同一時間只會最多出現一個

example:

3. 修飾字 (const, volatile, static......)

explain "volatile" and "const". can we use "volatile" and "const" in the same variable ? can we use "volatile" in a pointer?
最能幫我理解的就是舉 status register來當例子，如下:

"const volatile is used for defining Hardware Read-only Registers.example CPU status registers.
the value of these registers are read-only but the
value of these registers may change depend on the processor status. Thus const volatile variable can't be altered by the programmer but by the Hardware
" ref

中文版:
"volatile變數代表其所儲存的內容會不定時地被改變，宣告volatile變數用來告訴編譯器 (Compiler) 不要對該變數做任何最佳化操作，凡牽涉讀取該volatile變數的操作，保證會到該變數的實體位址讀取，而不會讀取CPU暫存器的內容 (提升效能) 。舉個例子，某一硬體狀態暫存器 (Status Register)就必須宣告volatile關鍵字，因為該狀態暫存器會隨時改變，宣告volatile便可確保每次讀取的內容都是最新的" cited from ref1

--------------------------------------------------

→ 何時可以用const?
1 co-work一個function時，有時會用傳參考的方式，但傳參考有點風險(別人可以不懂，就直接改了某個不該改的變數) ，要避免的你可以給這種 prototype:

int foo(const int &bar)

------------------------------------------------------------

幾個用法: (規則 * 和 & 左邊形容指向的值，右邊是本身)，for example

const int a=100; // 沒有*和&，所以簡單: const和int通通是形容a
int const b=100; // 同上
const int *a=&b; // 套規則: * 左邊的const和int是指向的值，所以a指標指向的值不能改，*右邊的是本身，所以a可以改(沒有const和int修飾到它)
int const *a=&b; //同上
int * const a = &b; //套規則: * 左邊的int是修飾a指向的值，所以，值可以改(因為沒const嘛)，*右邊的是本身，已被const修飾到了，所以a不能改
const int * const a = &b; // 也不用套三小規則了啦，都出現兩個const，就通通都不能改了啊!
const int &a=100; ///套規則: & 左邊的int是修飾a指向的值，值可以改(因為沒const嘛)，&右邊的是本身，所以a可以改(沒有const修飾到它)

note: 因為被const修飾到的東西未來都不能改了，所以宣告時要初始…不然就沒什用途了…(除非你希望該值是0?)

4. bit operation

example1:

可能是這樣解啦:

1 第四行和第五行好像可以"約分"一下

→ 第5行會變成: v = (v1&(~v2)) |v2

再變成→　(V1|V2) & ((~V2) | v2)

→　＆的右邊是1，所以V 就是V1|V2

example 2

a) #define set_bit(x, nth_bit) x|(1<<nth_bit)
b) #define clear_bit(x, nth_bit) x|(1<<nth_bit)
REF

? 難道要先展開成二進位? 再慢慢算?

5. ??

要考你 a+1 和 &a+1。
第一種的+1一次是跳一個int的大小(i.e., 4bytes in 32-bits cpu)
第二種的+1一次是跳一整個array的大小 (i.e., 4*5=20 bytes)

更清楚的說明在這 (see also this), 可以看到: a和&a值雖相同，但type不同。
所以 +1 時，要加的是 type的大小

所以*(a+1)是2，(*p-1)是garbage (unknown value)

答案: typedef void(*pf)(char *);

第一行那坨，眼睛只要看著 void (*)(char *)就好
它是一個function pointer的type

只要記得，function pointer的typedef 是把new type的name塞在第一個*後面

不要像我一開始還寫成:

~~typedef void(*)(char *) pf~~

先說: 我還看過規定 + - * /都不能用的。

解法1: 可以利用3的倍數的特性: 每個位數相加起來依舊是3的倍數。
例如: 369是3的倍數，那3+6+9=18也一定是3的倍數。
『每個位數相加』的動作一直做到只剩個位數為止，如上例 18還不是只剩個位數，所以繼續，1+8=9。最後的結果只要是3或6或9 那該數就是3的倍數。

9. explain lvalue and rvalue

2014年5月8日星期四

how to add a new parameter into .parv file in disksim

1 add your parameter in ssdmodel/modules/ssd.modspec as below:

2 declare a new variable to take the value of the parameter

3 make
note: this will generate ssdmodel_ssd_param.c
ssdmodel_ssd_param.h
ssdmodel_ssd_param.tex
modules.h

-----------------
contributed by Wade in oslab of CSIE in NCKU

2014年4月29日星期二

Play lo

Tomorrow

Go to play with the paper unsubmitted

Haha

Play is very important

2014年4月7日星期一

用simplescaler來量某段code的指令數的時候…發現了一個怪怪的地方
→ 每次執行指令數都會不同

什麼鬼? 今天再來找找看問題所在

2014年3月19日星期三

評估某段code的cpu overhead

1 把演算法寫成 code
2 cross compiler成 ARM binary (因為SSD controller中多半是用ARM)
3 用SimpleScaler來算指令數

------------------------------

目前的code(假設10個users)算出來如下:
1 dispatch request → 201 道 Inst. → 0.25 us
2 credits charging → 52 道 Inst. → 0.06 us

ps: 假設800Mhz的cpu, CPI = 1 (i.e., as BLAS), no cache。

0.25us 僅是完成一個page read 的 0.2% (i.e., 0.25/(25+100))
或僅是完成一個page write 的 0.08% (i.e., 0.25/(200+100))

2014年3月18日星期二

libgcc_s.so.1 找不到， error while loading shared libraries libgcc_s.so.1

為了裝 arm-elf-gcc 不知道為什麼把 shared library搞壞了

很多程式都說 error while loading shared libraries libgcc_s.so.1

用locate指令找了一下 libgcc_s.so.1 發現有三個地方有…

一開始單純的想法是直接把他copy到 /lib之下，但是事情那麼簡單…

為了不負爺爺的聲望，又做了一些check...最後很搞笑的發現剛剛copy的libgcc_s.so.1

是ARM binanry... (我是用file cmd去看的)

最後解法: 抓別電腦的 libgcc_s.so.1過來放進去 /lib中

2014年3月12日星期三

profiling ARM binary code

先從這下載 ARM-DS5 (好像有試用版啦)

--------------------------
網友

I don't know any free ARM profilers.

You can try ARM RVDS 4.0 Pro. It has a good profiler. And you can use emulator instead of real hardware with it. It simplifies some things, but you'll not receive information about cache-misses/memory-latency, and results may differ from tests on real hardware.

The price of RVDS is high enough. You can try trial for 30 or 45 days, maybe this will be enough to profile all you want.

---------------------------

Oprofile
可以裝一個在ARM機器上，然後跑你要profile的程式時，再同時run Oprofile去監控
和gprof不同的是:

因为gprof只是针对应用层的分析，而oprofile是通过硬件（CPU）本身支持的性能计数器进行的性能分析，贯穿内核到用户应用程序，很有参考价值 URL

2014年3月11日星期二

idea - prefetch in SSD

把read request所要的data從快gc的channel先prefetch出來…

好處: reduce latency

方法:1 prefetch 時 prefer 快 GC的 channel
→ 怎麼判斷 "快GC" (elem utilization, pended wt req)
→要prefetch 什麼 data ? (from history, seq ratio)

2014年3月2日星期日

實驗log IO trace的錄製 0223

模仿PVR (using intel open tool kit)，以下是參數

1st try
s i cap qdep wr wrnd rrnd str wrsz rdsz warm test bw iops lat
0 0 4300 8 100 5 100 1 32 32 5.0 5000.5 17.61 564 14.19
sinhome-desktop: sample 0 iter 0: (test) 88059.59 MB in 5000.46 sec 17.61 MB/sec

95% seq
32KB
address space 約4.5GB

2nd try

s i cap qdep wr wrnd rrnd str wrsz rdsz warm test bw iops lat

0 0 4500 8 100 0 100 1 32 32 5.0 3000.3 55.84 1787 4.47

sinhome-desktop: sample 0 iter 0: (test) 167530.88 MB in 3000.31 sec 55.84 MB/sec

post-processing to disksim format

cat inteltoolkit_trace.out | awk '{print ($1-1393167501.968118)*1000" ""0"" "$3" ""64"" ""0"}' > PVR_32KB_5GB.dis

note: output中的address單位是byte !!!

_________________________________________________________________________

postmark的參數

set size 65536 131072

set number 15000

set transactions 5000000

set location /media/benchmarkTarget2

set read 32768

set write 32768

set buffering false

set bias read -1

set bias create 5 // 設5會讓blktrace output長超快，而設10就超慢，待找問題

32KB
address space 5GB

post-processing to disksim format

cat tmp3 | awk '{print ($4-6.474369353)*1000" ""0"" "$8" "$10*8" ""0"}' > pm2disksim

加速user1

cat PM_32KB_5GB+PVR_32KB_5GB.dis | awk '{if($6==1) {print $1/15" "$2" "$3" "$4" "$5" "$6} else print $0}' |sort -g -k 1 >PM_32KB_5GB_15m+PVR_32KB_5GB.dis

2014年2月19日星期三

Exploiting workload dynamics to improve SSD read latency via differentiated error correction codes

goal: 加快 read page latency (如圖最下方)

方法:
如圖最下: 有點像切pipeline。一個pages分成多個segment，如最上方圖(b)，如此，讀第二個 segment的時候就可以同時幫第一個pages做ECC解碼的動作。

concern:
ECC size 均分到各個segment之， ECC的能力會變弱…(e.g., 原本能允許整個pages發生16bit的error，現在每個segment最多承受4bit)。所以要想辦法降低 error rate。方法: 降低寫入的速度，來提高reliability (也就是減少error rate啦)

how about write latency ? 不就犧牲太多??
配套 1 加RAM當 write buffer
2 只在有idle time的時候做"慢速寫入"
ps: idle time指的是host沒發request來的時候，此處是用估計的…非即時偵測。

2014年2月17日星期一

用blktrace 錄 postmark

1 準備一個partition (就是讓postmark噴 request過去的啦)。

a. what size of partition
b. what filesystem

e.g., sudo postmark xx.conf

2 打開blktrace (準備攔截噴到那個partition的IO)
例如　　blktrace -d /dev/sda3
note: 如果你硬要自己取 blktrace outputfile的名子，要小心…。e.g., 我取『pm_64- 128file_32rec_5000WTx_5GB.blktrace.out』這個名子 blkparse 都失敗…

3 新開一個terminal來啟動 postmark →設參數 (看你想要什麼樣的workload) → run
這樣postmark就開始噴request了

note: 跑postmark前，最好先清空cache。參考網址

ps 每次設參數很煩你就寫一個 .conf 檔，然後用 "load" 載入
note: 設定postmark file數時(e.g., set number)要確定沒超過 partition size，不然可能出現權限問題

4 等到噴完用ctrl + c 終止 blktrace ，然後再同一個目錄下會出現很多log檔~

5 用 blkparse 去解碼，不然你是看不懂那一堆 log檔的
e.g., blkparse sdb4.blktrace* > pm64_128kbfile_32kbrec_5GB.dis.tmp

6 post-processing if needed.
像是後製成 disksim可以吃的格式。

---------
ref: http://www.cse.unsw.edu.au/~aaronc/iosched/doc/blktrace.html

web2 +mp3 結果圖分析

1 原本paper上的圖有開work-conserving，要把他改成新圖。
而且只放前100sec (也就是有灌滿的期間)

2 在該段期間內，QDI差異約6~7倍 (當然，承受較多的user受到干擾)

3 無GC , so no GCI

2014年2月10日星期一

install linux

====partition plan=========
/ : 30G SSD
/boot : 1G SSD
/tmp: 50GB HDD
/home : 300 HDD
swap : 2G SSD
tool: http://www.junauza.com/2012/04/best-disk-partition-managers-for-linux.html

choose best server

apt-get update
@ 套件管理需知（建議先看，搞懂dkpg, apt, yum 等term...）

bison/flex/geany/gnuplot/htop/virtualbox/filezilla/terminator/inteltoolkit/postmark/chrome

pae

sudo apt-get install linux-generic-pae linux-headers-generic-pae

prompt color style

keyboard hot key

安裝insight
http://outsidenote.blogspot.tw/2013/03/install-insight-debugger-on-ubuntu.html

ref: http://sleepingwolf.pixnet.net/blog/post/19509749-%E3%80%90%E8%BD%89%E8%BC%89%E3%80%91%E5%AE%8C%E5%85%A8%E7%94%A8-linux-%E4%BE%86%E7%94%9F%E6%B4%BB

2014年1月28日星期二

『筆記』disksim在超急速trace下跑很慢，如何去加速

『筆記』disksim在超急速trace下跑很慢，如何去加速
1 先用gprof去查可能的bottleneck function
2 以title為例，bottleneck都在處理queue(大多是 insert，get或是delete )
3. 本次發現 logorg_addnewtooutstandq()是bottleneck。原因是裡面有個while loop的功能只為了找到某linked list的tail。解法是: 『維護一個pointer永遠指向outstandq的tail』。注意: outstandq有很多個(也就是有很多條linked lists)。
4. 注意: tail pointer指向的東西(假設是temp)可能會被移除，所以temp被移掉
時最好是將tail-pointer更新成 temp->prev，不然下次addnewtooutstandq時如果發現tail-pointer還是null，就必需重找…(就沒加速到了啦)

5. ps: gprof只有當程式全部跑完才會產生 gmon.out

2014年1月12日星期日

自評

me
無法擔大任
尚無夢想
愛找理由

do it for myself !

訂閱：文章 (Atom)

2014年12月30日 星期二

2014年12月26日 星期五

2014年12月10日 星期三

2014年12月9日 星期二

2014年12月2日 星期二

2014年10月29日 星期三

2014年10月21日 星期二

2014年9月2日 星期二

2014年8月29日 星期五

2014年7月29日 星期二

2014年7月20日 星期日

2014年6月26日 星期四

2014年6月22日 星期日

2014年5月16日 星期五