11/7/12
Nội dung
Tính toán song song và phân tán PGS.TS. Trần Văn Lăng tvlang@vast-‐hcm.ac.vn lang@lhu.edu.vn
Tài liệu: Introduc7on to Parallel Compu7ng Blaise Barney, Lawrence Livermore NaGonal Laboratory hIps://compuGng.llnl.gov/tutorials/parallel_comp/
1
2
1. Tổng quan 2. Khái niệm và thuật ngữ 3. Kiến trúc bộ nhớ của máy Znh song song 4. Mô hình lập trình song song 5. Thiết kế chương trình song song 6. Ví dụ
1.1 Tính toán song song là gì
• Theo truyền thống, phần mềm được viết theo
1. Tổng quan
lệnh rời rạc.
cách Znh toán tuần tự: – Được chạy trên một máy Znh đơn có một CPU; – Một bài toán được chia ra thành một chuỗi các câu
– Những câu lệnh này được thi hành sau câu lệnh khác. – Vào một thời điểm chỉ có một câu lệnh thực thi.
3
4
1. Tính toán song song là gì 2. Tại sao phải dùng Znh toán song song
1
11/7/12
Ví dụ Znh Gền lương cho nhiều người
• Trong một ngữ cảnh đơn giản, Znh toán song song
(Parallel CompuGng) là việc sử dụng đồng thời nhiều nguồn tài nguyên Znh toán để giải quyết một vấn đề: – Được chạy bằng cách sử dụng nhiều CPU. – Một vấn đề có thể chia ra thành nhiều phần rời rạc có thể
giải quyết một cách đồng thời.
– Mỗi phần được Gếp tục phân chia thành một chuỗi các câu
lệnh.
– Những câu lệnh của mỗi phần được thi hành một cách
đồng thời trên các CPU khác nhau.
5
6
Tiền lương mỗi người được 1 CPU Znh
– Một máy Znh duy nhất với nhiều bộ xử lý; – Một số tùy ý máy Znh được kết nối qua mạng; – Tổ hợp cả hai loại trên.
7
8
• Nguồn tài nguyên Znh toán có thể là:
2
11/7/12
– Được phân chia thành các phần công việc rời rạc mà có
thể giải quyết một cách đồng thời;
– Thực hiện nhiều câu lệnh chương trình vào bất kỳ thời
điểm nào;
• Bái toán Znh toán có thể: • Tính toán song song là một sự Gến hóa của Znh
gian nhưng vẫn trong cùng một chuỗi.
– Với nhiều nguồn tài nguyên Znh toán, bài toán được giải quyết ít thời gian so với chỉ một nguồn tài nguyên Znh toán.
9
10
toán tuần tự nhằm cố gắng mô phỏng những vấn đề đặt ra trong thế giới tự nhiên chứa đựng: – Nhiều sự phức tạp – Các sự kiện liên quan với nhau xãy ra cùng một thời
The Real World is Massively Parallel !
Ví dụ
11
12
• Hình thành giải thiên hà (Galaxy formaGon) • Chuyển động của hành Gnh • Vấn đề thời Gết và đại dương
3
11/7/12
Sử dụng Znh toán song song
• Về mặt lịch sử, Znh toán song song được coi là
• Giao thông đô thị • Chế tạo máy bay • Những mãng băng trôi
…
13
14
“Znh toán cao cấp” (the high end of compuGng), đã được sử dụng để mô hình hóa các vấn đề khó khăn trong nhiều lĩnh vực khoa học và kỹ thuật: – Khí quyển, trái đất, môi trường – Vật lý: hạt nhân, hạt, áp lực cao, nhiệt hạch, lượng tử,
Sử dụng Znh toán song song
• Ngày nay, những ứng dụng thương mại cũng đòi hỏi công suất lớn của máy Znh.
– Khoa học sinh học, công nghệ sinh học, di truyền học. – Hóa học, khoa học phân tử – Địa chất, địa chấn học – Cơ ký: từ tay chân giả cho đến tàu vũ trụ – Điện, thiết kế vi mạch, vi điện tử – Khoa học máy Znh, toán học
• Những ứng dụng này đòi hỏi xử lý một khối lượng
15
16
lớn dữ liệu; chẳng hạn: – Cơ sở dữ liệu, khai khoáng dữ liệu – Khai thác dầu – Công cụ (cid:156)m kiếm, dịch vụ kinh doanh dựa trên web
4
11/7/12
1.2 Tại sao phải dùng Znh toán song song
– Máy Znh song song có thể xây dựng trên các thành
phần giá rẻ
– Rút ngắn thời gian là sự Gết kiệm đáng kể.
– Chẩn đoán hình ảnh y tế (Medical image diagnosis) – Thiết kế dược phẩm – Quản lý các tập đoàn quốc gia, đa quốc gia – Mô hình tài chính và kinh tế – Đồ họa nâng cao, thự tại ảo, công nghiệp điện ảnh – Video mạng (Networked video) và công nghệ đa
phương Gện
– Môi trường làm việc cộng tác
17
18
• Tiết kiệm thời gian và/hoặc 7ền bạc:
Giải những bài toán lớn
– Những bài toán thách thức lớn (Grand Challenge) được đặt ra đòi hỏi nguồn tài nguyên Znh toán lên đến cả Peta phép Znh trong một giây
• Chẳng hạn:
– Động cơ (cid:156)m kiếm để xử lý hàng triệu phiên giao dịch
trong 1 giây.
19
20
• Nhiều vấn đề quá lớn và/hoặc quá phức tạp; nên sẽ không thực tế hoặc không thể giải quyết được trên một máy Znh đơn, đặc biệt khi bị giới hạn về bộ nhớ.
5
11/7/12
Các thách thức (Grand Challenge) (en.wikipedia.org/wiki/Grand_Challenge)
• Các Znh toán tượng trưng (Symbolic) như:
• Động lực học chất lỏng và chất khí • Tính toán cấu trúc điện tử cho việc thiết kế vật liệu mới
– speech recogniGon – computer vision – natural language understanding – simulaGon of complex systems
• Động lực học Plasma ứng dụng công nghệ nhiệt hạch và an toàn hiệu quả trong quân sự
21
22
• Những Znh toán về sự hiểu biết bản chất cơ bản của vật chất
• Cung cấp đồng thời: Một nguồn tài nguyên Znh
Sử dụng nguồn tài nguyên không địa phương (non-‐local resources) • Dùng nguồn tài nguyên Znh toán trên một mạng diện rộng, hoặc ngay cả trên mạng Internet khi nguồn tài nguyên tại chỗ trở nên cạn kiệt.
việc có thể được làm một cách đồng thời. Chẳng hạn, hệ thống Access Grid (www.accessgrid.org) cung cấp một mạng lưới cộng tác toàn cầu, ở đó mọi người có thể gặp nhau và chỉ đạo công việc một cách sát thực.
23
24
toán đơn chỉ có thể làm một công việc ở vào một thời điểm. – Nhưng với nhiều nguồn tài nguyên Znh toán, nhiều
6
11/7/12
SETi@home
– SETI@home (seGathome.berkeley.edu) sử dụng 2,9 triệu máy Znh kết nối Internet ở khắp các nước. – Folding@home (folding.stanford.edu) sử dụng máy
• Chẳng hạn:
Znh trên 450.000 campus.
25
26
• SETI (Search The Extraterestrial Intelleigence -‐ Tìm kiếm trí tuệ ngoài Trái đất): là một lĩnh vực khoa học với mục Gêu là để phát hiện cuộc sống thông minh ngoài Trái đất .
Folding@home
– Đài phát thanh SETI, sử dụng kính viễn vọng radio để nghe các Zn hiệu vô tuyến băng thông hẹp từ không gian. Tín hiệu xảy ra một cách tự nhiên, sẽ cung cấp bằng chứng của công nghệ ngoài Trái đất.
• Hệ thống bao gồm: • Mục 7êu: Tạo môi trường Znh toán phân tán
– Làm đài phát thanh SETI bằng cách sử dụng một siêu
máy Znh ảo bao gồm số lượng lớn các máy Znh kết nối Internet (5/1999).
27
28
nhằm (cid:156)m hiểu về sự kết xoắn và các đột biến của protein, cũng như các bệnh tật gây ra bởi các biến chứng này. Xuất phát từ Phòng thí nghiệm Pande, Standford University.
7
11/7/12
• Quá trình kết xoắn của protein, mặc dù đó là nền
• Protein là những "chú ngựa thồ" trong sinh học, và là những cỗ máy siêu nhỏ. tảng căn bản quan trọng trong sinh học, vẫn còn là điều mơ hồ và vẫn chưa có câu giải thích đích đáng
29
30
• Trước khi protein có thể lãnh những trách nhiệm cực kỳ quan trọng, chúng tự kết xoắn lại với nhau -‐ hay còn gọi là "fold".
Giới hạn của Znh toán tuần tự
• Giới hạn tuyệt đối bởi tốc độ ánh sáng là 30 cm/nanosecond;
và của dây đồng là 9 cm/nanosecond
• Cả những lý do vật lý cũng như thực tế đặt ra việc cần phải xây dựng những máy Znh nhanh hơn máy Znh tuần tự, cụ thể: – Tốc độ truyền: Phụ thuộc một cách trực Gếp vào việc dữ liệu di chuyển thông qua các phần cứng. Cụ thể
31
32
• Hơn nữa, khi sự kết xoắn của proteins bị sai lệch (còn gọi là "misfold"), chúng có thể tạo ra những hậu quả hết sức nghiêm trọng như: – Alzheimer: chứng bệnh mất trí – Mad Cow: bệnh bò điên – Parkinson: bệnh phân liệt – Và nhiều bệnh ung thư khác
8
11/7/12
– Giới hạn trong việc thu nhỏ: Công nghệ vi xử lý giúp
– Kiến trúc máy Znh hiện đại cho phép có thể nâng cao
năng lực xử lý, cụ thể có các kiến trúc:
tăng số transitor đặt trên một con chip. Tuy nhiên, khả năng đạt được cũng còn gặp nhiều khó khăn.
• Nhiều bộ phận thực thi (MulGple execuGon units) • Kiến trúc lệnh đường ống (Pipelined instrucGons): cho phép nạp một lệnh mới trong khi CPU đang xử lý lệnh trước đó.
• MulG-‐core
– Giới hạn về kinh tế: Một bộ xử lý đơn mạnh gía thành cao hơn nhiều so với việc sử dụng nhiều bộ xử lý với giá vừa phải.
33
34
Một cách tổng quát
35
36
• Ai và những gì đã làm về Tính toán song song
9
11/7/12
Sự phát triển
Ngay cả đơn vị đo Znh toán
• Với sự phát triển trong hơn 20 năm qua cho thấy nhờ sự nhanh hơn của mạng lưới, hệ thống phân tán và kiến trúc máy Znh đa xử lý, cho thấy sự song song là tương lai của máy Znh.
• Ngay trong cùng một thời điểm hiện tại, đã có
• 1 Yflop/s (YoIaFlop/s) = 1024 Flop/s • 1 Zflop/s (ZeIaFlop/s)= 1021 Flop/s • 1 Eflop/s (ExaFlop/s) = 1018 Flop/s • 1 Pflop/s (PetaFlop/s) = 1015 Flop/s • 1 Tflop/s (TetraFlop/s)= 1012 Flop/s • 1 Gflop/s (GigaFlop/s) = 109 Flop/s • 1 Mflop/s (MegaFlop/s) = 106 Flop/s • 1 Kflop/s (KiloFlop/s) = 103 Flop/s • 1 Flop/s = 1 FloaGng Point OperaGon per Second
37
38
những máy Znh nhanh hơn nhau gấp hơn cả 1000 lần.
Máy nhanh nhất (6/2012)
Máy nhanh nhất 6/2012
• Khả năng thực hiện khoảng 16.324.751.000.000.000.000 Flop/s
• Đặt tại Lawrence Livermore NaGonal Laboratory, Bộ Năng lượng, Hoa Kỳ
39
40
• Để thực hiện các nghiên cứu về Vật lý và Hóa học • Máy có 1.572.864 Core
10
11/7/12
Độ đo vật lý
Minh chứng về sự kết nối
– Được xác định bằng cách Znh số phép Znh cộng và
nhân được hoàn thành trong suốt một chu kỳ thời gian của máy.
• Sự phát triển mạng các máy Znh nối kết lại làm • Rpeak: là độ đo lý thuyết đỉnh điểm thay đổi bộ mặt của lĩnh vực Znh toán.
– Chẳng hạn, máy với 1.5 GHz có thể hoàn thành 4 phép Znh trong một cycle, thì hiệu suất lý thuyết là 6 GFlop/ s
• Từ tốc độ 10 Mbps, băng thông kết nối có thể vượt tốc độ Giga (Gigabit Ethernet, Infiniband, Myrinet, Quadric, v.v... )
41
42
• Rmax: là độ đo cực đại mà máy Znh có thể thực hiện được theo chuẩn LINPACK
Kiến trúc máy trong 10 năm qua
Thống kê theo kiến trúc
– Trong số 500 máy nhanh nhất thế giới, có 149 hệ thống
dạng cluster (hệ thống nhóm máy mạng).
– Trong số 149 hệ này có 23 máy tự làm (self-‐made).
• Theo số liệu 6/2003 (hIp://www.top500.org)
43
44
• Đến 6/2012
11
11/7/12
Theo hệ điều hành 10 năm qua
Theo hệ điều hành (11/2011)
45
46
• 11/2011
• 6/2012
2. Khái niệm và thuật ngữ
1. Kiến trúc máy Znh Von Neumann 2. Phân loại kinh điển của Flynn 3. Một vài thuật ngữ song song tổng quát
47
48
