Chương 1. TỔNG QUAN VỀ TÍNH TOÁN SONG SONG VÀ GPU 1. Tổng quan về tính toán song song Khoa học kỹ thuật ngày càng phát triển, đặt ra nhiều bài toán với khối lượng tính toán rất lớn. Trong số đó có những bài toán mà kết quả chỉ có ý nghĩa nếu được hoàn thành trong khoảng thời gian cho phép.
Ví dụ như các tính toán trong thời gian thực, mô phỏng các hoạt động ở mức lượng tử, tính quĩ đạo chuyển động của vật thể trong không gian, mô phỏng vụ nổ của vũ trụ, dự báo thời tiết. Để giải quyết những bài toán này, người ta đã nghiên cứu tăng tốc độ tính toán bằng hai phương pháp hay kết hợp cả hai: Phương pháp 1: Cải tiến công nghệ, tăng tốc độ xử lý của máy tính. Công việc này đòi hỏi nhiều thời gian, công sức và tiền của, nhưng tốc độ cũng chỉ đạt được đến một giới hạn nào đó. Phương pháp 2: Chia bài toán ra thành những công việc nhỏ để có thể chạy song song trên nhiều bộ xử lý.
Việc phát triển công nghệ tính toán theo phương pháp 2 đã cho ra đời công nghệ tính toán song song, đó là việc sử dụng đồng thời nhiều tài nguyên tính toán để giải quyết một bài toán. Các tài nguyên tính toán có thể bao gồm một máy tính với nhiều bộ vi xử lý, một tập các máy tính kết nối mạng hay là một sự kết hợp của hai dạng trên. Công nghệ tính toán song song cho phép giảm thời gian thực thi bài toán tùy thuộc cách phân chia và số bộ xử lý thực thi chương trình. Nguyên tắc quan trọng nhất của tính toán song song chính là tính đồng thời hay xử lý nhiều tác vụ cùng một lúc.
Trong tính toán song song hiện nay, có hai công nghệ chính: Thứ nhất là sử dụng các siêu máy tính với rất nhiều bộ xử lý được tích hợp bên trong được thiết kế đồng bộ cả về phần cứng và phần mềm. Các công nghệ được áp dụng trong các siêu máy tính thường là các công nghệ tiên tiến làm cho giá thành của hệ thống siêu máy tính tăng rất cao.Vì thế các siêu máy tính thường được sử dụng trong các lĩnh vực mà vấn đề tính toán phức tạp, nhạy cảm và yêu cầu thời gian thực như mô phỏng thực hiện của các động cơ máy bay, quốc phòng, vũ trụ. Cách thứ hai là kết nối các máy tính lại với nhau và cùng thực hiện bài toán. Hệ thống các máy tính kết nối này chính là hệ thống tính toán song song phân cụm.
Hệ thống này có ưu điểm là giá thành rẻ hơn rất nhiều so với siêu máy tính có cùng sức mạnh (do sử dụng các thiết bị thông thường) và tính linh hoạt của hệ thống (số nút, số bộ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 3 xử lý, bộ nhớ, thiết bị mạng. đều mang tính tuỳ biến cao). Sự phát triển mạnh mẽ của mạng máy tính, các công nghệ mạng hiện nay đã lấp đi hạn chế về truyền thông trong hệ thống máy tính song song phân cụm làm cho nó được phát triển rộng rãi. Các lĩnh vực sử dụng hệ thống tính toán song song phân cụm thường yêu cầu tính toán không quá lớn, không yêu cầu thời gian thực như xử lý ảnh, nhận dạng vân tay, tính toán kết cấu công trình, mô phỏng các thí nghiệm.
Các mô hình máy tính song song Một hệ thống máy tính song song là một máy tính với nhiều hơn một bộ xử lý cho phép xử lý song song. Định nghĩa này có thể bao quát được tất cả các siêu máy tính với hàng trăm bộ xử lý, các mạng máy tính trạm, hay các hệ thống nhúng … Thậm chí trong mấy năm gần đây các máy tính có vi xử lý áp dụng công nghệ mới multicore cho phép nhiều nhân trong một bộ xử lý cũng được coi là hệ thống máy tính song song [35]. Dựa vào sự phân biệt ở kết nối giữa các bộ xử lý (hay thành phần xử lý), giữa bộ xử lý và bộ nhớ mà có rất nhiều loại kiến trúc máy tính song song khác nhau. Nhưng theo nguyên tắc phân loại của Flynn thì có hai kiến trúc máy tính song song song thông dụng sau [35]: SIMD - Single Instruction Multiple Data: đơn lệnh đa dữ liệu MIMD - Multiple Instruction Multiple Data: đa lệnh đa dữ liệu Sự phân chia này được dựa trên kiến trúc bộ nhớ của các máy tính song song.
Các máy tính song song có bộ nhớ dùng chung (shared memory) có nhiều bộ xử lý cùng được truy nhập đến một vùng nhớ tổng thể dùng chung. Tất cả các sự thay đổi nội dung bộ nhớ do một bộ xử lý tạo ra sẽ được nhận biết bởi các bộ xử lý khác. Máy tính song song có bộ nhớ dùng chung Trong lớp máy tính này có thể phân chia làm 2 lớp nhỏ hơn: Lớp UMA (Uniform Memory Access – Truy cập bộ nhớ đồng nhất) cho phép thời gian truy cập bộ nhớ đối LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 4 với mỗi bộ xử lý là như nhau; Lớp NUMA (Non-Uniform Memory Access – Truy cập bộ nhớ không đồng nhất) có thời gian truy cập bộ nhớ không phải lúc nào cũng như nhau. Còn lại, các máy tính song song có bộ nhớ phân tán cũng có nhiều bộ xử lý nhưng với mỗi bộ xử lý chỉ có thể truy cập đến bộ nhớ cục bộ của nó, không có một vùng nhớ dùng chung nào cho tất cả các bộ xử lý.
Các bộ xử lý hoạt động độc lập với nhau và sự thay đổi trong vùng nhớ cục bộ không làm ảnh hưởng đến vùng nhớ của các bộ xử lý khác. Máy tính song song có bộ nhớ phân tán 1. Mô hình đơn lệnh đa dữ liệu - SIMD Hình 3. Hoạt động của hệ thống SIMD SIMD là một kiểu máy tính song song có tất cả các bộ xử lý chỉ thực hiện một lệnh duy nhất.
Tuy nhiên lệnh này được thực hiện trên các bộ dữ liệu khác nhau ứng với từng bộ xử lý khác nhau. Mô hình này có ưu điểm là đơn giản trong phần cứng cũng như phần mềm nhưng chỉ phù hợp để giải quyết các vấn đề tương đối đặc thù có tính cân đối cao trong xử lý như xử lý ảnh … Các giải thuật cho các đa máy tính thường chạy không hiệu quả trên các máy SIMD. LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Mô hình đa lệnh đa dữ liệu - MIMD.
MIMD là một mô hình kiến trúc máy tính song song thông dụng hiện nay. Với mô hình này thì tất cả các bộ xử lý sẽ thực hiện các lệnh khác nhau với các dữ liệu riêng khác nhau. Sự thực thi các lệnh có thể theo cơ chế đồng bộ hoặc không đồng bộ (synchronous or asynchronous), xác định hay không xác định (deterministic or non-deterministic). Điều này giúp cho mô hình MIMD rất linh hoạt trong việc xử lý song song.
Hoạt động của hệ thống MIMD Tuy nhiên, cùng với tính linh hoạt của mình, mô hình MIMD cũng mang theo một sự phức tạp nhất định. Việc lập trình được những bài toán song song theo mô hình này đòi hỏi nhiều công sức nghiên cứu, phân tích bài toán để tìm ra một cách phân rã tối ưu. Để lập trình theo mô hình này, lập trình viên cần có trình độ cao trong cả chuyên môn và trong kỹ thuật lập trình song song. Mô hình lập trình song song Công việc lập trình song song bao gồm việc thiết kế, lập trình các chương trình máy tính song song sao cho nó chạy được trên các hệ thống máy tính song song.
Hay có nghĩa là song song hoá các chương trình tuần tự nhằm giải quyết một vấn đề lớn hoặc làm giảm thời gian thực thi hoặc cả hai. Lập trình song song tập trung vào việc phân chia bài toán tổng thể ra thành các công việc con nhỏ hơn rồi định vị các công việc đó đến từng bộ xử lý (processor) và đồng bộ các công việc để nhận được kết quả cuối cùng. Nguyên tắc quan trọng nhất ở đây chính là tính đồng thời hoặc xử lý nhiều tác vụ cùng một lúc. Do đó, trước khi lập trình song song bạn cần phải biết được rằng bài toán có thể được song song hoá hay không (có thể dựa trên dữ liệu hay chức năng của bài toán).
Có hai hướng chính trong việc tiếp cận lập trình song song: LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 6 Song song hoá ngầm định (implicit parallelism): bộ biên dịch hay một vài chương trình khác tự động phân chia các công việc đến các bộ xử lý. Song song hoá bằng tay (explicit parallelism): người lập trình phải tự phân chia chương trình của anh ta đế nó có thể thực thi song song. Ngoài ra trong lập trình song song, người lập trình viên cần phải tính đến yếu tố cân bằng tải (load balancing) trong hệ thống. Phải làm cho các bộ xử lý thực hiện số công việc như nhau, nếu có một bộ xử lý có tải quá lớn thì cần phải di chuyển công việc đến bộ xử lý có tải nhỏ hơn.
Việc truyền thông giữa các bộ xử lý là một công việc không thể thiếu của lập trình song song. Có hai kỹ thuật truyền thông chủ yếu là: dùng bộ nhớ dùng chung (shared memory) hoặc truyền thông điệp (message passing). Một mô hình lập trình song song là sử dụng một tập các kỹ thuật phần mềm để thể hiện các giải thuật song song và đưa ứng dụng vào thực hiện trong hệ thống song song. Mô hình bao gồm các ứng dụng, ngôn ngữ, bộ biên dịch, thư viện, hệ thống truyền thông và vào/ra song song.
Trong thực tế, chưa có một máy tính song song nào cũng như cách phân chia công việc cho các bộ xử lý nào có thể áp dụng có hiệu quả cho mọi bài toán. Do đó, người lập trình phải lưa chọn chính xác mô hình lập trình song song hoặc pha trộn các mô hình đó để phát triển các ứng dụng song song trên một hệ thống riêng biệt. Hiện nay có rất nhiều mô hình lập trình song song: Đa luồng (Threads), Truyền thông điệp (Message Passing), Song song dữ liệu (Data Parallel), Lai (Hybird) [11]. Mô hình đa luồng Trong mô hình đa luồng (Threads), một luồng có thể có rất nhiều luồng xử lý.
Ví dụ, một chương trình chính a.out được đưa vào hệ thống để chạy. Nó sẽ thực hiện một vài công việc tuần tự rồi tạo ra một số luồng con. Mỗi luồng có dữ liệu cục bộ riêng của mình nhưng cũng có thể truy cập đến các tài nguyên chung của chương trình a. Mỗi luồng có thể được coi là một chương trình con của chương trình chính và có thể được thực hiện song song với các luồng khác.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.