Những điều tôi ước mình biết trước khi phát triển autorouter
(blog.autorouting.com)- Kinh nghiệm phát triển PCB autorouter mã nguồn mở cho tscircuit trong khoảng 1 năm cho thấy thiết kế nhằm giảm bài toán tìm kiếm như A*, trực quan hóa, phân hoạch không gian và caching là yếu tố cốt lõi của hiệu năng
- Trọng tâm của tối ưu hóa không nằm ở ngôn ngữ hay tốc độ của một vòng lặp đơn lẻ mà ở việc giảm số lần lặp; ngay cả với JavaScript, một thuật toán thông minh hơn và có thể cache vẫn có thể nhanh hơn cách triển khai mức thấp
- Trong tìm kiếm không gian, Spatial Hash Index có thể đơn giản và nhanh hơn các cây tổng dụng như QuadTree, nhưng nếu chọn sai kích thước ô thì mỗi lần truy vấn sẽ phát sinh chi phí cố định cao
- Với pipeline autorouter phức tạp, cần trực quan hóa đầu vào/đầu ra theo từng bước và kiểm tra quá trình lặp bằng hoạt ảnh; các hàm đệ quy và cách tiếp cận Monte Carlo bất lợi cho việc gỡ lỗi, tối ưu hóa và tính xác định
- Với A*, Greedy Multiplier của Weighted A* có thể chấp nhận hy sinh một phần tính tối ưu để tăng tốc đáng kể, và mỗi bước cần giảm xác suất thất bại để tạo ra trạng thái giúp các bước sau giải dễ hơn
Dùng A* làm công cụ tìm kiếm mặc định
- A* không phải là thuật toán chỉ dành cho lưới 2D mà là thuật toán nền tảng có thể dùng cho nhiều dạng tìm kiếm có thông tin (informed search)
- BFS duyệt mọi nút lân cận, còn A* ưu tiên duyệt các nút gần đích hơn
- Vì dùng thước đo khoảng cách bên ngoài đồ thị nên nó thuộc nhóm tìm kiếm có thông tin
- Thuật toán đệ quy gần với tìm kiếm theo chiều sâu (DFS), còn vòng lặp duyệt mà không sắp xếp ứng viên hay hàng xóm thì gần với BFS
- Chuyển mã hiện có theo kiểu BFS hoặc DFS sang A* thường mang lại cải thiện hiệu năng lớn
- Trong autorouter, nhiều tầng A* được dùng để tìm siêu tham số phù hợp với bài toán
- Chạy từng cấu hình autorouter như một ứng viên
- Phân bổ thêm số vòng lặp cho những cấu hình bắt đầu định tuyến thành công với chi phí tốt
- Đây là dạng meta-A* dùng cả chi phí khoảng cách lẫn chi phí lặp làm hình phạt
Thuật toán quan trọng hơn ngôn ngữ
- Autorouter của tscircuit đang được viết bằng JavaScript, và trong các cuộc thảo luận về hiệu năng người ta thường chỉ ra ngôn ngữ trước tiên
- Tối ưu thuật toán nhìn chung chia thành hai trục lớn
- Giảm số lần lặp cần thiết để thuật toán thông minh hơn
- Tăng tốc độ thực thi của từng vòng lặp
- Nếu tập trung quá mức vào việc tăng tốc một vòng lặp, bạn có thể chỉ đang chạy nhanh hơn một cách tiếp cận sai
- Ví dụ, cách chuyển mọi thứ thành lưới để kiểm tra chồng lấp có thể chậm bất kể ngôn ngữ nào
- Một thuật toán thông minh viết bằng JavaScript vẫn có thể nhanh hơn một thuật toán đơn giản được tối ưu mức thấp bằng assembly
- Nên dành 95% thời gian phát triển để giảm số lần lặp, và ngôn ngữ tốt là ngôn ngữ giúp bạn nhanh chóng đi tới thuật toán thông minh nhất, có thể cache được
Spatial Hash Index có thể tốt hơn cây
- Trong tối ưu hóa không gian đa chiều, QuadTree xuất hiện thường xuyên nhưng cấu trúc dữ liệu cây tổng dụng có thể chậm
- QuadTree được biết đến là cấu trúc dữ liệu giúp giảm tìm kiếm đối tượng gần nhau trong không gian 2D·3D từ
O(N)xuốngO(log(N)), nhưng cây không phải là biểu diễn có thông tin về dữ liệu - Spatial Hash Index không băm chính bản thân đối tượng mà băm vị trí của đối tượng để lưu vào các ô hoặc bucket của những vị trí lân cận
- Cách tiếp cận này mang kiểu truy cập nhanh dựa trên hàm băm như HashSet, HashMap áp dụng cho dữ liệu không gian
- Lý do băm không gian ít phổ biến hơn là vì phải chọn kích thước ô phù hợp
- Nếu hiệu chỉnh sai kích thước ô, mỗi lần truy vấn sẽ phát sinh chi phí cố định cao
- Trên thực tế, việc chọn kích thước ô hợp lý có lẽ không khó đến vậy
Phân hoạch không gian và caching thay đổi hiệu năng
- Một bo mạch như bên trong iPhone có thể có khoảng 10.000~20.000 trace, và ngay cả với công cụ EDA hàng đầu, một nhóm vẫn có thể mất nhiều tháng để định tuyến
- Một ý tưởng đơn giản nhưng quan trọng trong bài toán autorouting là thứ đã được định tuyến rồi thì trước đó cũng từng được định tuyến
- Lập trình viên game pre-bake navigation mesh, còn LLM nén Internet thành trọng số để phục vụ truy xuất
- Thế hệ autorouter tiếp theo có thể chia bài toán theo không gian và tận dụng một bộ nhớ đệm lớn chứa các lời giải đã được giải trước
- Nếu 99% bài toán autorouting đã được giải sẵn trong cache thì tốc độ của bản thân thuật toán sẽ bớt quan trọng hơn
- Hiện tại nhiều thuật toán chưa tập trung đủ vào khả năng tái sử dụng cache và phân hoạch không gian
- Có vẻ chi phí lưu trữ và caching đang giảm nhanh hơn mức tăng tốc tính toán, nên dùng 1GB cache để làm autorouter nhanh hơn 50% không phải vấn đề lớn
Nhìn trực tiếp vấn đề bằng trực quan hóa và profiling
- Nguyên tắc quan trọng là nếu không có trực quan hóa về vấn đề thì khó mà giải quyết được
- Chỉ nhìn vào con số khiến việc gỡ lỗi khó khăn; nếu tạo trực quan hóa cho từng bài toán con nhỏ, bạn sẽ hiểu vấn đề nhanh hơn nhiều
- Trong quá trình phát triển autorouter, nhiều khi việc giải quyết vấn đề bắt đầu từ trực quan hóa
- Cả thuật toán con tìm đường 45 độ cũng đã được trực quan hóa, và nó được dùng ở giai đoạn gần cuối của autorouter là Path Simplification Phase
- Công cụ profiling JavaScript cho biết tổng thời gian tính bằng mili giây đã tiêu tốn trên từng dòng mã
- Chỉ cần chạy JavaScript trong trình duyệt và mở tab Performance
- Nó cũng cung cấp flame chart và tính năng theo dõi mức dùng bộ nhớ
- Video ngắn liên quan: youtube short
Tránh đệ quy và Monte Carlo
- Nói chung nên tránh hàm đệ quy trong mã định hướng hiệu năng
- Hầu như luôn chạy đồng bộ nên khó ngắt giữa chừng để làm hoạt ảnh
- Về bản chất nó là DFS nên khó chuyển trực tiếp sang A*
- Không dễ theo dõi số lần lặp
- Trong hàm đệ quy, tính khả biến là điều không tự nhiên, nhưng với hiệu năng thì khả biến có thể quan trọng
- Cách triển khai dựa trên vòng lặp có thể nhanh hơn vì có thể duy trì tập
visitedNodesvà kiểm tra nút trước khi tìm kiếm - Thuật toán Monte Carlo tiếp cận lời giải bằng tính ngẫu nhiên, nhưng vì không mang tính xác định nên khó gỡ lỗi và hiếm khi tối ưu so với heuristic
- Khi bạn biết cách đánh giá ứng viên nhưng chưa biết cách đi tới lời giải, Monte Carlo có thể hữu ích để lấy trực giác
- Khi đã có thứ gì đó gần với hàm chi phí, nên dùng cách tốt hơn các kỹ thuật ngẫu nhiên như Monte Carlo hay Simulated Annealing
- Nếu nhạy cảm với cực tiểu cục bộ, có thể cân nhắc siêu tham số hoặc hàm chi phí phức tạp hơn
- Giống như nhà thiết kế PCB không vẽ ngẫu nhiên các đường trên bo mạch, trong miền này có thể tìm được heuristic tốt hơn
Giữ các thuật toán trung gian trong cùng hệ tọa độ
- Autorouter hiện là một pipeline gồm 13 giai đoạn và khoảng 20 thuật toán con
- Số lần lặp được đo trong các tác vụ như quyết định phân hoạch không gian hay đơn giản hóa đường đi ở ranh giới các vùng được autoroute độc lập
- Nếu trực quan hóa chồng lớp đầu vào và đầu ra của từng giai đoạn, bạn sẽ hiểu được ngữ cảnh của bài toán đang giải quyết
- Các vấn đề ở bước downstream, đặc biệt là bước high density routing, thường được giải quyết bằng cách cải thiện đầu ra của các bước trước
- Khi tạo thuật toán con, rất dễ bị cám dỗ tách bài toán về dạng đơn giản nhất và chuẩn hóa tọa độ quanh
(0, 0) - Việc chuẩn hóa hoặc biến đổi phức tạp có thể khiến bạn khó nhanh chóng thấy ảnh hưởng của kết quả từ giai đoạn đầu lên các giai đoạn sau
- Cách giữ nhất quán không gian tọa độ trong toàn bộ vòng đời thuật toán sẽ có lợi hơn
- Quan sát từng bước theo thứ tự rồi phóng to giúp tìm ra giai đoạn gây ra Design Rule Check thất bại
Hoạt ảnh vòng lặp và tránh lưới hóa
- Vì giảm số lần lặp là quan trọng, xem hoạt ảnh các vòng lặp của thuật toán giúp trực giác nhận ra phần tìm kiếm bị lãng phí
- Hoạt ảnh đặc biệt hữu ích khi điều chỉnh Greedy Multiplier
- Có trường hợp một trace đơn giản lẽ ra phải thất bại ngay nhưng lại cứ cố giải mãi ra phía ngoài; nếu không có hoạt ảnh thì rất khó phát hiện
- Có hai cách lớn để xác định hai trace A và B có chồng lên nhau không
- Xem từng segment của A và B rồi kiểm tra giao cắt
- Đánh dấu lưới nơi B tồn tại, sau đó kiểm tra xem trong các ô lưới A đi qua có B hay không
- Cách dùng lưới có thể dễ dàng chậm hơn 1000 lần
- Với toán học vector nhanh, phép dot product để xác định giao cắt giữa hai segment có thể còn nhanh hơn truy cập bộ nhớ để kiểm tra một ô lưới đơn lẻ
- Nói chặt chẽ hơn, để bảo đảm khoảng hở phù hợp thì cần tính khoảng cách giữa các segment; việc này phức tạp hơn kiểm tra giao cắt một chút nhưng không quá khác biệt
Xác suất thất bại và Weighted A*
- Trong giai đoạn phân hoạch không gian, có thể đo xác suất thất bại của việc giải ở từng bước như một chỉ báo sớm
- Unravel Autorouter theo dõi xác suất thất bại của từng Capacity Node ở mỗi giai đoạn chính của pipeline
- Mỗi bước tập trung giảm xác suất thất bại thông qua tái cấu hình nút lân cận hoặc định tuyến lại
- Xác suất thất bại thực sự có thể đo được, và khi thuật toán thay đổi thì dự đoán cũng có thể được cải thiện
- Mỗi bước có thể hoạt động theo hướng làm giảm khả năng thất bại của các bước sau
- Thay vì đưa quá nhiều ràng buộc cùng lúc, nên ưu tiên khả năng giải được
- Một khi bo mạch đã được giải, việc xử lý lời giải hiện có thường dễ hơn là tạo ra lời giải tối ưu ngay từ đầu
Đánh đổi tốc độ và tính tối ưu bằng Greedy Multiplier
- A* cơ bản đảm bảo lời giải tối ưu, nhưng nếu coi trọng tốc độ hơn thì có thể sửa nhẹ
f(n)để dùng Weighted A* - A* thông thường:
f(n) = g(n) + h(n) - Weighted A*:
f(n) = g(n) + w * h(n) - Weighted A* giải bài toán theo hướng tham lam hơn và thường chạy nhanh hơn rất nhiều
- Cách này đóng vai trò Greedy Multiplier, giúp tăng mạnh hiệu năng của A* để đổi lấy việc từ bỏ một phần tính tối ưu
- Có thể xem thêm Weighted A* và các biến thể A* khác tại weighted A* and other A* variants here
- Nhà phát triển game xử lý nhiều bài toán tương tự nhà phát triển autorouting, nên khi tìm nghiên cứu liên quan có thể xem các bài báo về phát triển game
Autorouter sắp được công khai
- Autorouter cho tscircuit đang tiến gần đến thời điểm phát hành
- Thành quả này sẽ được cung cấp dưới dạng mã nguồn mở theo giấy phép MIT
- Việc giải quyết autorouting có thể mở ra bước tiến lớn cho đổi mới trong thế giới vật lý và là mảnh ghép cốt lõi để tạo ra kiểu “vibe-building” cho sản phẩm điện tử
- Tài khoản liên quan: follow me on twitter.
1 bình luận
Ý kiến trên Hacker News
Nhìn chung tôi thuộc phe không tin autorouter, và với các công cụ AI đang bước vào lĩnh vực này cũng vậy, nhưng khó phủ nhận rằng có một cơ hội lớn để tạo nhanh một phần layout trong eCAD
Có lẽ tôi sẽ dùng công cụ đồng sáng tạo hơn là công cụ hoàn toàn tự động. Ở giai đoạn đầu thiết kế, vị trí linh kiện thường chưa được chốt, mà placement lại ảnh hưởng rất lớn đến routing. Tôi không thấy trên trang có nói placement có được đưa vào thuật toán hay không. Hiện tôi đã dùng các công cụ như push-and-shove hoặc thỉnh thoảng là tự động hoàn tất
Thị trường này nhỏ, công cụ thì phân mảnh, các hãng hiện hữu là những gã khổng lồ chậm chạp, còn người dùng là những người đam mê khó tính. Tôi nhất quyết không bỏ KiCad. Bản thân việc autorouter được viết bằng JavaScript thì tôi không có ý kiến gì nhiều, nhưng tôi tò mò liệu họ định bám vào các nhà cung cấp CAD hay hệ sinh thái công cụ mã nguồn mở, hay lại muốn kéo mọi người sang một hệ sinh thái mới khác
Nếu thân thiện với cache, tốc độ di chuyển linh kiện và thử các layout khác sẽ nhanh hơn nhiều. JavaScript giờ đã khá dễ mang đi, với cả các runtime nhỏ như QuickJS hay Proffor, và tôi nghĩ có thể chạy cục bộ rồi tự tạo các cache khổng lồ
Lock-in và phân mảnh hệ sinh thái trong EDA là điều mọi người đều nên lo ngại, nhưng tscircuit và autorouter này là công nghệ theo giấy phép MIT dễ dãi, nên trong EDA có thể, khá hiếm hoi, được làm để tương tác được với tất cả mọi bên
Sau khi cố định footprint, placement, ràng buộc và các net đã route thủ công, có thể lặp lại rất nhanh
Kể từ khi Cadence mua SPECCTRA vào thập niên 90, autorouter PCB đã khá trì trệ, nên thật vui khi có ai đó quay lại xử lý lĩnh vực này. Theo tôi nhớ, những người làm SPECCTRA đã chuyển sang mảng VLSI và không quay lại nữa; danh tiếng và tiền bạc có vẻ nằm ở đó. Có thể trong một thời gian đây là bãi mìn bằng sáng chế, và biết đâu bây giờ vẫn vậy
Auto-placement khi đó đã là một bài toán hoàn toàn khó nhằn, và giờ trông vẫn thế, nhưng cách tiếp cận AI tạo sinh có thể phù hợp. Một lần đặt linh kiện ban đầu tốt dựa trên AI tạo sinh có thể rút ngắn tổng thời gian. Vấn đề lớn nhất là thuyết phục những người cứng đầu rằng không cần hoàn hảo mà chỉ cần đủ tốt là đã được
Các nỗ lực làm schematic dạng code khiến tôi hơi khó hiểu. Nếu dùng làm định dạng backend thì mong là sẽ ổn, và tôi đặc biệt thích những tiến triển kiểu jitx, như mã hóa các quy tắc thiết kế ở mức app note và datasheet vào model linh kiện. Đọc mọi datasheet đến mức cần thiết cho thiết kế thương mại là khối lượng công việc lớn hơn nhiều so với tưởng tượng, và việc cho kỹ sư junior học quá trình đó cũng vậy, nên tự động hóa là có ích
Tuy nhiên, các cách tiếp cận này dường như bắt rễ từ ý tưởng xem schematic là dữ liệu đầu vào cho layout, một dạng mã nguồn. Schematic cũng là tài liệu thiết kế với một ngôn ngữ trực quan đã tiến hóa rất tinh tế, cần có thể truy cập được cả với người không cài bộ sản phẩm EDA. Những người học bằng cách giải mã các schematic kiểu Adafruit/Sparkfun/Shenzhen, nơi giảm tối đa wiring tường minh, có thể không hiểu hết giá trị của một schematic tốt
Một điểm nữa là xu hướng dựa quá nhiều vào phép loại suy để biến thiết kế cấp PCB thành giống thiết kế VLSI. Tôi không cho là hoàn toàn bất khả thi. Nếu DRC và công cụ kiểm chứng tốt hơn, thiết kế cấp linh kiện cũng có thể tiến gần hơn tới VLSI. Nhưng sự liên kết giữa thiết kế, EDA/CAM/mô phỏng, kiểm chứng, nhà sản xuất, đơn vị lắp ráp, nhà cung cấp linh kiện, cơ quan quản lý/chứng nhận quá lỏng lẻo, nên chỉ cần làm tốt một góc trong số đó đã là thành quả lớn
Ngày nay xu hướng là thực hiện thiết kế UHF có kiểm soát trở kháng cùng với các công cụ mô phỏng chuyên biệt theo miền. Vì vậy người ta route thủ công các trace quan trọng trước, tạo các island pole, rồi cuối cùng xử lý kết nối nguồn
Layout KiCad thì còn hơn không một chút, nhưng cố biến nó thành thêm một công cụ mô phỏng nửa vời nữa thì trông thật buồn cười
Đó là hỗ trợ cơ sở dữ liệu và tính năng outjob. Ngoài ra thì vấn đề gần với việc adoption và người dùng tận dụng các tính năng này như thế nào hơn; còn cơ sở dữ liệu thường kéo theo nhiều quan liêu nội bộ về việc dọn dẹp dữ liệu
Xét từ góc độ workflow giúp layout nhanh hơn, tôi nghĩ KiCad cũng đã phần nào đi theo hướng đó. Ví dụ có tính năng “tự động hoàn tất trace” được đưa vào khoảng bản 7.0. Trong pcbnew hình như phím tắt là F, nó sẽ trải trace của track đang đặt. Khi dùng cùng phím tắt “route từ phía đối diện của track” là E, năng suất tăng đáng kể khi làm việc giữa hai lưới ballout khác nhau
Ở phiên bản 9, có thể kéo bus hoặc nhiều track, nên luồng này có thể còn nhanh hơn
Thành thật mà nói, nếu có thể đi đến placement đủ hài lòng và đặt ràng buộc về vị trí route cho autorouter, thì tôi nghĩ có thể giao một phần đáng kể thiết kế cho autorouter. Ví dụ năm ngoái tôi làm một bo dùng NXP iMX8MP và eMMC; ballout ngoại vi quanh processor khớp tốt với ballout của eMMC, nên chỉ cần căn chip rồi vẽ dây. Nếu autorouter chỉ cần biết phải giữ data bus ở lớp trên cùng, nó đã có thể làm trong vài giây việc mất 10 phút
Có một vấn đề về tiêu chí thành công mà các dự án autorouter gặp phải. Dường như họ nghĩ phải xử lý được mọi thứ trên bo thì mới là “hoàn thành”, nhưng với tư cách kỹ sư điện thực chiến, tôi không muốn điều đó. Tôi muốn một autorouter cùng xử lý từng khối nhỏ của thiết kế, cho tôi thời gian review rồi mới chuyển sang khối tiếp theo
Nếu còn có thể đặt ràng buộc qua các lớp thì rất mạnh. Ví dụ như “giữ mọi net tên D0-7 ở lớp 1 và 3, khớp chiều dài với nhau trong phạm vi 5mm, và lấy D0 làm chuẩn chiều dài”. Nếu làm được điều này thì coi như đã giải quyết length tuning cho DRAM, và thiết kế có độ phức tạp rộng hơn nhiều sẽ trở nên khả thi với cả người dùng phổ thông
Nếu có thời gian, tôi muốn cho xem demo ý tôi là gì
Ở mục 8, việc bác bỏ phương pháp Monte Carlo quá sớm là một sai lầm lớn
Điểm cốt lõi của Monte Carlo là có thể đánh đổi độ chính xác lấy tốc độ. Thuật toán chạy càng lâu thì càng chính xác
Điều thú vị hơn là chiều ngược lại cũng thường dùng được. Có thể nhận được một kết quả rất không chính xác với tốc độ rất nhanh. Chẳng hạn thay vì khám phá mọi đường đi, chỉ khám phá một đường đi được chọn ngẫu nhiên
Cách này tỏa sáng khi đưa vào vòng lặp lồng nhau sâu nhất của thuật toán. Ví dụ, để huấn luyện một mạng nơ-ron học đi dây tự động, vòng lặp bên ngoài cập nhật các tham số của mạng nơ-ron, còn vòng lặp bên trong tính toán đường đi qua đồ thị
Nếu dùng Monte Carlo, miễn là không có thiên lệch, có thể giảm vòng lặp bên trong kiểm soát độ chính xác này xuống còn 1 lần lặp. Phương sai sẽ tăng khiến vòng lặp bên ngoài chậm lại, nhưng học máy “về mặt lý thuyết” vẫn có thể học được
Vì vậy có thể tạo ra một chính sách chọn quyết định đúng theo trực giác, giống như trong cờ vua hay cờ vây. Trong các biến thể tìm kiếm cây Monte Carlo như AlphaGo Zero, AlphaChess Zero, AlphaRouter Zero, ngay cả khi không có phần tìm kiếm, một bộ nhớ đệm khổng lồ được mã hóa bằng các tham số mạng nơ-ron sau khi học có thể tính đường đi ước lượng tốt nhất chỉ bằng một lượt truyền qua mạng nơ-ron, tức thời gian hằng số. Hằng số này có thể dễ dàng đánh đổi giữa bộ nhớ và tốc độ bằng cách tăng số tham số hoặc huấn luyện lâu hơn
MC là loại thuật toán giúp giữ cảm giác thực tế. Nó chậm, nhưng hầu như luôn rất đơn giản để triển khai, và đáng tin cậy để kiểm tra lại với độ tin cậy rất cao rằng mình chưa đi chệch sang một nơi hoàn toàn vô lý
Đây là một cuộc thảo luận rất hay về đi dây tự động, nhưng đoạn kết bằng câu “mảnh ghép cốt lõi giúp vibe-building thiết bị điện tử trở nên khả thi” khiến hơi nhói
Bản thân việc đi dây thì dễ. Nó trở nên phức tạp vào khoảnh khắc phải gỡ những đường đã đặt sẵn để thêm đường mới, và bùng nổ tổ hợp ập tới
Tôi nhớ bộ đi dây tự động từng có trong KiCad. Nó bị gỡ bỏ vì những lý do sở hữu trí tuệ mơ hồ, do tác giả từng làm việc ở một công ty đi dây tự động. Với những người dùng xin đưa nó trở lại, phản ứng kiểu như “đàn ông đích thực không dùng bộ đi dây tự động”
https://forum.kicad.info/t/autorouting-and-autoplacement/185...
Tôi hy vọng bộ đi dây tự động này và các công cụ khác tiếp sau sẽ giúp mọi người ra mắt sản phẩm điện tử đầu tiên mà không cần nhiều bản đồ chỉ dẫn hay đào tạo chính quy
Tất nhiên một bộ đi dây tự động tốt cũng phải hữu ích cho chuyên gia, nên tôi cũng mong nó giúp được phần đó
Nhưng với tư cách một trong những người già khó tính không mấy muốn thấy KiCad dồn sức cho bộ đi dây tự động, bộ đi dây tự động PCB luôn là thứ đau đầu và không hoạt động đúng
Có thể hiểu lý do nếu nhìn vào bộ đi dây tự động VLSI. Bộ đi dây tự động VLSI cũng từng là thứ đau đầu và không hoạt động đúng. Rồi VLSI có rất nhiều lớp, đến mức có thể phân riêng lớp cho đi dây dọc, lớp cho đi dây ngang, lớp cho nguồn, mà vẫn còn thêm vài lớp nữa cho kết nối dọc toàn cục, kết nối ngang toàn cục và nguồn toàn cục
Vấn đề căn bản của đi dây tự động PCB là PCB có nhiều chướng ngại vật hơn chip VLSI rất nhiều. Thứ nhất, bản thân linh kiện vừa là chướng ngại vừa là nút thắt. Thứ hai, via trên PCB hầu như luôn chặn mọi lớp của bo mạch, còn via trong VLSI chỉ chặn hai lớp mà nó kết nối. Thứ ba, via trên PCB thường lớn hơn bề rộng kim loại đi dây. Thứ tư, số lớp dùng trong PCB ít hơn VLSI rất nhiều. Phổ biến là 4 lớp, trong đó chỉ có 2 lớp thật sự dùng cho đi dây thông thường; vì chi phí nên 2 lớp cũng rất nhiều và còn khó đi dây tự động hơn, còn 6 lớp thì chỉ là thiểu số rất nhỏ
Kết quả là đi dây tự động PCB là một bài toán phức tạp hơn đi dây tự động VLSI rất nhiều
Bài viết nhấn mạnh đặc biệt đến trực quan hóa và hiệu ứng cache là một điểm hay
Tuy nhiên có vài chỗ khiến tôi lấn cấn. Nói rằng “thuật toán đệ quy là tìm kiếm theo chiều sâu, còn vòng lặp tìm kiếm mà không sắp xếp ứng viên hay láng giềng là tìm kiếm theo chiều rộng” có vẻ sai hoặc bỏ lỡ trực giác cốt lõi. DFS và BFS đều có thể viết bằng vòng lặp hoặc đệ quy; khác biệt thực sự là lấy ứng viên tiếp theo từ đỉnh hay đáy của stack, tức dùng stack (FILO) hay queue (FIFO)
Nhận định A* là nền tảng tốt nhất cho mọi tìm kiếm dựa trên thông tin cũng cần có ngữ cảnh. Nó hữu ích cho tìm đường khi có khái niệm “khoảng cách” đến mục tiêu dễ tính toán và chỉ chạy vài truy vấn trên cùng một đồ thị. Nếu định chạy nhiều truy vấn trên một đồ thị gần như tĩnh như mạng đường bộ, các thuật toán tiền xử lý như contraction hierarchy có thể tốt hơn. Nếu là bài toán tối ưu hóa nhưng không có mục tiêu cố định như bài toán người bán hàng du lịch, các heuristic tìm kiếm cục bộ khác như 2-opt có thể tốt hơn
“BFS khám phá tất cả nút kề còn A* ưu tiên các nút gần đích” đúng là một khác biệt, nhưng khác biệt lớn hơn là A* là thuật toán động. Vì vậy nó có thể kết thúc sớm khi chắc chắn đã tìm được đường đi ngắn nhất. BFS có thể chưa chắc chắn cho đến khi duyệt toàn bộ đồ thị, mà đồ thị thì có thể rất lớn
Trong hầu hết ngôn ngữ, diễn đạt như vậy dễ hơn so với việc nghĩ đến một stack bên ngoài. Vì thế khi thấy đệ quy trong mã thực tế thì nhiều khả năng nó gần với DFS hơn, nhưng đó không phải quy tắc nghiêm ngặt
BFS dùng queue FIFO, DFS dùng stack LIFO, A* dùng priority queue thường được triển khai bằng heap
Đây là một trong những bất biến cơ bản khiến BFS cho kết quả đúng, nên có thể kết thúc sớm khi đã đến tất cả mục tiêu
Khác biệt giữa A* và BFS nằm ở chỗ BFS không tìm đường ngắn nhất giữa hai điểm, mà tìm đường đi ngắn nhất từ một điểm xuất phát đến mọi điểm trong đồ thị. A* là sự đánh đổi để tăng tốc từng truy vấn riêng lẻ bằng cách trả lời một câu hỏi yếu hơn
Nếu cấu trúc bài toán cho phép, chỉ cần thay hàng nghìn lần gọi A* bằng một lần gọi BFS hoặc Dijkstra cũng có thể đem lại cải thiện tốc độ lớn. Một khác biệt quan trọng nữa là BFS chỉ hoạt động trên đồ thị có mọi cạnh cùng độ dài, còn A* hỗ trợ các cạnh có độ dài khác nhau. Hai thứ này không thể thay thế lẫn nhau, giống như việc tìm phần tử nhỏ nhất trong danh sách không thay thế cho việc sắp xếp danh sách
Các câu như “quadtree và mọi cấu trúc dữ liệu cây đa dụng đều chậm kinh khủng”, “cây không phải là biểu diễn chứa thông tin về dữ liệu”, “mỗi lần dùng cây là đang dùng một thuật toán O(log N) phức tạp hơn thay vì thuật toán băm O(~1)” là những nhận định đi khá sai hướng
Cách tiếp cận bằng hashing ổn khi các điểm phân bố đều và chỉ truy vấn các vùng gần với phân hoạch cố định đã chọn. Nếu không, O(1) đó có thể sụp thành O(n)
Khi không biết phân bố dữ liệu, cây là một biểu diễn có chứa thông tin
Thuật toán ngẫu nhiên cũng tương tự. Nếu không gian tìm kiếm gồm hàng nghìn tỷ mục hoặc khả năng trở lên thì sẽ làm gì? Nếu cũng không có heuristic thì sao? Trong tình huống không thể vét cạn và cũng không dùng được thuật toán thông minh, thuật toán ngẫu nhiên trở thành cứu cánh
Ứng dụng cụ thể này có thể không cần, nhưng tốt hơn nên tránh các khẳng định khái quát hóa
Nghiêm túc hơn thì các thuật toán dựa trên cây có xu hướng bị đánh giá quá cao, và có vẻ mọi người quá sa đà vào hành vi Big-O mà quên rằng hệ số hằng vẫn rất quan trọng ngay cả với hàng trăm nghìn phần tử. Những thứ như locality của dữ liệu cũng vậy. Đôi khi chỉ quét tuần tự còn nhanh hơn làm sổ sách cho một cấu trúc phức tạp hơn
Nhìn chung, tốt hơn là bọc các thao tác trong các wrapper nhỏ, làm bản triển khai dễ trước rồi để đo đạc quyết định
Trường hợp xấu nhất là phải viết lại toàn bộ chương trình theo một cấu trúc khác để nhắm đến hiệu năng tốt hơn, nhưng theo kinh nghiệm, khi viết lại file từ đầu thường cũng kéo theo khá nhiều cải thiện miễn phí
Tôi vẫn chưa tìm được cách nào thật sự ưng ý để lưu các điểm 2D hoặc 3D và truy vấn các điểm lân cận. kD-tree thì tốt, nhưng tôi muốn thêm điểm trong khi chạy, chứ không phải xây cấu trúc trên một tập cố định
Gần như mọi nội dung đều khớp với heuristic phát triển game của tôi. Tôi cũng hiểu việc chọn JavaScript
Hiện tôi đang làm một framework modding game hoạt động bằng S-expression kiểu Lisp, và nhận ra rằng tối ưu hóa để rút ngắn thời gian lặp sáng tạo là quan trọng hơn hết
Những thứ như A*, thuật toán Lee đều rất tuyệt. Không làm kèm trực quan hóa cho bất kỳ kiểu flood fill nào gần như là một tội ác. Như vậy là lãng phí quá nhiều dopamine
Đọc bài này khiến tôi tự hỏi liệu những kỹ thuật tôi chưa đọc nhưng nằm gần lĩnh vực phát triển game có hữu ích cho các vấn đề kiểu này không. Chắc tôi không phải người đầu tiên nghĩ rằng một router kiểu boids sẽ khá thú vị. Nghiêm túc hơn, tôi nghĩ trường khoảng cách có dấu dựa trên jump flooding có thể mang lại rất nhiều sức mạnh
Đặc biệt, phần về spatial hashing khớp với kinh nghiệm của tôi. Trong gần 20 năm, tôi không thấy nhiều trường hợp cấu trúc cây đáng với thời gian bỏ ra. Có một ngoại lệ: trình soạn thảo văn bản kiểu Lovecraft mà tôi làm dùng trie khá nhiều để xử lý tính phản hồi. Đó là một cách hay để biến 45.000 từ thành một máy trạng thái nén phục vụ xử lý sự kiện
Trước đây tôi từng viết về autorouter cho mẫu đệ quy; không gian lời giải nhỏ nên tương đối dễ dự đoán bằng các thuật toán học máy hiện có. Trong autorouting vẫn còn rất nhiều vùng thú vị chưa được khám phá
Tôi chưa biết jump flooding. Bổ sung cho những người khác: đó là thuật toán xấp xỉ nhanh trường khoảng cách theo cách song song. Chắc chắn có thể rất thú vị; cảm ơn vì đã cho biết
Cây cũng hợp với thuật toán đệ quy, và tác giả nói rằng có lý do để chọn thuật toán lặp thay vì đệ quy, nên các lời khuyên này ăn khớp với nhau
Nhìn rộng ra, phân biệt “đệ quy” và “không đệ quy” có phần nhân tạo. Câu hỏi thật sự là “một thuật toán dựng sẵn với các quy tắc nghiêm ngặt sẽ nắm luồng điều khiển, hay tôi nắm”. Nếu bạn quan tâm nhiều đến hiệu năng, câu trả lời nên là tôi nắm; khi trạng thái thực thi bị trừu tượng hóa vào stack do môi trường chạy cung cấp và trở nên khó thay đổi một cách kỳ lạ ở runtime, nó bắt đầu trở thành trở ngại
Câu “95% sự tập trung nên dành cho việc giảm số vòng lặp. Vì vậy ngôn ngữ không quan trọng” đúng ở một mức nào đó, nhưng nếu sau khi dùng một ngôn ngữ thông dịch/trừu tượng/chậm, vui nhộn và giàu biểu đạt để tạo ra một thuật toán xuất sắc, hiệu năng tốt mà hiệu năng vẫn quan trọng, thì chỉ cần viết lại cùng thứ đó bằng một ngôn ngữ cấp thấp có hiệu năng cao, và nếu cần thì viết cả assembly riêng cho từng kiến trúc
Có lý do khiến numpy, pandas, OpenCV, TensorFlow không được viết bằng Python thuần. Python đóng vai trò điều phối các tác vụ được triển khai bằng C++/assembly/CUDA hiệu năng cao, v.v.
Dù bạn có tự hào đến đâu về việc đã khám phá không gian vấn đề, tìm ra thuật toán hiệu quả và viết blog về nó, nếu cứ khăng khăng chỉ viết bằng Python hoặc JavaScript thuần thì khó mà trở thành một thư viện tính toán số phổ biến
Bài viết thú vị thật, nhưng nếu nhờ insight thuật toán của tác giả mà một bộ mã hóa HEVC JavaScript thuần giảm từ 1 ngày mỗi khung hình xuống 3 giờ, tôi nghĩ khó mà rút ra cùng kết luận
Tôi thấy rất nhiều từ khóa nhớ từ thời đại học. Ước gì có dịp dùng các thuật toán nổi tiếng và hay ho đó
Thực tế thì tôi chỉ đang làm các component UI và REST API để hiển thị kết quả Elasticsearch. Mọi thứ thú vị đều bị chôn trong hộp đen
Trong phát triển game có nhiều thuật toán không thể tránh khỏi, nên nếu muốn tạo thuật toán, hãy thử làm một game kiểu tower defense; bạn sẽ phải xử lý rất nhiều thuật toán kinh điển
Ít nhất, tôi nghĩ bằng khoa học máy tính hiện nay nên được tách nhỏ. Phần toán học hay ho nên thành một bằng riêng, và có thể gộp với một bằng mới liên quan đến AI. Lý thuyết cơ sở dữ liệu và mạng cũng nên là bằng riêng, assembly cấp thấp cũng vậy. Cách linh kiện điện tử, cổng NAND, đại số Boole, v.v. hoạt động nên chuyển sang ngành kỹ thuật điện tử
Nếu cứ khăng khăng rằng những người thị trường cần nhiều nhất, tức người có thể sản xuất các ứng dụng CRUD, nhất thiết phải có kiến thức học thuật, thì nên biến nó thành một bằng riêng hoặc chuyển sang hướng đào tạo nghề
Đồng thời, cũng cần xử lý bằng luật vai trò gác cổng trong yêu cầu tuyển dụng. Không nên cho phép yêu cầu bằng cấp gần như chẳng liên quan đến công việc thực tế. Hiện nay điều đó đang khiến bọn trẻ lãng phí nhiều năm cuộc đời, gánh nợ từ năm đến sáu chữ số đô la, chỉ để giúp công ty lọc người dễ hơn
Tôi không trực tiếp xử lý các bài toán không gian 2D/3D, nhưng bài học lớn nhất là giá trị của trực quan hóa
Con người rất giỏi hiểu và phân tích hình ảnh. Một bài học nữa là ý tưởng dùng phương pháp xác suất hoặc brute force để nắm hình dạng của vấn đề trước, rồi chọn cách tốt hơn phù hợp với nó, chứ không chỉ dựa vào hiểu biết lý thuyết thuần túy
Câu “ngôn ngữ triển khai không quan trọng” có thể đúng trong lĩnh vực này, nhưng nếu áp dụng vào kỹ nghệ phần mềm nói chung thì giả định rằng lựa chọn ngôn ngữ không ảnh hưởng đến tốc độ và số vòng lặp cần thiết là rất sai
Nếu đang ở giai đoạn kiểm soát các hạng mũ hoặc đa thức, khác biệt giữa Rust hay assembly hard-code với JavaScript hay VisualBasic có thể trở nên khá vô nghĩa