Superlinear Speedup

1เรื่องจริงที่ทำให้ผมจำคำว่า Superlinear Speedup มาจนวันนี้

เมื่อปี 2002 ผมใช้ Parallel Algorithm แก้ปัญหา Bioinformatics ที่มี Dynamic Programming เป็นแกน งานแบบนี้สร้างและอ้างข้อมูลในตารางขนาดใหญ่ หากจัดวางข้อมูลหรือแบ่งงานไม่เหมาะ หน่วยประมวลผลไม่ได้เสียเวลาที่สูตรคำนวณเป็นหลัก แต่เสียเวลารอข้อมูลจากหน่วยความจำระดับที่ช้ากว่า

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

ตัวเลข 281.25% ฟังดูเหมือนเครื่องแต่ละตัวทำงานเกินกำลังของตนเอง แต่ความหมายที่ถูกคือ baseline แบบลำดับแบก overhead บางอย่างไว้มาก พอแบ่งงาน working set ของแต่ละ CPU เล็กลงและเข้ากับ Cache ได้ดีขึ้น overhead นั้นลดลงอย่างมหาศาล เราจึงได้ทั้งประโยชน์จากการทำงานพร้อมกันและประโยชน์จาก Memory Hierarchy

ยี่สิบปีผ่านไป แนวคิดเดิมเดินทางไปไกลกว่าเครื่องเดิม

ต่อมาแนวคิดนี้ถูกนำไปสอนในวิชา Big Data Analytics ให้กับนักศึกษาสาขาสถิติ นักศึกษาคนหนึ่งนำหลักเดียวกันไปแก้ปัญหา Dynamic Programming ที่ใหญ่กว่ามากบน Apache Spark และลดเวลาจากกว่าหนึ่งปีเหลือประมาณ 13 ชั่วโมง

เรื่องที่น่าสนใจไม่ใช่การนำโค้ดเก่าไปวางบนเครื่องใหม่ เพราะสถาปัตยกรรมและ framework ต่างกันมาก สิ่งที่ถูกส่งต่อคือ วิธีมองปัญหา: อย่าดูแต่จำนวน operation ให้ดูด้วยว่าข้อมูลเคลื่อนผ่าน Cache, RAM, Disk และ Network อย่างไร และถามว่าการแบ่งงานสามารถเปลี่ยนระดับของหน่วยความจำที่ข้อมูลใช้งานอยู่ได้หรือไม่

แต่เรื่องเล่าที่ดีต้องมาพร้อมคำถามที่เข้มงวด

ก่อนประกาศว่าได้ Superlinear Speedup เราต้องตรวจว่าโปรแกรมสองแบบตอบโจทย์เดียวกัน ใช้ input เดียวกัน และวัดขอบเขตเวลาเท่ากันหรือไม่ โปรแกรมแบบขนานอาจเปลี่ยนอัลกอริทึม ใช้ approximation หรืออ่านข้อมูลที่ cache ไว้แล้ว ขณะที่ baseline อ่านจากดิสก์เย็น ๆ หากไม่แยกปัจจัยเหล่านี้ ตัวเลขอาจน่าตื่นเต้นแต่สรุปอะไรไม่ได้

2นิยาม Speedup, Efficiency และ Cost ให้ชัดก่อน

Efficiency เกิน 100% ไม่ได้แปลว่า CPU สร้างเวลาเพิ่ม

Efficiency เป็นตัวชี้วัดเทียบกับ baseline ไม่ใช่ประสิทธิภาพทางพลังงานหรืออัตราการใช้ CPU โดยตรง เมื่อ baseline เสียเวลารอ memory มาก แต่แบบขนานลดการรอนั้นได้ ค่า (E_p) จึงเกิน 1 ได้ สิ่งที่เกิน 100% คือ “ประโยชน์เมื่อเทียบกับการหารงานตามจำนวน CPU” ไม่ใช่กฎทางกายภาพของ CPU

Cost บอกว่าเร็วขึ้นด้วยทรัพยากรเท่าใด

โปรแกรมที่ใช้ 100 เครื่องและจบใน 1 นาทีอาจเร็วมาก แต่ใช้ทรัพยากรรวม 100 machine-minutes ขณะที่เครื่องเดียวใช้ 50 นาที โปรแกรมแรกมี latency ดีกว่าแต่ cost สูงกว่า การประเมิน Big Data จึงควรดูทั้งเวลาจบ ค่าใช้จ่าย และปริมาณงาน ไม่ควรยก Speedup เป็นคำตอบเดียว

Strong Scaling กับ Weak Scaling

Superlinear ที่เกิดจาก working set พอดี Cache มักปรากฏใน strong-scaling บางช่วง เพราะเมื่อเพิ่มเครื่องจน partition ข้าม “หน้าผา” ของ Memory Hierarchy เวลาลดลงกะทันหัน แต่ถ้าเพิ่มเครื่องต่อไป หลัง working set พอดีแล้ว ผลตอบแทนอาจกลับมาเป็น linear หรือต่ำกว่า linear

3ปัญหาตั้งต้น: การจับคู่ทุกค่าใน x กับทุกค่าใน y

for (int i = 0; i < n; i++)
  for (int j = 0; j < m; j++)
    z[i][j] = functionof(x[i], y[j]);

จำนวนคู่ที่คำนวณคือ O(nm) และจะเขียนเป็น O(n²) ได้เมื่อสมมุติว่า n กับ m โตในระดับเดียวกัน แต่ Big-O บอกจำนวนงานเชิงนามธรรม ยังไม่บอกว่าแต่ละ iteration รอข้อมูลจาก register, cache, RAM หรือ disk นานเพียงใด

Operation Count เท่ากัน เวลาจริงอาจต่างกันมาก

โปรแกรมสองตัวทำการคูณและบวกเท่ากัน แต่ตัวหนึ่งอ่านข้อมูลเรียงต่อเนื่อง ส่วนอีกตัวกระโดดข้าม memory จน cache miss ตลอด ทั้งคู่มี Big-O เท่ากัน แต่เวลาจริงต่างกันหลายเท่า นี่เป็นเหตุผลที่การวิเคราะห์อัลกอริทึมกับการวิเคราะห์สถาปัตยกรรมต้องอ่านควบคู่กัน

Working Set คือข้อมูลที่ต้องใช้ในช่วงหนึ่ง

ข้อมูลทั้งหมดอาจใหญ่หลายร้อยกิกะไบต์ แต่ถ้าในช่วงหนึ่งโปรแกรมใช้จริงเพียง block เล็ก ๆ Working set อาจพอดี Cache ในทางกลับกัน dataset ไม่ใหญ่มาก แต่เข้าถึงแบบกระโดดจน reuse ไม่ทัน Working set ที่มีผลต่อ locality อาจใหญ่กว่าที่คิด การแบ่งงานที่ดีจึงแบ่งตามรูปการเข้าถึง ไม่ใช่แบ่งจำนวน record อย่างเดียว

Temporal และ Spatial Locality

• Temporal locality: ค่าที่เพิ่งใช้มีโอกาสถูกใช้อีกในเวลาใกล้กัน เช่น y[j] ถูกใช้ซ้ำกับค่า x[i] หลายตัว
• Spatial locality: เมื่ออ่านตำแหน่งหนึ่ง ค่าที่อยู่ใกล้กันมีโอกาสถูกใช้ต่อ เช่นเดิน array ตามลำดับ

Cache ดึงข้อมูลเป็น cache line ไม่ใช่ทีละตัวแปร การจัด layout และ loop order ให้เดินตามหน่วยความจำต่อเนื่องจึงลด miss ได้ แม้จำนวน operation ทางคณิตศาสตร์ไม่เปลี่ยน

4เมื่อ Working Set ใหญ่เกินชั้นหน่วยความจำที่เร็วกว่า

คำว่า “swap” ในต้นฉบับใช้เพื่อสร้างภาพว่าข้อมูลถูกย้ายเข้าออก disk ซ้ำ ๆ ในเครื่องสมัยใหม่ควรใช้คำให้ตรงกรณี: cache miss, page fault, paging, application-level spill และ reread from storage มีผู้ควบคุมและรูปแบบต้นทุนต่างกัน การวิเคราะห์ที่ดีต้องดู metric ให้รู้ว่าเกิดแบบใดจริง

แบบจำลองนี้ตั้งใจให้เห็นองค์ประกอบ ไม่ใช่สูตรทำนายเวลาที่แม่นทุกเครื่อง ค่า latency และ bandwidth ซ้อนทับกันได้ ระบบมี prefetch, out-of-order execution และ asynchronous I/O แต่ถ้าส่วนหนึ่งใหญ่กว่าส่วนอื่นมาก การกำจัดส่วนนั้นย่อมเปลี่ยนเวลาได้มากกว่าการเพิ่มความเร็วของ arithmetic เล็กน้อย

Memory Hierarchy เป็นบันได ไม่ใช่สวิตช์สองสถานะ

Superlinear อาจเกิดเมื่อ partition ข้ามขอบระดับใดระดับหนึ่ง ไม่จำเป็นต้องเป็น RAM → Disk เท่านั้น การแบ่งให้ state พอดี L3 Cache ก็สร้างผลมากได้ โดยเฉพาะอัลกอริทึม Dynamic Programming ที่อ่านค่าข้างเคียงซ้ำ ๆ

ทางแก้แรก: จัดลำดับการเข้าถึงให้ swap น้อยลง

ถ้าแบ่ง y เป็น block ที่พอดีกับระดับหน่วยความจำเป้าหมาย แล้วประมวลผลทุกค่า x ที่เกี่ยวข้องให้ครบก่อนเปลี่ยน block เราเพิ่ม data reuse และลดการโหลดซ้ำ เทคนิคนี้เรียกได้ทั้ง blocking หรือ tiling ตามบริบท

เราไม่ควรสรุปว่าจะเหลือ swap “หนึ่งครั้ง” เสมอ เพราะขึ้นกับขนาด block, replacement policy, output และข้อมูลอื่นที่แย่ง Cache ประเด็นที่ถูกคือการจัดลำดับใหม่ลด I/O หรือ miss จากการใช้ข้อมูลซ้ำให้คุ้มก่อนถูกแทนที่

Loop Interchange และ Tiling

for (jb = 0; jb < m; jb += B)
  for (i = 0; i < n; i++)
    for (j = jb; j < min(jb+B, m); j++)
      z[i][j] = functionof(x[i], y[j]);

ตัวอย่างนี้สื่อแนวคิด แต่ loop order ที่ดีที่สุดขึ้นกับ layout ของ z, ขนาดของ x, การเขียน output และ vectorization หากแก้ให้ y reuse ดีขึ้นแต่เขียน z แบบกระโดด เราอาจย้ายปัญหาจาก input ไป output จึงควร profile ทั้งระบบ ไม่เลือกจาก intuition เพียงอย่างเดียว

ก่อนเพิ่มเครื่อง ลองลดงานที่ไม่จำเป็นบนเครื่องเดียว

ถ้าการทำ tiling, compression, sparse representation หรือเปลี่ยน data layout ทำให้ sequential baseline เร็วขึ้น 10 เท่า ตัวเลข speedup ของ parallel version อาจลดลง แต่ผลงานจริงดีขึ้น นี่เป็น paradox ที่สำคัญ: งานวิจัยที่รายงาน speedup ต่ำกว่าอาจมีโปรแกรมเร็วกว่าจริง เพราะ baseline ได้รับการ optimize อย่างยุติธรรมกว่า

5เมื่อแบ่งงานแล้ว Working Set ข้ามหน้าผาของ Memory Hierarchy

// worker 1                              // worker 2 (ทำพร้อมกัน)
for (i=0; i<n; i++)                       for (i=0; i<n; i++)
  for (j=0; j<memory_size; j++)             for (j=memory_size+1; j<n; j++)
    z[i][j] = functionof(x[i],y[j]);          z[i][j] = functionof(x[i],y[j]);

CPU 8 ตัวบนเครื่องเดียว ไม่เท่ากับ 8 เครื่องเสมอไป

คำว่า CPU ในเอกสารเก่าอาจหมายถึง processor จริงหลายตัว ขณะที่เครื่องปัจจุบันมี socket, core, hardware thread และ cache ที่แบ่งปันกันต่างระดับ หาก 8 cores แชร์ memory bandwidth หรือ L3 Cache เดียวกัน การแบ่งงานไม่ได้เพิ่มทรัพยากรทุกชนิดแปดเท่า ในทางกลับกันหลาย socket อาจมี memory controller แยกกันและให้ aggregate bandwidth สูงขึ้น

Aggregate Memory Capacity และ Aggregate Bandwidth

การใช้หลายเครื่องเพิ่มทั้งความจุ RAM รวมและ bandwidth รวม หาก single-node baseline ถูกจำกัดด้วย memory bandwidth การกระจายไปหลาย node อาจเพิ่มช่องทางอ่านข้อมูลพร้อมกัน แม้แต่ละ node ไม่ได้ประมวลผลเร็วกว่าเดิม นี่เป็นอีกสาเหตุหนึ่งที่ Speedup อาจสูงกว่าการนับ core อย่างผิวเผิน

NUMA: Memory ไม่ได้อยู่ห่างจากทุก Core เท่ากัน

บนเครื่องหลาย socket หน่วยความจำที่ผูกกับ socket เดียวกันเข้าถึงได้เร็วกว่า remote NUMA node หาก thread ถูกย้ายข้าม socket หรือข้อมูลถูก allocate คนละ node อาจเสีย locality การ pin thread และ first-touch placement ช่วยได้ในบาง workload แต่ต้องวัดจริง การเพิ่ม core โดยไม่สน NUMA อาจทำให้ performance แย่ลงแทนที่จะดีขึ้น

False Sharing: แบ่งตัวแปรแล้วแต่ยังแย่ง Cache Line เดียวกัน

สอง thread อาจเขียน counter คนละตัว แต่ counter อยู่ใน cache line เดียวกัน Cache coherence จึงส่ง line กลับไปกลับมาระหว่าง cores เหมือนคนสองคนเขียนคนละช่องบนกระดาษแผ่นเดียวและต้องส่งทั้งแผ่นทุกครั้ง ปัญหานี้เรียก false sharing การ padding หรือจัด layout ใหม่อาจลด overhead ได้

Cache Capacity ไม่ใช่เหตุผลเดียว

• Conflict miss ลดลง: การแบ่งข้อมูลเปลี่ยน mapping ของ address ต่อ cache set
• Translation Lookaside Buffer ดีขึ้น: working set ของ page translation เล็กลง
• Branch behavior เปลี่ยน: partition มีข้อมูลคล้ายกันมากขึ้นและทำนาย branch ง่ายขึ้น
• Vectorization ง่ายขึ้น: block เล็กและต่อเนื่องอาจช่วย compiler สร้าง SIMD
• Compression ทำงานต่างกัน: partition บางชนิดบีบอัดหรือถอดรหัสได้มีประสิทธิภาพกว่า

Superlinear มักเกิดเป็นช่วง ไม่ได้โตต่อไปตลอด

ลองเพิ่ม p จาก 1, 2, 4, 8, 16 เครื่อง ช่วง 1→4 อาจยัง sublinear เพราะทุก partition ใหญ่เกิน RAM พอถึง 8 partition จึงพอดีและเวลาไหลลงแรง เกิด superlinear เทียบ baseline แต่เมื่อเพิ่มเป็น 16 เครื่อง ข้อมูลพอดีอยู่แล้ว ประโยชน์ใหม่เหลือแค่แบ่งงาน ขณะที่ communication เพิ่ม ผลตอบแทนจึงลดลง

6Superlinear เกิดได้จากอะไรบ้าง

Cache effect เป็นคำอธิบายที่สำคัญ แต่ไม่ใช่คำอธิบายเดียว เราควรจัดสาเหตุเป็นหมวด เพราะแต่ละหมวดพิสูจน์และทำซ้ำต่างกัน

1) Cache, Paging และ Spill ลดลง

เป็นกรณีหลักของบทนี้ การแบ่งข้อมูลทำให้ state ต่อ worker เล็กลงและ reuse ในหน่วยความจำเร็วขึ้น สัญญาณที่คาดว่าจะเห็นคือ cache miss rate ลด, major page fault ลด, disk read/write ลด หรือ Spark spill metrics ลด หากเวลาลดแต่ metrics เหล่านี้ไม่เปลี่ยน ควรมองหาสาเหตุอื่น

2) รวมทรัพยากรหลายชนิด ไม่ใช่เพิ่ม CPU อย่างเดียว

เมื่อเพิ่ม node เราเพิ่ม RAM, cache, local SSD และ memory bandwidth ไปด้วย การกล่าวว่า “ใช้ CPU 8 ตัว” อาจซ่อนว่าระบบแบบขนานมี RAM รวมแปดเท่าและ disk channels หลายชุด หากต้องการรู้สาเหตุ ควรทดลองแยก เช่นใช้ core เท่าเดิมแต่จำกัด memory หรือเปรียบเทียบ scale-up กับ scale-out

3) Parallel Algorithm ทำงานน้อยกว่า Sequential Algorithm

บางครั้งโปรแกรมขนานไม่ได้เป็นเพียงเวอร์ชันแบ่งครึ่งของโปรแกรมลำดับ แต่ใช้โครงสร้างข้อมูล การประมาณ หรือ pruning ต่างกัน หากจำนวน operation ลดลง เราได้ algorithmic speedup ประกอบกับ parallel speedup การรายงานยังทำได้ แต่ควรบอกให้ชัดว่าเปรียบเทียบ implementation ต่างอัลกอริทึม ไม่ใช่สรุปว่า hardware อย่างเดียวสร้างผลทั้งหมด

4) Search Anomaly และ Branch-and-Bound

ในปัญหา search, optimization หรือ game tree worker หลายตัวสำรวจคนละส่วน บางตัวอาจพบคำตอบดีเร็ว แล้วส่ง bound ไปตัดกิ่งขนาดใหญ่ที่ sequential order เดิมจะยังไม่พบ ผลคือ parallel run สำรวจ node น้อยกว่าอย่างมาก แต่ใน run อื่นอาจพบ bound ช้าและไม่ได้ผลเช่นนั้น Superlinear แบบนี้จึงขึ้นกับ search order และข้อมูล

5) Randomized Algorithm

เมื่อ worker ใช้ random seed ต่างกัน โอกาสที่อย่างน้อยหนึ่งตัวพบเส้นทางดีเร็วเพิ่มขึ้น ลักษณะนี้คล้าย portfolio search Speedup อาจ superlinear ในค่าเฉลี่ยบาง distribution แต่ต้องรายงานหลาย run, seed และสถิติการกระจาย ไม่ควรเลือกเฉพาะรอบที่ดีที่สุด

6) Baseline ไม่ดีหรือวัดไม่เท่ากัน

Superlinear ที่เกิดจาก baseline ไม่ได้ optimize ไม่ใช่หลักฐานว่าปรากฏการณ์ไม่มีจริง แต่ไม่ใช่คำตอบที่น่าภูมิใจเท่าใดนัก ถ้า sequential code ใช้ compiler flag ต่างกัน ไม่ทำ tiling หรือใช้ algorithm คนละคุณภาพ เรากำลังวัดช่องว่างของ implementation มากกว่าประโยชน์ของ parallelism

Amdahl’s Law ไม่ได้ถูกทำลาย แต่สมมุติฐานถูกเปลี่ยน

Amdahl’s Law มองสัดส่วนงานลำดับและงานขนานภายใต้แบบจำลองที่ workload คงเดิม หาก parallel execution เปลี่ยน cache behavior หรือจำนวนงานจริง เวลาต่อหน่วยงานไม่เหมือน baseline แล้ว การใช้สูตรง่าย ๆ เพื่อประกาศว่า “เป็นไปไม่ได้” จึงใช้แบบจำลองผิดขอบเขต

ถ้า (f=0) สูตรให้ (S_p=p) แต่ Cache effect ทำให้ต้นทุนของส่วน ((1-f)) ต่อ operation ลดลงด้วย เราจึงต้องเพิ่มพารามิเตอร์ด้าน memory หรือใช้แบบจำลองที่ละเอียดกว่า ไม่ใช่บังคับข้อมูลให้เข้ากับสูตรที่ละตัวแปรสำคัญออกไป

Gustafson’s Law ตอบอีกคำถามหนึ่ง

Amdahl ถามว่างานขนาดคงเดิมเร็วขึ้นเพียงใด ส่วน Gustafson มองว่าเมื่อมีทรัพยากรมากขึ้น เรามักแก้ปัญหาใหญ่ขึ้นภายในเวลาที่รับได้ จึงเหมาะกับ weak scaling มากกว่า แต่ Gustafson ไม่ใช่คำอธิบาย Superlinear โดยตรง เราไม่ควรนำกฎสองข้อมาแข่งขันว่าใคร “ถูกกว่า” เพราะตอบคนละคำถาม

7เชื่อมโยงกับ Big Data และ Spark

Dataset 100 GB กับ RAM 64 GB ไม่ได้บอกว่าจะ Spill แน่นอน

ต้นฉบับยกตัวอย่าง dataset 100 GB บน RAM 64 GB แล้วสรุปว่าต้อง spill คำอธิบายนี้ง่ายเกินจริง เพราะงาน scan/filter สามารถ stream ทีละ partition โดยไม่ต้องเก็บ dataset ทั้งก้อนใน RAM งานจะ spill เมื่อ operator ต้องรักษาสถานะ เช่น sort, hash aggregation, join หรือ cache และ state นั้นเกิน memory ที่มี

Partition เล็กลงช่วยอะไร

• ลดข้อมูลที่ task หนึ่งต้อง sort หรือ hash พร้อมกัน
• สร้าง task มากพอให้ scheduler กระจายงานและทดแทน straggler
• ลดความเสียหายเมื่อ task ล้มและต้องคำนวณใหม่
• อาจทำให้ working set เข้ากับ Cache หรือ RAM ได้ดีขึ้น

แต่ partition เล็กเกินไปทำให้มี task จำนวนมาก เพิ่ม scheduling overhead, task startup, metadata, network connection และไฟล์เล็ก ผลลัพธ์จึงมีช่วงที่เหมาะ ไม่ใช่ “ยิ่งเล็กยิ่งดี”

จำนวน Partition ไม่เท่ากับจำนวน Core

มักมี partition มากกว่า core เพื่อให้ load balancing ทำงานได้ หากมี 8 cores และ 8 partitions แล้ว partition หนึ่งหนักกว่าที่เหลือสิบเท่า เจ็ด core จะว่างรอตัวสุดท้าย หากมี partitions มากขึ้น scheduler มีโอกาสเฉลี่ยความไม่แน่นอนได้ดีขึ้น แต่ถ้า key เดียวหนักมาก การเพิ่ม partition ทั่วไปอาจไม่แก้ เพราะ key เดียวกันยังไป partition เดียว

Spill ใน Spark เกิดที่ Operator ใด

reduceByKey ช่วยก่อนจะต้องเพิ่มเครื่อง

ถ้างานเป็นการรวมตาม key การใช้ reduceByKey หรือ partial aggregation ลด record ก่อน Shuffle ได้มากกว่า groupByKey ในหลายกรณี นี่เป็นการลด working set ด้วย Algebra ไม่ใช่ hardware การเลือก representation และ operator ที่ดีอาจกำจัด spill ได้โดยไม่เพิ่ม node

Broadcast Join เปลี่ยนรูปการเคลื่อนข้อมูล

หากตารางหนึ่งเล็กพอ broadcast ไปทุก executor ได้ เราหลีกเลี่ยงการ Shuffle ตารางใหญ่ทั้งสองฝั่ง แต่ broadcast table ต้องพอดี memory ของ executor และถูกทำสำเนาหลายชุด หากประเมินขนาดผิด เราอาจเปลี่ยนจาก network bottleneck ไปเป็น memory pressure การตัดสินใจจึงต้องอาศัยสถิติและ physical plan

Cache มีประโยชน์เมื่อใช้ซ้ำ ไม่ใช่เพราะ RAM ว่าง

Dataset ที่ใช้ครั้งเดียวไม่จำเป็นต้อง cache การเก็บอาจเพิ่ม serialization และ eviction หากใช้ซ้ำหลาย iterations เช่น machine learning หรือ graph algorithm การ cache working set ที่เหมาะช่วยตัดการอ่านและคำนวณ lineage ซ้ำ จุดนี้เชื่อมกับบทก่อน: Immutability ทำให้ cached partition ยังอ้างข้อมูลรุ่นเดิมได้ และ Lazy Evaluation ทำให้ cache ยังไม่เกิดจน action เรียกใช้

Dynamic Allocation ทำให้การทดลองซับซ้อนขึ้น

หากจำนวน executor เปลี่ยนระหว่าง run การระบุว่า “ใช้ p processors” อาจไม่ตรงตลอดเวลา การวัด scaling ควรควบคุมจำนวน executor, cores, memory และ concurrent jobs ให้ชัด หรืออย่างน้อยรายงาน executor timeline และ resource-seconds ไม่เช่นนั้น Speedup อาจมาจากทรัพยากรจริงที่ต่างจากค่าที่ตั้งใจ

Cloud VM มีความแปรปรวน

เครื่องเสมือนอาจแชร์ host, network และ storage กับผู้ใช้อื่น มี warm cache, burst credit หรือ throttling การทดลองครั้งเดียวจึงไม่น่าเชื่อถือ ควรรันซ้ำ สุ่มลำดับ configuration และรายงาน median พร้อม percentile หรือช่วงความเชื่อมั่นตามความเหมาะสม

8วิธีพิสูจน์ว่า Superlinear ที่เห็นมาจากอะไร

คำอธิบายเรื่อง Cache ฟังสมเหตุสมผล แต่ความสมเหตุสมผลยังไม่ใช่หลักฐาน เราต้องออกแบบการทดลองที่ทำให้สาเหตุคู่แข่งค่อย ๆ ถูกตัดออก

ขั้นที่ 1: กำหนด Baseline ให้ยุติธรรม

• ใช้อัลกอริทึมและความแม่นยำระดับเดียวกัน
• ใช้ compiler optimization, library และ data format เทียบเท่า
• รวม/ไม่รวมเวลาอ่านข้อมูลและ startup ด้วยขอบเขตเดียวกัน
• ยืนยันผลลัพธ์ ไม่ใช่แค่วัดว่าโปรแกรมจบเร็ว
• ใช้ sequential implementation ที่ได้รับการ optimize สมเหตุสมผล

ขั้นที่ 2: วัดหลายขนาดและหลายจำนวน Worker

อย่าวัดเพียง p=1 กับ p=8 ให้ใช้ 1, 2, 4, 8, 16 หากทำได้ แล้ววาด runtime, speedup, efficiency และ cost จุดที่กราฟเปลี่ยนความชันอาจตรงกับ working set ที่พอดี Cache/RAM หากมีเพียงสองจุด เราไม่เห็นหัวเข่าและอธิบายกลไกยาก

ขั้นที่ 3: เก็บ Hardware Counters และ System Metrics

ขั้นที่ 4: ทำ Controlled Experiment

หากสงสัย RAM capacity ให้จำกัด memory ของ sequential run หลายระดับ หากสงสัย Cache ให้เปลี่ยน problem size รอบขอบความจุ หรือใช้ blocking size หลายค่า หากสงสัย search order ให้ตรึง seed และนับ states ที่สำรวจ การเปลี่ยนทีละปัจจัยช่วยแยก correlation ออกจาก cause

ขั้นที่ 5: แยก Cold Run กับ Warm Run

Cold run อาจรวมการอ่านจาก storage และ JIT compilation ส่วน warm run ได้ประโยชน์จาก OS page cache, JVM JIT, connection pool และ cached data ทั้งสองแบบมีความหมาย แต่ต้องระบุและเทียบแบบเดียวกัน ควร warm up ตาม protocol แล้วรายงานอย่างโปร่งใส หรือรายงานทั้ง cold และ steady-state

ขั้นที่ 6: รันซ้ำและรายงาน Distribution

ค่าเฉลี่ยอย่างเดียวถูกลากโดย outlier ได้ ควรรายงานจำนวนรอบ median, min/max หรือ percentile พร้อมระบุเครื่องและ workload อื่นที่รันร่วมกัน สำหรับ randomized search ต้องรายงานหลาย seed ไม่เลือกเฉพาะ best case

ขั้นที่ 7: ตรวจคำตอบและปริมาณงาน

โปรแกรมที่เร็วกว่ามากอาจคำนวณไม่ครบ ใช้ early stopping คนละเกณฑ์ หรือผลตกหล่นเพราะ race condition จึงควรมี checksum, objective value, tolerance และ count ของ states/records ที่ประมวลผล ตัวเลข performance ที่ไม่มี correctness ไม่ใช่ Speedup แต่เป็นโปรแกรมที่เลิกงานก่อน

9แล็บย่อ: ตามหาหัวเข่าของ Memory Hierarchy

แล็บนี้ไม่ต้องใช้คลัสเตอร์ใหญ่ก็ทำได้ เป้าหมายไม่ใช่สร้างสถิติโลก แต่ฝึกเชื่อมกราฟเวลารันกับ working set และ Cache

แนวทางการทดลอง

1. สร้าง array หลายขนาด ตั้งแต่เล็กกว่า Cache ไปจนใหญ่กว่า RAM ส่วนที่จัดสรรได้อย่างปลอดภัย
2. เขียน kernel ที่อ่านซ้ำแบบต่อเนื่อง และอีกแบบที่เข้าถึงตำแหน่งสุ่ม
3. วัด throughput หลายรอบ แยก warm-up และเก็บ median
4. ทดลอง blocking size หลายค่าโดยไม่เพิ่ม thread
5. เพิ่ม thread 1, 2, 4, 8 และดูว่าจุดเปลี่ยนสัมพันธ์กับ working set ต่อ thread หรือไม่
6. ถ้ามีเครื่องมือ ให้เก็บ cache-miss และ page-fault counters

ตารางบันทึกที่ควรมี

สิ่งที่ต้องอภิปราย

• กราฟมีหัวเข่าตรงขนาดใด และตรงกับ Cache level ใดหรือไม่
• Sequential tiling ช่วยมากเพียงใดก่อนเพิ่ม thread
• เมื่อเพิ่ม thread Memory bandwidth อิ่มตัวตรงไหน
• ถ้าเกิด Superlinear มี metric ใดเปลี่ยนพร้อมกัน
• ถ้าไม่เกิด เป็นเพราะ working set ไม่ข้ามระดับหรือ overhead สูงเกินไป

10สรุปและขั้นตอนถัดไป

Superlinear Speedup ไม่ใช่เรื่องเหนือธรรมชาติ และไม่ใช่สิ่งที่ควรเกิดทุกครั้ง มันเป็นสัญญาณว่าการเพิ่ม parallelism เปลี่ยนปัจจัยอื่นไปพร้อมกัน—working set พอดี Cache/RAM, spill ลด, bandwidth รวมเพิ่ม, search order เปลี่ยน หรือจำนวนงานจริงลดลง

กรณีปี 2002 ที่ลดเวลาจาก 7.5 วันเหลือ 8 ชั่วโมงบน CPU 8 ตัวมีคุณค่ามากกว่าตัวเลข 22.5 เท่า เพราะสอนให้มองข้ามจำนวน CPU ไปยังเส้นทางของข้อมูล และเมื่อแนวคิดเดียวกันถูกนักศึกษานำไปใช้กับ Dynamic Programming บน Spark ในอีกยี่สิบปีต่อมา สิ่งที่สืบทอดไม่ใช่ platform แต่คือวิธีคิด

สิ่งที่ควรจำจากบทนี้มีดังนี้:

• Speedup ต้องมี baseline ที่ยุติธรรมและขอบเขตเวลาชัดเจน
• Big-O เท่ากันไม่ได้แปลว่าเวลาจริงเท่ากัน เพราะ Memory Hierarchy เปลี่ยน constant factor ได้มาก
• Working set ต่อ worker สำคัญกว่าขนาด dataset รวมเพียงตัวเลขเดียว
• Dataset ใหญ่กว่า RAM ไม่ได้แปลว่าจะ spill เสมอ ต้องดู state ของ operator
• Superlinear อาจเกิดจาก Cache, aggregate resources, algorithm, search order หรือ measurement artifact
• คำอธิบายควรมี metric รองรับ ไม่ใช่เดาจาก runtime เพียงสองค่า
• การ optimize sequential baseline อาจทำให้ Speedup ลดลง แต่ระบบจริงเร็วขึ้น ซึ่งเป็นผลลัพธ์ที่ดีกว่า

บทถัดไปจะเปลี่ยนจากคำถามว่า “ทำอย่างไรให้เร็วขึ้น” ไปสู่คำถามว่า “เมื่อข้อมูลอยู่หลายเครื่อง เราจะให้แต่ละสำเนาเห็นความจริงแบบใด” ผ่าน CAP, ACID, BASE และ NoSQL เป็นการย้ายจากข้อจำกัดของเวลาและหน่วยความจำ ไปสู่ข้อจำกัดของความสอดคล้องและความล้มเหลวของเครือข่าย