Ứ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

ỨNG DỤNG KHUNG LÀM VIỆC JAVA FORK/JOIN THỰC THI<br /> MỘT SỐ THUẬT TOÁN SẮP XẾP SONG SONG<br /> NGUYỄN LÊ TRUNG THÀNH<br /> NGUYỄN VĂN KHANG - ĐINH THỊ DIỆU MINH<br /> Trường Đại học Sư phạm – Đại học Huế<br /> 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<br /> 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<br /> sử dụng kỹ thuật đệ quy, trong đó các bài toán sau khi phân rã có kích thước<br /> tương đối nhỏ. Một trong những ưu điểm của khung làm việc Fork/Join là kỹ<br /> 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<br /> công việc thực hiện song song với chi phí đồng bộ hóa tương đối thấp.<br /> Khung làm việc Fork/Join được áp dụng để thực thi các thuật toán sắp xếp<br /> đệ 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<br /> thời gian thực hiện và hệ số tăng tốc của thuật toán song song.<br /> Từ khóa: khung làm việc Fork/Join, thuật toán work-stealing, sắp xếp trộn<br /> song song, sắp xếp nhanh song song<br /> <br /> 1. GIỚI THIỆU<br /> Ngôn ngữ Java đã hỗ trợ luồng (thread) và tương tranh (concurrency) từ rất sớm. Tuy<br /> 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<br /> 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<br /> không đồng bộ thay vì những công việc có tính tương tranh.<br /> 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<br /> 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<br /> 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ũ<br /> 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<br /> 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:<br /> 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<br /> 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<br /> ứ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<br /> ít hơn số lượng bộ vi xử lý hiện có.<br /> 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<br /> 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)<br /> 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ơ<br /> 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<br /> tương đối nhỏ.<br /> 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<br /> 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<br /> <br /> Tạp chí Khoa học và Giáo dục, Trường Đại học Sư phạm Huế<br /> ISSN 1859-1612, Số 02(30)/2014: tr. 73-81<br /> <br /> NGUYỄN LÊ TRUNG THÀNH và cs.<br /> <br /> 74<br /> <br /> đó 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<br /> toán song song trên những công việc này.<br /> 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<br /> toán sau khi được phân rã có kích thước tương đối nhỏ một cách hiệu quả.<br /> 2. TỔNG QUAN VỀ KHUNG LÀM VIỆC FORK/JOIN<br /> Khung làm việc Fork/Join là sự thực thi của giao diện ExecutorService. Nó được thiết<br /> kế để giải quyết bài toán theo chiến lược “chia để trị”:<br /> 1. Phân rã (fork) bài toán ban đầu thành những bài toán con nhỏ hơn.<br /> 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<br /> kích thước của nó chưa đủ nhỏ).<br /> 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<br /> quả của bài toán ban đầu.<br /> 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.<br /> Thread pool đã xuất hiện từ Java 5, tuy nhiên với khung làm việc Fork/Join ở Java 7,<br /> thread pool quản lý các luồng thực thi bằng thuật toán work-stealing. Thuật toán workstealing đượ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<br /> 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<br /> việc khác để thực hiện.<br /> 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<br /> AbstractExecutorService. ForkJoinPool trực tiếp thực hiện thuật toán “work-stealing”<br /> và chạy các thể hiện thực thi ForkJoinTask. Các đối tượng ForkJoinTask có 2 phương<br /> thức chính:<br />  Phương thức fork(): cho phép ForkJoinTask hiện tại khởi động một ForkJoinTask<br /> mới<br />  Phương thức join(): cho phép một ForkJoinTask chờ đợi sự hoàn tất của<br /> ForkJoinTask khác.<br /> Có 2 loại ForkJoinTask:<br />  RecursiveAction: các thể hiện của RecursiveAction không trả về giá trị khi được<br /> thực thi.<br />  RecursiveTask: các thể hiện của RecursiveTask trả lại giá trị khi được thực thi.<br /> 3. KỸ THUẬT WORK-STEALING<br /> 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<br /> work-stealing. Trong đó, mỗi luồng thực thi có một hàng đợi riêng. Hàng đợi này, có<br /> 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<br /> 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<br /> 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<br /> <br /> ỨNG DỤNG KHUNG LÀM VIỆC JAVA FORK/JOIN...<br /> <br /> 75<br /> <br /> 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<br /> 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<br /> 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<br /> 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<br /> hàng đợi.<br /> 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ì<br /> những nguyên nhân sau:<br /> 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<br /> 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<br /> 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<br /> hàng đợi.<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> tiếp của luồng này với các luồng khác được giảm xuống.<br /> 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ộ<br /> 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<br /> 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.<br /> 4. SỬ DỤNG KHUNG LÀM VIỆC FORK/JOIN THỰC THI MỘT SỐ THUẬT TOÁN<br /> SẮP XẾP SONG SONG<br /> 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ử<br /> 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à<br /> 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<br /> 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<br /> 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<br /> 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 để<br /> 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<br /> 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<br /> song, giúp sinh viên hình thành tư duy lập trình đa dạng và phong phú hơn.<br /> 4.1. Sắp xếp trộn song song (Parallel Merge Sort)<br /> 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<br /> 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ử,<br /> 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<br /> hiện như sau:<br /> 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,<br /> thực hiện sắp xếp theo thuật toán sắp xếp trộn tuần tự.<br /> <br /> NGUYỄN LÊ TRUNG THÀNH và cs.<br /> <br /> 76<br /> <br /> 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<br /> hiện việc sắp xếp trên từng phần một cách song song.<br /> 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<br /> gộp được sắp xếp.<br /> 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:<br /> 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à<br /> một phần đoạn mã của thuật toán:<br /> protected void compute() {<br /> if (start >= end) {<br /> return;<br /> } else if (end - start < threshold) {<br /> MergeSort.sequentialSort(array, start, end);<br /> } else {<br /> int middle = start + (end-start) /2;<br /> MergeSortAction worker1 = new MergeSortAction(array,<br /> start, middle, threshold);<br /> MergeSortAction worker2 = new MergeSortAction(array,<br /> middle + 1, end, threshold);<br /> invokeAll(worker1, worker2);<br /> merge(middle);<br /> }<br /> }<br /> <br /> Trong đó, lớp MergeSortAction là mở rộng của lớp RecursiveAction. Hàm tạo<br /> MergeSortAction(array, start, end, threshold) khi được gọi sẽ thực thi phương thức<br /> 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<br /> 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<br /> 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,<br /> 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<br /> 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ể<br /> 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<br /> song qua lời gọi invokeAll(worker1, worker2). Phương thức invokeAll bao gồm việc<br /> phân chia công việc (phương thức fork()) cho worker1, worker2 và chờ đợi cho đến khi<br /> 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<br /> đượ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<br /> merge(middle).<br /> Để 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<br /> ForkJoinPool:<br /> public void parallelMergeSort(int[] array) {<br /> <br /> ỨNG DỤNG KHUNG LÀM VIỆC JAVA FORK/JOIN...<br /> <br /> 77<br /> <br /> ForkJoinPool pool = new ForkJoinPool();<br /> MergeSortAction task = new MergeSortAction(array, 0,<br /> array.length-1,<br /> array.length/Runtime.getRuntime().availableProcessors());<br /> pool.invoke(task);<br /> }<br /> <br /> 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<br /> mảng các số nguyên được sinh ngẫu nhiên, kích thước mảng từ 2000000 đến 20000000<br /> đượ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<br /> nhân với thông tin cụ thể: (2 nhân) Pentium(R) Dual-Core CPU E5700@ 3.00GHz<br /> 3.00GHz 1.96 GB of RAM, 32-bit Operating System; (4 nhân) Intel(R) Core(TM) i73820QM CPU @ 2.70Ghz 2.70GHz, 12.0 GB of RAM, 64-bit Operating System, x64based processor, được cài đặt trên môi trường phát triển tích hợp Eclipse Juno.<br /> <br /> 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<br /> <br /> 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<br /> 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<br /> 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ý<br /> 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<br /> 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<br /> 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ệ<br /> 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<br /> 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à<br /> 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<br /> 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<br /> tiến khác nhằm tăng tốc độ thực hiện thuật toán nhanh hơn nữa.<br /> <br />