Báo cáo "Bài toán workflow scheduling trong môi trƣờng điện toán đám mây "

Chia sẻ: Phạm Huy | Ngày: | Loại File: PDF | Số trang:16

Thêm vào BST

Báo xấu

95
lượt xem 15
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tổng quan về điện toán đám mây, các khái niệm và sự cần thiết của việc thực thi workflow trong môi trƣờng điện toán đám mây. Trình bày các khái niệm về phƣơng pháp tối ƣu bày đàn PSO và cách xây dựng giải thuật PSO để giải quyết các bài toán tối ƣu. Giải thuật lập lịch sử Heuristic dựa tối ƣu bầy đàn đề xuất: bài toán lập lịch ứng dụng luồng công việc; xử lý các dữ liệu bài toán dùng giải thuật PSO; giải thuật Heuristic dựa PSO. Cài đặt, quá trình tiến hành và...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo "Bài toán workflow scheduling trong môi trƣờng điện toán đám mây "

Bài toán workflow scheduling trong môi trƣờng điện toán đám mây Kiều Tuấn Dũng Trƣờng Đại học Công nghệ Chuyên ngành: Công nghệ phần mềm; Mã số: 60 48 10 Cán bộ hƣớng dẫn khoa học: TS. Phạm Ngọc Hùng Năm bảo vệ: 2012 Abstract. Tổng quan về điện toán đám mây, các khái niệm và sự cần thiết của việc thực thi workflow trong môi trƣờng điện toán đám mây. Trình bày các khái niệm về phƣơng pháp tối ƣu bày đàn PSO và cách xây dựng giải thuật PSO để giải quyết các bài toán tối ƣu. Giải thuật lập lịch sử Heuristic dựa tối ƣu bầy đàn đề xuất: bài toán lập lịch ứng dụng luồng công việc; xử lý các dữ liệu bài toán dùng giải thuật PSO; giải thuật Heuristic dựa PSO. Cài đặt, quá trình tiến hành và bảng số liệu thử nghiệm cùng với những phân tích. Đƣa ra kết quả đã đạt đƣợc và nêu những dự định nghiên cứu tiếp theo. Keywords: Công nghệ phầm mềm; Bài toán; Điện toán đám mây Content. TÓM TẮT Đối với các công ty hay doanh nghiệp, việc quản lý dữ liệu và xử lý các bài toán sao cho hiệu quả là một trong những bài toán ƣu tiên hàng đầu. Muốn vậy các doanh nghiệp phải đầu tƣ tính toán rất nhiều loại chi phí khác nhau nhƣ: phần cứng, phần mềm, mạng, chi phí bảo trì, sửa chữa, nâng cấp, quản lý, kiểm soát bảo mật … Mô hình điện toán đám mây (Cloud Computing) đáp ứng đƣợc các yêu cầu đặt ra và đang đƣợc các công ty, doanh nghiệp hƣớng đến. Sử dụng mô hình này, các công ty, doanh nghiệp chỉ cần trả phí cho những ứng dụng luồng công việc (workflow) mà họ dùng (loại công việc đòi hỏi nhiều công đoạn xử lý theo trình tự định trƣớc) mà không cần đầu tƣ nhiều vào cơ sở hạ tầng, cũng nhƣ quan tâm nhiều đến công nghệ. Tuy nhiên, nhiều vấn đề của hệ thống xử lý đám mây xuất hiện nhƣ: làm sao để sử dụng một cách hiệu quả những tài nguyên phân tán hiện có, giảm thiểu chi phí tính toán và truyền thông … Từ đó bài toán lập lịch cho các ứng dụng workflow đƣợc đặt ra và đó là nội dung hƣớng tới của đề tài. Luận văn này sẽ tập trung vào biểu diễn một giải thuật heuristic dựa vào giải thuật tối ƣu bầy đàn (Particle Swarm Optimization – PSO) để lập lịch các ứng dụng cho các tài nguyên đám mây mà đƣa vào tính toán cả chi phí tính toán và chi phí truy cập dữ liệu. Luận văn đã thử nghiệm với một 0
ứng dụng luồng công việc trên môi trƣờng mô phỏng CloudSim bằng cách thay đổi chi phí tính toán và truyền thông. Luận văn đã so sánh chi phí tiết kiệm khi sử dụng giải thuật PSO với hai giải thuật Random và RoundRobin đã có. Kết quả luận văn đã chỉ ra rằng PSO đạt đƣợc tiết kiệm chi phí rất hiệu quả so với Random và RoundRobin. Bằng cách thử nghiệm trên môi trƣờng mô phỏng CloudSim và kiểm chứng đƣợc hiệu quả của giải thuật PSO trong vấn đề tiết kiệm chi phí hiệu quả khi thực thi các ứng dụng workflow trong môi trƣờng điện toán đám mây, luận văn hi vọng sẽ đem lại một kết quả có ý nghĩa trong thực tiễn, là hƣớng nghiên cứu trong các ứng dụng thực tế để xử lý hiệu quả bài toán tiết kiệm chi phí trong các doanh nghiệp. I. GIỚI THIỆU Mô hình hợp tác ở nhiều thử nghiệm khoa học trong nhiều lĩnh vực nhƣ sinh học cấu trúc, vật lý năng lƣợng cao, khoa học thần kinh liên quan đến việc sử dụng các nguồn dữ liệu phân tán. Kết quả, việc phân tích các tập dữ liệu này đƣợc biểu diễn và cấu trúc hóa nhƣ là các luồng công việc (workflow) khoa học. Những luồng công việc khoa học này thƣờng cần phải xử lý lƣợng dữ liệu rất lớn và các hoạt động tính toán chuyên sâu, Hệ thống quản lý luồng công việc khoa học đƣợc sử dụng để quản lý những thử nghiệm khoa học này bằng cách che giấu các chi tiết khi thực thi luồng công việc trên các tài nguyên phân tán đƣợc cung cấp bởi các nhà cung cấp dịch vụ đám mây. Điện toán đám mây (cloud computing) là một mô hình mới cho tính toán phân tán mà cung cấp hạ tầng, nền tảng và phần mềm (các ứng dụng) nhƣ là các dịch vụ. Các dịch vụ này đƣợc tạo sẵn nhƣ là các dịch vụ thuê bao (trả phí cho những gì mình sử dụng) dành cho các khách hàng. Điện toán đám mây giúp cung cấp linh hoạt nhiều tài nguyên tính toán cho các ứng dụng của khách hàng ở vị trí xác định (US ở amazon là một ví dụ 1) dựa trên các yêu cầu của họ. Cũng nhƣ vậy, các ứng dụng có thể lựa chọn vị trí lƣu trữ để lƣu trữ các dữ liệu (Amazon S3 2) ở các vị trí toàn cầu. Để đạt đƣợc hiệu quả tính toán và chi phí hiệu quả lập lịch công việc (task) và dữ liệu của ứng dụng trong môi trƣờng điện toán đám mây, bộ lập lịch phải có các chính sách lập lịch khác nhau thay đổi theo hàm mục tiêu: tối thiểu tổng thời gian thực thi, tối thiểu tổng chi phí thực thi, cân bằng tải trên tài nguyên đƣợc sử dụng khi gặp ràng buộc deadline của ứng dụng, v.v. Luận văn này tập trung vào nghiên cứu tối thiểu tổng chi phí thực thi của ứng dụng trên các tài nguyên đƣợc cung cấp bởi các nhà cung cấp dịch vụ đám mây, nhƣ Amazon và GoGrid 3. Luận văn đạt đƣợc điều này bằng cách sử dụng một phƣơng pháp meta-heuristic đƣợc gọi là tối ƣu bầy đàn (Particle Swarm Optimization – PSO). 1 http://aws.amazon.com 2 http://aws.amazon.com/s3/ 3 http://www.gogrid.com 1
PSO là một kỹ thuật tìm kiếm tối ƣu toàn cục bộ tự thích nghi đƣợc giới thiệu bởi Kennedy và Eberhart [4]. Giải thuật tƣơng tự các giải thuật dựa vào quần thể khác nhƣ giải thuật di truyền nhƣng nó không có sự tổ hợp lại của các tác nhân trong quẩn thể. Thay vào đó, nó dựa trên ứng xử xã hội của các cá thể. Trong mỗi thế hệ, mỗi cá thể tự điều chỉnh quỹ đạo dựa trên vị trí tốt nhất của nó (local best) và vị trí của cá thể tốt nhất (global best) trong cả quần thể. Khái niệm này làm tăng tính tự nhiên của các cá thể và nhanh chóng đạt tới giá trị tối ƣu toàn cục với giải pháp tốt nhất. PSO trở nên phổ biến, phát triển và trở thành hƣớng nghiên cứu rộng rãi trong nhiều ứng dụng trong những năm gần đây bởi tính đơn giản mà hiệu quả của nó với chi phí thấp. Một số ứng dụng đã sử dụng PSO: vấn đề điều khiển phản ứng điện áp (reactive voltage control problem), khai phá dữ liệu, kỹ thuật hóa học, nhận dạng mẫu, và kỹ thuật môi trƣờng. PSO cũng đƣợc ứng dụng để giải quyết các vấn đề NP-Hard nhƣ lập lịch và phân bổ công việc. Đóng góp của luận văn này là:  Luận văn đã xây dựng một mô hình phân bổ công việc (task) – tài nguyên (resource) (phân bổ các công việc cho các tài nguyên tính toán xử lý) để tổi thiểu toàn bộ chi phí thực thi.  Luận văn đã thiết kế một giải thuật heuristic sử dụng PSO để giải quyết vấn đề phân bổ công việc – tài nguyên dựa trên mô hình đề xuất. Phần còn lại của luận văn đƣợc cấu trúc nhƣ sau: chƣơng 2 trình bày tổng quan về điện toán đám mây, các khái niệm và sự cần thiết của việc thực thi workflow trong môi trƣờng điện toán đám mây. Chƣơng 3 sẽ đi nghiên cứu các khái niệm và chi tiết về giải thuật PSO, các vấn đề xây dựng giải thuật PSO để giải quyết bài toán tổng quan. Vấn đề của bài toán lập lịch luồng công việc sẽ đƣợc trình bày ở chƣơng 4. Đồng thời, chƣơng 4 sẽ trình bày phƣơng pháp giải quyết bài toán bằng giải thuật PSO và một thiết kế giải thuật heuristic sử dụng PSO để giải quyết vấn đề phân bổ công việc – tài nguyên dựa trên mô hình đã đề xuất. Chƣơng 5 sẽ trình bày cài đặt bài toán, kết quả bài toán. Và cuối cùng, chƣơng 6 sẽ tổng kết lại luận văn và hƣớng nghiên cứu tiếp theo. 2
II. LẬP LỊCH WORKFLOW TRONG MÔI TRƢỜNG ĐIỆN TOÁN ĐÁM MÂY 1. Tổng quan về điện toán đám mây Từ năm 2015 sẽ có khoảng 15 tỉ thiết bị kết nối đến internet và hầu hết đó là những thiết bị thông minh ví dụ nhƣ note book, netbook, điện thoại thông minh, ô tô thông minh và thậm chí là cả những chiếc ti vi thông minh tất cả chúng đều kết nối đến internet vì thế chúng ta cần phải có một giải pháp sao cho linh hoạt để đáp ứng đƣợc những dịch vụ cho hàng loạt những thiết bị - Đó là điện toán đám mây. Theo dự báo của Intel thì giá trị thị trƣờng dịch vụ của điện toán đám mây có thể đạt tới con số 43 tỉ đô la Mỹ vào năm 2012 và khẳng định trong vòng 3 năm tới dịch vụ điện toán đám mây có thể đạt tới mức tăng trƣởng gộp hằng năm là 27% một con số cực kỳ ấn tƣợng cao gấp năm lần so với dịch vụ truyền thống khác trong lĩnh vực IT. IBM là doanh nghiệp tiên phong trong khai trƣơng trung tâm điện toán đám mây đầu tiên ở Việt Nam vào tháng 9 năm 2008 với khách hàng đầu tiên là Công ty cổ phần công nghệ và truyền thông Việt Nam. Còn Microsoft trong tháng 5 vừa qua đã chính thức ký kết biên bản ghi nhớ với tập đoàn FPT nhằm thúc đẩy Điện toán đám mây tại Việt Nam. Sự phát triển của Điện toán đám mây đƣợc sơ đồ hóa theo nhƣ Hình 2.1 dƣới đây: mở đầu là công nghệ Clustering xuất phát từ nhu cầu đảm bảo hoạt động cho máy chủ và hệ thống mạng, clustering cho phép sử dụng nhiều máy chủ kết hợp với nhau tạo một cụm (cluster) có độ tin cậy cao (giảm thiểu khả năng rủi ro), có khả năng chịu đựng và chấp nhận các sai sót. Grid Computing, một hệ thống phân tán đƣợc bố trí song song, tận dụng mọi nguồn tài nguyên độc lập và rải rác về mặt địa lý, gần giống nhƣ Clustering, ra đời để giải quyết các bài toán lớn không giới hạn về mặt không gian địa lý và nền tảng hệ điều hành . Theo sau đó lại là nhu cầu tính toán cao với mục đích tiết kiệm phi phí, tính toán theo nhu cầu (utility computing). Ngƣời sử dụng chỉ phải trả chi phí cho những gì mà họ sử dụng giống nhƣ trả tiền theo hóa đơn điện, nƣớc hàng tháng. Tôi thuê sử dụng máy chủ trong 1h và tôi sẽ trả phí cho 1h mà tôi đã sử dụng của anh. Nhu cầu thuê phần cứng và trả tiền cho những gì mình sử dụng đã chuyển tiếp sang mô hình đi thuê phần mềm có trả phí. Tôi cũng không cần phải đầu tƣ nhiều phần mềm, khi nào tôi cần sử dụng, tôi sẽ thuê của anh và trả phí theo dịch vụ mà anh đƣa ra. Và cuối cùng, điện toán đám mây là tổng hợp toàn bộ các nhu cầu, tiện ích và các dịch vụ mà các mô hình trƣớc đem lại. Tất cả các tài nguyên (phần cứng, phần mềm) đều đƣợc sử dụng nhƣ là một dịch vụ, sẵn sàng đáp ứng mọi lúc, mọi nơi với chi phí hợp lý. 3
Sự phát triển của công nghệ tính toán và hình thành Điện toán đám mây Điện toán đám mây (Cloud Computing) Phần mềm như là dịch vụ Điện toán theo nhu cầu (SaaS) (Utility Computing) Điện toán lưới Tính toán phân cụm (Grid Computing) Thuê các ứng dụng nhƣ là (Clustering) dịch vụ thông qua mạng Cung cấp các tài nguyên tính Internet toán nhƣ là dịch vụ có đo lƣờng mức độ sử dụng Các phân cụm độc lập liên kết với nhau Tính toán hiệu năng cao Tính toán song song cho các Máy tính trao đổi qua các bài toán lớn giao thức Hình 2. 1: Sự phát triển của cloud computing từ clustering. 4
Ý tƣởng nền tảng của Điện toán đám mây đã phát triển từ khá lâu trên thế giới nhƣng cho đến gần đây cùng với sự bùng nổ của Internet và công nghệ mạng cũng nhƣ nhu cầu của thị trƣờng các tên tuổi lớn trên thế giới mới bắt đầu đƣa những ý tƣởng trở thành những ứng dụng thật tại thị trƣờng Việt Nam. 2. Workflow (Luồng công việc) Định nghĩa luồng công việc (workflow): Theo Ravneet [13], một luồng công việc hay một quy trình nghiệp vụ (bussiness process) là thứ tự các bƣớc, tác vụ, sự kiện hoặc tƣơng tác làm nên một quy trình để thực hiện một công việc nào đó. Lợi ích của việc thực thi luồng công việc trong môi trường Điện toán đám mây: Theo Ravneet [13], đƣa luồng công việc vào thực thi trong môi trƣờng điện toán đám mây cho phép sử dụng các dịch vụ đám mây khác nhau. Lợi ích chính của việc này chính là khả năng mở rộng ứng dụng. Không giống nhƣ môi trƣờng lƣới, môi trƣờng điện toán đám mây cho phép mở rộng các tài nguyên đám mây theo thời gian thực để đáp ứng nhu cầu thực thi. Khả năng co giãn của đám mây cho phép mở rộng quy mô linh hoạt khi có nhu cầu lớn hơn hoặc giảm đi khi nhu cầu thấp. Điều này cho phép hệ thống quản lý luồng công việc đáp ứng đƣợc nhu cầu về chất lƣợng dịch vụ theo yêu cầu của ứng dụng. Mô hình lấy ngƣời dùng làm trung tâm trong môi trƣờng điện toán đám mây làm tăng tính thân thiện và thỏa mãn yêu cầu của ngƣời dùng. Mô hình kinh doanh "trả cho những gì bạn đã sử dụng" làm giảm các chi phí thực thi luồng công việc. Cụ thể, lợi ích của việc thực thi trong môi trƣờng điện toán đám mây bao gồm: Ảo tƣởng về một nguồn tài nguyên vô hạn (Illusion of infinite resources): ngƣời dùng có thể đƣa ra yêu cầu tài nguyên cần thiết cho ứng dụng ở bất cứ thời điểm nào; Tài nguyên đi thuê (Lease): ngƣời sử dụng trực tiếp xác định nguồn tài nguyên cần thuê một cách hợp lý để lập lịch cho các tính toán của họ. Mô hình này là lý tƣởng vì nó làm giảm chi phí lập lịch; Tính co giãn (Elasticly): cho phép ngƣời dùng có thể thuê đƣợc và phân bổ tài nguyên theo nhu cầu. Hệ thống workflow dễ dàng phát triển hoặc thu nhỏ nguồn tài nguyên theo thời gian Thách thức của việc thực thi luồng công việc trong môi trường Điện toán đám mây: Theo Ravneet [13], những thách thức gặp phải khi thực thi luồng công việc trong môi trƣờng Điện toán đám mây bao gồm: Chi phí: trong thực tế, một số dịch vụ điện toán đám mây là miễn phí, nhƣng một số dịch vụ thì không. Điều này đồng nghĩa với việc ngƣời sử dụng sẽ phải tiền cho những gì mà họ sử dụng. Do vậy, chi phí trở thành một mối quan tâm lớn của các ứng dụng workflow. Nếu đƣa ra cả hai thuộc tính về thời gian và chi phí, ngƣời sử dụng sẽ phải đƣa ra ngay quyết định là trả nhiều chi phí hơn để giảm thời gian thực hiện hoặc tiết kiệm chi phí bằng cách cho phép kéo dài thời gian thực thi lâu hơn miễn là thời hạn cuối cùng để thực hiện công việc vẫn có thể đƣợc đáp ứng. Thỏa thuận cấp độ dịch vụ: với hầu hết các dịch vụ điện toán đám mây đến từ các tổ chức thƣơng mại lớn, các thỏa thuận cấp độ dịch vụ trở thành một mối quan tâm quan trọng cho cả nhà cung cấp 5
dịch vụ và khách hàng. Do cạnh tranh trong cung cấp dịch vụ đang nổi lên, các nhà cung cấp phải đảm bảo: chất lƣợng dịch vụ (QoS) tốt cho khách hàng và các điều khoản phải rõ ràng cho việc bồi thƣờng trong trƣờng hợp vi phạm. Khối lượng dữ liệu: tùy thuộc vào dịch vụ đƣợc cung cấp, khối lƣợng dữ liệu cần thiết đƣợc vận chuyển qua dịch vụ Nền tảng hỗ trợ: tùy thuộc vào dịch vụ, nền tảng hỗ trợ yêu cầu của các dịch vụ ứng dụng đám mây cũng có thể là một nhân tố hạn chế. Ngoài vấn đề trên, có thể có những thách thức khác nhƣ vấn đề an ninh, tuân thủ các quy định và minh bạch dữ liệu. Sự cần thiết của việc thực thi workflow trong môi trường Điện toán đám mây: Chúng ta đã thấy đƣợc những lợi ích khi thực thi luồng công việc [13] trong môi trƣờng điện toán đám mây ở trên. Hơn nữa, các ứng dụng luồng công việc thƣờng yêu cầu một môi trƣờng thực thi phức tạp bao gồm: hệ điều hành cụ thể, các thƣ viện, cấu trúc tệp tin hệ thống, nhiều chƣơng trình ứng dụng và các tệp tin cấu hình. Môi trƣờng này thƣờng khó có thể tạo trên các tài nguyên lƣới. Ngoài ra, mỗi một vị trí lƣới đều có cấu hình khác nhau, vì vậy các kết quả thƣờng phải nỗ lực thêm thời gian để chuyển tới các vị trí mới. Máy ảo cho phép phát triển các ứng dụng tạo ra đầy đủ các tùy biến, cấu hình các môi trƣờng thực thi đặc biệt cho các ứng dụng của họ. III. PHƢƠNG PHÁP TỐI ƢU BẦY ĐÀN (PSO) Giải thuật tối ưu hóa bầy đàn (Particle Swarm Optimization – PSO) lấy ý tƣởng từ cách đàn chim tìm thức ăn, nguồn nƣớc. Theo giả thuyết của bài toán, các cá thể ban đầu đƣợc dựng lên trong không gian đó. Mỗi cá thể có một vận tốc ban đầu, và giữa các cá thể cũng có kênh liên lạc. Các cá thể sau đó di chuyển trong không gian lời giải, mỗi cá thể sẽ đƣợc đánh giá bằng một hay nhiều tiêu chuẩn thích nghi, dần dần các cá thể này sẽ di chuyển về phía những cá thể tốt hơn trong phạm vi của chúng. Quần thể ban đầu gồm n cá thể (mỗi cá thể là một lời giải cho bài toán, nhƣng chƣa tối ƣu). Mỗi cá thể thứ i trong quần thể đƣợc biểu diễn bởi một vector xi m chiều (giá trị m tùy thuộc vào mỗi bài toán khác nhau và cách xử lý khác nhau), và một vector vận tốc vi m chiều với i = 1,…,n. Hàm mục tiêu của bài toán là f: Rm →R Mô tả thuật toán chi tiết như sau: B1: Khởi tạo quần thể với việc khởi tạo vector vị trí xi và vector vận tốc vi cho cá thể thứ i, i = 1,.., n (cho mỗi cá thể Pi trong quần thể P(n)) B2: Khởi tạo các thông tin ban đầu về vị trí tốt nhất của các cá thể và cả quần thể pbesti = xi (khởi tạo vị trí tốt nhất của cá thể thứ i bằng vị trí được khởi tạo hiện tại) gbest = min (f(xi)), i = 1,..n (khởi tạo vị trí tốt nhất của cả quần thể bằng vị trí nhỏ nhất trong tất cả các vị trí của tất cả các cá thể được khởi tạo) 6
B3: Bƣớc lặp với điều kiện lặp xác định trƣớc (sau một số lần lặp cho trước hoặc sau một số lần lặp mà không thu được kết quả tốt hơn). for 1
Hình 4. 1: Một workflow ví dụ. Theo Pandey [5], giả thiết chúng ta chỉ xét các ứng dụng thuộc dạng workflow (dữ liệu luồng) trong đó các tác vụ (task) không độc lập mà liên kết với nhau theo một đồ thị G = (V,E) thuộc dạng đồ thị DAG (Directed Acyclic Graph) trong đó: 1: V= tập các task = {T1, T2 ... Tn} 2: E = tập các cạnh biểu diễn mỗi liên hệ về dữ liệu giữa các task = {f j,k}trong đó cạnh fjk cho biết dữ liệu sinh ra bởi task Tj (đầu ra của Tj) sẽ là đầu vào của task Tk. 3: Tập các storage site (máy trạm lƣu trữ - làm nhiệm vụ kho chứa) S = {S1, ... Si} 4: Tập các compute site (máy trạm tính toán - làm nhiệm vụ tính toán, xử lý) S = {PC1, ... PCj}. 5: Chi phí để PCj xử lý xong task Tk đƣợc cho trƣớc, chính là ma trận TP trong Bảng 4.1. 6: Biết cost of unit data access dij = giá cƣớc dành cho máy trạm i khi truy cập một đơn vị dữ liệu đặt trên máy trạm j , giá này do các nhà cung cấp dịch vụ qui định, chính là Ma trận PP trong Bảng 4.2 Ở đây bắt đầu xuất hiện từ resource i, đƣợc hiểu là máy trạm i. Giả thiết dij = dji, dij+djk >= djk. 7: Mỗi task xuất ra output là một khối data và nó đƣợc dùng làm input cho task con. Kích thƣớc của những khối data đó đƣợc gọi là trọng số cạnh (edge-weight) ek1,k2 trong đó task k1 và k2 là cặp Cha-Con, tức là k1 sinh ra output file, file này đƣợc task k2 dùng làm input. Dữ liệu mô tả trong bảng DS – Bảng 4.3 Bảng 4. 1: Chi phí thực thi của mỗi Ti trên các PCj [5] PC1 PC2 PC3 TP[5x3]= T1 1.23 1.12 1.15 T2 1.17 1.17 1.28 8
T3 1.13 1.11 1.11 T4 1.26 1.12 1.14 T5 1.19 1.14 1.22 TP[i,j] = chi phí thực thi của Ti trên PCj (giá trị ở trên ma trận được lấy từ bảng giá sử dụng dịch vụ của Amazon EC2 cho các tài nguyên trong phạm vi 1.1$ - 1.28$/giờ Bảng 4. 2: Chi phí truyền thông giữa các PCj [5] PC1 PC2 PC3 PC1 0 0.17 0.21 PP[3x3]= PC2 0.17 0 0.22 PC3 0.21 0.22 0 PP[i,j]=chi phí truyền thông giữa hai PCi và PCj (giá trị theo đơn vị $/MB/giây) Bảng 4. 3: Kích thước input/output của Task i totaldata totaldata DST2,T3,T4[2x2]= Input 10 DST5[2x2]= Input 30 Output 10 Output 60 Input = dữ liệu đầu vào, output = dữ liệu đầu ra của các công việc (đơn vị: MB) Bài toán có thể phát biểu như sau: “Tìm phương án ánh xạ (mapping) M sao cho giá trị cost lớn nhất trong số các PC là nhỏ nhất” Cexe ( M ) j   wkj , M (k )  j ( 4. 1) k Ctx ( M ) j   d e M ( k 1), M ( k 2 ) k 1,k 2 , M (k1)  j, M (k 2)  j (4. 2) k 1k k 2k Ctotal (M ) j  Cexe (M ) j  Ctx (M ) j (4. 3) Cost (M )  max( Ctotal (M ) j ) , j  P (4. 4) Minimize(Cost (M )), M (4. 5) Giải thích ký hiệu: Cexe(M)j: là tổng cost mà máy PCj phải trả theo sự phân phối của phƣơng án mapping M. Nó bằng tổng các trọng số đỉnh (node-weight) , tức là chi phí thực thi của task k trên tài nguyên tính toán j (PCj), đại lƣợng trong ma trận TP trong bảng 4.1 Ctx(M)j: là tổng chi phí truy cập (access cost, bao gồm transfer cost- phí truyền thông) giữa các task thực hiện bởi PCj và những task khác, là cha hoặc con của những task kể trên. Gọi PC đƣợc M 9
giao thực hiện task k1 là M(k1), PC đƣợc M giao thực hiện k2 là M(k2), nhƣ vậy trọng số cạnh (edge- weight) ek1,k2 sẽ cho biết kích thƣớc file output mà task k1 sinh ra. Tất nhiên M(k1) là task Cha, task M(k2) là task con. Access cost = ek1,k2 (kích thƣớc file output mà task Cha k1 sinh ra cho task Con k2 dùng)  cƣớc truyền thông giữa M(k1) và M(k2). Cƣớc truyền thông của 1 đơn vị dữ liệu giữa 2 PC chính là dM(k1), M(k2) nêu trong mục (7) trên. Nếu 2 task chạy trên cùng PC thì cƣớc truyền =0. Giải thuật xử lý bài toán: Giải thuật 1: Giải thuật PSO B1: Xây dựng kích thƣớc cá thể bằng kích thƣớc các công việc sẵn sàng (task ready 4) t i  T B2: Khởi tạo vị trí các cá thể ngẫu nhiên từ các PC = 1, …, j và vận tốc vi ngẫu nhiên. B3: Với mỗi cá thể, tính giá trị hàm mục tiêu theo công thức (4) B4: Nếu giá trị hàm mục tiêu tốt hơn Pbest tốt nhất trƣớc đó, thiết lập lại giá trị Pbest bằng giá trị mới. B5: Sau bƣớc 3 và 4 cho tất cả các cá thể, chọn cá thể có giá trị tốt nhất coi là Gbest. B6: Đối với tất cả các cá thể, tính toán vận tốc sử dụng công thức: vik+1 = w.vik + c1.rand1.(pbesti – xik) + c2.rand2.(gbest – xik) và cập nhật lại vị trí các cá thể sử dụng công thức: xik+1 = xik + vik+1 B7: Nếu các điều kiện dừng và số lần lặp tối đa chƣa đáp ứng, lặp lại bƣớc 3. Nhận xét:  Giải thuật là động vì nó cập nhật liên tục chi phí truyền thông (dựa trên thời gian truyền thông trung bình giữa các tài nguyên) trong mỗi vòng lập lịch.  Giải thuật tái ánh xạ task-resource vì vậy mà nó tối ƣu chi phí tính toán, dựa trên trạng thái tài nguyên và mạng hiện tại. Giải thuật 2: Giải thuật PSO_Heuristic B1: Tính toán chi phí tính toán trung bình của tất cả các công việc trên tất cả các tài nguyên tính toán. (Dựa ma trận TP trên Bảng 4.1) B2: Tính toán chi phí (thông tin/kích thƣớc dữ liệu) trung bình giữa các tài nguyên. (Dựa ma trận PP trên Bảng 4.2) B3: Thiết lập trọng số các node: weight wkj = (chi phí tính toán trung bình) B4: Thiết lập trọng số cạnh ek1,k2 bằng kích thƣớc file chuyển giao giữa các task. (Dựa ma trận DS trên Bảng 4.3) B5: Tính toán PSO({ti}) với các tasks i  k B6: Repeat B7: For mọi task ở trạng thái “ready” ti  T do B8: Gán mỗi { t i  T } – {pj} theo giải thuật PSO B9: End For 4 Task Ready: Các task ở trạng thái “ready” là các task mà có task cha đã xử lý xong và cung cấp dữ liệu output cho nó 10
B10: Thực hiện mapping: gắn kết các công việc – tài nguyên. B11: Chờ xử lý công việc (sự phụ thuộc dữ liệu đầu vào và đầu ra giữa các công việc). B12: Cập nhật lại các công việc ở trạng thái “Ready” B13: Cập nhật lại chi phí giao tiếp giữa các tài nguyên theo trạng thái mạng hiện tại. B14: Tính toán PSO({ t i }). B15: Ultil không còn công việc nào phải thực thi. V. THỰC NGHIỆM Thực nghiệm sẽ tiến hành cài đặt giải thuật PSO_heuristic trên mô hình đã đề xuất ở Chƣơng 4 và đánh giá hiệu năng của giải thuật PSO_heuristic so với các giải thuật Random và RoundRobin. Để đo hiệu năng giải thuật, luận văn sử dụng chi phí hoàn thành thực thi ứng dụng nhƣ là độ đo. Luận văn sẽ tính toán tổng chi phí thực thi của luồng công việc sử dụng PSO_heuristic và Random, RounRobin. Host1: (1000, 1,0.1); - Host có 1 CPU với năng lực xử lý 1000MI, chi phí để thực thi 0.1 đvt/1000MI. Host2: (1000, 1,0.2); Host3: (1000, 1,0.3); Task1: (25000, 10000)); - Task có độ dài cần xử lý là 25000MI, output size = 10000byte Task2: (25000, 10000)); Task3: (25000, 10000)); Task4: (25000, 10000)); Task5: (25000, 60000)); Số cá thể: 25 Số thế hệ: 30 Số lần lặp: 30 Trọng số quán tính w = 0.85 Chi phí truyền: COST_COMMUNICATION = 0.1 Hệ số gia tốc: C1 = 1.5 và C2 = 0.5 11
50000 40000 30000 Cost 20000 10000 0 PSO_Heuristic Random RoundRobin Hình 5. 2: Biểu đồ so sánh kết quả thực nghiệm workflow sau 30 lần chạy Luận văn đánh giá giải thuật lập lịch heuristic cho luồng công việc (workflow) nhƣ mô tả ở hình 4.1. Mỗi một công việc đều có các dữ liệu đầu vào và đầu ra khác nhau nhƣ mô tả trong ma trận DS trong các Bộ test trên. Chi phí thực thi của mỗi công việc trên các tài nguyên PC1, PC2, PC3 đƣợc xác định trên ma trận TP và ma trận PP nhƣ ở các Bộ test. Luận văn thử nghiệm với 30 lần chạy độc lập trong Bộ test 1 và tính toán chi phí trung bình thực thi luồng công việc cho ra kết quả so sánh nhƣ đồ thị Hình 5.2. Kết quả cho thấy: - Giải thuật PSO-Heuristic cho kết quả rất tốt so với giải thuật Random và Roundbin, tiết kiệm đƣợc một nửa chi phí so với hai giải thuật. - Thử nghiệm trên các tham số: trọng số quán tính w, hệ số gia tốc C1, C2, và cải tiến với hệ số co K chƣa nhận đƣợc sự ảnh hƣởng rõ rệt. VI. KẾT LUẬN Luận văn đã trình bày một giải thuật lập lịch heuristic dựa trên tối ƣu bầy đàn. Nó mô tả một heuristic để tối thiểu tổng chi phí thực thi của ứng dụng luồng công việc trong môi trƣờng điện toán đám mây. Bằng cách thay đổi chi phí truyền thông giữa các tài nguyên và chi phí thực thi tên các tài nguyên, heuristic tính toán chi phí thực thi trung bình. Khi so sánh kết quả thực nghiệm giữa giải thuật PSO và hai giải thuật Random, RoundRobin, luận văn nhận thấy giải thuật PSO đạt đƣợc mục đích làm giảm chi phí thực thi rất nhiều cho ứng dụng luồng công việc. Heuristic đạt đƣợc mục đích là tổng quát hóa, nó có thể đƣợc sử dụng cho bất kỳ số công việc và các tài nguyên theo khía cạnh bằng cách tăng số chiều của cá thể và số lƣợng tài nguyên. Tuy nhiên luận văn mới chỉ dừng lại ở vấn đề tối thiểu tổng chi phí thực thi. Đối với các bài toán thực tế, chúng ta gặp phải rất nhiều bài toán khác nhau trong lập lịch: tối thiểu tổng thời gian thực thi, tối thiểu tổng chi phí thực thi và thời gian thực thi, cân bằng tải trên tài nguyên đƣợc sử dụng khi gặp ràng buộc deadline của ứng dụng, đảm bảo chất lƣợng dịch vụ … Cho nên, chúng ta cần phải đi sâu hơn nữa để giải quyết các vấn đề trên trong môi trƣờng mô phỏng. Ngoài ra, để đảm bảo tính chính xác và có cơ sở khoa học thuyết phục hơn, hƣớng nghiên cứu tiếp theo của đề tài sẽ tiến hành so sánh giải thuật PSO-Heuristic và giải thuật Gen di truyền và tiến tới tìm kiếm một giải thuật tốt hơn giải thuật PSO-Heuristic. Với kết quả có đƣợc, luận văn hi vọng sẽ 12
đem lại một kết quả khả quan để có thể trở thành tiền đề nghiên cứu các giải thuật lập lịch tốt hơn, ứng dụng trong việc xử lý các bài toán luồng công việc của các công ty, doanh nghiệp sử dụng dịch vụ điện toán đám mây trong thực tiễn và cho các nhà cung cấp dịch vụ điện toán đám mây với mục đích giảm chi phí cho các dịch vụ mà khách hàng của họ sử dụng. Điện toán đám mây đƣa ra nhiều thách thức cho các nhà phát triển hệ thống và ứng dụng, các kỹ sƣ, các nhà quản trị hệ thống và các nhà cung cấp dịch vụ. Một trong số những thách thức này là việc quản lý và lập lịch cho các ứng dụng luồng công việc chuyên sâu về dữ liệu (xử lý các bài toán có dữ liệu lƣu trữ lớn) trên đám mây. Những thách thức này đồng thời cũng là các hƣớng nghiên cứu đặt ra cho các nhà khoa học . Một trong số những thách thức này gồm có: Lập lịch ứng dụng dựa trên tính an toàn, bảo mật và tin cậy: mô hình điện toán đám mây hƣớng vào sử dụng các dịch vụ và hạ tầng của bên thứ ba để lƣu trữ các dữ liệu quan trọng và thực thi các hoạt động quan trọng. Trong ngữ cảnh này, sự tin tƣởng đối với các nhà cung cấp dịch vụ là cơ sở để đảm bảo mức độ mong muốn riêng tƣ của các dữ liệu đƣợc lƣu trữ bên trong đám mây. Các câu hỏi về tính minh bạch đƣợc đặt ra: làm thế nào để lập lịch các công việc và dữ liệu trên các máy ảo đƣợc quản lý bởi nhiều nhà cung cấp dịch vụ điện toán đám mây để các luồng dữ liệu mang tính chất riêng tƣ, bảo mật bị hạn chế chỉ với các tài nguyên tin cậy thông qua một mạng tin cậy ?; làm thế nào để theo dõi đƣợc nguồn gốc dữ liệu và các công việc trong môi trƣờng ảo hóa?; làm thế nào để lập lịch các thành phần sử dụng các thông tin này để áp dụng bộ lọc và quét hạn chế vi phạm an ninh? Thỏa thuật cấp độ dịch vụ (Servive Level Agreements – SLA) và chất lƣợng dịch vụ: thỏa thuận cấp độ dịch vụ xác định các đặc điểm chức năng và phi chức năng của dịch vụ đám mây đƣợc thỏa thuận giữa nhà cung cấp và các khách hàng. Các thông số phổ biến trên một SLA bao gồm: mô hình chi phí, mô hình sử dụng, độ đo tài nguyên, thanh toán và giám sát, cấp độ bảo mật. Ví dụ, một nhà cung cấp dịch vụ điện toán đám mây có thể đảm bảo thời gian đáp ứng tối thiểu từ một máy ảo, không gian lƣu trữ tối thiểu, độ tin cậy của dữ liệu. Các vi phạm trên SLA có thể xảy ra khi nhà cung cấp dịch vụ không đáp ứng đƣợc các điều kiện đặt ra của khách hàng: không có đƣợc thời gian đáp ứng mong muốn, bị gián đoạn dịch vụ thƣờng xuyên …SLA cũng xác định rõ trách nhiệm và việc bồi thƣờng trong trƣờng hợp các thỏa thuật SLA bị vi phạm. Với các ràng buộc thay đổi theo yêu cầu của khách hàng, giải thuật lập lịch phải đáp ứng đƣợc thách thức đặt ra: làm thế nào giải thuật lập lịch có thể đảm bảo cho nhà cung cáp dịch vụ đáp ứng đƣợc chất lƣợng dịch vụ và ngăn chặn vấn đề vi phạm thỏa thuận? 13
References. Tiếng Anh [1] P.Mell and T.Grance, “The NIST definition of Cloud Computing” , National Institute of Standards and Technology, Information Technology Laboratory, Version 15,July 2009. [2] I.P.Sokolov, “Cloud Computing: Overview, Concepts and Business Deployment Scenarios”, Bachelor’s thesis, Vienna University of Economics and Business, Austria, 2009. [3] “The Business Process Model”, white paper, Sparx Systems, 2004. [4] J.Kennedy and R.Eberhart, “Particle Swarm Optimization”, in IEEE International Conference on Neural Networks, vol.4, 1995, pp.1942-1948 [5] Suraj Pandey, Linlin Wu, Siddeswara Guru, and Rajkumar Buyya, A Particle Swarm Optimization (PSO)-based Heuristic for Scheduling Workflow Applications in Cloud Computing Environments, Proceedings of the 24th IEEE International Conference on Advanced Information Networking and Applications (AINA 2010), Perth, Australia, April 20-23, 2010. - Best Paper Award. [6] Suraj Pandey, Rajkumar Buyya. Scheduling and Management Techniques for Data-Intensive Application Workflows, Data Intensive Distributed Computing: Challenges and Solutions for Large-scale Information Management, T. Kosar (ed), IGI Global, USA, 2009. (in press, accepted on July 24, 2009)search,177(3):1930–1947,March2007. [7] Suraj Pandey, Kapil Kumar Gupta, Adam Barker and Rajkumar Buyya, Minimizing Execution Cost when using Globally Distributed Cloud Services, Proceedings of the 24th IEEE International Conference on Advanced Information Networking and Applications (AINA 2010), Perth, Australia, April 20-23, 2010. [8] Ajkumar Buyya, Suraj Pandey, Christian Vecchiola, Cloudbus Toolkit for Market-Oriented Cloud Computing, Proceeding of the 1st International Conference on Cloud Computing (CloudCom 2009, Springer, Germany), Beijing, China, December 1-4, 2009ence,17(9):1197–1214,2005. [9] Rodrigo N. Calheiros, Rajiv Ranjan, Anton Beloglazov, Cesar A. F. De Rose, and Rajkumar Buyya, CloudSim: A Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms, Software: Practice and Experience (SPE), Volume 41, Number 1, Pages: 23-50, ISSN: 0038-0644, Wiley Press, New York, USA, January, 2011. (Preferred reference for CloudSim) [10] Rajkumar Buyya, Rajiv Ranjan and Rodrigo N. Calheiros, Modeling and Simulation of Scalable Cloud Computing Environments and the CloudSim Toolkit: Challenges and Opportunities, Proceedings of the 7th High Performance Computing and Simulation Conference (HPCS 2009, ISBN: 978-1-4244-4907-1, IEEE Press, New York, USA), Leipzig, Germany, June 21-24, 2009. 14
[11] I-Ling Lin, “Particle Swarm Optimization for solving constraint satisfaction problem”, Thesis, Master of science in the school of Interactive Arts and Technology, Simon Fraser University, 2002 [12] Zhang Liping, Yu Huan-Jun, Hu Shang-xu, “Optimal choice of parameters for particle swarm optimization”, Journal of Zhejiang University SCIENCE ISSN 1009-3095. [13] Ravneet Kaur Chawla, “Designing a business application for workflows in Cloud Computing”, Thesis, Master of Engineering in Software Engineering, Thapar University. [14] Marco Dorigo, Vittorio Maniezzo, and Alberto Colorni. The ant system: an autocatalytic optimizing process. Technical Report No. 91-016 Revised, Department of Electronic Information, Politecnico di Milano, Politecnico di Milano, Italy, 1991. 15