Ứ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

Tạp chí Khoa học và Giáo dục, Trường Đại học Sư phạm Huế ISSN 1859-1612, Số 02(30)/2014: tr. 73-81 Ứ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 java.util.concurrent đượ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 toán của CPU không tăng nhiều trong khoảng 10 năm gần đây [3]. Để tăng tốc độ tính toán, thay vì tăng tốc độ xử lý của CPU, người ta thiết kế nhiều nhân (core) trên một chip. Với xu hướng đa nhân của phần cứng, vấn đề đặt ra là cần phải có một cơ chế song song thích hợp để giải quyết các bài toán sau khi được phân rã có kích thước tương đối nhỏ. Vấn đề trên được giải quyết bằng khung làm việc Fork/Join trên Java theo ý tưởng của Doug Lea [1]. Tác giả mô tả khung làm việc cho phép hỗ trợ lập trình song song, trong NGUYỄN LÊ TRUNG THÀNH và cs. 74 đó công việc ban đầu được phân rã thành những công việc nhỏ hơn và thực hiện tính toán song song trên những công việc này. Vì vậy, khung làm việc Fork/Join đã được đưa vào Java 7 nhằm để giải quyết các bài toán sau khi được phân rã có kích thước tương đối nhỏ một cách hiệu quả. 2. TỔNG QUAN VỀ KHUNG LÀM VIỆC FORK/JOIN Khung làm việc Fork/Join là sự thực thi của giao diện ExecutorService. Nó được thiết kế để giải quyết bài toán theo chiến lược “chia để trị”: 1. Phân rã (fork) bài toán ban đầu thành những bài toán con nhỏ hơn. 2. Thực thi các bài toán được phân rã bằng các luồng (tiếp tục phân rã bài toán nếu kích thước của nó chưa đủ nhỏ). 3. Chờ đợi và kết hợp (join) kết quả nhận được từ các bài toán con để có được kết quả của bài toán ban đầu. Khung làm việc Fork/Join phân phối công việc cho các luồng thực thi trong thread pool. Thread pool đã xuất hiện từ Java 5, tuy nhiên với khung làm việc Fork/Join ở Java 7, thread pool quản lý các luồng thực thi bằng thuật toán work-stealing. Thuật toán work- stealing được áp dụng trong Cilk [4] với ý tưởng là các luồng thực thi sau khi hoàn tất các công việc của mình có thể “lấy cắp” công việc của các luồng chưa hoàn tất công việc khác để thực hiện. Trung tâm của khung làm việc Fork/Join là lớp ForkJoinPool, một sự mở rộng của lớp AbstractExecutorService. ForkJoinPool trực tiếp thực hiện thuật toán “work-stealing” và chạy các thể hiện thực thi ForkJoinTask. Các đối tượng ForkJoinTask có 2 phương thức chính:  Phương thức fork(): cho phép ForkJoinTask hiện tại khởi động một ForkJoinTask mới  Phương thức join(): cho phép một ForkJoinTask chờ đợi sự hoàn tất của ForkJoinTask khác. Có 2 loại ForkJoinTask:  RecursiveAction: các thể hiện của RecursiveAction không trả về giá trị khi được thực thi.  RecursiveTask: các thể hiện của RecursiveTask trả lại giá trị khi được thực thi. 3. KỸ THUẬT WORK-STEALING Khung làm việc Fork/Join giảm tranh chấp công việc ở hàng đợi bằng kỹ thuật có tên work-stealing. Trong đó, mỗi luồng thực thi có một hàng đợi riêng. Hàng đợi này, có tên gọi là dequeue, có thể thao tác với các công việc ở cả 2 đầu của hàng đợi. Mỗi luồng thực hiện công việc được giao bằng cách phân rã thành các công việc nhỏ hơn. Sau khi phân rã, các công việc mới nhỏ hơn được thêm vào đầu của dequeue. Luồng lại tiếp tục ỨNG DỤNG KHUNG LÀM VIỆC JAVA FORK/JOIN... 75 lấy công việc ở đầu của dequeue để thực hiện. Việc bổ sung và lấy công việc tại đầu của dequeue được tiến hành theo nguyên tắc ngăn xếp (công việc nào được thêm vào sau cùng sẽ được lấy ra thực hiện đầu tiên). Sau một số lần lặp, các công việc nhỏ sẽ nằm phía trước hàng đợi, các công việc lớn hơn và chưa được phân chia sẽ nằm ở phía cuối hàng đợi. Với cách hoạt động như vậy, việc tranh chấp giữa các luồng được giảm đi đáng kể vì những nguyên nhân sau: 1. Mỗi luồng sẽ thực thi các công việc tại điểm đầu hàng đợi của nó. Nếu thực hiện xong các công việc của mình, nó sẽ truy cập vào điểm cuối hàng đợi của luồng khác để lấy công việc. Điều này làm cho xung đột sẽ không xảy ra ở điểm đầu của hàng đợi. 2. Việc “tranh chấp” nếu có xảy ra thì sẽ diễn ra ở cuối hàng đợi. Tuy nhiên, hiện tượng này xảy ra tương đối ít vì chỉ khi các luồng khác hoàn tất công việc của mình, chúng mới nhận công việc của luồng khác để thực thi. Các công việc ở cuối hàng đợi là các công việc có khối lượng lớn vì vậy nếu được giao cho một luồng nào đó, luồng này sẽ mất nhiều thời gian để xử lý công việc dẫn đến số lần giao tiếp của luồng này với các luồng khác được giảm xuống. Việc giảm tranh chấp xảy ra giữa các luồng dẫn đến việc giảm đáng kể chi phí đồng bộ hóa so với cách tiếp cận sử dụng thread pool. Kỹ thuật work-stealing tạo nên sự cân bằng trong thực hiện các công việc với chi phí đồng bộ hóa tương đối thấp. 4. SỬ DỤNG KHUNG LÀM VIỆC FORK/JOIN THỰC THI MỘT SỐ THUẬT TOÁN SẮP XẾP SONG SONG Với đặc thù của khung làm việc Fork/Join trên Java, nó thích hợp với lớp bài toán sử dụng kỹ thuật đệ quy, trong đó có các bài toán sắp xếp. Các thuật toán sắp xếp cũng là một phần quan trọng trong chương trình học của sinh viên khoa Tin học thông qua một số học phần bắt buộc như “Cấu trúc dữ liệu và giải thuật”, “Phân tích và thiết kế thuật toán”. Trong khuôn khổ chương trình, các thuật toán sắp xếp được giới thiệu cho sinh viên đều ở dạng thuật toán tuần tự. Nhóm tác giả áp dụng khung làm việc Fork/Join để thực thi một số thuật toán sắp xếp đệ quy tiêu biểu là sắp xếp trộn và sắp xếp nhanh với mục đích giới thiệu cho sinh viên các thuật toán sắp xếp dưới góc độ của lập trình song song, giúp sinh viên hình thành tư duy lập trình đa dạng và phong phú hơn. 4.1. Sắp xếp trộn song song (Parallel Merge Sort) Sắp xếp trộn là ví dụ điển hình của thuật toán sắp xếp sử dụng kỹ thuật đệ quy. Ý tưởng sắp xếp trộn là liên tiếp phân rã dữ liệu ban đầu cho đến khi còn một hoặc hai phần tử, sắp xếp rồi trộn chúng lại với nhau [5]. Thuật toán sắp xếp trộn song song được thực hiện như sau: 1. Nếu kích thước của dữ liệu ban đầu (thường là mảng) nhỏ hơn ngưỡng xác định, thực hiện sắp xếp theo thuật toán sắp xếp trộn tuần tự. NGUYỄN LÊ TRUNG THÀNH và cs. 76 2. Nếu kích thước của mảng lớn hơn ngưỡng xác định, chia mảng làm hai phần, thực hiện việc sắp xếp trên từng phần một cách song song. 3. Sau khi từng phần được sắp xếp, thực hiện việc trộn hai phần đó để được mảng gộp được sắp xếp. Khung làm việc Fork/Join thích hợp cho việc thực thi thuật toán sắp xếp trộn song song: tại mỗi bước, việc sắp xếp từng nửa của mảng được thực hiện song song. Dưới đây là một phần đoạn mã của thuật toán: protected void compute() { if (start >= end) { return; } else if (end - start < threshold) { MergeSort.sequentialSort(array, start, end); } else { int middle = start + (end-start) /2; MergeSortAction worker1 = new MergeSortAction(array, start, middle, threshold); MergeSortAction worker2 = new MergeSortAction(array, middle + 1, end, threshold); invokeAll(worker1, worker2); merge(middle); } } Trong đó, lớp MergeSortAction là mở rộng của lớp RecursiveAction. Hàm tạo MergeSortAction(array, start, end, threshold) khi được gọi sẽ thực thi phương thức compute() thực hiện sắp xếp mảng array từ chỉ số start đến chỉ số end. Nếu kích thước của mảng nhỏ hơn một ngưỡng xác định (threshold) thì mảng được sắp xếp trực tiếp bằng thuật toán sắp xếp trộn tuần tự qua lời gọi phương thức sequentialSort(array, start, end). Nếu kích thước mảng lớn hơn ngưỡng, công việc được chia làm hai: thể hiện worker1 của lớp MergeSortAction chịu trách nhiệm sắp xếp nửa bên trái của mảng, thể hiện worker2 chịu trách nhiệm sắp xếp nửa còn lại. Hai công việc được tiến hành song song qua lời gọi invokeAll(worker1, worker2). Phương thức invokeAll bao gồm việc phân chia công việc (phương thức fork()) cho worker1, worker2 và chờ đợi cho đến khi worker1, worker2 hoàn tất công việc (phương thức join()). Sau khi từng phần công việc được hoàn tất, các kết quả được trộn lại một cách tuần tự qua lời gọi phương thức merge(middle). Để sắp xếp mảng ban đầu, tác vụ task được tạo ra và thực thi thông qua đối tượng ForkJoinPool: public void parallelMergeSort(int[] array) { ỨNG DỤNG KHUNG LÀM VIỆC JAVA FORK/JOIN... 77 ForkJoinPool pool = new ForkJoinPool(); MergeSortAction task = new MergeSortAction(array, 0, array.length-1, array.length/Runtime.getRuntime().availableProcessors()); pool.invoke(task); } Thời gian thực hiện của thuật toán sắp xếp trộn tuần tự và sắp xếp trộn song song trên mảng các số nguyên được sinh ngẫu nhiên, kích thước mảng từ 2000000 đến 20000000 được thể hiện qua hình 1 và hình 2. Thuật toán lần lượt chạy trên hệ thống 2 nhân và 4 nhân với thông tin cụ thể: (2 nhân) Pentium(R) Dual-Core CPU E5700@ 3.00GHz 3.00GHz 1.96 GB of RAM, 32-bit Operating System; (4 nhân) Intel(R) Core(TM) i7- 3820QM CPU @ 2.70Ghz 2.70GHz, 12.0 GB of RAM, 64-bit Operating System, x64- based processor, được cài đặt trên môi trường phát triển tích hợp Eclipse Juno. Hình 1. Sắp xếp trộn tuần tự, sắp xếp trộn song song trên hệ thống 2 nhân và 4 nhân Hệ số tăng tốc (speedup) của chương trình song song được tính bằng thương số của thời gian thực hiện tuần tự và thời gian thực hiện song song trên p nhân [2]. Hệ số tăng tốc cho thấy sự gia tăng về tốc độ thực hiện chương trình. Thông thường, trường hợp lý tưởng là hệ số tăng tốc bằng số lượng nhân đang sử dụng, tuy nhiên trường hợp lý tưởng này hầu như hiếm khi xảy ra [2]. Kết quả cho thấy rằng hệ số tăng tốc của thuật toán sắp xếp trộn song song xấp xỉ 1,5 trên hệ thống 2 nhân và hệ số tăng tốc xấp xỉ 2,7 trên hệ thống 4 nhân. Đối với thuật toán sắp xếp trộn, bước trộn các kết quả được sắp xếp được thực hiện tuần tự và bước này chiếm khá nhiều thời gian (về lý thuyết là O(n) với n là kích thước của mảng) . Nếu bước trộn được thực hiện song song, kết quả thu được sẽ tốt hơn. Tuy vậy kết quả thu được ở trên là đáng ghi nhận và mở ra khả năng cho những cải tiến khác nhằm tăng tốc độ thực hiện thuật toán nhanh hơn nữa. NGUYỄN LÊ TRUNG THÀNH và cs. 78 Hình 2. Hệ số tăng tốc (speedup) của sắp xếp trộn song song trên hệ thống 2 nhân và 4 nhân 4.2. Sắp xếp nhanh song song (Parallel Quicksort) Ý tưởng của thuật toán sắp xếp nhanh là chọn ra phần tử chốt (pivot), đưa các phần tử nhỏ hơn phần tử chốt về một phía và các phần tử lớn hơn về một phía, sau đó tiếp tục thực hiện sắp xếp trên từng phần [5]. Thuật toán sắp xếp nhanh song song được thực hiện như sau: 1. Chọn phần tử chốt. 2. Phân chia dữ liệu thành từng phần gồm các phần tử bé hơn phần tử chốt, phần tử chốt, các phần tử lớn hơn phần tử chốt 3. Nếu kích thước của mảng bé hơn ngưỡng xác định, thực hiện thuật toán theo sắp xếp nhanh tuần tự 4. Nếu kích thước của mảng bé hơn ngưỡng xác định, thực hiện song song: a. Sắp xếp nhanh trên các phần tử bé hơn phần tử chốt b. Sắp xếp nhanh trên các phần tử lớn hơn phần tử chốt Thuật toán sắp xếp nhanh được thực hiện thông qua phương thức compute() thuộc lớp QuickSortAction - là mở rộng của lớp RecursiveAction. Phương thức compute() được thực thi khi hàm tạo QuickSortAction(array, start, end, threshold) được gọi. protected void compute() { if (start < end) { int pivot = QuickSort.partition(array, start, end); if (end - start < threshold) { ỨNG DỤNG KHUNG LÀM VIỆC JAVA FORK/JOIN... 79 QuickSort.sequentialSort(array, start, end); } else { QuickSortAction worker1 = new QuickSortAction(array, start, pivot – 1, threshold); QuickSortAction worker2 = new QuickSortAction(array, pivot + 1, end, threshold); invokeAll(worker1, worker2); } } } Phần tử chốt pivot được chọn thông qua phương thức partition(array, start, end) của lớp QuickSort được thiết kế để sắp xếp nhanh tuần tự. Nếu kích thước của mảng nhỏ hơn ngưỡng (threshold) thì thực hiện sắp xếp nhanh tuần tự bằng lời gọi phương thức sequentialSort(array, start, end). Ngược lại, nếu kích thước của mảng lớn hơn ngưỡng, công việc đưa chia làm hai: thể hiện worker1 của lớp QuickSortAction (là mở rộng của lớp RecursiveAction) thực hiện việc sắp xếp từ đầu mảng đến phần tử chốt, thể hiện worker2 thực hiện việc sắp xếp từ phần tử chốt đến cuối mảng. Công việc được thực hiện song song thông qua lời gọi invokeAll(worker1, worker2). Việc sắp xếp mảng ban đầu thể hiện qua tác vụ task và được thực thi bằng lời gọi invoke(task) thông qua thể hiện pool của lớp ForkJoinPool: private void parallelQuickSort(int[] array) { QuickSortAction task = new QuickSortAction(array, 0, array.length – 1, array.length / Runtime.getRuntime().availableProcessors()); ForkJoinPool pool = new ForkJoinPool(); pool.invoke(task); } Kết quả thuật toán sắp xếp nhanh song song thực hiện trên các mảng số nguyên ngẫu nhiên với kích thước từ 2000000 đến 20000000 được thể hiện ở hình 3 và hình 4. NGUYỄN LÊ TRUNG THÀNH và cs. 80 Hình 3. Sắp xếp nhanh tuần tự, sắp xếp nhanh song song trên hệ thống 2 nhân và 4 nhân Hình 4. Hệ số tăng tốc (speedup) của sắp xếp nhanh song song trên hệ thống 2 nhân và 4 nhân Từ kết quả trên, có thể nhận thấy sắp xếp nhanh song song tương đối hiệu quả với hệ số tăng tốc xấp xỉ 1,6 đối với hệ thống 2 nhân và hệ số tăng tốc xấp xỉ 3,5 đối với hệ thống 4 nhân. Kết quả trên tương đối tích cực khi hệ số tăng tốc của thuật toán sắp xếp nhanh song song cao hơn so với sắp xếp trộn song song. Trong thuật toán sắp xếp nhanh song song, thủ tục phân chia mảng theo phần tử chốt được thực hiện tuần tự và có độ phức tạp về lý thuyết là O(n), với n là kích thước của mảng. Tốc độ thực hiện thuật toán sắp xếp nhanh song song sẽ được tăng thêm khi thủ tục phân chia mảng theo phần tử chốt được thực hiện song song. ỨNG DỤNG KHUNG LÀM VIỆC JAVA FORK/JOIN... 81 5. KẾT LUẬN Bài báo trình bày khung làm việc Fork/Join trong Java 7, nhóm tác giả đã ứng dụng khung làm việc này để thực thi các thuật toán sắp xếp song song: sắp xếp trộn và sắp xếp nhanh. Thuật toán được nhóm tác giả cài đặt trên môi trường phát triển tích hợp Eclipse Juno và tiến hành đánh giá lần lượt trên hệ thống 2 nhân và 4 nhân. Kết quả đánh giá cho thấy sắp xếp trộn có hệ số tăng tốc xấp xỉ 1,5 trên hệ thống 2 nhân và xấp xỉ 2,7 trên hệ thống 4 nhân; sắp xếp nhanh có hệ số tăng tốc xấp xỉ 1,6 trên hệ thống 2 nhân và xấp xỉ 3,5 trên hệ thống 4 nhân. Kết quả thu được phần nào khẳng định sự hiệu quả của khung làm việc Fork/Join. Các thuật toán sắp xếp trên sẽ tiếp tục được nghiên cứu theo hướng song song hóa các thủ tục tuần tự còn tồn tại nhằm cải thiện hơn nữa tốc độ thực thi. TÀI LIỆU THAM KHẢO [1] D. Lea (2000). A Java Fork/Join framework, In Proceedings of the ACM 2000 conference on Java Grande, pages 36–43, New York. [2] Grossman D. (2012). A sophomoric introduction to shared-memory parallelism and concurrency, Lecture notes, University of Washington. [3] Herb Sutter (2005). The Concurrency Revolution, C/C++ Users Journal, 23(2). [4] Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, Yuli Zhou (1996). Cilk: An Efficient Multithreaded Runtime System. J. Parallel Distributed Computing, 37(1): pages 55-69. [5] T. H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein (2009). Introduction to Algorithms, Third Edition, MIT Press. Title: IMPLEMENTATION OF PARALLEL SORTING ALGORITHMS USING JAVA FORK/JOIN FRAMEWORK Abstract: This article presents a Java Fork/Join framework, which is a new feature in Java 7. This framework was designed to efficiently execute divide-and-conquer algorithms, which recursively divide problems into fine-grained sub-problems. One of the advantages of Fork/Join framework is work-stealing technique, which produces reasonable load balancing with no central coordination and minimal synchronization costs. This framework was applied for implementing two specific recursive sorting algorithms: merge sort and quicksort. The results were presented through running time and speedup of these algorithms. Keywords: Fork/Join framework, work-stealing algorithm, parallel merge sort, parallel quicksort ThS. NGUYỄN LÊ TRUNG THÀNH ThS. NGUYỄN VĂN KHANG ThS. ĐINH THỊ DIỆU MINH Khoa Tin học, Trường Đại học Sư phạm – Đại học Huế