Sep 18, 2015 課程紀錄

[2015q3 Week #1] [編輯共筆內容]

教材

 

課程公告

共筆使用方式

 

看影片想我們的未來

數位邏輯和程式設計

基本的電路之一:二進位加法器

Reference: 加法器與減法器 

用 C語言的 logical operator + recursion 來「模擬」邏輯電路

思考:

數字背後的道理

為什麼程式開發者要學習歷史?

出處: Xiqiao

各式 integer overflow:

The Evolution of Operating Systems

Tag: CTSS, Multics, Unix, BSD, Linux, Android, mbed

.

Abstract Data Type (ADT): the module’s state is manipulated only through its API (Application Programming Interface).

GNU/Linux (Linux 核心 + GNU 提供的系統工具), Android (修改過的 Linux 核心 + 非 GPL 的 userspace)

[p.22] ISA, ABI, API

[p.24] Operating system as resource manager

當資源可能被許多使用者使用時,OS 就需要一個 private task 來監控和管理使用者使用哪些資源。

[p.26] 作業系統演進

早期: serial processing 軍事用途(彈道模擬)

二 戰期間,賓州大學和阿伯丁彈道研究實驗室共同負責為陸軍每日   提供6張火力表,每張表都要計算幾百條彈道,一個熟練的計算員計算一條飛行時間60秒的彈道要花20小時。儘管改進了微分分析儀,聘用200多名計算員,  一張火力表仍要算兩三個月。這是電子計算機發展的迫切需求

[p.27] 分時多工系統

期望的硬體特徵

[p.32] 作業系統任務: 分配資源

電腦科學: 先有實作, 才有理論發表

[p.34] CTSS: 多人多工

用舊的OS開發新的OS: debugger and virtualization

process 可定義為

[p.42] process isolation, dynamic linking(模組化)

[p.50] microkernel: 只留下部份功能到核心

[p.52] SMP

分散式作業系統

關鍵字: NUMA (兩塊SMP, 互相通訊; 同質的核心, 是同一塊)

[p.55] OS design : 市場導向, 發展非線性向上, 起起伏伏

例: 先有CTSS(多人多工), 才有MS-DOS(單人單工)

[p.61] SMP

關鍵字: cache, snooping

[p.62] hypervisor實例: 大核(CA15)/小核(CA7)之間互相切換(依功能需求切換另一個核心時會通知另一個核心開機並將當前核心關機), 但是切換過程中的interrupt (中間切換過程約需 200 us), 由誰來收 -> [sol] 在核心上增加一個 interrupt 處理單元

[p.70] LInux system component

重點: system call, scheduler, memory management

一句話氣死 gcc

 二句話操死 gcc

 source: https://www.facebook.com/tj.wei1/posts/10204009017260579

From Source to Binary

LTO 帶來的提昇,可參考 gcc-5 的釋出說明 :(和 Firefox 有關)

應考慮 LLVM/Clang

記憶體

direct-mapped cache

在 MIPS的系統中,記憶體中的資料有對齊(每筆資料都是word,也就是4個byte),所以最後2個bit可以忽略,接著以地址的低位10個bit做為 cache index,高位20個bit做為tag判斷是不是需要的資料。所以這個cache需要2^10=1024個位置。

雖然上面這是cache實際大小的算法,但一般在叫cache都會將tag與valid field的大小去除,只會計算data的大小,所以上面那個cache的大小是4KB cache(1024 * 1 word = 1024 * 4 byte)

Fully associative

block可以放在cache中的任意位置,因此在cache中尋找block時需要搜尋整個cache,可以利用平行的comparator找出entry,只適合在較少block的cache中使用。

Set associative

介 於 direct-mapped 跟 fully  associative中間,block可以放在cache中一個固定數量的位置中,如果block可以被放在n個位置,則稱為n-way  set-associative  cache,cache會由一些含有n個block的集合組成,記憶體中的每一個block都可以對應到一個獨一的集合,而他可以被放在這個集合中的任意 一個位置。

在set-associative cache中,計算block在哪個set中的公式:`(Block number) % (Number of sets in the cache)`,例如上面的例子,block 12會放在`12 % 4 = set 0`中的任意位置,在搜尋時要搜尋過整個set。

Set Associative 還有多種 data replacement 的問題沒探究,另外 Fully 跟 Set Associative間還有應用面的問題,eg. multiple process/thread 在 fully or set associative 可能的問題...

Locating a Block in the Cache

Choosing Which Block to Replace

在directed-mapped中,每個block只能被放到一個固定的位置,所以miss發生時只能直接替換掉,但在associative cache中,可以選擇要將block放到哪一個位置

Handling Writes

Performance

在 設計Primary cache跟Secondary cache時會考慮不同面向,primary cache會專注在減少hit  time,以縮短pipeline stage的clock cycle,secondary cache則會專注在miss  rate,避免存取記憶體造成的miss penalty。

Virtual Memory

Page table

TLB

page  table會存在記憶體中,每次程式要使用資料都要存取記憶體兩次:一次是取得physical  address,第二是取得真正要的資料。一個被轉譯的virtual page  number很有可能會在被使用到,因為page同時具有temporal locality跟spatial locality。

現代的處理器會有一個特別的cache,用來紀錄最近轉譯的track,這種特殊的cache叫做translation-lookaside buffer(TLB)

整個流程:

  1. 程式將virtual address送到TLB尋找physical address,如果沒找到就到page table中找
  2. 找到physical address後看cache中有沒有存,如果沒有存就要處理cache miss

Cache Coherence

在多核心處理器中用來維護一致性的協定叫做cache coherence protocols

有一個實現coherence的方式是確保處理器在寫入資料時是互斥的,這種叫做`write invalidate protocol`,在寫入一份資料時,會將其他cache上的複本invalidate,這樣可以確保在寫入一個item時,其他的複本是不可讀也不可寫的。

關鍵字: DMA cache coherence

Pipeline

Hazard

  • Multi-core跟SMP 好像有一樣的問題?可以平行處理同一program嗎?
  • SMP -> AMP

    https://en.wikipedia.org/wiki/ARM_big.LITTLE

    搭配 Intel 影片: L01-06: 多核心處理器有前途嗎

    Rob Pike: Concurrency is Not Parallelism

  • SMP 的 snooping
  • Snoop Cache Coherency Protocol

    不同的cpu有對應的cache,資料存取的時候可以從cache裡面存取,而不是記憶體進而加快速度。

    ARM SCU (ARM Cortex-A9 MP)

    因為會利用cache對data bus進行snooping(窺探),當變數A被更改的時候,「如果自己對應的cache裡面也有變數A」,則對自己cache裡面的變數A進行更新,或者先將它設為invalid,等到下次要取值的時候進行更新。  

    預習教材