TỔNG QUAN VỀ TÍNH TOÁN SONG SONG TRONG KHOA HỌC ...

Có thể bạn quan tâm

Tải bản đầy đủ (.doc) (14 trang)

Trang chủ

Công Nghệ Thông Tin

Phần cứng

TỔNG QUAN VỀ TÍNH TOÁN SONG SONG TRONG KHOA HỌC MÁY TÍNH

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (216.84 KB, 14 trang )

TỔNG QUAN VỀ TÍNH TOÁN SONG SONGI. Tổng quan thuật toán song song1. Khái niệm thuật toán song songTính toán song song hay xử lý song song: là quá trình xử lý thông tin trong đó nhấnmạnh việc nhiều đơn vị dữ liệu được xử lý đồng thời bởi một hay nhiều bộ xử lý để giảiquyết một bài toán.Siêu máy tính: là những máy tính đa năng thông thường có tốc độ tính toán vô cùnglớn. Chúng chia làm hai loại:- Máy tính song song dựa trên bộ vi xử lý : được thiết kế với rất nhiều bộ xử lý cótốc độ vừa phải.- Siêu máy tính truyền thống (supercomputer) : ít bộ xử lý hơn nhưng tốc độ củamỗi bộ xử lý đó lại cực cao.Song song về dữ liệu (data parallelism): Là cơ chế sử dụng nhiều đơn vị xử lý thựchiện cùng một thao tác trên nhiều đơn vị dữ liệu .Song song điều khiển (control parallelism) : là cơ chế trong đó nhiều thao tác khácnhau tác động lên nhiều đơn vị dữ liệu khác nhau một cách đồng thời.Dây chuyền (pipeline) : là cơ chế chia công việc thành nhiều chặng nối tiếp, mỗichặng được thực hiện bởi một bộ phận khác nhau. Đầu ra của bộ phận này là đầu vào củabộ phận tiếp theo.Tăng tốc : tăng tốc của thuật toán song song là tỉ số giữa thời gian thực hiện trong tìnhhuống xấu nhất của thuật toán tuần tự tốt nhất và thời gian thực hiện cũng công việc đócủa thuật toán song song. 2. Các mức độ song songTăng tốc = Thời gian thực hiện trong tình huống xấu nhất theo thuật toán tuần tự nhanh nhấtThời gian thực hiện trong tình huống xấu nhất của thuật toán song song đang xétGiả sử có 10 công việc từng đôi một khác nhau thì ta giao cho 10 máy làm, ta có mứcsong song cao nhất, và chúng ta gọi là mức chương trình song song. Mỗi công việc ta lạichia thành các công đoạn (Task) và có thể thực hiện song song, ta gọi mức độ song songnày là mức song song chương trình con. Mỗi chương trình cũng như chương trình con lạicó hàng loạt câu lệnh, ta có mức độ song song câu lệnh, trong câu lệnh lại có hành loạtthao tác (operation) => mức độ song song thao tác.3. Phân loại các kiến trúc song songMột trong những phân loại hay được nhắc tới là của Flynn – 1972. Michael Flynnphân các kiến trúc máy tính thành bốn loại dựa trên tương tác giữa lệnh và dữ liệu :- SIMD(single instruction stream, single data stream) Đây chính là kiến trúc tuần tựVon Neuman, trong đó tại mỗi thời điểm chỉ một lệnh được thực hiện.- MISD (multiple instruction stream, single data stream) Kiến trúc này cho phépmột vài lệnh cùng thao tác trên một dữ liệu- SIMD (single instruction stream, multiple data stream) Cho phép một lệnh đượcthực hiện đồng thời trên các dữ liệu khác nhau.- MIMD (multiple instruction stream, multiple data stream). Cho phép nhiều lệnhkhác nhau có thể đồng thời xử lý nhiều dữ liệu khác nhau trong cùng một thờiđiểm.4. Đánh giá độ phức tạp của thuật toán song songTrong thuật toán tuần tự chúng ta chỉ quan tâm tới độ phức tạp về thời gian và khônggian, nhưng trong thuật toán song song thường có thêm một số đại lượng đo lường khác.Hơn nữa, độ phức tạp thời gian của thuật toán song song không chỉ đơn giản là việc đếmsố câu lệnh cơ bản như trong thuật toán tuần tự mà thay vào đó nó phụ thuộc vào cácphép toán cơ bản này có thể được thực hiện trên P (P > 1) bộ xử lý như thế nào. Bên cạnhđộ phức tạp thời gian độ phức tạp về số bộ xử lý cũng là một đại lượng quan trọng trongphân tích thuật toán song song. Thiết kế thuật toán song song hiệu quả bao gồm việc lựachọn cấu trúc dữ liệu phù hợp, phân bố bộ xử lý và cuối cùng là thực hiện thuật toán. Bađại lượng này tác động lẫn nhau như một tổ chức tính toán.4.1 Song song giới hạn và song song không giới hạnĐộ phức tạp thời gian của thuật toán song song cũng là một hàm của kích thước dữliệu đầu vào – n . Độ phức tạp thời gian là đại lượng quan trọng nhất của thuật toán songsong bởi vì động cơ chính của song song là nhằm tăng tốc thời gian tính toán. Độ phức tạp thời gian tồi nhất (hay đơn giản là độ phức tạp thời gian) của thuật toánsong song giải quyết bài toán Pn với kích thước đầu vào n là một hàm f(n) cho thời gianlớn nhất từ lúc bắt đầu thực hiện thuật toán trên một hay nhiều bộ xử lý đến lúc kết thúcthuật toán bởi một hay nhiều bộ xử lý với bất kỳ bộ dữ liệu nào.Các thuật toán song song được thực hiện trên một tập các bộ xử lý nên đòi hỏi việctruyền dữ liệu giữa chúng. Vì thế nó bao hàm hai hoạt động khác nhau. Một hoạt động làtính toán (như các phép toán số học hay logic) được thực hiện một cách cục bộ trên mộtbộ xử lý, hoạt động khác là gửi dữ liệu giữa các bộ xử lý. Trong thuật toán song song mộtbước cơ bản là một tập các hoạt động cơ bản có thể được thực hiện một cách đồng thờibởi một tập các bộ xử lý – độ phức tạp thời gian của một bước cơ bản là hằng số hayO(1). Độ phức tạp thời gian của thuật toán song song được xác định bởi việc đếm sốbước cơ bản và số bước chuyển giao dữ liệu, trong đó thời gian chuyển giao dữ liệu tạimỗi bước phụ thuộc vào mô hình liên kết giữa các bộ xử lý. Một số tài liệu còn gọi độphức tạp thời gian của thuật toán song song là độ sâu.Độ phức tạp thời gian của thuật toán song song phụ thuộc vào mô hình tính toán songsong được sử dụng một cách tốt nhất trên số lượng bộ xử lý. Vì thế, khi đưa ra độ phứctạp thời gian của thuật toán song song cần thiết đưa ra số lượng lớn nhất bộ xử lý cần sửdụng như một hàm của kích thước dữ liệu đầu vào n, và gọi là độ phức tạp số bộ xử lýcủa thuật toán. Việc tổng hợp và phân tích một thuật toán song song dưới mô hình có Pbộ xử lý (P là một số nguyên cố định và P > 1) được gọi là mô hình song song có giớihạn. Ngược lại, mô hình song song không giới hạn là khi mà chúng ta có và được phéptùy ý sử dụng một số lượng bộ xử lý không giới hạn .Thuật toán song song thực hiện trên mô hình P bộ xử lý được gọi là P-song song. Nếuthuật toán P-song song cho bài toán kích thước n đòi hỏi t(n) bước song song thì được gọilà P-có thể tính toán trong thời gian t. Chúng ta giả sử rằng một thuật toán song song Agiải quyết bài toán kích thước n với P bộ xử lý.Nếu tồn tại đa thức F sao cho ∀n , P ≤F(n) , thì số lượng bộ xử lý được gọi là cận đa thức, ngược lại thì không có cận đa thức.Thuật toán song song có giới hạn là thích hợp trong thực tế. Tuy nhiên, các thuật toánsong song không giới hạn có một sự quan tâm lớn về mặt lý thuyết, vì chúng đưa ra cácgiới hạn cho tính toán song song. Bằng trực giác điều đó có nghĩa là chúng ta giả sử tồntại một số lượng vô hạn bộ xử lý( nghĩa là thuật toán có thể sử dụng tùy ý số lượng bộ xửlý), và cũng không có giới hạn về truyền thông và truy cập bộ nhớ, thì thời gian tính toánkhông thể giảm dưới một giới hạn nào đó. Thực tế số lượng bộ xử lý là có giới hạn, nên thuật toán trên mô hình song songkhông giới hạn chỉ có thể sử dụng trong thực tế nếu chúng được chuyển thành thuật toánP-song song. Có hai phương pháp đưa ra các phép chuyển đổi này : phân tách bài toánhoặc là phân tách thuật toán. Ta có thuật toán song song A giải bài toán Pn kích thước đầuvào n trong thời gian t1(n) sử dụng p1(n) bộ xử lý. Giờ ta đi thiết kế thuật toán mới B giảibài toán Pn trong thời gian t2(n) sử dụng p2(n) bộ xử lý, trong đó p2(n) < p1(n). Cách thứnhất phân tách bài toán thành các bài toán nhỏ hơn với kích thước m (m < n), mỗi bàitoán được giải bởi thuật toán ban đầu với số lượng bộ xử lý nhỏ hơn – p2(m). Cách thứhai là phân tách một thuật toán, mỗi bước của nó được phân tách thành các bước nhỏ hơntheo một cách nào đó sao cho chúng được thực hiện với một số lượng bộ xử lý nhỏ hơn. 4.2. Cận trên và cận dướiThuật toán song song nhanh nhất được biết để giải quyết bài toán cho ta cận trên củatính toán đó. Nếu một ai đó thiết kế ra một thuật toán nhanh hơn thuật toán nhanh nhấttrước đó để giải quyết cùng một bài toán thì chúng ta nói rằng cận trên mới đã được thiếtlập cho việc tính toán lời giải của bài toán đó. Cận dưới xác định độ phức tạp của bàitoán, nghĩa là nó đưa ra lượng thời gian tối thiểu để giải quyết bài toán sử dụng một thuậttoán song song tùy ý.4.3. Chi phí, tăng tốc, và hiệu quả của thuật toán song songTăng tốc và hiệu suất : xét bài toán với thuật toán tuần tự tốt nhất có thời gian Ts,thuật toán song song Tp ; số bộ xử lý là P. Khi đó:Tăng tốc = Ts/TpHiệu suất = Ts/(PTp)Tăng tốc luôn nhỏ hơn số bộ xử lý, cố gắng đạt tới bằng nên hiệu suất đạt cùng lắm là1.4.4. Các kĩ thuật cho việc nâng cao hiệu quả của thuật toán song song - Giảm số lượng bộ xử lý - Giảm độ phức tạp thời gian4.5. Độ phức tạp của bài toánDưới đây là mô hình phân lớp độ phức tạp của bài toánNói chung xử lý song song không có tác dụng cho việc giải quyết các bài toán NP.Một bài toán thực hiện trong 400 tỷ thế kỷ trên một bộ xử lý sẽ mất 400 thế kỷ nếu chúngta thực hiện song song hóa một cách hoàn hảo và thực hiện trên 1 tỷ bộ xử lý. Vì thế, xửlý song song được sử dụng chính cho việc tăng tốc thời gian thực hiện của bài toán P.II. Tổng quan MPI1. Môi trường gửi nhận MPI.1.1 Khái niệm SPMD độc trình dùng bộ nhớ phân tán.Mỗi máy hoạt động theo nhịp đồng hồ riêng của mình và chỉ có thể đọc dữ liệu ở trênmáy của mình (distributed memory system & asynchronous operation mode). Đối vớimột mạng như vậy, thì về nguyên tắc, trên mỗi máy ta có thể cho chạy một trình riêng vàdữ liệu của mỗi trình là riêng (MPMD). Các trình này có thể khác nhau, tức là chúng giảiquyết các bài toán khác nhau, hoạt động độc lập và chỉ đến một lúc nào đó thì chúng mớitrao đổi dữ liệu cho nhau. Sự việc xảy ra là: nếu thời điểm khởi động các trình trên các máy khác nhau màkhông xác định, thì thời điểm cho việc chúng trao đổi dữ liệu cho nhau cũng không thểxác định được. Vậy chúng ta vẫn cần phải có một “trọng tài” để xác định thời điểm bắtđầu hoạt động cho chúng. Với quan niệm này người ta coi như tất cả chúng chỉ là mộttrình chung thôi độc trình. Điều này hàm ý: - (1) Trên mỗi máy tính chạy một trình,nhưng chúng hoàn toàn giống nhau, - (2) Tất cả các trình ấy được khởi động để chạycùng một lúc. Tuy chỉ sử dụng một độc trình, nhưng các máy tính khác nhau vẫn sẽ làm những“phần việc” của mình, bởi trong trình chung ấy, mỗi “phần việc” là những đoạn lệnhriêng – mà mỗi máy sẽ tự kiểm tra xem mình cần chạy đoạn lệnh nào.Các trình, tức là các đoạn lệnh “riêng” ấy, chỉ có thể truy cập trực tiếp vào bộ nhớRAM trong máy của mình – độc trình dùng bộ nhớ phân tán. Nếu ở trong trình có mộtbiến được khai báo thì tức là nó sẽ có mặt ở tất cả các máy tính. Điều vừa được trình bày ra ở trên hàm ý là các máy tính không thể thực hiện đượcviệc trao đổi giá trị với nhau thông qua các ô nhớ (bởi trên thực tế chúng chẳng có ô nhớchung nào cả!). Các máy tính muốn trao đổi dữ liệu với nhau thì phải thông qua các lệnhgửi-nhận mà MPI cung cấp. Đó là môi trường đảm nhận nhiệm vụ truyền tải dữ liệu quamạng. Mỗi máy tính muốn tham gia vào hệ thống MPI phải được cài thêm một trìnhthường trú, gọi là Driver-MPI. Nó gửi/nhận dữ liệu truyền theo đường mạng rồi chuyểnđến nơi qui định.1.2 Khái niệm mạng ảo.Mục đích của MPI là tạo ra một môi trường gửi-nhận dữ liệu thân thiện, cho phépchúng ta soạn thảo và thử trình MPI chỉ trên một máy, để sau đó chạy nó trên một mạngmáy tính – có thể có cấu trúc rất phức tạp. Để làm việc này MPI cho phép mô phỏng mộtmạng ảo chỉ trên một máy tính. Độc trình của chúng ta sẽ chạy trên các máy ảo này (vẫntheo nguyên tắc trên mỗi máy chạy một trình). MPI bảo đảm để về mặt hình thức máy ảohoàn toàn tương đương với máy thật. Điểm lưu ý là các độc trình trên cùng một máy thậtthì dùng chung đĩa cứng. Cho dù là trên cùng một máy, nhưng các độc trình không thể trực tiếp trao đổi dữ liệucho nhau (vì chúng chạy trên các máy ảo khác nhau). Hoàn toàn giống như các máy tínhđộc lập trong mạng, các chúng chỉ có thể trao đổi dữ liệu với nhau thông qua môi trườngMPI. Thông thường người ta viết và chạy thử trình trên một máy tính, khi ấy sẽ có sự phânbiệt giữa giữa trình và máy tính. Tuy nhiên, khi sử dụng trên một mạng gồm nhiều máytính thì, thường là, trên mỗi máy chỉ chạy có một trình. Vì vậy, mỗi khi không có khảnăng xảy ra nhầm lẫn, chúng ta sẽ dùng từ máy tính với hàm ý chỉ trình chạy trên nó. 1.3 Cấu trúc một trình MPICấu trúc khái quát của một trình MPI chạy trên nhiều máy bao gồm 2 phần. Phần thứnhất là việc mỗi máy tự “nhận biết” đoạn trình mà mình cần thực hiện, và phần thứ hai làthủ tục gửi-nhận dữ liệu cho nhau. Sơ đồ như sau:#include <stdlib.h>#include <stdio.h>#include <mpi.h>main(int argc,char **argv){…if (MPI_Init(&argc, &argv) != MPI_SUCCESS) exit(1); /* Initialize MPI */MPI_Comm_size( , &np );MPI_Comm_rank( , &ip );…If (ip == me) {… do work-of-me …} …MPI_Finalize(); exit(0); /* check-out */}Trong đó “np” là số lượng tiến trình, và “ip” là số hiệu của tiến trình hiện tại. Dựavào số hiệu “ip” mà ta biết được là phải thực hiện khúc lệnh nào.1.4 Tuần tự hóa song songCho dù muốn hay không, thì vấn đề tuần tự hóa cũng xuất hiện khi các đối tượng hoạtđộng song song cùng sử dụng chung một thiết bị, ví dụ như màn hình. Quá trình chuyểntừ song song sang tuần tự còn dính đến một vấn đề rắc rối là thứ tự trước sau. Ví dụ nhưviệc các máy tự tìm ra số hiệu của mình, rồi in ra trên màn hình (của máy số 0). Trên mànhình, số hiệu có thể xuất hiện theo một thứ tự không thể đoán trước được, và điều này làdo giữa các máy không có một giao tiếp nào để định ra thứ tự in; và do chúng chạy songsong nên máy nào “may mắn” hơn thì sẽ in ra trước, máy nào “ít may mắn” hơn sẽ in rasau(!).Để các máy có thể in số hiệu của mình theo thứ tự tăng dần, chúng ta cần phải có biệnpháp xử lý – biện pháp như thế được gọi là tuần tự hóa song song. Có thể có 2 biện pháp: 1. Biện pháp thứ nhất là gọi tên. Theo cách này chúng ta bắt tất cả các máy phảidừng lại trước “barrier” để chờ và chỉ máy nào được gọi tên thì mới được “đi qua”để thực hiện công việc của mình. 2. Biện pháp thứ hai là “chuyền cờ”. Theo phương pháp này có một chiếc “cờ” đượcchuyền từ máy này đến máy khác theo số hiệu tăng dần. Chỉ máy nào nhận đượccờ thì mới được thực hiện tiếp các lệnh của mình.1.5 Các phương pháp gửi-nhận cơ bảnBản chất của việc gửi dữ liệu từ một máy tính này sang một máy tính khác là việctruyền một dãy xung điện qua dây dẫn. Xung điện này chuyển tải nội dung của một ô nhớđặc biệt – “port” của máy “A” sang “port” của máy “B”. Cùng lúc ấy một chương trìnhchuyên dụng của máy “B” được kích hoạt để vận chuyển dữ liệu ấy tới nơi qui định. Nhưvậy vào thời điểm máy “A” gửi dữ liệu thì máy “B” phải hoạt động. Trường hợp ngượclại mà “B” vẫn muốn nhận được dữ liệu thì những dữ liệu ấy phải được một máy “C” nàođó khác nhận vào hộ. Về nguyên lý chỉ có thể có hai kiểu gửi-nhận:1. Gửi trực tiếp – transient: “A” gửi, “B” nhận. Nếu “B” không nhận thì những dữliệu này sẽ bị mất.2. Gửi gián tiếp – persistence: “A” gửi vào “C”, “B” nhận từ “C”. Máy “C” phải liêntục hoạt động. Mỗi kiểu gửi nói trên có thể được thực hiện theo một trong hai phương án sau:1. Gửi không đồng bộ – asynchorous. “A” đẩy luôn dữ liệu cho “B” mà không cầnbiết là “B” có nhận được dữ liệu không. Nếu B chưa sẵn sàng nhận thì dữ liệu sẽbị mất. 2. Gửi đồng bộ – synchronous. Trước khi gửi dữ liệu, thì “A” tự tạo ra và gửi tín hiệuđồng bộ cho “B”. Các tín hiệu này có khuôn dạng nhất định và được gửi đi gửi lạicho tới khi nào B nhận được mới thôi (như vậy nếu có mất thì không phải là mấtdữ liệu cần gửi mà chỉ là các tín hiệu đồng bộ). Tín hiệu đồng bộ hóa báo cho Bbiết các thông tin cần thiết như dung lượng dữ liệu sẽ gửi cho nó. Khi “A” nhậnđược tín hiệu hồi âm của B báo cho biết là B đang chờ để nhận dữ liệu do nó gửi,“A” chuyển ngay khối dữ liệu ấy cho “B” – đủ dung lượng như đã thông báo. Vềnguyên tắc “A” được giải phóng ngay sau khi bắt đầu gửi (để đi thực hiện lệnhkhác,) nhưng vì việc gửi là việc của nó nên thời gian ấy cũng là thời gian mà nóphải chờ. (Nếu “A” chờ cho tới khi “B” thông báo cho “A” biết là mình đã nhậnxong dữ liệu thì chúng ta gọi là gửi đồng bộ có bảo đảm.)Đối với các tiến trình trên một máy tính (đơn xử lý hay đa xử lý) hay ở các máy tínhkhác nhau trong một mạng thì việc gửi nhận dữ liệu cũng diễn ra tương tự như vậy, ngoạitrừ một điểm khác là toàn bộ quá trình gửi nhận do hệ điều hành MPI đảm nhận. MPIphục vụ công việc gửi nhận cho nhiều tiến trình cùng một lúc. Quá trình gửi-nhận của MPI được cải tiến theo cách cắt nhỏ dữ liệu cần chuyển rathành các khối nhỏ. Các khối này được chuyển, lần lượt lần lượt cho từng tiến trìnhmột (bằng cách làm này MPI tạo ra cảm giác là việc gửi-nhận giữa các tiến được thựchiện song song). Để làm được việc này MPI cấp cho mỗi tiến trình một vùng đệm(buffer). Vùng đệm này được gọi là vùng đệm hệ-thống, để phân biệt với vùng đệm tạmdo bản thân tiến trình tạo ra. Các khối dữ liệu cần chuyển được đưa vào vùng đệm.Việc gửi nhận được chia làm hai công đoạn. Công đoạn từ các tiến trình ra tới vùng đệm,và công việc luân chuyển dữ liệu giữa các vùng đệm. Đối với công đoạn từ tiến trình ra đến vùng đệm, một tiến trình muốn gửi dữ liệu thìnó phải thực hiện việc: - Đóng gói dữ liệu thành các khối, mỗi khối có thông tin hệ thống – overhead, vàdữ liệu. Thông tin hệ thống gồm có địa chỉ và các chỉ thị cho MPI về qui trình gửi-nhận. - Chuyển các khối dữ liệu vừa đóng gói ấy ra vùng đệm. Nếu là gửi ra vùng đệmtạm thì toàn bộ dữ liệu chỉ cần đóng thành 1 khối. Một tiến trình muốn nhận dữ liệu về nó phải thực hiện việc: - Copy khối dữ liệu từ vùng đệm hệ thống về. - Tách dữ liệu từ các khối nhỏ này và kết hợp chúng lại với nhau. Các tiến-trình không cần biết chi tiết về công đoạn luân chuyển dữ liệu giữa các vùngđệm với nhau, chúng trao cho MPI quyền điều hành toàn bộ quá trình này thông qua cácthông tin overhead có ở trong các khối dữ liệu. Các thông tin này báo cho MPI biết làphải làm gì với các khối dữ liệu ấy. 2. Một số hàm chính trong thư viện MPI2.1. Lệnh MPI_Send.Lệnh này dùng để gửi dữ liệu từ một máy này đến một máy khác. Lệnh MPI_Send chỉcó thể kết thúc nếu khối dữ liệu được chuyển xong. Từ điều này suy ra rằng: máy “A” gửidữ liệu cho “B” thì “B” phải nhận vào đã nhận xong rồi, “B” mới có thể gửi cái gì đấylại cho “A”, nếu nó thật sự muốn gửi ngược lại cho “A”! Điều này được minh họa trong sơ đồ sau. Nếu máy “A” và “B” mỗi máy đều có dữ liệu để ở sendbuf của mình, và muốn truyềnchúng cho nhau. Qui trình chuyển diễn ra tuần tự như sau: “A” gửi dữ liệu cho “B”, “B”nhận vào và để ở recvbuf trong máy của mình. Sau đó “B” chuyển dữ liệu của mình (để ởsendbuf trong máy của “B”) cho “A”, và “A” lại nhận và để ở recvbuf trong máy của nó. 2.2 Lệnh MPI_Recv Lệnh này dùng để nhận dữ liệu từ một tiến trình khác, ví dụ như tiến trình “A” nào đó,gửi cho. Một khi chưa có dữ liệu, tức là “A” chưa thực hiên lệnh gửi dữ liệu MPI_Sendđể gửi dữ liệu cho nó, thì nó sẽ phải chờ. 2.3. Lệnh MPI_SsendLệnh MPI_Ssend gửi dữ liệu từ một tiến trình này đến một tiến trình khác. Để thực hiện được công việc gửi bằng lệnh MPI_Ssend, trước hết tiến trình gửi – “A”phát tín hiệu cho “B” thông báo là có một lượng dữ liệu cần gửi cho nó và xin phép gửi.Tiến trình “A” sẽ phải chờ cho tới khi nào “B” gửi lại tín hiệu cho phép. Khi “A” nhậnđược tính hiệu cho phép báo là “B” đang sẵn sàng nhận dữ liệu thì dòng dữ liệu đượctruyền từ “A” sang “B”. Chỉ khi nào tiến trình “B” nhận xong dữ liệu thì lệnh gửiMPI_Ssend của tiến trình “A” nới được coi là kết thúc. Và chỉ khi ấy các lệnh tiếp theosau lệnh gửi của “A” và lệnh nhận của “B” mới được xử lý.So với lệnh gửi MPI_Send thì gửi bằng lệnh MPI_Ssend sẽ tiêu tốn thời gian hơn. Điềunày xảy ra là do quá trình đồng bộ hóa, tức là tiến trình gửi “A” chẳng những phải chờ đểđược tiến trình nhận “B” cho phép, mà còn phải chờ tới thời điểm MPI chuyển được khốidữ liệu vào vùng đệm hệ thống của “B”.3. Chiến lược phân việc cho máy tính Receiv β from “1”Send α to “1” Receiv α from “0”Send β to “0”Bản chất của việc tính toán song song là làm cho thời gian tính toán giảm đi. Việc nàyđược thực hiện thông qua việc sử dụng nhiều máy tính cùng thực hiện. Tuy nhiên, việc cóđược nhiều máy tính mới chỉ là điều kiện cần, vấn đề là chúng ta phải biết cách phân phốicông việc cho chúng một cách hợp lý nhất. Có 2 phương án phân chia việc cho các máy,theo “kế hoạch” và “đợi việc”. Cả hai phương án trên đều cần thiết và được áp dụng chocác trường hợp khác nhau. Phương án thứ nhất là phân phối theo kế hoạch. Theo phương án này công việc đượcgiao từ đầu theo năng lực tính toán. Phương án thứ hai thì các máy tính tranh nhau nhậnviệc, làm xong lại đến nhận tiếp. Phương án phân việc theo “kế hoạch” được sử dụng khi mà số lượng công việc ít,nhưng mỗi việc đòi hỏi nhiều thời gian chạy máy; và hơn thế những việc ấy tương đốikhác nhau (chẳng hạn như cộng và nhân ma-trận là các việc rất khác nhau). Phương án“xếp hàng” được sử dụng khi mà số lượng công việc rất nhiều, nhưng mỗi việc chỉ tốn ítthời gian chạy máy; và hơn thế chúng nó đều là các việc tương tự như nhau.

Tài liệu liên quan

Silde tổng quan về hệ thống thông tin trong phân tích thiết kế
- 86
- 1
- 10
Nghiên cứu tổng quan về tính toán lưới và cái đặt mô hình thử nghiệm
- 113
- 945
- 5
Tổng quan về công ty Sông Đà 12
- 19
- 433
- 0
Chương 1 - Tổng quan về An toàn thông tin
- 14
- 1
- 16
Tổng quan về xí nghiệp Sông Đà 8.06
- 22
- 339
- 0
Giới thiệu tổng quan về ngôn ngữ lập trình trong java
- 14
- 579
- 0
TỔNG QUAN VỀ TỈNH NINH BÌNH VÀ CÁC KHU DU LỊCH TRONG TỈNH
- 11
- 1
- 0
Tổng quan về an toàn bảo mật
- 20
- 448
- 0
TỔNG QUAN VỀ THANH TOÁN KHÔNG DÙNG TIỀN MẶT TRONG NỀN KINH TẾ THỊ TRƯỜNG
- 24
- 536
- 0
Tổng quan về thanh toán không dùng tiền mặt trong nền kinh tế thị trường
- 23
- 406
- 0