HPC Concept Map

HPC บทที่ 1–10: แผนผังและการคำนวณ

ตั้งแต่ ALU ในคอร์เดียวไปจนถึงซูเปอร์คอมพิวเตอร์ทั้งระบบ แท็บแผนผังใช้ดูความเชื่อมโยง แท็บการคำนวณสอนวิธีคิดโจทย์ตัวเลขแบบไม่ใช้เครื่องคิดเลข

เรื่องเดียวกันทั้งวิชา: จากคอร์เดียวสู่ซูเปอร์คอมพิวเตอร์

อ่านตามลำดับนี้จะเห็นว่าแต่ละบทแก้ปัญหาที่บทก่อนหน้าทิ้งไว้ คลิกคำที่ขีดเส้นใต้เพื่อเปิดโหนดนั้นบนแผนผัง

ตารางเปรียบเทียบที่มักออกสอบ

สรุปความต่างของคู่แนวคิดที่สับสนกันบ่อย ตัวเลขขนาดและเวลาเป็นค่าโดยประมาณของ CPU ยุคปัจจุบัน ใช้เพื่อเทียบลำดับขนาดเท่านั้น

ลำดับชั้นหน่วยความจำ

ระดับ	ขนาดโดยประมาณ	Latency โดยประมาณ	ใช้ร่วมกัน?	Balance (W/F)
Register	หลายสิบตัว ต่อคอร์	0–1 cycle	ส่วนตัวของแต่ละคอร์/เธรด	—
L1 Cache	32–64 KB ต่อคอร์ (แยก L1D/L1I)	~4 cycles (~1 ns)	ส่วนตัวของคอร์	cache: 0.5–1.0
L2 Cache	256 KB – ไม่กี่ MB	~10–15 cycles	ส่วนตัว หรือแชร์ 2 คอร์
L3 Cache	หลายสิบ MB ต่อชิป	~40–60 cycles	แชร์ทุกคอร์ในชิป
Main memory	หลาย GB – TB	~100 ns (หลายร้อย cycles)	แชร์ทั้งซ็อกเก็ต/ทั้งเครื่อง	0.03–0.5
Interconnect	—	µs (IB ~4 µs, GigE ~76 µs)	ข้ามเครื่อง	0.0001–0.02

ช่วง Balance มาจาก Table 3.1 ในบทที่ 3 ส่วนค่า latency ของเครือข่ายมาจากผลวัด PingPong ในบทที่ 4

SIMD · Vector · MIMD

	SIMD (คำสั่งในคอร์)	Vector processor	MIMD
หลักการ	1 คำสั่ง ทำกับ 2–16 ค่าใน register กว้าง	1 คำสั่ง ทำกับเวกเตอร์ยาวหลายร้อยค่า ผ่าน pipeline หลาย track	หลายคำสั่งอิสระ ทำกับข้อมูลคนละชุด
ตัวอย่าง	SSE, AVX, AVX-512, ARM SVE	NEC SX-8, Cray	Multicore CPU, cluster
ชอบข้อมูล	ต่อเนื่อง stride-1 ที่อยู่ใน cache	เวกเตอร์ยาว โหลดตรงจาก memory	งานแบ่งเป็นส่วนได้
การเขียนโปรแกรม	compiler vectorize, NumPy	compiler vectorize (strip-mining)	OpenMP, threads, MPI (SPMD)

UMA · ccNUMA · Distributed memory

	UMA (SMP)	ccNUMA	Distributed
Address space	เดียว (shared)	เดียว (shared ทางตรรกะ)	แยกแต่ละ process/node
หน่วยความจำ	ก้อนเดียว เวลาเข้าถึงเท่ากันทุกที่	กระจายตาม locality domain: local เร็ว, remote ช้ากว่า	แต่ละเครื่องมีของตัวเอง เข้าถึงข้ามเครื่องตรง ๆ ไม่ได้
เชื่อมกันด้วย	chipset / FSB	HyperTransport, Infinity Fabric, QPI/UPI, NUMALink	Network (InfiniBand, Ethernet, Tofu)
Coherence	ต้องมี (MESI)	ต้องมี (cc = cache-coherent)	ไม่ต้อง
ขยายได้	น้อย (bandwidth ร่วม)	ปานกลาง (ไม่กี่ซ็อกเก็ต)	มากที่สุด (Fugaku 158,976 nodes)
โปรแกรม	OpenMP, threads	OpenMP + ระวัง placement	MPI

Multicore · Multithreaded CPU · Multithreading

	Multicore CPU	Multithreaded CPU (SMT)	Multithreading (ซอฟต์แวร์)
คืออะไร	หลายคอร์จริงในชิปเดียว	1 คอร์ เก็บสถานะของ 2+ เธรด ใช้ ALU ร่วมกัน	โปรแกรมสร้างหลายเธรดใน process เดียว
อยู่ระดับ	ฮาร์ดแวร์ (ชิป)	ฮาร์ดแวร์ (ในคอร์)	ซอฟต์แวร์ (OS/โปรแกรม)
แชร์อะไร	L3, memory interface	execution units, L1/L2, pipeline	หน่วยความจำของ process (heap, globals)
ได้อะไร	peak FLOPS เพิ่มตามจำนวนคอร์	เติม pipeline bubble ไม่ได้เพิ่ม peak	ใช้หลายคอร์/เธรดฮาร์ดแวร์พร้อมกัน

OpenMP · MPI · Python

	OpenMP	MPI	Python threading	Python multiprocessing
หน่วยทำงาน	threads	processes (ranks)	threads	processes
หน่วยความจำ	shared	distributed (ของใครของมัน)	shared	แยกกัน
สื่อสารโดย	อ่านเขียนตัวแปรร่วม + sync	Send/Recv, Bcast, Reduce	ตัวแปรร่วม + Lock/Event	IPC, Queue, Pool.map
ใช้กับ	เครื่องเดียว (multicore/NUMA)	cluster, หรือเครื่องเดียวก็ได้	งาน I/O-bound, GUI	งาน CPU-bound
จุดต้องระวัง	race, false sharing, schedule	deadlock, ต้นทุน latency	GIL ทำให้ CPU-bound ไม่เร็วขึ้น	ใช้หน่วยความจำมาก, overhead สูง

ตัวอย่างคำนวณ Balance: ทำไมโค้ดส่วนใหญ่ได้ไม่ถึง peak

Vector triad A(i) = B(i) + C(i)*D(i) ทำ 2 flops ต่อรอบ และต้องอ่าน B, C, D (3 words) กับเขียน A (1 word) รวม 4 words หรือ 5 words ถ้านับ write-allocate ด้วย ดังนั้น code balance B_c ≈ 2–2.5 W/F

ชิป A64FX ของ Fugaku มี peak ประมาณ 3,072 GFlops/s (48 คอร์ × 2 GHz × 32 flops/cycle) และมี HBM2 ประมาณ 1,024 GB/s = 128 GWords/s จึงได้ B_m ≈ 128 / 3072 ≈ 0.042 W/F

lightspeed l = min(1, B_m/B_c) ≈ 0.042 / 2 ≈ 0.02 แปลว่า triad ที่ข้อมูลใหญ่เกิน cache จะได้ประมาณ 2% ของ peak เท่านั้น ตัวคุมความเร็วคือ bandwidth ไม่ใช่ ALU ผลวัด Stream triad ในสไลด์ (830+ GB/s) ก็สอดคล้องกับข้อนี้

ตัวเลข peak และ bandwidth ของ A64FX เป็นค่าโดยประมาณจากสเปกที่เผยแพร่ ใส่ไว้เพื่อให้เห็นวิธีคิด

พื้นฐาน · ใช้ทุกบท

0 · หน่วยที่ต้องแปลงให้คล่อง

โจทย์ HPC ผิดเพราะหน่วยมากกว่าผิดเพราะสูตร ให้แปลงทุกอย่างเป็นหน่วยเดียวกันก่อนเสมอ

\[ \text{K}=10^{3},\ \text{M}=10^{6},\ \text{G}=10^{9},\ \text{T}=10^{12},\ \text{P}=10^{15} \qquad \text{ms}=10^{-3},\ \mu\text{s}=10^{-6},\ \text{ns}=10^{-9}\ \text{s} \]

\[ 1\ \text{word} = 8\ \text{bytes (double)} \qquad\Rightarrow\qquad b\,[\text{GWords/s}] = \frac{b\,[\text{GB/s}]}{8} \]

\[ 1\ \frac{\text{MB}}{\text{s}} = \frac{10^{6}\ \text{B}}{10^{6}\ \mu\text{s}} = 1\ \frac{\text{B}}{\mu\text{s}} \qquad\qquad 1\ \frac{\text{GB}}{\text{s}} = 1\ \frac{\text{B}}{\text{ns}} \]

\[ f = 2\ \text{GHz} \;\Rightarrow\; 1\ \text{cycle} = \frac{1}{2\times 10^{9}}\ \text{s} = 0.5\ \text{ns} \]

หาร N ไบต์ด้วย B ที่เป็น MB/s จะได้คำตอบเป็น µs ทันที เช่น \(10^{4}\ \text{B} \div 100\ \text{MB/s} = 100\ \mu\text{s}\)

ขนาด cache มักนับแบบเลขฐานสอง \(1\ \text{KB} = 2^{10} = 1024\ \text{B}\) เช่น \(32\ \text{KB} = 32768\ \text{B}\) แต่ bandwidth และ FLOPS ใช้ฐานสิบ

บทที่ 1 · Floating-point ALU, SIMD, Multicore

1 · Peak FLOPS

Peak คือขีดสูงสุดตามทฤษฎีเมื่อ FPU ทุกตัวทำงานทุกรอบ หาได้จากการคูณจำนวนหน่วยทุกระดับเข้าด้วยกัน

\[ P_{\max} = n_{\text{core}} \times f \times \underbrace{n_{\text{FPU}} \times w_{\text{SIMD}} \times c_{\text{FMA}}}_{\text{flops / cycle / core}} \]

\(n_{\text{core}}\) จำนวนคอร์ (ส่วน MIMD), \(f\) ความถี่ (GHz)
\(w_{\text{SIMD}} = \dfrac{\text{register bits}}{64}\) สำหรับ double เช่น AVX2 256 บิต = 4, AVX-512 = 8
\(c_{\text{FMA}} = 2\) ถ้าเป็น fused multiply-add (คูณ + บวก = 2 flops) ไม่งั้นเป็น 1

ตัวอย่าง 1.1

CPU 8 คอร์, 2.5 GHz, AVX2 (256 บิต), มีหน่วย FMA 2 หน่วยต่อคอร์ จงหา peak (double)

\[ w = \frac{256}{64} = 4 \qquad \text{flops/cycle} = 2 \times 4 \times 2 = 16 \]

\[ P_{\max} = 8 \times 2.5\ \text{GHz} \times 16 = 320\ \text{GFlop/s} \]

ตัวอย่าง 1.2 · A64FX (Fugaku)

48 คอร์, 2 GHz, SVE 512 บิต, FMA 2 หน่วย

\[ 2 \times \frac{512}{64} \times 2 = 32\ \text{flops/cycle} \qquad P_{\max} = 48 \times 2 \times 32 = 3072\ \text{GFlop/s} \approx 3\ \text{TFlop/s} \]

คิด flops/cycle ต่อคอร์ให้เสร็จก่อน แล้วค่อยคูณคอร์และ GHz ตัวเลขจะเล็กกว่าและคูณง่ายกว่า

SMT (Hyper-Threading) ไม่ เพิ่ม peak ห้ามคูณจำนวน logical CPU

บทที่ 1 · Listing 1.1 vector triad

2 · คำนวณ MFlop/s จากผลวัด

Triad A(i) = B(i) + C(i)*D(i) หนึ่งรอบมีบวก 1 คูณ 1 = 2 flops วนซ้ำ R รอบ รอบละ N ค่า ใช้เวลา t วินาที

\[ \text{MFlop/s} = \frac{2 \cdot N \cdot R}{t \times 10^{6}} \]

ตัวอย่าง 2.1

N = 1000, R = 50,000, วัดได้ t = 0.05 s

\[ \frac{2 \times 10^{3} \times 5\times10^{4}}{0.05 \times 10^{6}} = \frac{10^{8}}{5\times 10^{4}} = 2000\ \text{MFlop/s} \]

ข้อมูลที่ใช้: 4 อาร์เรย์ × 1000 × 8 B = 32,000 B ซึ่งพอดีกับ L1 ขนาด 32 KB (32,768 B) ตรงกับช่วงเร็วสุดใน Fig 1.4

ตัวอย่าง 2.2 · แปลงกลับเป็น bandwidth

ที่ 2000 MFlop/s ทำได้ 1000 M รอบ/s แต่ละรอบย้าย 4 words = 32 B

\[ 10^{9}\ \tfrac{\text{iter}}{\text{s}} \times 32\ \tfrac{\text{B}}{\text{iter}} = 32\ \text{GB/s} \]

ถ้า memory ส่งได้แค่ 20 GB/s แปลว่าผลนี้มาจาก cache ไม่ใช่ memory

ขนาดข้อมูลของ triad = \(32N\) ไบต์ ใช้เช็กว่า N เท่านี้อยู่ใน cache ชั้นไหน

บทที่ 1 · Pipeline, FP ALU, vector processor

3 · Pipeline

pipeline m ขั้น ทำงานอิสระ N ชิ้น ชิ้นแรกออกหลัง m รอบ (wind-up) จากนั้นออกรอบละชิ้น

\[ T_{\text{pipe}} = m + N - 1 \ \text{cycles} \qquad\qquad T_{\text{no pipe}} = m \cdot N \ \text{cycles} \]

\[ \text{Speedup} = \frac{mN}{m + N - 1} \;\xrightarrow{\;N\to\infty\;}\; m \qquad\qquad \text{Throughput} = \frac{N}{m+N-1}\ \text{results/cycle} \]

ตัวอย่าง 3.1 · FP multiply 5 ขั้น (slide 20)

m = 5, N = 100

\[ T = 5 + 100 - 1 = 104 \qquad \text{Speedup} = \frac{500}{104} \approx 4.8 \qquad \text{Throughput} = \frac{100}{104} \approx 0.96 \]

ถ้า N = 4: \(T = 8\), throughput \(= 4/8 = 0.5\) ลูปสั้นเสียเวลาไปครึ่งหนึ่งกับ wind-up เหตุผลเดียวกับที่ vector processor ต้องการเวกเตอร์ยาว

ตัวอย่าง 3.2 · real dependency

A(i) = s*A(i-1) รอบถัดไปต้องรอผลรอบก่อนครบ m รอบ pipeline จึงช่วยไม่ได้

\[ T \approx m \cdot N = 500\ \text{cycles} \]

ช้ากว่ากรณีไม่มี dependency ประมาณ 4.8 เท่า

\(\frac{500}{104}\): คิดเป็น \(\frac{500}{100} = 5\) แล้วลดลง ~4% ได้ ≈ 4.8

บทที่ 1.3 · บทที่ 3.2 · Cache mapping, storage order

4 · Cache: จำนวน line, การ map, miss rate

ให้ \(C\) = ขนาด cache, \(L\) = ขนาด cache line, \(m\) = จำนวน way

\[ \#\text{lines} = \frac{C}{L} \qquad \#\text{sets} = \frac{C}{L \cdot m} \qquad \text{doubles/line} = \frac{L}{8} \]

Direct-mapped (m = 1): ตำแหน่งใน cache ของที่อยู่ addr คือ

\[ \text{index} = \left\lfloor \frac{\text{addr}}{L} \right\rfloor \bmod \frac{C}{L} \]

ตัวอย่าง 4.1

L1 ขนาด 32 KB, line 64 B, 8-way

\[ \#\text{lines} = \frac{32768}{64} = 512 \qquad \#\text{sets} = \frac{512}{8} = 64 \qquad \text{doubles/line} = \frac{64}{8} = 8 \]

ตัวอย่าง 4.2 · conflict ใน direct-mapped (Fig 1.10)

cache 32 KB direct-mapped, line 64 B (512 lines) ที่อยู่ 0 กับ 32768 ลงช่องไหน

\[ \left\lfloor \tfrac{0}{64} \right\rfloor \bmod 512 = 0 \qquad \left\lfloor \tfrac{32768}{64} \right\rfloor \bmod 512 = 512 \bmod 512 = 0 \]

ลงช่องเดียวกัน อาร์เรย์สองตัวที่ห่างกันเท่าขนาด cache พอดีจะไล่ทับกันทุกครั้ง (thrashing) set-associative แก้ได้เพราะลงได้ m ช่อง

Miss rate ตาม stride

เมื่อวิ่งผ่านอาร์เรย์ double ที่ใหญ่กว่า cache ด้วย stride \(k\) (line ละ 8 ค่า)

\[ \text{miss rate} = \min\!\left(1,\ \frac{k}{8}\right) \qquad \text{stride-1} = \tfrac{1}{8} = 12.5\%,\quad \text{stride-2} = 25\%,\quad \text{stride} \ge 8 = 100\% \]

ที่อยู่ของ element ในเมทริกซ์ N×N (double)

\[ \text{C (row-major):}\ \ \texttt{a[i][j]} \to (i \cdot N + j)\times 8 \qquad\qquad \text{Fortran (column-major):}\ \ \texttt{A(i,j)} \to \big((j-1)\cdot N + (i-1)\big)\times 8 \]

ลูปในสุดต้องเปลี่ยนตัวที่อยู่ "ขวาสุด" ใน C (j) และ "ซ้ายสุด" ใน Fortran (i) จึงเป็น stride-1

บทที่ 3.1 · Balance analysis และ lightspeed

5 · Machine balance, code balance, lightspeed

\[ B_m = \frac{b_{\max}\ [\text{GWords/s}]}{P_{\max}\ [\text{GFlop/s}]} \qquad\qquad B_c = \frac{\text{words moved (load + store)}}{\text{flops}} \]

\[ l = \min\!\left(1,\ \frac{B_m}{B_c}\right) \qquad\qquad P = l \cdot P_{\max} = \min\!\left(P_{\max},\ \frac{b_{\max}}{B_c}\right) \]

สูตรขวาสุดคิดง่ายที่สุด: ความเร็วที่ได้ = bandwidth (words/s) หารด้วย words ที่ต้องใช้ต่อ flop แต่ไม่เกิน peak

นับ B_c ของลูปมาตรฐาน

นับต่อ 1 รอบ: load ทุกอาร์เรย์ที่อ่าน + store ทุกอาร์เรย์ที่เขียน + write-allocate (WA) อีก 1 สำหรับอาร์เรย์ที่ถูกเขียนแต่ไม่ได้อ่าน

Kernel	Load	Store	WA	Flops	B_c (ไม่นับ WA)	B_c (นับ WA)
A = B + C·D (triad)	3	1	1	2	2	2.5
A = B + C (add)	2	1	1	1	3	4
A = A + s·B (daxpy)	2	1	0	2	1.5	1.5
A = s·A (scale)	1	1	0	1	2	2
s = s + A·B (dot)	2	0	0	2	1	1

ตัวอย่าง 5.1

เครื่องมี memory bandwidth 40 GB/s, peak 100 GFlop/s รัน triad ขนาดใหญ่เกิน cache (นับ WA)

\[ b_{\max} = \frac{40}{8} = 5\ \text{GW/s} \qquad B_m = \frac{5}{100} = 0.05\ \text{W/F} \]

\[ l = \frac{0.05}{2.5} = 0.02 \qquad P = 0.02 \times 100 = 2\ \text{GFlop/s} \qquad \Big(= \tfrac{b_{\max}}{B_c} = \tfrac{5}{2.5}\Big) \]

ได้แค่ 2% ของ peak เพราะเป็น memory-bound

ตัวอย่าง 5.2 · คิดเป็นไบต์แทน word

triad ใช้ 5 words × 8 B / 2 flops = 20 B/F

\[ P = \frac{40\ \text{GB/s}}{20\ \text{B/F}} = 2\ \text{GFlop/s} \]

ได้ผลเท่ากัน เลือกวิธีที่ไม่ต้องหาร 8

ตัวอย่าง 5.3 · กลับทิศ

ถ้าต้องการให้ triad ได้ 50% ของ peak 100 GFlop/s ต้องใช้ bandwidth เท่าไร

\[ b = P \cdot B_c = 50 \times 2.5 = 125\ \text{GW/s} = 1000\ \text{GB/s} \]

ถ้า \(B_c \le B_m\) ได้ \(l = 1\) คือ compute-bound ใช้ peak ได้เต็ม โค้ดที่ข้อมูลอยู่ใน cache ให้ใช้ balance ของ cache (0.5–1 W/F) แทน memory

บทที่ 5.3 · Strong / weak scaling

6 · Amdahl, Gustafson, Efficiency

s = สัดส่วนเวลา serial (ทำขนานไม่ได้), \(1-s\) = ส่วนขนานได้, N = จำนวน worker

\[ S(N) = \frac{1}{s + \frac{1-s}{N}} = \frac{N}{1 + s\,(N-1)} \qquad\qquad \lim_{N\to\infty} S = \frac{1}{s} \]

\[ \varepsilon(N) = \frac{S}{N} = \frac{1}{1 + s\,(N-1)} \qquad\qquad S_{\text{Gustafson}}(N) = s + (1-s)\,N \]

ใช้รูป \(\frac{N}{1 + s(N-1)}\) คิดในใจง่ายที่สุด เช่น s = 0.1, N = 8: \(\frac{8}{1 + 0.7} = \frac{8}{1.7} \approx 4.7\)

ตัวอย่าง 6.1

s = 0.05, N = 16

\[ S = \frac{16}{1 + 0.05 \times 15} = \frac{16}{1.75} \approx 9.14 \qquad \varepsilon = \frac{9.14}{16} \approx 57\% \qquad S_{\max} = \frac{1}{0.05} = 20 \]

ตัวอย่าง 6.2 · หา s จาก speedup ที่วัดได้

\[ s = \frac{N/S - 1}{N - 1} \]

รันบน 8 คอร์ได้ speedup 4

\[ s = \frac{8/4 - 1}{8 - 1} = \frac{1}{7} \approx 0.143 \]

ตัวอย่าง 6.3 · ต้องใช้กี่คอร์

\[ N = \frac{S\,(1-s)}{1 - s\,S} \qquad (S \lt 1/s) \]

s = 0.05 ต้องการ speedup 10

\[ N = \frac{10 \times 0.95}{1 - 0.5} = \frac{9.5}{0.5} = 19\ \text{cores} \qquad \text{check: } \frac{19}{1 + 0.05\times 18} = \frac{19}{1.9} = 10\ \checkmark \]

ตัวอย่าง 6.4 · Weak scaling

s = 0.1, N = 8 งานโตตาม N

\[ S = 0.1 + 0.9 \times 8 = 7.3 \qquad (\text{strong scaling: } 4.7) \]

ตัวอย่าง 6.5 · มีค่าสื่อสาร (ส่วนขยาย จากหนังสือ Hager & Wellein 5.3.6)

ถ้าการสื่อสารเพิ่มเวลา \(kN\) ตามจำนวน worker

\[ T(N) = s + \frac{1-s}{N} + kN \qquad N_{\text{opt}} = \sqrt{\frac{1-s}{k}} \]

s = 0.05, k = 0.01: \(N_{\text{opt}} = \sqrt{95} \approx 9.7\) เพิ่มคอร์เกินนี้กลับช้าลง

s \ N	2	4	8	16	∞
0.05	1.90	3.48	5.93	9.14	20
0.1	1.82	3.08	4.71	6.40	10
0.2	1.67	2.50	3.33	4.00	5

บทที่ 5.3.9 · บทที่ 6 Loop scheduling

7 · Load imbalance และ OpenMP schedule

เวลาของงานขนานคือเวลาของ worker ที่ช้าที่สุด

\[ T_{\text{par}} = \max_i t_i \qquad\qquad \varepsilon = \frac{\sum_i t_i}{N \cdot \max_i t_i} \]

ตัวอย่าง 7.1 · lagger (Fig 5.13)

4 worker ใช้เวลา 10, 10, 10, 14

\[ \varepsilon = \frac{44}{4 \times 14} = \frac{44}{56} \approx 78.6\% \]

ถ้าแบ่งงานสมดุล ทุกตัวจะใช้ 11 วินาที

แบ่งรอบลูปตาม schedule

ตัวอย่าง 7.2

ลูป 10 รอบ, 4 threads

static (ไม่ระบุ chunk): ก้อนต่อเนื่องเท่า ๆ กัน \(\lceil 10/4 \rceil = 3\) ได้ T0: 1–3, T1: 4–6, T2: 7–8, T3: 9–10 (3, 3, 2, 2)
static,2: แจกก้อนละ 2 วนรอบ T0: 1–2, 9–10 · T1: 3–4 · T2: 5–6 · T3: 7–8
dynamic,2: ก้อนละ 2 ใครว่างก่อนรับก่อน ลำดับขึ้นกับเวลาจริง

ตัวอย่าง 7.3 · งานรอบที่ i ใช้เวลา i หน่วย, 8 รอบ, 2 threads

รวมงาน \(1+2+\dots+8 = 36\) อุดมคติคือ 18 ต่อเธรด

\[ \textbf{static: } T_0 = 1+2+3+4 = 10,\ \ T_1 = 5+6+7+8 = 26 \;\Rightarrow\; \varepsilon = \frac{36}{2 \times 26} \approx 69\% \]

\[ \textbf{static,1: } T_0 = 1+3+5+7 = 16,\ \ T_1 = 2+4+6+8 = 20 \;\Rightarrow\; \varepsilon = \frac{36}{2 \times 20} = 90\% \]

ผลรวม 1 ถึง n = \(\frac{n(n+1)}{2}\) ใช้บ่อยมากในโจทย์งานไม่เท่ากัน

บทที่ 4.5 · บทที่ 10 MPI

8 · Network และต้นทุน MPI

\[ T = T_l + \frac{N}{B} \qquad\qquad B_{\text{eff}} = \frac{N}{T_l + N/B} \qquad\qquad N_{1/2} = T_l \cdot B \]

\(N_{1/2}\) คือขนาดข้อความที่ได้ bandwidth ครึ่งหนึ่งของ B (แทน \(B_{\text{eff}} = B/2\) แล้วแก้สมการ)

ตัวอย่าง 8.1 · Gigabit Ethernet (Fig 4.10): T_l = 76 µs, B = 111 MB/s = 111 B/µs

ข้อความ 100 B:

\[ T = 76 + \frac{100}{111} \approx 76.9\ \mu\text{s} \qquad B_{\text{eff}} = \frac{100}{76.9} \approx 1.3\ \text{MB/s} \]

latency ครอบงำเวลาเกือบทั้งหมด

ข้อความ 1 MB = \(10^{6}\) B:

\[ T = 76 + \frac{10^{6}}{111} \approx 76 + 9009 = 9085\ \mu\text{s} \approx 9.1\ \text{ms} \qquad B_{\text{eff}} \approx 110\ \text{MB/s} \]

\[ N_{1/2} = 76 \times 111 \approx 8436\ \text{B} \approx 8.4\ \text{KB} \]

ตัวอย่าง 8.2 · InfiniBand (Fig 4.11): T_l = 4.14 µs, B = 1320 MB/s

\[ N_{1/2} = 4.14 \times 1320 \approx 5465\ \text{B} \]

ตัวอย่าง 8.3 · PingPong

ข้อความไปและกลับใช้ \(2T\) โปรแกรมใน slide 29 จึงหาร 2: TIME = (E-S)/2

ตัวอย่าง 8.4 · รวมผลแบบ Listing 9.3

8 ranks, rank 0 รับผล 1 double (8 B) จากอีก 7 ranks ทีละตัวบน InfiniBand

\[ T \approx 7 \times \Big(4.14 + \frac{8}{1320}\Big) \approx 7 \times 4.15 \approx 29\ \mu\text{s} \]

ข้อความเล็กมาก เวลาเกือบทั้งหมดคือ latency ถ้าใช้ MPI_Reduce แบบ tree จะเหลือประมาณ \(\log_2 8 = 3\) ขั้น ≈ 12.4 µs

ข้อความเล็ก ใช้ \(T \approx T_l\) ได้เลย ข้อความใหญ่มาก ใช้ \(T \approx N/B\) ได้เลย ต้องคิดทั้งสองเทอมเฉพาะเมื่อ N ใกล้ \(N_{1/2}\)

ลองทำก่อนเปิดเฉลย · ไม่ใช้เครื่องคิดเลข

9 · โจทย์ฝึก

ข้อ 1 · CPU 16 คอร์, 3 GHz, AVX-512, FMA 2 หน่วยต่อคอร์ peak (double) เท่าไร

\[ 2 \times \frac{512}{64} \times 2 = 32\ \text{flops/cycle} \qquad P_{\max} = 16 \times 3 \times 32 = 1536\ \text{GFlop/s} \]

ข้อ 2 · โปรแกรมมีส่วน serial 20% speedup สูงสุดเท่าไร และบน 4 คอร์ได้เท่าไร

\[ S_{\max} = \frac{1}{0.2} = 5 \qquad S(4) = \frac{4}{1 + 0.2 \times 3} = \frac{4}{1.6} = 2.5 \]

ข้อ 3 · bandwidth 64 GB/s, peak 256 GFlop/s รัน daxpy (A = A + s·B) ขนาดใหญ่ ได้กี่ GFlop/s และกี่ % ของ peak

\[ b = \frac{64}{8} = 8\ \text{GW/s} \qquad B_c = \frac{3}{2} = 1.5 \qquad P = \frac{8}{1.5} \approx 5.33\ \text{GFlop/s} \]

\[ \frac{5.33}{256} \approx 2.1\% \]

ข้อ 4 · ส่งข้อความ 10 KB (10⁴ B) บน Gigabit Ethernet (76 µs, 111 MB/s) ใช้เวลาและได้ B_eff เท่าไร

\[ T = 76 + \frac{10^{4}}{111} \approx 76 + 90 = 166\ \mu\text{s} \qquad B_{\text{eff}} = \frac{10^{4}}{166} \approx 60\ \text{MB/s} \]

ขนาดนี้ใกล้ \(N_{1/2}\) ≈ 8.4 KB จึงได้ราวครึ่งหนึ่งของ B

ข้อ 5 · รันบน 8 คอร์ได้ speedup 6 ส่วน serial เป็นเท่าไร

\[ s = \frac{8/6 - 1}{8 - 1} = \frac{1/3}{7} = \frac{1}{21} \approx 0.048 \]

ข้อ 6 · cache direct-mapped 16 KB, line 64 B ที่อยู่ 20480 ลง index ไหน

\[ \#\text{lines} = \frac{16384}{64} = 256 \qquad \left\lfloor \frac{20480}{64} \right\rfloor = 320 \qquad 320 \bmod 256 = 64 \]

ข้อ 7 · pipeline 4 ขั้น ทำ 12 งาน ใช้กี่รอบ และ speedup เทียบไม่มี pipeline

\[ T = 4 + 12 - 1 = 15 \qquad \text{Speedup} = \frac{4 \times 12}{15} = \frac{48}{15} = 3.2 \]

ข้อ 8 · 3 workers ใช้เวลา 8, 12, 10 วินาที efficiency เท่าไร

\[ \varepsilon = \frac{8 + 12 + 10}{3 \times 12} = \frac{30}{36} \approx 83\% \]

ข้อ 9 · ลูป 12 รอบ, 3 threads, schedule(static,2) thread ไหนได้รอบไหน

T0: 1–2, 7–8 · T1: 3–4, 9–10 · T2: 5–6, 11–12

ข้อ 10 · เครื่องมี B_m = 0.1 W/F โค้ด dot product (B_c = 1) เป็น memory-bound หรือ compute-bound ได้กี่ % ของ peak

\[ B_c = 1 \gt B_m = 0.1 \;\Rightarrow\; \text{memory-bound} \qquad l = \frac{0.1}{1} = 10\% \]

เรื่องเดียวกันทั้งวิชา: จากคอร์เดียวสู่ซูเปอร์คอมพิวเตอร์

ตารางเปรียบเทียบที่มักออกสอบ

ลำดับชั้นหน่วยความจำ

SIMD · Vector · MIMD

UMA · ccNUMA · Distributed memory

Multicore · Multithreaded CPU · Multithreading

OpenMP · MPI · Python

ตัวอย่างคำนวณ Balance: ทำไมโค้ดส่วนใหญ่ได้ไม่ถึง peak

0 · หน่วยที่ต้องแปลงให้คล่อง

1 · Peak FLOPS

2 · คำนวณ MFlop/s จากผลวัด

3 · Pipeline

4 · Cache: จำนวน line, การ map, miss rate

Miss rate ตาม stride

ที่อยู่ของ element ในเมทริกซ์ N×N (double)

5 · Machine balance, code balance, lightspeed

นับ Bc ของลูปมาตรฐาน

6 · Amdahl, Gustafson, Efficiency

7 · Load imbalance และ OpenMP schedule

แบ่งรอบลูปตาม schedule

8 · Network และต้นทุน MPI

9 · โจทย์ฝึก

นับ B_c ของลูปมาตรฐาน