Thuật toán song song - Giới thiệu
An algorithmlà một chuỗi các bước nhận đầu vào từ người dùng và sau một số tính toán, sẽ tạo ra đầu ra. Aparallel algorithm là một thuật toán có thể thực hiện một số lệnh đồng thời trên các thiết bị xử lý khác nhau và sau đó kết hợp tất cả các đầu ra riêng lẻ để tạo ra kết quả cuối cùng.
Xử lý đồng thời
Sự sẵn có dễ dàng của máy tính cùng với sự phát triển của Internet đã thay đổi cách chúng ta lưu trữ và xử lý dữ liệu. Chúng ta đang sống trong thời đại mà dữ liệu có sẵn rất nhiều. Hàng ngày, chúng ta xử lý khối lượng dữ liệu khổng lồ đòi hỏi tính toán phức tạp và điều đó cũng diễn ra trong thời gian nhanh chóng. Đôi khi, chúng ta cần tìm nạp dữ liệu từ các sự kiện tương tự hoặc có liên quan đến nhau xảy ra đồng thời. Đây là nơi chúng tôi yêu cầuconcurrent processing có thể phân chia một nhiệm vụ phức tạp và xử lý nó trên nhiều hệ thống để tạo ra đầu ra trong thời gian nhanh chóng.
Xử lý đồng thời là điều cần thiết khi nhiệm vụ liên quan đến việc xử lý một lượng lớn dữ liệu phức tạp. Ví dụ bao gồm - truy cập cơ sở dữ liệu lớn, thử nghiệm máy bay, tính toán thiên văn, vật lý nguyên tử và hạt nhân, phân tích y sinh, lập kế hoạch kinh tế, xử lý hình ảnh, người máy, dự báo thời tiết, dịch vụ dựa trên web, v.v.
Song song là gì?
Parallelismlà quá trình xử lý đồng thời một số tập lệnh. Nó làm giảm tổng thời gian tính toán. Song song có thể được thực hiện bằng cách sử dụngparallel computers,tức là một máy tính có nhiều bộ xử lý. Máy tính song song yêu cầu thuật toán song song, ngôn ngữ lập trình, trình biên dịch và hệ điều hành hỗ trợ đa nhiệm.
Trong hướng dẫn này, chúng ta sẽ chỉ thảo luận về parallel algorithms. Trước khi đi sâu hơn, trước tiên chúng ta hãy thảo luận về các thuật toán và các loại của chúng.
Thuật toán là gì?
An algorithmlà một chuỗi các hướng dẫn theo sau để giải quyết một vấn đề. Trong khi thiết kế một thuật toán, chúng ta nên xem xét kiến trúc của máy tính mà thuật toán sẽ được thực thi. Theo kiến trúc, có hai loại máy tính -
- Máy tính tuần tự
- Máy tính song song
Tùy thuộc vào kiến trúc của máy tính, chúng ta có hai loại thuật toán -
Sequential Algorithm - Một thuật toán trong đó một số bước hướng dẫn liên tiếp được thực hiện theo trình tự thời gian để giải quyết một vấn đề.
Parallel Algorithm- Bài toán được chia thành các bài toán con và được thực hiện song song để có các kết quả đầu ra riêng lẻ. Sau đó, các đầu ra riêng lẻ này được kết hợp với nhau để có được đầu ra mong muốn cuối cùng.
Không dễ để chia một vấn đề lớn thành sub-problems. Các vấn đề phụ có thể có sự phụ thuộc dữ liệu giữa chúng. Do đó, các bộ xử lý phải giao tiếp với nhau để giải quyết vấn đề.
Người ta thấy rằng thời gian cần thiết của các bộ xử lý trong việc giao tiếp với nhau nhiều hơn thời gian xử lý thực tế. Vì vậy, trong khi thiết kế một thuật toán song song, việc sử dụng CPU hợp lý cần được xem xét để có được một thuật toán hiệu quả.
Để thiết kế một thuật toán đúng cách, chúng ta phải có một ý tưởng rõ ràng về các model of computation trong một máy tính song song.
Mô hình tính toán
Cả hai máy tính tuần tự và song song đều hoạt động trên một tập hợp (dòng) hướng dẫn được gọi là thuật toán. Tập hợp các hướng dẫn (thuật toán) này hướng dẫn máy tính về những gì nó phải làm trong mỗi bước.
Tùy thuộc vào luồng lệnh và luồng dữ liệu, máy tính có thể được phân thành bốn loại:
- Máy tính luồng hướng dẫn đơn, luồng dữ liệu đơn (SISD)
- Máy tính một luồng hướng dẫn, nhiều luồng dữ liệu (SIMD)
- Máy tính nhiều luồng hướng dẫn, một luồng dữ liệu (MISD)
- Máy tính nhiều luồng hướng dẫn, nhiều luồng dữ liệu (MIMD)
Máy tính SISD
Máy tính SISD chứa one control unit, one processing unit, và one memory unit.
Trong loại máy tính này, bộ xử lý nhận một luồng lệnh từ bộ điều khiển và hoạt động trên một luồng dữ liệu từ bộ nhớ. Trong quá trình tính toán, ở mỗi bước, bộ xử lý nhận một lệnh từ bộ điều khiển và hoạt động trên một dữ liệu duy nhất nhận được từ bộ nhớ.
Máy tính SIMD
Máy tính SIMD chứa one control unit, multiple processing units, và shared memory or interconnection network.
Tại đây, một đơn vị điều khiển duy nhất sẽ gửi hướng dẫn đến tất cả các đơn vị xử lý. Trong quá trình tính toán, ở mỗi bước, tất cả các bộ xử lý nhận được một bộ lệnh duy nhất từ bộ điều khiển và hoạt động trên bộ dữ liệu khác nhau từ bộ nhớ.
Mỗi đơn vị xử lý có bộ nhớ cục bộ riêng để lưu trữ cả dữ liệu và lệnh. Trong máy tính SIMD, các bộ xử lý cần giao tiếp với nhau. Điều này được thực hiện bởishared memory hoặc bằng cách interconnection network.
Trong khi một số bộ xử lý thực thi một tập hợp các lệnh, các bộ xử lý còn lại sẽ chờ tập các lệnh tiếp theo của chúng. Hướng dẫn từ bộ phận điều khiển quyết định bộ xử lý nào sẽ làactive (thực hiện hướng dẫn) hoặc inactive (chờ hướng dẫn tiếp theo).
Máy tính MISD
Như tên cho thấy, máy tính MISD chứa multiple control units, multiple processing units, và one common memory unit.
Ở đây, mỗi bộ xử lý có bộ điều khiển riêng và chúng chia sẻ một bộ nhớ chung. Tất cả các bộ xử lý đều nhận được hướng dẫn riêng lẻ từ bộ điều khiển của riêng họ và chúng hoạt động trên một luồng dữ liệu duy nhất theo hướng dẫn mà chúng đã nhận được từ bộ điều khiển tương ứng. Bộ xử lý này hoạt động đồng thời.
Máy tính MIMD
Máy tính MIMD có multiple control units, multiple processing units, và một shared memory hoặc là interconnection network.
Ở đây, mỗi bộ xử lý có đơn vị điều khiển riêng, bộ nhớ cục bộ, đơn vị số học và logic. Chúng nhận được các bộ hướng dẫn khác nhau từ các đơn vị điều khiển tương ứng và hoạt động trên các bộ dữ liệu khác nhau.
Ghi chú
Máy tính MIMD chia sẻ bộ nhớ chung được gọi là multiprocessors, trong khi những mạng sử dụng mạng kết nối được gọi là multicomputers.
Dựa trên khoảng cách vật lý của các bộ xử lý, đa máy tính có hai loại:
Multicomputer - Khi tất cả các bộ xử lý ở rất gần nhau (ví dụ: trong cùng một phòng).
Distributed system - Khi tất cả các bộ xử lý ở xa nhau (ví dụ: ở các thành phố khác nhau)