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

PGS.TS. NGUYỄN MẬU HÂN

Thừa Thiên Huế, 2016


LỜI CAM ĐOAN

Tôi xin cam đoan luận văn này là cơng trình nghiên cứu của cá nhân tơi.
a. Những nội dung trong luận văn này là do tôi thực hiện dưới sự hướng dẫn
trực tiếp của PGS.TS Nguyễn Mậu Hân.
b. Tất cả số liệu, kết quả nghiên cứu trong luận văn là trung thực.
c. Các tham khảo dùng trong luận văn đều được trích dẫn rõ ràng và trung
thực về tên tác giả, tên cơng trình, và thời gian cơng bố.
Tác giả

Phan Quang Nhật


LỜI CẢM ƠN

Lời đầu tiên, cho phép tôi được bày tỏ lịng kính trọng và biết ơn sâu sắc tới
PGS.TS. Nguyễn Mậu Hân, bộ môn Công nghệ phần mềm khoa Công nghệ thông
tin trường Đại học Khoa học Huế, người đã trực tiếp tận tình hướng dẫn tơi trong
q trình làm luận văn.
Tôi xin chân thành cảm ơn ThS. Nguyễn Hồng Hà, người đã cho tơi những
góp ý rất hữu ích, cùng tồn thể các thầy cơ giáo Khoa Cơng nghệ thông tin trường
Đại học Khoa học Huế đã tận tình dạy dỗ trong suốt hai năm học vừa qua.
Tơi xin chân thành cảm ơn ơng Hồng Ngọc Hồi Quang, trưởng phịng
Điều Độ Cơng ty Điện Lực Thừa Thiên Huế, người đã định hướng cho tôi ý tưởng
và hỗ trợ tơi trong q trình phát triển ứng dụng, cùng tồn thể cán bộ nhân viên

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ể hồ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


Base Class Library (Thư viện lớp cơ sở)

BXL

Bộ xử lý

CD

Compact Disk (Đĩa quang)

CPU

Central Processing Unit (Bộ xử lý trung tâm)

CRL

Common Runtime Language (Bộ thực thi ngôn ngữ
chung)

CSDL

Cơ Sở Dữ Liệu

HĐH

Hệ Điều Hành

LINQ

Language Integrated Query (Ngôn ngữ truy vấn tích hợp)


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)


PVM

Parallel Virtual Machine (Máy ảo song song)

RTU

Remote Terminal Units (Khối thiết bị đầu cuối)

SCADA
SISD

Supervisory Control and Data Acquisition
(Hệ thống điều khiển giám sát và thu thập dữ liệu)
Single Instruction Single Data (Đơn lệnh đơn dữ liệu)


SIMD

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

SMP

Symmetric Multi-Processor (Đa bộ xử lý đối xứng)

TPL

Task Parallel Library (Thư viện tác vụ 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 đồ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 tố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 tốn tuần tự khơng giúp tốc độ tính tố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 tố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 đố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



Trên thế giới, việc nghiên cứu về các phương pháp lập trình song song cũng
đã có nhiều cơng trình và đã được ứng dụng nhiều trong đời sống xã hội. Tuy nhiên,
như đã nêu ở phần trên, với xu thế phát triển, với yêu cầu của xã hội, luôn đặt ra
nhiều thách thức mới, đòi hỏi phải tiếp tục nghiên cứu nhiều giải pháp tối ưu hơn và
ứng dụng nhiều hơn trong đời sống xã hội hiện đại.
Việc nghiên cứu về các phương pháp lập trình song song ngày càng được
quan tâm. Nhiều ngơn ngữ lập trình song song đang được sử dụng như: Fortran 90,
C-Linda, PVM với C/C++, CDC 6600, …
Tại Việt Nam, đã có một vài hệ thống xử lý song song được nghiên cứu
thành công và đưa vào ứng dụng như hệ thống máy tính bó song song do CADPRO
thiết kế cho Trung tâm Quốc gia dự báo khí tượng thủy văn, hoặc các trung tâm dữ
liệu của FPT Telecom, ... Tuy nhiên, số lượng không nhiều các hệ thống xử lý song
song kiểu này đã chứng tỏ xử lý song song chưa thực sự phát triển mạnh mẽ ở Việt
Nam.
Hiện nay, cũng như các ngành nghề khác, ngành Điện đang tích cực khuyến
khích việc ứng dụng Công nghệ thông tin vào trong các hoạt động sản xuất kinh
doanh. Các ứng dụng nghiệp vụ ngày càng đóng vai trò quan trọng và được chú
trọng đầu tư, phát triển. Việc tích hợp các phương pháp lập trình song song vào
trong các ứng dụng nghiệp vụ giúp tăng tốc độ tính tốn, xử lý dữ liệu. Từ đó, trở
thành một trong những yếu tố giúp tăng năng suất lao động và việc phục vụ khách
hàng ngày càng tốt hơn.
Từ những kiến thức đã nghiên cứu, cũng như kinh nghiệm công tác của bản
thân, dù chỉ là một phần nhỏ, trong khuôn khổ của luận văn này, tôi đã tự phát triển
ứng dụng lập trình song song theo luồng, cụ thể là sử dụng lớp Parallel trong .NET
framework 4.5, 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ế để minh họa cho phần kiến thức nghiên cứu trong luận văn.

3. Mục đích của đề tài
11



- 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à
ngồ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 tố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

mới, trong đó có ý tưởng kết hợp nhiều BXL vào trong một máy tính hay cịn gọi là
xử lý song song (Multiprocessor) hoặc kết hợp sức mạnh tính tốn của nhiều máy
tính dựa trên kết nối mạng (gọi là máy tính song song - multicomputer).
1.1.2. Định nghĩa về xử lý song song
Xử lý song song là quá trình xử lý gồm nhiều tiến trình được kích hoạt đồng
thời và cùng tham gia giải quyết một vấn đề, nói chung là thực hiện trên những hệ
thống đa BXL [1].
13


1.1.3. Phân biệt xử lý song song và xử lý tuần tự
Khái niệm xử lý song song khác với xử lý tuần tự:
-

Trong tính tốn tuần tự, một BXL thì mỗi thời điểm thực hiện một phép

-

tốn.
Trong tính tốn song song, một số BXL kết hợp với nhau để giải quyết
cùng một vấn đề tức là tại cùng một thời điểm có thể thực hiện được nhiều
phép tốn đồng thời cho nên giảm được thời gian xử lý tức là tại cùng một
thời điểm có thể thực hiện được nhiều phép tốn đồng thời.
Mục đích của xử lý song song là tận dụng các khả năng của các hệ đa BXL

để thực hiện những tính tốn nhanh hơn trên cơ sở sử dụng nhiều BXL đồng thời.
Câu hỏi đặt ra là ứng dụng xử lý song song trong thực tiễn liệu có hiện thực hay
khơng? Dưới đây là những yếu tố dẫn đến việc chuyển đổi từ xử lý tuần tự sang xử
lý song song hoàn toàn phù hợ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 tố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.

1.2.1. Mơ hình SISD - Đơn luồng lệnh, đơn luồng dữ liệu
Đây chính là mơ hình máy tính truyền thống kiểu Von Neumann. Tại mỗi
thời điểm, nó thực hiện một chỉ lệnh chỉ đọc và ghi một mục dữ liệu.
Tất cả các máy tính SISD chỉ có một thanh ghi (register) được gọi là bộ đếm
chương trình, được sử dụng để nạp địa chỉ của lệnh tiếp theo và kết quả là thực hiện
theo một thứ tự xác định của các câu lệnh.

Hình 1.1.1.2. Mơ hình hoạt động của kiến trúc SISD
Mơ hình SISD cịn được gọi là SPSD, đơn chương trình đơn luồng dữ liệu.
1.2.2. Mơ hình SIMD - Đơn luồng lệnh, đa luồng dữ liệu
Mơ hình này được gọi là kiến trúc xử lý mảng. Máy tính SIMD có một đơn
vị điều khiển để điều khiển nhiều đơn vị xử lý thực hiện theo một luồng các câu
lệnh. CPU phát sinh tín hiệu điều khiển tới tất cả các phần xử lý, những BXL này
cùng thực hiện một phép toán trên các mục dữ liệu khác nhau, nghĩa là mỗi BXL có
luồng dữ liệu riêng.

15


Hình 1.1.1.3. Mơ hình hoạt động của kiến trúc SIMD
Đây chính là mơ hình máy tính phổ biến trên thị trường như: ILLIAC IV,
DAP, Connection Machine CM-2.
1.2.3. Mơ hình MISD - Đa luồng lệnh, đơn luồng dữ liệu
Mơ hình này cho phép một vài lệnh cùng thao tác trên cùng một dữ liệu, chia
thành 2 nhóm:
-

Lớp các máy tính u cầu những đơn vị xử lý (PU) khác nhau với những

-


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. Song song hóa máy tính tuần tự
Mục tiêu của máy tính song song là khai thác tới mức tối đa các khả năng sử
dụng của các thiết bị phần cứng nhằm giải quyết nhanh các bài toán được đặt ra
thực tế. Nhưng với người lập trình thì kiến thức về cấu trúc phần cứng hồn tồn
khó nắm bắt. Do đó dưới đây chúng ta đi tìm hiểu về kỹ thuật xử lý song song được
áp dụng trong các máy tính có một BXL.
1.3.1.1.1. Xử lý theo ngun lý hình ống trong CPU
Nhiều pha xử lý khác nhau của các câu lệnh có thể thực hiện theo ngun lý
hình ống. Ví dụ: nạp câu lệnh về từ bộ nhớ, giải mã (decode), xác định các toán
hạng, thực hiện các phép toán số học/logic và lưu trữ kết quả,… Những câu lệnh
trong chương trình có thể thực hiện gối đầu nhau theo ngun lý hình ống và nó sẽ
hiệu quả hơn khi dựa vào kỹ thuật tạo ra vùng đệm dữ liệu.
Bằng cách thực hiện như trên thì trong quá trình thực hiện của BXL có thể
thực hiện được nhiều câu lệnh gối đầu nhau trong cùng một thời gian. Trước khi
một câu lệnh kết thúc thực hiện thì câu lệnh tiếp theo đã có thể thực hiện pha giải
mã, câu lệnh khác lại có thể được nạp về, …
1.3.1.1.2. Đa đơn vị chức năng
Hầu hết các máy tính truyền thống chỉ có một đơn vị số học và logic trong
BXL. Ở mỗi thời điểm nó chỉ có thể thực hiện một chức năng.
Nhiều máy tính thực tế hiện nay có nhiều đơn vị chức năng (nhất là những
chức năng chuyên biệt) và những đơn vị này có thể thực hiện song song được.
Những đơn vị chức năng này độc lập với nhau và do vậy có thể thực hiện đồng
thời. Thường đó là các đơn vị thực hiện các phép toán rất cơ bản như: phép
cộng, nhân, chia, tăng, giảm, các phép logic và các phép dịch chuyển (shift).
Vấn đề chính của những máy tính này là cần phải xây dựng bộ lập lịch tối ưu
để phân chia theo câu lệnh thực hiện sao cho tận dụng được tối đa các đơn vị chức
năng cũng như các tài nguyên mà máy tính cung cấp.
18



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
tố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.2. Mơ hình trừu tượng của máy tính song song
Trước khi xem xét những kiến trúc máy tính song song cụ thể, chúng ta hãy
nghiên cứu một mơ hình trừu tượng của máy tính song song. Mục đích chính là
muốn thể hiện được những khả năng tính tốn của máy tính song song mà khơng
quan tâm đến những ràng buộc cụ thể của những máy tính có trong thực tế.
Thơng thường sau khi xây dựng các thuật toán song song chúng ta quy ước
là phát triển thuật tốn cho mơ hình trừu tượng này, sau đó ánh xạ sang những máy
tính cụ thể với một số ràng buộc nào đó.
Máy tính truy cập ngẫu nhiên song song PRAM chứa một đơn vị điều khiển,
bộ nhớ chung và một tập không giới hạn các BXL, mỗi BXL lại có một bộ nhớ
riêng. Mỗi BXL có một chỉ số duy nhất được sử dụng để xác định địa chỉ trong quá
trình trao đổi các tín hiệu và quản lý các ngắt. Tất cả các BXL đều chia sẻ bộ nhớ
chung với yêu cầu khơng giới hạn. Các câu lệnh có thể bắt đầu thực hiện ở bất kỳ
thời điểm nào, ở bất kỳ vị trí nào của bộ nhớ.
Một số điều cần lưu ý khi phát triển những thuật toán cho các máy tính song
song tổng qt:
-

Khơng bị giới hạn về số lượng BXL. Với nhiều BXL thì tốc độ tính tốn sẽ

-

càng thực hiện nhanh hơn.
Tất cả các bộ vi xử lý đều có thể truy cập đến mọi vị trí của bộ nhớ.
Không giới hạn về dung lượng bộ nhớ chung chia sẻ trong hệ thống.
Các BXL có thể đọc bất kỳ một vị trí nào của bộ nhớ, khơng cần phải chờ
để những BXL khác kết thúc công việc truy cập vào bộ nhớ.


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 tố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 ngun 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
tố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 tố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.

Trong mảng tâm thu SA, mỗi PE (Processing Element) được xem như một tế
bào (một ô trong mảng) bao gồm:
-

Một số thanh ghi (register)
Một bộ cộng (adder)
Các mạch điều khiển
Đơn vị logic - số học ALU
Dựa vào SA người ta xây dựng kiến trúc SAP. Trong kiến trúc SAP nêu trên:

bộ điều khiển (Controller) làm nhiệm vụ giao diện cho BXL chính (Host Processor)
và gửi các tín hiệu điều khiển q trình vào/ra dữ liệu cho SA.
Hiệu quả của SA phụ thuộc rất nhiều vào các đặc tính vào/ra của dữ liệu. Nó
sẽ rất hiệu quả đối với những bài tốn mà số liệu đọc/ghi thực hiện với nhịp độ cao,
đều đều và liên tục như các bài toán xử lý ảnh, qui hoạch tuyến tính, ...
1.3.6. Kiến trúc máy tính kiểu MIMD
21


Máy tính kiểu MIMD là loại đa BXL hoặc cịn gọi là hệ thống đa máy tính,
trong đó mỗi BXL có đơn vị điều khiển (CU) riêng và thực hiện chương trình riêng
của mình. MIMD có những đặc trưng sau:
-

Xử lý phân tán trên một số BXL độc lập
Chia sẻ với nhau một số tài nguyên, trong đó có hệ thống bộ nhớ
Mỗi BXL thao tác độc lập và có thể thực hiện đồng thời với nhau
Mỗi BXL chạy một chương trình riêng

1.4. BỘ NHỚ CỦA MÁY TÍNH SONG SONG

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

Bit lựa chọn s để xác định ơ nhớ thích hợp cho việc thực hiện đọc/ghi.
Hai kết quả ở đầu ra:

-

Bit đối sánh m chỉ ra dữ liệu được lưu trong bộ nhớ có đối sánh được với

-

bit đối số a.
Bit kết quả ra q.

23


Hình 1.1.1.7. Mơ tả một ơ nhớ AM

Hình 1.1.1.8. Mơ tả cấu trúc của bộ nhớ kết hợp
1.4.1. Bộ nhớ truy cập ngẫu nhiên song song
Mơ hình tính tốn song song được biết dưới tên gọi PRAM bao gồm bộ nhớ
chung RAM với m vùng bộ nhớ đủ lớn để chia sẻ cho p BXL.
Bộ nhớ chung PRAM được sử dụng để lưu trữ dữ liệu và là vùng để trao đổi
dữ liệu giữa các BXL. Nó cho phép các BXL truy cập vào bộ nhớ đồng thời và có
thể hoạt động một cách dị bộ.
Mơ hình loại này có các phương thức truy cập sau:
a. Các phương thức truy cập bộ nhớ:
24


-


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

-


BXL sẽ được chọn để ghi dữ liệu đó.
Ghi đồng thời tự do (Arbitrary CW): một số BXL muốn ghi dữ liệu đồng
thời vào một vùng nhớ, nhưng có một BXL được phép thay đổi giá trị của
vùng nhớ đó. Trong trường hợp này, chúng ta phải chỉ ra cách để lựa chọn

-

BXL thực hiện việc ghi.
Ghi đồng thời ngẫu nhiên (Random CW): BXL được lựa chọn để ghi dữ

-

liệu là ngẫu nhiên.
Ghi đồng thời tổ hợp (Combining CW): tất cả các dữ liệu mà các BXL
định ghi đồng thời vào bộ nhớ được tổ hợp lại thành một giá trị. Giá trị này
sẽ được ghi vào bộ nhớ đó.

25