Xây dựng hệ thống tính toán song song cho bài toán tính FFT hữu hạn

Xử lý song song được xem là một giải pháp hiệu quả nhằm nâng cao hiệu năng tính toán của hệ thống, đặc biệt trong các bài toán yêu cầu về tốc độ xử lý nhanh trong khi khối lượng dữ liệu cần xử lý là rất lớn. Với một hệ thống xử lý song song, ngoài các giải thuật song song đòi hỏi phải có một cơ sở hạ tầng phần cứng song song đủ mạnh để thực thi các giải thuật này. Trong phạm vi của bài báo, nhóm tác giả đề xuất và xây dựng một hệ thống xử lý song song áp dụng cho bài toán tính FFT (Fast Fourier Transform) hữu hạn.
Nội dung trích xuất từ tài liệu:
Xây dựng hệ thống tính toán song song cho bài toán tính FFT hữu hạn THE INTERNATIONAL CONFERENCE ON MARINE SCIENCE AND TECHNOLOGY 2016 Xây dựng hệ thống tính toán song song cho bài toán tính FFT hữu hạn Design of parallel computing system for solving limited FFT problem Nguyễn Bình Minh, Lê Quốc Định, Nguyễn Trọng Đức Trường Đại học Hàng hải Việt Nam, minhnb@vimaru.edu.vn Tóm tắt Xử lý song song được xem là một giải pháp hiệu quả nhằm nâng cao hiệu năng tính toán của hệ thống, đặc biệt trong các bài toán yêu cầu về tốc độ xử lý nhanh trong khi khối lượng dữ liệu cần xử lý là rất lớn. Với một hệ thống xử lý song song, ngoài các giải thuật song song đòi hỏi phải có một cơ sở hạ tầng phần cứng song song đủ mạnh để thực thi các giải thuật này. Trong phạm vi của bài báo, nhóm tác giả đề xuất và xây dựng một hệ thống xử lý song song áp dụng cho bài toán tính FFT (Fast Fourier Transform) hữu hạn. Từ khóa: Tính toán song song, máy tính cụm, Raspberry Pi 2, biến đổi Fourier nhanh. Abstract Parallel computing has been considered as an efficient solution to improve performance of computation systems. This is particularly the case of computing a large amount of computation in a short time. In a parallel computing system, along with a set of algorithms, there must be a parallel hardware infrastructure which is sufficient to execute these algorithms. In this paper the authors proposed and designed a parallel computing system for solving the limited FFT problem. Keywords: Parallel computing, cluster computer, raspberry Pi2, FFT. 1. Đặt vấn đề Việc ứng dụng máy tính trong hầu hết các lĩnh vực đã góp phần quan trọng thúc đẩy sự phát triển kinh tế - xã hội. Đặc biệt, trong lĩnh vực tính toán, máy tính là công cụ không thể thiếu khi giải quyết những bài toán đòi hỏi khối lượng tính toán lớn, độ chính xác cao (điều khiển tàu vũ trụ, xử lý thông tin về gen, điều khiển các lò phản ứng hạt nhân,..). Với những bài toán này, việc tính toán xử lý chỉ trên một bộ vi xử lý hoặc trên một máy tính cá nhân không thể đáp ứng được yêu cầu đặt ra. Giải pháp cho vấn đề này đó là sử dụng các siêu máy tính hoặc kết hợp nhiều máy tính với nhau để tính toán. Khi đó, nhu cầu xây dựng một hệ thống có khả năng tính toán song song để có thể tính toán, giải quyết một vấn đề nào đó cùng lúc tại nhiều máy tính khác nhau trở nên cấp thiết và đã được các nhà khoa học tập trung nghiên cứu [1]. Khái niệm về hệ thống tính toán song song ra đời. Tính toán song song hay xử lý song song là quá trình xử lý thông tin trong đó nhấn mạnh việc nhiều đơn vị dữ liệu và nhiều câu lệnh được xử lý đồng thời bởi một hay nhiều bộ xử lý để giải quyết một bài toán [2]. Với phương pháp lập trình cổ điển việc thực hiện tuần tự các lệnh trong một chương trình không giúp phát huy được tối đa hiệu năng của các hệ thống song song. Điều này đòi hỏi phải có những giải thuật, chương trình phù hợp để tận dụng được sức mạnh của các hệ thống đó, vì vậy giải pháp lập trình song song ra đời. Trong lập trình song song, các hoạt động song song của chương trình được xác định một cách rõ ràng, những hoạt động này thường được xem như là tiến trình hay là tác vụ. Bên cạnh đó, là các ngôn ngữ lập trình song song có khả năng điều chỉnh các tình huống mà ở đó các tiến trình đòi hỏi phải trao đổi, tương tác với nhau. Một chương trình song song sẽ cho hiệu năng cao nếu biết ứng dụng tốt các ngôn ngữ lập trình song song thích hợp và các giải thuật song song tốt nhất. Như vậy, một hệ thống xử lý song song sẽ liên quan trực tiếp đến kiến trúc phần cứng, phần mềm hệ thống, các giải thuật và ngôn ngữ lập trình [2-4]. HỘI NGHỊ QUỐC TẾ KHOA HỌC CÔNG NGHỆ HÀNG HẢI 2016 429 THE INTERNATIONAL CONFERENCE ON MARINE SCIENCE AND TECHNOLOGY 2016 Trong phạm vi của bài báo, nhóm tác giả đề xuất và xây dựng một hệ thống tính toán song song với mô hình kiến trúc phân cụm. Thử nghiệm hệ thống với giải thuật biến đổi nhanh Fourier, trên cơ sở đó đưa ra những đánh giá về hiệu năng của hệ thống đạt được. Nội dung bài báo bao gồm 04 mục, mục 1 - Mở đầu, mục 2 - Hệ thống tính toán song song, đưa ra mô hình, kiến trúc hệ thống. Mục 3 - Xây dựng hệ thống và mục 4 - Kết luận, là những đánh giá về hệ thống đã xây dựng cũng như hướng nghiên cứu, phát triển tiếp theo. 2. Hệ thống tính toán song song 2.1. Kiến trúc máy tính song song Một trong những phân loại kiến trúc máy tính song song được biết đến nhiều nhất là phân loại của Michael Flynn. Cách phân loại này dựa vào đặc tính số lượng bộ xử lý, số lệnh thực hiện, cấu trúc bộ nhớ,… để chia máy tính thành bố n loại: kiến trúc đơn dòng lệnh - đơn dòng dữ liệu (SISD); kiến trúc đơn dòng lệnh - đa dòng dữ liệu (SIMD); kiến trúc đa dòng lệnh - đơn dòng dữ liệu (MISD) và kiến trúc đa dòng dữ liệu - đa dòng lệnh (MIMD) [5]. Hình 1a. Kiến trúc SISD Hình 1b. Kiến trúc SIMD Hình 1c. Kiến trúc MISD Hình 1d. Kiến trúc MIMD - Kiến trúc SISD (Single Instruction-Single Data), hệ thống chỉ bao gồm một đơn vị điều khiển và một đơn vị thực hiện, như vậy ở mỗi thời điểm chỉ thực hiện được một lệnh (hình 1a); - Kiến trúc SIMD (Single Instruction-Multiple Data), hệ thống bao gồm một đơn vị điều khiển và nhiều đơn vị thực hiện, như vậy ở mỗi thời điểm có thể thực hiện được một lệnh trên nhiều dòng dữ liệu khác nhau (hình 1b); - Kiến trúc MISD (Multiple Instruction-Single Data), hệ thống bao gồm nhiều đơn vị điều khiển và một đơn vị thực hiện, như vậy ở mỗi ...