ในยุคที่วงการคอมไพเลอร์ ML ถูกครอบงำโดยการเรียนรู้แบบเสริมกำลัง การปรับแต่งอัตโนมัติ และโมเดลขนาดใหญ่ โค้ด C++ บริสุทธิ์ที่มีเพียงไม่กี่พันบรรทัดและแทบไม่มีการพึ่งพาใดๆ กลับคว้าตำแหน่งชนะเลิศในสาขาวิศวกรรมระบบ (Track A) ของการแข่งขัน Google MLSys Competition 2026[1] โค้ดนี้ไม่ต้องพึ่งพาการฝึกฝน ไม่เกี่ยวข้องกับกลไกกล่องดำ และไม่มีองค์ประกอบที่คลุมเครือ — “เคล็ดลับ” ทั้งหมดที่นำไปสู่ชัยชนะถูกจัดวางไว้อย่างเปิดเผยในไดเรกทอรี source/
- การจัดตารางกราฟคำนวณ DAG โดยใช้การค้นหาแบบบีม สำหรับการจำลองการจัดตารางไทล์ภายใต้ข้อจำกัดของหน่วยความจำเร็วที่จำกัด
- โค้ดโครงการ: https://github.com/wenqi-deng/mlsys-2026-graph-scheduler
- หน้าผู้เขียน: https://wenqi-deng.github.io/
- บทความเต็มประมาณ 9,000 คำ ใช้เวลาอ่าน 35 นาที เวอร์ชันพอดแคสต์ 29 นาที
โซลูชันนี้มาจากนักศึกษาปริญญาตรีสาขา Turing Class คณะวิทยาการสารสนเทศและเทคโนโลยี มหาวิทยาลัยปักกิ่ง Wenqi Deng[2] ภายใต้การแนะนำของศาสตราจารย์ Xupeng Miao แห่งมหาวิทยาลัยปักกิ่ง
โซลูชันนี้มุ่งเน้นไปที่ปัญหาคลาสสิกที่มีมายาวนานในสาขาระบบ ML — แต่ครั้งนี้ถูกกลั่นกรองออกมาอย่างแม่นยำเป็นพิเศษ: เมื่อกำหนด DAG ของโอเปอเรเตอร์ ชุดขนาดไทล์ของฮาร์ดแวร์ และโครงสร้างหน่วยความจำสองชั้น “หน่วยความจำเร็ว + หน่วยความจำช้า” จะตัดกราฟการคำนวณออกเป็นกราฟย่อยหลายกราฟ และเลือกขนาดไทล์ ลำดับการ遍历 และกลยุทธ์การคงอยู่ (retain) สำหรับแต่ละกราฟย่อย เพื่อให้เวลาแฝงโดยรวมน้อยที่สุดได้อย่างไร
นี่ไม่ใช่ปัญหาการตัดสินใจเฉพาะที่ที่อัลกอริทึมแบบละโมบขั้นตอนเดียวจะแก้ไขได้: ค่าใช้จ่ายในการเข้าถึงหน่วยความจำที่ประหยัดได้ในช่วงแรก มักจะต้องชดใช้ด้วยการคำนวณซ้ำสองเท่าในขั้นตอนต่อมา และข้อจำกัดด้านความจุของหน่วยความจำเร็วที่เข้มงวด อาจทำให้แผนการรวมที่ “ดูดีที่สุด” นำไปสู่การเกิด OOM (หน่วยความจำไม่เพียงพอ) ได้ทุกเมื่อ
โซลูชันของผู้เขียนนั้นทั้งเรียบง่ายและทรงพลัง — สร้างแบบจำลองปัญหาการจัดตารางเป็นการค้นหาสถานะอย่างชัดเจน ใช้การค้นหาแบบบีม (กลยุทธ์ฮิวริสติกที่สมดุลระหว่างการมองการณ์ไกลแบบละโมบกับค่าใช้จ่ายในการแจกแจง: ในแต่ละขั้นตอนจะเก็บเฉพาะเส้นทางที่มีคะแนนสูงสุด k เส้นทางเท่านั้น ไม่ติดกับดักเฉพาะที่ของ “ดีที่สุดในปัจจุบัน” และไม่失控จากการแจกแจงทุกความเป็นไปได้) เพื่อควบคุมขอบเขตการค้นหา ใช้ตัวจำลองระดับไทล์เพื่อรับประกันความถูกต้อง และใช้เทมเพลตผู้สมัครที่มีโครงสร้างเพื่อระงับการระเบิดของชุดค่าผสม
แบบจำลองการค้นหา แผนภาพนี้แสดงให้เห็นกรอบงานหลักที่ผู้เขียนเปลี่ยนการจัดตารางกราฟย่อยเป็นปัญหาการค้นหา โดยแบ่งออกเป็นสามโมดูลอย่างชัดเจน ได้แก่ สถานะเริ่มต้น กระบวนการค้นหา และสถานะเป้าหมาย สถานะเริ่มต้นถูกกำหนดให้ไม่มีการดำเนินการใดๆ และเทนเซอร์ถูกเก็บไว้ในหน่วยความจำช้า สถานะเป้าหมายคือการดำเนินการทั้งหมดเสร็จสมบูรณ์และเอาต์พุตกลับไปยังหน่วยความจำช้า การเปลี่ยนสถานะต้องเป็นไปตามข้อจำกัดด้านความจุของหน่วยความจำเร็ว แบบจำลองภาพนี้เป็นตรรกะพื้นฐานสำหรับการค้นหาแบบบีม การสร้างกราฟย่อยผู้สมัคร และการประเมินผล ช่วยให้เข้าใจวิธีการหลีกเลี่ยงหน่วยความจำล้นและลดความเสี่ยงในการติดอยู่ในจุดที่เหมาะสมที่สุดในท้องถิ่นผ่านการ遍历สถานะ เป็นการสนับสนุนภาพหลักของการออกแบบวิธีการ
ต่อไปนี้จะเริ่มต้นจากคำสั่ง make all บรรทัดเดียว ตามเส้นทางหลัก Solver → BeamSearchScheduler → CandidateGenerator → Evaluator → TileSimulator ผ่าโครงสร้างทางวิศวกรรมของมัน และเจาะลึกพลังที่แท้จริงของ “การค้นหาแบบบีม + ฮิวริสติก + การจำลองที่เข้มงวด” ทั้งสามประการ
สารบัญ
- หนึ่ง: การเริ่มต้นใช้งานอย่างรวดเร็ว
- สอง: แก่นแท้ของปัญหา: การจัดตารางกราฟคำนวณใน “ช่องว่าง” ของหน่วยความจำสองระดับ
- สาม: ภาพรวมสถาปัตยกรรมและปรัชญาการออกแบบ
- 3.1 ปัญหาถูกแบ่งออกเป็นสามชั้นนามธรรม
- 3.2 จุดเริ่มต้นระดับบน: Solver ที่ “อ่านกราฟแล้วเลือกวิธี”
- สี่: โครงสร้างการค้นหาแบบบีม: สถานะ ผู้สมัคร การตัดกิ่ง
- 4.1 สถานะการค้นหาที่ประกอบด้วยสตริงบิตสามชุด
- 4.2 วงหลัก: ขยาย — ประเมิน — ตัดซ้ำ — ตัดกิ่ง
- 4.3 ข้อจำกัดสำคัญที่ถูก “กอบกู้” ซ้ำแล้วซ้ำเล่า
- 4.4 แนวคิดการค้นหาโหนดแบบฮิวริสติกสไตล์ A*
- ห้า: การสร้างผู้สมัคร: ใช้การตัดสินเชิงโครงสร้างแทนการใช้กำลัง
- 5.1 ผู้สมัครสามประเภท ครอบคลุมรูปแบบการคำนวณทั่วไป
- 5.2 กรวยย้อนกลับ: อนุญาตให้คำนวณซ้ำได้เพียงครั้งเดียว
- 5.3 การจัดลำดับผู้สมัคร: ให้ความสำคัญกับขนาดใหญ่และไม่คำนวณซ้ำ
- หก: Evaluator และ TileSimulator: “คำนวณ” ผู้สมัครให้เป็นเวลาแฝง
- 6.1 การแจกจ่ายตามประเภท: ผู้สมัครต่างกัน อัลกอริทึมต่างกัน
- 6.2 การเลือกมิติ: ลำดับเรขาคณิตแบบพับครึ่ง
- 6.3 TileSimulator: “บัญชีที่เข้มงวด” ทีละไทล์
- 6.4 ลำดับการ遍历: แบบแรสเตอร์เทียบกับแบบงู
- เจ็ด: กลยุทธ์การคงอยู่: เกมระดับจุลภาคข้ามขอบเขตกราฟย่อย
- 7.1 กฎเหล็กหนึ่งข้อและคะแนนหนึ่งคะแนน
- 7.2 ใครเป็นผู้รับผิดชอบ? ให้ตัวจำลองเป็นผู้ตัดสิน
- แปด: หลักฐานเชิงประจักษ์: ผลงานบนเกณฑ์มาตรฐานสาธารณะ 5 รายการ
- บทสรุป: ทำไม “ฝ่ายวิศวกรรม” ถึงชนะ?
หนึ่ง: การเริ่มต้นใช้งานอย่างรวดเร็ว
ทั้งโครงการต้องการเพียง
g++ -std=c++20 -O2ในการสร้าง ไม่ต้องใช้ CMake, LLVM หรือ Python (สคริปต์ตรวจสอบเพิ่มเติมเท่านั้นที่ต้องใช้ Python) การพึ่งพามีเพียงไฟล์ส่วนหัวเดียวในตัวnlohmann/json[3]
# 1. โคลนโครงการ
git clone https://github.com/wenqi-deng/mlsys-2026-graph-scheduler
cd mlsys-2026-graph-scheduler
# 2. สร้าง (คำสั่งย่อที่ให้ไว้ใน README)
mkdir build && make all
# 3. รันตัวอย่างเดียว
./build/mlsys benchmarks/example_problem.json solution.json
# 4. รัน benchmark ทั้งหมดและตรวจสอบ (ต้องใช้ python3 และสคริปต์ verify อย่างเป็นทางการ)
make verify
สคีมาของ JSON อินพุตได้รับการออกแบบให้เรียบง่ายมาก — `widths/heights` กำหนดรูปร่างของเทนเซอร์ `op_types/inputs/outputs/base_costs` ใช้อธิบายโอเปอเรเตอร์ บวกกับพารามิเตอร์ฮาร์ดแวร์สามตัว: `fast_memory_capacity`, `slow_memory_bandwidth` และ `native_granularity` คำจำกัดความโครงสร้างที่สมบูรณ์สามารถดูได้ที่ `benchmarks/example_problem.json`[4] benchmark ขนาดใหญ่กว่า 24 รายการที่ให้มาอย่างเป็นทางการทั้งหมดอยู่ในไดเรกทอรี `benchmarks/`[5] และรายงานทางเทคนิคโดยละเอียดพร้อมงานนำเสนออยู่ใน `report/`[6]
// ที่มา: benchmarks/example_problem.json
{
“widths”: [128, 128, 128],
“heights”: [128, 128, 128],
“op_types”: [“Pointwise”, “Pointwise”],
“inputs”: [[0], [1]],
“outputs”: [[1], [2]],
“base_costs”: [100, 10],
“fast_memory_capacity”: 20000,
“slow_memory_bandwidth”: 10,
“native_granularity”: [128, 128]
}
## สอง: แก่นแท้ของปัญหา: การจัดตารางกราฟคำนวณใน "ช่องว่าง" ของหน่วยความจำสองระดับ
> เพื่อทำความเข้าใจว่าเหตุใดตัวแก้ปัญหานี้จึง "ถูกออกแบบมาเช่นนี้" เราต้องมองเห็นพื้นหลังทางกายภาพของปัญหาก่อน
แผนภาพสถาปัตยกรรมปฏิสัมพันธ์ระหว่างหน่วยความจำช้า หน่วยความจำเร็ว และเอ็นจิ้นกราฟย่อย สถาปัตยกรรมนี้แสดงให้เห็นข้อจำกัดหลักของหน่วยความจำแบบต่างชนิดใน GPU อย่างชัดเจน: หน่วยความจำช้ามีความจุมากแต่แบนด์วิธต่ำ ใช้สำหรับเก็บข้อมูลถาวร หน่วยความจำเร็วมีแบนด์วิธสูงแต่ความจุจำกัด รองรับการคำนวณแบบเรียลไทม์ การถ่ายโอนข้อมูลระหว่างหน่วยความจำสองชั้นนี้ทำให้เกิดเวลาแฝงอย่างมีนัยสำคัญ กลไกเทนเซอร์ประจำที่สามารถลดค่าใช้จ่ายในการโหลดซ้ำได้ สถาปัตยกรรมนี้กำหนดขอบเขตฮาร์ดแวร์สำหรับการปรับแต่งการจัดตารางให้เหมาะสม เน้นย้ำถึงความขัดแย้งหลักของ "การลดเวลาแฝงให้เหลือน้อยที่สุดภายใต้ข้อจำกัดด้านหน่วยความจำ" และเป็นพื้นฐานและทิศทางการปรับให้เหมาะสมสำหรับการจัดตารางการค้นหาแบบบีมในภายหลัง
ในสถานการณ์การวิจัย มีสื่อจัดเก็บข้อมูลสองประเภทที่มีลักษณะขัดแย้งกัน:
- **หน่วยความจำช้า (Slow memory)** มีความจุเพียงพอแต่แบนด์วิธจำกัด ประสิทธิภาพการอ่าน/เขียนข้อมูลค่อนข้างต่ำ
- **หน่วยความจำเร็ว (Fast memory)** มีความเร็วในการอ่าน/เขียนสูงมากแต่ความจุจำกัดอย่างยิ่ง เป็นตัวกลางหลักในการดำเนินการคำนวณ
ในระหว่างการดำเนินการกราฟย่อย การรวมโอเปอเรเตอร์ยังก่อให้เกิดเทนเซอร์ภายในชั่วคราว (ephemeral internal tensors) เพิ่มเติม ซึ่งยิ่งบีบพื้นที่หน่วยความจำเร็ว แต่ละกราฟย่อยต้องกำหนดพารามิเตอร์粒度 `[w, h, k]` — `w/h` ในทิศทางเชิงพื้นที่กำหนดขนาดไทล์เอาต์พุต `k` ในทิศทางการลดรูปกำหนดการแบ่งชั้นในของ MatMul ซึ่งส่งผลโดยตรงต่อการจัดสรรหน่วยความจำและประสิทธิภาพการจัดตาราง ข้อมูลต้องโต้ตอบระหว่างหน่วยความจำช้า/เร็วผ่านการโหลด/จัดเก็บ ในขณะที่ "เทนเซอร์ประจำที่" (resident tensors) สามารถข้ามขอบเขตกราฟย่อยและถูกเรียกใช้โดยเอ็นจิ้นถัดไปในหน่วยความจำเร็วได้โดยตรง
> เป้าหมายหลักของการแก้ปัญหามีเพียงประโยคเดียว: **ลดเวลาแฝงรวมของการดำเนินการกราฟคำนวณให้เหลือน้อยที่สุด โดยรับประกันว่าแต่ละขั้นตอนการดำเนินการเหมาะสมกับข้อจำกัดด้านความจุของหน่วยความจำเร็ว**
แนวคิดในการแก้ปัญหาของผู้เขียนคือการเปลี่ยนการจัดตารางกราฟย่อยเป็น**ปัญหาการค้นหาสถานะอย่างชัดเจน** สถานะการค้นหาถูกออกแบบเป็นสามสิ่งอันดับ `(covered ops, stored tensors, resident tensors)`:
- ในตอนเริ่มต้น ไม่มีโอเปอเรเตอร์ใดถูกครอบคลุม อินพุตกราฟทั้งหมดอยู่ในหน่วยความจำช้า หน่วยความจำเร็วว่างเปล่า
- สถานะเป้าหมายต้องการให้โอเปอเรเตอร์ทั้งหมดถูกครอบคลุม และเอาต์พุตกราฟทั้งหมดอยู่ในหน่วยความจำช้า
แผนภาพการเปลี่ยนสถานะของแบบจำลองการค้นหากราฟคำนวณ DAG แผนภาพนี้แสดงสถานะเริ่มต้น ตรรกะการเปลี่ยนสถานะ และสถานะเป้าหมายของแบบจำลองการค้นหา สถานะการค้นหาถูกกำหนดโดยสามสิ่งอันดับ: โอเปอเรเตอร์ที่ครอบคลุม เทนเซอร์ที่จัดเก็บ เทนเซอร์ประจำที่ แผนภาพนี้เปลี่ยนการจัดตารางกราฟย่อยเป็นปัญหาการค้นหาที่สามารถวนซ้ำได้ สถานะเริ่มต้นคืออินพุตทั้งหมดอยู่ในหน่วยความจำช้า ไม่มีโอเปอเรเตอร์ใดถูกครอบคลุม แต่ละการเปลี่ยนสถานะจะเลือกกราฟย่อยที่เป็นไปได้เพื่ออัปเดตสถานะ สถานะเป้าหมายคือครอบคลุมโอเปอเรเตอร์ทั้งหมดและการจัดเก็บเอาต์พุตเสร็จสมบูรณ์ สามสิ่งอันดับนี้วัดปริมาณสถานะการคำนวณและหน่วยความจำได้อย่างแม่นยำ หลีกเลี่ยงความคลุมเครือของข้อมูลการจัดตาราง แบบจำลองนี้แยกย่อยการตัดสินใจจัดตารางที่ซับซ้อนเป็นการค้นหาสถานะ เป็นกรอบทางทฤษฎีสำหรับการค้นหาแบบบีม รับประกันว่ากระบวนการจัดตารางสามารถติดตามและปรับให้เหมาะสมได้ และปรับให้เข้ากับลักษณะการพึ่งพาของกราฟคำนวณ DAG
การเปลี่ยนสถานะคือ "การเลือกแผนการดำเนินการกราฟย่อยที่เป็นไปได้" ซึ่งต้องเป็นไปตามข้อจำกัดแข็งสองข้อพร้อมกัน:
1. อินพุตที่จำเป็นทั้งหมดต้องอยู่ในหน่วยความจำเร็วแล้ว หรือสามารถโหลดจากหน่วยความจำช้าได้
2. กระบวนการดำเนินการทั้งหมดต้องปฏิบัติตามขีดจำกัดความจุของหน่วยความจำเร็วอย่างเคร่งครัด
## สาม: ภาพรวมสถาปัตยกรรมและปรัชญาการออกแบบ
> ซอร์สโค้ดของตัวแก้ปัญหาทั้งหมดกระจายอยู่ในไฟล์น้อยกว่า 20 ไฟล์ภายใต้ `source/`[7] โดยมีลำดับชั้นที่สะอาดมาก:
main.cpp ──► จุดเริ่มต้นบรรทัดคำสั่ง
problem_io.* ──► อ่าน/เขียน JSON
solver.* ──► Solver ระดับบนสุด ปรับไฮเปอร์พารามิเตอร์แบบปรับตัว
state_search.* ──► วงหลักการค้นหาแบบบีม (BeamSearchScheduler)
candidate_generator.* ─► สร้างผู้สมัครเชิงโครงสร้าง (โอเปอเรเตอร์เดี่ยว/ลูกโซ่/กรวย)
cost_model.* ──► Evaluator: ผู้สมัคร → กราฟย่อย + เวลาแฝง
retention_policy.* ──► กลยุทธ์การคงเทนเซอร์ข้ามขอบเขตกราฟย่อย
tile_simulator.* ──► ตัวจำลองระดับไทล์ที่ “คำนวณเวลาแฝง+ตรวจสอบหน่วยความจำ” จริงๆ
graph_utils.* ──► โทโพโลยี DAG, ก่อนหน้า/ถัดไป, เครื่องมือเรขาคณิต
mlsys.h ──► โครงสร้างข้อมูลหลักเช่น Problem/Solution
### 3.1 ปัญหาถูกแบ่งออกเป็นสามชั้นนามธรรม
> ผู้เขียนแบ่งปัญหาการปรับให้เหมาะสมแบบผสมนี้เป็นสามชั้นนามธรรมอย่างสะอาดตา แต่ละชั้นเปิดเผยข้อมูลน้อยที่สุดเท่าที่จำเป็นต่อชั้นบน:
1. **ชั้นโครงสร้าง (`CandidateGenerator`)**: ดูเฉพาะโทโพโลยี DAG เสนอชื่อ "โอเปอเรเตอร์ใดบ้างที่สามารถใส่ในกราฟย่อยเดียวกัน" — โอเปอเรเตอร์เดี่ยว, ลูกโซ่เชิงเส้น, กรวยย้อนกลับ, กรวยย้อนกลับพร้อมการคำนวณซ้ำ
2. **ชั้นเรขาคณิต (`Evaluator`)**: เมื่อกำหนดผู้สมัครแล้ว ให้แจกแจง粒度ไทล์ `(w, h, k)`, ชุดที่คงไว้ และลำดับการ遍历
3. **ชั้นกายภาพ (`TileSimulator`)**: จำลองการเข้าถึงหน่วยความจำและการคำนวณจริง **ทีละไทล์** ตาม粒度เฉพาะ สร้าง `latency` และ `peak_fast_memory` ที่เข้มงวด
การแบ่งชั้นนี้ทำให้แต่ละองค์ประกอบสามารถนำไปใช้ได้อย่างอิสระและจริงจัง — โดยเฉพาะตัวจำลองไทล์ระดับล่างสุด ความถูกต้องของมันจะกำหนดโดยตรงว่าโซลูชันทั้งหมดจะถูกตัดสินว่าผิดโดยสคริปต์ตรวจสอบอย่างเป็นทางการหรือไม่
### 3.2 จุดเริ่มต้นระดับบน: Solver ที่ "อ่านกราฟแล้วเลือกวิธี"
### เวอร์ชันเขียนใหม่เชิงลึกและลดความซ้ำซ้อน
ฟังก์ชัน `Solver::solve` แม้จะมีเพียง 20 บรรทัด แต่ตรรกะหลักของมันนั้นใช้งานได้จริงอย่างยิ่ง — **ปรับงบประมาณการค้นหาแบบไดนามิกตามขนาดของกราฟคำนวณ** กลยุทธ์นี้เป็นกุญแจสำคัญที่ทำให้โซลูชันที่ชนะเลิศนี้สามารถหลีกเลี่ยงการหมดเวลาได้อย่างมีประสิทธิภาพเมื่อต้องจัดการกับกราฟขนาดใหญ่
```cpp
// ที่มา: source/solver.cpp
mlsys::Solution Solver::solve(const mlsys::Problem &problem) const {
SearchConfig cfg = config_;
// การปรับสำหรับกราฟขนาดใหญ่: "ควบคุม" กระบวนการค้นหาโดยการจำกัดขอบเขตการค้นหาให้แคบลง ใช้บีมที่กว้างขึ้น
if (problem.ops.size() > 80) {
cfg.beam_width = 5;
cfg.max_candidate_ops = 5;
cfg.max_recompute_depth = 1;
cfg.max_retained_outputs = 1;
} else if (problem.ops.size() > 50) {
cfg.beam_width = 4;
cfg.max_candidate_ops = 5;
}
GraphInfo graph(problem);
BeamSearchScheduler scheduler(graph, cfg);
return scheduler.build_solution();
}
ประโยค “keeping the search bounded >> using a wider beam” ในความคิดเห็นของโค้ดชี้ให้เห็นถึงปรัชญาการออกแบบหลักโดยตรง: แทนที่จะขยายขอบเขตการค้นหา ควรจำกัดให้แคบลงอย่างจริงจัง เมื่อจำนวนโอเปอเรเตอร์เกิน 80 ความกว้างของบีมจะลดลงจาก 8 เหลือ 5 ทันที พร้อมกับพารามิเตอร์อื่นๆ เช่น ขนาดกรวยผู้สมัคร ความลึกในการคำนวณซ้ำ และจำนวนเทนเซอร์ที่คงไว้ ก็ถูกลดระดับลงเช่นกัน นี่คือการตัดสินใจสำคัญที่ทำให้ฝ่ายปฏิบัติทางวิศวกรรมเอาชนะฝ่ายค้นหาแบบสุ่มสี่สุ่มห้าได้
สี่: โครงสร้างการค้นหาแบบบีม: สถานะ ผู้สมัคร การตัดกิ่ง
ทำไมต้องใช้การค้นหาแบบบีม (Beam Search) แทนกลยุทธ์แบบละโมบล้วนๆ? เพราะการละโมบทีละขั้นตอนแทบจะหลุดจากกับดักจุดที่เหมาะสมที่สุดในท้องถิ่นไม่ได้อย่างแน่นอน — ขั้นตอนหนึ่งประหยัดค่าใช้จ่ายในการเข้าถึงหน่วยความจำ แต่ขั้นตอนถัดไปถูกบังคับให้จ่ายค่าใช้จ่ายในการคำนวณสองเท่า การค้นหาแบบบีมโดยการรักษาแผนการจัดตารางบางส่วนคุณภาพสูงหลายแผนพร้อมกัน ทำให้ตัวเลือกที่ดู “ด้อยกว่า” ในช่วงแรก มีโอกาส “พลิกกลับมา” ได้ในภายหลังผ่านผลตอบแทนโดยรวม
แผนภาพด้านล่างแสดงกระบวนการปรับแต่งการจัดตารางโอเปอเรเตอร์โดยใช้การค้นหาแบบบีมอย่างสมบูรณ์ ซึ่งประกอบด้วยห้าขั้นตอน: ขยายสถานะบีม, ประเมินผู้สมัครด้วยตัวจำลอง, เพิ่มกราฟย่อยเพื่อสร้างสถานะใหม่, ตัดสถานะที่เทียบเท่ากันซ้ำ, และคงสถานะที่ดีที่สุดตามเวลาแฝงรวมโดยประมาณ ฟังก์ชันลำดับความสำคัญด้านล่างใช้เวลาแฝงของสถานะปัจจุบันเป็นหลัก เสริมด้วยผลรวมถ่วงน้ำหนักของต้นทุนพื้นฐานของโอเปอเรเตอร์ที่ยังไม่ครอบคลุม เพื่อสร้างสมดุลระหว่างประสิทธิภาพเฉพาะที่และค่าใช้จ่ายส่วนที่เหลือโดยรวม ชี้นำการค้นหาให้เลือกเส้นทางที่มีเวลาแฝงต่ำและงานเหลือน้อย นี่คือกรอบงานการปรับให้เหมาะสมการค้นหาแบบบีมที่มีข้อมูลฮิวริสติกทั่วไป
วงจรทั้งหมดดำเนินการเพียงสี่การดำเนินการหลักในแต่ละขั้นตอน: ขยายผู้สมัคร → ประเมินด้วยการจำลอง → ตัดสถานะที่เทียบเท่ากันซ้ำ → จัดลำดับและตัดกิ่งตามค่าประมาณ
4.1 สถานะการค้นหาที่ประกอบด้วยสตริงบิตสามชุด
สถานะ (State) ถูกบีบอัดอย่างจงใจให้เป็น
vector<bool>สามชุด ทำให้คำถาม “เคยเข้าถึงสถานะเดียวกันนี้หรือไม่” สามารถลดรูปเป็นการเปรียบเทียบสตริงที่แฮชได้:
// ที่มา: source/search_types.h
struct ScheduleState {
std::vector<bool> covered_ops; // โอเปอเรเตอร์ที่ถูกครอบคลุมแล้ว
std::vector<bool> stored_tensors; // เทนเซอร์ที่ตกไปอยู่ในหน่วยความจำช้าแล้ว
std::vector<bool> resident_tensors; // เทนเซอร์ที่อยู่ในหน่วยความจำเร็ว "ข้ามขอบเขตกราฟย่อยเพียงครั้งเดียว"
int covered_count = 0;
double total_latency = 0.0;
std::vector<mlsys::Subgraph> schedule; // ลำดับกราฟย่อยที่ยอมรับแล้ว
};
สิ่งที่ควรค่าแก่การคิดอย่างลึกซึ้งที่สุดคือความหมายของ resident_tensors — มันจำกัดอย่างเคร่งครัดว่าเทนเซอร์สามารถข้ามขอบเขตกราฟย่อยได้เพียงครั้งเดียว ข้อจำกัดที่ดูเหมือนเข้มงวดนี้ ตัดพื้นที่สถานะของ “การคงอยู่ในหน่วยความจำเร็ว” ซึ่งในทางทฤษฎีอาจระเบิดได้ กลับมาสู่มิติที่จำกัด ในขณะเดียวกัน มันสอดคล้องอย่างสมบูรณ์กับกฎในรูปแบบเอาต์พุตอย่างเป็นทางการที่ “tensors_to_retain ใช้กับเอาต์พุตของกราฟย่อยปัจจุบันเท่านั้น” ทำให้มั่นใจในความสอดคล้องของการออกแบบ
4.2 วงหลัก: ขยาย — ประเมิน — ตัดซ้ำ — ตัดกิ่ง
4.3 ข้อจำกัดสำคัญที่ถูก “กอบกู้” ซ้ำแล้วซ้ำเล่า
การใช้งานวงหลักแสดงไว้ด้านล่าง โดยความคิดเห็นที่เพิ่มใหม่ในโค้ดอธิบายกระบวนการแต่ละขั้นตอนอย่างชัดเจน:
// ที่มา: source/state_search.cpp
for (int step = 0; step < config_.max_search_steps; step++) {
// (1) การตัดสินสิ้นสุด: หากในบีมมีสถานะที่ "ครอบคลุมกราฟทั้งหมด + เอาต์พุตกราฟทั้งหมดอยู่บนพื้น" ที่สมบูรณ์ ให้ส่งคืนทันที
for (const auto &state : beam) {
if (state.covered_count == (int)graph_.problem().ops.size()
&& is_all_outputs_stored(state)) {
if (!best_complete.has_value() ||
state.total_latency < best_complete->total_latency) {
best_complete = state;
}
}
}
if (best_complete.has_value()) return mlsys::Solution{best_complete->schedule};
// (2) ขยาย: แต่ละสถานะสร้างผู้สมัครเชิงโครงสร้าง → จัดลำดับ → ตัดทอน
std::vector<ScheduleState> expanded_beam;
for (const auto &state : beam) {
auto candidates = generator_.generate(state);
std::sort(candidates.begin(), candidates.end(),
[&](const Candidate &a, const Candidate &b) {
if (a.ops.size() != b.ops.size()) // ผู้สมัครขนาดใหญ่優先 (รวมโอเปอเรเตอร์มากขึ้น)
return a.ops.size() > b.ops.size();
if (a.uses_recompute != b.uses_recompute) // ไม่คำนวณซ้ำ優先
return !a.uses_recompute;
return a.tip_op < b.tip_op; // ความเสถียร
});
if (candidates.size() > config_.max_candidate_num)
candidates.resize(config_.max_candidate_num);
// (3) ประเมิน: ส่งผู้สมัครแต่ละรายไปยัง Evaluator เพื่อรับกราฟย่อยเฉพาะพร้อม latency
for (const auto &candidate : candidates) {
if (!consumes_required_residents(graph_, state, candidate)) continue;
Evaluator evaluator(graph_, config_, state, candidate);
auto eval = evaluator.evaluate_candidate();
if (!eval.has_value()) continue;
/* ...อัปเดต covered_ops / stored_tensors / resident_tensors... */
expanded_beam.push_back(std::move(next_state));
}
}
// (4) ตัดสถานะที่เทียบเท่ากันซ้ำ + จัดลำดับแบบฮิวริสติก + ตัดทอนเป็น beam_width
/* ... best_beam_map เก็บ state_key ที่มี latency น้อยที่สุด ... */
/* ... จัดเรียงตาม estimated_total_latency จากน้อยไปมาก, resize เป็น beam_width ... */
}
ต่อไป ฟังก์ชันการตัดสิน consumes_required_residents ที่ดูเหมือนไม่เด่นนี้ จริงๆ แล้วยึดมั่นในสัญญาหลักที่ว่า “การคงไว้หมายถึงสัญญาที่จะบริโภคทันที”: เทนเซอร์ใดๆ ที่ยังคงอยู่ในหน่วยความจำเร็ว แต่ยังไม่ได้ถูกจัดเก็บลงในหน่วยความจำช้า ผู้บริโภคที่ยังไม่เสร็จทั้งหมดจะต้องตกอยู่ในชุดผู้สมัครนี้ทั้งหมด มิฉะนั้น ข้อมูลที่เก็บรักษาไว้อย่างยากลำบากในรอบก่อนหน้าจะ “หายไปอย่างไร้ร่องรอย” ที่ขอบเขต ทำให้แผนไม่ถูกต้อง
// ที่มา: source/state_search.cpp
static bool consumes_required_residents(const GraphInfo &graph,
const ScheduleState &state,
const Candidate &candidate) {
std::unordered_set<size_t> candidate_ops(candidate.ops.begin(),
candidate.ops.end());
for (size_t t = 0; t < state.resident_tensors.size(); ++t) {
if (!state.resident_tensors.at(t) || state.stored_tensors.at(t)) continue;
for (size_t consumer : graph.consumers_of_tensor().at(t)) {
if (state.covered_ops.at(consumer)) continue;
if (!candidate_ops.count(consumer)) return false; // ผู้บริโภคไม่อยู่ ปฏิเสธ
}
}
return true;
}
4.4 แนวคิดการค้นหาโหนดแบบฮิวริสติกสไตล์ A*
ในการขยายแต่ละรอบของการค้นหาแบบบีม ระบบจะสร้างผู้สมัครเชิงโครงสร้างหลายรายสำหรับแต่ละสถานะในบีมปัจจุบัน ผู้สมัครเหล่านี้จะถูกจัดลำดับตามชุดกฎลำดับความสำคัญ: ผู้สมัครที่รวมโอเปอเรเตอร์ได้มากกว่าจะอยู่ข้างหน้า ผู้สมัครที่หลีกเลี่ยงการคำนวณซ้ำจะอยู่ถัดไป และสุดท้ายคือการรักษาความเสถียรผ่าน ID โอเปอเรเตอร์ หลังจากจัดลำดับแล้ว จะคงไว้เฉพาะผู้สมัคร max_candidate_num ตัวแรกเท่านั้น เพื่อควบคุมขนาดของกิ่งการค้นหา
ถัดไป ผู้สมัครแต่ละรายจะถูกส่งไปยังตัวประเมิน (Evaluator) เพื่อประเมินเวลาแฝงอย่างแม่นยำ ตัวประเมินจะจำลองกระบวนการดำเนินการของผู้สมัครบนฮาร์ดแวร์เป้าหมาย และส่งคืนกราฟย่อยที่มีค่าเวลาแฝงเฉพาะ หากการประเมินล้มเหลว (เช่น ทรัพยากรไม่เพียงพอ) ผู้สมัครนั้นจะถูกข้ามไป ด้วยวิธีนี้ ระบบจะรับประกันว่าการขยายแต่ละขั้นตอนอยู่บนพื้นฐานของความสามารถในการดำเนินการจริง ไม่ใช่การเดาแบบฮิวริสติกล้วนๆ
สุดท้าย สถานะที่ประเมินสำเร็จทั้งหมดจะเข้าสู่ขั้นตอนการตัดซ้ำและจัดลำดับ ระบบจะใช้ state_key แฮชสถานะ และคงไว้เฉพาะอินสแตนซ์ที่มีเวลาแฝงน้อยที่สุดสำหรับแต่ละสถานะที่ไม่ซ้ำกัน จากนั้นจะจัดเรียงตาม estimated_total_latency จากน้อยไปมาก และตัดทอนเป็นขนาด beam_width เพื่อให้แน่ใจว่าการค้นหามุ่งเน้นไปที่สถานะที่มีแนวโน้มดีที่สุดเสมอ
กรอบงานการค้นหานี้ไม่ได้ใช้กลยุทธ์แบบละโมบล้วนๆ แต่引入了ฟังก์ชันการประเมินค่าที่มีน้ำหนักเบาแต่มีประสิทธิภาพ มันใช้ “10% ของต้นทุนพื้นฐานของโอเปอเรเตอร์ที่ยังไม่ครอบคลุม” เป็นค่าประมาณขอบเขตล่างของค่าใช้จ่ายในอนาคต และบวกกับเวลาแฝงที่เกิดขึ้นแล้ว เพื่อใช้ร่วมกันในการตัดกิ่งบีม ซึ่งสอดคล้องกับสูตรลำดับความสำคัญที่กล่าวถึงในตอนต้นของส่วนนี้:
// ที่มา: source/state_search.cpp
double BeamSearchScheduler::estimated_total_latency(
const ScheduleState &state) const {
double remaining = 0.0;
for (size_t op_id = 0; op_id < graph_.problem().ops.size(); ++op_id) {
if (!state.covered_ops.at(op_id)) {
remaining += 0.10 * static_cast<double>(
graph_.problem().ops[op_id].base_cost);
}
}
return state.total_latency + remaining;
}
ค่าสัมประสิทธิ์ 0.10 ไม่ได้ถูกตั้งขึ้นโดยบังเอิญ — ความตั้งใจเดิมของผู้เขียนคือ ให้ค่าประมาณ “มองโลกในแง่ดี แต่ไม่หลุดจากความเป็นจริง”: มองโลกในแง่ดีเพื่อหลีกเลี่ยงการตัดเส้นทางที่มีศักยภาพจริงๆ ออกไปอย่างผิดพลาด; ไม่หลุดจากความเป็นจริงเพื่อให้สามารถสร้างความแตกต่างระหว่างสถานะต่างๆ ได้อย่างมีประสิทธิภาพ นี่คือทั้งศิลปะคลาสสิกในการปรับพารามิเตอร์การค้นหาแบบบีม และการประยุกต์ใช้แนวคิดการยอมรับได้ (admissibility) ของฮิวริสติกในอัลกอริทึม A* ในทางวิศวกรรม
ห้า: การสร้างผู้สมัคร: ใช้การตัดสินเชิงโครงสร้างแทนการใช้กำลัง
หากการค้นหาแบบบีมคือโครงกระดูกของวิธีการทั้งหมด CandidateGenerator ก็คือเนื้อและเลือด ผู้เขียนปฏิบัติตามกฎทองทางวิศวกรรมที่นี่: “สร้าง
⚠️ หมายเหตุ: เนื้อหาได้รับการแปลโดย AI และตรวจสอบโดยมนุษย์ หากมีข้อผิดพลาดโปรดแจ้ง
☕ สนับสนุนค่ากาแฟทีมงาน
หากคุณชอบบทความนี้ สามารถสนับสนุนเราได้ผ่าน PromptPay
本文来自网络搜集，不代表คลื่นสร้างอนาคต立场，如有侵权，联系删除。转载请注明出处：https://www.itsolotime.com/th/archives/36132