Thuật toán song song - Cấu trúc
Để áp dụng đúng bất kỳ thuật toán nào, điều rất quan trọng là bạn phải chọn một cấu trúc dữ liệu thích hợp. Đó là bởi vì một thao tác cụ thể được thực hiện trên một cấu trúc dữ liệu có thể mất nhiều thời gian hơn so với cùng một thao tác được thực hiện trên một cấu trúc dữ liệu khác.
Example- Để truy cập phần tử thứ i trong một tập hợp bằng cách sử dụng một mảng, có thể mất một khoảng thời gian không đổi nhưng bằng cách sử dụng danh sách liên kết, thời gian cần thiết để thực hiện cùng một phép toán có thể trở thành một đa thức.
Do đó, việc lựa chọn cấu trúc dữ liệu phải được thực hiện khi xem xét kiến trúc và kiểu hoạt động sẽ được thực hiện.
Các cấu trúc dữ liệu sau đây thường được sử dụng trong lập trình song song:
- Danh sách liên kết
- Arrays
- Mạng siêu khối
Danh sách liên kết
Danh sách liên kết là cấu trúc dữ liệu có không hoặc nhiều nút được kết nối bằng con trỏ. Các nút có thể chiếm hoặc không các vị trí bộ nhớ liên tiếp. Mỗi nút có hai hoặc ba phần - mộtdata part lưu trữ dữ liệu và hai dữ liệu còn lại link fieldslưu trữ địa chỉ của nút trước đó hoặc nút tiếp theo. Địa chỉ của nút đầu tiên được lưu trữ trong một con trỏ bên ngoài được gọi làhead. Nút cuối cùng, được gọi làtail, thường không chứa bất kỳ địa chỉ nào.
Có ba loại danh sách được liên kết -
- Danh sách liên kết Singly
- Danh sách được liên kết gấp đôi
- Danh sách liên kết hình tròn
Danh sách liên kết Singly
Một nút của danh sách được liên kết đơn lẻ chứa dữ liệu và địa chỉ của nút tiếp theo. Một con trỏ bên ngoài được gọi làhead lưu trữ địa chỉ của nút đầu tiên.
Danh sách được liên kết gấp đôi
Một nút của danh sách được liên kết kép chứa dữ liệu và địa chỉ của cả nút trước và nút tiếp theo. Một con trỏ bên ngoài được gọi làhead lưu trữ địa chỉ của nút đầu tiên và con trỏ bên ngoài được gọi tail lưu trữ địa chỉ của nút cuối cùng.
Danh sách liên kết hình tròn
Một danh sách liên kết vòng rất giống với danh sách liên kết đơn ngoại trừ thực tế là nút cuối cùng đã lưu địa chỉ của nút đầu tiên.
Mảng
Mảng là một cấu trúc dữ liệu nơi chúng ta có thể lưu trữ các kiểu dữ liệu tương tự. Nó có thể là một chiều hoặc nhiều chiều. Mảng có thể được tạo tĩnh hoặc động.
Trong statically declared arrays, kích thước và kích thước của mảng được biết tại thời điểm biên dịch.
Trong dynamically declared arrays, thứ nguyên và kích thước của mảng được biết trong thời gian chạy.
Đối với lập trình bộ nhớ dùng chung, các mảng có thể được sử dụng như một bộ nhớ chung và đối với lập trình song song dữ liệu, chúng có thể được sử dụng bằng cách phân vùng thành các mảng con.
Mạng siêu khối
Kiến trúc siêu khối rất hữu ích cho các thuật toán song song mà mỗi tác vụ phải giao tiếp với các tác vụ khác. Cấu trúc liên kết siêu khối có thể dễ dàng nhúng các cấu trúc liên kết khác như vòng và lưới. Nó còn được gọi là n-cubes, trong đónlà số thứ nguyên. Một siêu khối có thể được xây dựng một cách đệ quy.