Đề tài Thiết kế giải thuật song song

Máy tính điện tử là một trong những phát minh vĩ đại nhất của thế kỷ 20, vừa ra đời sau chiến tranh thế giới hai nhưng nó đã phát triển một cách nhanh chóng và có sức sống mãnh liệt. Trong những thập niên 60, nền tảng để thiết kế máy tính số đều dựa trên mô hình của John von Newman với một đơn vị xử lý được nối với một vùng lưu trữ làm bộ nhớ và tại một thời điểm chỉ có một lệnh máy được thực thi. Kiến trúc truyền thống này ngày có nhiều hạn chế do thúc đẩy của các bài toán xuất phát 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.