Báo cáo nghiên cứu khoa học PHƯƠNG PHÁP XỬ LÝ LOGIC VỊ TỪ BẰNG NHỮNG THUẬT TOÁN SONG SONG

Ngày nay, những thành công trong việc áp dụng logic vào hệ thống cơ sở dữ liệu để xử lý thông tin đang được nhiều nhà tin học quan tâm, đặc biệt là vấn đề tìm lời giải tối ưu của chương trình logic nói chung và datalog nói riêng. Ở lĩnh vực này, các ứng dụng về dự báo thời tiết, chẩn đoán bệnh... đang ngày một đặt ra nhiều yêu cầu mới như tốc độ xử lý, khối lượng công việc thực hiện. ...
Nội dung trích xuất từ tài liệu:
Báo cáo nghiên cứu khoa học " PHƯƠNG PHÁP XỬ LÝ LOGIC VỊ TỪ BẰNG NHỮNG THUẬT TOÁN SONG SONG " PHƯƠNG PHÁP XỬ LÝ LOGIC VỊ TỪ BẰNG NHỮNG THUẬT TOÁN SONG SONG Nguyễn Mậu Hân, Phạm Xuân Thiện Trường Đại học Khoa học, Đại họcHuế 1. Giới thiệu: Ngày nay, những thành công trong việc áp dụng logic vào hệ thống cơ sởdữ liệu để xử lý thông tin đang được nhiều nhà tin học quan tâm, đặc biệt là vấnđề tìm lời giải tối ưu của chương trình logic nói chung và datalog nói riêng. Ởlĩnh vực này, các ứng dụng về dự báo thời tiết, chẩn đoán bệnh... đang ngày mộtđặt ra nhiều yêu cầu mới như tốc độ xử lý, khối lượng công việc thực hiện. Trongchương trình logic và datalog người ta đã đưa ra những phương pháp và thuậttoán xử lý như phương pháp xử lý từ dưới lên (bottom up), phương pháp xử lý từtrên xuống (top down), phương pháp ma tập, tối ưu hóa các câu vấn tin hội, cácđệ qui tuyến tính... nhưng các thuật toán này chỉ thực hiện trong môi trường xử lýtuần tự mà chưa chú ý đến môi trường xử lý song song. Trong thực tế, chưa có một máy tính song song nào cũng như cách phânchia công việc cho các bộ xử lý nào có thể áp dụng có hiệu quả cho mọi bài toán.Do đó, việc chọn lựa mô hình máy tính và cách phân chia công việc để thực hiệnsong song bài toán đóng một vai trò quan trọng. Trong phạm vi bài báo nàychúng tôi xin giới thiệu một vài thuật toán song song thực hiện nhóm các quy tắcđệ quy có quan hệ bao đóng bắc cầu nhằm rút ngắn thời gian thực hiện cũng nhưchi phí kết nối. 2. Một số kiến trúc song song: Data Arithmetic Stream Processor1 1 Data Contr Control Arithmetic Stream2 - Kiến trúc SIMD (Single Stream ol Unit Processor2 2 Signa  instruction multiple data) Arithmetic Data Processorn Stream Instruction 3 Trong một máy SIMD, nhiều Memory thành phần xử lí được giám sát bởi Hình 1: Mô hình của một kiến trúc SIMD một đơn vị điều khiển. Tất cả những thành phần xử lí đều nhận cùng mệnh lệnh từ đơn vị điều khiển nhưng lại thực hiện trên những tập dữ liệu khác nhau và đến từ những luồng dữ liệu khác nhau. Một máy SIMD biểu diễn ở hình 1 với những đặc điểm sau: xử lí phân tán trên một số lượng lớn phần cứng, thực hiện đồng thời trên nhiều thành phần dữ liệu khác nhau và thực hiện cùng một câu lệnh trên các thành phần dữ liệu. - Kiến trúc MIMD Processors .... Processor1 Processor2 ProcessorN(Multiple instruction multipledata): Interconnection Network Một máy tính MIMD là .... Memory Memory Memorymột hệ thống nhiều bộ xử lí và Module1 Module2 ModuleNnhiều bộ nhớ, trong đó mỗi bộ Global Memory Hình 2: Mô hình MIMD chặt, truy cập bộ nhớ đềuxử lí có một đơn vị xử lí riêngvà thực hiện chương trình riêng. Các máy MIMD có các đặc trưng sau: xử líphân tán thông qua một số các bộ xử lí độc lập, chia sẻ tài nguyên chứa trong hệthống bộ nhớ chính, mỗi bộ xử lí thực hiện độc lập, đồng thời và thực hiện cácchương trình riêng. Các hệ thống MIMD thực hiện các phép toán theo dạng songsong không đồng bộ, các nút hoạt động hợp tác chặt chẽ nhưng thực hiện độc lập. Những máy tính MIMD gồm các bộ kết nối chặt và c ...