Chương 1 - Giới thiệu nêu lên mục đích của lập trình song song, những khó khăn của lập trình song song truyền thống, dẫn đến yêu cầu một mô hình lập trình song song kiểu mới linh hoạt hơn. Chƣơng này cũng trình bày mục tiêu của luận văn, tổ chức của luận văn. Chương 2 - Tổng quan về đơn vị xử lý đồ họa (GPU), cung cấp cái nhìn tổng quan về tính toán song song đa dụng trên đơn vị xử lý đồ họa. Mô tả sự khác nhau cơ bản giữa đơn vị xử lý trung tâm (CPU) và đơn vị xử lý đồ họa (GPU).
Phần lớn của chƣơng này dành cho việc giải thích các nguyên tắc cơ bản của tính toán song song đa dụng trên đơn vị xử lý đồ họa và giao diện lập trình ứng dụng (API) trên GPU. TIEU LUAN MOI download : skknchat@gmail.com 13 Chương 3 - Mô hình trường ngẫu nhiên có điều kiện (CRF), trình bày mô hình lý thuyết CRF, phƣơng pháp ƣớc lƣợng tham số của mô hình CRF và một số ứng dụng của CRF. Chương 4 - Ứng dụng GPU song song hóa từng phần công cụ CRF++, giới thiệu công cụ CRF++, cách thức mà tác giả của CRF++ thực hiện, từ đó đề xuất chiến lƣợc song song CRF++ bằng GPU thông qua các thƣ viện lập trình cho GPU nhƣ CUDA, Thrust. Phần cuối của chƣơng sẽ đƣa ra kết quả thực nghiệm cũng nhƣ một số đánh giá, nhận xét.
TIEU LUAN MOI download : skknchat@gmail.com 14 CHƢƠNG 2: TỔNG QUAN VỀ ĐƠN VỊ XỬ LÝ ĐỒ HỌA (GRAPHIC PROCESSING UNIT-GPU) 2. Tóm tắt lịch sử phát triển của đơn vị xử lý đồ họa (GPU) Trong suốt 20 năm qua GPUs đã trải qua những phát triển lớn. Bắt đầu phát triển từ đơn vị xử lý đồ họa 2D đơn giản, đến đa mục đích, có thể lập trình đƣợc, song song mức độ cao, có nhiều lõi đơn vị xử lý với khả năng tính toán phi thƣờng và băng thông bộ nhớ rất cao. Lịch sử của GPUs những năm 1970 với các máy tính có Atari 8-bit.
Những chíp đồ họa này đƣợc sử dụng để hòa trộn đồ họa và dữ liệu văn bản rồi hiển thị chúng lên màn hình. Những năm 1980, kiến trúc của chíp này trở thành nền tảng của sản xuất chíp hàng loạt tiếp theo, đƣợc tích hợp trong Commodore Amiga. Chíp này là chip đầu tiên có đầy đủ các đặc tính tăng tốc đồ họa – nó chứa các đặc tính nhƣ: vẽ hình ảnh gốc, tô màu hình ảnh, chuyển khối hình ảnh, v.Đặc tính cách mạng là tất cả video đƣợc đẩy vào phần cứng. Năm 1984, gần 10 năm sau khi phần cứng tăng tốc đồ họa trở thành chuẩn, IBM giới thiệu tăng tốc 2D/3D đầu tiên dƣới cái tên IBM Professional Graphics Controller, nhƣng thành công thì không đƣợc nhƣ mong đợi.
Việc thiếu tính tƣơng thích, xử lý chậm và giá cao ($4.500) làm cho dự án này thất bại [7]. Trong suốt những năm 1990, nhu cầu tăng tốc đồ họa trở nên cấp thiết, bởi vì số lƣợng máy trạm ngày càng tăng với nền tảng công nghệ của Microsoft Windows. Năm 1993, S3 Graphics giới thiệu chíp đơn 2D tăng tốc đầu tiên - S3 86C911, dƣới tên mã là Porsche 911. Chíp này thiết lập chuẩn tăng tốc 2D trong vòng vài năm.
Năm 1995 gần nhƣ tất cả các nhà sản xuất chíp đã bổ sung hỗ trợ tăng tốc 2D vào sản phẩm của họ. Giữa những năm 1990 đồ họa 3D thời gian thực trở nên phổ biến hơn trong máy tính và trò chơi điều khiển. Nhu cầu đồ họa 3D thời gian thực dẫn đến phát triển tăng tốc 3D thời gian thực đầu tiên. Các chíp giá rẻ nhƣ S3 ViRGE, Matrox Mystique hay Ati Rage đƣợc dựa trên 2D tăng tốc và thêm các đặc tính 3D.
Bƣớc đột phá đầu tiên đến năm 1996, khi 3Dfx Interactive giới thiệu tăng tốc 3D đầu tiên đầu đủ tính năng có tên là Voodoo [8]. Gia tăng tốc độ này xác định tiêu chuẩn mới cho chip đồ họa 3D cho ba năm tiếp theo. Bƣớc đột phá lớn thứ hai đến năm 1999 khi tổng công ty nVidia giới thiệu GPU đầu tiên – NV10, TIEU LUAN MOI download : skknchat@gmail.com 15 dƣới tên mã GeForce 256. Tất cả các con chíp hiện nay về cơ bản đều xuất phát từ kiến trúc này.
Vào cuối năm 2006 nVidia giới thiệu kiến trúc thiết bị hợp nhất cho tính toán đầu tiên - Compute Unified Device Architecture (CUDA). Các công ty đối thủ AMD/ATI giới thiệu kiến trúc của họ (ATI FireStream) vài tháng sau đó. Thời điểm này GPU trở nên dễ tiếp cận để phát triển phần mềm bằng các ngôn ngữ lập trình chuẩn công nghiệp và thiết lập cách thức mới cho tính toán hiệu năng cao [2]. Sự khác nhau giữa GPU và CPU Ý tƣởng chính của tính toán song song đa dụng trên GPU (GPGPU) là sử dụng nhiều bóng bán dẫn (transistor) để xử lý dữ liệu và xử lý dữ liệu song song.
Đây là sự khác biệt chính giữa CPU và GPU. GPU chủ yếu định hƣớng các thao tác song song dữ liệu hơn là trữ dữ liệu (caching data) và điều khiển luồng [2]. Nhu cầu này chủ yếu xuất phát từ dựng hình đồ họa, bởi vì thiết bị đồ họa bắt buộc phải xử lý một lƣợng lớn các phần tử dữ liệu đồ họa (nhƣ các điểm ảnh, đỉnh và mảnh) và thao tác trên các phân tử này (lightning, blending, clipping, texturing, …). Song song là cách để giảm lƣợng thời gian cần thiết để xử lý dữ liệu và giảm chi phí tổng thể bằng cách phân phối nó trong xử lý các phần tử.
Nguyên tắc cơ bản là quá trình dựng hình đồ họa là cố định. Dữ liệu đƣợc xử lý bởi phần cứng đồ họa đi qua nhiều giai đoạn trƣớc khi chúng đƣợc hiển thị và chuỗi sự kiện này là không thay đổi. Hình 1: Sự khác nhau giữa CPU và GPU – GPU có nhiều bộ xử lý để định hướng xử lý song song dữ liệu [2]. TIEU LUAN MOI download : skknchat@gmail.com 16 Hình 2: So sánh tốc độ tính toán giữa CPU và GPU [2] CPU phải xử lý nhiều tác vụ khác nhau vào cùng một thời gian.
Vì vậy CPU phải đƣợc tối ƣu hóa cho mục đích này, chủ yếu lƣu trữ dữ liệu quan trọng đƣợc dùng bởi tiến trình đang chạy và nhanh chóng chuyển ngữ cảnh giữa các tiến trình đang chạy. Tất cả các tác vụ đƣợc cung cấp một thời gian xử lý xác định trƣớc để thực thi mã của chúng. Khi đến thời gian này, hệ điều hành chuyển CPU sang tiến trình tiếp theo. Chuyển đổi ngữ cảnh giữa các tiến trình đang chạy có thể đƣợc tính toán với cƣờng độ lớn.
TIEU LUAN MOI download : skknchat@gmail.com 17 Ngƣợc lại, GPU xử lý nhiều nhất một nhiệm vụ tại một thời điểm nhƣng thực hiện nhiều lần song song. GPU sử dụng mô hình song song dữ liệu, để có thể giải quyết các vấn đề số học cƣờng độ cao hơn CPU. Khi cùng một đoạn mã GPU đƣợc thực hiện song song nhiều lần thì không cần kiểm soát luồng và quản lý bộ nhớ đệm (cache). Thực thi tác vụ song song không đƣợc hỗ trợ trong GPU.
Có nghĩa là, không thể thực thi hai hoặc nhiều chƣơng trình khác nhau trên cùng GPU vào cùng một thời điểm. Mô hình xử lý dữ liệu song song ánh xạ các phần tử dữ liệu vào các đơn vị làm việc cơ sở đƣợc gọi là các luồng (thread). Tính song song thread cùng với phân cấp bộ nhớ chia sẻ và hàng rào đồng bộ hóa giữa các luồng làm nên khái niệm trừu tƣợng về mô hình lập trình song song đa dụng của GPU [2]. Mô hình xử lý song song dữ liệu Mục này sẽ trình bày các khái niệm cơ bản trong đơn vị xử lý đồ họa.
Kernel là một đoạn mã chƣơng trình, đƣợc thể hiện bởi một hàm hay thủ tục viết bằng một ngôn ngữ lập trình cụ thể. Thread là một thực thể chạy mã nhị phân, đƣợc thực thi song song nhiều lần [2]. Có thể nói kernel là một “mẫu hàm” cho một nhóm thread. Hai thuật ngữ quan trọng tiếp theo là host và device.
Host là bao gồm bộ xử lý trung tâm và DRAM của CPU, còn device gồm các bộ xử lý và DRAM của GPU. Host và device đƣợc phân tách bởi không gian địa chỉ của hai DRAM. Host thực thi chƣơng trình chính (mã tuần tự) còn device thực thi kernel (mã song song). Device trong mô hình này làm việc giống nhƣ một bộ đồng xử lý (co-processor) đối với host.
Hình 3 thể hiện cách thức thực thi mã tuần tự và song song. GPU thread dùng xử lý dữ liệu song song và mô hình lập trình. Trong mô hình này, các phần tử dữ liệu cơ sở đƣợc lƣu trong bộ nhớ GPU đƣợc ánh xạ vào thread đang chạy. Bộ nhớ GPU (không gian địa chỉ) là một mảng tuyến tính của các phần tử cơ bản (bytes).
Để ánh xạ thread vào bộ nhớ đối tƣợng chúng ta cần biết cách tổ chức thread. Cơ cấu tổ chức này phải có khả năng xác định rõ đối tƣợng bộ nhớ từ các giá trị định danh thread đƣợc sinh ra một cách tự động. Để làm đƣợc điều này, cách dễ dàng nhất là tổ chức thread thành lƣới (grid) ảo đa chiều của các thread. Với công nghệ CUDA, lƣới này có 5 chiều và để định hƣớng tốt hơn, lại đƣợc chia thành 2 loại: khối 3 chiều của thread và lƣới 2 chiều của khối của thread.
TIEU LUAN MOI download : skknchat@gmail.com 18 Hình 3: Nguyên lý lập trình trên GPU [2] Số định danh duy nhất của thread có thể ƣớc lƣợng từ một số biến liên quan, đƣợc khởi tạo khi lƣới của khối thread đƣợc liệt kê. Các biến này có thể truy cập từ bên trong mỗi kernel. Mỗi thread có biến riêng của nó, chứa tọa độ TIEU LUAN MOI download : skknchat@gmail.com 19 ba chiều x, y, z trong khối. Khối thread chứa các biến chiều x, y, z ứng với các trục , , và tọa độ 2 chiều x, y trong lƣới khối thread.
Các chiều của lƣới khối thread cũng có thể truy cập từ trong các biến x, y. Các chiều của khối thread và của lƣới phải đƣợc thiết lập trƣớc khi chạy các tính toán. Số định danh duy nhất của thread trong khối thread và số định danh duy nhất của block trong grid đƣợc tính nhƣ sau [2]: threadId = x + y * x+ z* x* y (2.2) Hình 4: Ví dụ về lưới 5 chiều của thread Cơ cấu phân cấp cung cấp phƣơng tiện để tính toán trên các cấu trúc dữ liệu nhƣ véctơ, ma trận hay mảng ba chiều. Tuy nhiên do hạn chế của phần cứng, kích thƣớc của khối thread hay số thread trong mỗi block là giới hạn1.
1 Đối với nVidia CUDA tương thích với 1.