สิ่งที่อยากรู้ก่อนเริ่มพัฒนา Autorouter

 (blog.autorouting.com)
1 คะแนน โดย GN⁺ 2025-03-29 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

"บทเรียนสำคัญเพื่อสร้างเครื่องมือเดินลายวงจรอัตโนมัติ (Autorouter) ที่เร็วที่สุดในโลก"

ใช้ A* algorithm ให้ทั่วถึง

  • A* เป็นอัลกอริทึมที่ทรงพลังและยืดหยุ่นมากที่สุดสำหรับปัญหาการค้นหา
  • ใช้ได้กับปัญหาหลากหลาย ไม่ใช่แค่ 2D grid แบบง่าย ๆ
  • A* เร็วและมีประสิทธิภาพกว่า BFS เพราะเป็นการค้นหาแบบมีข้อมูลกำกับ ที่จะสำรวจโหนดที่ใกล้เป้าหมายก่อน
  • DFS หรือ BFS ที่ใช้อยู่ในโค้ดเดิมส่วนใหญ่สามารถแทนที่ด้วย A* ได้
  • เพื่อปรับปรุงประสิทธิภาพ สามารถรัน A* หลายอินสแตนซ์แล้วจัดสรรทรัพยากรเพิ่มให้กับค่าตั้งที่ทำผลงานได้ดีกว่า

อัลกอริทึมสำคัญกว่าภาษาโปรแกรม

  • ต่อให้พัฒนา autorouter ด้วย Javascript ก็ไม่ได้มีปัญหาอะไรเลย
  • หัวใจของการ optimization คือการลดจำนวนรอบการทำซ้ำ
  • สำคัญกว่าประสิทธิภาพของภาษา คือ “จะสร้างอัลกอริทึมที่ฉลาดได้เร็วแค่ไหน”
  • Javascript เหมาะกับการสร้างอัลกอริทึมที่ฉลาดมากกว่าการพึ่งการวนซ้ำจำนวนมาก

Spatial Hash Indexing มีประสิทธิภาพกว่าการใช้โครงสร้างต้นไม้

  • โครงสร้างข้อมูลแบบ tree เช่น Quadtree โดยทั่วไปมักช้า
  • Spatial Hash Index จะ hash ตำแหน่งของวัตถุแล้วจัดกลุ่มวัตถุที่อยู่ใกล้กันในเชิงพื้นที่เพื่อประมวลผลร่วมกัน
  • โครงสร้างแบบ hash ให้ประสิทธิภาพการค้นหาที่ใกล้เคียง O(1)
  • ต้องเลือกขนาด cell ให้เหมาะสมจึงจะได้ผลดี และการเลือกขนาดที่เหมาะสมก็ไม่ได้ยากนัก

การแบ่งพื้นที่และ cache สำคัญกว่าอัลกอริทึม 1000 เท่า

  • แม้แผงวงจรจะซับซ้อน แต่ส่วนใหญ่ก็มีแพตเทิร์นที่เกิดซ้ำ
  • เหมือนกับการพัฒนาเกม การ cache ผลลัพธ์ที่คำนวณไว้ล่วงหน้าช่วยเพิ่มประสิทธิภาพได้อย่างมหาศาล
  • โครงสร้างที่ cache ได้และการแบ่งพื้นที่จะเป็นหัวใจสำคัญของ autorouter ในอนาคต
  • พื้นที่จัดเก็บข้อมูลมีราคาถูกลงอย่างรวดเร็ว และแม้ใช้ cache ระดับหลาย GB ก็ยังช่วยเพิ่มประสิทธิภาพได้มาก

ถ้าไม่มีการทำภาพให้เห็น ก็แก้ปัญหาไม่ได้

  • สำหรับทุกปัญหา เริ่มต้นด้วยการสร้างเครื่องมือ visualization ก่อนเสมอ
  • การทำภาพให้เห็นช่วยให้ debugging เร็วขึ้นมากกว่า 10 เท่า
  • แม้จะเป็นเพียงขั้นตอนอัลกอริทึมง่าย ๆ หากทำเป็นภาพก็จะหาสาเหตุของปัญหาได้เร็ว

เครื่องมือ profiling ของ Javascript มีประโยชน์มาก

  • ในแท็บ Performance ของ Chrome Developer Tools สามารถดูเวลาที่ใช้ของแต่ละส่วนของโค้ดได้
  • วิเคราะห์ Flame Chart, การใช้หน่วยความจำ และอื่น ๆ ได้ง่ายโดยไม่ต้องมีเฟรมเวิร์กเพิ่มเติม
  • เป็นเครื่องมือที่มีประโยชน์มากสำหรับการ debugging ด้านประสิทธิภาพ

อย่าใช้ฟังก์ชัน recursive

  • ฟังก์ชัน recursive โดยทั่วไปเป็นแบบ synchronous และเปลี่ยนไปใช้ A* ได้ยาก
  • การเขียนแบบวนซ้ำเร็วกว่า และติดตามโหนดที่เคยเยี่ยมชมได้ง่ายกว่า
  • ในฟังก์ชัน recursive การเปลี่ยนสถานะทำได้ยากและไม่มีประสิทธิภาพ
  • ถ้าเป็นไปได้ ควรเขียนด้วยลูปเป็นหลัก

ควรหลีกเลี่ยงอัลกอริทึมแบบ Monte Carlo

  • อัลกอริทึมที่อาศัยความสุ่มเป็นแบบไม่กำหนดแน่นอนและ debug ได้ยาก
  • heuristic ที่ออกแบบเฉพาะกับโดเมนให้ประสิทธิภาพที่ดีกว่าเสมอ
  • ไม่มีนักออกแบบ PCB คนไหนลากเส้นแบบสุ่ม → จึงไม่ใช่แนวทางที่สมจริง
  • อย่างไรก็ตาม ในช่วงต้นอาจมีประโยชน์สำหรับใช้จับทิศทางเบื้องต้น

ยึดแต่ละขั้นของอัลกอริทึมไว้กับพื้นที่ปัญหาจริง

  • หาก normalize sub-algorithm โดยอิงจากจุดกำเนิด จะทำให้มองภาพรวมของการไหลทั้งหมดได้ยาก
  • การทำภาพอินพุตและเอาต์พุตของแต่ละขั้นช่วยให้เห็นว่าขั้นตอนไหนเป็นตัวก่อข้อผิดพลาด
  • การรักษาระบบพิกัดให้สอดคล้องกันตลอดพร้อมคงลำดับการไหลของอัลกอริทึมไว้เป็นสิ่งสำคัญ

ทำภาพกระบวนการวนซ้ำเป็น animation

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

ไม่ต้องใช้ grid ก็พอด้วยคณิตศาสตร์สำหรับตรวจจับการตัดกัน

  • แทนที่จะใช้ grid หากใช้ vector math จะเร็วกว่ามาก
  • ในหลายกรณี การคำนวณทางคณิตศาสตร์เร็วกว่าการเข้าถึงหน่วยความจำ
  • ด้วย LLM การเขียนคณิตศาสตร์สำหรับตรวจจับการตัดกันก็ง่ายขึ้นมาก
  • การใช้ grid โดยไม่จำเป็นเป็นสาเหตุหนึ่งของประสิทธิภาพที่ลดลง

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

  • สามารถประเมินความน่าจะเป็นของความล้มเหลวได้ในแต่ละโหนดของการแบ่งพื้นที่
  • จากนั้นจึงปรับโครงสร้างหรือค้นหาใหม่ก่อนในโหนดที่มีแนวโน้มจะล้มเหลวสูงในขั้นถัดไป
  • ความน่าจะเป็นของความล้มเหลวสามารถวัดได้ชัดเจน และมีโอกาสปรับปรุงได้มากกว่า heuristic
  • การเพิ่มโอกาสในการแก้ปัญหาได้สำเร็จโดยรวม อาจมีประสิทธิภาพกว่าการมุ่ง optimize อย่างเดียว

Weighted A* ช่วยเพิ่มความเร็วได้ 100 เท่า

  • A* แบบพื้นฐานรับประกันเส้นทางที่เหมาะที่สุด แต่มีความเร็วช้า
  • Weighted A* ค้นหาแบบละโมบมากขึ้น จึงเพิ่มความเร็วได้อย่างมาก
  • สามารถทำได้เพียงกำหนดค่าน้ำหนักใน f(n) = g(n) + w * h(n)
  • แม้จะเสียความเป็น optimal ไปเล็กน้อย แต่ก็แก้ปัญหาได้เร็วขึ้นมาก
  • เป็นเทคนิคที่ใช้บ่อยในสายพัฒนาเกมและควรค่าแก่การอ้างอิง

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-03-29
ความคิดเห็นบน Hacker News

  • การมองข้ามวิธี Monte-Carlo อย่างรวดเร็วถือเป็นความผิดพลาดครั้งใหญ่

    • จุดเด่นของวิธี Monte-Carlo คือสามารถแลกเปลี่ยนระหว่างความแม่นยำกับความเร็วได้
    • ยิ่งปล่อยให้อัลกอริทึมทำงานนานเท่าไร ผลลัพธ์ก็จะยิ่งแม่นยำขึ้น
    • ในทางกลับกัน ก็สามารถได้ผลลัพธ์ที่ไม่แม่นยำแต่รวดเร็วได้เช่นกัน
    • แทนที่จะสำรวจทุกเส้นทาง จะสำรวจเพียงเส้นทางเดียวที่ถูกเลือกแบบสุ่ม
    • การใช้ Monte-Carlo ในลูปชั้นในสุดของอัลกอริทึมจะให้ผลดี
    • ตัวอย่างเช่น ตอนฝึก neural network ลูปภายนอกจะอัปเดตพารามิเตอร์ของ neural network และลูปภายในจะคำนวณเส้นทางผ่านกราฟ
    • หากใช้ Monte-Carlo สามารถลดความแม่นยำของลูปภายในให้เหลือการวนซ้ำเพียง 1 ครั้งได้
    • โดยสัญชาตญาณแล้ว สิ่งนี้ทำให้สร้างนโยบายที่ตัดสินใจได้ถูกต้องเสมอ
    • ในหมากรุกหรือโกะ สามารถใช้รูปแบบของ Monte-Carlo tree search เพื่อคำนวณเส้นทางที่เหมาะสมที่สุดได้

  • มีจุดยืนว่า "อย่าเชื่อ autorouter"

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

  • บทความกล่าวถึงประเด็นสำคัญเกี่ยวกับการทำภาพให้เห็นและผลของแคช

    • recursive algorithm คือการค้นหาแบบ depth-first
    • DFS และ BFS สามารถเขียนได้ทั้งแบบ iterative หรือ recursive
    • A* มีประโยชน์สำหรับการหาเส้นทาง
    • BFS จะสำรวจโหนดข้างเคียงทั้งหมด ส่วน A* จะให้ความสำคัญกับโหนดที่อยู่ใกล้จุดหมายมากกว่า
    • A* เป็นอัลกอริทึมแบบ dynamic ที่สามารถหยุดก่อนกำหนดได้อย่างมั่นใจเมื่อพบเส้นทางสั้นที่สุด

  • เป็นการอภิปรายเรื่อง autorouting ที่ยอดเยี่ยม

    • ตัวการ routing เองนั้นง่าย
    • จะซับซ้อนเมื่อจำเป็นต้องเอาสิ่งที่ routing ไว้แล้วออกเพื่อให้มีที่สำหรับสิ่งใหม่
    • คิดถึง autorouter ของ KiCAD

  • 95% ของการโฟกัสควรอยู่ที่การลดจำนวนรอบการทำซ้ำ

    • หากประสิทธิภาพยังคงสำคัญ ก็ควรเขียนใหม่ด้วยภาษาระดับล่าง
    • numpy, pandas, OpenCV, TensorFlow ถูกทำขึ้นด้วย C++/assembly/CUDA ประสิทธิภาพสูง

  • QuadTree และโครงสร้างข้อมูลแบบต้นไม้ทั่วไปนั้นช้ามาก

    • ต้นไม้ไม่ใช่วิธีแสดงข้อมูลเชิงสารสนเทศของตัวข้อมูล
    • วิธีแบบ hashing เหมาะเฉพาะเมื่อจุดมีการกระจายตัวอย่างสม่ำเสมอ
    • อัลกอริทึมแบบสุ่มมีประโยชน์เมื่อพื้นที่ค้นหามีขนาดใหญ่มาก

  • แทบทุกอย่างสอดคล้องกับ heuristic ในการพัฒนาเกม

    • A*, อัลกอริทึมของ Lee และอื่น ๆ ล้วนยอดเยี่ยม
    • การเขียน flood fill โดยไม่มีการทำภาพให้เห็นถือเป็นเรื่องไม่ควรอย่างยิ่ง
    • โดยเฉพาะ spatial hashing ที่ตรงกับประสบการณ์มาก

  • "การทำดัชนีด้วย spatial hash > โครงสร้างข้อมูลแบบต้นไม้" ใช้ได้ดีในโดเมนนี้ แต่ไม่ควรถูกยอมรับว่าเป็นความจริงสากล

    • หากจุดไม่ได้กระจายอย่างสม่ำเสมอ hash function อาจทำงานได้ไม่ดี

  • จำคีย์เวิร์ดที่เรียนในมหาวิทยาลัยได้

    • ไม่มีโอกาสได้ใช้อัลกอริทึมเท่ ๆ
    • กลับต้องไปสร้าง UI component และ REST API แทน

  • ในฐานะคนที่ไม่ได้เกี่ยวข้องโดยตรงกับปัญหาเชิงพื้นที่ 2D/3D บทเรียนที่สำคัญที่สุดคือคุณค่าของการทำภาพให้เห็น

    • มนุษย์เก่งมากในการทำความเข้าใจและวิเคราะห์ภาพ
    • แนวคิดในการใช้วิธีเชิงความน่าจะเป็นหรือวิธี brute-force เพื่อทำความเข้าใจรูปร่างของปัญหานั้นสำคัญมาก