Sunday, May 6, 2018

Computer Systems

這學期我修了影響我很深的三堂課,

operating systems

distributed computing systems

interconnection networks

每一門課中 都接觸到了大量相關領域的論文


在系統這個領域

Trade off 和 performance 一直是主要的課題

或者說 how to utilize the resources.


網路與系統 探討的是工程問題

也就是沒有最佳解或是唯一答案

會隨著參數或是硬體設備更新

有所突破

同樣的設計執行不同的程序也會有不同的表現


這些沒有標準答案又開放的學科

一開始學習會很挫折

通常研究一個問題時

切入一個點時需要做很多假設

先想好想要改進的點

然後試想可能可以改進的情況

同時間還要注意更動是否符合原本的設想

否則可能會在解決問題的同時製造出另外一個問題


目前我掌握這方面還是有限

只能從案例中學習

但是在分析一個系統時

已經能夠用比較全面的角度去切入

以及考慮不同情況

Thursday, February 22, 2018

Paxos Algorithm

最近上 operating systems, distributed systems 的課看了一些論文,

發現網路上中文資料相對英文還是少了一點,

所以想嘗試以初學者的角度解釋一些概念。


Paxos Algorithm 通常用在容錯分布式系統 (fault-tolerant distributed systems) 用來實現 Consensus Algorithm.

先來討論一下為什麼需要分布式系統。

假設你是一家銀行,擁有帳戶和餘額。

a. 今天我去領錢,機器當機了

1. 如果只有一個主機存資料,
-> 所有帳戶餘額會不正確

2. 如果有多個主機
-> 根據沒有當機的主機,recovery


b. 但是如果有多個主機,

餘額減少的那個主機,

如何更新餘額給其他主機知道就是 Paxos algo 討論的問題


核心概念:

每個process(node) 有 proposer, acceptor, learner.

proposer 送request 給其他 acceptors. (acceptors 有可能會收到多個)
prepare_request(n)

acceptors 會選收到最高的 n 的傳回去proposer
response_to_prepare_request(Proposal[m, w]/None)

proposer 根據 response 選出 MAJORITY 之後傳給其他 acceptor
accept_request(proposal[n,v])

acceptor 傳給其他 learner
decision(proposal[n,v])

learner 把收到的value寫到系統裡。

最終全部的process 都會有更新過的value.


這些步驟裡面有寫可以簡化,因此 paxos 還有其他的變種算法。


references:

https://www.youtube.com/watch?v=UUQ8xYWR4do
http://lamport.azurewebsites.net/pubs/paxos-simple.pdf

Sunday, January 28, 2018

Structure Padding in C/C++

這篇會簡單提到 C/C++ 裡面的struct padding.

前幾天面試有遇到相關問題, 沒有研究過 compiler 當場回答不出來

之後在網路上查了相關資料並且用clion測試後整理出結論:

structure 是 C/C++ 用來把不同data type 打包起來

struct car {
  int serial_number;
  long long year;
  char type;
  char name[8];
} car_t;

問題 1:  sizeof(car_t) 有多大呢?

這種問題,是半開放的問題

需要做很多假設

1. 第一件事一定要考慮 32/ 64 bit machines.
這個或許會影響 pointer size 的不同. 為什麼我說也許, 因為platform 也會影響 pointer size.

2. 第二件事是compiler,有些comiler 可以optimize. 我不太懂就不多贅述了

考慮完之後我們可以計算


  int serial_number; -> 32 bits -> 4 bytes
  long long year; -> 64 bits -> 8 bytes
  char type; -> 8 bits -> 1 byte;
  char name[8]; ->  8 * 8 bits -> 8 bytes

得到 4 + 8 + 1 + 8 = 21 bytes.

這並不是正確答案

在底層實作上會加上padding.

通常會找出struct 中最大的 bytes. 然後一個一個往下放進去

以上述例子

最大的element 是 8 bytes. 放不下的時候要補足8 bytes 再往下做

int serial_number; -> 4 bytes
#### padding 4 bytes
long long year; -> 8 bytes
#### padding 0 bytes
char type; -> 1 byte  +   char name[:7] -> 7 bytes
#### padding 0 bytes
char name[8:]; -> 1 byte
#### padding  7 bytes

最後總共會是32 bytes.

依照上述的規則如果我們把順序調整

struct car {
  int serial_number;
  char type; // change the order
  long long year;
  char name[8];
} car_t;

int serial_number; -> 4 bytes
char type; -> 1 byte
#### padding 3 bytes
long long year; -> 8 bytes
#### padding 0 bytes
char name[8]; -> 8 byte
#### padding 0 bytes

總共會用到 24 bytes

在底層C/C++ structure 非常常用

如果可以減少 size 也許會對performance有很大影響


https://www.ibm.com/developerworks/library/l-port64/index.html
https://www.geeksforgeeks.org/structure-member-alignment-padding-and-data-packing/







Sunday, December 31, 2017

ECE MS 課程

過了一學期,

記錄一下在美國MS跟BS就讀的差別

美國碩士有non thesis 學程 修完課就可以畢業

這是我以ECE, Computer System Software. CS 的角度去看



先從碩士課程開始好了

我覺得主要分四類


一種是通識類型的

這種類型的課跟大學部的課沒有太大區別

目的通常是把碩博士的知識水平拉到及格線

也是大家所說的涼課/水課

這種類型的課程大部分的資料都可以在網路上找到

很適合有基礎但是有觀念不熟的人去聽



一種是Project 為主

用Projects 帶概念並且實現

通常會要求團隊合作

學習強度的深淺會跟隊友還有自己投入的心力有關

這些Project也可以成為面試的相關經驗

我認為這類課程是最接近我在實習時做的事情

缺點是花了心力的項目也許對未來的工作沒有直接關係



一種是研究導向

這類課程是BS不會接觸到的

上學期修的課要求每周同學輪流上台講解一篇Paper,

用現今技術去帶概念

例如這星期講 Dynamic Analysis

老師會選幾篇相關的paper幫助理解

這種課程比較像是幫助論文型學生找研究方向和題目

也可以當作練習presentation

培養在一大串廢話中找重點的能力


最後一種比較特別

通常是一個教授擅長的領域

例如 Advanced XXX, 或是 XXX Theory

這種課程比較容易跟找工作脫鉤

比較是為了興趣而學的



在大學需要有目的去選課

通識加上大部分專業課程有prerequisite

課表沒有想像中那麼彈性

在Georgia Tech ECE 很容易被迫為了學分畢業門檻去修相關課程

我算是修了很多有趣的課程 沒有特意去挑涼課

我很多同學他們課表都很像因為涼課大家皆知

我在通識方面修了

日文 靜力學 剛體力學 美國歷史 體育 現代物理

在選修上

嵌入式系統 網路 計算機結構 演算法 機率


在BS如果是將來想走研究路線

可能大學就會去做專題去實驗室打雜

修一些比較理論的課

跟教授套關係

同時洗GPA準備申請




反觀碩士課程

我個人是認為碩士沒有所謂的方向

比較像把BS 有興趣但是沒學完的東西學完

選課通常也比較自由

Monday, December 4, 2017

Dash Python API 中文簡介

這學期的雲端計算 project

用了 Dash 當作 front-end

這是 Dash 介紹

Written on top of Flask, Plotly.js, and React.js, Dash is ideal for building data visualization apps with highly custom user interfaces in pure Python. It's particularly suited for anyone who works with data in Python


整個架構需要寫一個 app.py

可以包含 plot graph 還有 html layout.

比較進階的寫法是 live updating components

這個 feature 可以設個 interval


讓網站在一個時間內自動update

這裡是簡單的example, 提供兩種寫 graph 的方法


https://gist.github.com/boalinlai/7da3aac5a73cd45e046c88bdaae016cf

layout 裡面用 id 去指定function

call back function 裡面要有 data, layout

然後設置一個 time interval

最後

指定完 host 還有 port 之後

sudo python app.py

Sunday, November 19, 2017

Cloud Computing AWS (雲端計算)

雲端計算會這麼實用,

在我的觀點主要有兩類,



第一點是計算量的負擔,

傳統的計算必須先空出硬體資源

造成過多資源空轉

雲端計算能夠把計算量分散

同時實現

用多少拿多少的硬體支援



第二點是簡化開發流程

最早以前要開發一個環境

要買主機 把作業系統(windows, linux macos) 裝進去

再來用虛擬機 (virtual machine)

直接從電腦上用軟體模擬出硬體空間

到現在

可以用AWS 直接拿一個虛擬主機來用

接來會針對我有興趣的AWS 技術做介紹

Wednesday, October 4, 2017

Information Theory (資訊理論)

這篇文章會記錄我對 information theory 的了解。


==== Entropy ====

先來討論所有機率是平均分佈


A 有一個硬幣,正面反面出現機率各一半

A 擲了一次硬幣 現在他想把結果告訴 B

但是A 和 B 不可以直接溝通 只能透過其他方式

這些方式有共通點, 只能有兩個狀態

例如:聲調高低, 顏色深淺

我們可以把兩種狀態用 0, 1 來表示

在硬幣的例子,我們可以用 0 代表反面,  1 代表正面

A 擲了2次硬幣 2 次都是正面。

A 現在只要用兩個 1 就可以讓 B 知道結果了

現在我們可以換一個角度想兩種狀態的意義,

A 給 B 0 或 1
可以想成 B 可以問 A 一個問題

A 會回答 0 或 1 代表 是或否

這個例子B 問 A 1個問題就可以知道 1 次結果 



2 個問題 2 次結果


現在考慮骰子 x  = [1, 2, 3, 4, 5, 6], p(x) = 1/6

我們一樣只有兩種狀態

A 丟了 6

現在 B 需要什麼資訊才能知道 A 拿到 6 呢?

a,  B 可以問 A, 是 1,  是 2 ,  是 3 ... 是6?

考慮最壞結果

B 必須問 A 6 個問題

但是  B 也有可能第一次就問到正確結果

 B 實際上不能確定他到底要問幾次才知道


b.  B 可以問A:這個數字是否是 {1, 2, 3} 
這樣子的話我們一次可以把一半的可能去除

1 -> 01
2 -> 001
3 -> 000
4 -> 11
5 -> 100
6 -> 101


由於 log2(6)  = 2.58 不是整數,
我們需要 3 個問題 來確定數字是什麼




a, b 的差別:


假設丟的次數很大

a. 

我們可以想成我們平均需要 3.5 個問題可以問出結果

b.
在 b 情況 3 個問題就可以得到 A 丟的結果

當次數很大時

我們考慮長度

2 * (2 * 1/6) +  4 * (3*1/6) = 2.667

這裡可以看到我們算出來的平均長度會比log2(6) 大

2.667  > log2(6)  = 2.58


to be continue...

Computer Systems

這學期我修了影響我很深的三堂課, operating systems distributed computing systems interconnection networks 每一門課中 都接觸到了大量相關領域的論文 在系統這個領...