TÍNH TOÁN SONG SONG

Một công việc, một vấn đề nào đó hay một bài toán nào đó,… (như xây dựng một công trình nhà ở, đô thị, cầu cống, may mặc, giải một bài toán,… ) nếu được phân chia thành các vấn đề nhỏ hơn, các vấn đề nhỏ này nếu có thể thực hiện đồng thời, thì ta nóivấn đề đó được thực hiện song song. Sau khi tất cả các vấn đề con được thực hiện xong, các kết quả của chúng sẽ được kết nối lại để có kết quả chung cho cả vấn đề cần giải quyết. Chẳng...
Nội dung trích xuất từ tài liệu:
TÍNH TOÁN SONG SONGTÍNH TOÁN SONG SONG LÊ HUY THẬPGIÁO TRÌNH 1. 1. Tổng quanMột công việc, một vấn đề nào đó hay một bài toánnào đó,… (như xây dựng một công trình nhà ở, đôthị, cầu cống, may mặc, giải một bài toán,… ) nếuđược phân chia thành các vấn đề nhỏ hơn, các vấnđề nhỏ này nếu có thể thực hiện đồng thời, thì ta nóivấn đề đó được thực hiện song song. Sau khi tất cảcác vấn đề con được thực hiện xong, các kết quảcủa chúng sẽ được kết nối lại để có kết quả chungcho cả vấn đề cần giải quyết. Chẳng hạn việc đàomóng công trình và chuẩn bị sắt làm móng có thểlàm đồng thời. Sau khi hai cả hai phần việc này xong,chúng ta có thể đổ móng cho công trình. Hoặc khicộng hai véc tơ n phần tử, chúng ta có thể phânnhóm các phần tử và chia cho các bộ xử lý cùng thựchiện phép cộng,…Tính toán song song là sự phát triển của tính toán tu ần t ự, tính toán song song rất phức tạp, các sự kiện liên quan với nhau xảy ra tại cùng thời điểm, cùng trong phạm vi một chuỗi hành động. Chẳng hạn:• Hệ hô hấp và hệ tuần hoàn của các loài động vật• Việc hình thành dãy Ngân Hà• Vận động của hành tinh• Đại dương và thời tiết• Trôi dạt, tích tụ và kiến tạo địa tầng.• Giao thông giờ cao điểm• Tuyến đường Ô tô trong thành phố• Xây dựng các tuyến giao thông trong thành ph ố1.1.1. Tính toán tuần tự, chương trình tuần tự và song songTính toán tuần tựMột vấn đề được chia thành một dãy rời rạc các chỉ thị mà máy tính có thể hiểu để thực hiện.Máy tính thực hiện các chỉ thị theo thứ tự mà chúng xuất hiện.Chỉ có duy nhất một chỉ thị được thực hiện tại một th ời điểm.Chương trình tuần tự Chương trình được viết trên một ngôn ngữ nào đó để thể hiện việc tính toán tuần tự được gọi là chương trình tuần tự. Máy tính tuần tựLoại máy tính thực hiện các lệnh mộtcách tuần tự và tại mỗi thời điểm chỉ mộtchỉ thị duy nhất được thực hiện – máy tínhchỉ có một CPU. Vì chỉ có một CPU nêncòn gọi là máy tính đơn nguyên. MINH HỌA TÍNH TOÁN TUẦN TỰBài toán cần giải Các câu lệnh s sn si CPU s3 s2 s1 .. Hình 1-1. Cách giải quyết vấn đề của máy tính tuần tự . Ví dụ 1-1Viết chương trình có tên HELLO.CPP (trong C++) để đưa dòng “Hello World !” ra màn hình là chương trình tu ần tự. Chương trình có dạng sau đây:t1 : #include t2 : int main ( )t3: {t4 : cout Tính toán song songTính toán song song là quá trình tính toán gồm nhiều tiến trình đồng thời và cùng tham gia tính toán giải quyết một vấn đề, và nói chung phải thực hiện trên các hệ thống đa bộ xử lí.Một vấn đề cần tính toán được phân hoạch thành các phần tính toán rời rạc, các phần này được tính toán song song với nhau.Các chỉ thi của từng phần thực hiện đồng thời trên các CPU khác nhau.Quan niệm đơn giản nhất, tính toán song song là sử dụng đồng thời nhiều máy tính được kết nối lại hoặc trên một máy tính có nhiều hơn hai bộ xử lý. MINH HỌA TÍNH TOÁN SONG SONG CPU CPU CPU CPUHình 1-2. Cách thực hiện các phần song song trên máy tính song song NHẬN XÉTĐể tính toán song song chúng ta cần m ột trong nh ững tài nguyên:• Hoặc một máy tính nhưng có nhiều bộ xử lý,• Hoặc một số tùy ý các máy tính được kết nối thành mạng.• Hoặc tổ hợp cả hai loại trên.Các công việc có thể tính toán song song có các tính ch ất sau:Có thể chia thành các phần rời rạc, các phần đó có th ể thực hiện đồng thời;• Có thể thực hiện nhiều câu lệnh tại cùng một th ời điểm;• Hiệu năng-theo nghĩa sử dụng ít thời gian (hay tiền bạc) hơn tính toán tuần tự trên máy đơn nguyên. Chương trình song songChương trình được viết trên một ngôn ngữnào đó để thể thực hiện việc tính toánsong song được gọi là chương trình songsong. Ví dụ 1-2Tính tổng hai véc tơ: C = A + BChương trình tuần tự trên máy tính đơn nguyên có thể như sau (giả mã) for(i = 0 ; i < n; i++) { C[i] = A[i] + B[i]; } Máy tính có p bộ xử lý. Hãy phân hoạch N phần tử của hai mảng A và B thành p phần, bộ xử lý thứ k nhận nk phần tử.Bộ xử lý 1 2 … pCác chỉ số phần tử mảng 0 … n1-1 n1 … n2-1 … np-1 … np-1 ACác chỉ số phần tử mảng 0 … n1-1 n1 … n2-1 … np-1 … np-1 BCác chỉ số phần tử mảng 0 … n1-1 n1 … n2-1 … np-1 … np-1 C for (j = nk -1 ; j < (nk -1) ; j++) { C(j) = A[j] + B[j] } Trong đó k = 1, 2,3, …và n0 = 0Mục đích của tính toán song song1. Nâng cao hiệu năng tính toán2. Mô hình hóa các vấn đề khoa học kỹ thuật rất phức tạp trong thế giới thực.…Chẳng hạn:• Khí quyển, Trái đất, Môi trường• Vật lý ứng dụng, Hạt nhân, Hạt, Áp suất cao, S ự nóng chảy, Lượng tử ánh sáng• Sinh học, Công nghệ sinh học, Di truyền học• Hóa học, Khoa học phân tử• Địa chất, Địa chấn học• Công nghệ vũ trụ• Kỹ thuật điện, Thiết kế mạch, Vi điện tử• Khoa học máy tính, Toán học• …..1.1.2. Tại sao sử dụng tính toán songsongTiết kiệm thời gian và / hoặc tài chính Khi chi phí nhiều tài nguyên cho một công việc nào đó sẽ rút ngắn được thời gian hoàn thành công việc đó, và tiết kiệm các chi phí tiềm năng. Phần cứng song song có thể được xây dựng với giá thành thấp và dễ mua.Giải quyết được các vấn đề lớn hơn, phức tạp hơn• Nhiều vấn đề quá lớn, quá phức tạp đến nỗi nó không thực tế hoặc không có khả năng giải quyết chúng trên máy tính đơn, đặc biệt là bộ nhớ máy tính lại bị hạn chế. Chẳng hạn các vấn đề:• Dự báo thời tiết, bã ...