Tăng tốc độ giải thuật mã hóa Huffman cho nén ảnh số bằng GPU

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