2015年4月8日 星期三

計算機組織 - 電腦概述


摩爾定律

每隔18~24個月,積體電路上可容納的電晶體個數便會增加一倍。
 

電腦系統的種類
  • 桌上型電腦(Desktop computers):一般泛用的個人電腦。
  • 伺服器型電腦(Server computers):涉及網路,追求高效能、高容量及高穩定性。
  • 嵌入式電腦(Embedded computers):嵌入於其他系統(如手機、電視)中的電腦,追求耗電與效能之間的平衡。


程式的處理階層:


軟體層面(Software):
應用程式(Application software):為了達成特定需求(如遊戲、圖片\影片編輯......等等),由高階語言編成的軟體。
系統軟體(System software) :負責管理及協調硬體階層,包括了作業系統及編譯器等等。
硬體層面(Hardware):
囊括了處理器、記憶體,以及IO控制器等等。

程式語言的階層:

高階語言(High level language):
貼近人類語言,容易閱讀及編寫,透過編譯器或直譯器轉換為機器碼。
組合語言(Assembly language):
屬於低階語言,指令多與處理器直接對應,以文字來描述機器的行為,透過組譯器轉換為機械碼。
機器碼(Machine code):
由0和1構成的處理器的指令集,電腦可以直接識別。

電腦的元件:

不論是嵌入式、伺服器,或是桌上型電腦,都包含了這5個主要部分:
  • 輸入與輸出元件
  • 記憶元件
  • 控制元件
  • 資料路徑(Data path)

效能評估

Response Time and Throughput


  •  Response Time(反應時間)
又稱為elapsed time,表示要完成一件工作所需花費的時間。其中包括了CPU time、I/O、OS overhead及閒置時間。
  •  Throughput(生產能力):在一定時間內所能完成的工作量

CPU time


即CPU處理給定的工作所花費的時間,可再細分為User CPU time(處理器在處理這分工作所花的時間)與System CPU time(作業系統為了執行這份工作額外的準備時間)
CPU time 可以這麼定義:

CPU Time = CPU Clock Cycles * Clock Cycle Time
= CPU Clock Cycles / Clock Rate

Clock cycle稱為時脈週期,時脈(Clock)就像電腦中的一個計數器,每當時脈走了一格,便是完成了一個時脈周期,而走這一格所花費的時間,即是Clock Cycle Time,因此CPU Time即是總共走了幾個時脈周期乘上每走一個時脈周期所要花費的時間。

因此,若要改善CPU Time,我們能從減少clock cycle,或是增加Clock Rate著手。

CPI


CPI (Cycle per instruction) ,表示每執行一個指令(Instruction),所要花費的時脈周期
Clock Cycles =  Sigma(CPIi * Instruction Counti ),i from 1 to n.
Average CPI  = Clock Cycles/Instruction count

指令的個數由編譯器、ISA(ISA instruction set architecture)、程式與演算法共同決定。

CPU Power


Power = Capacitive load * Voltage2 * Frequency

設計要追求高響應(Frequency)而低功耗(Power),便須下調前兩者的影響,然而在2004年後,降低電壓與冷卻的技術飽和而停滯,在功率挑戰中形同撞上了一面高牆(Power wall),為了執續強化處理器的效能,技術便轉往多核心發展。


然而純粹增加核心數並不完全相關於效能改善,即是說「在單核心中要執行100s的工作,在五核心的電腦並不會只要執行20s」,實際上,它要花費 36 秒,這個數字是由阿姆達爾定律所推得(80/5 + 20 = 36),阿姆達爾闡明了:即便無限的增加處理器的個數,仍然存在一個加速上限。

2015年1月13日 星期二

Graph - 圖

1.如何定義一張圖:
 
圖(Graph)是由點(Vertex)與邊(Edge)構成,以G = (V,E)表示。

2014年12月9日 星期二

數位簽章

Digital Signature



什麼是數位簽章:
  • 數學演算法或其他運算方式,對要簽署的文件進行加密,所產生的結果
數位簽章的需求:
  • 驗證
    • 簽章者身份 (不可偽冒)
    • 簽章日期、時間
    • 訊息完整性 (不可偽造)
  • 透過此簽章,能讓第三方來解決紛爭 (不可否認性)
 數位簽章流程:
  • 產生簽章
    • 有一份文件M 
    • 計算文件的摘要 H(M),明文中1bit的不同,會在摘要產生大量不同  
    • 加密摘要:Ek(h)
    • 獲得簽章 S = Ek(h)
  • 同時傳送M與S給對方,完成簽章的傳送
  • 接收方也有一把驗證金鑰,可以對文件與簽章進行比對,確認這個簽確實是對應這份文件
  • 注意:簽章屬於非對稱式金鑰
    • 為什麼要是非對稱?
      • 若為對稱式金鑰,接收方可用同樣方式產生出簽章來仿冒傳送人
    • 加密用的是私鑰,解密用的是公鑰
    • 也就是說,簽章的結果是所有人都可以比對的
      • 有利於第三方驗證

2014年12月8日 星期一

組合邏輯電路

1.組合電路 v.s 循序電路
  • 組合電路:
    • 由邏輯閘構成,輸出為當前運算的結果
  • 循序電路:
    • 使用了儲存原件與邏輯閘
    • 輸出關係到輸入與先前儲存的結果
2.組合電路設計順序
  • 確定問題
  • 確定輸入與輸出
  • 指派輸入與輸出變數
  • 推導真值表
  • 簡化布林函式
  • 繪製邏輯電路圖並驗證結果
3.加法器
  • 半加器:2輸入2輸出,兩個當前要相加的bit,輸出該位元相加值與進位值
  • 全加器:3輸入2輸出,兩個當前要相加的bit,一個為前個bit的進位 ,輸出該位元相加值與進位值 
  • 透過串連的全加器,可夠成N-bit的加法器(漣波進位加法器)
    • 跟直觀的人為加法一樣,由後往前加,所以必須知道前一個bit是否有進位才可繼續運算 →造成傳遞延遲
  • 為了避免漣波進位的延遲 → 超前進位加法器
    • 因電路複雜使成本增加,但是簡短了運算時間
    • 打破資料相依性,使相加結果只與C0(初始值)有關
      • 使用疊代,將目前進位以前一次相加的結果取代,始終用最低位元表示
      • 因此,越高層(高bit)的電路,複雜度會愈趨增加
  • 使用加法器實做減法器
    • 可以透過一個位元操作
    • 減法其實等於與2補數相加,而2補數為1補數再加1
    • 那麼
      • 有AB兩數
      • 透過一個位元M,傳給C0,先將與B的各個Bit與M做Xor再送入全加器
      • 當M = 0時,B xor M = B,C0 = 0,為加法
      • 當M = 1時,B xor M = B',C0 = 1,所得為B的1補數+1=B的2補數,為減法
4. 溢位
  • 定義:一個n-bits間的運算卻造成了n+1-bits的結果 → 進位到了表示正負號的bit
  • 電腦必須偵測溢位並設置正反器以供之後調用
  • 如何避免溢位?
    • 假設有7bits相加
    • 使用9bits去儲存,多的2個bit
      • 第9 bit當作正負號
      • 第8 bit當做額外進位(7→8)
5.比較器
  • 兩輸入:A、B,三輸出:A>B、A<B、A=B 
  • 假設A、B的為4bits:A3A2A1A0、B3B2B1B0
  • 令Xi = AiBi + Ai'Bi' (Ai XNOR Bi)、即Ai、Bi相同時為1
  • 當A = B →  A3 = B3(X3 = 1) ...... A0 = B0(X0 = 1) → A=B可以表示為 X3*X2*X1*X0
  • 判斷A > B:A3B3'+x3A2B2'+x3x2A1B1'+x3x2x1 A0B0'
    • 先看A3B3'
      • 如果A3是1、B3是1:該項為0 → 往下一bit繼續比
      • 如果A3是1、B3是0:該項為1 → 不用比了,A > B
      • 如果A3是0、B3是1:該項為0,而且x3為0 → 接下來的每項都 = 0 → A < B
      • 如果A3是0、B3是0:該項為0、不過x3為1 → 可以往下一bit繼續比
    •  可以發現x3、x2...可以用做比較是否進行的標準
  • 判斷A < B:A3'B3+x3A2'B2+x3x2A1'B1+x3x2x1 A0'B0
6.n to m 解碼器
  • 有 n 個 bits→ 能表示 2^n種情形
    • 解碼器目的:輸入有n bits,產生2^n種輸出 
    • 即是表現出所有的 minterm 型式
    • 既然能表示出所有的 minterm,即能利用解碼器實做出任何電路
      • 但是效率並非最佳化
7.編碼器
  • 解碼器的逆操作: 2^n → n
  • 無法用卡諾圖化簡,直接用結果畫電路
  • 優先權編碼器
    • 允許多個輸入為1,因為只看最高位元,其他為Don't care (X)
8.多工器 (選擇器)
  • 目的:從多個輸入中,選擇出其中一個輸入
    • 比如說有輸入A、B,選擇用位元S
      • 使 A AND S、B AND S',再將他們做 OR
      • 在 S = 0時,輸出的是 B
      • 在 S = 1時,輸出的是 A
9.三態閘
  • 輸出:0、1、高阻抗(斷開電路,不會產生邏輯訊號)

2014年12月5日 星期五

OpenSource翻譯組會議紀錄

Opensource.com翻譯組開發會議 @2014/12/5

思考核心:

    1.傳承與延續的方法
    2.組員內部分工
    3.如何使成員對工作建立認同感
    4.如何吸引新成員參與專案

2014年11月22日 星期六

JavaScript 基本資料型態

資料型態決定了以什麼方式呈現這個資料,大致上有字元(文字)、數字與邏輯值三種型式。

JavaScript屬於弱型別,也就是在宣告變數時不必特定指定資料型態,變數具體的資料型態會根據變數的具體內容推算出來,並且能隨著內容改變更改型態。