Tăng tốc độ giải thuật mã hóa HUFFMAN cho nén ảnh số bằng GPU - Đào Huy Du

Điều khiển – Cơ điện tử - Truyền thông Đào Huy Du, “Tăng tốc độ giải thuật mã hóa Huffman cho nén ảnh số bằng GPU.” 80 TĂNG TỐC ĐỘ GIẢI THUẬT MÃ HÓA HUFFMAN CHO NÉN ẢNH SỐ BẰNG GPU Đào Huy Du* Tóm tắt: Trong các phương pháp nén đặc biệt là các phương pháp nén không tổn hao nếu muốn kết quả nén đạt tỷ lệ nén cao đồng nghĩa với việc thời gian nén sẽ cao. Giải thuật mã hóa Huffman là một giải thuật mã hóa không mất mát thông tin được áp dụng vào việc nén các đối tượng (văn bản, hình ảnh,) cần độ chính xác cao, tuy nhiên giải thuật này cần một khoảng thời gian khá lớn để thực thi các thao tác mã hóa. Trong bài báo này, tác giả đưa ra phương pháp cải tiến giải thuật Huffman áp dụng trong nén ảnh có độ phân giải cao bằng cách chia ảnh thành các khối con để có thể thực hiện mã hóa song song trên các lõi của GPU. Việc thực thi giải thuật đề xuất này được thực thi trên GPU của NVIDIA kết hợp với các thư viện hỗ trợ xử lý song song của MatLab, đồng thời, đưa ra kết quả để so sánh hiệu suất giữa việc mã hóa có sử dụng và không sử dụng GPU. Từ khóa: Paralell Computing, GPU, Huffman, Paralell Coding. 1. ĐẶT VẤN ĐỀ Với mục đích cắt giảm chi phí trong việc lưu trữ ảnh và thời gian để truyền ảnh đi xa nhưng vẫn đảm bảo chất lượng của ảnh, nén ảnh là một trong những bước quan trọng nhất trong quá trình truyền thông và lưu trữ. Nén ảnh được áp dụng rất rộng rãi trong thực tế như: truyền các văn bản dưới dạng đồ họa, nén ảnh trong y tế, các ảnh dữ liệu chụp từ vệ tinh v.v... Nén ảnh là kỹ thuật được sử dụng để làm giảm kích thước của ảnh bằng cách loại bỏ một số thành phần dư thừa trong ảnh hay thay thế các thành phần trong ảnh bằng một thành phần khác nhằm làm giảm kích thước ảnh. Phương pháp cắt giảm các thông tin dư thừa trong dữ liệu gốc và làm cho dữ liệu sau nén nhỏ hơn rất nhiều so với dữ liệu gốc được gọi là phương pháp nén mất mát thông tin. Ngược lại, phương pháp nén mà sau khi giải nén thu được chính xác dữ liệu gốc gọi là phương pháp nén không mất mát thông tin [1]. Một số ảnh cần độ chính xác cao thường phải áp dụng kỹ thuật mã hóa không mất mát thông tin để truyền thông hoặc lưu trữ. Ví dụ trong lĩnh vực y tế, đối với kỹ thuật chụp CT-Scanner thì mỗi lát cắt của hình ảnh có thế lên đến 150MB hoặc cao hơn, vì vậy, một tập dữ liệu đầy đủ cho một chẩn đoán trung bình có thể từ 200MB đến 400MB [2]. Với những dữ liệu ảnh như vậy, độ phân giải sẽ rất lớn và cần nhiều dung lượng lưu trữ và đặc biệt chi phí cho thời gian nén và giải nén sẽ cao. Giải thuật mã hóa Huffman được sử dụng rộng rãi trong các ứng dụng liên quan đến truyền thông, các ứng dụng nén dữ liệu ảnh và video [3] [4], giải thuật này đặc biệt phù hợp với những tập dữ liệu lớn nhưng có số lượng các đối tượng xuất hiện trong đó là ít. Giải thuật mã hóa Huffman gồm có 2 bước chính: Bước thứ nhất, dữ liệu ảnh đầu vào được xử lý để tạo ra cây nhị phân và bảng từ mã; Bước thứ 2, mỗi mức xám trong dữ liệu đầu vào được so sánh với bảng từ mã để tạo ra luồng bit nhị phân. Trong bước thứ 2, đây là giai đoạn chiếm nhiều thời gian nhất trong các giai đoạn nén Huffman do việc phải đi so sánh từng phần tử trong tập dữ liệu với bảng từ mã để tạo ra chuỗi dữ liệu mã hóa. Cho dù việc mã hóa Huffman song song là một vấn đề khá phức tạp, song đã có nhiều công trình tập trung nghiên cứu như: tác giả P. Berman, M. Karpinski và Y. Nekrich [5] đã nghiên cứu việc sử dụng n bộ xử lý để tạo ra bảng từ mã song song, nhưng chưa đề cập đến vấn đề mã hóa song song. Trong [6], tác giả trình bày phương pháp giải mã song song mà có một bị lỗi trong quá trình truyền từ tập dữ liệu mã hóa. Trong [7], tác giả đề cập đến Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san ACMEC, 07 - 2017 81 ảnh hưởng của các kiến trúc phần cứng khác nhau đến việc mã hóa Huffman theo phương pháp động. Các kỹ thuật nén JPEG và MPEG cũng áp dụng phương pháp mã hóa Huffman để làm tăng tốc độ nén [8] [9] [10] [11]. Với sự ra đời và phát triển nhanh chóng của bộ xử lý đồ họa GPU (Graphics Processing Unit) cùng với Kiến trúc thiết bị tính toán hợp nhất CUDA (Compute Unified Device Architecture ) của NVIDIA với mô hình xử lý SIMD (Single Instruction Multi Data), nhiều nhà nghiên cứu cũng đã tập trung giải quyết các bài toán xử lý dữ liệu trên GPU. Trong [12], tác giả đã sử dụng GPU để song song hóa giải thuật mã hóa theo độ dài và đã đạt được tốc độ xử lý cao bằng cách giới hạn cho độ dài từ mã; Trong [13], tác giả đã thay đổi giải thuật Huffman để tạo ra khối dữ liệu nén và giải nén hoàn toàn độc lập với nhau và làm tăng tốc độ lên gấp 3 lần so với mã hóa Huffman tuần tự. Trong nghiên cứu này, chúng tôi thực hiện việc mã hóa ảnh mầu có độ phân giải cao sử dụng giải thuật Huffman bằng cách tạo ra các ma trận mầu sau đó chia các ma trận này thành các khối con để đưa vào thực hiện trên từng lõi của GPU. Kết quả kiểm nghiệm cho thấy tốc độ mã hóa và giải mã tăng khoảng 5 lần so với thực hiện giải thuật Huffman tuần tự. Bài báo được trình bày trong 04 mục: Mục 2 trình bày về kiến trúc CPU-GPU và phương thức xử lý của GPU[3]; Mục 3: Mã hóa Huffman song song; Mục 4: Kiểm thử Phương pháp mã hóa Huffman song song để thực thi trên GPU và kết quả so sánh việc thực hiện giải thuật này trên CPU và GPU; Mục 5: Kết luận. 2. KIẾN TRÚC BỘ XỬ LÝ ĐỒ HỌA - GPU CPU được xem như là bộ não của hệ thống máy tính, các hệ thống máy tính hiện nay thường được tích hợp hệ thống card đồ họa; hệ thống này không chỉ phục vụ cho các ứng dụng về xử lý đồ họa mà đã được phát triển để có thể thực hiện một số chức năng tính toán theo mô hình SIMD. Hệ thống Card đồ họa này được gọi là GPU (Graphics Processing Unit). Để thực hiện được các thao tác tính toán một cách hiệu quả, GPU cần được hỗ trợ kiến trúc tính toán song song do Nvidia phát triển gọi là CUDA (Compute Unified Device Architecture - Kiến trúc thiết bị tính toán hợp nhất) [14]. Như được chỉ ra trên hình 1, CPU thường chỉ được thiết kế với một vài lõi tuy nhiên bộ nhớ Cache có kích thước khá lớn nên việc truy cập bộ nhớ không bị giới hạn. Trong khi đó, GPU bao gồm hàng trăm lõi và có thể xử lý đồng thời hàng nghìn luồng lệnh, vì vậy GPU có thể hỗ trợ trong việc tăng tốc độ thực hiện công việc đồng thời tiết kiệm được chi phí đầu tư Qui trình tính toán trên GPU được thực thi như sau [14]: 1. Dữ liệu được chuyển từ bộ nhớ chính (trên CPU) đến bộ nhớ của GPU. 2. Chuyển lệnh cần thao tác từ CPU sang GPU. 3. Mỗi lõi (Core) của GPUsẽ thực thi lệnh một cách song song trên tập dữ liệu riêng biệt. Hình 1. Luồng xử lý dữ liệu trên CUDA [15]. Điều khiển – Cơ điện tử - Truyền thông Đào Huy Du, “Tăng tốc độ giải thuật mã hóa Huffman cho nén ảnh số bằng GPU.” 82 4. Xong khi kết thúc công việc, các Core chuyển kết quả từ bộ nhớ trên GPU về bộ nhớ chính của CPU. Với sự phát triển nhanh chóng của GPU không chỉ trong lĩnh vực đồ họa mà còn thành công trong các kỹ thuật tính toán truyền thống hay song song [16]. Trước đây, mọi thao tác tính toán được thực hiện trên CPU, tuy nhiên khi hệ thống máy tính được tích hợp GPU thì các thao tác tính toán được đưa vào xử lý trên GPU bằng cách di chuyển dữ liệu từ CPU sang GPU và công việc được thực thi nhanh hơn nhờ kỹ thuật xử lý song song nhiều luồng dữ liệu trên các lõi của GPU. 3. MÃ HÓA HUFFMAN SONG SONG Mã hóa Hufman được giới thiệu năm 1952 bởi D. A. Huffman [17], giải thuật này là một giải thuật mã hóa không mất mát thông tin sử dụng trong nén dữ liệu. Tư tưởng của giải thuật sẽ thay thế mỗi đối tượng đầu vào bằng mã bit có độ dài thay đổi, trong đó độ dài của mã bit được xác định dựa vào tần suất xuất hiện của đối tượng đó khi một đối tượng đầu vào có tần suất xuất hiện càng nhiều sẽ được thay thế bởi mã bit càng ngắn. Để thực hiện được, giải thuật Huffman cần thực hiện 2 giai đoạn: (1) Xác định tần suất xuất hiện các đối tượng và xây dựng cây nhị phân và bảng mã hoá, (2) Mã hóa dữ liệu. Khi kích thước ảnh càng lớn, khoảng thời gian để mã hóa càng kéo dài. Do tính chất xử lý của GPU là hoạt động theo mô hình SIMD, nên mỗi lõi trong GPU sẽ đảm nhiệm việc thực hiện các thao tác mã hóa các phần tử ảnh tương ứng với mỗi luồng dữ liệu đưa vào đó. Để thực hiện được việc mã hóa các điểm ảnh song song trên GPU, ảnh phải được tách ra thành 3 ma trận tương ứng với 3 mầu Red, Green, Blue. Gọi ba ma trận đó là Rc, Gc và Bc với kích thước của mỗi ma trận là mxn; Tư tưởng chính trong giải thuật được thực hiện thành 04 bước: Bước thứ nhất: Tách ảnh mầu ban đầu thành 03 ma trận ảnh tương đương với 3 mầu cơ bản là Red, Green và Blue, bước này được thực hiện tuần tự trên CPU. Bước thứ 2: Sau khi ảnh chính được tách ra thành 3 ma trận tương ứng với 3 mầu Red, Green và Blue mỗi ma trận sẽ được xây dựng một cây nhị phân và bảng từ mã tương ứng với các mức xám trong từng ma trận đó. Các bước từ tách ma trận, xây dựng cây nhị phân, tạo bảng từ mã cho mỗi ma trận thành phần đều được thực hiện song song trên CPU và kết quả của bước này sẽ được lưu tại bộ nhớ của mỗi CPU. Bước thứ 3: Sau khi hoàn thành việc xây dựng cây nhị phân và bảng từ mã, mỗi ma trận thành phần sẽ được tách ra thành các khối (mỗi khối sẽ tương ứng với một hàng của Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san ACMEC, 07 - 2017 83 ma trận) và kích thước của mỗi khối sẽ là (m-1)x1, số lượng các Block chính bằng số hàng của ma trận, nếu ma trận có n-1 hàng tương ứng sẽ có n-1 Block. Bước thứ 4: CPU sẽ chuyển các Block vào GPU để thực hiện việc mã hóa. Mỗi Block sẽ được thực hiện mã hóa đồng thời trên mỗi Thread của GPU. Nếu GPU càng có nhiều Thread thì càng có nhiều Block được mã hóa trong cùng một thời điểm, vì vậy tốc độ mã hóa của giải thuật này phụ thuộc vào số lượng Thread của GPU. Mỗi phần tử của ma trận sẽ được so sánh với bảng từ mã và tạo ra các mã tương ứng. Mỗi một Block sau khi đã mã hóa, giải thuật đề xuất sẽ đi ghép giá trị của các phần tử trong các Block này thành 1 file nhị phân. Sau khi thực hiện xong việc tạo ra các File nhị phân kết quả đưa trả về cho CPU, CPU tiếp tục ghép các File nhị phân thành một File tổ hợp. Trong bước thứ 4, mỗi khi tạo ra được một luồng bit nhị phân mã hóa cho các mức xám trong 1 Block, theo nguyên tắc bộ xử lý luôn lưu nội dung của File nhị phân có số bit là bội của 8, nếu file nhị phân chưa đạt được kích thước bằng bội của 8, bộ xử lý sẽ tự động bổ sung số các bit ‘0’ để độ dài File đạt được độ dài theo đúng quy định. Chính nguyên tắc này, gây ra sự nhầm lẫn cho bộ giải mã khi nhận được 1 luồng dữ liệu bit không chính xác theo đúng nội dung mã hóa. Giải pháp để khắc phục trong giải thuật chúng tôi đã gán thêm vào đầu mỗi File nhị phân đã mã hóa kích thước thực của luồng bit mã hóa để khi bộ giải mã nhận và đọc đúng nội dung của luồng bit mà không bị nhầm lẫn bởi các bit ‘0’ được bổ sung. Giả sử File được mã hóa có nội dung:1010010111101100111001111011110110110 Độ dài của file là 37, bộ xử lý sẽ bổ sung thêm 3 bit ‘0’, và File mã hóa sẽ là cuối cùng sẽ là: 1010010111101100111001111011110110110000. Để có thể đọc được đúng độ dài file mã hóa và loại trừ lưu được số bit ‘0’ bổ sung, giải thuật này chèn 2byte vào đầu mỗi file để lưu độ dài byte mã hóa. File ví dụ trên sẽ thành : 00000000001001011010010111101100111001111011110110110000. Hình 2. Minh họa giải thuật để xuất. Điều khiển – Cơ điện tử - Truyền thông Đào Huy Du, “Tăng tốc độ giải thuật mã hóa Huffman cho nén ảnh số bằng GPU.” 84 Trong giải thuật 1, 2, 3, 4, 5 trình bày các bước thực hiện thao tác mã hóa song song áp dụng cho ảnh mầu Giải thuật 1. Tách ma trận mầu thành 3 ma trận thành phần là Red, Green và Blue (tuần tự trên CPU). Đưa ảnh màu Image(RGB )vào xử lý để tách thành 3 ma trận mầu thành phần là Red_Matrix, Green_Matrix và Blue_Matrix Algorithm1 ImgMatComp(file_name) Input: image(RGB) Divide image into Red_Matrix (mxn) Divide image into Green_Matrix (mxn) Divide image into Blue_Matrix (mxn) Output:Red_Matrix, Green_Matrix, Blue_Matrix Giải thuật 2. Xác định tần suất xuất hiện các các mức xám trên ba ma trận thành phần (song song trên CPU). Đối với mỗi ma trận mầu thành phần Red_Matrix, Green_Matrix và Blue_Matrix sẽ được chuyển vào 1CPU để thực hiện thao tác tính tần suất xuất hiện của các mức xám GreyLevel và kết quả được đưa vào 3 bảng Pro_Table tương đương. Algorithm2 Greylevel_Prob Input:Matrix(Red_Matrix,Green_Matrix,Blue_Matrix) Parfor iii=1:3 // each CPU Each (matrix())// each matrix that has size of(m x n) as: Red_Matrix, Green_Matrix, Blue_Matrix { For I: (0-m) do For j: (0-n) do { For index:(0-255) do Compare GreyLevel[i,j]=index Add GreyLevel [i,j]->Pro_table quanlity= quanlity +1 } } Output: Prob_table_Red[GreyLevel,quanlity], Prob_table_Green[GreyLevel,quanlity], Prob_table_Blue[GreyLevel,quanlity] Giải thuật 3. Xây dựng 03 cây nhị phân tương ứng với ba ma trận thành phần (song song trên CPU). Mỗi bảng tần xuất Pro_Table sẽ đi xây dựng cây nhị phân Huf_Tree tương ứng bằng cách sắp xếp giá trị trong bảng theo giá trị tăng dần và các nút của cây nhị phân được gán là các trọng số W của mức xám GreyLevel trong bảng Pro_Table. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san ACMEC, 07 - 2017 85 Algorithm3 BinaryTree Parfor iii=1:3 // each CPU Sort Pro_table_(Red, Green, Blue) ascending i=n while i>=1 do if(Huf_tree[i]≠null) T=merge(Huf_Tree[i], Wi[1]) Remove Wi[1] from Wi if (weight(Greylevel) ≠ 1/2i-1)or (Wi≠) if(Next_greylevel[i] ≠i-1 ) Next_greylevel[i-1]= next_greylevel[i] Next_greylevel[i]=i-1 if(weight(greylevel) > 1/2i-1) Wi-1=merger(Wi-1,Greylevel) if(Huf_Tree(i)is odd) Huf_Tree(Next_greylevel[i]=last(Wi)) i= Next_greylevel[i] Giải thuật 4. Chia mỗi ma trận thành phần thành các khối (Block) và mã hóa mỗi block trong ma trận thành phần thành các file nhị phân tương ứng (song song trên CPU). Chia các ma trận thành phần các khối và các khối con sẽ được mã hóa đồng thời chính bằng số lõi NumberGPUCore của GPU, kết quả mã hóa được lưu trong các file nhị phân binarry_file. Algorithm4 BinaryBlocks thread=NumberGpuCore Parfor n=(1÷thread) for i= (1:lenght(Huff_Tree)) codeword[i]=’’ parfor xx=gpuarray(1:length(index) ) for ind=1:length(symb) if index(xx)==symb(ind) np_data_t{xx}=np(ind); end end end convert block into binary_file add2bytes(binary_file); end Giải thuật 5. Ghép các File nhị phân thành File tổ hợp hoàn chỉnh. Algorithm5 Mergefile(n); for x=1:n(Binary_File) Final_File(Merge Binary_File); end Điều khiển – Cơ điện tử - Truyền thông Đào Huy Du, “Tăng tốc độ giải thuật mã hóa Huffman cho nén ảnh số bằng GPU.” 86 4. KIỂM THỬ Trong phần thử nghiệm cho giải thuật nén Huffman song đề xuất, chúng tôi đã cài đặt giải thuật này trên cả CPU và GPU hỗ trợ kiến trúc CUDA của Nvidia có cụ thể như sau: Cấu hình CPU GPU Phần cứng Intel(R)Xeon(R)CPUE3- 1225V2@3.3Ghz@3.3Ghz 4 Core, 7GB Ram NVIDIA Quadro 600, 96 Cores, GPU Memory Specs: 1 GB DDR3, MaxThreadsPerBlock: 1024 Phần mềm Windows 10, 64-bit Operating System. Matlab R2014a Windows 10, 64-bit Operating System Matlab R2014c Hai ảnh mầu được chụp với độ phân giải cao và được đưa vào mã hóa là VietnamFlag và Flowers: Hình 3. Flowers. Hình 4. VietNamFlag. Cơ sở dữ liệu ảnh như sau: Bảng 1. Các thông số dữ liệu ảnh. Thử nghiệm thứ nhất: thực hiện nén các ảnh trong cơ sở dữ liệu bằng giải thuật Huffman tuần tự trên CPU. Thử nghiệm thứ hai: thực hiện giải thuật nén Huffman đề xuất trên GPU. Hai ảnh mầu được đưa vào để thực hiện mã hóa sẽ được chia thành các Block con và được đưa đến các Core của GPU để xử lý. Cụ thể, với ảnh VietNamFlag sẽ được chia thành 3000 Blocks; ảnh Flowers chia thành 3920 Blocks. Hai ảnh này sẽ được xử lý trên 1024 Thread của 96 Core của GPU. Kết quả thu được như sau: Bảng 2. So sánh kết quả của giải thuật được cài đặt trên CPU và GPU. Tên ảnh VietNamFlag Flowers Dung lượng 5,8MB 24,7MB Kích thước 3000 x 4496 3920 x 2205 Số Block 3000 3920 Thời gian mã hóa(s) CPU 1,5027 27,337 GPU 2,170 4,614 Tên ảnh Dung lượng Kích thước VietNamFlag 5,8MB 3000x4496 Flowers 24,7MB 3920x2205 Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san ACMEC, 07 - 2017 87 Hình 5. Kết quả mô phỏng giải thuật trên CPU và GPU. 5. KẾT LUẬN Trong bài báo, tác giả đã xây dựng giải thuật Huffman song song để cho phép thực hiện song song trên bộ xử lý đồ họa GPU. Trong giải thuật này, các ảnh mầu có kích thước lớn được phân chia ra thành các Block, số Block chính bằng số hàng của ma trận, và giá trị của mỗi phần tử trong Block tương ứng với một mức xám sẽ được mã hóa dựa trên bảng từ mã được xây dựng. Kết quả mã hóa cuối cùng thu được sẽ được lưu thành một file nhị phân. Do giải thuật được thiết kế cho phép tách và chuyển các Block vào từng Core của GPU để có thể thực hiện các thao tác mã hóa một cách đồng thời cho nhiều Block nên đã rút ngắn được khoảng thời gian mã hóa ảnh. Dựa trên kết quả thực thi cho thấy, khoảng thời gian rút ngắn được từ 4 đến 5 lần so với khi thực hiện giải thuật này trên CPU. Ngoài ra, tốc độ mã hóa cũng phụ thuộc vào số Core của GPU, nếu giải thuật được cài đặt trên GPU có càng nhiều Core thì tốc độ tính toán sẽ càng nhanh. TÀI LIỆU THAM KHẢO [1]. M. Rabbani and P. W. Jones, "Digital Image Compression," vol. Spie, 1991. [2]. Anders Eklund, Paul Dufort, Daniel Forsberg and and Stephen LaConte, "Medical Image Processing on the GP: Past, Present and," Medical Image Processing, vol. 17, no. 8, pp. 1073-1094, 2013. [3]. M. Adler, "Deflate algorithm," [Online]. Available: [4]. ISO/IEC JTC 1/SC 29/WG1 – Coding of Still. [Performance]. ISO/IEC JTC 1/SC 29/WG1 N6922, 2015. [5]. P. Berman,M. Karpinsk and Y. Nekrich, "Approximating Huffman Codes in Parallel," Journal of Discrete Algorithms, Vols. Vol. 5, no. 3, pp. 479-490, 2007. [6]. M. B. a. W. Plandowski, "Guaranteed Synchronization of Huffman Codes with Known Position of Decoder," Proceedings of Data Compression Conference, pp. 33- 42, 2009. [7]. L.Y. Liu, J.F. Wang, R.J. Wang and J.Y. Lee, "Design and hardware architectures for dynamic Huffman coding," Proc. Computers and Digital Techniques, pp. 411- 418, 1995. [8]. J.S. Patrick, J.L. Sanders, L.S. DeBrunner and and V.E DeBrunner, "JPEG Điều khiển – Cơ điện tử - Truyền thông Đào Huy Du, “Tăng tốc độ giải thuật mã hóa Huffman cho nén ảnh số bằng GPU.” 88 compression/decopmression via parallel processing," Proc. Signals,Systems and Computers, pp. 596-600, 1996.. [9]. Y. Nishikawa and S. Kawahito and T. Inoue, "A Parallel Image Compression System for High-Speed Cameras," Proc. International Workshop on Imaging Systems and Techniques, pp. 53-57, 2005.. [10]. S.T. Klein and Y. Wiseman, "Parallel huffman decoding with applications to jpeg files," The Computer Journal, vol. 46, p. 487–497, 2003. [11]. S. Wahl, H.A. Tantawy, Z. Wang and P. Wener and S. Si, "Exploitation of Context Classification for Parallel Pixel Coding in Jpeg-LS," Proc. IEEE International Conference on Image Processing, pp. 2001-2004, 2011. [12]. A. Balevic, "Parallel Variable-Length Encoding on GPGPUs," Proc. Parallel Processing Workshops, pp. 26-35, 2010.. [13]. R.L. Cloud, M.L. Curry, H.L. Ward and A. Skjellum and P. Bangalore, "Accelerating Lossless Data Compression with GPUs," Journal of Undergraduate Research, vol. 3, pp. 26-29, 2009. [14]. I. Buck and and J. Nickolls , “NVIDIA CUDA software and GPU parallel computing architecture”, In Microprocessor Forum, 2007. [15]. Cuda, https://en.wikipedia.org/wiki/CUDA, [Online]. [16]. J. D. Owens, M. Houston, D. Luebke, S. Green, J. E. Stone and a. J. C. Phillips, "GPU Computing," IEEE Proceedings, Vols. Vol. 96, No. 5, p. DOI: 10.1109/JPROC.2008.917757, May 2008. [17]. D. A. Huffman, "A Method for the Construction of Minimum Redundancy Codes," Proceedings of the Institute of Radio Engineers, vol. 40, pp. 1098-1101, 1952. ABSTRACT ACCELERATING HUFFMAN CODING FOR IMAGE COMPRESSION ON GPU Dijkstra's algorithm executed parallel on multi-core processor is the best option, but the cost of multi-core processors is extremely expensive. GPU launch to be a new choice for the field of parallel computing. There are many research methods to build algorithm Dijkstra that allows to run on the graphics processor and give positive results in terms of time than the execution on multiple processors. In parallel the implementation phase of the algorithm on GPUs requires data copy operations from the CPU to the GPU to calculate and vice versa when returning results. It is the speed limit of the algorithm calculations. In this paper, the author would like to present parallelization method Dijkstra algorithm to execute on the GPU with the method that does not copy the data to maximize the speed calculation algorithm. Keywords: Paralell Computing, GPU, Huffman, Paralell Coding. Nhận bài ngày 12 tháng 05 năm 2017 Hoàn thiện ngày 10 tháng 6 năm 2017 Chấp nhận đăng ngày 20 tháng 7 năm 2017 Địa chỉ: Khoa Điện Tử - Trường Đại Học Kỹ Thuật Công Nghiệp Thái Nguyên. * Email: daohuydu@tnut.edu.vn