Tài liệu Xử lý song song trên PVM và ứng dụng trong bài toán bảo mật thông tin

DAI HỌC QUOC GIA H À NỘI K H O A ( ÔNC, N G H Ệ NGUYỄN VIỆT ANH XỬ LÝ SONG SONG TRÊN PVM VÀ ỨNG DỰNG TRONG BÀI TOÁN BẢO MẬT THÔNG TIN C HUYÊN NGÀNH: C Ô N G N G H E T H Ô N G T IN MÃ S ố : 1.01.10 LUẬN VĂN THẠC ■ • s! N G Ư Ờ I H Ư Ớ N G DẪN KHOA HỌC: TSKH. PHẠM TRẰN NHU V -L O / Z Z 1 HÀ NỘI -2003 M Ụ C LỤC DANH MỤC CÁC TỪ VIẾT TẮT. D A N H M Ụ C B Ả N G B IỂ U HÌNH V Ẽ .................................................................................................................... 4 M ớ Đ Â U ............. .......................................................................................................................... ............................................................ 5 C hư ơn g 1 T ổn g quan về 7 x ử lý s o n g s o n g ........................... 1 . 1 M á y t í n h s o n g s o n g ................... ................. ..................................................................................... 1.2 P h â n l o ạ i m á y t í n h s o n g s o n g ...................................... 1 .................................................................................. £ 1.2.1 P h â n l o ạ i d ự a t r ê n c ơ c h ế đ i ề u k h i ể n c l m n g ................................................................................................8 a ) H ộ t h ố n g đ a x ử lý m ộ t d ò n g l ệ n h n h i ề u d ò n g d ữ 8 b) H ệ t h ố n g đ a x ử lý n h i ề u d ò n g l ệ n h n h i ề u d ò n g d ữ l i ệ u ..................9 1.2.2 C á c h p h â n l o ạ i d ự a t r ê n s ự t ư ơ n g t á c g i ữ a c á c B X L . ....................................................... 9 a) C h i a s è b ộ n h ớ c h u n g ................................................ ......................................................................... JQ ..................................................................................J J b ) T r u y ề n t h ô n g đ i ệ p ..... ................................................. 1. 3 M ô h ì n h l ậ p t r ì n h s o n g s o n g ..................................... ...........................................................................................I I 1.3.1 M ô h ì n h n h i ệ m v ụ - k c n l i l i ê n l ạ c ............................. 12 ..................................................................................................... ! í a) T ố c đ ộ ..................... ............................... ' b ) T í n h đ ộ c l ậ p á n h x ạ ............................................... I c) T í n h m o d u l e . d ) T í n h x á c đ ị n h .......................................... 14 1 . 3 . 2 M ô h ì n h c h i a SC b ộ n h ớ c h u n g ......................................... ............................................................................. 1.4 H i ệ u n ă n g c ù a x ử lý s o n g s o n g .........7............................ 14 ............................................................................. <5 .......................................................................... ^ 1.4.1 D ị n h l u ậ t A m d a h l ' s ........... .................................... I 1.4.2 C â n b à n g t à i ..................................................... a ) C á c t h u ậ t t o á n c â n b ằ n g tài t ậ p t r u n g ................................... ](•’ b) C á c t h u ậ t t o á n c â n b à n g tài p h â n t á n h o à n l o à n .............................. 16 . c) C á c t h u ậ t t o á n c â n b à n g tài p h â n t á n m ộ t n ử a ........................ 17 d ) S ự b ế t ắ c ( D e a d l o c k ) ............................................... ...... ....................................................................................... I ý C h ư ơ n g 2 S o n g s o n g h o á t hu ật t oá n t ự ................................ . . ]<) 2.1 C á c c h i ê n l ư ợ c p h á t t r i ê n ứ n g d ụ n g s o n g s o n g ............ Ịọ 2. 1. 1 S o n g s o n g h o á t ự đ ộ n g ............ ....................... ................. ............................................................................... ỊỌ 2 . 1 . 2 X â y d ự n g c á c t h ư v i ệ n s o n g s o n g ............................... Ịọ 2 . 1.3 K ế t h ừ a c á c t h à n h p h ầ n c h í n h .................................... 2. 2 C á c b ư ớ c c ơ b à n s o n g s o n g h o á tl ni ật t o á n t u ầ n t ự 2. 2. 1 P h â n r ã ................................................. 20 21 a) K ỹ t h u ậ t p h â n r ã t h e o m i ề n ................................... 21 b ) K ỹ t h u ậ t p h â n rã c h ứ c n ă n g ........................................... 22 c) T i ê u c h u â n đánli giá giai đ o ạ n p h â n 2 . 2 . 2 T r u y ề n t h ô n g ....... .. .............................. r ã .......................... 23 ......................................................................................................... 2 1 a ) T r u y ề n t h ô n g c ụ c b ộ ......................................................... ........................................................................2 <5 ......................................................................... 2C b ) T r u y ề n t h ô n g t o à n c ụ c ............................................. c ) 1 r u y ề n t h ô n g đ ộ n g và k h ô n g c ó c ấ u t r ú c ................................... 27 d ) T r u y ề n t h ô n g k h ô n g d ồ n g b ọ ................................................. 27 e) T i ê u c h u ẩ n đ á n h gia thiết kế t r u y ề n t h ô n g ló 2 . 2 . 3 T ồ n g h ợ p ................................................................. 29 a ) T ă n g k í c h t h ư ớ c n h i ệ m v ụ ....................................... 3Q b ) B à o đ ả m t í n h m ề m d e o .................................... 21 c ) G i ả m c h i p h í x â y d ự n g p h ầ n m ề m .................................... ' d ) T i ê u c h u ẩ n đ á n h g i á g i a i đ o a n t ổ n g h ợ p .............. 2.2.4 Ánh xạ.............................. >s r * ' 1-i I . .1 ........ 2.3 Các chicn lược thict ké ......................................... 2.3.1 S o n g s o n g h o á k ế í q u á .................................................. . 2 . 3 . 2 S o n g s o n g h o n d ạ i d i ệ n ........................................................ .... ' .......... 31 ỳ) ..... .......................... ....... ......... „ ............................................................................. Y I .................................................................. 3 g 7 2.3.3 S o n g s o n g h o á c h u y ê n b i ệ t ........................................................................................... 39 2 . 3 . 4 P h â n l ớ p c á c b à i t o á n á p d ụ n g c h i ế n l ư ợ c t h i ế t k ế ..................................................................................41 a) S o s á n h b a c h i ế n l ư ợ c t h i ế t k ể ....................................................................................... 41 b ) P h â n l ớ p c á c b à i t o á n ........................................................................................................ 41 2.4 Môi t r ư ờ n g l ậ p t r i n h s o n g s o n g .............................................................................................. 43 2. 4. 1 M ộ t s ố m ô i t r ư ờ n g l ậ p t r ì n h p h ổ b i ế n ............................................................................................................ 4 3 a) M P I ( M e s s a g e P a s s i n g I n t e r f a c e ) ................................................................................................. b) 43 P V M ( P a r a l l e l V i r t u a l M a c h i n e ) .......................................................................................................... 44 c) S o s á n h g i ữ a M P I và P V M ................................................................................................................................ 4 4 2 . 4 . 2 M á y à o sone, s o n g ( P V M ) ........................................................................................................ 45 a) K h á i q u á t c h u n g ..................................................................................................... 45 b ) M ộ t s ố d ặ c đ i ể m c ù a P V M .................................................................................................... 46 c ) M ộ t s ố t h à n h p h ầ n c ù a P V M .......................................................................................... 46 d) N g u y ê n l ý h o ạ t đ ộ n g .............................................................................................................................................. 4 g e ) M ộ t s ố m ô h ì n h á p d ụ n g t r o n g c á c ứ n g d ụ n g t r ê n P V M ......................................................................5 0 C h ư o ì i g 3 B à i t o á n b ả o m ậ t t h ô n g ( i n ............................................................................. SI 3.1 B à i t o á n m ã h o á t r o n g b à o m ậ t t h ô n g t i n ............................................................................................................... 51 3. 1. 1 B à i t o á n .................................................................................................................................... 51 3 . 1 . 2 M ộ t s ố h ệ m ã p h ổ b i ế n ............................................................................................................. 52 a) H ệ m ã c h u ẩ n D E S ( D a t a E n c r y p t i o n S t a n d a r d ) ...................................................................................... 5 2 b ) H ệ m ã c ô n g k h a i .................................................................................................................. 52 3 . 2 T h u ậ t t o á n m ã h o á c ô n g k h a i R S A ...................................................................... 53 3. 2. 1 T h u ậ t t o á n ....................................................................................................... 53 3 . 2 . 2 Q u y t r ì n h m ã h o á v à gi ả i m ã v ớ i h ệ m ã R S A .............................................................................................53 a)T ạokho b) á .............................................................................................................. 53 M ã h o á t ệ p t i n ................................................................................................... 54 c ) G i ã i m ã t ệ p t i n ............................................................................................... 54 3 . 2 . 3 S o n g s o n g h o á t h u ậ t t o á n t ì m s ố n g u y ê n t ố ................................................................................................. 55 3. 3 T h ử n g h i ệ m ................................................................................................................. 55 3 . 3 . 1 C à i đ ã t t h u ậ t t o á n t ì m s ổ t h e o h a c h i ế n l ư ợ c t h i ế t k ế ............................................................................. 5 5 a ) S o n g s o n g h o á k ế t q u à .............................................................................................................................................. 5 5 b) S o n g s o n g l i oá dại d i ệ n ....................................................................................................... c) S o n g s o n g h o n c h u y ê n b i ệ t .......................................................................................................................... 3 . 3 . 2 T h ử n g h i ệ m , đ á n h g i á k ế t q u ả ....................................................................................................................... 56 57 58 a) T h ử n g h i ệ m ..................................... ............................................................................................... 58 b ) K ế t q u à ( h ử n g h i ệ m ...................................................................................................................... 58 c) Đ á n h g i á , n h ậ n x c t ............................................................................................................... 3 . 3 . 3 C h ư ơ n g t r ì n h m ã h o á v ă n b à n v ớ i k l i o á R S A ...................... 59 59 K É T L U Ậ N ........... ............................................. ...................................... . T Ả I I.ĨỆŨ TI IA M P H Ụ L Ụ C ......................... . . ^ . . . . . . . . . . . . . . Z Z Z Z Z Z Z Z [ " Z Z Z Z Z [ Z ' " Z Z Z Z Z Z Z Z Z m 6! DANH MỤ C CÁC T Ừ VIÉT TẮT Viêt tăt BX L PVM TID RSA MPI SIMD M IM D T iê ng Viêt Bộ x ử lý Máy ảo song song Định danh nhiệm vụ Ticng Anh Processor Parallel Virtual Machine Task Identifier Rivert Shamir Adle man Message Passing Interface Single Intruction Multiple Data Multi Intruction Multiple Data 4 DANH MỤC BẢNG BIÉƯ HÌNH VẼ B à n g 1 M ố i q u a n h ệ g i ữ a ti ến t r ì n h v à n h i ệ m v ụ ...........................................................................................................41 B á n g 2 C ấ u t r ú c c l u r ơ n g t r i n h ..................................................................................................................................................... 41 B à n g 3 So sánh m ộ t số tính n ă n g giữ a P V M v à MPI ......................................................................................................4 5 H ì n h 1-1 H ệ t h ố n g m ộ t d ò n g l ệ n h n h i ề u d ò n g d ữ l i ệu ( S I M D ) ..................................................................................9 H ỉ n h 1-2 H ệ t h ố n g n h i ề u d ò n g l ệ n h n h i ề u d ò n g d ữ l i ệu ( M I M D ) ...........................................................................9 H ì n h 1-3 M á y t í n h s o n g s o n g c h i a s ẻ b ộ n h ớ c h u n g ..................................................................................................10 H ì n h 1-4 M á y t í n h s o n g s o n g c ó b ộ n h ớ p h â n t á n ...................................................................................................... 11 H ì n h 1-5 S ự p h ụ t h u ộ c t h ờ i g i a n v à o s ố l ư ợ n g B X L c ù a đ ị n h l u ậ t A m d a h l ................................................. 15 H ì n h 1- 6 B X L P|( k ế t k h ố i đ ể g ử i X c h o Pj vì v ù n g đ ệ m c ủ a Pj đ ầ y ..................................................................18 H ì n h 2-1 S o n g s o n g h o á t ự đ ộ n g ................................................................................................................................................. 19 I í ì n h 2 - 2 X â y d ự n g c á c t l nr v i ệ n s o n g s o n g .........................................................................................................................2 0 H ì n h 2 - 3 S ử d ụ n g lại c á c t h à n h p h ầ n c h í n h .........................................................................................................................2 0 H ì n h 2 - 4 M ỗ i n h i ệ m v ụ đ ả m n h ậ n c ô n g v i ệ c tại đ i ể m l ư ớ i v à t r u y ề n t h ô n g v ớ i 4 lân c ậ n c ù a n ó .. 2 6 H ì n h 2- 5 M ỗ i t i ế n t r ì n h x ử lý m ộ t p h ầ n v i ệ c c ù a k ế t q u à ............................................................................................37 H ì n h 2 - 6 C á c t i ế n t r ì n h t h ự c h i ệ n s o n g s o n g t ừ n g c ô n g v i ệ c t h à n h p h ầ n ........................................................... 3 8 H ì n h 2 - 7 C ấ u t r ú c c ủ a T I D .............................................................................................................................................................4 7 H i n h 3-1 S ơ đ ồ k h ố i t h u ậ t t o á n t ạ o k h o á h ệ R S A ..................................................................................................... 54 H ì n h 3-2 M ỗ i tiến trình “ đ à m đ ư ơ n g ” m ộ t n h i ệ m v ụ ....................................................................................................5 6 ] l ì n h 3- 3 N h i ề u t i ế n t r ì n h đ à m n h ậ n n h i ề u n h i ệ m v ụ ............................................................................................... 5 6 H ì n h 3- 4 M ố i t i ế n t r ì n h d á m n h ậ n c h u y ê n b i ệ t k i ể m t r a m ộ t s ố n g u y ê n t ố ..................................................... 57 H ì n h 3- 5 K ế t q u à tliir n g h i ệ m c h i ế n l ư ợ c v ớ i s ố l ư ợ n g c á c B X L k h á c n h a u ................................................. 5 9 H ì n h 3 - 6 G i a o d i ệ n c h í n h c ù a c h ư ơ n g t r ì n h ......................................................................................................................... 6 7 H ì n h 3 - 7 T ạ o k h o á v ớ i 11= 1 2 3 4 ................................................................................................................................................ 6 7 H ì n h 3 - 8 T ệ p till d ù n g đ ể m ã h o á ...............................................................................................................................................6 9 H ì n h 3 - 9 T ệ p till đ ã đ ư ợ c m ã h o á v ớ i c ặ p k h o á ( e , n ) .....................................................................................................6 0 5 M Ở ĐÀU Sự phát triển khoa học kỹ thuật thường dược thách thức bởi lớp bài toán lớn cần phải giải quyết trong mọi lĩnh vực của đời sổng xã hội như dự báo thời tiết, khai phá dữ liệu, xử lý ảnh, trí tuệ nhân tạo. an toàn dữ liệu, tự động hoá V. . V. Lớp các bài toán này vừa đòi hỏi đáp ứng thời gian thực vừa yêu cầu xử lý trên khối lượng dữ liệu không lô. Việc giải quyết lớp các bài toán này thườ ng đòi hỏi phải sử dụng các bộ xử lý có hiệu năng cao. Máy tính song song ra đời để đáp ứng đòi hỏi đó và x ử lý song song ra đời dựa trên các máy tính loại này. Theo [14], [17] xử lý song song là thao tác xử lý thông tin đồng thời trên các phần tử dữ liệu thuộc một hay nhiều tiến trình để giải quyết một vấn đề nào đó. Máy tính song song đơn giản là một tập hợp các B X L (thường là cùng kiểu) cỏ mối liên hệ với nhau theo một cách thức nhất định có khả năng xử lý song song. Xử lý song song phát triển với mục đích làm tăng khà năng tính toán của máy tính băng cách kết hợp nhiều bộ xử lý tham gia vào quá trình tính toán thay vì sử dụng các máy tính chuyên dụng đắt tiền. Các xu hướn g VC ứng dụng, kiến trúc máy tính và m ạ n g cho thấy rằng trong tương lai cơ chế song song sẽ được sir dụng không chỉ trong các sicii máy tính mà ngay ca trong các trạm làm việc, máy tính cá nhân và mạ ng máy tính. Khi đó các chương trình phải tận dụng được không những các B X L trcn cùng một máy tính mà còn cả các BXL khác có thể sử dụng được trcn mạng. D o phần lớn các giải thuật hiện nay là các giải thuật tuần tự nên cần có những giải thuật và cấu trúc dữ liệu mới cho phép nhiều thao tác dược thực hiện đồng thời. Bởi vậy khả năng chạy dồng thời đang trờ thành một trong những đòi hỏi cơ bản của các phần mềm. Xử lý song song ngày càng thể hiện rõ sức mạnh của mình trong việc giải quyết nhiều lớp bài toán và trong các ứng dụng cụ thể. Các bài toán về an toàn dữ liệu cũng là một trong các ứng dụng đó. Nhir chung ía bict an toàn và bào mật dữ liệu đã được quan tâm từ rốt sớm Gần (tây với sự phát triển cùa mạng toàn cầu Internet, ván (lồ an toàn và bảo mật (lữ liệu được đặt ra càng cấp bách hơn và nhu cầu ứng dụng xử lý song song trong lĩnh 6 vực này do cũng vậy cũng tăng lên. Trong khuôn khổ luận văn “Xử lý song song trên P V M và ứng dụng trong bài toán bảo mật thông tin” chúng tôi nghiên cứu, áp dụng xử lý song song làm tăng hiệu quà thuật toán mã hoá công khai RSA - một trong thuật toán mà hoá phổ biến. Luận văn dược trình bày trong ba chương: Ch ươn g 1: Tổng quan về xử lý song song: trình bày tồng quan các khái niệm, các mô hình má y tính, mô hình lập trình, vấn đề hiệu năng của xử lý song song. Các vân đề được trình bày trong chương này là nền tảng cho các nghiên cứu của chúng tôi trong suốt quá trình thực hiện đề tài. Chương 2: Song song hoá thuật toán tuần tự: trình bày các bước cơ bản dể song song hoá thuật toán tuần tự, từ những các bước cơ bản này tập trung nghicn cứu một số bước quan trọng, nghicn cứu một số chiến lược thiết kế song song phổ biến cùng với môi trường lập trinh song song Parallel Virtual Machine (PVM) để tiến hành thử nghiệm bài toán. Thông qua thử nghiệm, cũng nh ư một số nghicn cứu của các nhà khoa học khác, chúng tôi mạnh dạn đề xuất sự phân lớp các bài toán dựa trcn tập dữ liệu kết quà dể sử dụng chiến lược thiết kể phù hợp. C hư ơng 3: Bài toán hảo mật thông tin: Chún g tôi đề cập đến bài toán bảo mật thông tin và tập trung vào bài toán mã lioá công khai RSA. Trong bài toán mã hoá RSA chúng chúng tôi áp dụng xử lý song song giải thuật tìm số nguyên tố - là một bước quan trọng trong giải thuật RSA. Chúng tôi tiến hành thử nghiệm cài đặt áp dụng các chiến lược thiết kế đã trình bày trong chương 2. Từ kết quả thừ nghiệm, tiến hành so sánh và chọn một giải pháp song song hoá tói ưu nhất để xây dựng chương trình mã hoá tệp văn bản. Phân kết luận, tóm tắt các vấn đề dã trinh bày trong các chương cũng như kết quả đạt được. Ngoài ra phần két luận cũng chỉ ra một số vấn đề chưa được giải quyêt thâu đáo trong quá trình thực hiện đc tài và hướng nghiên cứu trong tương lai của chúng tôi. 7 Chương 1 Tổng quan về xử lý song song 1.1 Máy tính song song Tốc độ của chiếc máy tính nhanh nhất dã tăng theo hàm mũ kể từ năm 1945 cho đen nay với tỷ lệ (rung bình là 10 lần trong 5 năm. Sự tăng trưởng này SC vẫn tiếp diễn, do đã có sự thay đổi quan trọng trong kiến trúc máy tính là sự thay đổi từ kiến trúc tuần tự sang kiến trúc song song nhàm duy trì được tốc độ tăng này. Tốc độ của máy tính phụ thuộc vào thời gian cần thiết để thực hiện một thao tác cơ bản và số iượng các thao tác cơ bản có thể được thực hiện đồng thời. Rõ ràng là thời gian thực hiện một thao tác cơ bản sẽ bị giới hạn bởi chu kỳ đồng hồ của BXL, nghĩa là thời gian để thực hiện thao tác nguycn tổ nhất. Tuy nhiên thời gian cùa một chu ki đồng hồ đang giảm đi rất chậm và dườn g như sắp tiếp cận tới giới hạn vật lý. Do vậy không thể dựa trên nhữ ng B X L nhanh hơn để làm tăng tốc độ tính toán. N ha m vượt qua những giới hạn này các nhà thiết kế đã sử dụng khả năng tính toán song song trong một con chip, chẳng hạn tiến hành tính toán đồng thời trên cả 64 bit trong thao tác nhân hai số. Tuy nhiên một kết quả trong lý thuyết về dộ phức tạp VLSI (Very Large Scale Inlergration) [14],[24] cho thấy ràng chiến lược này đòi hỏi chi phí rất cao. Kct quả này được phát hiểu như sau: Với các tính toán truyền dẫn (là các lính toán trong dó bất kì đầu ra nào cũng phụ thuộc vào tất cả đầu vào) thì thời gian T dể một chip có diện tích A giải quyết một bài toán phải thoả mãn điều kiện [AxT2J > f(N) (Í'(N) là một hàm phụ thuộc vào kích thước vấn đề, và N là kích thước của vấn dề). T ừ kết quả trên có thổ thấy việc xây dựng các thành phàn (Component) ricng rẽ chạy nhanh hơn khônẹ những là nít khó khăn mà việc thực hiện diều (ló cũng không kinh tế. Thay vào đó việc sử dụng dồng thời nhiều thành p h ầ n có tốc độ chậm hơn có the SC rẻ hơn. N h ữ n g nhà thiết kế máy tính cỏ thổ sử dụng nhiều kỹ thuật khác nhau để vượt qua giới hạn này và làm tàng tốc độ một máy tính đơn như cơ chế pipeline, hay sir dụng nhiều đơn vị tỉnh toán (Multi function units). Một xu hư ớn g nữa là các nhà thiết kế sử dụng nhiều máy lính mà mỗi máy trong số chúng có BXL, bộ nhớ ricng 8 rẽ và được kêt nôi theo một logic nào đó. Cách tiếp cận này ngày càng trở ncn dễ thực hiện hơn hời các kỹ thuật VLSI cho phép làm giảm số lượng thành phần cần thiết cho một máy tính. Do giá cùa một máy tính tỷ lệ với sổ thành phần mà nó có ncn khả năng tích hợp cho phép tăng số lượng B X L có trên một máy tính với cùng giá như cu. Kêt quà là số lượng BX L trên một máy tính ngày càng tăng lên. Sô lượng B X L trên một máy tính đang tiếp tục tăng và hiện tại trong một số môi trường tỷ lệ tăng đang là hai lần trong một hoặc hai năm. Do đó các ứng dụng có thể được sử dụng trên các máy tính có số lượng BX L ngày càng tăng trong vòng đời cua chúng. Bởi vậy khả năng m ở rộng (scalability) (khả năng phần mề m tận dụng được nhiều nhất các B X L có thể sử dụng) trờ thành một thuộc tính quan trọng cho phép chuyển đổi và bảo vệ chi phí đầu tư cho ứng dụng. 1.2 Phân loại máy tính song song Theo Flynn [14] phân loại kiến trúc máy tính dựa vào hai khái niệm dòng lệnh (instruction stream) và dòng dữ liệu (data stream). Một dòng lệnh là một chuỗi các lệnh được thực hiện hởi một máy tính. Một dòng dữ liệu là chuỗi dữ liệu được xử lý bời một dòng lệnh. Dựa trcn hai ticu chí này, máy tính được phân loại dựa trên cơ chê điều khiển chung. Ngoài ra một số cách phân loại máy tính khác dựa trcn sự tương tác giữa các BXL, kiêu và sô lượng các BX L và việc thực hiện xử lý là đồng bộ hay không đồng bộ [4], 1.2.1 Phân loại (lựa trên cơ chế diều khiển chung Phân lớn các máy tính song song thường có một cơ chế điều khiển chung song vân đề đặt ra ở dây là các hoạt dộng của máy lính dược điều khiển ở mức độ nào. Xc m việc điêu khiên theo hai khái cạnh khác nhau, một khía cạnh, cơ chế điều khiển chung chỉ được sử dụng để nạp chương trình và dữ liệu vào các B X L còn sau đó các B X L hoạt động độc lập. Khía cạnh khác, cơ chế điều khiển được sử dụng để hướn g dẫn cho các BXL các công việc phái làm tại mỗi bước. Giữa hai khía cạnh này là những cơ chế điều khiển trung gian. Hai loại cơ chế điều khiển phổ biến nhất !à a) H ệ tliổng đa x ử lý một (lòng lệnh nhiều dòng (lữ liệu Các m áy tính véc-tơ thuộc vào loại này, Mỗi máy tính véc-tơ có thể thực hiện 9 một dòng lệnh, tuy nhiên nỏ có nhiều BXL số học khác nhau mà mỗi B XL này có khả năng nạp và xử lý dữ liệu ricng của nó. Bởi vậy trong hất kỳ thời điểm nào một thao tác luôn ờ cùng trạng thái thực thi trên nhiều đơn vị xử lý mà mỗi trong sổ chúng có the xử lý dữ liệu riêng rẽ. Một ví dụ là chiếc máy C M - 200 IIìiili 1-1 llộ (hống một dòng lệnh nhiều (lòng dữ liệu (SI1MD) b) Hệ tliông đa x ử lý nhiêu (lòng lệnh nhiều dòng dí7' liệu Phần lớn các máy tính da xử lý hiện nay đều thuộc vào loại này. Trong các máy tính loại này nhiêu dòng lệnh có thể dược thực hiện cùn g mội lúc và mỗi dòng lệnh có thê xử lý clữ liệu ricng biệt. Các máy tính M I M D ban đầu có rất ít tương lác giữa các C PU song hiện nay phần lớn các máy tính đều đượ c thiết kế cho phép tương tác giữa các C P U được thực hiện một cách hiệu quả. Có thể liệt kc một số máy tính M I M D như Symmetry, TC2000, nCƯBE2, Paragon XP/S và Connection Machine CM-5. Hình 1-2 Hộ thống nhiều (lòng lộnli nhiều dòng ch! liệu ( M I M D ) 1.2.2 Cách phân loại dựa trên sự tương tác giữa các BXL Một trong những khía cạnh quan trọng cun các máy tính song song là vơ ché trao đổi thông tin giữa các BXĨ., lĩai kiến trúc phổ biến là kiến trúc chia xẻ bộ nhớ (shared memory) và kiên true truyền thông điệp (message passing). 10 a) Chìa sẻ bộ nhỏ' chung Sử dụng một bộ nhớ chia sẻ toàn cục (global shared memory) mà tất cà các BXL đều có thể truy nhập đến. Một B X L có thể trao đổi với một B XL khác bằng cách ghi vào bộ nhớ toàn cục và BXL thứ hai sẽ đọc tại cùng vị trí đó trong bộ nhớ. Điêu này cho phép giải quyết vắn đề trao đổi thông tin giữa các BXL, tuy nhiên lại dẫn đến vấn đề về việc truy nhập dồng thời các vị trí khác nhau trong bộ nhớ bởi nhiêu BXL. Có 2 cách tiếp cận chù yếu để xử lý vấn đề truy nhập bộ nhớ là sử dụng hệ thống chuyển mạch (switching systems) hoặc các B X L truy nhập bộ nhớ thông qua bus hệ thống. Đối với các hộ thống truy nhập bộ nhớ thông qua bus chung, việc thiết ké tương dối đan giản, song nếu có nhiều BXL thì bus có thể trở thành nút cổ chai khi có nhiều B XL cùng truy nhập bộ nhở. Bởi vậy số lượng B X L trong các hệ thống nay thường tương dôi nhỏ và cao nhất là vào khoảng vài chục B X L Nhăm tránh các nut cổ chai khi truy nhập bộ nhớ, các nhà thiết kế sử dụng hộ thông chuyển mạch để cung cấp nhiều dường truy nhập vào bộ nhớ toàn cục. Trong những hộ thống này các BXL dược nối vào bộ nhở thông qua một hoặc nhiều lớp chuyên mạch. Mặc dù cung cáp băng thông lớn hơn các hệ thống sử dụng bus song khi có nhiều truy nhập đến bộ nhớ cùng sử dụng một chuyển mạch thì tốc độ truy nhập cũng sẽ giám đi rắt nhiều. Một khó khăn nữa của việc sử dụng hệ thống chuyên mạch là thời gian truy nhập bộ nhớ sẽ cao và k hôn g đồng bộ. Tuy nhiên việc sử dụng kiến trúc này khiến cho việc thiết kế giải thuật trở nên đơn giản và ở mức cao hơn bởi hệ thống được xử lý như là tất cả các B X L đều được nối trực tiếp với nhau. Hình 1-3 Máy lính song song chia SẺ bộ nhó chung b) Truyền thông điệp Ngược lại với với các máy tính chia xẻ bộ nhớ chu ng là các máy tính song song có bộ nhớ phân tán trong đó không tồn tại bộ nh ớ chia sẻ chung mà mỗi BXL có bộ nhớ cục bộ riêng của chúng. Với kiến trúc nh ư vậy việc m ở rộng các máy tính có bộ nhớ phân tán trở nên đơn giản hơn rất nhiều. Kết quả là các nhà thiết kế có thể dưa ra các hệ thống có tới hàng nghìn BXL mà không phải thay đổi nhiều trong cấu trúc thiết kế. Tro ng các máy tính song song có hộ nh ớ phân tán các B X L liên lạc với nhau băng các thông điệp (message) qua một m ạ ng liên kết (interconnection network) gồm các liên kết truyền thông trực tiếp giữa một số cặp BXL. Một trong những lựa chọn quan trọng trong thiết kế lúc đó sẽ là các cặp BXL nào được nối với nhau. Tốc độ licn lạc là tối ưu khi các BXL được nối trực tiếp với nhau tuy nhiên điều này thường là không khả thi do số lượng các liên kết là quá lớn đẫn đến việc tăng giá thành của hệ thống. Cách thứ hai đưực sử dụng là các B X L liên lạc thông qua một bus chia sẻ, điều này thường dẫn đến độ trễ cao khi số lượng BXL lớn do vấn đồ tranh chap bus. Hình 1-4 Máy tính song song cỏ hộ nhó phân tán 1.3 Mô hình lập trình song song Việc dưa ra một mỏ hỉnh máy tính chung cho việc lập trình giúp cho việc thiết kế giải thuật trờ nên dơn giàn hơn. Lập trình tuần tự đã có m ô hình truyền thống là mô hình Vo nN eum an. Lập trình song song dưa thêm những khó khăn mới vào mô hình lập trình tuần tự. Nếu chương trình được thực hiện ở m ứ c thấp nhất thì không những số lệnh thực hiện là rắt lớn mà nó còn phải quàn lý trực liếp quá trình thực 12 hiện song song của hàng ngàn BXL và kết hợp hà ng triệu tương tác liên BXL. Bời vậy khả năng trừu tượng và tính module là các đặc tính rất quan trọng trong lập trình song song. Vậy mức độ trừu tượng nào sẽ phù hợp với m ô hình lập trình song song. Rõ ràng là mô hỉnh này cần cho phép đánh giá cụ thể về khả năng thực hiện đồng thời cũng như tính cục bộ để cho phép phát triển các c hư ơn g trình có khả năng m ở rộng và có tính module. Mô hình đó cũng cần phải đơn giản và phù hợp với mô hình kiến trúc của máy tính song song. Dưới đây chủng tôi trình bày hai mô hình đáp ứng được các yêu cầu nêu trên là nhiệm vụ - kênh liên lạc (Task - channel) và mô hình chia sẻ bộ nhớ chung. 1.3.1 M ô hình nhiệm vụ - kênlí liên lạc Mô hình nhiệm vụ/kênh licn lạc [15] có thế được lỏm tắt như sau: ❖ Một công việc tính toán song song hao gồm một hoặc nhiều nhiệm vụ. Các nhiệm vụ có thể được thực hiện đồng thời, s ố lượng nhiệm vụ có the thay đổi trong thời gian thực thi c hươ ng trình. ❖ Mồi nhiệm vụ là một chương trình tuần tự và có bộ nhớ cục bộ (có the coi đó là một máy Vo nN eum an ào). Một tập các cổng vào và cổng ra (ĩnports and oulports) được định nghĩa như giao diện của nó với môi trường. ❖ Một nhiệm vụ có thẻ thực hiện 4 thao tác cơ bản ngoại trừ việc dọc và ghi vào bộ nhớ cục hộ, dó là: gửi thông điệp tới các cổng ra, nhận thông điệp từ các cổng vào, tạo ra nhiệm vụ mới và kết thúc viêc thực thi c hư ơng trình. ❖ Thao tác gửi dữ liệu là không đồng bộ (nó dược hoàn thành ngay lập tức). Thao tác nhận dữ liệu là đồng bộ theo nghĩa là nó khiến cho việc thực thi của nhiệm vụ phải dừng lại cho đến khi nhận được thông diệp. ❖ Các cặp cổng vào/cổng ra cố thể được nối bởi một hàng thông điệp dược gọi là một kcnh licn lạc. Các kcnh liên lạc có the được lạo ra lioặe xoa di. 13 •> Các nhiệm vụ được ánh xạ vào các BXL vật lý theo nhiều cơ chế khác nhau, cơ chế ánh xạ được sử dụng không làm ảnh hưởng tới ngữ nghĩa của chươ ng trình. Có thể có nhiều nhiệm vụ được ánh xạ lên một B X L Đặc điểm của mô hình nhiệm vụ - kênh liên lạc a) Tốc độ Các khái niệm trừu tượng về lập trình tuần tự trong m ô hỉnh như khái niệm thù tục và cấu trúc dữ liệu là hiệu quả bởi chúng có thể đượ c ánh xạ trực tiếp và đơn giàn lên chiếc máy tính VonNeuman. Các khái niệm về nhiệm vụ và kênh liên lạc cũng có thể được ánh xạ trực tiếp lên mô hình máy tính song song. Một nhiệm vụ đại diện cho một đoạn mã được thực hiện tuần tự trên một BXL. Nếu hai nhiệm vụ licn lạc với nhau qua một kcnh chung được ánh xạ lcn các B X L khác nhau thỉ kênh liên lạc giữa chúng được thể hiện như truyền thông liên BXL, nếu chúng được ánh xạ lẻn cùng một B X L thì một cơ chế hiệu quả hơn có thể được sử dụng. b) Tỉnh độc lập ánh xạ Trong mô hình trên các nhiệm vu tương tác với nhau sử dụng cùng một cơ chế là kcnh licn lạc không tính đến vị trí cùa nhiệm vụ. Do đó kết quà đưa ra hởi chương trình không phụ thuộc vào vị trí nhiệm vụ thực thi. Bởi vậy việc thiết kế các giải thuật song song có thể được thực hiện mà không cần tính đến số lượng BX1, trong thực tê. r h ô n g thường các thiết kế đều đưa đến sổ lượng nhiệm vụ tạo ra lớn hơn sô lượng B X L có, khi đó việc đạt dược khả năng m ở rộng (scalability) là tương đôi rõ ràng. Việc tạo ra nhiêu nhiệm vụ hơn số B X L cũng cho phép giảm bớt chi phí truyền thông hởi khi một nhiệm vụ đang truy nhập dữ liệu ở xa thì một nhiệm vụ khác có thể đang thực hiện công việc tính toán. c) Tính m odule Khi thiêt kê một chương trình có tính module, nhiều thành phần của chương trinh có thể được phát triển như các module độc lập và sau đó đưc kết hợp lại để tạo thành chương trình. Các module có thể được thay đổi mà không cần thay đổi các thành phần khác. Các dặc tính của chương trình có thể đượ c xác định lừ các đặc tả về các module và các mã lệnh nổi các module. Việc áp đụ ng có hiệu quả các thiết kế module sẽ giúp giảm bớt độ phức tạp cùa chương trinh cũn g n hư cho phép tái sử dụng các đoạn mà. 14 Khái niệm mội nhiệm vụ trong mô hình nhiệm vụ /kênh liên lạc phù hợp một cách tự nhiên với một module trong quá trình thiết kế. Một nhiệm vụ ở đây bao gồm cả dừ liệu và mã lệnh thao tác trên dữ liệu này, các cổn g m à nó gửi và nhận thông điệp tạo nên giao diện của nó. Bởi vậy các ưu điểm của thiết kế module có thể được áp dụng trực tiếp trong mô hình nhiệm vụ/kênh liên lạc. Gi ưa mô hình n h i ệ m vụ/kênh liên l ạ c và c á c thuật n g ữ lập trinh hướng đối tượng cũng có nhiêu điểm giống nhau. Các nhiệm vụ cũng giốn g như các đổi tượng bao bọc dữ liệu và mã của nhiệm vụ thao tác trên dữ liệu đó. Sự khác biệt giữa chúng là mô hình nhiệm vụ/kênh licn lạc cung cấp khả năng thực hiện đồng thời sử dụng các kênh liên lạc chứ không phải các phươ ng thức để thực hiện các tương tác và không hỗ trợ khả năng thừa kế. d) Tính xác định Một giải thuật hay một chương trình được coi là xác định nếu như sự thực thi với một dữ liệu vào riêng biệt luôn đưa ra một két quả duy nhất. Nếu giải thuật là khong xác đinh thì các lân thực thi khác nhau của ch ươn g trình sẽ đưa ra những kết quà khác nhau. Mặc dù tính không xác định đôi khi là hữu ích và được hồ trợ việc hỗ trợ tính xác định của chương trình trên mô hình lập trình song song giúp cho việc viet chương trình trở ncn dê dàng hơn nhiêu. Một ch ươ ng trình xác định sẽ (lỗ hiểu và dễ kiểm tra tính đúng đắn hơn, Trong mô hình nhiệm vụ/kcnh liên lạc mỗi kênh có một nhiệm vụ gửi và một nhiệm vụ nhận, nhiệm vụ ycu cầu dữ liệu phải ngừng thực thi cho đến khi có thông diệp tới giúp cho việc đảm bảo tính xác định của chương trình. 1.3.2 Mô hình chia sẻ bộ nhớ chung Trong mô hình bộ nhớ chung [ 15] các nhiệm vụ cùng chia xẻ một không gian địa chỉ chung có thể được truy nhập đọc ghi theo ph ư ơ n g thức không dồng bộ. Các cơ chê khác nhau n h ư khoá (Locks) và semaphore được sử dụng để điều khiển việc truy nhập tới bộ nhớ chung. Xct theo quan điểm của lập trình viên thì ưu điểm của m ô hình nảy là không có khái niệm sờ hữu (lữ liệu, nghĩa là không phải chỉ định rỗ ràng quá trình truyền dữ liệu giữa nhiệm vụ gửi và nhiệm vụ nhận dữ liệu. Tính chất này giúp cho việc phát triền chương trình dơn gián hơn. Tuy nhicn khi dó việc hiểu và đảm hào lính cục hộ trờ nôn khó khăn và cũng dược chú ý nhiều nhắt trong 15 phần lớn các kiến trúc chia xẻ hộ nhớ chung. Việc viết các chươ ng trinh xác định cũng trờ nên khó khăn. 1.4 Hiệu năng cùa xử lý song song Trong phấn này chúng tôi trinh bày một số vấn đề liên quan đến hiệu năng cùa xử lý song song bao gồm: k h ỉ năng tăng tốc độ lính toán, việc cân bằng tài (Load balancing) và sự bế tắc (Deadlock). 1.4.1 Định luật A m dahl's Trong nhiều ứng dụng thực tế đòi hòi thời gian thực, vấn đề cần giải quyết có kích thước cố định, do đó khối lượng công việc phải làm cũng tlurờng xác định được trước. Định luật (lo Amdahl [91 phát biểu (1967) nhàm đánh giá hiệu năng cùa VICC tinh toán cho các bai toán thuộc dạng này Khi tăng số lượng BXL trong hệ (hống máy song song, khói lượng công việc đư ạ c phân phối cho nhiều BXL thực hiện. Mục tiêu chính là tìm được kết quả cùa bài nhanh nhắt có thể hay nói một cách khác là giảm đến m ứ c tối đa thời gian tính toán. Định luật Amdahl: Gọi f là phần nhỏ của (hao tác tính toán trong quá trình tính toán phải thực hiện một cách tuần tụ. 0 < f < 1. Tốc độ tối đa s có thể đạt được bằng cách Sừ dụng máy tính song song với p BXL dược cho bởi côn g thức: s < —— —?— —— . / + 0 ~ /)/? Thời gian cho phần việc xử lý song song của ứng dụng sẽ giảm dần đến 0 khi ta tăng sổ lượng BXL. Thời gian cho phần việc xử lý tuần tự luôn là hàng số. p-l P--2 !>=4 llìnli 1-5 S ụ phụ thuộc thời ginn v à n số lirợng 11X1, của định luật Amdahl 16 1.4.2 Cân bằng tái Ciià sử răng nếu dữ liệu được phân tán trên các bộ nhớ địa phư ơn g của các BXL trong hệ thống nhiều máy tính, khi đó khối lượng công việc của các B X L cần phải được phân phôi hợp lý trong suôt quá trình tính toán. Tro ng nhiều trường hợp giả sử này là đúng, tuy nhiên trong thực tế điều không phải lúc nào cũng thực hiện được. Giải pháp dược đưa ra ở đây là cân bằng tải động nhằm mục đích làm thay đổi sự phân phối khối lượng công việc giữa các B X L trong quá trình thực hiện tính toán. ỉ hông thườ ng sau khi phân phối khối lượng công việc cho mồi BXL, quá trình cân bàng tải động thực hiện bốn bước cơ bản dưới đây: Giá m sát hiệu năng của mỗi BXL, trao dôi thông tin trạng thái giữa các BXL, tính toán và ra quyết định phân phối lại khối lượng công việc và cuối cùng là thực hiện viêc chuyển đổi dữ liệu thực De thực hiện điều này rất nhiều thuật toán để thực hiện cân bàng tải động dược đê xuât. í heo kêt quà Znati ct al [14] phân lớp các thuật toán này theo chiến lược tập trung, phân tán hoàn toàn (Fully distributed) và phân tán một nửa (Scmi distributed). a) Các thuật toán cân bằng tải tập trung Nh ằm đưa ra quyết định có tính chất tổng thể trong việc phân phối lại khối lượng công việc cần thực hiện cho các RXL. Một vài thuật toán trong lớp này sử dụng thông tin hệ thông có tính toàn cục đổ lưu trạng thái của các máy ricng biệt trong hệ thống. T hô ng tin này sẽ cho phép thuật toán phân phối công việc cho các BXL một cách dễ dàng. Tuy nhiên khối lượng thông tin tăng theo tỷ lệ thuận với số lượng các BXL, do đó đòi hỏi khối lượng lớn hộ nhớ trên m ột B X L để lưu thông tin trạng thái. Vỉ vậy các thuật toán thuộc lớp này không được tiếp cận một cách rộng h) Cúc thuật toán cân bằng tải phân tản hoàn toàn Trong chiên lược này, môi B X L có một bàn sao về thông tin trạng thái của hệ thông. Các B X L trao đổi thông tin trạng thái với nhau và sử dụng các thông tin này dể làm thay đổi một cách cục bộ việc phân chia công việc. Tu y nhicn các B XL chỉ có thông tin trạng thái cục hộ ncn việc cân hẩng tải không tốt bằng các thuật toán 17 cân băng tải tập trung. c) Cúc thuật toán cân bằng tải phân tán m ột nửa Các thuật toán thuộc lớp này chia các BXL thành từng miền. Trong mỗi miền sử dụng thuật toán cân bằng tải tập trung để phân phối côn g việc cho các BXL thuộc miền đó. ả) S ự bế tắc (Deadlock) Các tiến trình xử lý bị rơi vào tình trạng bế tấc [14] nếu mỗi tiến trình đó nắm giữ tài nguyên mà một vài tiến trình khác đang yêu cầu để x ử lý. Lý do tiềm ẩn tồn tại sự bế tắc là do nhiều liến trình cùng sử dụng nguồn tài nguyên chung mà không có sự kiểm soát tốt. Sự bế tắc tồn tại trong các các hệ điều hành đa nhiệm, cũng như các hệ thống đa BXL và đa máy tính. Đổi với các hệ thống da máy tính, một trong các sự bế tắc phổ biến là bế lắc vùng đệm (Buffer deadlock) - xảy ra khi một tiến trinh đợi một thông điệp mà thông điệp này có thể không bao giờ nhận được do vùng đệm hệ thống dã đày . Xem xét hệ thống đa máy tính với các B X L xử lý kh ông đồng bộ. B X L Pj gửi thông diệp cho BX L khác Pj không kết khối cho tới khi có thao tác đọc thông điệp đó. Mặt khác khi B X L Pj gửi thông điệp cho BXL Pj, nội dung của thòng điệp được lưu trong vùng độp của hộ thống cho đến khi B XL Pj nhận và đọc thông điệp. Giả sử rang trong cùng một thời điểm có nhiều B X L cùng gửi thông điệp đến BXL Pj và điều này sẽ làm cho vùng đệm bị đầy. Việc gửi các thông điệp tiếp theo chỉ thực hiện được khi B X L Pj đọc một hay nhiều thông điệp. Giả sử B X L p k là một trong các B XL có khả năng gửi thông điệp đến BXL Pj. Neu B X L Pj cố gắng đọc thông điệp do BXL p k gửi đến, nó sẽ bị kết khối cho đến khi nội dung thông điệp có trong vùng đệm. Rõ ràng B X L p k bị kết khối cho đến khi BXL Pj loại bỏ một hay nhiều thông điệp từ vùng đệm, và như vậy B XL Pị và p k rơi vào sự bế tác. ỊTRUW5TÀM ĨHG-:; ĨIN ' :L" ■ ! i Nr V: LO/ 1 IX Hình 1-6 B X L p k kết khối để gùi X cho Pj vì vùng đệm của Pj đầy. Pj không thể để nhận được X. Pj và p k roi vào s ự bế (ắc Theo kết quà nghiên cứu cùa Coffman và Denning, bốn điều kiện dưới đây là nguyên nhân gây ra sự bể tác. 1 Sự loại trừ lẫn nhau: Mỗi tiến trình có sự độc quyền trong việc sử dụng tài nguyên cùa nó 2 K hô ng có sự ưu tiên: Mỗi tiếp trinh không bao giờ giải phóng tài nguycn mà tiến trình đó đang chiếm giữ cho đến tận khi không còn sử dụng chúng nữa. 3 Sự chờ đợi tài nguyên: Mỗi tiến trình dang chiếm giữ tài nguyên trong khi lại chờ đợi các tiến trình khác giải phóng chúng. 4 Sự chờ đợi giữa các tiến trình: Tiến trình đợi tài nguyên mà tiến trình kế ticp dang chiêm giữ mà tài nguyên dỏ không dượ c giải phóng. M ột so cách khắc phục sự bế tắc Cách tiêp cận thứ nhất là dò tìm sự bế tắc khi chúng xảy ra và cố gắng khôi phục lại. Một cách khác dể tránh sự bế tắc thông qua sử d ụng các thông tin yêu cầu lài nguycn của các tiến trình để điều khiển sự phân phối để khi tiếp tục phân phối các tài nguyên không là nguyên nhân dổ các tiến trình rơi vào sir bế tắc. Cách tiếp cận thứ ba đê tránh sự bê tăc là ngăn câm không để xảy ra ba điều kiện nêu sau cùng trong bốn điều kiện nêu trên. 19 Chương 2 Song song hoá thuật toán tự 2.1 Cac chiên lược phát triển ứng dụng song song Một câu hỏi được đặt ra khi phát triển ứng dụng song song là sự lựa chọn giữa việc chuyên đôi từ một ứng đụng tuần tự đã có sẵn hay là xây dựng một ứng dụng song song từ ban đầu. í rong khuôn khổ luận văn, chúng tôi chỉ tập trung vào việc phát triển ứng dụng song song dựa trên ứng dụng tuần tự [15] đã có sẵn. Có ba chiên lược thông dụng phổ biến để tạo ra ứng dụng song song là song song hoá tự động, sử dụng các thư viện song song và lưu lại các thành phần chính của chương trinh tuân tự. Sau đây chúng tôi trình bày khái quát về các chiến lược này. 2. L ĩ Song song hoó tự động Mục đích của chiến lược này là giúp dỡ người lập trình thực hiện các nhiệm vụ một cách song song. Bộ hiên dịch có thể chấp nhận các đoạn mã lệnh và thực hiện song song hoá chúng một cách hiệu quà mà không cần người lập trình bỏ công sưc. I uy nhiên, dicii nay là rất khó trờ thành hiện thực vì khó xây dựng công nghệ cho bộ biên dịch. Existing Source C ode M i n o r C ' od e Automatic -------- ► Modification Parallel w■ Parallelization Application Hình 2-1 Song song hoá (ụ động 2.1.2 X ây (ỉiptg các th ư viện song song Y tương cua phương pháp này là xây các đoạn mã lệnh song song được sử dung lại nhiều lần trong một số ứng dụng thành các thư viện để có thể dùng nó xây dựng ưng dụng khác một cách dễ dàng. I hư viện này có thổ được hình thành theo hai cách, cách thứ nhất bao gói (Encapsulate) các cấu trúc điều khiển của các lớp dối tượng trong ứng đụng, cách thứ hai tiến hành cài đặt song song một số thuật toán cốt lõi cùa các thủ tục.