BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC

PHAN QUANG NHẬT

NGHIÊN CỨU LẬP TRÌNH SONG SONG
VÀ ỨNG DỤNG TRONG VIỆC TỔNG HỢP
THÔNG SỐ VẬN HÀNH LƯỚI ĐIỆN

LUẬN VĂN THẠC SĨ KHOA HỌC
KHOA HỌC MÁY TÍNH

Thừa Thiên Huế, 2016


BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC

PHAN QUANG NHẬT

NGHIÊN CỨU LẬP TRÌNH SONG SONG
VÀ ỨNG DỤNG TRONG VIỆC TỔNG HỢP
THÔNG SỐ VẬN HÀNH LƯỚI ĐIỆN
CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ: 60.48.01

LUẬN VĂN THẠC SĨ KHOA HỌC
ĐỊNH HƯỚNG ỨNG DỤNG
NGƯỜI HƯỚNG DẪN KHOA HỌC

phòng Điều Độ Công ty Điện Lực Thừa Thiên Huế đã hỗ trợ tôi trong thời gian qua.
Và cuối cùng, tôi xin cảm ơn ba mẹ và vợ tôi, những người đã luôn theo sát
động viên, giúp đỡ tôi để có thể hoàn thành tốt luận văn này.
Thừa Thiên Huế, ngày
-

tháng

năm 2016


MỤC LỤC
Trang


DANH MỤC CÁC BẢNG
Trang


DANH MỤC HÌNH ẢNH
Trang


ANH MỤC CÁC CHỮ VIẾT TẮT
ALU

Arithmetic Logic Unit (Đơn vị logic số học)

BCL



MIMD

Multiple Instruction Multiple Data (Đa lệnh đa dữ liệu)

MISD

Multiple Instruction Single Data (Đa lệnh đơn dữ liệu)

MPI

Message Passing Interface (Giao diện trao đổi thông điệp)

ODMS

Operational Data Management System
(Hệ thống quản lý dữ liệu thông số vận hành)

OPC

OLE of Process Control (OLE cho điều khiển quá trình)

PE

Parallel Execution (Thực hiện song song)

PRAM

Parallel Random Access Memory
(Bộ nhớ truy cập ngẫu nhiên song song)

MỞ ĐẦU

1. Tính cấp thiết của đề tài
Ngày nay, chúng ta đang sống trong thời đại bùng nổ thông tin. Thông tin
không chỉ tăng trưởng theo cấp số cộng, mà theo cấp số nhân. Các tập đoàn, các
công ty hay bất kì tổ chức lớn nào đều đang phải đối mặt với nhu cầu xử lý một
khối lượng dữ liệu ngày càng khổng lồ. Sự tăng trưởng này đòi hỏi các chiến lược
mới để tăng tốc việc tính toán dữ liệu.
Từ đó, các giải pháp nhằm tăng tốc độ tính toán đã được ra đời. Từ năm 2001
đến năm 2003 tốc độ của Pentium 4 đă tăng gấp đôi từ 1.5GHz lên đến 3GHz. Tuy
nhiên, định luật Moore về “Số lượng transistor trên mỗi đơn vị inch vuông sẽ tăng
lên gấp đôi sau mỗi hai năm” hiện nay đã không còn chính xác, khi mà từ năm 2007
đến năm 2011, tốc độ của CPU chỉ tăng từ 2.93 Ghz lên đến 3.9 Ghz, tức là tăng
33% [6]. Có thể nói, việc gia tăng xung hoạt động của CPU trong tương lai gần sẽ
sớm đạt đến ngưỡng giới hạn.
Trước thực tế này, các công ty sản xuất vi xử lý đã nhanh chóng chuyển
hướng sang phát triển công nghệ đa lõi, với cơ chế xử lý song song trong các máy
tính nhằm tăng hiệu năng và tiết kiệm năng lượng.
Tuy nhiên, việc sử dụng công nghệ đa lõi, ví dụ 02 lõi, để xử lý các ứng dụng
tính toán tuần tự không giúp tốc độ tính toán tăng gấp đôi mà chúng chỉ tăng thêm
khoảng 30%.
Để tận dụng tối đa ưu thế của công nghệ đa lõi, việc nghiên cứu và phát triển
các thuật toán, các phương pháp lập trình song song là rất cần thiết và đóng vai trò
quan trọng trong việc phát triển ứng dụng song song cho nhiều lĩnh vực khác nhau,
như: dự báo thời tiết, sắp xếp, tìm kiếm, mô phỏng các mô hình vật lý, chuẩn đoán y
khoa, thăm dò dầu khí,…
Vấn đề này là nội dung chính của luận văn.
2. Tình hình nghiên cứu và tính mới của đề tài
10




- Tìm hiểu về máy tính song song
- Tìm hiểu về các phương pháp lập trình song song
- Ứng dụng lập trình song song trong việc tổng hợp thông số vận hành lưới
điện: sử dụng .NET Framework 4.5, Microsoft SQL Server 2014.
4. Phương pháp nghiên cứu
- Tìm hiểu lý thuyết dựa vào các giáo trình, sách tham khảo được xuất bản
bởi những nhà xuất bản đáng tin cậy, các bài báo, tạp chí, tài liệu có uy tín trong và
ngoài nước.
- Phát triển và triển khai ứng dụng lập trình song song trong việc tổng hợp
thông số vận hành lưới điện tỉnh Thừa Thiên Huế.

12


CHƯƠNG 1. TỔNG QUAN VỀ MÁY TÍNH SONG SONG
1.1. TỔNG QUAN VỀ MÁY TÍNH SONG SONG
1.1.1. Tại sao phải xử lý song song
Trong những thập niên 60, các máy tính đều được thiết kế dựa trên mô hình
của John Von Neumann. Cùng với một đơn vị xử lý sẽ được kết nối với một vùng
lưu trữ dùng làm bộ nhớ và tại một thời điểm chỉ có một lệnh được thực thi.

Hình 1.1.1.1. Mô tả kiến trúc Von Neumann
Ngày nay, xuất hiện những bài toán mà những hệ thống đơn một bộ xử lý
(BXL) không đáp ứng được yêu cầu xử lý về thời gian và khối lượng dữ liệu lớn.
Mặc dù trong những năm qua người ta không ngừng gia tăng tốc độ của các BXL
nhưng do giới hạn về vật lý nên khả năng tính toán của chúng cũng không thể tăng
mãi được.
Điều này dẫn tới việc người ta không ngừng tìm kiếm, đưa ra các giải pháp


Tốc độ xử lý của các BXL theo kiểu Von Neumann đã dần tiến tới giới hạn,

-

không thể cải tiến thêm được.
Hiện nay giá thành của phần cứng (CPU) giảm mạnh, tạo điều kiện để xây

-

dựng những hệ thống có nhiều BXL với giá thành hợp lý.
Sự phát triển của công nghệ mạch tích hợp cho phép tạo ra những hệ thống
có hàng triệu transistor trên bộ vi xử lý.
Định nghĩa: Một máy tính song song là tuyển tập các BXL, thường là cùng

một loại, kết nối với nhau theo một cách nào đó để có thể hợp tác với nhau trong
hoạt động và trao đổi dữ liệu được với nhau.
Phần lớn các hệ điều hành ngày nay đều đã hỗ trợ đa xử lý/đa nhiệm và cho
phép nghiên cứu và khai thác các phương pháp lập trình song song [3]. Nhưng điều
quan trọng là hệ thống tích hợp thêm nhiều BXL có khả năng tham gia “cùng giải
một bài toán” cho trước.

14


1.2. PHÂN LOẠI CÁC KIẾN TRÚC MÁY TÍNH SONG SONG
Một trong những phân loại kiến trúc máy tính song song được biết đến nhiều
nhất là phân loại của Flynn, được sử dụng từ năm 1966 [1]. Michael Flynn dựa vào
đặc tính về số lượng BXL, số chương trình thực hiện, cấu trúc bộ nhớ, … đã đưa ra
cách phân loại nổi tiếng được nhiều người chấp nhận.


chỉ lệnh khác nhau để thực hiện trên cùng một mục dữ liệu.
Lớp các máy tính có các luồng dữ liệu được chuyển tuần tự theo dãy các
CPU liên tiếp.

Hình 1.1.1.4. Mô hình hoạt động của kiến trúc MISD
1.2.4. Mô hình MIMD - Đa luồng lệnh, đa luồng dữ liệu
16


Mô hình này cho phép nhiều lệnh khác nhau có thể đồng thời xử lý nhiều dữ
liệu khác nhau trong cùng một thời điểm.
Hầu hết các hệ thống MIMD đều có bộ nhớ riêng và cũng có thể truy cập vào
bộ nhớ chung khi cần, do vậy giảm thiểu được thời gian trao đổi dữ liệu giữa các
BXL trong hệ thống.

Hình 1.1.1.5. Mô hình hoạt động của kiến trúc MIMD
Đâ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 như: BBN
Butterfly, Alliant FX, iSPC của Intel, ...
1.3. KIẾN TRÚC MÁY TÍNH SONG SONG
Theo như sự phân loại của Flynn thì có hai họ kiến trúc quan trọng nhất cho
các máy tính song song là SIMD và MIMD. Những kiến trúc khác nhau sẽ tạo ra
những khả năng khác nhau cho việc xử lý song song.
Ngay trong kiến trúc tuần tự ta cũng có thể tận dụng tốc độ cực nhanh của
các BXL để thực hiện xử lý song song theo nguyên lý chia sẻ thời gian và chia sẻ tài
nguyên. Tất nhiên là với kiến trúc máy tính song song thì mục đích chính là khai
thác triệt để khả năng của kiến trúc song song để viết các chương trình song song.
17



1.3.1.1.3. Sự gối đầu của CPU và các thao tác vào/ra (I/O)
Nhiều phép vào/ra có thể thực hiện đồng thời đối với nhiều nhiệm vụ tính
toán khác nhau bằng cách sử dụng các bộ điều khiển vào/ra, các kênh hay những
BXL vào/ra khác nhau. Trong các máy tính hiện nay có nhiều bộ điều khiển thiết bị
ra/vào cho phép đa xử lý vào/ra do vậy tăng được tốc độ trao đổi dữ liệu giữa các
thiết bị ngoài với CPU.
1.3.1.1.4. Các hệ thống bộ nhớ phân cấp
Tốc độ các phép toán thực hiện trong BXL nhanh hơn rất nhiều việc truy cập
vào bộ nhớ và tốc độ truy cập vào bộ nhớ nguyên thủy (bộ nhớ trong) nhanh hơn
đối với các bộ nhớ phụ (bộ nhớ ngoài).
Các thanh ghi được sử dụng trực tiếp cho các ALU. Bộ nhớ cache được xem
như vùng đệm giữa BXL và bộ nhớ chính. Sự song song hóa trong sự trao đổi dữ
liệu theo thứ tự phân cấp là cách khai thác chung để cải tiến hiệu quả xử lý của hệ
thống. Ví dụ trong khi dữ liệu chuyển từ bộ nhớ phụ vào bộ nhớ chính thì đồng thời
có thể chuyển dữ liệu từ bộ nhớ cache vào CPU.
1.3.1.1.5. Đa chương trình và chia sẻ thời gian
Các hệ điều hành của máy tính đơn BXL cho phép thực hiện song song dựa
vào cách tiếp cận phần mềm. Trong cùng một khoảng thời gian, có nhiều tiến trình
cùng truy cập vào dữ liệu từ những thiết bị vào/ra chung.
Các hệ điều hành đa chương trình luân phiên thực hiện các chương trình
khác nhau. Để thực hiện việc này HĐH sử dụng Bộ lập lịch chia sẻ thời gian làm
nhiệm vụ phân chia CPU cho mỗi tiến trình một khoảng thời gian cố định theo
phương pháp quay vòng tròn. Bằng cách đó, tất cả các tiến trình đều được sẵn sàng
để thực hiện trên cơ sở được phép sử dụng CPU và những tài nguyên khác của hệ
thống.
Do vậy, về nguyên tắc việc phát triển những chương trình song song trên
máy đơn BXL thực hiện được nếu có hệ điều hành cho phép nhiều tiến trình thực
hiện, nghĩa là có thể xem hệ thống như là đa BXL.
19

1.3.3. Kiến trúc máy tính kiểu SIMD
Trong máy tính SIMD, tất cả các phần tử xử lý đều được điều hành bởi một
đơn vị điều khiển (CU). Tất cả các đơn vị xử lý nhận được cùng một lệnh từ CU
nhưng hoạt động trên những tập dữ liệu khác nhau. Mô hình máy tính SIMD có
những đặc tính sau:
-

Phân tán việc xử lý trên nhiều phần cứng.
Thao tác đồng thời trên nhiều phần tử dữ liệu.
20


-

Thực hiện cùng 1 tính toán trên tất cả các phần tử dữ liệu.

1.3.4. Kiến trúc máy tính kiểu MISD
BXL hình ống chính là BXL kiểu MISD làm theo nguyên lý hình ống.
Nguyên lý này dựa vào phương pháp phân đoạn hoặc chia nhỏ một tiến trình tính
toán thành một số đoạn nhỏ hơn để thực hiện trong các pha liên tiếp. Tất cả các giai
đoạn của một tiến trình được thực hiện tuần tự, khi thực hiện xong thì bắt đầu thực
hiện các tiến trình tiếp theo. Mỗi pha thực hiện xong sẽ truyền kết quả cho các pha
tiếp theo.
Như vậy, trong cách thực hiện theo nguyên lý hình ống, khi một giai đoạn
công việc đang thực hiện thì một giai đoạn khác có thể nạp dữ liệu vào và dữ liệu
vào của giai đoạn này có thể là kết quả của giai đoạn trước nó.
1.3.5. Các bộ xử lý mảng tâm thu SAP
Năm 1978 Kung và Leiserson đề xuất một loại kiến trúc được gọi là mảng
tâm thu (Systolic Array) cho những tính toán đặc biệt. Mảng tâm thu viết tắt là SA,
là một mảng các đơn vị xử lý được kết nối cục bộ với nhau.

Một trong những thành phần quan trọng nhất của kiến trúc máy tính là bộ
nhớ. Bộ nhớ thường được chia thành n mức. Bộ nhớ mức 1 là mức bộ nhớ cao nhất
và có dung lượng nhỏ nhất, nhanh và đắt nhất thường được gắn chặt với BXL thành
bộ nhớ cục bộ. Bộ nhớ mức 2 thường nhỏ hơn, rẻ hơn và chậm hơn mức 1 [4].
Về nguyên tắc, dữ liệu được chuyển đổi từ các mức lân cận của các bộ nhớ
và hoàn toàn được điều khiển bởi bộ nhớ mức 1. Về lý thuyết trong cấu trúc phân
cấp bộ nhớ, tốc độ truy cập bộ nhớ trung bình bằng tốc độ truy cập ở mức cao (mức
1). Nhưng chi phí của các đơn vị nhớ trung bình lại gần với giá của bộ nhớ ở mức
thấp nhất (mức n).
Các hệ thống bộ nhớ phân cấp có tốc độ thực hiện các phép toán trong BXL
nhanh hơn rất nhiều so với việc truy cập vào bộ nhớ. Tốc độ truy cập vào bộ nhớ
trong nhanh hơn rất nhiều so với việc truy cập vào bộ nhớ ngoài.
Hệ thống bộ nhớ phân cấp như thế có thể mô tả như hình bên dưới:

22


Hình 1.1.1.6. Mô tả cấu trúc của bộ nhớ phân cấp
Sau đây chúng ta tìm hiểu một vài mô hình bộ nhớ của máy tính song song.
1

Bộ nhớ kết hợp
Bộ nhớ kết hợp (AM - Associative Memory) bao gồm các ô nhớ (cell). Mỗi ô

nhớ của AM có 4 đầu vào và 2 đầu ra. Các đầu vào (input) của mỗi ô nhớ bao gồm:
-

Bit đối số a
Bit đọc/ghi R/W xác định thao tác tương ứng cần thực hiện
Bit khoá k


Concurrent Read (CR): nhiều BXL có thể đọc đồng thời cùng một ô nhớ.
Exlusive Read (ER): p BXL đọc được p vùng nhớ khác nhau và mỗi BXL

-

đọc được duy nhất một vùng nhớ và mỗi vùng nhớ được đọc bởi một BXL.
Concurrent Write (CW): cùng một thời điểm cho phép nhiều BXL ghi vào

-

cùng một vùng nhớ.
Exlusive Write (EW): p BXL ghi được vào p vùng nhớ khác nhau. Mỗi
BXL ghi được vào một vùng nhớ và mỗi vùng nhớ được ghi bởi một BXL.
b. Các loại CW:

-

Ghi đồng thời có ưu tiên (Priority CW): các BXL được gắn mức ưu tiên và
khi có nhiều BXL muốn ghi dữ liệu vào một vùng nhớ thì ưu tiên cho BXL
có mức ưu tiên cao nhất. Các mức ưu tiên có thể gắn tĩnh hoặc động theo

-

những qui tắc được xác định khi thực hiện.
Ghi đồng thời chung (Common CW): Khi các BXL ghi cùng một giá trị thì
chúng được phép ghi vào cùng một vùng nhớ. Trong trường hợp này, một

-