CS:APP 第 2 章：資訊的表示與處理 (Data Representation) Integer Overflow & Casting

1. 資訊存儲 (Information Storage)

電腦最小的可定址單位是 Byte (8 bits)。

U8 = 0x00~0xFF

字組大小 (Word Size)：32-bit 或 64-bit 決定了虛擬位址空間的最大範圍。

位元組順序 (Byte Ordering)：

Big Endian (大端序) 的邏輯最符合人類閱讀習慣

• 0x01234567 在 Little Endian 記憶體中的排列為 67 45 23 01

• Big Endian通常小的在後（尾端）但是大部分cpu 都是使用 Little Endian 

2. 整數表示法 (Integer Representations)

Unsigned (無符號)：直接二進位編碼

0x1 = 1

0x10 =2

0x11 = 1+2 = 3

Two's Complement (二進位補數)：用於表示正負數，最高位元（MSB）權重為負。

S8:

0000 0000 = 0

0100 0000 = 64

1000 0000 = -128

1100 0000 = -128+64 = -64

TMin 與 TMax 的不對稱性：在 8-bit 中，範圍是 -128 到 127。

3. 整數運算與溢位 (Integer Arithmetic)

整數運算的本質是 模運算 (Modular Arithmetic)。

• Unsigned Addition：結果若超過 $2^w - 1$，則會減去 $2^w$（Wrap around）。

• Two's Complement Addition：

  • 正溢位：兩個正數相加得到負數。

  • 負溢位：兩個負數相加得到正數。

• 乘法與位移：編譯器常用 shl (左移) 代替乘以 2 的冪次，用 shr (右移) 代替除法。

• 邏輯右移 (Logical)：補 0（用於 Unsigned）。

• 算術右移 (Arithmetic)：補符號位元（用於 Signed）。

4. 浮點數 (Floating Point)

// 利用 union 觀察同一塊記憶體的位元分佈

typedef union {

float f;

struct {

uint32_t frac : 23; // 尾數 (Fraction)

uint32_t exp : 8; // 階碼 (Exponent)

uint32_t sign : 1; // 正負號 (Sign)

} parts;

uint32_t raw;

} FloatConv;

r@ubuntu-server:~/leaarning$ ./test

--- Analysis: Normalized 1.0 (1.000000) ---

Raw Hex: 0x3F800000

Sign: 0, Exponent (Raw): 127, Fraction: 0x000000

Type: Normalized

Actual Exponent (E): 0

--- Analysis: Normalized -0.15625 (-0.156250) ---

Raw Hex: 0xBE200000

Sign: 1, Exponent (Raw): 124, Fraction: 0x200000

Type: Normalized

Actual Exponent (E): -3

--- Analysis: Denormalized Small (0.000000) ---

Raw Hex: 0x000002CA

Sign: 0, Exponent (Raw): 0, Fraction: 0x0002CA

Type: Denormalized (Subnormal - Very small)

--- Analysis: Infinity (inf) ---

Raw Hex: 0x7F800000

Sign: 0, Exponent (Raw): 255, Fraction: 0x000000

Type: Special Value (Infinity)

--- Analysis: NaN (nan) ---

Raw Hex: 0x7FC00000

Sign: 0, Exponent (Raw): 255, Fraction: 0x400000

Type: Special Value (NaN)

==============================================================

1. 無符號整數溢位 (Unsigned Integer Overflow)

 

unsigned int a = UINT_MAX;

a = a + 1; // 產生溢位

Unsigned Max: 4294967295

After Overflow (a + 1): 0

2. 有符號整數溢位 (Signed Integer Overflow)

int b = INT_MAX;

b = b + 1;

Signed Max: 2147483647

After Overflow: -2147483648

3. 隱式型別轉換與正負號問題 (Implicit Casting & Signedness)

int x = -1;

unsigned int y = 1;

驚訝吧！-1 居然大於 1

原因：x 被轉成 unsigned 的數值是 4294967295

4. 窄化轉換 (Narrowing Conversion)

int big_val = 0x12345678;

char small_val = (char)big_val; // 只保留最後 8 bits

Original: 0x12345678

Truncated: 0x78 (Only 0x78 is kept)

CS:APP -「第 6 章：記憶體階層」 Cache Locality: 「在處理大數據陣列時，Row-major 和 Column-major 的存取順序對效能有什麼影響？」

Q

Cache Locality: 「在處理大數據陣列時，Row-major 和 Column-major 的存取順序對效能有什麼影響？」

A 

• Row-major (連續): 當 CPU 讀取 arr[0][0] 時，會把後面的 arr[0][1], arr[0][2] 一起放進 Cache Line (通常 64 bytes)。下一次迴圈要用時，資料已經在 Cache 裡了（Cache Hit）。

• Column-major (跳躍): 存取 arr[0][0] 後，下一個要拿 arr[1][0]。這兩個元素在記憶體中隔了 $10000 \times 4$ bytes，遠超過 Cache Line 的長度。CPU 必須重新去主記憶體抓資料（Cache Miss），導致速度大幅下降。

什麼順序會有差？

在現代 CPU 架構中，當你從記憶體讀取一個位元組時，硬體並不會只抓那一個位元組，而是抓取一整塊連續的資料，這被稱為 Cache Line（通常是 64 Bytes）。

## 1. Row-major (列優先) 存取：Cache Friendly

C 語言的二維陣列在記憶體中是橫向連續存放的。如果你用 row-major 順序存取（外迴圈是 i, 內迴圈是 j）

## 2. Column-major (行優先) 存取：Performance Killer

如果你把迴圈順序對調（外迴圈是 j, 內迴圈是 i）：

每次存取 array[i][j] 之後，下一個要抓的是 array[i+1][j]。在記憶體中，這兩個位址隔了「一整列」的距離。Cache Line 抓進來的資料還沒用到就被踢出去了。

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#define N 10000 // 10000 x 10000 的矩陣，約佔 400MB 記憶體

// 分配在 Heap 以免 Stack Overflow

int (*arr)[N];

int main() {

arr = malloc(sizeof(int[N][N]));

if (!arr) return 1;

struct timespec start, end;

double cpu_time_used;

// --- 測試 1: Row-major (順著記憶體位址存取) ---

clock_gettime(CLOCK_MONOTONIC, &start);

long long sum = 0;

for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++) {

sum += arr[i][j];

}

}

clock_gettime(CLOCK_MONOTONIC, &end);

cpu_time_used = (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1e9;

printf("Row-major (順向) 耗時: %f 秒\n", cpu_time_used);

// --- 測試 2: Column-major (跳躍記憶體位址存取) ---

clock_gettime(CLOCK_MONOTONIC, &start);

sum = 0;

for (int j = 0; j < N; j++) { // 注意：這裡迴圈對調了

for (int i = 0; i < N; i++) {

sum += arr[i][j];

}

}

clock_gettime(CLOCK_MONOTONIC, &end);

cpu_time_used = (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1e9;

printf("Column-major (跳向) 耗時: %f 秒\n", cpu_time_used);

free(arr);

return 0;

}

r@ubuntu-server:~/leaarning$ gcc -O0 cache_test.c -o cache_test

r@ubuntu-server:~/leaarning$ ./cache_test 

Row-major (順向) 耗時:   0.260539 秒

Column-major (跳向) 耗時: 0.429585 秒

AWS CLI -- 第三步 EC2 定時自動開關機

 

 3.1創立 IAM 角色

開一個給lamda用的role

aws iam create-role --role-name lambda-ex --assume-role-policy-document '{"Version": "2012-10-17","Statement": [{ "Effect": "Allow", "Principal": {"Service": "lambda.amazonaws.com"}, "Action": "sts:AssumeRole"}]}'

arn:aws:iam::1234:role/lambda-ex 

創立一個json (定義ec2開關機權限)

vi policy.json 

{ 
  "Version": "2012-10-17", 
  "Statement": 
[ 
 { 
   "Effect": "Allow", "Action": [ "logs:CreateLogGroup", "logs:CreateLogStream", "logs:PutLogEvents" ], 
    "Resource": "arn:aws:logs:*:*:*" }, 
 { 
   "Effect": "Allow", "Action": [ "ec2:Start*", "ec2:Stop*" ], "Resource": "*" 
 } 
] 
}

 創立一個policy 

aws iam create-policy --policy-name ec2-start-stop-policy --policy-document file://policy.json 

 arn:aws:iam::1234:policy/ec2-start-stop-policy

新增這個policy到role裡

aws iam attach-role-policy --role-name lambda-ex --policy-arn arn:aws:iam::aws:policy/service-role/AWSLambdaBasicExecutionRole

aws iam attach-role-policy --role-name lambda-ex --policy-arn  arn:aws:iam::1234:policy/ec2-start-stop-policy

記下他的ARN

3.2 新增lamda 函式

vi start.py

 

import boto3

region = 'ap-northeast-1'

instances = ['i-1234']

 

def handler (event, context):

    ec2 = boto3.client('ec2', region_name=region)

    ec2.start_instances(InstanceIds=instances)

    print('started your instances: ' + str(instances))

 

vi stop.py

 

import boto3

region = 'ap-northeast-1'

instances = ['i-1234']

 

def handler (event, context):

    ec2 = boto3.client('ec2', region_name=region)

    ec2.stop_instances (InstanceIds=instances)

    print('stopped your instances: ' + str(instances)) 

 

zip start.zip start.py 

zip stop.zip stop.py 

 

 使用3.1的ARN

aws lambda create-function --function-name start_function \
--zip-file fileb://start.zip --handler start.handler --runtime python3.7 \
--role arn:aws:iam::1234:role/lambda-ex 

 aws lambda create-function --function-name stop_function \
--zip-file fileb://stop.zip --handler stop.handler --runtime python3.7 \
--role arn:aws:iam::1234:role/lambda-ex 

3.3 新增排程

 1-5 早上八點開機

aws events put-rule --name "start_function" --schedule-expression "cron(0 0 ? * MON-FRI *)" 

  1-5 下午六點關機

 aws events put-rule --name "stop_function" --schedule-expression "cron(0 10 ? * MON-FRI *)" 

AWS CLI -- 第二步 建立 Ec2

 

 2.0 確認網路環境

 

( VPC 是AWS的一種虛擬網路服務

確認要使用的VPC id及其 subnet id << 要跟AMI同一地區

 

subnet-1234

vpc-1234

 2.1創立keypair

aws ec2 create-key-pair --key-name serverKeyPair

把顯示的文字存成pem檔

aws ec2 describe-key-pairs --key-name serverKeyPair

2.2 創立Security Group

 

 

創立Security Group

aws ec2 create-security-group --group-name serverSecurityGroup --description "server security group" --vpc-id vpc-1234

>>會回你創好的SGid

我們把這組SG的 1883 + 22 port 打開

 aws ec2 authorize-security-group-ingress --group-id sg-1234--protocol tcp --port 1883 --cidr 0.0.0.0/0

 aws ec2 authorize-security-group-ingress --group-id sg-1234--protocol tcp --port 22 --cidr 0.0.0.0/0

檢查一下現在的設定值 

aws ec2 describe-security-groups --group-ids sg-1234

2.3 搜尋要用的作業系統

找到自己要用的AMI

https://cloud-images.ubuntu.com/locator/

Amazon AWS

ap-northeast-1

bionic

18.04

amd64

hvm-ssd

20220610

ami-0a2e24115d3ca5d76

2.4 創立EC2 instances

aws ec2 run-instances \
    --image-id ami-0a2e24115d3ca5d76 \
    --instance-type t2.micro \
    --subnet-id subnet-1234\
    --security-group-ids sg-1234\
    --associate-public-ip-address \
    --key-name serverKeyPair

 >>查詢其中的instance-ids

i-1234

aws ec2 describe-instances \
    --instance-ids i-1234

 aws ec2 describe-instances --instance-ids i-1234--query 'Reservations[].Instances[].PublicDnsName'

>>查詢其中的 PublicDnsName 

1234.ap-northeast-1.compute.amazonaws.com

2.5 登入並使用server

 還記得2.1用的pem檔嗎

 

可以使用linux mac 內建的ssh指令

 ssh -i "serverKeyPair.pem" ubuntu@1234.ap-northeast-1.compute.amazonaws.com

 

或是 windows 使用putty 做登入 

 (要先使用puttygen 轉換pem 為ppk檔

 hostname :

ubuntu@1234.ap-northeast-1.compute.amazonaws.com

 port:  22

Connection >> SSH >> Auth >> 選擇PPK檔

好用的指令

開機 

aws ec2 start-instances --instance-ids i-1234

關機 

aws ec2 stop-instances --instance-ids i-1234

重開機 

aws ec2 reboot-instances --instance-ids i-1234

AWS CLI -- 第一步 新增IAM 帳號

可以local 使用AWS shell

https://docs.aws.amazon.com/cli/latest/userguide/cli-chap-getting-started.html

或是直接用cloudshell

https://us-east-1.console.aws.amazon.com/cloudshell
 

1. 創建admin account

 

1.1  創建admin group

aws iam create-group --group-name Admins

aws iam list-groups 

1.2  連接admin group policy

aws iam attach-group-policy --group-name Admins --policy-arn arn:aws:iam::aws:policy/AdministratorAccess 

aws iam list-attached-group-policies --group-name Admins 

1.3 創建admin user

aws iam create-user --user-name admin 

1.4 創建password

串建空白範本 

aws iam create-login-profile --generate-cli-skeleton > create-login-profile.json 

修改為需要的帳號密碼(請注意密碼有最低安全限制

 vi  create-login-profile.json 

{
    "UserName": "admin",
    "Password": "admin",
    "PasswordResetRequired": true
} 

aws iam create-login-profile --cli-input-json file://create-login-profile.json 

 1.5 加入user group

aws iam add-user-to-group --user-name admin --group-name Admins 

如何在一般docker container 裡用USB硬碟?

首先拿到USB硬碟mount完的路徑

device 是 /dev/usb/bus/001/014

但是我們要拿的是可以存取的資料夾路徑

譬如 /media/lab734/Kingston

在docker create時加上 -v /media/lab734/Kingston:/mnt/usb/Kingston

container裡面會有/mnt/usb/Kingston 裡面就是USB硬碟的資料了

一般docker 操作

去找到你要複製的image 和TAG

tensorflow/tensorflow:2.0.0b1-gpu-py3-jupyter

創一個新的container

sudo nvidia-docker create

--name lab734docker //名子

-p 7777:8888 //本機跟虛擬機的port-forwaording
--privileged=true //開放真的root權限

--device /dev/nvidia-uvm:/dev/nvidia-uvm //把顯卡映射進來

-it //來個可以互動的命令列 方便之後操作

-v /media/lab734/Kingston:/mnt/usb/Kingston

//映射資料夾 這裡是用上面的USB硬碟

tensorflow/tensorflow:2.0.0b1-gpu-py3-jupyter

//來源的image

sudo nvidia-docker create --name lab734docker -p 7777:8888 --privileged=true --device /dev/nvidia-uvm:/dev/nvidia-uvm --device /dev/nvidia0:/dev/nvidia0 --device /dev/nvidiactl:/dev/nvidiactl -it -v /home/lab734:/home/usr tensorflow/tensorflow:2.0.0b1-gpu-py3-jupyter 

docker start lab734docker

//開機~

docker ps//現在開了哪幾台

docker exec -it lab734docker /bin/bash
//進入shell打指令 ctrl +D 退出

docker stop lab734docker
//停掉

docker rm lab734docker

//移除container 
apt-get install update

pip3 install --upgrade pip
pip install matplotlib pillow opencv-python==3.4.2.16
apt-get install libgtk2.0-dev


docker exec -it CH /bin/bash