Xây dựng chương trình xử lý song song để xác định một số nguyên lớn có phải là số nguyên tố hay không?
XÂY DỰNG CHƯƠNG TRÌNH XỬ LÝ SONG SONG ĐỂ XÁC ĐỊNH
MỘT SỐ NGUYÊN LỚN CÓ PHẢI LÀ SỐ NGUYÊN TỐ HAY KHÔNG?
SV. Nguyễn Thị Hoài Thương
Email: [email protected]
Võ Minh Tiến
Email: [email protected]
Lớp ĐHCNTT10, Khoa SP Toán – Tin
GVHD: ThS. Nguyễn Thị Thùy Linh
Tóm tắt nội dung:
Gần đây, sự phát triển của kiến trúc máy tính song song đi kèm theo nó là các
thuật toán song song đã làm thay đổi nhiều quan niệm về khả năng giải quyết các bài
toán lớn hiện nay. Nhiều ứng dụng trong thực tế yêu cầu phải bảo mật và an toàn dữ
liệu nên vấn đề bảo mật và an ninh mạng được quan tâm hàng đầu.
Để tăng khả năng xử lý song song của máy tính song song thì phải khai thác tối
đa năng lực của các bộ xử lý (CPU). Vì vậy, nhằm tăng khả năng tính toán của các
CPU và nâng cao hiệu quả của giải thuật, chúng tôi lựa chọn nghiên cứu “Xây dựng
chương trình xử lý song song để xác định một số nguyên lớn có phải là số nguyên
tố hay không?”. Đề tài có thể giải quyết được vấn đề về cải thiện tốc độ xử lý, đáp
ứng yêu cầu mã hóa trong lĩnh vực an toàn và bảo mật thông tin, đặc biệt là hệ mật mã
RSA.
1. Mở đầu
Tại sao phải xử lý song song?
Hiện nay, với sự xuất hiện ngày càng nhiều các hệ thống điện tử đã làm cho
lượng thông tin trong mọi lĩnh vực phát triển nhanh chóng, có cấu trúc đa dạng và
phức tạp, đòi hỏi máy tính phải xử lý một lượng dữ liệu rất lớn với tốc độ cao. Có thể
nói rằng những máy tính xử lý tuần tự theo kiểu Von Neumann (có 1CPU) khó có thể
đáp ứng được yêu cầu về thời gian và khối lượng công việc thực hiện.
Xử lý song song là quá trình xử lý gồm nhiều tiến trình được kích hoạt đồng thời
và cùng tham gia giải quyết một bài toán. Nói chung, xử lý song song được thực hiện
trên những hệ thống đa bộ xử lý (hay còn gọi là máy tính song song như hiện nay). Do
1
đó, thực hiện xử lý song song trên các máy tính song song để tăng hiệu quả và tốc độ
tính toán của giải thuật.
Mô hình xử lý song song đã và đang phát triển mạnh mẽ, giải quyết những vấn
đề bế tắc mà mô hình xử lý tuần tự gặp phải như: vấn đề thời gian thực hiện chương
trình, tốc độ xử lý, khả năng lưu trữ của bộ nhớ,… Trong bối cảnh đó chúng tôi quyết
định “Xây dựng chương trình xử lý song song xác định một số nguyên lớn có phải
là số nguyên tố hay không?” nhằm giải quyết vấn đề trên.
Bài toán kiểm tra số nguyên tố là một trong những bài toán cơ bản nhưng khá
quan trọng trong khoa học máy tính, đặc biệt là lĩnh vực an toàn và bảo mật thông tin.
Thuật toán song song “xác định một số nguyên lớn có phải là số nguyên tố hay
không?” sẽ đáp ứng được nhu cầu tính toán ngày càng cao về thời gian, tốc độ, quy
mô,.. của bài toán. Nếu không có giải thuật song song cho bài toán này thì thời gian,
tốc độ xử lý chậm, khả năng lưu trữ, quy mô nhỏ và đặc biệt là làm hạn chế việc ứng
dụng bài toán cho các ứng dụng quan trọng…Vì vậy nhu cầu thực hiện tính toán song
song để có thể tính toán, giải quyết một vấn đề nào đó cùng một lúc trên nhiều vi xử lý
khác nhau đã trở nên cấp thiết và cần được nghiên cứu.
2. Kết quả chính
2.1. Đặt vấn đề
Kiểm tra một số có phải số nguyên tố hay không là một bài toán khá quan trọng
trong lĩnh vực bảo mật thông tin. Vì số nguyên tố được sử dụng rất rộng rãi trong các
giải thuật mã hóa dùng khóa mở (public key cryptography algorithms), ứng dụng trong
các bộ phát sinh số giả ngẫu nhiên (pseudorandom) và bảng hash (hash table).
Vấn đề đặt ra là phải kiểm tra số nguyên tố lớn. Việc tính toán trên số nguyên lớn
mất rất nhiều thời gian, đòi hỏi phải xử lý song song cho quá trình xác định số nguyên
lớn có phải là số nguyên tố không? Muốn vậy thì giải thuật đi kèm theo nó phải là
thuật toán song song.
2
2.2. Thiết kế thuật toán song song cho bài toán “xác định một số nguyên lớn có
phải là số nguyên tố hay không?”
2.2.1. Định nghĩa số nguyên tố
Số nguyên tố là số nguyên dương chỉ chia hết cho 1 và chính nó. Theo định nghĩa
này số nguyên tố là số tự nhiên và chỉ có hai ước số phân biệt, đó chính là số 1 và bản
thân nó.
2.2.2. Thiết kế thuật toán
Input: Số nguyên dương x;
Output = True, nếu x là số nguyên tố
Flase, ngược lại
Xử lý:
B1: //Chữ số cuối của x là: 0,2,4,5,6,8
if ( (x chia hết cho 2)
hoặc (x >5 và x chia hết cho 5) )
return false;
B2: //Chữ số cuối của x là: 1,3,7,9
Gọi cx = số ký tự (căn bậc 2 của x); n = số ký tự của x;
cx = (n+1)/2 (lấy phần nguyên);
/*Chứng minh:
ả sử √x =a ;
Gi
cx = số ký tự của a;
n = số ký tự của x;
x sẽ có tối đa: cx + (cx+1) ký tự, tối thiểu cx+(cx-1) ký tự,
Ví dụ: a=84 cx=2, x=a*a=84*84
x có tối đa 2+2+1=5 ký tự, tối thiểu 2+2-1=3 ký tự
84*10 < x < 84*100 ;
Vậy n = 2cx-1 hoặc 2cx hoặc 2cx+1
3
cx = (n+1)/2 hoặc n/2 hoặc (n-1)/2
Ta chọn cx = (n+1)/2 (lớn nhất trong 3 kết quả vì tìm một số gần với kết
quả căn(x) , cho cx lớn nhất mà phải đảm bảo kết quả tìm được lớn hơn
căn(x). Thuật toán sẽ chia từ 3,...căn(x), được quyền chia khỏi căn(x)
nhưng không bỏ sót phần từ nào từ 3…căn(x))
Ví dụ: √125 có (3+1)/2 = 2 ký tự
x=125, n=3, cx=2 (căn(x) có 2 chữ số, nhưng không biết chính xác là số
nào, nên chọn số nguyên lớn nhất có 2 chữ số là 99, khi đó thuật toán sẽ
chia x cho khoảng (3,99).
B3: // Ta có cx là số ký tự của √x
Gọi m là số nguyên lớn nhất có cx ký tự
Thực hiện chia x cho S, với S={3,5,7,9,. . ,m}
Phân hoạch tập S thành S1,S2,S3,S4 tùy ý và ngẫu nhiên.
Phân công cho các nhân CPU xử lý trên 4 tập S1,S2,S3,S4. với
mỗi nhân thực thi lệnh sau:
if ( x chia hết cho i)
return false;
Nếu 1 nhân trả về False thì dừng các nhân còn lại và chương trình
trả về False, ngược lại thì True.
2.3. Cài đặt thuật toán
OpenMP (Open Multi-Processing) đã được các nhà phát triển tích hợp thành
chuẩn trong các ngôn ngữ lập trình phổ biến như: C/C++,…Và được hỗ trợ trong hầu
hết các hệ điều hành. OpenMP là một giao diện lập trình ứng dụng (API - Application
Program Interface) được sử dụng để điều khiển các luồng (Thread) dựa trên cấu trúc
chia sẻ bộ nhớ chung.
Do đó, để cài đặt thuật toán cho bài toán chúng tôi sử dụng ngôn ngữ lập trình
C++ với OpenMP trên Visual Studio 2010.
Cấu trúc dữ liệu:
4
Xây dựng class SuperInt, để khai báo kiểu số nguyên lớn với tối đa 10000 ký tự,
hoặc lớn hơn. Với các phương thức cơ bản: Cộng, Trừ, Nhân, Chia, Chia lấy dư có cấu
trúc như sau:
#include <iostream>
using namespace std;
#include <conio.h>
#include <String.h>
#define maxInt 10000
class SuperInt{
public: char supInt[maxInt];
public:
SuperInt::SuperInt(char *s){
.. .
}
void SuperInt::setValue(char s[]){
.. .
}
bool SuperInt::checkType(){
.. .
}
SuperInt::SuperInt(){}
.. .
};
Hàm kiểm tra số nguyên tố:
bool isChan(SuperInt a){
.. .
}
void isNgto(SuperInt s, SuperInt a, SuperInt b){
.. .
}
Chương trình chính sử dụng thư viện quan trọng: <omp.h>
#include "stdafx.h"
#include "targetver.h"
#include <math.h>
#include <omp.h>
#include <conio.h>
#include "SuperInt.h"
Đoạn chương trình xử lý song song:
#pragma omp parallel shared() private()
{
#pragma omp sections nowait
{
#pragma omp section { //Hàm thực thi}
#pragma omp section { //Hàm thực thi}
}
}
5
2.4. Kết quả thực hiện
Chương trình đã được thực nghiệm trên máy Server của Trường Đại học Đồng
Tháp với cấu hình máy:
-
-
-
Vi xử lý: Intel (R) Xeon (R) CPU E5540 @2.53GHz (8CPUs), ~2.5GHz
Bộ nhớ trong: 6132 MB RAM
Hệ điều hành: Windows Server® 2008 Standard (6.0, Build 6002)
Kết quả thực nghiệm:
Số nguyên lớn
2147483647
Song song (s)
11.03621
Tuần tự (s)
45.70646
68718952447
274876858367
120.56385
130.56179
509.29799
564.68737
Bảng 1 : Thống kê kết quả
6
Thời gian (s)
600
500
400
300
200
100
Tuần tự
Song song
Số nguyên
lớn
2147483647
68718952447
274876858367
0
Hình 1: Đồ thị so sánh kết quả
Nhận xét:
Thời gian thực hiện chương trình rút ngắn (tốc độ xử lý song song nhanh hơn
khoảng 4 lần so với tốc độ xử lý tuần tự). Tốc độ này tính bằng giây (s) và còn tùy
thuộc vào lượng công việc hiện có trong hệ thống.
Giải thuật chỉ tối ưu với số nguyên dương lớn hơn 10 chữ số trong cùng giải thuật
và xử lý song song, vì các phép toán cơ bản phải thực hiện qua bước trung gian của
class SuperInt.
Phương pháp kiểm tra số nguyên tố cổ điển là đơn giản và dễ thực hiện, đương
nhiên nó được áp dụng đối với bài toán có dữ liệu nhỏ, độ phức tạp bình thường và
thời gian cho phép,...
7
Phương pháp xây dựng thuật toán song song “xác định một số nguyên lớn có
phải là số nguyên tố hay không? đã giải quyết được những vấn đề:
- Kiểm tra được số nguyên lớn là số nguyên tố.
- Tận dụng tối đa sức mạnh của các máy tính đa xử lý hiện nay.
- Tốc độ xử lý song song nhanh hơn nhiều lần so tốc độ xử lý tuần tự.
- Tăng tốc các ứng dụng, tăng hiệu suất làm việc cho người sử dụng.
Việc áp dụng kết quả nghiên cứu đã tạo điều kiện cho sinh viên chuyên nghành
CNTT nói chung và sinh viên chuyên ngành CNTT Trường Đại học Đồng Tháp nói
riêng, khai thác được tối đa năng lực các CPU, tạo tiền đề cho giải quyết các bài toán
lớn, đặc biệt là tăng tốc độ xử lý và mang lại hiệu quả trong lĩnh vực an toàn và bảo
mật thông tin.
8
Tài liệu tham khảo
[1] Đoàn Văn Ban, Nguyễn Mậu Hân, Xử lý song song và phân tán, NXB KH&KT,
2006.
[2] TS. Trần Văn Hoài, Bài giảng môn học sau đại học Tính toán song song.
[3] PGS.TS. Trần Văn Lăng, Bài giảng Tính toán song song và phân tán.
[4] PGS.TS. Nguyễn Đức Nghĩa, Bài giảng môn Tính Toán song song, NXB Đại học
Bách Khoa Hà Nội, 2008.
[5] Hội nghị sinh viên nghiên cứu khoa học năm 2013 Lĩnh vực Khoa học Tự nhiên,
Trường Đại Học Đồng Tháp.
[6] Gunnar Staff. “Convergence and Stability of the Parallel algorithm: A numerical
and theoretical investigation” – Department of Mathematical Sciences,
Norwegian University of Science and Technology, N-7491 Trondheim, Norway.
[7] “Introduction to OpenMP” – subpercomputing Institute of Minnesota University
9
9 trang
23360
Free
Bạn đang xem tài liệu "Xây dựng chương trình xử lý song song để xác định một số nguyên lớn có phải là số nguyên tố hay không?", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- xay_dung_chuong_trinh_xu_ly_song_song_de_xac_dinh_mot_so_ngu.pdf
