Nghiên cứu tính toán song song và ứng dụng vào hệ thống tính cước data 3G

1 HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- NHỮ THANH THẾ NGHIÊN CỨU TÍNH TOÁN SONG SONG VÀ ỨNG DỤNG VÀO HỆ THỐNG TÍNH CƯỚC DATA 3G TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI - 2013 2 Luận văn được hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: TS. TRỊNH ANH TUẤN Phản biện 1: ……………………………………………………………… Phản biện 2: ……………………………………………………..……….. Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ....... giờ ....... ngày ....... tháng ....... .. năm ............... Có thể tìm hiểu luận văn tại: - Thư viện của Học viện Công nghệ Bưu chính Viễn thông 3 MỞ ĐẦU 1. Lý do chọn đề tài Nhu cầu tính toán trong lĩnh vực khoa học, công nghệ ngày càng cao và trở thành một thách thức lớn, từ đó các giải pháp nhằm tăng tốc độ tính toán đã được ra đời, từ năm 2001 đến năm 2003 tốc độ của Pentium 4 đă tăng gấp đôi từ 1.5GHz lên đến 3GHz, tuy nhiên hiệu năng của CPU (Central Processing Unit) không tăng tương xứng như mức gia tăng xung của CPU, và việc gia tăng tốc độ xung của CPU nhanh chóng chạm phải ngưỡng tối đa mà cụ thể trong khoảng thời gian 2 năm từ năm 2003 đến năm 2005 tốc độ của CPU chỉ tăng từ 3GHz lên 3.8GHz. Trong quá trình tăng tốc độ xung của CPU các nhà sản xuất đã chạm phải vấn đề về nhiệt độ của CPU sẽ quá cao và các giải pháp tản nhiệt khí đã đến mức tới hạn không thể đáp ứng được khả năng làm mát khi CPU hoạt động ở xung quá cao như vậy. Vì vậy việc gia tăng xung hoạt động của CPU không sớm thì muộn cũng sẽ đi vào bế tắc. Trước tình hình này, các nhà nghiên cứu vi xử lý đã chuyển hướng sang phát triển công nghệ đa lõi, nhiều lõi, với cơ chế xử lý song song trong các máy tính nhằm tăng hiệu năng và tiết kiệm năng lượng. Với dữ liệu lớn mà Hệ thống tính cước data 3g mạng Vinaphone đang đảm nhiệm, cần tăng tốc xử lý và tính toán. Để đảm bảo thời gian cung cấp thông tin cho khách hàng. Xuất phát từ nhu cầu trên tôi chọn đề tài: “NGHIÊN CỨU TÍNH TOÁN SONG SONG VÀ ỨNG DỤNG VÀO HỆ THỐNG TÍNH CƯỚC DATA 3G” 4 2. Luận văn được tổ chức thành ba chương Chương 1. Nghiên cứu tổng quan về tính toán song song - Giới thiệu chung tính toán song song - Phân loại máy tính toán song song - Các mô hình lập trình tính toán song song Chương 2. Nghiên cứu thư viện lập trình song song Pthread - Giới thiệu PThread - Cài đặt PTHREAD với Visual studio 2008 64bit - Giới thiệu các hàm chính của pthread - Đồng bộ hóa các tác vụ trong Pthread - Một số ví dụ mẫu về Pthread Chương 3: Ứng dụng tính toán song song vào bài toán tính cước data 3g cho Vinaphone. - Khảo sát hiện trạng hệ thống - Đề xuất giải pháp tính cước data 3g trên hệ đa lõi - Phân tích, thiết kế hệ thống tính cước - Cài đặt và thử nghiệm - So sánh, đánh giá kết quả giữa chương trình trước và sau khi áp dụng tính toán song song 5 Chương 1 - NGHIÊN CỨU TỔNG QUAN VỀ TÍNH TOÁN SONG SONG 1.1. Tổng quan về tính toán song song Khoa học kỹ thuật ngày càng phát triển, đặt ra nhiều bài toán với khối lượng tính toán rất lớn. Trong số đó có những bài toán mà kết quả chỉ có ý nghĩa nếu được hoàn thành trong khoảng thời gian cho phép. Để giải quyết những bài toán này, người ta đã nghiên cứu tăng tốc độ tính toán bằng hai phương pháp hay kết hợp cả hai: - Phương pháp 1: Cải tiến công nghệ, tăng tốc độ xử lý của máy tính. Công việc này đòi hỏi nhiều thời gian, công sức và tiền của, nhưng tốc độ cũng chỉ đạt được đến một giới hạn nào đó. - Phương pháp 2: Chia bài toán ra thành những công việc nhỏ để có thể chạy song song trên nhiều bộ xử lý. Việc phát triển công nghệ tính toán theo phương pháp 2 đã cho ra đời công nghệ tính toán song song, đó là việc sử dụng đồng thời nhiều tài nguyên tính toán để giải quyết một bài toán. Các tài nguyên tính toán có thể bao gồm một máy tính với nhiều bộ vi xử lý, một tập các máy tính kết nối mạng hay là một sự kết hợp của hai dạng trên.. 1.1.1. Các mô hình tính toán song song Một hệ thống máy tính song song là một máy tính với nhiều hơn một bộ xử lý cho phép xử lý song song. Dựa vào sự phân biệt ở kết nối giữa các bộ xử lý (hay thành phần xử lý), giữa bộ xử lý và bộ nhớ mà có rất nhiều loại kiến trúc máy tính song song khác nhau. Nhưng theo nguyên tắc phân loại của Flynn thì có hai kiến trúc máy tính song song song thông dụng sau: ƒ SIMD - Single Instruction Multiple Data: đơn lệnh đa dữ liệu ƒ MIMD - Multiple Instruction Multiple Data: đa lệnh đa dữ liệu 6 1.1.1.1. Mô hình đơn lệnh đa dữ liệu – SIMD SIMD là một kiểu máy tính song song có tất cả các bộ xử lý chỉ thực hiện một lệnh duy nhất. Tuy nhiên lệnh này được thực hiện trên các bộ dữ liệu khác nhau ứng với từng bộ xử lý khác nhau. Mô hình này có ưu điểm là đơn giản trong phần cứng cũng như phần mềm nhưng chỉ phù hợp để giải quyết các vấn đề tương đối đặc thù có tính cân đối cao trong xử lý như xử lý ảnh … Các giải thuật cho các đa máy tính thường chạy không hiệu quả trên các máy SIMD. 1.1.1.2. Mô hình đa lệnh đa dữ liệu – SIMD MIMD là một mô hình kiến trúc máy tính song song thông dụng hiện nay. Với mô hình này thì tất cả các bộ xử lý sẽ thực hiện các lệnh khác nhau với các dữ liệu riêng khác nhau. Sự thực thi các lệnh có thể theo cơ chế đồng bộ hoặc không đồng, xác định hay không xác định. Điều này giúp cho mô hình MIMD rất linh hoạt trong việc xử lý song song. 1.2. Mô hình lập trình song song Công việc lập trình song song bao gồm việc thiết kế, lập trình các chương trình máy tính song song sao cho nó chạy được trên các hệ thống máy tính song song. Hay có nghĩa là song song hoá các chương trình tuần tự nhằm giải quyết một vấn đề lớn hoặc làm giảm thời gian thực thi hoặc cả hai. Lập trình song song tập trung vào việc phân chia bài toán tổng thể ra thành các công việc con nhỏ hơn rồi định vị các công việc đó đến từng bộ xử lý và đồng bộ các công việc để nhận được kết quả cuối cùng. Nguyên tắc quan trọng nhất ở đây chính là tính đồng thời hoặc xử lý nhiều tác vụ cùng một lúc. Có hai hướng chính trong việc tiếp cận lập trình song song: - Song song hoá ngầm định: bộ biên dịch hay một vài chương trình khác tự động phân chia các công việc đến các bộ xử lý. 7 - Song song hoá tường minh: người lập trình phải tự phân chia chương trình của họ đế nó có thể thực thi song song. Hiện nay có rất nhiều mô hình lập trình song song: Đa luồng, Truyền thông điệp, Song song dữ liệu, Lai 1.2.1. Mô hình đa luồng Nhiều hệ thống cung cấp sự hỗ trợ cả hai luồng nhân và luồng người dùng nên tạo ra nhiều mô hình đa luồng khác nhau. Chúng ta sẽ xem xét ba loại cài đặt luồng thông thường. 1.2.1.1. Mô hình 1:1 (thread cấp nhân) Mô hình một-một ánh xạ mỗi luồng người dùng tới một luồng nhân. Nó cung cấp khả năng đồng hành tốt hơn mô hình nhiều-một bằng cách cho một luồng khác chạy khi một luồng thực hiện lời gọi hệ thống nghẽn; nó cũng cho phép nhiều luồng chạy song song trên các bộ xử lý khác nhau. 1.2.1.2. Mô hình N:1 (thread cấp người dùng) Một mô hình N:1: tất cả các thread cấp ứng dụng đều vạch ra một đơn thực thể được lập lịch cấp nhân. Nhân không có tri thức về thread ứng dụng. Với phương pháp này, ngữ cảnh chuyển có thể được hoàn thành rất nhanh và ngoài ra, nó có thể được thực hiện ngay cả trên những nhân đơn giản mà không hỗ trợ thread. 1.2.1.3. Mô hình N:M (thread tích hợp) Mô hình N:M chỉ ra với N thread ứng dụng tương ứng với M thực thể nhân Đây là kết hợp giữa cấp nhân (1:1) và cấp người dùng (N:1). Nói chung, hệ thống thread N:M thể hiện phức tạp hơn thread nhân hoặc thread người dùng, bởi vì đòi hỏi mã của cả thread nhân và thread người dùng. 8 1.2.2. Mô hình truyền thông điệp Truyền thông điệp là mô hình được sử dụng rộng rãi trong tính toán song song hiện nay. Nó thường áp dụng cho các hệ thống phân tán. 1.2.3. Mô hình song song dữ liệu Mô hình song song dữ liệu nhấn mạnh các thao tác song song trên một tập dữ liệu. Các luồng làm việc chung trên cùng một cấu trúc dữ liệu nhưng ở các phần khác nhau. 1.2.4. Mô hình lai Là sự kết hợp của hai hay nhiều mô hình lập trình song song để tạo ra sự thuận lợi và hiệu quả hơn trong việc tính toán. 1.2.5. Mô hình đơn chương trình đa dữ liệu Mô hình đơn chương trình đa dữ liệu là một mô hình lập trình ở mức cao mà có thể thực hiện bởi sự kết hợp các mô hình lập trình song song ở trên. Một chương trình được thực thi bởi tất cả các tác vụ cùng một lúc và các tác vụ sử dụng các dữ liệu khác nhau. 1.2.6. Mô hình đa chương trình đa dữ liệu Giống như SPMD, mô hình đa chương trình đa dữ liệu (MPMD) là một mô hình lập trình ở mức cao mà có thể thực hiện bởi sự kết hợp các mô hình lập trình song song ở trên. 1.3. Sự cần thiết của công cụ phát triển ứng dụng song song Lập trình là một công việc đòi hỏi cần đầu tư nhiều công sức và thời gian. Vì thế các môi trường phát triển tích hợp đã được phát triển từ rất sớm nhằm trợ giúp cho các lập trình viên thuận lợi hơn trong việc lập trình đồng thời làm giảm thời gian lập trình. Hiện nay, các môi trường phát triển tích hợp như Microsoft Visual Studio, Borland Studio, Eclipse,... thực sự đã làm cho việc lập trình trở lên dễ dàng thậm chí đối với cả những người mới bắt đầu học lập trình. 9 Chương 2 – NGHIÊN CỨU THƯ VIỆN LẬP TRÌNH SONG SONG PTHREAD Thread là một mô hình lập trình phổ biến cho phép nhiều thread đơn có thể chạy trên cùng một tiến trình, và các thread này có thể chia sẻ tài nguyên của tiến trình cũng như có thể tính toán độc lập. Và ứng dụng hữu ích nhất của mô hình này là khi nó được áp dụng cho một tiến trình đơn lẻ để cho phép tính toán song song trên một hệ thống đa xử lý. Trong bản luận văn này, tôi sẽ trình bày mô hình này trên chuẩn IEEE POSIX 1003.1c, được gọi là POSIX thread hay Pthread. 2.1. Giới thiệu về Thread và Multithread 2.1.1. Tổng quan về Thread Trong khoa học máy tính một chuỗi các tính toán kết quả từ một nhánh của một chương trình máy tính chia thành hai hoặc nhiều nhiệm vụ chạy đồng thời. Sự thể hiện của các thread và tiến trình là khác nhau trong một hệ điều hành, nhưng trong hầu hết các trường hợp, một thread được nằm bên trong một tiến trình. Nhiều thread có thể tồn tại cùng trong một tiến trình và chia sẻ tài nguyên như bộ nhớ, trong khi những tiến trình khác nhau không thế chia sẻ tài nguyên. 2.1.2. So sánh Thread với tiến trình Thread khác với tiến trình trong hệ điều hành đa nhiệm truyền thống ở các điểm sau: - Các tiến trình thường được độc lập, còn các thread thì tồn tại như là các tập con của một tiến trình. - Tiến trình có trạng thái thông tin đáng kể, trong khi nhiều thread trong một tiến trình chia sẽ trạng thái tiến trình cũng như bộ nhớ và các tài nguyên khác. - Tiến trình có vùng địa chỉ riêng biệt, trong khi thread chia sẽ không gian địa chỉ của chúng. - Ngữ cảnh chuyển giữa các thread trong cùng một tiến trình thường sẽ nhanh hơn chuyển giữa các tiến trình. 10 2.1.3. Đa thread và những lợi thế Multi thread như là một mô hình lập trình phổ biến và cho phép thực hiện nhiều thread tồn tại trong một tiến trình đơn. Những thread này chia sẻ tài nguyên của tiến trình nhưng cũng có thể tính toán độc lập. Mô hình lập trình thread cung cấp cho người phát triển những sự hữu ích của việc tính toán đồng thời. Lợi thế này của lập trình multi thread cho phép nó tính toán nhanh hơn trên hệ thống máy tính có nhiều CPU, CPU với nhiều nhân hoặc qua một cụm máy – bởi vì những thread của chương trình cho vay chính bản thân nó để thực hiện sự đồng thời. 2.1.4. Vấn đề đưa ra của thread Truy cập đồng thời và cấu trúc dữ liệu, những thread trong cùng một tiến trình chia sẻ cùng không gian địa chỉ, điều này cho phép đồng thời chạy các đoạn mã thành từng cặp để trao đổi dữ liệu một cách thuận tiện và chặt chẽ mà không cần chi phí hoạt động hoặc sự phức tạo của giao tiếp liên tiến trình. Tuy nhiên, khi chia sẽ giữa các thread, kể cả những cấu trúc dữ liệu đơn giản cũng trở nên rủi ro nếu chúng yêu cầu nhiều hơn một cấu trúc CPU để cập nhật: hai thread có thể cố gắng cập nhật cấu trúc dữ liệu cùng lúc và tìm thấy những sự thay đổi không mong muốn. 2.2. Cài đặt Pthread với Visual studio 2008 64bit Mục này hướng dẫn chi tiết nguồn tải các lib, inlcule và cấu hình Pthread với Visual studio 2008 64bit. 2.3. Lập trình trên POSIX THREAD 2.3.1. Tổng quan về Pthread 2.3.1.1. Khái niệm Pthread Thread là một dòng các điều khiển trong một process hay một ứng dụng. 11 2.3.1.2. Tại sao lại sử dụng Pthread Động lực chính đế sử dụng Pthread là để nhận ra hiệu quả tiềm năng của một chương trình. Khi so sánh với việc tạo ra và quản lý một process, một thread được tạo ra với ít chi phí hoạt động của hệ điều hành hơn. Quản lý thread cũng yêu cầu ít tài nguyên hệ thống hơn là quản lý process. 2.3.1.3. Các pthread API Những Ptrhead API thông thường được định nghĩa trong chuẩn ANSI/IEEE POSIX 1003.1 – 1995. Các thủ tục con trong đó bao gồm các API Pthreads có thể được chính thức nhóm lại thành bốn nhóm chính: - Quản lý thread: các thủ tục làm việc trực tiếp với thread: tạo thread, tách, nối… Chúng cũng bao gồm các hàm để thiết lập hoặc truy vấn thuộc tính thread (như nối, lập lịch…). - Mutexes: các thủ tục xử lý việc đồng bộ hóa, được gọi là một “mutex”, viết tắt của “mutual exclusion”. Các hàm mutex cung cấp các hàm tạo, phá hủy, khóa và mở khóa mutexes. Các hàm này được bổ sung thêm các hàm thuộc tính mutex để thiết lập hoặc sửa đổi các thuộc tính liên kết với mutexes. - Biến điều kiện: các thủ tục để đánh địa chỉ liên kết giữa các thread để chia sẻ một mutex. - Đồng bộ hóa: các thủ tục quản lý đọc/ghi các khóa. - Quy ước đặt tên: tất cả các định danh trong thư viện đều được bắt đầu với pthread_. 2.3.2. Quản lý Thread Các thủ tục chính: - pthread_create (thread, attr, start_routine, arg): dùng để khởi tạo thread. - pthread_attr_itit (attr): Khởi tạo thuộc tính cho một thread - pthread_attr_destroy (attr): hủy thuộc tính của một thread. - pthread_exit (status); Dùng để ngắt một thread đang thực thi. 2.3.2.1. Tạo thread - pthread_create() Các tham số trong thủ tục pthread_create: 12 - Thread: một định danh duy nhất cho một thread mới và được trả về bởi thủ tục con. - Attr: một đối tượng thuộc tính có thể được sử dụng để thiết lập các thuộc tính cho thread. Bạn có thể xác định một đối tượng thuộc tính thread, hoặc để NULL với giá trị mặc định. - Start_routine: thủ tục C để thread sẽ thực thi một lần khi nó được tạo ra. - Arg: một tham số đơn để có thể được truyền cho start_routine. Nó phải được truyền bởi tham chiếu như là con trỏ kiểu void. - Mỗi một lần được tao ra, thread có thể tạo ra các thread khác. Không có hệ thống cập bậc hoặc phụ thuộc giữa các thread. 2.3.2.2. Thiết lập các thuộc tính cho Thread 2.3.2.3. Hủy thread Có một vài cách mà trong đó Pthread bị hủy: o Những thread mà trả về từ thủ tục bắt đầu của nó (thủ tục chính với thread ban đầu). o Những thread thực hiện lời gọi tới hàm pthread_exit. o Những thread bị hủy từ những thủ tục khác bằng hàm pthread_cancel. o Tiến trình cuối bị ngắt trong khi thực hiện lời gọi tới hàm khác hoặc thoát khỏi thủ tục con. Hàm pthread_exit được sử dụng để thoát khỏi một thread. 2.3.2.1. Truyền tham số cho Thread Thủ tục pthread_create() cho phép người lập trình có thể truyền một đối số cho thủ tục khởi tạo thread. Trong trường hợp có nhiều tham số cần truyền, sự giới hạn này rất dễ dàng được vượt qua bằng cách tạo ra 1 cấu trúc bao gồm tất cả các tham số, sau đó truyền 1 tham số con trỏ của struct này vào thủ tục pthread_create(). Tất cả các tham số đều phải được truyền bằng tham chiếu và kiểu (void *). Ví dụ 1: truyền 1 tham số: 13 //Hàm thực hiện nhiệm vụ trong thread. void* do_loop(void *data){ int i, j; int me = *((int*)data); for(i=0;i<10;i++){ // de nhin cho biet cac thong tin se duoc chay như thế nào Sleep(100); for(j=0;j<10;j++) ; printf("Me:%d value is %d\n ", me,i); } //pthread_exit(NULL); return 0; } int ExampleThread::One_Param_Thread(void) { printf("\nStarting thread One_Param_Thread"); pthread_t p_thread, p_thread1; int thr_id; int a = 1, b = 2; thr_id = pthread_create(&p_thread,NULL,do_loop,(void *)&a); do_loop((void*)&b); thr_id = pthread_create(&p_thread1,NULL,hello,(void *)&a); printf("\nEnd thread Ex2"); return true; } Ví dụ 2: Truyền nhiều tham số sử dụng struct. 14 ////------------------------structure---------------------//// typedef struct data_message{ int thread_no; char message[100]; } thr_data; void * print_thr (void *data){ thr_data *ptr; ptr = (thr_data *)data; //Sleep(500); printf("Thread %d say.......%s\n",ptr->thread_no,ptr->message); pthread_exit(0); return 0; } //Truyen du lieu cau truc du lieu vao thread. int ExampleThread::Multi_Param_Thread(void) { pthread_t p_thread1, p_thread2; thr_data data1, data2; data1.thread_no = 1; strcpy_s(data1.message,100,"hello...."); data2.thread_no = 2; strcpy_s(data2.message,100,"world...."); int thr_id1, thr_id2; thr_id1 = pthread_create(&p_thread1,NULL, print_thr,(void *)&data1); thr_id2 = pthread_create(&p_thread2,NULL, print_thr,(void *)&data2); printf("Multi_Param_Thread................................\n"); return true; 15 } 2.3.3. Nối và tách Thread 2.3.3.1. Những thủ tục chính - Pthread_join (threadid,status): dùng để nối các thread lại - Pthread_detach(threadid,status): dùng để phân tách các thread - Pthread_attr_setdetachstate(attr,detachstate): dùng để thiết lập thuộc tính tách thread - Pthread_attr_getdetachstate(attr,detachstate): dùng để lấy trạng thái thuộc tính tách thread 2.3.3.2. Nối thread – pthread_join() Nối là một cách để thực hiện việc đồng bộ hóa giữa các thread Thủ tục pthread_detach() có thể được sử dụng để tách một thread thậm chí thread đó được tạo ra với thuộc tính là có thể nối được. Không có thủ tục ngược lại. 2.3.4. Dữ liệu riêng của Thread 2.3.4.1. Khái niệm dữ liệu riêng của thread Trong cơ chế dữ liệu thread cụ thể, chúng ta có khái niệm về các khóa và giá trị. Mỗi khóa có một tên, và trỏ tới một vài vùng nhớ. Những khóa với cùng tên trong hai thread đồng thời luôn luôn trỏ tới những vùng nhớ khác nhau, điều này được quản lý bởi thư viện các hàm để bố trí các khối bộ nhớ để truy cập thông qua các khóa này. 2.3.4.2. Cấp phát dữ liệu riêng của thread Hàm pthread_key_create() được dùng để cấp phát một khóa mới. Khóa này bây giờ sẽ trở nên có giá trị cho tất cả các thread trong tiến trình. Khi một khóa được tạo ra, giá trị mặc định là NULL. Sau đó trong mỗi thread có thể thay đổi giá trị như nó mong muốn. 16 2.3.4.3. Truy cập vào dữ liệu riêng của thread 2.3.4.4. Xóa dữ liệu trong thread Hàm pthread_key_delete() có thể được dùng để xóa khóa, sử dụng hàm này như sau: Int rc = pthread_key_delete(key); Hàm này sẽ trả về 0 nếu thành công, hoặc EINVAL nếu có lỗi. 2.4. Đồng bộ hóa các tác vụ trong POSIX THREAD Để việc đồng bộ hóa các tác vụ, tránh vấn đề tranh chấp tài nguyên, có thể sử dụng sử dụng các tính năng của Posix Thread như: - Mutex (mutual exclusion): loại trừ lẫn nhau - Biến điều kiện (Condictional variable). - Semephores: báo hiệu. 2.4.1. Mutex 2.4.1.1. Khái niệm mutex. Biến mutex là một trong những phương tiện chính để thực hiện việc đồng bộ thread và cho việc bảo vệ việc chia sẻ dữ liệu khi xảy ra nhiều lời gọi. 2.4.1.2. Tạo ra và phá hủy mutex 2.4.1.2.1. Những thủ tục - Pthread_mutex_init(mutex, attr) - Pthread_mutex_destroy(mutex) - Pthead_mutexattr_init (attr) - Pthread_mutexattr_destroy(attr) 2.4.1.2.2. Cách sử dụng Biến mutex phải được khia bảo với kiểu pthread_mutex_t và phải được khởi tạo trước khi nó được sử dụng. 17 Đối tương attr được sử dụng để thiết lập thuộc tính cho đối tượng mutex và phải là kiểu pthead_mutexattr_t nếu được sử dụng. Các thủ tục pthead_mutexattr_init() và pthread_mutexattr_destroy() được dùng để tạo ra và phá hủy đối tượng thuộc tính mutex tương ứng. Pthead_mutexattr_destroy() nên được dùng để giải phóng đối tượng mutex khi nó không còn cần thiết. 2.4.1.3. Khóa và mở khóa mutex 2.4.1.3.1. Các thủ tục - Pthread_mutex_lock(mutex) - Pthead_mutex_trylock(mutex) - Pthead_mutex_unlock(mutex) 2.4.1.3.2. Cách sử dụng Thủ tục pthread_mutex_lock() được sử dụng bởi một thread để thu được một khóa trên một biến mutex xác định. Nếu biến mutex đã được khóa bởi một thread khác, lời gọi này sẽ chặn lời gọi thread cho tới khi mutex được mở khóa. Thủ tục pthread_mutex_trylock() sẽ cố thử khóa một mutex. 2.4.2. Biến điều kiện 2.4.2.1. Khái niệm về biến điều kiện Biến điều kiện cung cấp một cách nữa cho thread để đồng bộ hóa. Trong khi mutexes thể hiện sự đồng bộ bằng cách điều khiển thread truy cập tới dữ liệu thì biến điều kiện cho phép thread đồng bộ dựa trên giá trị thực của dữ liệu. 2.4.2.2. Tạo ra và phá hủy 1 biến điều kiện 2.4.2.2.1. Các thủ tục - Pthread_cond_init (condition, attr) - Pthread_cond_destroy(condition) - Pthead_condattr_init(attr) - Pthread_condattr_destroy(attr) 18 2.4.2.2.2. Cách sử dụng Biến điều kiện phải được khai báo với kiểu pthread_cond_t, và phải được khởi tạo trước khi chúng được sử dụng. Có hai cách để khởi tạo biến điều kiện: - Theo cách tĩnh: khi chúng được khai báo: pthread_cond_t myconvar = PTHREAD_COND_INITIALIZER. - Theo cách động: với thủ tục pthread_cond_init. ID của biến điều kiện được tao ra được trả về với lời gọi thread thông qua tham số condition. Phương thức này cho phép thiết lập thuộc tính cho biến điều kiện, attr. 2.4.2.3. Waiting và signaling trên biến điều kiện. 2.4.2.3.1. Các thủ tục - Pthread_cond_wait (condition, mutex) - Pthread_cond_signal (condition) - Pthread_cond_broadcast (condition) 2.4.2.3.2. Cách sử dụng Thủ tục pthread_cond_wait() ngăn lời gọi thread cho tới khi điểu kiện xác định được báo hiệu. Thủ tục này nên được gọi trong khi mutex bị khóa và nó sẽ tự động mở khóa mutex trong khi chờ đợi. 2.4.3. semaphore 2.4.3.1. Những thủ tục chính - sem_init (sem_t *sem, int pshared, unsigned int value). - sem_wait (sem_t * sem). - sem_post (sem_t * sem). - sem_destroy (sem_t * sem). 2.4.3.2. Cách sử dụng - Thủ tục sem_init (): dùng để khởi tạo biến semaphore, trong đó: sem_t *sem: tên biến của semaphore, Pshared: giá trị bằng 0; dùng cho biến chia sẻ giữa các threads, bằng 1 dùng chia sẻ giữa các processes. - sem_wait (sem_t * sem): hàm cung cấp một tín hiệu khóa của semaphore. 19 - sem_post (sem_t * sem): hàm cung cấp một tính hiệu mở của semaphore - sem_destroy(sem_t * sem): hàm dùng để hủy giá trị semaphonre Chương 3 – ỨNG DỤNG TÍNH TOÁN SONG SONG VÀO BÀI TOÁN TÍNH CƯỚC DATA 3G VINAPHONE 3.1. Hiện trạng hệ thống 3.1.1. Cơ sở hạ tầng - Hệ điều hành: Window 2008 64bit - Bộ vi xử lý: Intel Xeon CPU x7542 24-core 2.7 GHz - Bộ nhớ RAM: 64GB DDR 3 - Ổ cứng: 2.3TB - Database: Oracle 11g. 3.1.2. Hệ thống tính cước data 3g - Nguồn dữ liệu - Quy trình xử lý - Phần mềm xử lý - Khó khăn và hạn chế 3.2. Giải pháp đề xuất Kết hợp với việc tận dụng cấu hình thiết bị phần cứng sẵn có tại Trung tâm, Tôi đề xuất dùng công nghệ lập trình Microsoft Visual C++ 2008 64bit để tận dụng bộ nhớ Ram và áp dụng phương pháp xử lý xong xong để tận dụng số lượng CPU sẵn có của máy chủ. 20 3.2.1. Giải pháp tổng thể Tôi xin đề xuất Giải pháp Tính cước data 3g cho Trung tâm cước để đáp ứng những yêu cầu đề ra. Giải pháp được mô tả như sau: Hình 3.1. Mô hình giải pháp tổng thể Rating3g là phần mềm gồm đầy đủ, hoàn chỉnh cho người dùng đầu cuối, được phát triển để giải quyết các nghiệp vụ, tốc độ xử lý về tính cước data 3g cho các thuê bao trả sau, nó bao gồm các tính năng chính: - Rating3g: Khả năng tính cước cho các thuê bao trả sau. Module chức năng trên phải đáp ứng được các nền tảng các dịch vụ sau: - Quản lý hợp nhất các KPIs, Cảnh báo - Khả năng cấu hình động các tham số. - Phân tích dữ liệu: Được thực hiện nhằm tối ưu hóa các biểu đồ và báo cáo. - Quản trị - Giám sát và quản lý tại một điểm duy nhất tất cả các module và các quá trình. 21 3.2.2. Giải pháp chi tiết tính cước Hình 3.2. Mô hình giải pháp tính cước 3g Rating3g có kiến trúc dựa trên nhiều lớp chức năng. Điều này cho phép hệ thống được triển khai ở quy mô khác nhau, cho các dịch vụ khác nhau và các sản phẩm. Ngoài ra, hệ thống có đủ linh hoạt để phù hợp với phát triển sản phẩm mới và dịch vụ, tích hợp với sản phẩm của bên thứ 3. - Module chức năng tính cước data 3g cho thuê bao trả sau đóng vai trò tính toán dữ liệu cước chi tiết, khuyến mại cho khách hàng. - Module được xây dựng để thực hiện các chức năng chính sau: o Thu thập thông tin dữ liệu o Sắp xếp thông tin o Tính cước data 3g  Lọc bản ghi cước trùng, áp giá, khuyến mại theo từng gói cước dịch vụ.  Cho phép tính nhiều lần trong tháng. 22  Tính cước gói, cước thuê bao, cước sử dụng dịch vụ, cho phép xử lý đồng thời nhiều file cuộc gọi, nhiều loại tổng đài o Chia tách số liệu: Thực hiện tách số liệu chi tiết theo từng tỉnh thành. 3.3. Phân tích, thiết kế hệ thống tính cước 3.3.1. Phân tích 3.3.1.1. Chức năng thu thập dữ liệu Chức năng có nhiệm vụ thu thập dữ liệu các bản tin cước, phân loại bản tin cước trả trước trả sau, trả trước Đọc thông tin từ Oracle Xử lý phân loại bản ghi trả trước/trả sau Ghi ra file *.dat Bỏ qua Trả trước Trả sau 3.3.1.2. Chức năng sắp xếp dữ liệu Chức năng có nhiệm vụ sắp xếp theo thứ tự tăng dần thông tin các bản tin cước truy cập theo các tiêu chí. Làm đầu vào cho chức năng tính cước được đúng theo trật tự thời gian. Đọc file *.dat Sắp xếp thông tin Ghi ra file *.dbf 3.3.1.3. Chức năng tính cước chi tiết Chức năng có nhiệm vụ áp giá cước chi tiết, tính khuyến mại, tính hạn mức thanh toán tối đa. 23 Đọc file *.dbf Đọc dữ liệu Oracle Tính cước chi tiết Ghi ra file kết quả Ghi ra file lỗi Bản ghi không hơp lệ Bả n g h i h ơ p lệ 3.3.1.4. Chức năng tách cước theo từng tỉnh Chức năng có nhiệm vụ tách các bản ghi cước chi tiết từ file chung ra các file theo từng tỉnh phục vụ hệ thống tổng hợp cước. Đọc file *.dbf Đọc dữ liệu Oracle Tách cước theo từng tỉnh Ghi ra file *.dbf - Dữ liệu đầu vào: o Danh sách file định dạng *.bdf, chứa thông tin các tỉnh theo ngày; o Danh sách thuê bao chuyển tỉnh, danh sách thuê bao nghiệp vụ - Xử lý tách tỉnh:Phân chia dữ liệu ra file theo từng tỉnh - Dữ liệu đầu ra: o File *.bdf; đã được chia tách theo từng tỉnh (HNI, HCM, …) o Lưu trữ: trên server tính cước 3.3.2. Thiết kế Ở mục này này nêu lên các nội dung về mô hình quan hệ và mô tả chi tiết các bảng dư liệu 24 3.3.2.1. Mô hình quan hệ cơ sở dữ liệu - Mô tả chi tiết bảng dữ liệu SERVICE_CODES, PRICES, PRICE_GROUPS, TIME_UNITS,PROMO_DISPATCHES,EXCEPTION_LISTS. 25 3.3.2.2. Mô hình chức năng CommonLib CDateTime m_DateTime CString DateToString(); CString TimeToString(); RECORD_INDEX_CDR3G *pBuff Int Index_Cdr_3g() RateIndex CFile fOut,fOutPre LOAITB *pLoaiTB int Get_CDR_Detail() RateCollect int m_nSize; bool m_fClearMem; TYPE * GetFirst() TYPE * GetNext() MemBlockLib Long RecordIndexLen Int Sort_Process() SortLib DBLib CFile m_cFile long m_nRecsInBuff int Create() int FindFieldPos() int getCurRecData() Char MATINH_NEW[5] int nFileList int Load_Price_Tariffs( ) int Rating_Data() Rating Int Rating3g() MainRating Char MATINH_NEW[5] int nFileList int Main_Split() Int ThrDetail() RateSplit - CommonLib: chứa các thông tin về hàm, lưu log, xóa file… - DbLib: chứa các thông tin về tạo tệp foxpro, xác định vị trí trường,… - MemblockLib: chứa các thông tin về cây tìm kiếm,…. - RateCollect:thu thập dữ liệu,...; Lớp RateIndex: chứa các thông tin về hàm sắp xếp dữ liệu ….; - Rating: chứa các thông tin về hàm tính cước, khuyến mại,Lớp RateSplit: chứa các thông tin về hàm phân tách dữ liệu,…. - SortLib: chứa các thông tin về thư viện sắp xếp dữ liệu,…. 3.4. Cài đặt và thử nghiệm Ở mục này này nêu lên các nội dung - Cấu hình tại máy tính cước - Một số kết quả, và hình ảnh thử nghiệm hệ thống. 26 3.5. ĐÁNH GIÁ, SO SÁNH SỰ CẢI TIẾN SO VỚI TÍNH TOÁN TUẦN TỰ 3.5.1. So sánh 3.5.1.1. Thời gian tính toán tuần tự và tính toán song song áp dụng chức năng tách cước Thông tin thời gian thực hiện tính toán (tính theo giờ) Số bản ghi (triệu) Tính toán tuần tự (foxpro) Tính toán tuần tự (c++) Tính toán song song (c++) 100 1.50 0.40 0.30 200 2.00 0.80 0.45 300 3.90 1.50 0.58 400 5.20 2.00 0.90 500 6.50 3.00 1.15 600 8.00 3.50 1.40 Theo kết quả trong bảng phân tích trên; khi số liệu bản ghi là 100 triệu thì tính toán tuần tự và tính toán song song dùng c++; cũng đã nhanh hơn rất nhiều tính toán tuần tự Foxpro và khi từ 200 triệu bản ghi trở đi thì tốc độ có sự khác biệt rất lớn. Với kết quả trong bảng phân tích khi số liệu bản ghi thử nghiệm là từ 200 triệu kết quả tính toán song song nhanh hơn rất nhiều so với tính toán tuần tự cùng dùng c++ 27 3.5.1.2. Biểu đồ hiện tính toán tuần tự và tính toán song song chức năng tách cước chi tiết Hình 3.3. Biểu đồ so sánh thời gian thực hiện 3.5.2. Đánh giá kết quả Với số lượng phần tử nhỏ < 200 triệu bản thì tính toán trên tuần tự và tính toán song song đều rất nhanh. Nhưng khi số lượng bản ghi mô phỏng tăng lên thì áp dụng tính toán song song nhanh hơn tuần tự rất nhiều lần. 28 KẾT LUẬN Trong khóa luận tốt nghiệp này, tôi đã tìm hiểu về thread, multithread và các lợi thế của thread và multithread so với tiến trình và đa tiến trình. Ngoài ra, tôi cũng đồng thời cài đặt thành công vào bài toàn tính cước data 3g cho Vinaphone để thấy được hiệu quả của việc sử dụng multithread. Biều đồ so sánh trong chương 4 đã chỉ rõ rằng, với lượng dữ liệu đầu càng lớn, thì hiệu năng tính toán của việc sử dụng thuật toán tuần tự càng lớn so với việc không sử dụng tín toán song song. Như vậy với đề tài “NGHIÊN CỨU TÍNH TOÁN SONG SONG VÀ ỨNG DỤNG VÀO HỆ THỐNG TÍNH CƯỚC DATA 3G” tôi mong muốn đem lại phần nào kiến thức để giúp mọi người có thể ứng dụng vào các bài toán tính toán với số liệu lớn. Để tôi có được những kết quả như ngày hôm nay cũng như hoàn thành nội dung luận văn tốt nghiệp Thạc sĩ khoa học này, trước hết phải kể đến công lao đào tạo của tất cả các Thầy, Cô giáo trong Học viện Công nghệ Bưu chính - Viễn thông, sự động viên giúp đỡ của tất cả người thân, bạn bè. Đặc biệt tôi xin được bày tỏ lòng kính trọng và biết ơn tới TS.Trịnh Anh Tuấn, người đã gợi ý cho tôi hướng nghiên cứu của luận văn, hỗ trợ giúp đỡ tôi những kiến thức khoa học bổ ích. Thầy đã đưa ra những nhận xét quý giá và trực tiếp hướng dẫn tôi trong quá trình thực hiện luận văn này. Tôi xin chân thành cám ơn các anh chí đồng nghiệp trong Công ty NEO nơi tôi đang công tác. Và đối tác Vinphone đã tạo điều kiện cho tôi tham gia và phát triển chương trình. Cuối cùng, tôi xin gửi lời cảm ơn tới gia đình và bạn bè của tôi, những người đã động viên, khuyến khích tôi rất nhiều trong cuộc sống cũng như trong quá trình công tác và học tập. Do thời gian có hạn nên chương trình không thể tránh được các thiếu sót các mặt còn hạn chế chẳng hạn như: - Thiếu các giao diện chức năng để cấu hình các tham số thiết lập bảng giá cước, thông tin quản lý tham số, thông tin các công văn khuyến mại. 29 - Chưa áp dụng tính toán song song vào chức năng tính cước, chức năng thu thập số liệu. Tôi mong muốn nhận được sự chỉ bảo, góp ý chân thành của các Thầy Cô giáo cùng các anh chị đồng nghiệp. Hà Nội, tháng 11/2013 Xin chân thành cảm ơn. Nhữ Thanh Thế 30 HƯỚNG PHÁT TRIỂN TIẾP THEO Do thời gian có hạn nên chương trình còn nhiều hạn chế, trong tương lai có thể phát triển và mở rộng theo các định hướng sau: - Hoàn thiện và triển khai cho các cán bộ vận hành tại Trung tâm tính cước Vinaphone. - Xây dựng các form thiết lập các tham số, báo cáo thống kê - Áp dụng tính toán song song vào chức năng thu thập số liệu - Triển khai áp dụng tính toán song song vào các hệ thống: o Đối soát dữ liệu: đối soát lưu lượng cước của Vinaphone với các đối tác Viettel, Mobifone, … o Tổng hợp cước: tổng hợp dữ liệu cước chi tiết và thông tin thuê bao để tạo dữ liệu hóa đơn. - Nghiên cứu tính toán lưới, đám mây (sử dụng MPI hoặc PVM) - Nghiên cứu tính toán dữ liệu lớn dùng giải pháp Bigdata, MapReduce - Nghiên cứu tính toán song song trên GPU.