Đề tài: Tìm hiểu tính toán song song hóa thuật toán và ứng dụng song song bài toán sắp xếp theo giỏ (bucket sort)

Bốn thập kỷ qua chứng kiến sự phát triển bùng nổ về sức mạnh máy tính, tạo tiền đề cho những bước tiến chưa từng thấy về phát minh, năng suất lao động và phúc lợi cho con người. Nhưng quá trình đó giờ đây đứng trước một trở ngại mà ít ai nghĩ đến: sự kết thúc của quá trình mở rộng sức mạnh điện toán. Ngành tin học đã đạt đến giới hạn của những gì từng khả thi với một hay hai vi xử lý trung tâm hoạt động theo chuỗi truyền thống (serial processing). Ngành nào vẫn dựa vào mô hình đó...
Nội dung trích xuất từ tài liệu:
Đề tài: Tìm hiểu tính toán song song hóa thuật toán và ứng dụng song song bài toán sắp xếp theo giỏ (bucket sort) Nội dung: Tìm hiểu tính toán song song hóa thuật toán và ứng dụng song song bài toán sắp xếp theo giỏ (bucket sort) MỤC LỤC TÀI LIỆU THAM KHẢO........................................................................................ 15 2 Phần I: MỞ ĐẦU Bốn thập kỷ qua chứng kiến sự phát triển bùng nổ về sức mạnh máy tính, tạo tiền đề cho những bước tiến chưa từng thấy về phát minh, năng suất lao động và phúc lợi cho con người. Nhưng quá trình đó giờ đây đứng trước một trở ngại mà ít ai nghĩ đến: sự kết thúc của quá trình mở rộng sức m ạnh điện toán. Ngành tin học đã đạt đến giới hạn của những gì từng khả thi với một hay hai vi xử lý trung tâm hoạt động theo chuỗi truy ền thống (serial processing). Ngành nào vẫn dựa vào mô hình đó để tiếp tục phát tri ển năng suất, tăng trưởng kinh tế và phát triển xã hội thì cần ph ải bắt đ ầu m ột b ước nhảy mới vào điện toán xử lý song song (parallel processing). Ngày nay, với các bài toán yêu cầu xử lý trên một số lượng d ữ li ệu l ớn và phức tạp như sự mô phỏng những hệ thống phức tạp và những vấn đề thách thức lớn như: dự báo thời tiết và khí h ậu, nh ững phản ứng hoá h ọc và hạt nhân, hệ gen sinh học, ... đặt ra một nhu cầu lớn v ề t ốc đ ộ tính toán. Những bài toán này thường yêu cầu một lượng lớn các phép tính lặp lại trên một khối lượng lớn dữ liệu để đưa ra một kết quả đúng đắn, và các phép tính này cần hoàn thành trong khoảng thời gian h ợp lý. Ví d ụ nh ư bài toán d ự bào thời tiết không thể xử lý bằng các máy tính thông thường vì th ời gian xử lý là khoảng 10 năm, điều này hoàn toàn không phù hợp. Đề giải quyết được các bài toán trên ta cần phải tăng tốc độ tính toán. Mặc dù trong những thập kỷ vừa qua chúng ta đã được chứng ki ến nh ững thành tựu to lớn về công nghệ vi xử lý. Tốc độ đồng hồ của các b ộ x ử lý đã tăng từ khoảng 40MHz (MIPS R3000, circa 1988) tới trên 2,0 GHz (Pentium 4, circa 2002); cùng một lúc các bộ xử lý có khả năng thực hiện đa ch ỉ l ệnh trong cùng một chu kỳ ... nhưng do giới hạn về vật lý nên kh ả năng tính toán của các bộ xử lý không thể tăng mãi được. Minh họa một cách đơn giản, tính toán truy ền thống gi ống nh ư vi ệc một người đọc bài văn theo kiểu tuần tự từ đầu đến cu ối, còn tính toán song song thì giống như tách bài văn đó thành các phần và cho nhiều người khác nhau cùng đọc một lúc để có kết quả nhanh hơn. Tính toán song song mang lại một nền tảng mới cho sự phát triển của công nghệ xử lý. Đây là một hướng đi mới, đúng đắn và hiệu quả cho công nghệ điện toán trong tương lai. Bài viết sau đây về đề tài “Tìm hiểu về tính toán song song , áp d ụng gi ải quyết một số bài toán” phần nào thể hiện được nh ững kiến thức cơ b ản đ ầu tiên về tính toán song song, tính đúng đắn và ứng dụng của nó. Phần II: NỘI DUNG I. Những khái niệm cơ bản về tính toán song song 1. Nhu cầu tính toán hiệu năng cao và tính khả dụng của tính toán song song. a. Nhu cầu tính toán song song Ví dụ 1: Oregon State University: Mô phỏng các dòng chảy lưu thông của đ ại dương --> xác định nguyên nhân gây trái đất đang nóng dần lên. - Phân chia đại dương thành: • 4096 vùng từ đông sang tây. • 1024 vùng từ bắc sang nam. • 12 tầng biển. • Xấp sỉ 50 triệu khối trong không gian 3 chiều. - Mô phỏng lưu thông thực hiện ~ 30 tỷ phép tính trong 10 phút. Công việc này thực hiện liên tục trong năm. Ví dụ 2: Dự báo thời tiết (weather forecasting): - Chia bầu khí quyển theo không gian 3 chiều, mỗi khối kích thước 1mile x 1mile x 1mile. - Ước tính khoảng 5x10^8 khối (cells). - Trên mỗi khối cần thực hiện ~ 200 phép toán -> cần thực hiện ~ 10^11 phép toán. - Nếu cần dự báo cho 1 tuần, chu kỳ 1 phút -> c ần th ực hi ện 10^4 l ần, mỗi lần 10^11phép toán. - Siêu máy tính có thể thực hiện: 10^9 phép toán trên 1 giây -> c ần 10^6 giây ~ 10 ngày để thực hiện. Ví dụ 3: Mô phỏng tương tác của các protein với phân tử nước (Levin 1990): - Thực hiện trên máy Cray X/MP (~800 triệu phép toán / 1 giây): đ ể mô phỏng 10^-12 giây phản ứng protein cần 1 giờ thực hiện. - Nếu mô phỏng một phản ứng thực sự trên cùng máy Cray X/MP cần 31,688 năm. TÓM LẠI: Yêu cầu về thực nghiệm nghiên cứu, mô phỏng -> giải quy ết nh ững bài toán có khối lượng tính toán lớn trong một khoảng th ời gian chấp nh ận được. Phương hướng giải quyết vấn đề: - Thực hiện trên các siêu máy tính mạnh. - Thực hiện phân chia công việc thực hiện song song trên hệ thống các máy tính Tính khả dụng của tính toán song song SIÊU MÁY TÍNH: Khả năng tính toán phụ thuộc nhiều vào tốc độ xử lý của CPU -> phụ thuộc vào cấu trúc và số lượng transistors ch ứa trong CPU –> Có những giới hạn nhất định về kích thước, nhiệt độ -> không th ể tăng s ố transistors lên mãi được THỰC HIỆN SONG SONG: Nguyên tắc: thực hiện phân chia công việc chính thành các công việc con, có thể thực hiện song song với nhau. Xây dựng hệ thống song song từ nhiều bộ xử lý riêng biệt. Th ực hi ện các công việc song song trên các bộ xử lý đó. Vấn đề: - Phương pháp phân chia công việc. - Môi trường hỗ trợ thực hiện song song. Ví dụ: Xếp sách trong thư viện Sách trong thư viện được phân loại theo chữ cái đầu tiên và sắp xếp theo thứ tự. Sách cùng nhóm được xếp trên cùng một giá. Các giá đặt trong các tủ sách. Thư viện nhập một số lượng sách lớn -> yêu cầu thủ th ư phải s ắp x ếp sách theo đúng nguyên tắc. Cách giải quyết hiệu quả nhất? + Nếu chỉ có 1 thủ thư - Cách thứ nhất: Lấy từng cuốn sách rồi sắp xếp vào vị trí thích h ợp -> không hiệu quả. - Cách thứ hai: Sắp xếp các cuốn sách theo th ứ t ự trước rồi man ...