Tổng quan nghiên cứu

Việc sắp xếp thời khóa biểu hợp lý và hiệu quả là một yêu cầu quan trọng đối với các trường đại học hiện nay, đặc biệt khi số lượng môn học, phòng học và giảng viên ngày càng tăng, dẫn đến không gian tìm kiếm phức tạp và thời gian xử lý kéo dài. Theo ước tính, các giải thuật truyền thống khi chạy trên bộ xử lý đơn thường mất hàng giờ đến hàng chục giờ để tạo ra thời khóa biểu phù hợp với các ràng buộc cứng và mềm. Mục tiêu của nghiên cứu này là phát triển và hiện thực giải thuật di truyền (Genetic Algorithm - GA) song song trên bộ đồng xử lý Intel Xeon Phi nhằm giảm đáng kể thời gian thực thi mà vẫn đảm bảo chất lượng thời khóa biểu.

Phạm vi nghiên cứu tập trung vào bài toán sắp xếp thời khóa biểu hệ tín chỉ tại một trường đại học, với dữ liệu đầu vào gồm số lượng môn học, phòng học, giảng viên và các ràng buộc cụ thể về thời gian, phòng học, và giảng viên bận việc. Thời gian nghiên cứu kéo dài từ tháng 1 đến tháng 6 năm 2018, thực hiện trên máy trạm trang bị bộ đồng xử lý Intel Xeon Phi 7120p với 61 nhân và 244 luồng thực thi. Ý nghĩa của nghiên cứu được thể hiện qua việc rút ngắn thời gian thực thi lên đến 20 lần đối với tập dữ liệu nhỏ và 4 lần đối với tập dữ liệu lớn so với các giải thuật truyền thống, đồng thời vẫn đảm bảo các ràng buộc cứng và tối ưu hóa các ràng buộc mềm trong thời khóa biểu.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên hai lý thuyết chính: giải thuật di truyền (Genetic Algorithm - GA) và các phương pháp song song cho giải thuật di truyền. GA mô phỏng quá trình tiến hóa tự nhiên, bao gồm các bước khởi tạo quần thể, chọn lọc, lai ghép, đột biến và tìm kiếm cục bộ (Local Search) nhằm tối ưu hóa lời giải. Các khái niệm chính bao gồm:

  • Ràng buộc cứng và mềm: Ràng buộc cứng như không trùng lịch giảng viên, phòng học không bị trùng, môn học thực hành phải vào phòng thực hành; ràng buộc mềm như ưu tiên xếp các tiết học cùng môn ở cùng phòng, phòng học đủ sức chứa sinh viên, tiết học trải đều trong tuần.
  • Phương pháp song song: Bao gồm mô hình Master-Slave, Fine-Grained và Coarse-Grained, trong đó mô hình Master-Slave được áp dụng để phân bổ tính toán giá trị lượng giá cho các luồng xử lý trên Xeon Phi.
  • Kiến trúc Intel Xeon Phi: Bộ đồng xử lý với hơn 50 nhân, mỗi nhân có 4 luồng, hỗ trợ vector 512-bit SIMD, tối ưu cho các tác vụ tính toán song song và vector hóa.

Phương pháp nghiên cứu

Nguồn dữ liệu sử dụng là tập dữ liệu ITC-2007 Curriculum Based Course TimeTabling, gồm 19 bộ dữ liệu đầu vào với số lượng môn học từ 30 đến hơn 120, số phòng học từ 138 đến 390, và số tiết học từ 5 đến 20 ngày trong tuần. Phương pháp phân tích bao gồm:

  • Hiện thực giải thuật di truyền với cấu trúc MEM (Memory) và tìm kiếm cục bộ để cải thiện chất lượng lời giải.
  • Áp dụng song song hóa trên bộ đồng xử lý Intel Xeon Phi 7120p theo hướng Native, sử dụng OpenMP để phân phối các phép lai ghép và đột biến trên các luồng xử lý.
  • Thời gian nghiên cứu thực hiện trong 6 tháng, từ tháng 1 đến tháng 6 năm 2018, với các thử nghiệm trên tập dữ liệu nhỏ và lớn để đánh giá hiệu quả về thời gian và chất lượng lời giải.

Cỡ mẫu nghiên cứu là 100 cá thể trong quần thể, số lần lặp tối đa 3000, thời gian thực thi tối đa 2000 giây cho mỗi thử nghiệm. Phương pháp chọn mẫu là khởi tạo ngẫu nhiên cá thể, áp dụng các phép lai đa điểm và đột biến hai điểm, ba điểm để đa dạng hóa quần thể.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

  1. Tăng tốc độ thực thi đáng kể: Giải thuật di truyền song song trên Xeon Phi cho thời gian thực thi nhanh hơn 20 lần so với thực thi trên bộ xử lý đơn đối với tập dữ liệu nhỏ (ví dụ Comp1, Comp11). Với tập dữ liệu lớn, thời gian thực thi giảm khoảng 4 lần so với các giải thuật truyền thống không song song, từ hơn 16.784 giây xuống còn khoảng 2000 giây.

  2. Chất lượng thời khóa biểu tương đương hoặc tốt hơn: Kết quả về số vi phạm ràng buộc mềm của giải thuật đạt mức 5 đối với Comp1 và 0 đối với Comp11, tương đương hoặc gần bằng các giải thuật tiên tiến như “repair-based timetable” của Clark et al. và “threshold acceptance metaheuristic” của Geiger.

  3. Hiệu quả song song hóa với số luồng thực thi: Với tập dữ liệu nhỏ, số luồng thực thi tối ưu là 122 (gấp đôi số core), còn với tập dữ liệu lớn là 244 (gấp 4 lần số core). Việc tăng số luồng giúp giảm thời gian thực thi nhưng vượt quá mức này không cải thiện đáng kể.

  4. Ứng dụng cấu trúc MEM và Local Search: Việc sử dụng cấu trúc MEM giúp tạo cá thể con hiệu quả, tránh tối ưu cục bộ, trong khi Local Search cải thiện chất lượng cá thể bằng cách giảm vi phạm ràng buộc cứng và mềm.

Thảo luận kết quả

Nguyên nhân chính của việc tăng tốc độ thực thi là do tận dụng kiến trúc nhiều nhân và vector SIMD 512-bit của Intel Xeon Phi, kết hợp với song song hóa các phép lai ghép và đột biến trên nhiều luồng. So với các nghiên cứu trước đây chỉ chạy trên CPU đơn hoặc đa nhân hạn chế, việc sử dụng bộ đồng xử lý này giúp giảm đáng kể thời gian tính toán mà không làm giảm chất lượng lời giải.

Kết quả cũng cho thấy việc áp dụng Local Search và cấu trúc MEM là cần thiết để tránh rơi vào tối ưu cục bộ, đặc biệt với các tập dữ liệu lớn có không gian tìm kiếm phức tạp. So sánh với các giải thuật như Simulated Annealing hay Tabu Search, giải thuật di truyền song song trên Xeon Phi đạt hiệu quả cân bằng giữa thời gian và chất lượng.

Dữ liệu có thể được trình bày qua biểu đồ so sánh thời gian thực thi giữa các số luồng khác nhau và bảng so sánh số vi phạm ràng buộc giữa các giải thuật, giúp minh họa rõ ràng hiệu quả của phương pháp đề xuất.

Đề xuất và khuyến nghị

  1. Mở rộng sử dụng đa bộ đồng xử lý: Áp dụng lập trình offload để tận dụng đồng thời hai card Intel Xeon Phi và CPU trên máy trạm, nhằm tăng hiệu suất tính toán và giảm thời gian thực thi hơn nữa.

  2. Tối ưu hóa hàm lượng giá và Local Search: Sử dụng các mảng trung gian để giảm số lần tính toán hàm lượng giá trong Local Search, từ đó giảm thời gian thực thi mà vẫn đảm bảo chất lượng lời giải.

  3. Kết hợp các heuristic khác: Áp dụng kết hợp với các phương pháp tìm kiếm khác như Tabu Search hoặc các thuật toán metaheuristic hỗn hợp để tránh tối ưu cục bộ và nâng cao chất lượng thời khóa biểu.

  4. Phát triển giao diện người dùng và tích hợp hệ thống: Xây dựng giao diện trực quan cho người quản trị để dễ dàng nhập dữ liệu, điều chỉnh ràng buộc và theo dõi kết quả, đồng thời tích hợp giải thuật vào hệ thống quản lý đào tạo của trường.

Các giải pháp trên nên được thực hiện trong vòng 12-18 tháng tiếp theo, với sự phối hợp giữa nhóm nghiên cứu và bộ phận công nghệ thông tin của trường đại học.

Đối tượng nên tham khảo luận văn

  1. Nhà quản lý đào tạo đại học: Giúp hiểu rõ các phương pháp tối ưu hóa thời khóa biểu, giảm thiểu xung đột lịch học và nâng cao hiệu quả sử dụng phòng học, tiết kiệm thời gian và nguồn lực.

  2. Nhà nghiên cứu và sinh viên ngành khoa học máy tính, công nghệ thông tin: Cung cấp kiến thức về giải thuật di truyền, lập trình song song trên kiến trúc Intel Xeon Phi, cũng như các kỹ thuật tối ưu hóa phức tạp.

  3. Chuyên gia phát triển phần mềm giáo dục: Tham khảo để phát triển các ứng dụng lập lịch thời khóa biểu hiệu quả, tích hợp các thuật toán metaheuristic và tận dụng phần cứng hiện đại.

  4. Nhà quản trị hệ thống HPC (High Performance Computing): Hiểu cách khai thác bộ đồng xử lý Intel Xeon Phi trong các bài toán thực tế, từ đó tối ưu hóa tài nguyên tính toán cho các ứng dụng tương tự.

Mỗi nhóm đối tượng có thể áp dụng kết quả nghiên cứu để cải tiến quy trình làm việc, nâng cao hiệu quả và chất lượng sản phẩm hoặc dịch vụ liên quan đến lập lịch và tối ưu hóa.

Câu hỏi thường gặp

  1. Giải thuật di truyền là gì và tại sao được chọn cho bài toán này?
    Giải thuật di truyền là phương pháp tối ưu hóa dựa trên mô phỏng quá trình tiến hóa tự nhiên, có khả năng tìm kiếm lời giải tốt trong không gian lớn và phức tạp. Nó phù hợp với bài toán sắp xếp thời khóa biểu do tính đa mục tiêu và nhiều ràng buộc phức tạp.

  2. Intel Xeon Phi có ưu điểm gì trong việc thực thi giải thuật?
    Intel Xeon Phi có kiến trúc nhiều nhân (hơn 50 nhân), hỗ trợ đa luồng và vector SIMD 512-bit, giúp thực thi song song hiệu quả các phép tính trên mảng lớn, giảm thời gian xử lý đáng kể so với CPU đơn.

  3. Các ràng buộc cứng và mềm trong bài toán được xử lý như thế nào?
    Ràng buộc cứng được đảm bảo tuyệt đối trong quá trình tạo và cải thiện cá thể bằng Local Search, còn ràng buộc mềm được tối ưu hóa để giảm thiểu vi phạm, nâng cao chất lượng thời khóa biểu.

  4. Tại sao cần áp dụng song song hóa trên Xeon Phi?
    Do không gian tìm kiếm lớn và số lượng phép tính nhiều, thực thi trên bộ xử lý đơn sẽ rất chậm. Song song hóa tận dụng nhiều nhân và luồng giúp giảm thời gian thực thi từ hàng giờ xuống còn vài phút hoặc giây.

  5. Giải thuật có thể áp dụng cho các trường đại học khác không?
    Có, giải thuật được thiết kế linh hoạt với dữ liệu đầu vào đa dạng và có thể điều chỉnh các ràng buộc phù hợp với từng trường, giúp mở rộng ứng dụng trong nhiều môi trường đào tạo khác nhau.

Kết luận

  • Đã hiện thực thành công giải thuật di truyền song song trên bộ đồng xử lý Intel Xeon Phi, giảm thời gian thực thi lên đến 20 lần với dữ liệu nhỏ và 4 lần với dữ liệu lớn.
  • Giải thuật đảm bảo các ràng buộc cứng và tối ưu hóa ràng buộc mềm, cho kết quả thời khóa biểu chất lượng tương đương các giải thuật tiên tiến khác.
  • Sử dụng cấu trúc MEM và Local Search giúp tránh tối ưu cục bộ và cải thiện chất lượng lời giải.
  • Kết quả thử nghiệm trên tập dữ liệu ITC-2007 với 19 bộ dữ liệu đầu vào đa dạng, chứng minh tính hiệu quả và khả năng ứng dụng thực tế.
  • Hướng phát triển tiếp theo bao gồm mở rộng sử dụng đa bộ đồng xử lý, tối ưu hàm lượng giá, kết hợp các heuristic khác và phát triển giao diện người dùng.

Đề nghị các nhà nghiên cứu và chuyên gia công nghệ thông tin tiếp tục khai thác và phát triển giải thuật này để nâng cao hiệu quả quản lý thời khóa biểu trong các cơ sở giáo dục đại học.