NGHIÊN CỨU QUY TRÌNH SONG SONG TRONG YEAST VÀ XÂY DỰNG CÁC ỨNG DỤNG SONG SONG CHO Thuật toán hình thành chất lỏng TRÊN BỀ MẶT. Đề tài nghiên cứu “Nghiên cứu xử lý song song trong GIS và xây dựng ứng dụng song song các thuật toán ước tính dòng chảy bề mặt” được thực hiện và hoàn thành tại Phòng Kỹ thuật - Trung tâm Ứng dụng Hệ thống Thông tin Địa lý - Sở Khoa học và Công nghệ Thành phố Hồ Chí Minh.
MỞ ĐẦU
Tính cấp thiết của đề tài
Vì những lý do trên, tôi đã đề xuất cho dự án của mình một phương pháp tính toán song song tích lũy dòng chảy cho hệ thống thoát nước được xây dựng từ DEM lớn. Đề tài: “Nghiên cứu xử lý song song trong GIS và phát triển ứng dụng song song hóa thuật toán dòng chảy bề mặt”.
Mục tiêu nghiên cứu của đề tài
Đối tƣợng và phạm vi nghiên cứu
- Đối tƣợng nghiên cứu
- Phạm vi nghiên cứu
TỔNG QUAN VỀ THUẬT TOÁN VÀ TÍNH TOÁN SONG SONG
Đại cƣơng về tính toán song song
- Một số khái niệm và thuật ngữ
- Các mức độ song song (Level of parallelism)
- Phân loại các kiến trúc song song
- Mô hình SIMD (PRAM)
- Dùng công nghệ EREW mô phỏng các kiến trúc CRCW, CREW
- Họ máy MIND
- Hệ đa xử lý với bộ nhớ phân tán (Multi processor system with
- Hệ đa xử lý với bộ nhớ dùng chung phân tán (Multi processor
- Ngôn ngữ mô tả thuật toán song song
Do cách bộ xử lý thực thi đồng thời nên thời gian thực hiện song song: O(1). Giao tiếp giữa các bộ xử lý được thực hiện thông qua bộ nhớ dùng chung.
Các mô hình tính toán song song và minh họa
- Mô hình cây nhị phân (Bimary Tree Model)
- Mô hình mạng
- Thuật toán k-cube-Min
- Thuật toán song song tính tích ma trận
- Đánh giá hiệu quả của thuật toán song song
Trong khoảng thời gian từ đến, phép cộng được thực hiện bởi bộ xử lý 1. Như vậy phép cộng 8 số sử dụng 4 bộ xử lý có thể hoàn thành sau 3 đơn vị thời gian. Giả sử chúng ta có một thuật toán song song để giải bài toán đó với thời gian tính toán Tp và bộ xử lý P.
Thời gian tính toán tuần tự được định nghĩa là thời gian tính toán của thuật toán song song khi nó được chạy trên bộ xử lý máy tính song song. Điều này cho phép phân tích hiệu quả của thuật toán khi số lượng bộ xử lý tăng lên. Thời gian tính toán nhanh nhất của thuật toán tuần tự trên bộ xử lý máy tính song song được sử dụng.
Tính toán song song trong .NET và minh họa
- Task
- Vòng lặp song song (Parallel Loops)
- Parallel LINQ
Như đã trình bày ở trên, mô hình lập trình song song sẽ chia chương trình thành các nhiệm vụ nhỏ (Tasks). Mỗi tác vụ khi được khai báo và khởi tạo sẽ được máy tính thực hiện song song trong cùng một thời điểm. Chúng ta cũng có thể buộc một Tác vụ chạy sau khi tất cả các tác vụ khác đã hoàn thành hoặc đợi một thời gian bằng cách sử dụng phương thức Task.Wait();.
Mô hình lập trình song song sử dụng vòng lặp song song để khắc phục nhược điểm của lập trình tuần tự như đã nêu ở trên. Các vòng lặp ở đây sẽ được CPU thực thi đồng thời, giúp tăng hiệu suất hoạt động của máy tính, tính toán và giảm thời gian hệ thống. Tuy nhiên, chúng ta không được hiểu lầm rằng các vòng lặp này sẽ được thực hiện tuần tự. Việc thực thi song song được thực hiện bởi trình biên dịch và CPU.
Thuật toán Floyd – Warshall và bài toán tìm đƣờng đi ngắn nhất giữa mọi
Cấu trúc lệnh trên khá giống với cấu trúc lệnh của lập trình tuần tự. LINQ song song được gọi là LINQ thông thường, nhưng điểm khác biệt là việc thực hiện song song các truy vấn LINQ tới cơ sở dữ liệu. Thuật toán Floyd-Warshall và bài toán tìm đường đi ngắn nhất giữa mỗi cặp đỉnh của đồ thị.
Dựa vào thuật toán trên tôi áp dụng thuật toán tìm dòng tích lũy cho bài toán của mình.
DỮ LIỆU, NỘI DUNG VÀ PHƢƠNG PHÁP NGHIÊN CỨU
Dữ liệu
- Mô hình dữ liệu DEM
- File text độ cao
Trong phần Raster input nhấn chọn dữ liệu DEM cần điều chỉnh. Sau đó bấm vào phần đầu ra raster bề mặt và chọn vị trí lưu dữ liệu DEM đã điều chỉnh và đặt tên cho nó. Mỗi pixel trong mô hình dữ liệu DEM cung cấp cho chúng ta độ cao kỹ thuật số của lưu vực tại thời điểm đó.
Và để đạt được chiều cao đó, chúng ta sẽ sử dụng công cụ Raster to ASCII trong hộp công cụ Arc của ArcGis. Ngoài phần đầu ra của file raster ASCII, chúng ta còn click chọn vị trí lưu dữ liệu độ cao dưới dạng file văn bản và đặt tên cho nó. Các con số bên dưới mô tả chiều cao của DEM tại mỗi vị trí và được phân tách bằng dấu cách.
Thuật toán định dòng chảy trên bề mặt địa hình
- Giới thiệu thuật toán phân tích dòng chảy D8
- Xác định hƣớng dòng chảy
- Tính toán sự tích lũy dòng chảy
- Giới thiệu các công cụ tìm dòng trong ArcGIS
- ArcSWAT
- Bộ công cụ tìm dòng chảy tích lũy trong ArcGIS
Sự tích lũy dòng chảy cho một ô nhất định trong khu vực trong mô hình DEM được xác định bằng cách tính tổng số ô lưới tập trung nước trong ô đó theo hướng dòng chảy. Tiếp tục với ví dụ trước, khi đã tính được hướng của từng ô, công việc tính toán tích lũy dòng chảy trở nên đơn giản hơn, cộng tất cả các ô dòng chảy ta có kết quả như bảng 3.2.1.2. Các dòng chảy và lưu vực mặc định: sử dụng mạng lưới dòng chảy và tiểu lưu vực hiện có.
Hoàn tất quá trình khoanh vùng lưu vực, nhấn nút Thoát để hoàn thành toàn bộ quá trình khoanh vùng lưu vực và xem kết quả. Nhận xét: Việc thực hiện tính toán dòng tích lũy bằng các công cụ tính toán trên khá phức tạp. Ngoài ra, các công cụ trên chỉ có thể tính toán các DEM và lưu vực con nhỏ, còn việc sử dụng chúng cho các DEM và lưu vực lớn cho chúng ta kết quả không hiệu quả hoặc mất nhiều thời gian và không thể điều chỉnh kết quả như hình.
Cài đặt thuật toán D8 (tuần tự)
- Đọc dữ liệu (đọc file text độ cao)
- Xác định hƣớng dòng chảy theo D8
- Tính toán tích lũy dòng chảy (D8)
Theo thuật toán tính hướng dòng chảy D8, ô tại vị trí (i, j) sẽ chảy về ô có chiều cao nhỏ nhất trong số 8 ô xung quanh nó, tức là ô có giá trị chênh lệch giá trị tuyệt đối lớn nhất về chiều cao trong số 7 ô. tế bào. các ô còn lại. Ví dụ hướng là 1 thì ô sẽ chảy thẳng về vị trí đó nên điều kiện ràng buộc là số cột cộng 1 (j + 1) phải nhỏ hơn số cột của mảng. Tạo biến max để tìm giá trị lớn nhất khi lặp qua từng ô. tối đa gấp đôi = 0;.
Để bài tập trở nên đa dạng hơn, trong phần tìm đường tích lũy này tôi sẽ không sử dụng thuật toán Floyd (sẽ dành cho các phép tính song song) mà thay vào đó tôi sẽ sử dụng thuật toán đệ quy để tính toán. Khi biết vị trí nào đang chảy, tôi sẽ xử lý chuỗi đó bằng cách chia vị trí cho số cột để lấy tọa độ đường của các vị trí đó và chia vị trí còn lại cho cột để lấy tọa độ cột của vị trí ở đó. Ở bước 2 mình chỉ cần lặp lại đếm số ô chảy về để lấy số tích lũy.
Tại sao phải cài đặt thuật toán song song
Để so sánh với thuật toán này, tôi cũng đã tạo một ứng dụng tương tự, trong đó tôi cũng tính tích ma trận từ 2 ma trận ngẫu nhiên với số hàng và số cột. Hiệu năng CPU khi thực hiện các phép tính tuần tự ở mức trung bình, đồ thị cho thấy tốc độ chạy của máy chưa thực sự ổn định và chưa thực sự tận dụng được tối đa khả năng của CPU. Hình 3.4.2 cho thấy trong trường hợp này thao tác song song đã sử dụng tất cả khả năng của CPU để thực hiện thao tác. Đồ thị đạt đỉnh và duy trì ở mức cao nhất.
Điều này chứng tỏ tại sao các thao tác song song lại nhanh hơn và tốn ít thời gian hơn so với các thao tác tuần tự. Vì chạy đồng thời trên nhiều lõi nên mỗi dòng hoàn thành sẽ được in ngay lập tức. Kết luận: Với những so sánh trên, có thể thấy các thao tác song song có ưu điểm rất lớn so với các thuật toán tuần tự, đặc biệt đối với dữ liệu lớn, các gói dữ liệu mà chúng ta có thể phải xếp hàng đợi. Hàng giờ chờ đợi kết quả, phương pháp xử lý song song sẽ là một giải pháp mới và cũng là thách thức lớn đối với người lập trình (đối với những bài toán phức tạp).
Cài đặt thuật toán song song D8
- Đọc dữ liệu
- Xác định song song hƣớng dòng chảy theo D8
- Tính toán song song tích lũy dòng chảy theo D8
Trong phần này, tôi sẽ sử dụng thuật toán Floyd để tính tích lũy song song và tôi cũng sẽ viết mã song song cho thuật toán này. Sau đó mình cộng điểm để được kết quả tích lũy. Theo thuật toán Floyd, tôi cần tạo ma trận D0 để đưa vào tính toán.
Sau khi có kết quả tích lũy chúng ta trích ranh giới để đưa vào mảng. Đầu tiên, để xem kết quả ở định dạng raster, tôi đã tạo một biểu mẫu mới để chuyển đổi dữ liệu tệp văn bản (.txt) sang tệp raster (.img). Nút chuyển đổi sử dụng gói truyền dữ liệu ArcEngine và gói phát triển ArcGis để chuyển đổi.
CÁC KẾT QUẢ NGHIÊN CỨU
- Giới thiệu dữ liệu thử nghiệm
- Nhóm công cụ xây dựng trong chƣơng trình
- Các kết quả thực hiện đƣợc trong 2 ứng dụng phân tích hƣớng dòng chảy76
- Kết luận
- Kiến nghị
Lưu tệp văn bản kết quả: Đây là nút dùng để lưu kết quả mà chúng tôi tính toán thông qua các thuật toán như Thuật toán D8 và tích lũy chúng trở lại tệp văn bản ArcGis. Để lưu kết quả tích lũy cũng như tính toán của thuật toán D8, chọn nút lưu file văn bản kết quả vào khung soạn thảo. Một hộp thoại sẽ xuất hiện nơi chúng ta có thể chọn ổ lưu trữ và lưu tên tệp tex kết quả. Sau khi hoàn thành các bước chúng ta sẽ được file text thu được có tên và đường dẫn như chúng ta đã lưu.
Để xem kết quả raster trên biểu mẫu sau khi chuyển đổi, hãy làm như sau. Và đây là kết quả của thuật toán tìm kiếm luồng tích lũy dữ liệu DEM của Trường Đại học Nông Lâm TP.HCM. Ứng dụng có khả năng sử dụng kết quả của hướng dòng chảy được xác định trước đó để tính toán tích lũy dòng chảy vào một ô.
Với thuật toán nhân ma trận được triển khai theo định nghĩa, chúng ta có độ phức tạp thuật toán là O(n3). Thuật toán Fox nhân ma trận với ý tưởng thực hiện n bước (từ bước 0 đến bước n-1). Ý tưởng của thuật toán nhân ma trận Fox là giá trị của cij được xác định bằng tổng các tích của các phần tử tiếp theo ai,i+k trong cùng một hàng của ma trận.
Thực hiện xoay hàng cho ma trận A, chuyển hàng i+1 sang hàng i, các giá trị của hàng 0 được chuyển sang hàng n-1. Phép nhân ma trận A và B ở trên có thể song song với số bộ xử lý p (p