Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Sắp xếp kết hợp song song với cân bằng tải
Tóm tắt
Sắp xếp kết hợp song song hữu ích cho việc sắp xếp một khối lượng lớn dữ liệu một cách tiến bộ. Phép sắp xếp kết hợp cần được song song hóa một cách cẩn thận vì thuật toán thông thường có hiệu suất kém do giảm dần số lượng bộ xử lý tham gia xuống một nửa, và chỉ còn một trong giai đoạn sáp nhập cuối cùng. Thuật toán sắp xếp kết hợp cân bằng tải được đề xuất sử dụng tất cả các bộ xử lý trong suốt quá trình tính toán. Nó phân phối đồng đều dữ liệu cho tất cả các bộ xử lý trong mỗi giai đoạn. Do đó, mỗi bộ xử lý đều bị buộc phải hoạt động trong tất cả các giai đoạn. Cải tiến hiệu suất đáng kể đã đạt được với khả năng gia tốc lên đến (P−1)/log P, trong đó P là số lượng bộ xử lý. Kết quả thí nghiệm cho thấy một khả năng gia tốc 9.6 (giới hạn trên là 10.7) trên 32 bộ xử lý Cray T3E khi sắp xếp 4 triệu số nguyên 32-bit, và khả năng gia tốc 2.3 (giới hạn trên là 2.8) trên cụm máy tính PC 8 nút.
Từ khóa
#sắp xếp kết hợp #song song #cân bằng tải #hiệu suất #bộ xử lýTài liệu tham khảo
K. Batcher, Sorting Networks and Their Applications, Proceedings of the AFIPS Spring Joint Computer Conference 32, Reston, VA, pp. 307-314 (1968).
Y. Kim, M. Jeon, D. Kim, and A. Sohn, Communication-Efficient Bitonic Sort on a Distributed Memory Parallel Computer, International Conference on Parallel and Distributed Systems (ICPADS'2001) (June 2001).
J. S. Huang and Y. C. Chow, Parallel Sorting and Data Partitioning by Sampling, Proceedings of 7th Computer Software and Applications Conference, pp. 627-631 (November 1983).
A. C. Dusseau, D. E. Culler, K. E. Schauser, and R. P. Martin, Fast Parallel Sorting under Log P: Experience with the CM-5, IEEE Transactions on Computers, Vol. 7 (August 1996).
S. J. Lee, M. Jeon, D. Kim, and A. Sohn, Partitioned Parallel Radix Sort, J. Parallel Distr. Comput. (JPDC), 62:656-668 (2002)also in 3rd International Symposium on High Performance Computing (ISHPC'2000), Tokyo, Japan, pp. 160–171 (October 2000).
A. Sohn and Yuetsu Kodama, Load Balanced Parallel Radix Sort, Proceedings of the 12th ACM International Conference on Supercomputing (July 1998).
R. Cole, Parallel Merge Sort, SIAM J. Comput., 17(4):770-785 (1998).
R. Hockney, Performance Parameters and Benchmarking of Supercomputers, Parallel Computing, 17(10/11):1111-1130 (December 1991).