Nghiên cứu mô hình tính toán song song trên kiến trúc máy tính đa nhân tích hợp (Many Integrated Core) và ứng dụng

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (6.37 MB, 26 trang )

Trang 1<div class="page_container" data-page="1">

HỌC VIỆN CƠNG NGHỆ BƯU CHÍNH VIỄN THÔNG

NGUYEN HÙNG PHÚC

(MANY INTEGRATED CORE) VÀ UNG DỤNG CHUYEN NGANH : KHOA HOC MAY TÍNH

MA SO: 60.48.01.01

TOM TAT LUAN VAN THAC SI

HA NOI - 2016

</div>Trang 2<div class="page_container" data-page="2">

Luận văn được hồn thành tại:

HỌC VIEN CƠNG NGHỆ BƯU CHÍNH VIÊN THONG

Người hướng dẫn khoa học: TS. HOÀNG LÊ MINH

Phản biện 1: PGS.TS Nguyễn Hải Châu

Phản biện 2: TS. Tạ Quang Hùng

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: I0 giờ 00 ngày 20 tháng 08 năm 2016

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

</div>Trang 3<div class="page_container" data-page="3">

MO DAU

Ngày nay, với sự bùng nổ của công nghệ thông tin và internet, nhu cầu tinh toán

trong lĩnh vực khoa học ngày càng trở nên cấp bách và đối mặt với nhiều thách thức, do đó

có nhiều giải pháp lần lượt được đưa ra nhằm tăng khả năng xử lý tính tốn và rút ngắn tối đa thời gian tính tốn. 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ệ da lõi, nhiều lõi, đa nhân với cơ chế xử lý song song và phân tán trong các máy tính hiệu năng cao nhằm tăng hiệu năng và chi phí năng lượng hợp lý. Các bộ xử lý tiên tiến, các hệ thống tính tốn tích hợp, phức tạp có tốc độ cao đều áp dụng kỹ thuật xử lý song song, coi đây như là một kỹ thuật tiên tiến, khả thi, có tinh mở cao.

Năm 1965, nhà đồng sáng lập hãng Intel là Gordon Moore đăng một bài viết trong đó dự báo số bóng bán dẫn transistor trên mạch tích hợp sẽ tăng gấp đôi mỗi năm (về sau điều chỉnh lại là "tăng gấp đôi theo chu kỳ 18 tháng"), sau này được biết đến là “định luật More”. Tuy nhiên với sự phát triển như vũ bão của công nghệ, và sự hạn chế của kỹ thuật, lượng transistor không cịn tăng được nữa, tính quy mơ của định luật More khơng cịn. Đã đến lúc cần một giải pháp khác cho sự phát triển của cơng nghệ điện tốn. Và tính tốn song song sẽ có thé đem đến một nền tang phát triển mới.

Như chúng ta đã biết tính tốn song song khơng phải là một khái niệm mới trong thời

đại ngày nay. Tính tốn song song ra đời dé giải quyết các bài toán thực hiện tuần tự nhưng

có khả năng chia nhỏ thành nhiều tác vụ song song dé tăng hiệu suất xử lý của bài tốn. Bằng cách ứng dụng mơ hình tính tốn song song, hiện nay trên thế giới đã ra đời rất nhiều

siêu máy tính nhằm phục vụ cho nhu cầu tính tốn lớn. Chính vi vậy tại hội thảo siêu điện toán Quốc tế 2011 Intel đã đưa ra kiến trúc máy tính đa nhân tích hợp (Many Integrated Core — MIC), có thé xem MIC như một xử lý phối hợp (Co-processor) và lợi thé của nó là có thê dùng chung trình biên dịch, chung các cơng cụ, chung ứng dụng của các CPU Intel và thay vi dé xử lý các ống lệnh đồ hoa, MIC tập trung vào tính tốn thơng thường dựa trên điện tốn song song (Parallel Computing). Đây là một kiến trúc lớn được Intel định hướng đến phân khúc điện toán siêu cấp, chun làm các tính tốn quy mơ lớn như thiên văn học, dự báo thời tiết, vật ly lượng tử, khai thác dầu khí, khám phá phân tử, chuẩn đốn y khoa, các dịch vụ trên điện toán đám mây hay phá mã mật khẩu...

Minh họa một cách đơn giản, tính tốn truyền thống giống như việc một người đọc

bài văn theo kiêu tn tự từ dau đên ci, cịn tính tốn song song thi giơng như tach bai văn

</div>Trang 4<div class="page_container" data-page="4">

đó thành các phan và cho nhiều người khác nhau cùng đọc một lúc dé có kết quả nhanh hơn.

Tính tốn song song mang lại một nền tảng mới cho sự phát triển của công nghệ xử lý. Đây là một hướng đi mới, đúng đắn và hiệu quả cho cơng nghệ điện tốn trong tương lai. Thay

được lợi ích to lớn đó, em chọn đề tài “Nghiên cứu mơ hình tính todn song song trên kiến

trúc may tính da nhân tích hợp (Many Integrated Core) và ứng dụng”.

Mục đích nghiên cứu chính của luận văn là phần nào thể hiện được những kiến thức cơ bản về tính tốn song song, ứng dụng của tính tốn song song trên kiến trúc máy tính đa nhân tích hợp dé giải bài toán phá mã mật khẩu. Từ đó ứng dụng vào các ngành khoa học khác để thực hiện những tính tốn nhanh hơn, việc xử lý song song sẽ giải quyết được những bài toán lớn hơn, phức tạp hơn trong thực tế.

Luận văn gồm 3 chương chính với các nội dung sau:

Chương 1: Lý thuyết về tính tốn song song và tính tốn hiệu năng cao. Nội dung của chương này trình bày kiến thức hiểu biết về tính tốn hiệu năng cao, tính tốn

song song, các mơ hình lập trình song song và thuật toán song song.

Chương 2: Nghiên cứu về kiến trúc MIC. Chương này tập trung tìm hiểu kiến trúc

máy tính đa nhân tích hợp, tìm hiểu thư viện và cơng cụ phát triển các ứng dụng song song cho hệ thống tính tốn hiệu năng cao trên nền tảng đa nhân tích hợp.

Chương 3: Giải bài tốn phá mật khẩu được mã hóa theo chuỗi MD5 trên hệ thống HPC. Chương này sử dụng thư viện lập trình song song MPI trên hệ thống MIC ứng dụng giải bài toán phá mật khẩu được mã hóa theo chuỗi MD5 (có khơng quá 6 ký tự).

</div>Trang 5<div class="page_container" data-page="5">

CHƯƠNG 1: LÝ THUYET VE TÍNH TỐN SONG SONG VA TÍNH

TOAN HIEU NANG CAO

1.1. Tổng quan về tinh toán hiệu năng cao

1.1.1. Giới thiệu về tính tốn hiệu năng cao

Tính tốn hiệu năng cao (High Performance Computing - HPC) là một trong những

lĩnh vực nghiên cứu dang được quan tâm hiện nay trên thế giới. Hiểu một cách đơn giản, tính tốn hiệu năng cao cho phép tận dụng tối đa tài nguyên tính tốn và lưu trữ để tạo ra một hệ thống đáp ứng yêu cầu ứng dụng trong thời gian nhanh hơn, với chỉ phí thấp hơn.

Phương thức tính tốn truyền thống được thực hiện dưới hình thức một ứng dụng

chạy trên một máy chủ hay một workstation. Tất cả các lệnh của một ứng dụng đều được xử lý trên hệ thong cục bộ. Trong khi đó, tính tốn hiệu năng cao lại sử dung sức mạnh xử lý của nhiều hệ thống dé xử lý các lệnh của một ứng dụng. Việc phân phối khối lượng xử lý trên nhiều hệ thống sẽ giúp tăng tốc độ xử lý dữ liệu.

1.12. Nhu cầu xây dựng hệ thống tính tốn hiệu năng cao

Nhu cầu ứng dụng Cơng nghệ thơng tin trong các hoạt động nghiên cứu khoa học và công nghệ, quản lý kinh tế xã hội ngày càng cao, địi hỏi phải giải quyết nhiều các bài tốn xử lý lớn với khối lượng tính tốn khơng 16 đến mức các máy tính tuần tự (Sequential Computer) khơng đủ mạnh dé có thé đưa ra một phương án lời giải trong giới hạn thời gian cho phép. Ý tưởng xây dựng các máy tính song song tuy đã xuất hiện từ lâu trong các nghiên cứu, nhưng mới chỉ trở thành hiện thực trong vòng vài chục năm gần đây.

1.1.3. Hệ thống HPC tại Viện Công nghệ phan mém và Nội dung số

Bang 1.1: Tốc độ tính tốn của hệ thống HPC tại viện CNPM & NDS [6]

</div>Trang 6<div class="page_container" data-page="6">

1.2. Lý thuyết về tính tốn song song

1.2.1. Khái niệm tính tốn song song

Tính tốn song song hay xử lý song song (Parallel Computing/Parallel Processing) là

quá trình xử lý thơng tin trong đó nhiều đơn vị dữ liệu được kích hoạt xử lý đồng thời và

cùng tham gia giải quyết một bài tốn.

Phân biệt giữa tính tốn song song và tính tốn tuần tự:

Bảng 1.2: Phân biệt tính tốn tuần tự và song song

Tính tốn tuần tự Tính tốn song song

Mỗi thời điểm chỉ thực hiện được một —_ | Mỗi thời điểm có thê thực hiện được phép toán nhiều phép toán

Thời gian thực hiện phép toán chậm Thời gian thực hiện phép toán nhanh

1.2.2. Một số thuật ngữ dung trong tính toan song song

Lập trình song song (Parallel Programming) là việc lập trình sử dụng một ngơn ngữ

có hỗ trợ xử lý song song các lệnh trong một chương trình.

Máy tính song song (Parallel Computer) là một máy tính có nhiều bộ xử lý (multiple-processor) có khả năng phối hop với nhau dé giải quyết các bai tốn.

Siêu máy tính (Supercomputer) là một máy tính đa năng có khả năng giải các bài

tốn đơn với tốc độ tính tốn cao (cỡ hàng nghìn tỉ phép tính trong một giây). So với các máy tính được chế tạo cùng thời thì siêu máy tính có tốc độ xử lý lớn hơn hàng nghìn lần.

Các siêu máy tính hiện đại là các máy tính song song. Một vài siêu máy tính có số lượng ít bộ xử lý nhưng rất mạnh, đa số siêu máy tính có số lượng bộ xử lý rất lớn.

Thông lượng (Throughput) của một thiết bị là lưu lượng đữ liệu được truyền tải qua thiết bị trong một đơn vi thời gian. Có nhiều cách để cải tiến thơng lượng của một thiết bị như: tăng tốc độ, tăng số thao tác tại một thời điểm...

Song song hóa dữ liệu (Data Parallelism) là việc sử dụng nhiều bộ chức năng (functional units) để xử lý cùng một thao tác đồng thời cho các phần tử của một tập dữ liệu.

Song song điều khiển (Control Parallelism) là cơ chế trong đó nhiều thao tác khác nhau tác động lên nhiều đơn vị dit liệu khác nhau một cách đồng thời.

Dây chuyền (Pipelining) là cơ chế chia công việc thành nhiều chặng nối tiếp nhau,

mỗi chặng được thực hiện bởi một bộ phận khác nhau. Đầu ra của bộ phận này là đầu vào

của bộ phận tiếp theo.

</div>Trang 7<div class="page_container" data-page="7">

Tăng tốc (Speedup): Tăng tốc của thuật toán song song là tỷ số giữa thời gian thực

hiện trong tình huống xấu nhất của thuật toán tuần tự tốt nhất và thời gian thực thiện cùng

cơng việc đó của thuật tốn song song.

Hiệu qua (Efficiency) của thuật toán song song được tinh bang Tăng tốc/Số bộ xử ly tham gia tính tốn.

1.2.3. Tại sao phải tính tố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 tốn rất lớn. Trong số đó có những bài tốn mà kết qua chỉ có ý nghĩa nêu được hồn thành

trong khoảng thời gian cho phép. Ví dụ như các tính tốn trong thời gian thực, mơ phỏng

các hoạt động ở mức lượng tử, tính qui đạo chuyền động của vật thé trong không gian, xử ly ngôn ngữ tự nhiên, dự báo thời tiết... Hầu hết những bài tốn này, những máy tính xử lý tuần tự khơng đáp ứng được yêu cầu, do đó cần phải có những hệ thống máy tính thật mạnh

mới đáp ứng được những yêu cầu của thực tế.

Mặc dù tốc độ xử lý của các bộ xử lý tăng nhiều trong những năm qua, nhưng do giới hạn về vật lý nên khả năng tính tốn của chúng khơng thê tăng mãi được. Điều này dẫn tới

là muốn tăng được khả năng tính tốn của các hệ thống máy tính thì đích cuối cùng là phải

khai thác được khả năng xử lý song song của chúng. Ngày càng xuất hiện nhiều bài toán mà những hệ thống đơn một bộ xử lý không đáp ứng được yêu cau xử lý về thời gian, do đó địi hỏi phải sử dụng những hệ thống đa bộ xử lý và đòi hỏi phải xử lý song song.

1.2.4. Tìm hiểu các kiến trúc máy tính song song

1.2.4.1. Tổng quan về kiến trúc máy tính

Máy tính được xây dựng từ các khối cơ sở:

- Bộ nhớ: Đề lưu trữ dữ liệu

- Các đơn vị logic và số học: Thực hiện các phép toán, được ký hiệu là ALU

- Các phan tử xử lý: Bộ điều khiển (CU — Control Unit) và các thiết bị vào/ra dit liệu. - Các Bus trao đôi dit liệu.

1.2.4.2. Phan loại máy tính song song

Sự phân loại máy tinh song song được dựa trên kiến trúc bộ nhớ của chúng. Các zmáy

tính song song có bộ nhớ chia sẻ (Shared Memory) có nhiều bộ xử lý cùng được truy nhập đến một vùng nhớ tổng thé dùng chung. Tất cả các sự thay đổi nội dung bộ nhớ do một bộ

xử lý tạo ra sẽ được nhận biết bởi các bộ xử lý khác. Người lập trình khơng phải quan tâm

đên việc phân chia dir liệu.

</div>Trang 8<div class="page_container" data-page="8">

Còn lại, các máy tính song song có bộ nhớ phân tán (Distribute Memory) cũng có

nhiều bộ xử lý nhưng với mỗi bộ xử lý chỉ có thé truy cap đến bộ nhớ cục bộ của nó, khơng

có một vùng nhớ dùng chung nào cho tât cả các bộ xử lý.

Interconnection Network

Hình 1.2: Máy tính song song có bộ nhớ phân tan [14]

1.2.4.3. Các mơ hình kiến trúc máy tính song song

Mơ hình kiến trúc máy tính song song theo Flynn (1996) dựa trên hai yếu tố cơ bản:

Dòng lệnh (instruction stream) va dịng dữ liệu (data stream).

Bảng 1.3: Mơ hình máy tính song song theo Flynn

(instruction stream) (data stream) *

Trạng thái đơn Trang thái đơn

(single) (single) Data)

Trang thai don Trang thai da

(single) (multiple) Data)

Trang thai da Trang thai don

(multiple) (single) Data)

Trang thai da Trang thai da MIMD (Multiple Instruction

(multiple) (multiple) Multiple Data)

</div>Trang 9<div class="page_container" data-page="9">

Hình 1.3: Mơ hình kiến trúc máy SISD [13]

Máy tính đơn dịng lệnh, đa luồng dữ liệu

May tinh SIMD đóng vai trị quan trọng trong xử lý song song. Chúng có thé thao tác

trên các dữ liệu biểu diễn đưới dạng vector hay ma trận (trên thực tế các dữ liệu về thời tiết

hoặc các nghiên cứu về bức xạ gây ung thư thường được biéu diễn dưới dạng vector). Máy tính SIMD có thể xử lý các bài toán này trong một khoảng thời gian ngắn hơn so với các mơ hình khác. Trong trường hợp kích thước của vector đúng bằng số lượng bộ vi xử lý thì hiệu

suất của máy SIMD sẽ đạt tối ưu. Trong trường hợp mà số bộ vi xử lý và kích thước vector khác nhau, thì tốc độ xử lý của máy tính SIMD cũng tốt hơn nhiều so với máy tính tuần tự.

Hình 1.4: Mơ hình kiến trúc may SIMD [13]

Máy tính đa dịng lệnh, đơn luồng dữ liệu

MISD là một kiến trúc song song mà trong đó tại mỗi thời điểm các bộ xử lý thực

hiện các thao tác khác nhau trên cùng một dữ liệu (ngược với máy tính loại SIMD). Máy

tính MISD có ý nghĩa về mặt lý thuyết nhiều hơn thực tế; cho tới thời điểm này, kiến trúc MISD vẫn chưa có một phiên bản chính thức nào được xây dựng hay nghiên cứu phát triển.

</div>Trang 10<div class="page_container" data-page="10">

Data Stream

Instruction Stream

Hình 1.5: Mơ hình kiến trúc máy MISD [13]

Máy tính da dịng lệnh, da luồng dữ liệu

Máy tính MIMD cịn được gọi là máy tính đa bộ xử ly (multiprocessors) trong đó các

bộ xử lý có các chức năng độc lập nhau. Tại bắt cứ thời điểm nào, các bộ xử lý của máy tính

MIMD có thé thực hiện các lệnh khác nhau trên các di liệu khác nhau một cách không đồng bộ. Đây là loại kiến trúc phức tạp nhất, nhưng nó là mơ hình hỗ trợ xử lý song song cao nhất và đã có nhiều máy tính được thiết kế theo kiến trúc này.

Unit n (Program, Data)

Hình 1.6: Mơ hình kiến trúc may MIMD [13]

1.3. Cac mơ hình lập trình tính tốn song song

1.3.1. Tìm hiểu về lập trình song song

Lập trình tính tốn song song tập trung vào việc phân chia bài tố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.

</div>Trang 11<div class="page_container" data-page="11">

1.3.2. Một số mơ hình lập trình tính tốn song song

1.3.2.1. Mơ hình chia sẻ bộ nhớ

Mơ hình này được thiết kế cho máy tính xử lý song song, các tác vụ chia sẻ không

gian dia chỉ dung chung, được doc/ghi một cách không đồng bộ.

1.3.2.2. Mô hình đa luồng

Trong mơ hình đa luồng (Threads), một bài tốn có thé có rất nhiều luồng xử lý.

1.3.2.3. Mơ hình truyền thơng điệp (Message Passing)

Trong máy tính song song cung cấp kỹ thuật truyền thông điệp dé trao đổi giữa các

tác. Hai tác vụ nằm trên hai máy khác nhau có thể trao đổi với nhau băng kỹ thuật truyền

</div>Trang 12<div class="page_container" data-page="12">

thông điệp trên mạng kết nối. Các thơng điệp có thể là các lệnh, dữ liệu, tín hiệu đồng bộ

hay ngắt.

Hình 1.9: Mơ hình truyền thơng giữa các tác vụ trên hai máy tính [12]

1.3.2.4. Mơ hình song song dt liệu

Trong mơ hình song song dữ liệu (Data Parallel), hầu hết các công việc song song

đều tập trung thực hiện các phép toán trên một tập dữ liệu. Tập dữ liệu này thường được tô chức trong một cấu trúc dữ liệu thông dụng như mảng hoặc khối. Một tập tác vụ sẽ làm việc trên cùng cấu trúc dữ liệu nhưng mỗi tác vụ sẽ làm việc trên một phần dir liệu khác nhau với

cùng phép tốn.

task 1 task 2 ven task n

Hình 1.10: Mơ hình song song đữ liệu [12]

1.3.2.5. Mơ hình hướng đối tượng

1.3.2.6. M6 hình logic

1.4. Tìm hiểu thuật tốn song song

1.4.1. Nguyên lý thiết kế thuật toán song song

</div>Trang 13<div class="page_container" data-page="13">

Khi thiết kế giải thuật song song, cần tuân thủ 5 nguyên lý sau:

- Các nguyên lý lập lịch: Mục đích là giảm tối thiểu các bộ xử lý sử dụng trong giải

thuật sao cho thời gian tính tốn là khơng tăng (xét theo khía cạnh độ phức tạp).

- Nguyên lý hình ống: Nguyên lý này được áp dụng khi bài toán xuất hiện một dãy

các thao tác {Th, Tạ, ..., Tạ}, trong đó T;+ 1 thực hiện sau khi T; kết thúc.

- Nguyên lý chia để trị: Chia bài toán thành những phần nhỏ hơn tương đối độc lập với nhau và giải quyết chúng một cách song song.

- Nguyên lý đô thị phụ thuộc dé liệu: Phân tích mỗi quan hệ dé liệu trong tính tốn

dé xây dựng đồ thị phụ thuộc dit liệu và dua vào đó dé xây dựng giải thuật song song.

- Nguyên ly diéu kiện ganh đua: Nêu hai tiễn trình cùng muốn truy cập vào cùng một mục dé liệu chia sẻ thì chúng phải tương tranh với nhau, nghĩa là chúng có thé cản trở lẫn

1.4.2. Phân tích, danh gia thuật tốn song song

Độ phức tạp tính tốn của thuật tốn song song khơng chỉ phụ thuộc vào kích cỡ của

dữ liệu đầu vào mà còn phụ thuộc vào kiến trúc máy tính song song và số lượng các bộ xử

lý được phép sử dụng trong hệ thống.

Độ phức tạp thời gian là thước đo quan trọng nhất đánh giá mức độ hiệu quả của

thuật toán song song.

1.4.3. Một số chiến lược song song hóa phổ bién 1.4.3.1. Song song hóa kết qua

1.4.3.2. Song song hóa đại diện

1.4.3.3. Song song hóa chuyên biệt

1.5. Kết luận chương 1

Dé phát huy khả năng của những hệ thống máy tính hỗ trợ tính tốn song song cần

phải xây dựng mơ hình lập trình song song và thuật toán song song phù hợp. Nhờ các giải

thuật song song hợp lý đã làm thay đổi quan niệm về khả năng giải được trong thực tế của những bài toán khác nhau. Nhiều thuật toán trước đây khơng thể chấp nhận vì khối lượng

tính tốn q lớn thì ngày nay lại hồn tồn khả thi.

</div>