Thiết kế giải thuật song song

từ những yêu cầu thực tế và được khoa học hiện nay coi như những thánh thức lớn “grand challenges”, đây là các bài toán đặt ra để mô phỏng thế giới thực của một vấn đề, hiện tượng có yêu cầu về tính toán và khả năng lưu trữ lớn. Để đáp ứng nhu cầu của khoa học, kiến trúc máy tính cũng thay đổi nhanh chóng nhằm tăng cường sức mạnh tính toán và xử lý theo từng thế hệ. Sức mạnh của máy tính theo kiến trúc John von Newman có thể được cải thiện theo hai xu hướng khác nhau: Thứ nhất : Dựa vào sự phát triển của công nghệ Thứ hai : Dựa vào sự cải tiến về kiến trúc Các cải tiến về kiến trúc có thể tăng khối lượng công việc thực hiện cho mỗi chu kỳ lệnh, trong khi tiến bộ về công nghệ có thể giảm thời gian cần thiết cho mỗi chu kỳ lệnh. Sự cải tiến về công nghệ đã trải qua nhiều giai đoạn phát triển khác nhau và trở thành một chỉ tiêu quan trọng trong khi phân chia các thế hệ máy tính. Từ thế hệ thứ nhất dùng đèn điện tử, thế hệ thứ hai dùng công nghệ bán dẫn, đến thế hệ thứ ba dùng công nghệ mạch tích hợp lớn VLSI ( Very Large Scale Intergrated Circuit). Với công nghệ này, các VLSI có thể tích hợp từ hàng trăm nghìn đến hàng triệu transistors trên một đơn chíp và có thể tạo ra các tần số đồng hồ hàng trăm MHz. Sự cải tiến về mặt công nghệ hy vọng còn tiếp tục phát triển nhờ vào sự tích hợp ngày càng lớn mật độ các thành phần trên một chip, do đó giảm được thời gian trễ vận chuyển giữa các thành phần trên chíp. Vào giữa thập niên 1970, các tiến bộ kiến trúc quan trọng như bộ nhớ song song bit( bit-parallel memory), số học song song bit ( bit-parallel arithmetic), bộ nhớ truy nhập nhanh (cache memory), pipeline lệnh (instruction pipelining), khối đa chức năng (multiple functional units), pipeline dữ liệu (data pipelining) - đã được kết hợp trong thiết kế máy supercomputer hay mainframe. Từ đó, để năng cao hiệu năng của các bộ xử lý đơn người ta có ý định giảm thời gian chu kỳ lệnh. Tuy nhiên với công nghệ VLSI kết hợp với những tiến bộ kiến trúc cho phép máy tính đơn có khả năng tính toán cao, thực hiện hàng trăm triệu phép tính trên một giây nhưng điều này vẫn chưa đáp ứng được các thách thức khoa học với các bài toán như mô hình thời tiết và môi trường toàn cầu, tính toán chu trình đại dương. vũ trụ học và thiên văn học, y học và mô hình các xương và cơ quan con người, phản ứng hoá học và hạt nhân. v. v. Ngày nay, các ứng dụng có tính thương mại đang tác động đến việc phát triển máy tính song song bởi những ứng dụng này yêu cầu xử lý số lượng lớn dữ liệu theo các cách thức phức tạp. Ví dụ như cơ sở dữ liệu song song, khai phá dữ liệu, tìm kiếm dầu mỏ, chuẩn đoán dưới sự trợ giúp của máy tính trong y học, quản lý của các công ty kinh doanh, tổ chức đa quốc gia, công nghệ multimedia và video trên mạng. v. v. Nguyên nhân chính hạn chế trong việc phát triển máy tính đơn có tốc độ cao là do sự hạn chế vật lý của IC, chúng ta không thể gia tăng mãi khả năng tích hợp các linh kiện bán dẫn trên cùng một chíp và tốc độ truyền tải tín hiệu của mạch điện bị hạn chế không vượt quá tốc độ ánh sáng. Để tăng cường sức mạnh tính toán giải quyết các bài toán lớn có độ tính toán cao, người ta phát triển theo hướng kiến trúc máy tính, với ý tưởng kết hợp nhiều bộ xử lý vào trong một máy tính mà người ta hay gọi là máy tính song song Multiprocessor hoặc kết hợp sức mạnh tính toán của nhiều máy tính dựa trên kết nối của mạng cục bộ đã có, người ta gọi là máy tính song song Multicomputer. Điều này đã được Daniel Slotnick ở trường đại học Illinois thực hiện với thiết kế hai máy tính song song là máy Solomon được xây dựng bởi công ty Westinghouse Electric Company vào đầu những năm 1960 và sau đó vào đầu những năm 1970, máy tính ILLIAC IV được lắp ráp tại công ty Burroughs Corporation. Tại trường đại học Carnegie-Mellon, hai máy tính song song là C. mmp và Cm* - được xây dựng trong suốt những năm 1970. Trong những năm đầu 1980, các nhà nghiên cứu tại Caltech đã xây dựng ra máy Cosmic Cube, một hình thức sơ khai của máy tính song song Multicomputer. Sự hội tụ giữa kiến trúc song song và công nghệ xây dựng các máy lớn truyền thống đã dẫn đến sự phát triển các máy tính song song có hàng chục, trăm, hoặc thậm chí hàng nghìn các microprocessor. Với hiệu năng cao nhất, các máy tính song song như Intel’s Paragon XP/S, MasPar’s MP-2 và Thinking Machines’ Cm 5, đã vượt qua tốc độ của các máy supercomputer đơn bộ xử lý truyền thống như Cray Y/MP và NEC SX-3. Đối với việc xây dựng các máy tính song song có hàng trăm đến hàng ngàn bộ xử lý với bộ nhớ chính có kích thước lớn sẽ rất tốn kém, không hiện thực đối với nhu cầu thực tế nhưng bù lại sẽ có môi trường tính toán ổn định và sức mạnh tính toán lớn. Với máy tính song song kết nối nhiều máy tính sẵn có thông qua mạng cục bộ sẽ đáp ứng được về giá thành, tận dụng được máy tính sẵn có, khả năng lưu trữ dữ liệu sẽ lớn hơn và hiện nay với mạng LAN tốc độ cao sẽ cho phép ta thực hiện được điều này. Tuy nhiên với môi trường tính toán không đồng nhất về tốc độ xử lý trên mỗi máy tính, khả năng lưu trữ. . sẽ làm cho việc thực hiện bài toán trở nên khó khăn. Để giải quyết vấn đề này các phần mềm được xây dựng ra như PVM ( Parallel Virtual Machine ), MPI, Linda, P4, . v. v. cho phép thực thi song song bài toán trên mô hình Multicomputer. Ngoài việc có sức mạnh tính toán nhanh, máy tính song song có khả năng lưu trữ lớn với mô hình bộ nhớ phân tán và khả năng chịu hỏng tốt hơn máy tính đơn bộ xử lý. Đối với máy tính đơn, khi bộ xử lý bị sự cố thì cả hệ thống dừng hoạt động còn các máy tính song song vẫn có thể thực hiện công việc khi một vài bộ xử lý hay máy tính có sự cố. Việc bảo đảm độ tin cậy cao có tầm quan trọng khi sử dụng máy tính trong các lĩnh vực mà sự cố có thể xảy ra thảm hoạ như điều khiển phóng vệ tinh, kiểm soát và điều khiển các nhà máy điện nguyên tử. . v. v. Tuy nhiên, để khai thác được sức mạnh tiềm tàng trong các máy tính song song lớn yêu cầu sự phát triển và kết hợp hợp lý của kiến trúc, hệ điều hành, ngôn ngữ lập trình và giải thuật, phần mềm tính toán song song. Bởi vì giải thuật tuần tự không còn phù hợp nữa khi thực hiện trên máy song song, nên việc xây dựng, thiết kế giải thuật song song là điều quan trọng từ đó có thể phân rã công việc trên các phần tử xử lý khác nhau. Việc phân rã có thể được tiến hành theo hai cách, phân rã theo miền và phân rã theo chức năng. Tiếp theo là mã hoá công việc đó theo một ngôn ngữ hỗ trợ việc tính toán song song và hệ điều hành điều khiển hoạt động tính toán phải có sự hỗ trợ. Nếu trong quá trình tính toán mà lựa chọn không tốt kiến trúc song song sẽ làm cho hiệu quả thực hiện giảm đi. Để xây dựng một giải thuật song song ta phải có sự phân tích bài toán hoặc giải thuật tuần tự, từ đó cho phép ta có kết luận có thể song song bài toán hay không. Nếu được, ta sẽ tiếp tục xây dựng giải thuật bằng cách phân rã bài toán ra thành các công việc nhỏ, xây mối liên hệ giữa các công việc, quyết định được có thể song song được những tác vụ nào, sau đó ấn định vào mô hình máy tính song song cụ thể. Trong khi xây dựng có thể có nhiều phương hướng thiết kế khác nhau tạo ra các giải thuật khác nhau. Việc đánh giá hiệu quả của từng giải thuật cho phép ta quyết định giải thuật nào sẽ được áp dụng dựa trên mô hình hiệu năng. Để đánh giá tốt hiệu quả giải thuật, chúng ta cần xem xét các chỉ tiêu như tốc độ ( Speedup), hiệu quả (Efficiency), linh động ( Scalability). Điều này cần có kiến thức về tính toán độ phức tạp giải thuật, tổ chức mạng kết nối giữa các phần tử xử lý, chi phí truyền thông giữa các phần tử trong giải thuật. Những vấn đề này sẽ được đề cập trong đồ án tốt nghiệp với mong ước góp phần nhỏ bé của mình vào việc phát triển nghiên cứu về lĩnh vực tính toán song song. Đề tài cho đồ án tốt nghiệp là : “ Thiết kế giải thuật song song” Nhiệm vụ của đồ án bao gồm: Tìm hiểu kỹ thuật tổ chức giải thuật tính toán song song. Nghiên cứu các vấn đề liên quan đến phương pháp phân rã bài toán, phục vụ cho việc xây dựng giải thuật song song và đánh giá được các phương pháp phân rã. áp dụng cho bài toán giải hệ phương trình tuyến tính bằng phương pháp phân rã LU. Đưa ra các giải thuật song song cho bài toán và đánh giá hiệu quả của các giải thuật. Mô phỏng một số giải thuật phân rã bài toán giải hệ phương trình tuyến tính. Nội dung của đồ án tốt nghiệp gồm 5 chương và tài liệu tham khảo. Chương 1 sẽ đề cập tổng quan về tính toán song song với các vấn đề liên quan đến việc thiết kế giải thuật song song như các mô hình tính toán song song, kiến trúc bộ nhớ máy tính song song, các mô hình lập trình song song. Chương 2 đề cập đến mô hình thiết kế giải thuật, các công đoạn trong quá trình thiết kế. Trong mỗi công đoạn sẽ đưa ra được những vấn đề cần quan tâm cho người thiết kế. Chương 3 sẽ đề cập đến mạng kết nối giữa các bộ xử lý và đi sâu vào vấn đề ánh xạ tĩnh các tác vụ phân rã theo miền vào kiến trúc máy tính song song cụ thể. Chương 4 đề cập đến mô hình hiệu năng đánh giá hiệu quả của giải thuật song song sau khi thiết kế và phân tích tính qui mô của giải thuật. Những đánh giá này sẽ giúp cho người thiết kế có khả năng chọn lựa giải thuật trong công đoạn thiết kế. Chương 5 sẽ đi sâu thiết kế giải thuật song song cho bài toán giải hệ phương trình tuyến tính theo phương pháp tách LU. Mô phỏng một số giải thuật và thử nghiệm một số bài toán giải hệ.  Chương I Tổng quan về tính toán song song Trong chương này đề cập sơ lược đến các vấn đề cơ bản trong tính toán song song như phân loại kiến trúc song song của Flynn, kiến trúc bộ nhớ, mô hình lập trình song song. v. v. v, qua đây sẽ đưa đến cái nhìn tổng quan để định hướng khi thiết kế giải thuật. 1. 1 Kiến trúc Von Neumann Hơn 40 năm qua, hầu hết các máy tính đều thiết kế dựa theo mô hình phổ biến được biết đến như máy Von Neumann. Tên máy tính được đặt theo tên nhà toán học người Hungarian Jon Von Neumann. Máy tính Von Neumann sử dụng khái niệm chương trình lưu trữ ( stored-program), CPU sẽ thực hiện theo dãy các phép toán đọc, ghi trên bộ nhớ do chương trình lưu trữ chỉ định. Memory CPU Fetch Execute Hình 1. 1: Mô tả kiến trúc Von Neumann Đối với kiến trúc Von Neumann thì bộ nhớ được sử dụng để lưu trữ cả lệnh cho chương trình lẫn dữ liệu. Lệnh chương trình là dữ liệu đã được mã hoá, chương trình sẽ dựa vào đây để thực hiện, còn dữ liệu đơn giản chỉ là thông tin được chương trình sử dụng. Khi đó CPU sẽ lấy các lệnh hay dữ liệu từ bộ nhớ, giải mã các lệnh và sau đó thực hiện tuần tự các lệnh này. 1. 2. Phân loại Flynn Một trong những phân loại kiến trúc máy tính song song được biết nhiều nhất là phân loại của Flynn, được sử dụng từ năm 1966. Michael Flynn phân loại kiến trúc máy tính thành 4 loại dựa trên sự biểu hiện của cặp khái niệm : dòng lệnh ( instruction stream) và dòng dữ liệu ( data stream), mỗi loại nằm trong một trong hai trạng thái là Đơn (Single) hoặc Đa( Multiple). Theo Flynn các kiến trúc máy tính gồm 4 loại được thể hiện trong ma trận sau: SISD Single Instruction Single Data SIMD Single Instruction Multiple Data MISD Multiple Instruction Single Data MIMD Multiple Instruction Multiple Data Hình 1. 2: Mô tả phân loại kiến trúc của Flynn Đơn dòng lệnh đơn dòng dữ liệu (SISD). Đây là kiến trúc của một máy tuần tự, trong bất kỳ một chu kỳ đồng hồ nào chỉ có một dòng lệnh đang được thực hiện bởi CPU và chỉ một dòng dữ liệu đang được sử dụng như là đầu vào cho chương trình. Kiến trúc này chỉ sử dụng một thanh ghi được gọi là bộ đếm chương trình để đảm bảo cho dòng lệnh được thực hiện tuần tự. Kiến trúc này được sử dụng cho hầu hết các máy tính cá nhân, các workstation và mainframe đơn CPU. Hình 1. 3. Mô tả kiến trúc SISD Đơn dòng lệnh đa dòng dữ liệu ( SIMD). Với kiến trúc này, tất cả các đơn vị xử lý sẽ thực hiện cùng một lệnh tại bất kỳ chu kỳ đồng hồ nào nhưng mỗi đơn vị này có thể thao tác trên một phần tử dữ liệu khác nhau. Trong kiến trúc này thường có một đơn vị điều khiển lệnh ( Control Unit ), có mạng kết nối bên trong giữa các đơn vị xử lý, có băng thông rất lớn và mảng rất lớn các đơn vị lệnh có dung lượng rất nhỏ. Kiến trúc này đặc biệt phù hợp cho các bài toán có mức độ đồng đều cao như trong lĩnh vực xử lý ảnh. Kiến trúc này là cơ sở xây dựng các máy tính song song kiểu bộ xử lý mảng ( array processor) như Connection Machine CM-2, Maspar MP-1, MP-2. Hình 1. 4. Mô tả kiến trúc SISD Đa dòng lệnh đơn dòng dữ liệu ( MISD). Kiến trúc này cho phép một vài lệnh cùng thao tác trên cùng một dữ liệu. Có rất ít máy tính song song dựa trên kiến trúc này. Có hai cách để mô tả cách tổ chức của MISD. Cách thứ nhất được xét đến các lớp máy yêu cầu các đơn vị xử lý riêng nhận các lệnh riêng biệt xử lý trên cùng một dữ liệu. Cách thức thứ 2 được xét đến lớp các máy tính, trong đó dữ liệu chuyển qua một dãy các đơn vị xử lý. Đa dòng lệnh đa dòng dữ liệu (MIMD). Hiện nay, đây là kiến trúc song song phổ biến nhất với mỗi bộ xử lý có thể thực hiện một dòng lệnh và một dòng dữ liệu khác nhau. Hầu hết các máy tính supercomputer, máy tính Multicomputer và Multiprocessor đều được xây dựng dựa trên kiến trúc này. Hình 1. 4 Mô tả kiến trúc MIMD 1. 3 Các kiến trúc bộ nhớ máy tính song song Có 3 kiến trúc bộ nhớ cơ bản là dùng chung ( shared memory), phân tán ( distributed memory) và kết hợp giữa hai kiến trúc trên Hybrid ( distributed-shared memory). 1. 3. 1 Bộ nhớ dùng chung Các máy tính song song dùng chung có nhiều dạng, biến đổi trong phạm vi rộng nhưng có đặc điểm chung là khả năng cho các bộ xử lý truy nhập tới toàn bộ nhớ như là không gian địa chỉ toàn cục( global address space). Hình 1. 5 Mô tả máy tính song song bộ nhớ dùng chung Các bộ xử lý có thể thao tác một cách độc lập nhưng chia sẻ cùng tài nguyên bộ nhớ, sự thay đổi trong một vị trí bộ nhớ bởi một bộ xử lý thì tất cả các bộ xử lý còn lại sẽ nhận thấy được. Tuy nhiên còn có thể phân ra thành 2 loại chính dựa vào thời gian truy nhập bộ nhớ là truy nhập bộ nhớ đồng bộ- UMA ( Uniform Memory Access) và truy nhập bộ nhớ không đồng bộ-NUMA ( Non-Uniform Memory Access). Thuận lợi của mô hình này là lập trình thân thiện đối với người sử dụng với việc chia sẻ dữ liệu, môi trường tính toán ổn định nhưng kém linh động giữa bộ nhớ và các CPU. Nếu thêm nhiều CPU ta sẽ gặp phải các vấn đề do tăng dung lượng trên đường truyền thông giữa bộ nhớ và bộ nhớ, quản lý đồng bộ việc truy nhập đồng thời của các bộ xử lý đến cùng vị trí bộ nhớ, truy nhập có chính xác vị trí bộ nhớ trên không gian bộ nhớ dùng chung. Ngoài ra sẽ chi phí rất tốn kém để thiết kế và sản xuất các máy tính kiểu này khi gia tăng số lượng bộ xử lý. 1. 3. 2 Bộ nhớ phân tán Cũng như kiến trúc dùng chung, kiến trúc phân tán có nhiều dạng nhưng chia sẻ một đặc điểm chung là hệ thống bộ nhớ phân tán yêu cầu một mạng truyền thông kết nối giữa bộ nhớ bộ xử lý. Hình 1. 6 Mô tả kiến trúc bộ nhớ phân tán Mỗi bộ xử lý đều có bộ nhớ cục bộ riêng, địa chỉ bộ nhớ không ánh xạ tới các bộ xử lý khác, bởi vậy không có khái niệm không gian địa chỉ toàn cục ngang qua tất cả bộ xử lý. Các bộ xử lý sẽ thao tác độc lập trên bộ nhớ riêng của nó. Sự thay đổi dữ liệu tạo ra đối với bộ nhớ riêng không ảnh hưởng đến bộ nhớ của các bộ xử lý khác, bởi vậy không có sự đụng độ do truy nhập đồng thời từ nhiều bộ xử lý. Khi một bộ xử lý cần truy nhập đến dữ liệu trong bộ xử lý khác hoặc hai bộ xử lý cần trao đổi dữ liệu cho nhau thì cần có truyền thông giữa chúng qua mạng kết nối. Thuận lợi của kiến trúc này là bộ nhớ khả chuyển với số lượng bộ xử lý, gia tăng số lượng bộ xử lý và kích thước bộ nhớ tỷ lệ với nhau. Chí phí xây dựng máy tính không lớn, có thể dùng hệ thống mạng máy tính sẵn có. Tuy nhiên, kiến trúc này sẽ khó khăn cho người lập trình bởi cần có những công đoạn thực hiện truyền thông giữa các máy tính khi trao đổi dữ liệu, việc ánh xạ cấu trúc dữ liệu hiện có lên kiến trúc bộ nhớ của máy tính và thời gian truy nhập dữ liệu không đồng bộ. 1. 3. 3 Bộ nhớ kết hợp Ngày nay, các máy tính song song lớn nhất và nhanh nhất cung cấp cả kiến trúc bộ nhớ chung và phân tán. Mô hình này hình thành dựa theo việc liên kết nhiều máy tính song song kiến trúc bộ nhớ chung thành máy tính lớn hơn thông qua mạng truyền thông. Hình 1. 7. Mô tả kiến trúc bộ nhớ kết hợp Kiến trúc này kết hợp ưu và nhược điểm của cả hai kiến trúc trên. 1. 4 Các mô hình lập trình song song Mô hình lập trình cung cấp cho người lập trình cái nhìn đơn giản và trong suốt với hệ thống phần cứng và phân mềm của máy tính. Các mô hình lập trình song song được thiết kế chuyên dụng cho các mô hình máy tính song song điển hình như Multiprocessors, Multicomputers và Array Processor. Đơn vị song song trong các mô hình lập trình là tiến trình ( process) hay tác vụ (task) tương ứng với các thao tác thực hiện bởi đoạn mã lệnh tuần tự, độ lớn đoạn mã lệnh này thay đổi trong các ứng dụng và mô hình lập trình khác nhau. Ngoài ra còn có một số mô hình lập trình khác như hướng đối tượng, song song theo logic. 1. 4. 1 Lập trình bộ nhớ dùng chung Trong mô hình này được thiết kế cho máy tính Multiprocessors, các tác vụ chia sẻ không gian địa chỉ dùng chung, được đọc/ghi một cách không đồng bộ. Có một số kỹ thuật như khoá (locks) hay cờ(semaphores) được sử dụng để điều khiển truy nhập đến bộ nhớ dùng chung. Truyền thông giữa các tác vụ thông qua các biến dùng chung. Shared Memory Task A Task C Task B Hình 1. 8: Mô tả truyền thông giữa các tác vụ sử dụng biến dùng chung Hiện nay, mô hình này được hỗ trợ theo các cáh khác nhau trong hầu hết các hệ điều hành 32-bit, điển hình trong các thư viện liên kết của Unix có hỗ trợ việc tạo các tiến trình, khối bộ nhớ dùng chung, cờ và kỹ thuật truyền thông giữa các tiến trình. 1. 4. 2 Truyền thông điệp Trong máy tính Multicomputers cung cấp kỹ thuật truyền thông điệp ( message passing) để trao đổi giữa các tác vụ. Hai tác vụ nằm trên hai máy khác nhau có thể trao đổi với nhau bằng kỹ thuật truyền thông điệp trên mạng kết nối. Các thông điệp có thể là các lệnh, dữ liệu, tín hiệu đồng bộ hay ngắt. Hai mô hình truyền thông điệp được thực thi và sử dụng là đồng bộ hay không đồng bộ. Hình 1. 9 Mô tả truyền thông giữa hai tác vụ trên hai máy tính khác nhau Hiện nay, PVM và MPI là hai mô hình lập trình song song điển hình sử dụng kỹ thuật mày. 1. 4. 3 Mô hình song song dữ liệu Trong mô hình này, hầu hết các công việc song song đều tập trung thực hiện các phép toán trên một tập dữ liệu. Tập dữ liệu này thường được tổ chức trong một cấu trúc dữ liệu thông dụng như mảng hoặc khối. Một tập tác vụ sẽ làm việc trên cùng cấu trúc dữ liệu nhưng mỗi tác vụ sẽ làm việc trên một phần dữ liệu khác nhau với cùng phép toán. Mô hình này thiết kế chủ yếu dành cho máy tính song song kiểu bộ xử lý mảng (array processor) Hình 1. 10 Mô tả mô hình song song dữ liệu 1. 4. 4 Mô hình hướng đối tượng Trong mô hình này, ánh xạ các đơn vị thực hiện vào các đối tượng. Các đối tượng được tạo ra và thao tác theo cách tự động, việc xử lý được thực hiện thông qua gửi và nhận giữa các đối tượng. Các mô hình lập trình hiện nay đều xây dựng các đối tượng từ mức thấp như tiến trình, tác vụ, hàng đợi và cờ tín hiệu đến mức cao như monitor hay module chương trình. Các ngôn ngữ lập trình song song hướng đối tượng như CORBA, DCE, JAVA, CC++ 1. 4. 5 Mô hình logic Dựa trên cơ sở logic tiên đề, lập trình logic phù hợp cho xử lý trí thức giải quyết cơ sở tri thức lớn. Mô hình này chấp nhận một chiến lược tìm kiếm ẩn và hỗ trợ song song trong xử lý suy luận logic. Một câu hỏi được trả lời nếu hợp với các sự kiện được tìm thấy trong cơ sở dữ liệu. Hai sự kiện hợp nhau nếu tiền đề của chúng và các đối kết hợp là như nhau. Xử lý việc hợp và thống nhất có thể được song song dưới các điều kiện chắc chắn. Mô hình này được áp dụng song song cho các ứng dụng trí tuệ nhân tạo. 1. 5 Truyền thông trong mô hình Multicomputer Nét nổi bật giữa các máy tính Multicomputer trước đây và các hệ thống ngày nay là sự thay đổi cách thức truyền thông giữa các bộ xử lý. Thế hệ đầu tiên cuả mô hình Multicomputer, như Intel iPSC/10 , nCUBE/10 và các hệ thống dựa trên T800 Transputerr , được đặc trưng bởi phần mềm quản lý truyền thông điệp store and forward ( store and forward message passing). Để gửi một message từ một bộ xử lý tới một bộ xử lý không liền kề, mỗi bộ xử lý trung gian dọc theo đường truyền message phải lưu trữ toàn bộ message sau đó đẩy message xuống đường truyền tới bộ xử lý tiếp theo. Thậm chí truyền dữ liệu được hoàn thành thông qua các kênh DMA thì CPU bị ngắt mỗi lần truyền theo kiểu DMA được khởi tạo. Processor 1 Processor 1 Y Processor 1 T Y Processor 1 R T Y Processor 2 E Processor 2 E R Processor 2 E R T Y Processor 2 E R T Processor 3 Processor 3 Processor 3 Processor 3 R T Y Processor 1 Processor 1 Processor 1 Processor 1 Processor 2 Processor 2 R T Y Processor 2 T Y Processor 2 Y Processor 3 E Processor 3 E R Processor 3 E R T Processor 3 E R T Y Hình1. 11 Mô tả cơ chế định đường store and forward Ngược lại, đối với các mô hình máy tính song song thế hệ thứ hai, chẳng hạn như Intel iPSC/2, và nCUBE 2, có cơ chế định đường message chuyển mạch. Chẳng hạn như mỗi nút trong mô hình iPSC/2 và iPSC/860 có một Card con logic định đường gọi là module kết nối trực tiếp (Direct –Connect Module). Các module kết nối trưc tiếp thiết lập một mạch từ nút nguồn đến nút đích. Mỗi lần mạch được thiết lập, message truyền trong một dạng được pipeline từ nút nguồn tới nút đích mà không có một nút trung gian nào lưu message này. Khi một message được truyền từ một nút tới một nút không liền kề thì không cần ngắt CPU của các nút trung gian và chỉ tác động vào các module kết nối trực tiếp. Hình dưới đây mô tả cơ chế này. 80386 Numeric Coprocessor Memory Direct-Connect Routing Module 80386 Numeric Coprocessor Memory Direct-Connect Routing Module 80386 Numeric Coprocessor Memory Direct-Connect Routing Module Hình 1. 12 Mô tả các module kết nối trực tiếp trên máy tính Intel iPSC/2 hỗ trợ cơ chế định đường message. Cơ chế truyền thông khác nhau sẽ ảnh hưởng rất nhiều đến tính toán chi phí truyền thông trong khi thiết kế giải thuật. Sau chương đầu tiên, ta đã tìm hiểu được sơ bộ các kỹ thuật tổ chức giải thuật tính toán song song khác nhau phụ thuộc vào mô hình máy tính cụ thể. Những tìm hiểu này là cơ sở đi vào lĩnh vực tính toán song song, tạo bước nền trước khi đi vào thiết kế giải thuật song song trong chương sau.  Chương 2 Thiết kế Giải Thuật song song Trong chương này đề cập đến phương pháp thiết kế giải thuật song song cho bài toán, quá trình thiết kế không dễ dàng để có thể rút gọn thành công thức đơn giản như công thức giải hệ phương trình bậc hai, giải hệ phương trình tuyến tính. v. v. mà yêu cầu có sự sắp xếp tư duy thông nhất mà thường được đề cập đến như là sự “sáng tạo”. Mục đích của chương này là đưa ra một khung thiết kế, một sự đánh giá mang tính toán học nhằm giảm bớt những chi phí do phải quay lui lại sau khi lựa chọn phương án không hợp lý. 2. 1 Mô hình thiết kế Trong mô hình thiết kế này, đơn vị để thực hiện song song là tác vụ. Mỗi tác vụ bao gồm chương trình thực hiện tuần tự và bộ nhớ cục bộ. Khi đó tính toán song song là thực hiện đồng thời hai hay nhiều tác vụ, số lượng tác vụ có thể biến đổi trong suốt thời gian thực hiện chương trình. Các tác vụ có thể ánh xạ tới các bộ xử lý theo nhiều cách khác nhau, trong đó nhiều tác vụ có thể ánh xạ lên cùng một bộ xử lý. Các tác vụ được kết nối với nhau thông qua các kênh truyền (chanel) và thực hiện việc gửi và nhận các message trên kênh. Để thực hiện việc kết nối đồng thời với nhiều tác vụ khác, một tác vụ sẽ có thêm một tập các cổng vào, ra, mỗi cổng sẽ giao tiếp với một tác vụ khác. Tác vụ gửi sẽ đặt các message lên kênh tại cổng ra, còn tác vụ nhận thì xoá bỏ message trên kênh thông qua cổng vào. Phép toán gửi là không đồng bộ, dữ liệu được gửi đi ngay lập tức, trong khi đó phép toán nhận thì đồng bộ, bởi vậy việc thực hiện tác vụ sẽ dừng lại cho đến khi message được nhận. Khi không còn message thì kênh truyền sẽ bị huỷ bỏ. Hình 2. 1 Mô tả kết nối giữa các tác vụ. Sự đóng gói đối với tác vụ cho ta thấy tính cục bộ, dữ liệu nằm trong bộ nhớ cục bộ của tác vụ ta gọi đó là dữ liệu “gần”, còn dữ liệu khác là dữ liệu “xa”. Trong khi đó, kênh truyền sẽ chỉ ra sự phụ thuộc dữ liệu giữa các tác vụ trong khi quá trình tính toán. Bởi vì các tác vụ giao tác với nhau sử dụng kỹ thuật kênh truyền mà không quan tâm đến việc định vị tác vụ, do đó kết quả tính toán bởi một chương trình không phụ thuộc vào nơi mà tác vụ thực hiện. Các giải thuật phải được thiết kế và thực thi mà không quan tâm đến số lượng bộ xử lý trên máy tính song song sẽ thực hiện bài toán. Thông thường việc thiết kế bài toán sẽ tạo ra số tác vụ lớn hơn nhiều so với số bộ xử lý, điều này sẽ làm cho giải thuật đạt được khả năng linh động cao và có thể xen kẽ giữa tính toán và truyền thông để tăng hiệu năng. Các kênh truyền kết nối giữa các tác vụ có thể hoặc không tương ứng với đường kết nối giữa các bộ xử lý trong mạng. Hai tác vụ trao đổi dữ liệu thông qua kênh truyền có thể được ấn định tới: Trên cùng một bộ xử lý, khi đó không cần truyền thông trên mạng. Nằm trên hai bộ xử lý được kết nối trực tiếp, khi đó chỉ truyền thông trực tiếp giữa hai bộ xử lý. Nằm trên hai bộ xử lý không kết nối trực tiếp, khi đó yêu cầu định đường message trên mạng. 2. 2 Phương pháp thiết kế Hầu hết các bài toán lập trình đều có một vài lời giải song song. Phương án tốt nhất có thể khác so với phương án được đề nghị bởi các giải thuật tuần tự đang tồn tại. Phương pháp thiết kế đưa ra ở đây có xu hướng tiếp cận ban đầu trên mô hình độc lập với máy tính song song, vấn đề đựợc chú trọng là tính đồng thời và các khía cạnh thiết kế trên kiến trúc máy tính cụ thể được đề cập sau trong tiến trình thiết kế. Phương pháp này hình thành lên tiến trình thiết kế gồm có 4 công đoạn: phân rã, truyền thông, tích tụ và ánh xạ. Trong hai công đoạn đầu, chúng ta chú trọng vào tính đồng thời và linh động, tìm kiếm để khám phá giải thuật với những tiêu chuẩn này. Trong hai công đoạn sau, thứ 3 và 4, chuyển tập trung sang tính cụ bộ và các vấn đề liên quan đến hiệu năng khác. Bốn công đoạn được tóm lược và mô tả như sau: Phân rã (Partitioning ): Công việc tính toán và dữ liệu được phân rã thành các tác vụ nhỏ. Trong công đoạn này chúng ta bỏ qua các vấn đề thực tế như truyền thông, số bộ xử lý trên máy đích. Chúng ta chỉ tập trung vào vấn đề nhận ra được các khả năng để thực thi song song. Truyền thông (Communication ): Sau khi phân rã bài toán thành các tác vụ nhỏ, yêu cầu về truyền thông giữa các tác vụ được đặt ra. Trong công đoạn này cũng xác định các cấu trúc và giải thuật truyền thông thích hợp. Tích tụ ( Agglomeration). Các cấu trúc truyền thông và tác vụ được định nghĩa trong hai công đoạn đầu của quá trình thiết kế được đánh giá đối với yêu cầu hiệu năng và chi phí thực thi. Trong công đoạn này, các tác vụ có thể được tích tụ vào trong tác vụ lớn hơn nhằm năng cao hiệu năng hoặc giảm chi phí khác. ánh xạ ( Mapping). ấn định các tác vụ vào trong bộ xử lý, mục đích là cố gắng thoả mãn hai mục tiêu đối ngược nhau : cực đại hoá khả năng của bộ xử lý và cực tiểu hoá chi phí truyền thông. ánh xạ có thể thực hiện tĩnh trước khi tính toán hoặc tự động trong thời gian thực hiện bởi các giải thuật cân bằng tải. Hình 2. 2 : Mô tả các công đoạn thiết kế giải thuật song song. Kết quả của quá trình thiết kế là hướng đến một chương trình có thể tạo ra hoặc huỷ bỏ các tác vụ một cách tự động, sử dụng các kỹ thuật cân bằng tải để điều khiển ánh xạ các tác vụ đến các bộ xử lý. Các công đoạn thiết kế giải thuật được trình bày ở đây thực hiện tuần tự. Tuy nhiên, trong thực tế đây là tiến trình song song mức cao, với nhiều vấn đề liên quan được xem xét đồng thời. Mặc dù chúng ta tìm kiếm để tránh quay lui nhưng việc đánh giá từng phần hoặc toàn bộ thiết kế có thể yêu cầu thay đổi quyết định thiết kế được tạo ra trong các công đoạn trước đó. Chi tiết của bốn công đoạn sẽ được trình bày trong các mục tiếp theo, trong đó sẽ tìm hiểu sâu về công đoạn và vấn đề cần quan tâm khi thiết kế giải thuật. 2. 3 Phân rã Mục đích của công đoạn này là khám phá đến mức tối đa khả năng song song của bài toán, do đó chú trọng đến việc định nghĩa một tập lớn các tác vụ nhỏ không có sự liên kết, được gọi là các tác vụ fine-grain. Khi đó, khối lượng công việc được thực hiện thông qua truyền thông giữa các tác vụ là không có. Khi phân rã một giải thuật, người thiết kế đầu tiên thường chú trọng nhất về dữ liệu kết hợp với một bài toán, sau đó xác định một phân rã thích hợp cho dữ liệu và công việc cuối cùng là kết hợp tính toán với dữ liệu như thế nào. Kỹ thuật này được gọi là phân rã theo miền ( domain decomposition). Một cách tiếp cận khác là phân rã tính toán được thực hiện đầu tiên và sau đó kết hợp dữ liệu với tính toán - được gọi là phân rã theo chức năng( functional decomposition). 2. 3. 1. Phân rã theo miền Thông thường, hướng tiếp cận này quan tâm đến phân chia dữ liệu của bài toán. Nếu có thể, chúng ta phân chia dữ liệu thành các phần nhỏ có kích thước xấp xỉ nhau. Tiếp theo phân chia tính toán được thực hiện. Thông thường là kết hợp mỗi phép toán với phần dữ liệu mà phép toán thao tác trên đó. Việc phân chia này thường đem lại một số lượng lớn tác vụ, mỗi tác vụ bao gồm một số dữ liệu và một tập các phép toán thực hiện trên dữ liệu này. Khi phép toán yêu cầu dữ liệu từ một vài tác vụ khác thì dữ liệu sẽ được vận chuyển giữa các tác vụ thông qua truyền thông. Yêu cầu này sẽ được chỉ ra trong pha tiếp theo của tiến trình thiết kế. Hình 2. 3 Mô tả phân rã bài toán theo miền Dữ liệu được phân rã có thể là đầu vào, đầu ra hay các giá trị trung gian của chương trình. Có thể có các phân rã khác nhau dựa trên cấu trúc dữ liệu khác nhau hoặc cấu trúc dữ liệu được truy xuất tuần tự nhất. Các pha khác nhau của tính toán có thể thao tác trên các cấu trúc dữ liệu khác nhau hoặc yêu cầu phân rã khác nhau trê._.n cùng một cấu trúc dữ liệu. Trong trường hợp này, ta nên xem xét mỗi pha một cách riêng biệt và sau đó xác định các giải thuật phân rã và song song phát triển cho mỗi pha phù hợp cùng nhau. Ví dụ ta cần phân rã một bài toán đơn giản liên quan đến khung lưới 3 chiều như bài toán mô hình thời tiết, khung lưới 3 chiều thể hiện trạng thái của khí quyển hoặc thể hiện không gian 3 chiều trong bài toán xử lý ảnh. Tính toán được lặp lại trên mỗi điểm của khung lưới. Khi đó phân rã bài toán có thể theo 1, 2 hoặc 3 chiều x, y, z. Tuy nhiên trong công đoạn đầu tiên này, người thiết kế thường quan tâm đến phân rã có tính linh hoạt nhất và khi đó mỗi tác vụ sẽ được xác định tương ứng cho mỗi điểm. Hình 2. 4 Mô tả các phương pháp phân rã theo miền khác nhau cho bài toán liên quan đến khung lưới 3 chiều. 2. 3. 2 Phân rã chức năng Phân rã chức năng cho ta một hướng nhìn khác, mang tính bổ xung về bài toán. Trong hướng tiếp cận này, người thiết kế chú trọng đầu tiên vào tính toán được thực hiện hơn là dữ liệu được thao tác bởi phép tính. Nếu hướng tiếp cận này thành công, sẽ phân chia quá trình tính toán thành các tác vụ riêng rẽ. Sau đó ta sẽ tiến hành kiểm tra yêu cầu dữ liệu cho những tính toán của tác vụ này. Khi yêu cầu dữ liệu riêng rẽ nhau thì phân chia là hoàn toàn, còn không thì có thể yêu cầu vận chuyển dữ liệu giữa các tác vụ để tránh lặp lại dữ liệu. Việc lặp lại dữ liệu sẽ được giải quyết thông qua việc phân rã theo miền. Hình 2. 4 Mô tả phân rã bài toán theo chức năng Một ví dụ quen thuộc cho phương pháp phân rã theo chức năng là bài toán mô hình tính toán thời tiết. Xác định thời tiết thông qua việc tổng hợp dữ liệu từ các mô hình thành phần là : mô hình khí quyển ( Atmospheric Model), mô hình thuỷ học(Hydrology Model ), mô hình mặt đất( Land Surface Model) và mô hình đại dương( Ocean Model). Hình 2. 5 Mô tả phân rã chức năng trong mô hình tính toán thời tiết Khi đó, mỗi thành phần chức năng có thể xem như là một tác vụ riêng biệt và tiếp tục được song song bởi phân rã theo miền đối với dữ liệu tương ứng cho từng tác vụ. Các mũi tên biểu hiện sự trao đổi dữ liệu giữa các thành phần trong suốt thời gian tính toán chẳng hạn như mô hình khí quyển tạo ra ra dữ liệu về tốc độ gió sẽ được sử dụng trong tính toán của mô hình đại dương, mô hình đại dương tạo ra dữ liệu về nhiệt độ mặt biển sẽ được sử dụng trong mô hình khí quyển. Đối với hầu hết các giải thuật song song thì phân rã theo miền hình thành cơ bản cho giải thuật. Phân rã chức năng chỉ được đánh giá là cách nhìn khác về bài toán, bổ xung cho phương pháp phân rã theo miền. Tuy nhiên đối với các bài toán phức tạp thì phân rã theo miền cũng đóng vai trò quan trọng như là một kỹ thuật để cấu trúc chương trình, đơn giản hoá bài toán phức tạp bằng tập các bài toán đơn giản hơn, liên kết với nhau. Phân rã chức năng sẽ giảm bớt được đáng kể chi phí thiết kế. Giải thuật song song tốt sẽ kết hợp được cả phương pháp phân rã theo miền và phân rã theo chức năng. Trong công đoạn phân rã, đôi khi giải thuật tuần tự không thể hiện cho ta khả năng song song. Khi đó cần có sự phân tích theo các hướng khác nhau về bài toán, ta mới có thể phân rã được. Một ví dụ điển hình là bài toán tính số đỉnh của một cây duyệt theo thứ tự trước. Nếu nhìn vào giải thuật tuần tự, ta thấy bài toán có vẻ tuần tự vốn có. Bởi vì, chúng ta không thể gán nhãn cho các nút bên phải khi chưa biết bao nhiêu nút ở cây bên trái và cũng không thể gán nhãn cho các nút ở cây con bên phải của cây con bên trái và cứ thế. Ta hãy xem xét mô tả đệ qui về bài toán này. PREORDER. TRAVERSAL (nodeptr): Begin If nodeptr null then nodecount nodecount + 1 nodeptr. label nodecount PREORDER. TRAVERSAL (nodeptr. left) PREORDER. TRAVERSAL(nodeptr. right) Endif End Để có thể chuyển sang giải thuật song song, ta hãy xem xét bài toán trên quan điểm khác. Quan điểm về lưu trữ dữ liệu, về mối liên hệ giữa các nút. Thay vì chú trọng đến các đỉnh (vertices) của cây, ta quan tâm đến các cạnh (edges). Khi thực hiện duyệt theo thứ tự trước, giải thuật sẽ tiến hành một cách hệ thống thông qua tất cả các cạnh của cây. Thực tế, giải thuật duyệt cây dọc theo mỗi cạnh hai lần, lần thứ nhất từ đỉnh cha tới đỉnh con, sau đó thì duyệt ngược lại. Nếu chia mỗi cây thành hai cây, một cây ứng với duyệt từ trên xuống còn cây kia ứng với duyệt trở lại. Khi đó, bài toán duyệt cây sẽ chuyển sang bài toán duyệt một danh sách liên kết đơn, bài toán này có thể phân rã để thực hiện song song được. D A C B F G E H A C B F G D E H Hình 2. 6 Mô tả phương pháp phân rã bài toán tính số đỉnh cây duyệt theo thứ tự trước 2. 3. 3 Các vấn đề cần quan tâm Trong công đoạn này, ta nên đưa ra một hoặc nhiều hướng phân rã cho một bài toán. Trước khi tiến hành đánh giá các yêu cầu truyền thông, ta nên xem xét các vấn đề được liệt kê dưới đây để tránh gặp phải những sai sót không dễ nhận ra trong quá trình thiết kế. Hầu hết công việc của bài toán khoa học và kỹ thuật lớn thường được hoàn thành trong một số đoạn mã, người ta thường gọi đó là các “hotspots” của bài toán. Khi phân rã bài toán, ta lên chú trọng vào các đoạn mã này, bỏ qua các đoạn mã chiếm thời gian CPU không đáng kể. Phân chia bài toán thành các tác vụ với số lượng lớn hơn nhiều so với số bộ xử lý. Nếu không, sự linh hoạt khi áp dụng vào mô hình cụ thể sẽ không có. Tránh yêu cầu tính toán và lưu trữ dư thừa. Bởi nếu không sẽ không có khả năng mở rộng đối với các bài toán lớn hơn. Ta có thể so sánh được kích thước của các tác vụ, nếu không sẽ khó khăn khi ta định vị số lượng ngang nhau giữa các bộ xử lý. Số lượng tác vụ phải linh hoạt với kích thước bài toán, nếu không có thể khó giải bài toán lớn hơn khi có nhiều bộ xử lý hơn. 2. 4 Truyền thông Các tác vụ được tạo ra trong công đoạn phân rã có xu hướng được thực hiện đồng thời nhưng nhìn chung không thể thực hiện một cách độc lập. Tính toán được thực hiện trong một tác vụ thường sẽ yêu cầu dữ liệu kết hợp với tác vụ khác. Sau đó, dữ liệu phải được truyền giữa các tác vụ để cho phép tính toán được thực hiện. Luồng thông tin này được chỉ ra trong công đoạn truyền thông của một tiến trình thiết kế. Trong mô hình thiết kế, ta đã khái niệm hoá truyền thông giữa hai tác vụ như một kênh kết nối, trên đó một tác vụ có thể được gửi và những tác vụ khác có thể nhận. Bởi vậy, truyền thông kết hợp với một giải thuật có thể được chỉ ra trong hai pha. Đầu tiên là xác định cấu trúc kênh là trực tiếp hoặc không trực tiếp kết nối các tác vụ yêu cầu dữ liệu ( consumers) với các tác vụ chiếm giữ dữ liệu ( producers). Thứ hai, chỉ ra các message được gửi và nhận trên những kênh này. Việc định nghĩa ra các kênh truyền sẽ làm phức tạp bài toán còn gửi message sẽ tăng chi phí truyền thông. Bởi vậy, chúng ta tránh đưa ra các kênh và phép toán truyền thông không cần thiết. Hiệu năng có thể năng cao bằng cách phân tán các phép toán truyền thông trên nhiều tác vụ và tổ chức các phép toán truyền thông sao cho có thể thực hiện đồng thời. Trong các bài toán phân rã theo miền, có thể sẽ khó khăn khi xác định yêu cầu truyền thông bởi vì ta không nhận thấy được sự phụ thuộc dữ liệu giữa các tác vụ. Sau khi thực hiện công đoạn phân rã sẽ hình thành ra tập các tác vụ không liên kết. Tuy nhiên, sự phụ thuộc dữ liệu giữa các tác vụ vẫn còn khi mà một số phép toán trong tác vụ này yêu cầu dữ liệu từ các tác vụ khác. Tổ chức truyền thông một cách hiệu quả có thể đang trở thành thách thức, thậm chí các phân rã đơn giản có thể có cấu trúc truyền thông phức tạp. Ngược lại, các yêu cầu truyền thông trong các giải thuật song song đạt được bằng phân rã chức năng thường là đơn giản, chúng tương ứng với luồng dữ liệu trao đổi giữa các tác vụ. Chẳng hạn như bài toán mô hình thời tiết, truyền thông tương ứng với luồng dữ liệu liên kết giữa các thành phần của mô hình. Thông thường có hai kiểu truyền thông là truyền thông cục bộ, mỗi tác vụ truyền thông với một tập nhỏ các tác vụ khác gọi là các tác vụ kề bên của nó, còn lại gọi là truyền thông toàn cục, yêu cầu mỗi tác vụ truyền thông với nhiều tác vụ. 2. 4. 1 Truyền thông cục bộ Cấu trúc truyền thông cục bộ đạt được khi một phép toán yêu cầu từ một số nhỏ các tác vụ bên cạnh khác. Khi đó sẽ đơn giản để xác định các kênh kết nối giữa tác vụ thực hiện phép toán (consumer) với các tác vụ nắm giữ dữ liệu (producer) để tính toán và đưa ra các phép toán nhận và gửi thích hợp trong các tác vụ này. Để mô tả kiểu truyền thông này, ta xem xét các yêu cầu truyền thông trong tính toán số của phương pháp vi phân hữu hạn Jacobi. Trong bài toán này, một lưới đa chiều các điểm được tạo ra, điểm ở giữa sẽ được cập nhật theo các điểm bên cạnh. Sau đây là công thức tính cho lưới 2 chiều. Truyền thông giữa các tác vụ được biểu diễn như sau: Hình 2. 7 Mô tả truyền thông cục bộ giữa các tác vụ Tác vụ T sẽ gửi X sang các vụ bên cạnh và nhận dữ liệu là X, X, X, X từ các vụ bên cạnh. 2. 4. 2 Truyền thông toàn cục Một phép toán truyền thông toàn cục sẽ được thực hiện với sự tham gia của nhiều tác vụ. Khi phép toán được thực hiện, sẽ không đơn giản để nhận ra các cặp producer/consumer. Với cách tiếp cận trên thì có thể dẫn đến quá nhiều truyền thông hoặc hạn chế khả năng tính toán đồng thời. Ví dụ, xem xét bài toán thực hiện phép toán rút gọn song song, rút gọn N giá trị phân tán trên N tác vụ. S = Giả sử rằng có một tác vụ làm nhiệm tính toán tổng S, khi đó tác vụ này cần yêu cầu các giá trị X0, X1, . . . từ các tác vụ 1, 2, . . . Bởi vậy, ta có thể định nghĩa một cấu trúc truyền thông cho phép mỗi tác vụ truyền thông giá trị của nó tới tác vụ tính S một cách độc lập. Tuy nhiên, tác vụ tính S chỉ có thể nhận và tính tổng chỉ một số tại một thời điểm, nên cách tiếp cận này có độ phức tạp O(N) về thời gian để tính tổng N số, đây không phải là giải thuật tốt. Hình 2. 8 Mô tả truyền thông toàn cục trong bài toán tính tổng Ví dụ trên đã mô tả hai vấn đề chung ngăn cản thực hiện song song hiệu quả trong các giải thuật dựa trên quan điểm hoàn toàn cục bộ về truyền thông. Giải thuật này được tập trung hoá, không phân tán tính toán và truyền thông. Một tác vụ đơn phải tham gia trong tất cả phép toán. Giải thuật là tuần tự, không cho phép nhiều phép toán truyền thông và tính toán xử lý đồng thời. Chúng ta cần giải quyết cả hai vấn đề này để phát triển giải thuật song song tốt. Phân tán tính toán và truyền thông Trước hết, ta xem xét vấn đề phân tán tính toán và truyền thông kết hợp với bài toán tính tổng. Việc phân tán thực hiện bằng cách thay vì chỉ một tác vụ tính toán tổng, mỗi tác vụ i, 0<i< N-1, sẽ thực hiện tính tổng. Si= Xi + Si-1 Hình 2. 9 Một giải thuật tính tổng, kết nối N tác vụ thành một mảng có thứ tự để tính tổng N số được phân tán giữa các tác vụ này. Yêu cầu truyền thông kết hợp với giải thuật này có thể thoả mãn bằng cách kết nối N tác vụ trong mảng một chiều. Tác vụ N-1 gửi giá trị của nó sang tác vụ bên cạnh. Từ tác vụ 1 tới N-2, mỗi tác vụ sẽ phải chờ nhận tổng cục bộ từ tác vụ bên phải, cộng tổng cục bộ đó với giá trị nằm trong tác vụ và gửi kết quả sang tác vụ bên tay trái. Tác vụ 0 sẽ chứa tác vụ cuối cùng. Giải thuật này phân tán N-1 phép toán cộng và truyền thông, nhưng cho phép thực hiện đồng thời chỉ khi nhiều phép tính tổng được thực hiện Do đó một tính tổng đơn lẻ vẫn phải thực hiện N-1 bước. Đồng thời không bao trùm: Chia và trị ( Uncovering Concurrency: Divide and Conquer) Các khả năng để tính toán và truyền thông đồng thời thường có thể không được bao trùm khi thực hiện chiến lược “chia và trị” để giải quyết bài toán. Để giải bài toán phức tạp như tính tổng N số, giải thuật tìm kiếm để phân chia bài toán thành 2 hoặc nhiều hơn các bài toán đơn giản với độ lớn xấp xỉ bằng nhau. Phân chia này được cung cấp đệ qui đến khi đưa ra một tập các bài toán con không thể phân chia được nữa. Kỹ thuật “chia và trị “ có tác động tốt trong tính toán song song khi các bài toán con có thể được giải quyết đồng thời. Ví dụ bài toán tính tổng 8 số sử dụng chiến lược “chia và trị” như hình sau Hình 2. 10 Cấu trúc cây của giải thuật tính tổng 8 số theo chiến lược “chia và trị”. Với phương pháp phân chia truyền thông như trên, các tổng trong cùng một mức có thể thực hiện đồng thời, bởi vậy toàn bộ công việc tính tổng N số có thể đạt trong logN bước tính toán. 2. 4. 3 Các vấn đề cần quan tâm Sau khi thực hiện công đoạn truyền thông, giải thuật song song đã có cấu trúc phân rã và truyền thông. Tuy nhiên, việc xem xét lại quá trình thiết kế dựa trên các vấn đề được đưa ra dưới đây sẽ đánh giá được phần nào mức độ hoàn chỉnh. Tất cả các tác vụ có thực hiện cùng số lượng phép toán truyền thông không?. Nếu không, nên xem xét lại thiết kế để các phép toán truyền thông có thể được phân tán cân bằng hơn. Mỗi tác vụ có truyền thông chỉ với một số nhỏ các tác vụ bên cạnh hay không?. Nếu như mỗi tác vụ phải truyền thông với nhiều tác vụ thì ta có thể thực hiện truyền toàn cục thông qua truyền thông cục bộ. Các phép toán truyền thông có thể xử lý đồng thời không? Nếu không, giải thuật sẽ không hiệu quả và không linh động. Nên sử dụng kỹ thuật chia và trị như giải thuật tính tổng. Xen kẽ giữa truyền thông và tính toán nếu có thể. Thực hiện được điều này sẽ tăng được hiệu năng cho giải thuật. 2. 5 Tích tụ Trong hai công đoạn đầu của quá trình thiết kế đã phân rã tính toán cần thực hiện thành một tập các tác vụ và đưa ra truyền thông giữa các tác vụ có trao đổi dữ liệu với nhau. Tuy nhiên những kết quả đạt được trong hai công đoạn đầu vẫn chỉ mang tính lý thuyết, chưa chỉ ra thực hiện có hiệu quả trên một máy tính song song. Trong thực tế, sự phân chia trong hai công đoạn đầu có thể có hiệu quả cao, ví dụ như sự phân chia ban đầu tạo ra quá nhiều tác vụ so với số bộ xử lý trên máy tính đích và máy tính này lại không thiết kế để thực hiện có hiệu quả các tác vụ có khối lượng tính toán nhỏ. Trong công đoạn tích tụ này, ta sẽ chuyển thiết kế có tính lý thuyết vào thực tế. Xem xét lại các quyết định đã tạo ra trong pha phân rã và truyền thông để đạt được một giải thuật sẽ thực hiện hiệu quả trên một lớp máy tính song song nào đó. Đặc biệt là xem xét việc tích tụ các tác vụ nhỏ đã tạo ra trong pha phân rã thành các tác vụ có kích thước lớn hơn được gọi là các tác vụ grain-coarsed. Khi tích tụ các tác vụ nhỏ thành tác vụ lớn hơn, chí phí truyền thông sẽ giảm đi nhưng đồng nghĩa với việc làm giảm tiềm năng thực hiện đồng thời và khả năng linh động của giải thuật. Hình 2. 11 Các ví dụ minh hoạ cho công đoạn tích tụ. Kích thước của tác vụ được gia tăng bằng cách rút gọn chiều phân rã từ 3 xuống 2. Các tác vụ ban đầu được kết hợp lại dẫn đến phân rã theo 3 chiều với kích thước lớn hơn. (c) Các cây con trong cấu trúc “chia và trị” được hợp lại (d) Các nút trong một giải thuật cây được kết hợp Số lượng tác vụ trong pha tích tụ, mặc dù được rút gọn nhưng vẫn phải lớn hơn số bộ xử lý. Trong trường hợp này, việc thiết kế của ta vẫn có phần lý thuyết bởi vì các vấn đề liên qua đến ánh xạ vẫn còn chưa được giải quyết. Vấn đề này sẽ được đề cập đến trong công đoạn ánh xạ. Nhưng, nếu pha tích tụ giảm số tác vụ xuống bằng với số bộ xử lý thì mỗi tác vụ sẽ tương ứng với một bộ xử lý và quá trình thiết kế có thể dừng ở công đoạn này. 2. 5. 1Gia tăng kích thước tác vụ Trong pha phân rã của quá trình thiết kế, ta cố gắng chú trọng vào việc xác định càng nhiều tác vụ càng tốt nếu như có thể. Đây là nguyên tắc tốt bởi vì nguyên tắc buộc chúng phải xem xét một lớp rộng các khả năng để thực hiện song song. Tuy nhiên, chi phí truyền thông để thực hiện sẽ rất lớn, ảnh hưởng đến hiệu năng song song. Trên hầu hết các máy tính song song, khi muốn nhận và gửi các message thì ta phải dừng công việc tính toán để khởi tạo truyền thông, chi phí cho truyền thông trên mạng thường lớn, do đó ta cần phải giảm số lượng thời gian dành cho việc truyền thông. Thời gian truyền thông phụ thuộc vào số lượng dữ liệu gửi và số lần gửi và nhận message. Do đó để năng cao hiệu năng, ta cần phải kết hợp các tác vụ nhỏ lại thành tác vụ lớn hơn nhằm giảm số lần truyền message giữa các tác vụ. Xem xét ví dụ tích tụ trong bài toán vi phân hữu hạn hai chiều sau: Hình 2. 12 Mô tả phân rã và tích tụ theo hai chiều của bài toán. Trong hình (a), tính toán được phân rã thành 88 = 64 tác vụ, mỗi tác vụ tương ứng với một điểm đơn. Mỗi tác vụ yêu cầu 4 truyền thông, tổng là 64 4= 256 yêu cầu truyền thông, truyền 256 đơn vị dữ liệu. Hình (b), tích tụ các tác vụ nhỏ thành tác vụ lớn theo hai chiều, có 22 tác vụ, mỗi tác vụ lớn tương ứng với 16 điểm, tổng yêu cầu truyền thông là 4 4 = 16, giá trị dữ liệu được truyền là 16 4 =64. Như vậy với việc tích tụ thành tác vụ lớn hơn, chi phí truyền thông sẽ giảm đi rất nhiều. Đôi khi ta cũng có thể kết hợp hài hoà giữa lặp lại tính toán để giảm bớt yêu cầu truyền thông và thời gian thực hiện. Ví dụ như xem xét một biến thể của bài toán tính tổng đã ví dụ trước. Tính tổng được lặp lại trong mỗi tác vụ. (a) (b) Hình 2. 13 Sử dụng mảng và cây để thực hiện một phép tính tổng và broadcast. Bên tay trái ( Hình a ) là tính tổng, bên tay phải( Hình b) là broadcast. Để tính tổng và broadcast, theo kiểu mảng sẽ cần 2(N-1) bước, trong khi đó thì mô hình cây cần 2logN bước để tính tổng N giá trị lặp lại trên N tác vụ. Một cách tiếp cận đơn giản để phân tán tính tổng là sử dụng giải thuật dựa trên mô hình mảng hoặc cây tính toán tổng trong một tác vụ đơn, sau đó broadcast tổng đến mỗi tác vụ. Những giải thuật này dễ có cảm giác là tối ưu bởi vì chúng không thực hiện bất cứ tính toán hay truyền thông nào vô ích. Tuy nhiên cũng tồn tại giải thuật có thời gian thực hiện ít hơn mặc dù có gia tăng việc lặp lại những tính toán và truyền thông. ý tưởng cơ bản là thực hiện nhiều phép tính tổng đồng thời, với mỗi tính tổng đồng thời đem lại một giá trị trong tác vụ khác. Chúng ta xem xét một biến thể khác là tính tổng trên mô hình Butterfly. Khi đó, mỗi tác vụ sẽ nhận dữ liệu từ hai tác vụ, thực hiện phép cộng đơn, gửi dữ liệu của phép cộng đến hai tác vụ trong đoạn tiếp theo. Khi sử dụng mô hình này đã gia tăng công việc thực hiện, tính tổng và broacast tổng chỉ cần log N bước. Như vậy trong nhiều bài toán, lặp lại tính toán trên các tác vụ có thể rút gọn được thời gian tính toán. Hình 2. 14 Mô tả tính tổng N giá trị trên N tác vụ với mô hình Butterfly 2. 5. 2 Duy trì khả năng linh động Khi tích tụ các tác vụ để tạo ra các quyết định thiết kế, ta có thể sẽ hạn chế một cách không cần thiết tính qui mô của giải thuật. Ví dụ, ta có thể chọn phân rã chỉ theo một chiều đối với cấu trúc dữ liệu đa chiều, với lý do rằng cách phân chia này đưa ra khả năng thực hiện đồng thời cao hơn đối với số bộ xử lý hiện có. Tuy nhiên, chiến lược này bị hạn chế nếu như giải thuật phải chuyển sang thực hiện trên các máy tính song song lớn hơn. Khi đó có thể dẫn đến một giải thuật hiệu quả thấp. Nếu có khả năng tạo ra một số lượng tác vụ có thể thay đổi thì giải thuật sẽ trở lên khả chuyển và qui mô hơn. Khả năng linh động này cũng trở lên hữu ích khi mã hoá giải thuật vào một máy tính cụ thể, bởi vì cho phép ta luôn có thể tạo ra số tác vụ lớn hơn số bộ xử lý, khả năng xen kẽ giữa truyền thông và tính toán có thể thực hiện. Lợi ích tiếp theo của việc tạo ra nhiều tác vụ hơn số bộ xử lý là cung cấp nhiều cơ hội hơn cho các chiến lược ánh xạ, cân bằng nạp tính toán trên các bộ xử lý. Vấn đề này sẽ được trình bày trong mục tiếp theo. Tối ưu hoá về số lượng tác vụ là một câu hỏi khó, thường phải có kết hợp giữa các nghiên cứu thực tế và mô hình phân tích để trả lời được câu hỏi này. Tuy nhiên, tính linh hoạt không cần thiết cứ phải tạo ra một số lượng lớn tác vụ. Điều quan trọng là thiết kế của ta không hạn chế số lượng có thể được tạo ra, khi đó độ lớn của từng tác vụ có thể được điều chỉnh bởi một thông số nhập vào khi chạy. 2. 5. 4 Các vấn đề cần quan tâm Những quyết định phân rã và truyền thông trong hai công đoạn đầu có thể được thay đổi trong công đoạn này nhằm giảm thời gian thực hiện bài toán. Xem xét lại giải thuật qua 3 công đoạn thiết kế ban đầu là cần thiết để đạt được giải thuật song song tốt khi xem xét đến mô hình máy cụ thể. Tích tụ đã giảm chi phí truyền thông bằng việc tăng tính cục bộ dữ liệu chưa ? Nếu không, kiểm tra giải thuật để xác định xem ta có thể đạt được bằng cách sử dụng chiến lược tích tụ khác. Nếu như thựchiện tích tụ làm cho tính toán phải lặp lại thì ta phải xác định xem lợi ích đem lại của tính toán lặp lại có lớn hơn chí phí bỏ ra như thời gian tính toán tăng lên, chí phí về thực hiện chương trình. . . Số lượng tác vụ vẫn linh động với kích thước bài toán ? nếu không, giải thuật mà ta thiết kế không có khả năng giải quyết các bài toán lớn hơn trên máy tính song song lớn hơn. Nếu việc tích tụ làm mất các khả năng để thực hiện đồng thời, ta đã kiểm tra lại xem giải thuật có đủ tính đồng thời cho máy tính hiện thời và trong tương lai không ? Một giải thuật có sự đồng thời kém có thể vẫn trở lên hiệu quả nhất, nếu các giải thuật khác có chi phí truyền thông quá lớn. Khi đó mô hình hiệu năng có thể được sử dụng để xác định. 2. 6 ánh xạ Trong công đoạn thứ tư và là cuối cùng của quá trình thiết kế giải thuật song song, mỗi tác vụ sẽ được ấn định vào một bộ xử lý nào đó. Công đoạn thiết kế này không có trong giải thuật thiết kế cho các máy tính đơn bộ xử lý hoặc bộ nhớ dùng chung bởi vì thường được hệ điều hành hoặc các kỹ thuật phần cứng cung cấp lập lịch trình tự động. Nhìn chung, cho đến nay các kỹ thuật ánh xạ đa năng vẫn chưa được phát triển cho các máy tính song song, ánh xạ vẫn còn là một bài toán khó mà ta phải chỉ ra rõ ràng khi thiết kế bài toán. Mục đích của việc phát triển các giải thuật ánh xạ thường là để cực tiểu hoá tổng thời gian thực hiện. Chúng ta sử dụng hai chiến lược sau để đạt được mục đích này. Đặt các tác vụ có thể thực hiện đồng thời trên các bộ xử lý khác, khi đó sẽ năng cao tính đồng thời Đặt các tác vụ thường có truyền thông với nhau trên cùng bộ xử lý, khi đó sẽ gia tăng tính cục bộ. Rõ ràng, hai chiến lược này thường mâu thuẫn với nhau và thiết kế của ta sẽ liên quan đến sự kết hợp giữa hai chiến lược. Hơn nữa, các giới hạn về tài nguyên có thể hạn chế số lượng tác vụ được đặt trên một bộ xử lý đơn. Bài toán ánh xạ được biết đến như bài toán NP-complete, có nghĩa là giải thuật đánh giá những kết hợp của hai chiến lược trong trường hợp chung có độ phức tạp thời gian tính toán là hàm đa thức. Trong mục này sẽ đưa ra sự phân loại bài toán và trình bày một vài kỹ thuật mang tính mô phỏng. Rất nhiều giải thuật được phát triển sử dụng các kỹ thuật phân rã theo miền, nét nổi bật là số lượng cố định các tác vụ kích thước ngang nhau và truyền thông giữa các tác vụ tạo lên đồ thị có cấu trúc. Trong trường hợp này, một ánh xạ tĩnh có hiệu quả là dễ dàng đạt được. Chúng ta ánh xạ các tác vụ trong một cách cực tiểu hoá truyền thông giữa các bộ xử lý. Khi đó kiến trúc mạng liên kết giữa các bộ xử lý sẽ ảnh hưởng rất nhiều đến công việc ánh xạ tĩnh. Vấn đề này sẽ được đề cập chi tiết hơn trong chương sau khi tìm hiểu về kiến trúc bộ xử lý. Trong các giải thuật dựa trên phân rã theo miền phức tạp với khối lượng công việc biến đổi cho mỗi tác vụ và truyền thông giữa các tác vụ tạo lên đồ thị bất kỳ, các chiến lược ánh xạ và tích tụ hiệu quả không trở lên rõ ràng cho người thiết kế. Bởi vậy, ta có thể cung cấp các giải thuật cân bằng nạp động, tìm kiếm để nhận ra các chiến lược tích tụ và ánh xạ thích hợp, thông thường người ta sử dụng các kỹ thuật mang tính chất kinh nghiệm( heuristic techniques). Đối với các giải thuật dựa trên phân rã chức năng thường dẫn đến tính toán bao gồm nhiều tác vụ có thời gian thực hiện ngắn và thường liên kết với các tác vụ khác chỉ tại thời điểm bắt đầu và kết thúc thực hiện, các yêu cầu cục bộ ít. Trong trường hợp này, ta có thể sử dụng các giải thuật lập lịch trình tác vụ ( task-scheduling) để định vị tác vụ vào các bộ xử lý nhằm tối ưu khả năng tính toán cho bộ xử lý. 2. 6. 1 Các giải thuật cân bằng nạp Một lớp rộng các kỹ thuật cân bằng nạp đa năng hoặc cho ứng dụng cụ thể đã được đề xuất, sử dụng trong các giải thuật song song dựa trên phân rã theo miền. Ta sẽ xem xét một số cách tiếp cận sau : phương pháp phân đôi đệ quy (recursive bisection), giải thuật cục bộ, phương pháp xác xuất, và ánh xạ chu trình. Tất cả kỹ thuật này có xu hướng tích tụ các tác vụ nhỏ fine-grained định nghĩa trong phân rã ban đầu thành một tác vụ lớn coarse-grained cho một bộ xử lý. a. Phân đôi đệ quy: Được sử dụng để phân rã miền bài toán thành các miền nhỏ có thời gian tính toán xấp xỉ nhau trong khi cố gắng cực tiểu hoá chi phí truyền thông, các kênh truyền thông sẽ ngang qua đường biên tác vụ. Đầu tiên, miền được phân chia theo một chiều dẫn đến hai miền con. Công việc phân chia sẽ được lặp lại đối với miền mới cho đến khi bằng với số miền con ta yêu cầu. Giải thuật phân chia này sẽ tự thực hiện trong khi song song. b. Giải thuật cục bộ Trong kỹ thuật phân đôi đệ qui có chi phí tương đối lớn bởi vì giải thuật yêu cầu biết toàn cục về trạng thái tính toán. Ngược lại, các giải thuật cân bằng nạp cục bộ thay đổi nạp tính toán sử dụng những thông tin lấy từ một số lượng nhỏ các bộ xử lý bên cạnh. Bởi vì các giải thuật cục bộ chi phí không cao nên có thể trở lên hữu dụng trong các trường hợp mức độ thay đổi nạp có tính cố định. Tuy nhiên, giải thuật cục bộ thường kém hiệu quả hơn giải thuật toàn cục, đặc biệt có thể trở lên chậm với những thay đổi lớn. c. Phương pháp xác xuất. Đây là một cách tiếp cận cân bằng nạp đơn giản đặc biệt, tác vụ được định vị tới bộ xử lý được chọn ngẫu nhiên. Nếu số lượng các tác vụ lớn, ta có thể hy vọng mỗi bộ xử lý sẽ được định vị với số lượng tính toán tương tự nhau. Thuận lợi của phương pháp này là chi phí thấp và có tính qui mô cao. Nhược điểm là có xu hướng chi phí truyền thông cao. d. ánh xạ chu trình. Trong kỹ thuật này, các tác vụ sẽ được ánh xạ theo chu trình tới các bộ xử lý. Kỹ thuật này là một hình thức của ánh xạ xác xuất. Ngoài ra ta có thể ánh xạ theo chu trình khối tác vụ đến bộ xử lý. 2. 6. 2 Các giải thuật lập lịch trình tác vụ Các giải thuật lập lịch trình tác vụ có thể được sử dụng khi phân rã bài toán theo chức năng, mỗi tác vụ ít có yêu cầu dữ liệu cục bộ. Khi đó một vùng tác vụ tập trung hoặc phân tán được duy trì, trong đó các tác vụ mới được thiết lập và từ đó các tác vụ được lấy ra để định vị đến bộ xử lý. Thông thường bài toán được giải quyết bằng một tập các tác vụ nhân công (worker), mỗi tác vụ worker trên một bộ xử lý. Có một số cách tiếp cận sau: chủ /tớ ( manager/ worker), chủ /tớ phân cấp ( hierarchical manager/ worker ) và tản quyền. Manager/ Worker. Manager là một tác vụ quản lý tập trung chịu tránh nhiệm định vị bài toán. Mỗi worker sẽ lặp lại yêu cầu và thực hiện bài toán được phân phát từ manager. Worker cũng có thể gửi tác vụ mới đến manager để định vị tới worker khác. Kỹ thuật này làm cho manager dễ dẫn đến quá tải khi số lượng yêu cầu đồng thời từ các worker lớn. Hình 2. 13 Mô tả mô hình lập lịch trình Manager/ Worker Manager/ Worker phân cấp là một biến đổi của tổ chức Manager/ Worker, hạn chế được hiện tượng quá tải trong manager bằng cách phân chia các worker thành các tập rời nhau, mỗi tập có một Manager phụ ( Submanager). Các worker sẽ yêu cầu tác vụ từ Submanager, và chính Submanager cũng liên lạc định kỳ với manager và với các submanager khác để cân bằng nạp giữa các tập bộ xử lý. Tản quyền. Trong sơ đồ tản quyền, không có bộ quản lý tập trung. Thay vào đó, một vùng tác vụ riêng biệt được duy trì trên mỗi bộ xử lý và các worker rỗi sẽ yêu cầu công việc từ các bộ xử lý khác. Các bộ xử lý được worker liên lạc có thể là liền bên cạnh hoặc một tập bộ xử lý ngẫu nhiên. 2. 6. 3 Các vấn đề cần quan tâm Bây giờ, ta đã hoàn thành quá trình thiết kế giải thuật song song với việc chỉ ra các tác vụ được định nghĩa trong công đoạn trước được ánh xạ tới bộ xử lý. Trong quyết định ánh xạ phải kết hợp được giữa phân tán công việc cân bằng và chi phí truyền thông thấp. Khi có thể, ta sử dụng một sơ đồ ánh xạ tĩnh để định vị mỗi tac vụ tới một bộ xử lý. tuy nhiên, khi số lượng hay kích thước các tác vụ biến đổi hoặc không được biết tận lúc chạy, chúng ta có thể sử dụng một sơ đồ cân bằng nạp tĩnh. Khi bài toán phân rã theo chức năng thì cấu trúc lập lich trình có thể được sử dụng để lập lịch trình tính toán. Nếu sử dụng sơ đồ cân bằng nạp tập trung, bạn có kiểm tra được manager không bị quá tải không ? Nếu sử dụng sơ đồ cân bằng nạp động, bạn có đánh giá được chi phí tương đối so với các chiến lược khác không?. Các sơ đồ ánh xạ theo chu trình hay theo xác xuất là đơn giản và ta nên quan tâm đến những kỹ thuật này, bởi vì chúng có thể tránh được việc lặp lại các phép toán cân bằng nạp. Sau công đoạn này, công việc thiết kế một hoặc nhiều giải thuật cho bài toàn đã hoàn thành. Tuy nhiên để chọn lựa ra giải thuật hiệu quả trong số các giải thuật trong quá trình thiết kế tạo ra, ta cần có sự đánh giá sơ bộ thông qua các tiêu chuẩn đánh giá liên quan liên quan đến kiến trúc máy tính. Các vấn đề này sẽ được đề cập đến trong hai chương tiếp theo. Chương 3 Mạng kết nối Trong máy tính song song, khi truy nhập dữ liệu từ xa sẽ yêu cầu truyền thông giữa các bộ xử lý hoặc giữa bộ xử lý với bộ nhớ. Nếu như kết nối trực tiếp điểm tới điểm giữa hai bộ xử lý bất kỳ thì chi phí cho việc kết nối mạng sẽ rất lớn bởi vì sẽ dùng O (p) dây kết nối giữa các bộ xử lý. Để giảm chi phí dây kết nối và truyền thông, việc kết nối được thực hiện có chọn lọc giữa các cặp bộ xử lý. Do đó, khi truyền thông giữa hai bộ xử lý không được kết nối trực tiếp sẽ yêu cầu kỹ thuật định đường thông qua bộ xử lý trung gian. Kết quả của quá trình kết nối là mạng liên kết và kiến trúc của mạng phần nào xác định độ trễ ( latency) và băng thông ( bandwidth ) truyền thông. Những thông số này sẽ ảnh hưởng đến thời gian truyền thông trong khi tính toán. Sau đây sẽ trình bày một số mạng liên kết thông dụng và đánh giá thông qu._. phần tử tương ứng với hàng j. Trong giải thuật khử Gauss, đối với mỗi cột i khử các phần tử dưới đường chéo chính bằng cách cộng với bội số của hàng i với các hàng phía dưới. Giải thuật khử tuần tự như sau: For k = 1 to n-1 For j= k + 1 to n For i = k+1 to n a = a– (a/ a)*a Công việc tính toán trong một bước được minh hoạ như hình vẽ dưới đây: (k, k) (k, i) (j, k) cột k cột i hàng k hàng j i (i, j) Khử Cập nhật Hình 5. 1 Mô tả tính toán trong giải thuật khử Guass Giải thuật tách ma trận A = L * U dựa theo giải thuật khử Gauss ta sẽ được L là ma trận tam giác dưới với các phần tử nằm trên đường chéo chính =1 và U là ma trận tam giác trên. Sau khi kết thúc thủ tục tách, thì L được lưu trữ trong phần dưới đường chéo chính và U được lưu trữ trong phần trên của A. Giải thuật tách tuần tự được trình bày như sau: For k = 1 to n-1 For i= k + 1 to n l = a/a end for j = k +1 to n For i = k +1 to n a = a - l. a end end end Trong giải thuật tuần tự, công việc tính toán l được được ra ngoài vòng lặp trong để giảm chi phí tính toán trong mỗi bước lặp. A = L U Thông thường, giải thuật khử Gauss có sự hoán đổi giữa các hàng để tìm ra phần tử xoay có giá trị tuyệt đối lớn nhất. Tuy nhiên, để đơn giản hoá bài toán, tạm thời bỏ qua vấn đề tìm phần tử xoay có giá trị lớn nhất. Xem xét độ phức tạp của giải thuật. Giải thuật khử Gauss tuần tự yêu cầu khoảng n/3 cặp phép toán cộng nhân, bởi vậy thời gian yêu cầu thực hiện là T= t n/3 với t là thời gian yêu cầu thực hiện phép cộng -nhân. Quá trình thiết kế giải thuật song song được trình bày như sau: a. Phân rã Đối với 2 vòng for i, j = 1, …. , n sẽ hình thành lên ma trận có n phần tử Một cách tự nhiên, ta phân rã ma trận thành n tác vụ, mỗi tác vụ tại vị trí (i, j) sẽ lưu trữ hệ số a, tính toán và lưu trữ các phần tử sau: u nếu i j l nếu i > j Các phần tử 0 dưới đường chéo chính trong ma trận U, phần tử =0 phía trên đường chéo chính và các phần tử =1 trên đường chéo chính không cần phải tính toán và lưu trữ, ta mặc định trong kết quả. b. Truyền thông Các bước tính toán có sự phụ thuộc dữ liệu lẫn nhau nên truyền thông là cần thiết giữa các tác vụ. Truyền thông giữa các tác vụ được mô tả như hình dưới đây. Hình 5. 2 Mô tả truyền thông giữa các tác vụ Khi đó ta có chương trình mô phỏng cho từng tác vụ như sau: Program for task(i, j) For k= 1 to min (i, j) –1 Recv a Recv l a= a- l* a end if i j then broadcast a to task(k, j), k = i +1, …. , n else recv a l= a/ a broadcast l to tasks(i, j), k = j+1, …, n end c. Tích tụ Với mảng hai chiều n n các tác vụ, các chiến lược kết hợp tác vụ như sau: 1-D: kết hợp n/p hàng hoặc cột 2-D: kết hợp các tác vụ thành mảng con 2 chiều (n/) (n/) với các chiến lược này, công đoạn tích tụ đều tạo ra p tác vụ lớn hơn. d. ánh xạ Mỗi tác vụ tạo ra từ công đoạn kết hợp sẽ được ấn định vào một trong p bộ xử lý. Với mỗi chiến lược tích tụ, ta có một giải thuật song song song tương ứng. 5. 1. 1 Giải thuật song song theo hàng Trong công đoạn tích tụ các tác vụ, giải thuật hướng theo hàng sẽ thực hiện việc kết hợp n/p hàng các tác vụ ban đầu thành một tác vụ lớn. Khi đó không cần thiết broadcast l theo chiều ngang bởi vì các tác vụ này được thực thi chỉ trong một tác vụ. Tuy nhiên, chiến lược tích tụ này không song song được việc cập nhật các phần tử nằm cùng trong một hàng. Vẫn yêu cầu broadcast theo chiều dọc để truyền dữ liệu trong mỗi hàng ở trên tới các tác vụ ở dưới để cập nhật dữ liệu. Hình 5. 3 Mô tả truyền thông giữa các tác vụ tích tụ theo hàng Giải thuật theo hàng 1-D như sau: For k=1 to n-1 If k myrows then Broadcast { a: k < j < n } to other tasks Else Recv{ a: k jn } End For i myrows, i > k, l = a/a. end for j = k+1 to n for i myrows, i > k, a= a- l*a end end end Thời gian thực hiện Tính toán độ phức tạp tính toán của thuật toán. -Tại bước thứ k, việc cập nhật các tác vụ yêu cầu khoảng (n-k)/p phép toán. - Độ phức tạp cho toàn bộ n-1 bước sẽ là : T t n/(3p). Tính toán độ phức tạp về truyền thông. Tương tự như tính toán độ phức tạp, số lượng dữ liệu broadcast tại bước thứ k là khoảng n-k, bởi vậy trên mô hình 1-D Mesh, các bộ xử lý nối nhau thành đường thẳng và truyền thông với nhau bằng kỹ thuật circuit-switched với ảnh hưởng của khoảng cách giữa các bộ xử lý t h nhỏ có thể bỏ qua. Ta có chi phí cho truyền thông sẽ là T (p-1) tn + (p-1)t n/2 Tổng thời gian thực hiện là : T t n /(3p) + t(p-1)n + t(p-1) n/2 Các vấn đề đặt ra cho việc thực thi giải thuật song song theo hàng là: Phân tán công việc không đều, mỗi tác vụ sẽ đi vào trạng thái rỗi ngay khi hàng cuối cùng được hoàn thành. Nếu tác vụ quản lý khối các hàng liên tiếp thì bộ xử lý được ấn định tương ứng sẽ rỗi thời gian rất lâu trước khi toàn bộ tính toán được hoàn thành. Hơn nữa, công việc cập nhật các hàng sẽ ít đi nhanh chóng khi số hiệu hàng gia tăng. Các phương pháp giải quyết cho vấn đề này là: ấn định các hàng tới các tác vụ theo chu trình, với hàng thứ i được ấn định tới task thứ i mod n hoặc ấn định theo kiểu chu trình khối (block-cyclic) hoặc Pipeline việc tính toán và truyền dữ liệu, với phương pháp này sẽ cải thiện được hiệu năng của giải thuật song song. Thay vì làm việc trên cùng một bước lặp tại một thời điểm, tất cả các bộ xử lý có thể được lập lịch trình thực hiện một cách không đồng bộ. Trong khi pipeline giải thuật khử Gauss thì mỗi bộ xử lý sẽ thực hiện độc lập bất kỳ hoạt động gửi hoặc tính toán trừ phi nó đang chờ nhận dữ liệu dùng cho hoạt động đó. + Tại bước k, mỗi tác vụ hoàn thành cập nhật phần còn lại của nó trước khi chuyển tới bước tiếp theo k+1. Tuy nhiên tác vụ quản lý hàng k+1 có thể broadcast ngay sau khi nó được cập nhật trước khi nó tiếp tục việc cập nhật phần còn lại của bước thứ k. + Với chiến lược gửi trước “ send ahead” sẽ cho phép các tác vụ khác bắt đầu tiến hành công việc trên tác vụ tiếp theo sớm hơn bởi vì thời gian chờ đợi dữ liệu cần thiết cho việc tính toán đã được rút gọn. 5. 1. 2 Giải thuật song song theo cột Việc tích tụ theo cột cũng tương tự như giải thuật theo hàng, với n/p cột các tác vụ cơ sở tạo thành một tác vụ lớn. Khi thực thi giải thuật sẽ không phải broadcast các hàng theo chiều dọc nhưng ngược lại phải broadcast theo chiều ngang cho các task vụ nằm bên phải. Không song song được việc tính toán hệ số nhân của các hàng dùng vào việc khử các phần tử dưới đường chéo chính cũng như song song việc cập nhật các phần tử bất kỳ cột nào đưa ra. Hình 5. 4 Mô phỏng truyền thông giữa các tác vụ tích tụ theo côt Giải thuật LU theo cột được mô phỏng như sau: For k=1 to n-1 If k mycols then For i=k+1 to n l= a/a end broadcast { l: k < i n } to other tasks Else Recv{ l: k jn } End For i mycols, j > k, For i= k +1 to n a= a- l*a end end end Tính toán độ phức tạp giải thuật, các vấn đề cũng như phương pháp giải quyết cũng tương tự như giải thuật song song tích tụ theo hàng. 5. 1. 3 Giải thuật song song hai chiều Tiếp theo chúng ta sẽ xem xét giải thuật tách A=L*U hai chiều, khi đó mảng (n/) (n/) các tác vụ cơ sở sẽ được kết hợp lại tạo thành tác vụ lớn. Việc tích tụ này sẽ kết hợp đặc điểm của giải thuật theo cột và giải thuật theo hàng. Như broadcast theo chiều ngang và chiều dọc được yêu cầu để truyền thông các đoạn ma trận theo hàng và các hệ số nhân theo cột Hình 5. 5 Mô phỏng truyền thông giữa các tác vụ tích tụ kết hợp Giải thuật song song kết hợp được mô phỏng như sau: For k=1 to n-1 If k myrows then Broadcast { a: j mycols, j > k} to other tasks in my task column Else Recv{ a: j mycols, j > k} End If k mycols then For i myrows, i < k l = a/a. end broadcast { l: i myrows, i > k} to other tasks in my task row end else recv { l: i myrows, i > k} end for j mycols, j > k for i myrows, i > k, a= a - l a end end end Tính toán thời gian thực hiện của thuật toán. Tại bước thứ k, việc cập nhật bởi mỗi tác vụ yêu cầu khoảng (n-k)/p phép toán. Do đó tổng số trên n-1 bước sẽ là : T t tn/(3p) Số lượng dữ liệu broadcast tại bước k dọc theo mỗi hàng mỗi cột của mỗi tác vụ khoảng (n-k)/, bởi vậy trên mô hình 2-D mesh Ta có T 2 tn + tn/ Tổng thời gian thực hiện là: T tn/(3p) + 2 tn + t n/ Cũng tương tự như giải thuật tích tụ theo hàng hoặc cột, giải thuật kết hợp có các vấn đề như: Mỗi tác vụ sẽ trở nên rỗi ngay sau khi các hàng và cột của nó hoàn thành. Số lượng công việc tính toán ít đi khi số hiệu hàng và cột tăng lên. Để cải thiện vấn đề cân bằng nạp và tính đồng thời người ta có thể ấn định hàng cột vào tác vụ theo chu trình, với hệ số của ma trận A là a ấn định vào tác vụ (i mod , j mod ). Ngoài ra có thể ấn định theo khối- chu trình (block-cyclic). Hiệu năng có thể năng cao bằng cách pipeline tính toán và truyền dữ liệu. Tại bước thứ k, mỗi tác vụ sẽ hoàn thành việc cập nhật ma trận con còn lại trước khi chuyển đến bước thứ k+1. Công việc broadcast mỗi đoạn của hàng k+1, tính toán và broadcast mỗi đoạn hệ số nhân cho bước thứ k+1 có thể được khởi tạo ngay sau khi các đoạn liên quan đến hàng k+1 và cột k+1 được cập nhật bởi tác vụ quản lý nó, trước khi hoàn thành việc cập nhật còn lại cho bước thứ k Với chiến lược gửi trước “send ahead” sẽ cho phép các tác vụ khác tiến hành công việc trên bước tiếp theo sớm hơn. 5. 1. 4 Khử Gauss với kỹ thuật lựa chọn phần tử xoay Do các hàng của hệ phương trình tuyến tính không ràng buộc thứ tự, cho nên ta có thể hoán đổi các hàng cho nhau mà không ảnh hưởng đến hệ. Việc chọn phần tử xoay a sao cho giá trị tuyệt đối lớn nhất nhằm tránh khả năng chia cho phần tử rất nhỏ và nhằm đảm bảo chắc chắn rằng số nhân không vượt quá 1 về độ lớn, làm giảm đi sự khuyếch đại lỗi do làm tròn. Với partial pivoting dẫn đến sự tách L*U theo hình thức sau: PA = LU Với P là ma trận chuyển vị của A Nếu PA=LU thì hệ Ax=b sẽ trở thành PAx = LU x= Pb Từ đó ta có giải hệ tam giác dưới Ly= Pb theo giải thuật rút gọn tiến, tiếp theo sẽ giải hệ tam giác trên với giải thuật rút gọn quay lui U x= y. Với kỹ thuật partial pivoting sẽ làm phức tạp việc thực thi song song giải thuật khử Gauss và ảnh hưởng thực sự đến hiệu năng. Đối với giải thuật tích tụ theo cột thì việc tìm kiếm theo phần tử xoay là không yêu cầu truyền thông giữa các tác vụ nhưng tính toán hoàn toàn tuần tự. Mỗi khi phần tử xoay được tìm thấy thì chỉ số của hàng xoay phải được truyền thông tới các tác vụ khác, và các hàng phải được hoán chuyển một các hoàn toàn hay hình thức trong mỗi tác vụ. Với giải thuật tích tụ theo hàng, tìm kiếm phần tử trục xoay sẽ được song song nhưng yêu cầu truyền thông giữa các tác vụ và ngăn cản pipeline giữa các bước tính toán liên tiếp. Nếu hoán chuyển hàng hoàn toàn thì chỉ có hai tác vụ liên quan đến, còn nếu hoán chuyển hình thức( chỉ số hàng được thay đổi ) thì việc ánh xạ các hàng tới các tác vụ sẽ đựợc thay đổi, điều này có thể làm giảm đi tính đồng thời và cân bằng nạp của giải thuật. Với giải thuật kết hợp hàng và cột, tìm kiếm trục xoay được song song nhưng yêu cầu truyền thông giữa các tác vụ dọc trên cột và ngăn cản pipeline giữa các bước tính toán liên tiếp. Do kỹ thuật partial pivoting tác động làm giảm hiệu năng nên có một vài lựa chọn được đưa ra nhằm hạn chế vấn đề tìm kiếm : Tìm kiếm phần tử xoay chỉ nằm trong khối các hàng Tìm kiếm có mức ngưỡng 5. 2 Giải hệ phương trình với ma trận hệ số tam giác Sau khi thực hiện phân rã A= L*U, ta sẽ thu được: L là ma trận tam giác dưới ( lower triangular ) bởi vì tất cả các phần tử phía trên đường chéo chính đều = 0, l= 0 với i < j. U là ma trận tam giác trên ( upper triangular) bởi vì tất cả các phần tử phía dưới đường chéo chính đều = 0, u= 0 với i> j. Đối với các giải thuật trực tiếp giải hệ phương trình tuyến tính thì việc đưa ma trận hệ số về ma trận tam giác là điều quan trọng bởi vì hệ tuyến tính ma trận hệ số tam giác thường dễ giải bằng các bước khử liên tiếp. Giải thuật tuần tự giải L* y = b. Đối với hệ phương trình tam giác thấp, y có thể tìm được bằng giải thuật rút gọn tiến. Giải thuật được trình bày như sau: x=(b- , i=1, …, n for j=1 to n x= b/l for i = j+1 to n b= b- lx end end Giải thuật tuần tự giải U * x = y Đối với hệ phương trình tam giác trên, x có thể tìm được bằng giải thuật rút gọn quay lui. Giải thuật được trình bày như sau: x=(b- , i=1, …, n for j=1 to n x= b/u for i = 1 to j-1 b= b- ux end end Phân tích độ phức tạp của giải thuật tuần tự. Giải thuật rút gọn tiến và rút gọn quay lui yêu cầu khoảng n/2 phép nhân và số lượng tương tự đối với phép cộng, bởi vậy thời gian tính toán đối với mô hình tuần tự là: T= t n/2 Với t là thời gian tính toán cho cặp phép nhân và cộng. Trong mục này chỉ xem xét xây dựng giải thuật song song đối với hệ phương trình tam giác dưới, hệ phương trình tam giác trên sẽ được giải tương tự. Phân rã Phân rã bài toán thành các tác vụ, mỗi tác vụ tương ứng với một phần tử trong ma trận L cần cập nhật. For i=2, …, n, j= 1, …, i-1 tác vụ (i, j). Mỗi tác vụ sẽ + lưu trữ l + tính toán lx - For i = 1, …, n, tác vụ (i, i). Mỗi tác vụ sẽ + lưu trữ l và b + tính tổng t= + tính toán và lưu trữ x= (b- t)/l Với việc phân chia này dẫn đến mảng 2 chiều tam giác n( n-1)/2 tác vụ. b. Truyền thông Đối với các tác vụ for j=1, …, n-1, mỗi tác vụ task(j, j) sẽ broadcast x tới task(j, j), i=j+1, . . , n. for i=2, . . , n tính tổng các kết quả thu gọn lx từ các tác vụ task(i, j), j=1, …, i-1. tới task(i, i). Truyền thông giữa các tác vụ được mô phỏng theo hình vẽ sau: Hình 5. 6 Mô tả truyền thông giữa các tác vụ Program for task (i, j), ij If i=j then If i> 1 then Recv sum reduction t else t=0 end x=(b-t)/l broadcast x to tasks(k, i), k=i+1, . . , n else recv x t = lx send t for sum reduction across tasks (i, k), k=1, …. , i-1, to task(i, i) end c. Tích tụ Với mảng hai chiều tác vụ, các chiến lược tích tụ tự nhiên là : Kết hợp n/p hàng hoặc cột Kết hợp hàng cột với ma trận con kích thước (n/) (n/) trong cả hai trường hợp đều đem lại p tác vụ d. ánh xạ Mỗi tác vụ sẽ được ấn định vào một trong p bộ xử lý. 5. 2. 1 Giải thuật song song tích tụ theo hàng Khi đó sẽ kết hợp p hàng tác vụ cơ sở tạo ra một tác vụ lớn. Với các tích tụ này sẽ không cần truyền thông để thực hiện rút gọn tổng trên hàng bởi vì bất kỳ hàng nào được đưa ra đều được chứa toàn bộ trong một tác vụ. Không thực hiện song song trong việc tính những tổng này. Tuy nhiên vẫn yêu cầu broadcast theo chiều dọc để truyền thông các thành phần của x. Hình 5. 7 Mô tả truyền thông giữa các tác vụ tích tụ theo hàng Giải thuật song song tích tụ theo hàng được mô phỏng như sau: For j=1 to n If j myrows then x= b/l broadcast x to other tasks else recv x end for i myrows, i > j, b= b- l x end end Các vấn đề đặt ra khi kết hợp theo hàng Mỗi tác vụ sẽ rỗi ngay sau khi thành phần lời giải tương ứng với hàng cuối cùng trong tác vụ đó được tìm ra. Nếu ta kết hợp liên tiếp các hàng vào một tác vụ thì có thể tác vụ sẽ rỗi một thời gian lâu trong khi toàn bộ tính toán hoàn thành Tính toán sẽ nhiều lên khi số hiệu hàng tăng lên Các phương pháp giải quyết Cân bằng nạp và tính đồng thời có thể được cải thiện bằng cách ấn định các hàng vào các tác vụ theo chu trình với hàng i được ấn định vào tác vụ i mod p. Có các cách ánh xạ khác như chu trình-khối (block-cyclic) hay đối đầu ( reflection ). Hình 5. 8 Mô tả truyền thông giữa các tác vụ ánh xạ chu trình Hình 5. 9 Mô tả truyền thông giữa các tác vụ ánh xạ đối đầu Tính toán thời gian thực hiện của giải thuật Nếu các bước liên tiếp được pipeline thì thời gian thực hiện xấp xỉ là T= t(n + 2n(p-1))/(2p) + (t+ t)(n-1) - Nếu không pipeline được các bước tính toán liên tiếp thì số hạng thể hiện chi phí truyền thông được nhân thêm với một hệ số : + p-1 đối với máy tính song song có mạng kết nối bộ xử lý hình 1-D Mesh + 2(-1) đối với máy tính song song có mạng kết nối bộ xử lý hình 2-D Mesh + log(p) đối với máy tính song song có mạng kết nối bộ xử lý hình hypercube Những hệ số này thể hiện chiều dài đường truyền thông thực hiện broadcast. Cải thiện hiệu năng Hiệu năng có thể cải thiện thực sự bằng chiến lược “gửi trước “( send ahead) trong đó tại mỗi bước thứ j tác vụ quản lý hàng j+1 có thể tính toán x và broadcast x trước khi hoàn thành cập nhật đối với x. Hiệu quả đạt được của pipeline bị tác động mạnh bởi cấu trúc mạng và ánh xạ các hàng tới các tác vụ. Ví dụ ánh xạ chu trình trên mạng Ring cho phép hoàn thành hầu hết khả năng pipeline trong khi kiến trúc Hypercube thì thấp hơn nhiều. 5. 2. 2 Giải thuật song song tích tụ theo cột Tiếp theo chúng ta sẽ xem xét việc tích tụ theo 1 chiều hướng cột, với n/p cột các tác vụ cơ sở hình thành nên tác vụ lớn. Khi tích tụ theo cột thì không cần thiết broadcast các thành phần của x theo chiều dọc, bởi vì bất kỳ cột ma trận nào đưa ra đều nằm hoàn toàn trong cùng một tác vụ. Truyền thông theo chiều ngang vẫn được yêu cầu để rút gọn các tổng tính ở vòng lặp bên trong. Tuy nhiên không có thực thi song song trong việc tính toán các tích số có kết quả từ thành phần được đưa ra từ x. Hình 5. 9 Mô tả truyền thông giữa các tác vụ tích tụ theo cột Giải thuật được mô phỏng như sau For j=1 to n t= 0 for j mycols, j < i t = t + lx end if i mycols then recv sum reduction of t x= ( b-t)/l else send t for sum reduction across tasks end end Cũng tương tự giải thuật đối với hàng, các vấn đề đặt ra trong cân bằng nạp và tính đồng thời gồm có: Các tác vụ vẫn còn rỗi tận đến khi phần tử lời giải tương ứng với cột đầu tiên của nó được tính. Nếu mỗi tác vụ quản lý một khối liên tục các cột thì một tác vụ vẫn có thể rỗi trong suốt thời gian hầu hết công việc tính toán. Số lượng công việc tính toán sẽ giảm đi khi số hiệu cột tăng lên. Các phương pháp giải quyết ấn định các cột vào các tác vụ theo chu trình với cột thứ j ấn định vào trong task j mod p Việc ánh xạ khác cũng có thể thực hiện như chu trình khối ( block-cyclic) hay đối đầu (reflection) Hình 5. 10 Mô tả truyền thông giữa các tác vụ tích tụ ánh xạ chu trình Hình 5. 11 Mô tả truyền thông tích tụ ánh xạ đối đầu 5. 2. 3 Giải thuật song song hai chiều Tiếp theo ta xem xét việc tích tụ theo hai chiều với mỗi tác vụ lớn được tạo thành bởi kết hợp mảng con hai chiều ( n/) ( n/) tác vụ ban đầu. Giải thuật này kết hợp đặc điểm của hai giải thuật tích tụ theo cột và theo hàng. Với giải thuật này, broadcast được yêu cầu theo chiều dọc và rút gọn tổng theo chiều ngang được yêu cầu truyền thông giữa các thành phần lời giải và tích luỹ các kết quả vòng lặp bên trong một cách tương ứng. Các vấn đề đối với giải thuật Nếu mỗi tác vụ quản lý một khối liên tiếp hàng và cột thì chúng ta sẽ có một giải thuật khối các tác vụ nhỏ với hiệu quả và tính đồng thời thấp. Hơn nữa với cách tiếp cận này sẽ dẫn đến chỉ có (p + ) /2 là không trống rỗng. Lãng phí gần một nửa các bộ xử lý trong ma trận Mesh 2-D. Để giải quyết vấn đề này thì việc ấn định theo cách chu trình các hàng và cột tới các tác vụ, với phần tử ma trận hệ số l được ấn định vào tác vụ (i mod , j mod ), kết quả là có p tác vụ không trống rỗng, bởi vậy ma trận Mesh 2-D có thể được sử dụng. Hình 5. 12 Mô tả truyền thông tích tụ kết hợp Hình 5. 13 Mô truyền thông giữa các tác vụ ánh xạ chu trình Nhưng ta nhận thấy vòng lặp trên các thành phần lời giải liên tiếp và thực hiện tương ứng với rút gọn tổng theo chiều ngang và broadcast theo chiều dọc, do đó vẫn có hạn chế về tính đồng thời bởi vì thực hiện tính toán cho mỗi thành phần chỉ liên quan đến một hàng tác vụ và một cột tác vụ. Để giải quyết vấn đề này, một giải thuật tốt hơn có thể đạt được bằng cách tính toán các thành phần lời giải trong một nhóm , điều này cho phép tất cả các tác vụ cập nhật kết quả một cách đồng thời. Mỗi bước của giải thuật này gồm có 4 pha như sau: Việc tính toán thành phần lời giải tiếp theo bởi các tác vụ trong ma trận tam giác thấp sử dụng giải thuật song song tích tụ hai chiều. Việc broadcast các thành phần lời giải kết quả theo chiều dọc từ các tác vụ trên đường chéo chính tới các tác vụ trong ma trận tam giác trên Tính toán cập nhật kết quả được thực hiện bởi tất cả các tác vụ. Rút gọn tổng theo chiều ngang sẽ được thực hiện bởi các tác vụ trong ma trận tam giác trên đến các tác vụ trên đường chéo chính. Hình 5. 14 Mô tả các pha trong giải thuật tính toán theo nhóm Tính toán thời gian thực hiện Toàn bộ thời gian yêu cầu được tính toán một cách xấp xỉ là: T= tn/(2p)+ (4(t+ t) + 5 t) n với s là chiều dài đoạn. Như vây ta đã áp dụng tiến trình thiết kế vào trong bài toán giải hệ phương trình tuyến tính. Đây là bài toán cơ bản, có nhiều ứng dụng trong các giải thuật song song thiết kế cho bài toán phức tạp. Chương tiếp sẽ trình bày phương pháp mô phỏng một số giải thuật song song đã thiết kế và đánh giá qua thời gian thực hiện. 5. 3 Thực thi giải thuật Các giải thuật song song cho bài toán giải hệ phương trình tuyến tính được thiết kế cho mô hình tính toán nhiều bộ xử lý. Mỗi máy tính thực hiện một hoặc nhiều tiến trình, trao đổi dữ liệu thông qua mạng truyền thông kết nối. Tuy nhiên ta vẫn có thể mô phỏng được giải thuật trên mô hình máy tính đơn bộ xử lý với việc phân chia thời gian, xử lý một cách xen kẽ các tiến trình. 5. 3. 1 Xây dựng chương trình  Trên một máy tính đơn bộ xử lý thì tại một thời điểm chỉ có một tiến trình thực hiện, do đó các tiến trình không thể đồng thời thực hiện song song nhiều dòng lệnh trên máy tính một bộ xử lý. Trong các hệ điều hành hỗ trợ tính toán song song thì vấn đề này có thể giải quyết bằng cách tạo ra các processor logic, mỗi processor này quản lý một tiến trình tương ứng và thực hiện tiến trình khi nhận được processor vật lý. Với mô hình phân chia thời gian này, các tiến trình sẽ có cảm giác như đang chỉ có duy nhất một tiến trình sử dụng hệ thống. Trong khi thực thi tiến trình song song, mỗi tiến trình có thể thuộc một trong ba trạng thái sau: Nhập Khởi tạo Sẵn sàng Thực hiện Ngắt Kết thúc Vào từ chế độ phân chia thời gian Ra trong chế độ phân chia thời gian Hình 6. 1 Công việc và trạng thái tiến trình Tiến trình nằm trong trạng thái sẵn sàng khi đã được cung cấp đầy đủ tài nguyên để thực hiện, chờ đợi được cung cấp processor vật lý. Tiến trình trong trạng thái thực khi đang thực hiện các lệnh trên processor vật lý. Còn tiến trình trong trạng thái ngắt khi đợi xuất hiện một sự kiện hoặc cung cấp tài nguyên để thực hiện. Tại mỗi thời điểm, có nhiều tiến trình đang tồn tại và có trạng thái riêng. Do đó, để quản lý được các tiến trình song song trong máy tính đơn bộ xử lý, các hệ điều hành cần phải tổ chức lưu thông tin trạng thái tiến trình vào khối điều khiển tiến trình PCB ( Process Control Block). Khối điều khiển này sẽ chứa toàn bộ trạng thái của tiến trình. Các tiến trình chủ yếu nằm trong hai trạng thái là sẵn sàng và ngắt. Tổ chức các tiến trình trong cùng một trạng thái thành một dòng hàng đợi thực sự ( tức là tổ chức theo kiểu FIFO). Khi một tiến trình được cung cấp processor vật lý, các thông tin trong bảng mô tả như bộ đếm chương trình, các thanh ghi, con trỏ stack được nạp vào trong processsor và lưu trữ giá trị hiện thời của CPU. Khi dừng tiến trình lại để chuyển sang tiến trình khác, cần thiết phải lưu trạng thái của các thanh ghi vào PCB. Khi bắt đầu thực hiện một tiến trình mới, cần nạp các trạng thái được lưu trong PCB vào trong processor. Chương trình cần duy trì được các hàng đợi trạng thái trong khi thực hiện, bởi vì các hàng đợi thể hiện trạng thái của tất cả các tiến trình đang tồn tại. Công cụ để các tiến trình có thể thực hiện chính xác là ngắt. Ngắt sẽ phân chia thời gian tính toán cho từng tiến trình, các thiết bị ngoại vi sử dụng ngắt để báo cho processor biết sự thay đổi trạng thái của mình. Trên quan điểm lập trình, từ góc độ processor, ta có thể định nghĩa ngắt ngừng đột xuất việc thực hiện một tiến trình để chuyển sang thực hiện tiến trình khác khi có một sự kiện nào đó xảy ra. Như vậy ngắt là công cụ chuyển điều khiển tới một tiến trình khác mà tiến trình hiện tại không biết. Phần lớn các máy tính đều có đồng hồ độc lập đo khoảng thời gian. Do đó có thể dùng đồng hồ để điều khiển processor theo thời gian. Cần xác lập một khoảng thời gian nhất định cho đồng hồ và giá trị này tự động được giảm dần cho đến khi xuất hiện tín hiệu ngắt đồng hồ. Bằng cách này có thể tạo đồng hồ riêng cho từng tiến trình và việc xử lý dòng xếp hàng kết hợp với thứ tự ưu tiên trở nên dễ dàng hơn nhiều. mỗi phần tử của danh sách ứng với dòng xếp hàng chứa tên tiến trình và khoảng thời gian cần cung cấp processor. Mỗi lần có ngắt đồng hồ báo hết thời gian thì hệ thống kích hoạt tiến trình khác và nạp khoảng thời gian mới bộ đếm thời gian. Tuy nhiên để quản lý các tiến trình như các hệ điều hành 32 bít, ta cần truy xuất vào hệ thống, lấy được các trạng thái của tiến trình đang thực hiện. Với các ngôn ngữ lập trình thông thường thì việc thực hiện các tiến trình song song như thế sẽ rất khó bởi vì người lập trình phải phụ thuộc vào trình biên dịch của ngôn ngữ cụ thể. Đối với bài toán giải hệ phương trình tuyến tính thì các tiến trình được thiết kế phụ thuộc vào tham số hàng, cột. Do đó, đơn vị phân chia là thời gian thực hiện một hàng cột, mỗi tiến trình sẽ thực hiện một hàng hoặc cột sau đó chuyển sang tiến trình khác thực hiện. Lý do giải quyết bài toán lớn vì nếu với bài toán nhỏ do tốc độ của máy tính là quá lớn nên thời gian để giải quyết một bài toán là rất nhỏ ( chỉ khoảng micro giây) nên ta không thể nhận biết được lợi ích của việc thực hiện song song. Vì vậy, bài toán đưa ra thử nghiệp yêu cầu cần phải có số bậc lớn. Mặt khác, do hạn chế về ngôn ngữ thực hiện (ngôn ngữ C), bộ nhớ dành cho chương trình tối đa là 640KB nên việc lưu trữ và trao đổi dữ liệu là hạn chế. Để có thể giải quyết được bài toán lớn ta phải thực hiện việc lưu trữ và truy xuất với bộ nhớ bên ngoài ( ổ đĩa cứng). Cụ thể việc thực hiện được minh hoạ như sau: Tất cả các hệ số của hệ phương trình được lưu trữ ở bộ nhớ ngoài. Khi cần một hệ số nào thì hệ số đó sẽ được đọc vào bộ nhớ trong ( biến tạm thời). Sau khi xử lý xong thì tất cả các biến tạm thời đó lại được lưu trở lại bộ nhớ ngoài ( tất cả các biến đã xử lý và chưa xử lý). Quá trình cứ tiếp tục như vậy cho đến khi chương trình kết thúc. Kết quả sẽ được lưu ra bộ nhớ ngoài. Thước đo đánh giá sự khác biệt giữa thực hiện song song và thực hiện tuần tự đó là thời gian thực hiện của chương trình với cùng một đầu vào. Thời gian thực hiện song song sẽ được tính toán theo cách sau : Khi bắt đầu thực hiện tiến trình ta khởi tạo bộ đếm thời gian (sẽ lấy theo đồng hồ hệ thống). Như vậy mỗi tiến trình sẽ có một bộ đếm thời gian riêng. Khi tiến trình thực hiện xong ( một hàng hoặc một cột), bộ đếm được lưu lại và sẽ được tiếp tục tính toán khi ta bắt đầu lại tiến trình này ( giá trị khởi tạo cho bộ đếm thời gian của tiến trình này là thời gian của việc thực hiện tiến trình này trước đó). Sau khi thực hiện xong thì thời gian thực hiện song song sẽ bằng thời gian lớn nhất mà một trong các tiến trình trên thực hiện. Để so sánh ta sẽ thực hiện giải bài toán này theo giải thuật tuần tự và sẽ thu được thời gian thực hiện tuần tự này, sau đó đem so sánh thời gian đã thu được ở bước thực hiện song song để thấy được hiệu quả của giải thuật song song. 5. 3. 3 Các hạn chế và hướng phát triển chương trình Chương trình được thực hiện trên mô hình máy tính đơn bộ xử lý nên những đánh giá về thời gian không hợp lý bởi vì chưa tính toán được chi phí thời gian truyền thông. Ngoài ra chưa thể áp dụng phân chia thời gian vào bài toán bất kỳ. Các giải thuật song song được thiết kế trên mô hình nhiều bộ xử lý, do đó để đánh giá được giải thuật cũng như thấyđược hiệu quả về thời gian, ta nên xây dựng chương trình trên mô hình máy tính song song Multiprocessor hoặc Multicomputer. Thông thường để giảm chi phí sản xuất máy tính song song, các bài toán song song thường được thực thi trên mạng cục bộ kết nối các máy tính cá nhân sẵn có dựa trên hỗ trợ của hệ điều hành mạng như Unix, Window NT với môi trường tính toán PVM hay MPI. Kết luận Báo cáo đã đề cập đến những vấn đề chung khi thiết kế giải thuật song song như các mô hình tổ chức giải thuật song song, đưa ra các công đoạn trong quá trình thiết kế, cũng như các vấn đề liên quan khi đánh giá hiệu quả giải thuật. áp dụng vào bài toán cụ thể và xây dựng chương trình minh hoạ cho những thiết kế. Tuy nhiên, với hạn chế về thời gian và kiến thức nên chưa xây dựng được chương trình mô phỏng trên nhiều máy tính khác nhau để có thể đánh giá được đúng thời gian thực hiện giải thuật song song. Hiện nay, tính toán song song đang đóng vai trò quan trọng trong các ứng dụng thực tế cũng như các bài toán phục vụ nghiên cứu khoa học. Tìm hiểu được các vấn đề liên quan đến thiết kế giải thuật sẽ đóng vai trò quan trọng khi phát triển ứng dụng song song. Tài liệu tham khảo Nguyễn Thanh Tùng, Giáo trình cơ sở chuyên nghành hệ điều hành, 1995. Nguyễn Đình Trí, Toán cao cấp I, NXB Giáo dục, 1998. Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, NXB Giáo dục, 1998. Nguyễn Thúc Hải, Mạng máy tính và hệ thống mở, NXB Giáo dục, 1997. Michael J. Quinn, Parallel Computing Theory and Practice, NXB McGraw-Hill, 1994. Albert Y. Zomaya, Parallel and Distributed Computing Handbook, NXB McGraw-Hill, 1996. M. Sasikumar, Dinesh Shikhare, P. Ravi Prakash, Introduction To Parallel Processing, Prentice Hall of India, 2000 Joel M. CrichLow, An Introduction to Distributed and Parallel Computing, Prentice Hall, 1997 Ian Foster, Designing and Building Parallel Programs, 1995 10. htttp://www. llnl. gov/computing/turorials/workshops/workshop /parallel_computing 11. Michael Tischer, Cẩm nang lập trình hệ thống, NXB Giáo dục, 1996 ._.