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 
HỘI NGHỊ QUỐC TẾ KHOA HỌC CÔNG NGHỆ HÀNG HẢI 2016 429 
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]. 
THE INTERNATIONAL CONFERENCE ON MARINE SCIENCE AND TECHNOLOGY 2016 
HỘI NGHỊ QUỐC TẾ KHOA HỌC CÔNG NGHỆ HÀNG HẢI 2016 430 
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 thời điểm có thể thực hiện được nhiều lệnh 
trên cùng một dòng dữ liệu (hình 1c); 
THE INTERNATIONAL CONFERENCE ON MARINE SCIENCE AND TECHNOLOGY 2016 
HỘI NGHỊ QUỐC TẾ KHOA HỌC CÔNG NGHỆ HÀNG HẢI 2016 431 
- Kiến trúc MIMD (Multiple Instruction-Multiple Data), hệ thống bao gồm nhiều đơ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 nhiều 
lệnh trên nhiều dòng dữ liệu khác nhau (hình 1d). 
Từ phân loại của Michael Flynn có thể thấy, các mô hình kiến trúc cho một hệ thống tính 
toán song song có thể sử dụng: kiến trúc SIMD và MIMD. 
2.2. Hệ thống tính toán song song 
Như đã đề cập trên, các mô hình kiến trúc cho một hệ thống tính toán song song có thể sử 
dụng bao gồm kiến trúc SIMD và MIMD. Khi đó, các mô hình lập trình song song tương ứng được 
đề xuất [5]: 
- Mô hình chia sẻ bộ nhớ (Shared Memory): các máy tính trong hệ thống chia sẻ bộ nhớ với 
nhau, lệnh và dữ liệu được chia sẻ theo luồng (Thread). Mô hình lập trình tương ứng cho 
các hệ thống này đó là lập trình luồng (hình 2a); 
- Mô hình phân tán bộ nhớ (Distributed Memory): hệ thống bao gồm các máy đơn được kết 
nối với nhau qua mạng liên kết. Mô hình lập trình tương ứng cho các hệ thống này đó là 
truyền thông thông điệp (hình 2b). 
Hình 2a. Mô hình chia sẻ bộ nhớ Hình 2b. Mô hình phân tán bộ nhớ 
Hình 2a minh họa cho hệ thống đa bộ vi xử lý (đa nhân - Core) được tích hợp trên cùng hệ 
thống vật lý duy nhất. Mỗi nhân thực hiện việc xử lý tuần tự từng gói dữ liệu, tuy nhiên sự kết hợp 
của nhiều nhân sẽ làm tăng tốc độ xử lý chung của hệ thống. 
Hình 2b minh họa cho hệ thống đa máy tính (máy tính cụm - Cluster), các máy tính độc lập 
được kết nối với nhau thành một hệ thống thống nhất thông qua việc sử dụng các phần mềm và các 
công nghệ kết nối mạng thích hợp. Hiệu năng của hệ thống được cải thiện nhờ khả năng tính toán 
song song của các máy con trong hệ thống khi các ứng dụng tính toán phức tạp được “chia nhỏ” 
thành các tác vụ. 
Trong phạm vi của bài báo, hệ thống tính toán song song mà nhóm tác giả đề xuất và xây 
dựng là một hệ thống tính toán cụm. 
3. Xây dựng hệ thống 
3.1. Hệ thống tính toán song song với Rasp Berry Pi 2 
Hệ thống tính toán phân cụm được chỉ ra trong hình 3. Các Computer Node thực hiện các 
tác vụ tính toán, trong khi các Management Node có vai trò là một giao diện để giao tiếp giữa hệ 
thống với người sử dụng, tất cả được kết nối bởi một hệ thống mạng Ethernet [6]. 
THE INTERNATIONAL CONFERENCE ON MARINE SCIENCE AND TECHNOLOGY 2016 
HỘI NGHỊ QUỐC TẾ KHOA HỌC CÔNG NGHỆ HÀNG HẢI 2016 432 
Hình 3. Kiến trúc hệ thống máy tính cụm 
Hệ thống mà nhóm tác giả đề xuất sử dụng 04 máy tính mini Raspberry Pi 2 như các 
Computer Node, các Node được kết nối với nhau qua mạng Ethernet: 10/100 Mbs (Hình 4). 
Hình 4. Hệ thống tính toán song song với Rasp Berry Pi 2 
Các Raspberry Pi 2 được lựa chọn với cấu hình CPU 4 lõi, xung nhịp 900 MHz kiến trúc 
ARM, bộ nhớ RAM 1Gb (DDR2) [7]. Hệ thống chạy trên hệ điều hành Linux, mô hình lập trình 
truyền thông thông điệp (MPI-Message Passing Interface), sử dụng các thư viện mở MPICH. 
3.2. Biến đổi Fourier nhanh 
Biến đổi Fourier: chuyển tín hiệu x(n) từ miền thời gian sang miền tần số ω (hay tần số f = 
ω/2π) [8]: 
( ) ( )j j n
n
X e x n e 
 
Khi đó X(ejω) là một hàm biến phức vì vậy có thể biểu diễn nó trong miền tần số ω dưới 
dạng phần thực và phần ảo. Tuy nhiên, trong thực tế chỉ có số lượng hữu hạn các giá trị rời rạc 
được lưu trữ, vì vậy ω được rời rạc hóa trong miền giá trị từ 0 đến 2π thành n điểm với khoảng cách 
2π/n. Với phương pháp biến đổi như vậy, độ phức tạp về thời gian tính toán cho n điểm (mẫu) là 
O(n2). Để tăng hiệu năng tính toán, phương pháp biển đổi Fourier nhanh (FFT- Fast Fourier 
Transform) được hình thành. Ý tưởng chủ đạo của FFT là chia bài toán thành các bài toán con để 
tính toán (chia và trị). Khi đó, độ phức tạp về thời gian tính toán cho n điểm là O (nlogn). 
Bài toán tính FFT đã được giải quyết, tuy nhiên khi lượng mẫu rất lớn, vấn đề xử lý trở lên 
phức tạp với một hệ thống máy đơn và giải thuật tính toán tuần tự. Trong khuôn khổ của bài báo 
THE INTERNATIONAL CONFERENCE ON MARINE SCIENCE AND TECHNOLOGY 2016 
HỘI NGHỊ QUỐC TẾ KHOA HỌC CÔNG NGHỆ HÀNG HẢI 2016 433 
này, nhóm tác giả đề xuất giải thuật song song cho phép tính FFT trên hệ thống Rasp Berry Pi 2, 
giải thuật gồm ba pha chính. 
- Pha thứ nhất, hoán vị các giá trị tần số đầu vào và sắp xếp lại các chỉ số; 
- Pha thứ hai, thực hiện các thao tác (nhân chập) với logn giá trị tần số; 
- Pha thứ ba, lặp lại các bước trên khắp các hướng của mảng. 
Gọi n là số mẫu vào, p là số phần tử xử lý trong hệ thống, với giải thuật tính FFT song song, 
độ phức tạp về thời gian tính toán cho n mẫu là O (nlogn/p). 
3.3. Thử nghiệm giải thuật song song trên Raspberry Pi 2 
Tiến hành thử nghiệm giải thuật song song trên Raspberry Pi 2 (hình 5), kết quả thu được 
như mô tả trong bảng 1: 
Bảng 1. Kết quả thử nghiệm 
STT Số phần tử Giải thuật tuần tự (ms) Giải thuật song song (ms) 
1 256 0.000868 0.038 
2 4096 0.015 0.047 
3 65536 0.36 0.20 
4 1048576 7.53 3.43 
5 16777216 151.29 53.83 
Trong lần thứ nhất, số phần tử đầu vào n = 256, thời gian thực hiện FFT tuần tự ttt = 
0.000868 ms, thời gian thực hiện FFT song song tss = 0.038 ms. Tương tự, ở lần 2: ttt = 0.015 ms và 
tss = 0.047 ms. Như vậy có thể thấy với những bộ dữ liệu nhỏ, thời gian thực hiện giải thuật song 
song lớn hơn so với giải thuật tuần tự. Điều này có thể lí giải do ngoài thời gian tính toán, hệ thống 
còn chi phí lượng thời gian không nhỏ cho truyền thông giữa các nút. Tuy nhiên, khi số phần tử đầu 
vào đủ lớn (lần 3, 4 và 5) thời gian thực hiện giải thuật song song giảm đi đáng kể (lần 5: 
53.83/151.29), điều này đồng nghĩa với việc hiệu năng của hệ thống đã được cải thiện (tăng lên gần 
3 lần). 
Hình 5. Kết quả thử nghiệm FFT song song trên Rasp Berry Pi 2 
THE INTERNATIONAL CONFERENCE ON MARINE SCIENCE AND TECHNOLOGY 2016 
HỘI NGHỊ QUỐC TẾ KHOA HỌC CÔNG NGHỆ HÀNG HẢI 2016 434 
4. Kết luậ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 khi yêu cầu về tốc độ xử lý nhanh song khối lượng dữ liệu 
cần xử lý khổng lồ. 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 khuôn khổ 
của bài báo, nhóm tác giả đã xây dựng thành công hệ thống tính toán song song hiệu năng cao dựa 
trên mô hình kiến trúc máy tính cụm với nền tảng là các máy tính mini Raspberry Pi 2. Bên cạnh 
đó, giải thuật song song tính FFT cũng được đề cập, từ đó nhóm tác giả tiến hành cài đặt thử 
nghiệm và đưa ra những so sánh nhằm khẳng định sự ưu việt trong hiệu năng của hệ thống đã được 
xây dựng. 
Tài liệu tham khảo 
[1]. Hesham El-Rewini, Mostafa ABD-El-Barr. Advanced Computer Architecture and Parallel 
processing. Willey. 2005. 
[2]. Thomas Rauber, Gudula Runger. Parallel Programming. Springer. 2007. 
[3]. Nguyễn Đức Nghĩa. Tính Toán Song Song. NXB Đại học Quốc gia Hà Nội. 2007. 
[4]. Lê Huy Thập. Cơ sở lí thuyết song song. NXB Thông tin và truyền thông. 2010. 
[5]. K. Hwang. Advanced Computer Architecture. McGraw-Hill Education (India). 2010. 
[6]. Barry Wlkingson, Michael Allen. Parallel Programming, Technique and Applications Using 
Networked Workstations and Parallel Computers. Prentice Hall New Jersey. 1999. 
[7]. Andrew K. Dennis. Raspberry Pi Super Cluster. Birmingham Publishing. 2013. 
[8]. Quách Tuấn Ngọc. Xử lý tín hiệu số. NXB Giáo dục. 1997.