TAILIEUCHUNG - Ứng dụng khung làm việc Java Fork/Join thực thi một số thuật toán sắp xếp song song

Bài báo trình bày khung làm việc Java Fork/Join – một đặc điểm mới trong Java 7. Khung làm việc này thích hợp để giải quyết lớp bài toán sử dụng kỹ thuật đệ quy, trong đó các bài toán sau khi phân rã có kích thước tương đối nhỏ. | ỨNG DỤNG KHUNG LÀM VIỆC JAVA FORK/JOIN THỰC THI MỘT SỐ THUẬT TOÁN SẮP XẾP SONG SONG NGUYỄN LÊ TRUNG THÀNH NGUYỄN VĂN KHANG - ĐINH THỊ DIỆU MINH Trường Đại học Sư phạm – Đại học Huế Tóm tắt: Bài báo trình bày khung làm việc Java Fork/Join – một đặc điểm mới trong Java 7. Khung làm việc này thích hợp để giải quyết lớp bài toán sử dụng kỹ thuật đệ quy, trong đó các bài toán sau khi phân rã có kích thước tương đối nhỏ. Một trong những ưu điểm của khung làm việc Fork/Join là kỹ thuật work-stealing, kỹ thuật này tạo nên sự cân bằng về khối lượng các công việc thực hiện song song với chi phí đồng bộ hóa tương đối thấp. Khung làm việc Fork/Join được áp dụng để thực thi các thuật toán sắp xếp đệ quy tiêu biểu: sắp xếp trộn và sắp xếp nhanh. Kết quả được thể hiện qua thời gian thực hiện và hệ số tăng tốc của thuật toán song song. Từ khóa: khung làm việc Fork/Join, thuật toán work-stealing, sắp xếp trộn song song, sắp xếp nhanh song song 1. GIỚI THIỆU Ngôn ngữ Java đã hỗ trợ luồng (thread) và tương tranh (concurrency) từ rất sớm. Tuy nhiên, cho đến năm 1995 hầu hết các nền tảng phần cứng vẫn chưa hỗ trợ việc tính toán song song. Tại thời điểm đó, luồng chủ yếu được sử dụng cho những công việc có tính không đồng bộ thay vì những công việc có tính tương tranh. Theo thời gian, các hệ thống đa bộ vi xử lý ngày càng dễ tiếp cận hơn, các ứng dụng khai thác sức mạnh của tính toán song song trên hệ thống đa bộ vi xử lý cũng nhiều hơn. Lập trình viên nhận thấy rằng xây dựng chương trình song song trên nền tảng cũ trở nên khó khăn và dễ phát sinh lỗi. Mặc dù gói được bổ sung vào Java 5 hỗ trợ các thành phần hữu ích trong việc xây dựng các chương trình tương tranh: hàng đợi, thread pool., tuy nhiên những kỹ thuật này thích hợp cho việc giải quyết những bài toán mà sau khi được phân rã có kích thước tương đối lớn; các chương trình ứng dụng chỉ cần phân rã công việc của chúng sao cho số công việc tương tranh không ít hơn số lượng bộ vi xử lý hiện có. Tốc độ tính .

• Cơ sở dữ liệu
• Khung làm việc Java Fork Join
• Khung Java Fork Join
• Thuật toán sắp xếp song song
• Thuật toán work stealing
• Sắp xếp trộn song song
• Sắp xếp nhanh song song