劉振亮，孫煜東，閆 華

(太原理工大學(xué) 信息化管理與建設(shè)中心，太原 030024)

1 引 言

近年來(lái)，隨著激光雷達(dá)(LiDAR，Light Detection And Ranging)掃描技術(shù)的不斷進(jìn)步，掃描精度逐漸提高，掃描獲得的數(shù)據(jù)以指數(shù)級(jí)增長(zhǎng)，如果直接進(jìn)行數(shù)據(jù)傳輸或存儲(chǔ)，不僅成本高、實(shí)施難度大，而且很難實(shí)現(xiàn)，需要進(jìn)行數(shù)據(jù)壓縮等預(yù)處理再進(jìn)行傳輸.

常見(jiàn)的點(diǎn)云壓縮算法一般分為兩類：第一類是基于幾何學(xué)壓縮.首先對(duì)點(diǎn)云數(shù)據(jù)預(yù)處理，獲得網(wǎng)格模型，再對(duì)其進(jìn)行壓縮.典型算法有三角網(wǎng)格剖分法[1]、頂點(diǎn)聚類算法[2]、邊折疊法、小波分解法等.該類方法需要在網(wǎng)絡(luò)拓?fù)涞幕A(chǔ)上根據(jù)采樣點(diǎn)對(duì)網(wǎng)格進(jìn)行重構(gòu)，進(jìn)一步簡(jiǎn)化.簡(jiǎn)化效果好，但是需要構(gòu)造和維護(hù)龐大的拓?fù)湫畔ⅲ?jì)算量大，效率較低.第二類是基于點(diǎn)云數(shù)據(jù)本身的壓縮，直接對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行處理，典型算法有比例壓縮法、基于八叉樹的壓縮算法[3]、基于特征點(diǎn)的壓縮算法[4]和基于預(yù)測(cè)模式的壓縮算法[5].這類方法直接對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行簡(jiǎn)化，操作簡(jiǎn)單，尤其是以LASzip[6]、LASCompression[7]等為代表的預(yù)測(cè)模式算法應(yīng)用最為廣泛.本文選取LASzip無(wú)損壓縮作為研究對(duì)象.

然而，單純依靠壓縮算法遠(yuǎn)遠(yuǎn)不能實(shí)現(xiàn)數(shù)據(jù)實(shí)時(shí)處理的目標(biāo).隨著多核并行技術(shù)的不斷發(fā)展，僅僅依賴單核對(duì)數(shù)據(jù)進(jìn)行壓縮，并不能很好的解決壓縮速度慢的問(wèn)題，并行處理技術(shù)是提高LASzip壓縮算法壓縮、解壓縮速度的有效方法，目前高性能計(jì)算有兩大趨勢(shì)，并行計(jì)算集群和CPU處理器與GPU顯卡的異構(gòu)混合計(jì)算.在GPU加速方面[8]，利用GPU計(jì)算能力，將訓(xùn)練數(shù)據(jù)傳到GPU端進(jìn)行計(jì)算提高訓(xùn)練速度.盧敏等人[9]以地形因子計(jì)算為例，分析并測(cè)試了基于共享內(nèi)存模型的CPU多核并行模式與基于流處理器模型的GPU眾核并行模式的計(jì)算性能，在此基礎(chǔ)上實(shí)現(xiàn)了負(fù)載均衡的設(shè)備間任務(wù)劃分，進(jìn)行CPU與GPU異構(gòu)混合的并行技術(shù)改良研究.另一方面，多核CPU加速也是一個(gè)較熱的并行研究領(lǐng)域，宋剛等人[10]提出一種基于共享存儲(chǔ)的并行壓縮策略.通過(guò)Beowulf集群測(cè)試，并行化的gzip程序取得了極大的性能提升，壓縮速度顯著提升.

本文對(duì)傳統(tǒng)的LASzip壓縮算法進(jìn)行介紹，分析其耗時(shí)部分，結(jié)合該算法特點(diǎn)，比較不同核數(shù)和不同數(shù)據(jù)量分塊單元的串并行算法執(zhí)行時(shí)間及壓縮比，通過(guò)OpenMP技術(shù)優(yōu)化LASzip壓縮算法壓縮、解壓縮過(guò)程，實(shí)現(xiàn)了多核CPU并行加速.并將該算法在臺(tái)式機(jī)四核機(jī)器上進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)發(fā)現(xiàn)，OMP-LASzip并行壓縮算法通過(guò)損失少量壓縮比，換取數(shù)據(jù)壓縮、解壓縮速度的大幅提高，充分發(fā)揮了多核處理器的性能，在實(shí)時(shí)性傳輸和節(jié)省存儲(chǔ)空間上有很大的應(yīng)用空間.

2 背景知識(shí)

2.1 LAS格式

LAS文本格式從2003年發(fā)布至今，經(jīng)過(guò)數(shù)次修訂，目前已更新到LAS1.4版1.

表1 LAS1.4版本格式結(jié)構(gòu)Table 1 Structure and format of the LAS1.4

2.2 LASzip算法

LASzip算法是一種針對(duì)特定點(diǎn)云格式las開發(fā)的無(wú)損壓縮算法，采用預(yù)測(cè)模式進(jìn)行編碼，僅保存預(yù)測(cè)錯(cuò)誤的數(shù)據(jù)項(xiàng).LASzip對(duì)點(diǎn)數(shù)據(jù)記錄區(qū)按組成項(xiàng)目分塊壓縮，每一項(xiàng)都有獨(dú)立的版本號(hào)和壓縮模型，方便后續(xù)las數(shù)據(jù)類型的擴(kuò)展，壓縮方案也各不相同.LASzip算法以50，000個(gè)點(diǎn)為單位編碼，由于壓縮后每塊大小不同，壓縮器在文件末尾存儲(chǔ)一個(gè)塊列表明確每個(gè)數(shù)據(jù)塊的起始字節(jié).當(dāng)開始一個(gè)新塊時(shí)，LASzip壓縮器存儲(chǔ)第一個(gè)點(diǎn)作為原始字節(jié)，然后初始化熵編碼器，并將該點(diǎn)作為預(yù)測(cè)模式的初始值.接下來(lái)的點(diǎn)一項(xiàng)項(xiàng)由下面的壓縮模式順序壓縮.LASzip串行壓縮算法執(zhí)行步驟描述如下：

Step1.對(duì)于las文件中的公共頭文件區(qū)和變長(zhǎng)記錄區(qū)(包括擴(kuò)展變長(zhǎng)記錄區(qū))的內(nèi)容并不進(jìn)行壓縮，僅拷貝到壓縮后的輸出文件laz中.并將點(diǎn)類型的值增加128，以防las讀取器直接讀取laz文件.

Step2.點(diǎn)云數(shù)據(jù)分塊編碼.

Step3.POINT10數(shù)據(jù)項(xiàng)壓縮

1)壓縮器編碼6位掩碼用以指定強(qiáng)度、返回值、分類值、掃描角等級(jí)、用戶信息、點(diǎn)資源ID等屬性值與之前處理過(guò)的點(diǎn)屬性相比是否改變；

2)壓縮器對(duì)預(yù)測(cè)錯(cuò)誤(點(diǎn)屬性發(fā)生改變)的值進(jìn)行編碼.

Step4.GPSTIME10數(shù)據(jù)項(xiàng)壓縮

將雙精度浮點(diǎn)數(shù)GPSTIME10視為有符號(hào)64比特整型數(shù)，存儲(chǔ)當(dāng)前數(shù)據(jù)之前連續(xù)四個(gè)壓縮完成的GPSTIME10值取delta平均值.

Step5.RGB12數(shù)據(jù)項(xiàng)壓縮

1)las點(diǎn)云數(shù)據(jù)用16位無(wú)符號(hào)整型數(shù)記錄R，G，B通道.用256乘以8位顏色值，此時(shí)較低的8位為0；

2)LASzip對(duì)每個(gè)顏色通道的高位和低位分別壓縮：首先熵編碼6位指定哪些字節(jié)已經(jīng)作為符號(hào)轉(zhuǎn)變.對(duì)于所有字節(jié)都發(fā)生變化的，與前一個(gè)壓縮完成的數(shù)據(jù)項(xiàng)差分取模256進(jìn)行熵編碼.

Step6.WAVEPACKET13數(shù)據(jù)項(xiàng)壓縮

LASzip簡(jiǎn)單的熵編碼波形描述符索引，如果該數(shù)據(jù)點(diǎn)沒(méi)有波形信息和索引，則記為一個(gè)字節(jié)的無(wú)符號(hào)數(shù)0，否則表示可變長(zhǎng)記錄區(qū)已經(jīng)記錄波形信息.

Step7.BYTE數(shù)據(jù)項(xiàng)壓縮

一個(gè)las文件可能存在“額外的字節(jié)”，這是因?yàn)閘as頭文件定義的字節(jié)數(shù)大于各自的點(diǎn)類型字節(jié)數(shù).此時(shí)對(duì)每一個(gè)BYTE數(shù)據(jù)項(xiàng)進(jìn)行上下文熵編碼作為前一項(xiàng)BYTE數(shù)據(jù)項(xiàng)模256的差分.

2.3 OpenMP介紹

隨著多核處理器性能不斷提升，為了提高多核處理器利用率，決定引入OpenMP并行設(shè)計(jì)技術(shù)，設(shè)計(jì)人員只需研究系統(tǒng)瓶頸，重構(gòu)算法即可提升算法性能.OpenMP是高效的多核編程處理方案，以線程為基礎(chǔ)，通過(guò)編譯指導(dǎo)語(yǔ)句實(shí)現(xiàn)并行，在CPU核數(shù)擴(kuò)展性、方便性和可移植性上都有很大的優(yōu)勢(shì).使得串行應(yīng)用程序在多核共享存儲(chǔ)系統(tǒng)上，并行加速效率獲得大幅提升.

圖1 Fork-Join執(zhí)行模式流程圖Fig.1 Executive flow of Fork-Join

OpenMP技術(shù)根據(jù)fork-join模式，對(duì)可并行的部分利用OpenMP子句和命令創(chuàng)建多個(gè)子線程實(shí)現(xiàn)并行.在并行域階段，主線程和子線程同時(shí)工作；并行結(jié)束后，子線程隨之結(jié)束或掛起，程序返回主線程繼續(xù)執(zhí)行，并行算法中fork-join流程如圖1所示.

3 基于OpenMP的點(diǎn)云壓縮算法OMP-LASzip多核并行設(shè)計(jì)及實(shí)現(xiàn)

3.1 多核并行壓縮模型

基于OpenMP的多核并行技術(shù)為點(diǎn)云數(shù)據(jù)的并行壓縮處理提供了很好的平臺(tái)，為了改變?cè)即兴惴?，使其更好發(fā)揮作用，根據(jù)多核環(huán)境并行特性，借助Intel軟件工具VTune[12]對(duì)算法性能進(jìn)行分析，建立基于OpenMP技術(shù)和LASzip算法的多核并行設(shè)計(jì)模型OMP-LASzip.VTune是Intel一個(gè)比較強(qiáng)大的性能分析軟件，主要包括三個(gè)小工具：

1)Performance Analyzer：性能分析，找到軟件性能比較熱的部分，即性能瓶頸的關(guān)鍵點(diǎn)，幫助收集數(shù)據(jù)發(fā)現(xiàn)問(wèn)題.

2)Intel Threading Checker：用于查找線程錯(cuò)誤，檢測(cè)資源競(jìng)爭(zhēng)、線程死鎖等問(wèn)題.程序在并行化后，可以通過(guò)Threading Checker檢測(cè)是否存在多線程相關(guān)的錯(cuò)誤.

3)Intel Threading Profiler：線程性能檢測(cè)工具，多線程化可能存在負(fù)載不平衡，同步開銷過(guò)大等線程相關(guān)的性能問(wèn)題.

該工具可以幫助監(jiān)測(cè)任一線程任何時(shí)刻的運(yùn)行狀態(tài).

具體建立并行壓縮模型步驟如下：

Step1.使用Intel軟件工具VTune性能分析LASzip串行算法，發(fā)現(xiàn)熱點(diǎn)代碼；

Step2.分析串行算法耗時(shí)部分及熱點(diǎn)代碼的并行化可行性；

Step3.并行建模，實(shí)現(xiàn)并行LASzip算法；

Step4.使用Intel Threading Checker 和 Intel Threading Profiler對(duì)OMP-LASzip多核并行設(shè)計(jì)模型進(jìn)行調(diào)試，優(yōu)化代碼；

Step5.檢測(cè)算法執(zhí)行性能，包括是否達(dá)到負(fù)載平衡，加速比、多核利用率、線程運(yùn)行效率等情況；

Step6.使用Intel Threading Checker進(jìn)一步檢查算法性能和潛在漏洞；

Step7.若存在漏洞，則返回Step 3優(yōu)化算法.

在算法并行過(guò)程中，首先要找到程序耗時(shí)部分，因?yàn)檫@部分代碼一旦能夠?qū)崿F(xiàn)并行處理，將大幅度提高算法執(zhí)行效率.當(dāng)然，除了熱點(diǎn)代碼，執(zhí)行時(shí)間較長(zhǎng)或執(zhí)行頻率較高的算法實(shí)現(xiàn)并行也對(duì)提高系統(tǒng)運(yùn)行效率、提高加速比起到促進(jìn)作用.

3.2 OMP-LASzip算法基本原理

由2.2節(jié)LASzip串行算法步驟可知串行算法基本流程.大場(chǎng)景點(diǎn)云數(shù)據(jù)在壓縮過(guò)程中按數(shù)據(jù)項(xiàng)不同分塊壓縮，壓縮方式也各不相同.為了引入OpenMP技術(shù)，現(xiàn)從算法實(shí)現(xiàn)流程進(jìn)行分析.考慮到壓縮過(guò)程中連續(xù)數(shù)據(jù)之間雖然有一定程度的相關(guān)性，但是由于數(shù)據(jù)分塊壓縮時(shí)以50，000個(gè)數(shù)據(jù)點(diǎn)為一個(gè)單元，且壓縮過(guò)程中不涉及數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題，因此可以直接并行化.通過(guò)將數(shù)據(jù)分為n組，同時(shí)分配樣本數(shù)據(jù)給n個(gè)線程，每組數(shù)據(jù)使用一個(gè)線程來(lái)實(shí)現(xiàn)LASzip算法的并行壓縮.采用OpenMP相關(guān)語(yǔ)句和命令來(lái)給并行壓縮的數(shù)據(jù)分配多個(gè)線程.

本文利用OpenMP多核并行技術(shù)對(duì)LASzip算法進(jìn)行并行化研究.分析LASzip串行程序中耗時(shí)部分，同時(shí)分析耗時(shí)部分的可并行性，通過(guò)OpenMP添加并行語(yǔ)句對(duì)原有串行程序進(jìn)行并行化，提出基于OpenMP的點(diǎn)云無(wú)損并行壓縮算法OMP-LASzip.

3.3 OMP-LASzip算法實(shí)現(xiàn)

LASzip算法只對(duì)點(diǎn)數(shù)據(jù)記錄區(qū)進(jìn)行壓縮，對(duì)公共頭文件區(qū)、變長(zhǎng)記錄區(qū)和擴(kuò)展變長(zhǎng)記錄區(qū)并不進(jìn)行壓縮，僅拷貝到輸出文件中，因此計(jì)劃LASzip算法執(zhí)行分兩部分進(jìn)行：

圖2 OMP-LASzip算法流程圖Fig.2 Flow of OMP-LASzip algorithm

1)讀入點(diǎn)云文件.僅保留點(diǎn)數(shù)據(jù)記錄區(qū)內(nèi)容，將不需要壓縮的其他數(shù)據(jù)項(xiàng)直接寫入輸出文件；

2)壓縮點(diǎn)云數(shù)據(jù).為了減少壓縮算法運(yùn)行時(shí)間，提高點(diǎn)云數(shù)據(jù)處理效率，需要對(duì)壓縮過(guò)程實(shí)現(xiàn)OpenMP并行化.串行傳播的過(guò)程是點(diǎn)云數(shù)據(jù)分塊后順序壓縮的過(guò)程，使用并行語(yǔ)句后，數(shù)據(jù)分組并行壓縮提高壓縮效率.調(diào)用lasmerge函數(shù)對(duì)數(shù)據(jù)以n個(gè)點(diǎn)為單位進(jìn)行分塊，分配給多個(gè)線程并行壓縮.

采用一個(gè)讀線程，一個(gè)寫線程，多個(gè)壓縮線同時(shí)工作.其中讀線程負(fù)責(zé)讀數(shù)據(jù)，循環(huán)檢測(cè)緩沖區(qū)，將空緩沖區(qū)填滿；寫線程負(fù)責(zé)寫數(shù)據(jù)，將壓縮完的數(shù)據(jù)按照讀的順序?qū)懙捷敵鑫募?為了保證讀寫順序一致，即壓縮文件按順序?qū)懭胼敵鑫募?，引入讀寫順序隊(duì)列機(jī)制.當(dāng)讀線程檢測(cè)到一個(gè)緩沖區(qū)為空，就從原文件中讀一塊數(shù)據(jù)加入到緩沖區(qū)中，同時(shí)將該緩沖區(qū)的序號(hào)加入到讀寫順序隊(duì)列中，這樣，寫線程就必須按著讀寫順序隊(duì)列里面存儲(chǔ)的緩沖區(qū)序號(hào)寫輸出文件，由于緩沖區(qū)和輸出隊(duì)列一一對(duì)應(yīng)，這個(gè)序號(hào)也就是輸出隊(duì)列的序號(hào)，寫線程就可以從這個(gè)序號(hào)對(duì)應(yīng)的輸出隊(duì)列中取得數(shù)據(jù)，寫入輸出文件，從而保證寫文件時(shí)保持原文件的順序.同時(shí)保證每個(gè)文件(除了最后一個(gè))數(shù)據(jù)量近似相等，多核運(yùn)行時(shí)負(fù)載均衡.下圖為對(duì)點(diǎn)數(shù)據(jù)記錄區(qū)OMP-LASzip算法數(shù)據(jù)壓縮部分詳細(xì)流程圖(見(jiàn)圖3)：

圖3 OMP-LASzip算法數(shù)據(jù)壓縮部分詳細(xì)流程圖Fig.3 Flow of partial details of OMP-LASzip algorithm

解壓過(guò)程原理相同，調(diào)用lasmerge函數(shù)對(duì)帶解壓文件以n個(gè)點(diǎn)為單位分塊，運(yùn)用OpenMP技術(shù)，對(duì)數(shù)據(jù)塊并行解壓縮，以下是并行順序壓縮的偽代碼：

#pragma omp parallel for

//OpenMP的for循環(huán)并行語(yǔ)句

for(i=0；i<(totalnum/n)；i++)

//totalnum為點(diǎn)云總數(shù)，n為每塊點(diǎn)云包含的數(shù)量，i為點(diǎn)云塊數(shù)

{

OMP-LASzipPOINT( ) ；//POINT10數(shù)據(jù)項(xiàng)壓縮

OMP-LASzipGPSTIME()；//GPSTIME10數(shù)據(jù)項(xiàng)壓縮

OMP-LASzipRGB ( ) ；//RGB12數(shù)據(jù)項(xiàng)壓縮

OMP-LASzipWAVEPACKET( ) ；//WAVEPACKET13數(shù)據(jù)項(xiàng)壓縮

OMP-LASzipBYTE( ) ；//BYTE數(shù)據(jù)項(xiàng)壓縮

}

在并行設(shè)計(jì)模型和OMP-LASzip算法實(shí)現(xiàn)之后，考慮到如果串行編程存在錯(cuò)誤，勢(shì)必會(huì)影響到并行算法的實(shí)現(xiàn)，因此還需要對(duì)結(jié)果進(jìn)行調(diào)試與優(yōu)化，以保證計(jì)算性能達(dá)到最優(yōu)效果.采用多線程并行完成工作雖然可以提高系統(tǒng)運(yùn)行效率，但是也提高了程序設(shè)計(jì)錯(cuò)誤的風(fēng)險(xiǎn).因此，在算法并行化完成后，對(duì)處理結(jié)果進(jìn)行進(jìn)一步的調(diào)試與優(yōu)化十分必要.

4 實(shí)驗(yàn)結(jié)果與分析

本文的實(shí)驗(yàn)數(shù)據(jù)來(lái)源文獻(xiàn)2，選取5個(gè)數(shù)據(jù)量大于2G的點(diǎn)云數(shù)據(jù)集，數(shù)據(jù)分別按5，000，000、7，500，000、10，000，000、12，500，000、15，000，000個(gè)點(diǎn)為單位分塊壓縮.實(shí)驗(yàn)平臺(tái)為臺(tái)式機(jī)Intel(R) Core i7-4770四核八線程處理器，主頻3.50GHz.開發(fā)環(huán)境是在Windows 7 Professional X64位系統(tǒng)上安裝Microsoft Visual Studio 2013，OpenMP直接在Microsoft Visual Studio 2013中配置.由于算法引入讀寫線程，則并行壓縮線程數(shù)最多為6.為保證LASzip算法在串行設(shè)計(jì)時(shí)的正確性，確保并行實(shí)現(xiàn)的順利進(jìn)行，實(shí)驗(yàn)計(jì)劃先對(duì)OMP-LASzip算法串行程序進(jìn)行測(cè)試，并將實(shí)驗(yàn)數(shù)據(jù)在并行環(huán)境中進(jìn)行實(shí)驗(yàn)，表2為OMP-LASzip算法壓縮結(jié)果性能比較，定義壓縮比：

(1)

其中s′為壓縮后文件大小，s為原始文件大小.統(tǒng)計(jì)10次取平均值得到并行多核LASzip壓縮算法相對(duì)串行算法的壓縮比誤差：

e=|kn-k|

(2)

其中，kn表示以n個(gè)點(diǎn)為單位的點(diǎn)云數(shù)據(jù)壓縮比，k表示原始點(diǎn)云文件壓縮比.

表2 OMP-LASzip算法壓縮結(jié)果性能比較Table 2 Comparison of the compress result of OMP-LASzip

實(shí)驗(yàn)發(fā)現(xiàn)，數(shù)據(jù)分塊后壓縮較原串行壓縮，壓縮比有所下降，這是因?yàn)閿?shù)據(jù)分塊后每個(gè)數(shù)據(jù)塊的起始數(shù)據(jù)無(wú)法使用預(yù)測(cè)模式進(jìn)行編碼， 因此造成壓縮比降低， 但從結(jié)果可知誤差維持在1%以內(nèi)， 驗(yàn)證了并行算法的可行性.實(shí)際上，并行壓縮就是在損失少量壓縮比的前提下?lián)Q取壓縮速度的提高.以CA_042_NE_PtCl.las實(shí)驗(yàn)結(jié)果為例，以下為多線程點(diǎn)云數(shù)據(jù)并行分塊壓縮的時(shí)間.

表3 多線程下點(diǎn)云數(shù)據(jù)并行分塊壓縮時(shí)間(單位：s)Table 3 Time of the compression of OMP-LASzip in multi-thread

圖4 多線程點(diǎn)云數(shù)據(jù)并行分塊壓縮時(shí)間示意圖Fig.4 Diagram of compress time in multi-thread of point cloud data

加速比是衡量并行程序的指標(biāo)，即用最優(yōu)執(zhí)行時(shí)間除以并行執(zhí)行時(shí)間所得到的比值，加速比可以描述程序并行后獲得的性能收益，公式如下：

(3)

其中，s(p)為加速比，t1為最優(yōu)串行算法執(zhí)行時(shí)間，ti為線程數(shù)為i時(shí)的并行算法執(zhí)行時(shí)間.從表4可知當(dāng)n=5，000，000時(shí)，線程數(shù)為2時(shí)，理想加速比為2，但實(shí)驗(yàn)發(fā)現(xiàn)此時(shí)加速比達(dá)到2.21，出現(xiàn)了“超線性加速比現(xiàn)象”.理論上講，當(dāng)在p個(gè)處理器上運(yùn)行的并行程序，其理想的運(yùn)行速度應(yīng)為串行程序運(yùn)行速度的p倍，但是由于通信延遲，負(fù)載不均衡等原因，很難達(dá)到理想加速比.然而實(shí)驗(yàn)顯示，線程數(shù)為2時(shí)，加速比達(dá)到2.21，超過(guò)理想加速比2，這是因?yàn)椴⑿谐绦蛲瓿闪溯^少的工作，即一般情況下，并行執(zhí)行時(shí)所要訪問(wèn)的數(shù)據(jù)都駐留在每個(gè)處理器的cache中，而順序執(zhí)行時(shí)必須訪問(wèn)存儲(chǔ)器系統(tǒng)中運(yùn)行較慢的部分，因此由于并行程序所完成的工作量比串行程序的少，從而出現(xiàn)了超線性加速比現(xiàn)象.

從表4可以看出，當(dāng)分塊點(diǎn)數(shù)量恒定時(shí)，加速比與線程數(shù)呈正相關(guān).實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)線程數(shù)為6時(shí)與線程數(shù)為4相比加速比提高并不理想，這是由于系統(tǒng)硬件條件的限制，即使所有線程都分配到任務(wù)，系統(tǒng)CPU接近100%，壓縮程序的執(zhí)行效率并不會(huì)有很大提升，因?yàn)榫€程的增加必然會(huì)提高系統(tǒng)開銷，影響程序性能.

同時(shí)實(shí)驗(yàn)可以看到當(dāng)線程數(shù)恒定時(shí)， 隨著單位塊內(nèi)點(diǎn)云數(shù)量的增加， 加速比并沒(méi)有相應(yīng)增加，而是出現(xiàn)了小幅波動(dòng)甚至下降的結(jié)果，這是因?yàn)殡S著單位點(diǎn)云數(shù)量增多，數(shù)據(jù)量增

大，點(diǎn)云塊數(shù)量減少，容易造成負(fù)載不均衡反而降低算法運(yùn)行效率.由表4可以看出，當(dāng)單位點(diǎn)云數(shù)量n=5，000，000時(shí)隨著線程數(shù)增加，加速比隨之升高，與其他單位點(diǎn)云數(shù)量相比性能提升最優(yōu).同時(shí)，當(dāng)線程數(shù)為4時(shí)(考慮到讀寫線程，實(shí)際運(yùn)

表4 多線程加速比實(shí)驗(yàn)結(jié)果Table 4 Data chart of different thread of speed-up ratio

行線程數(shù)為6)，加速比達(dá)到3以上，最高達(dá)到3.98，優(yōu)化效果顯著；當(dāng)線程數(shù)增加到6時(shí)，加速比較線程數(shù)為4時(shí)略有提高，此時(shí)8線程全部運(yùn)行，CPU利用率過(guò)高，不利于系統(tǒng)正常運(yùn)行，因此決定采用1個(gè)讀線程，1個(gè)寫線程，4個(gè)壓縮線程共同操作，保證各壓縮線程負(fù)載平衡，達(dá)到最優(yōu)運(yùn)行效果.

5 結(jié) 論

在對(duì)大量旅游景點(diǎn)數(shù)據(jù)進(jìn)行三維重建過(guò)程中，對(duì)采集到的點(diǎn)云數(shù)據(jù)進(jìn)行實(shí)時(shí)處理、壓縮、傳輸，對(duì)于提高建模效率、保證數(shù)據(jù)真實(shí)性、完整性具有重要意義.本文針對(duì)LASzip算法，分析其耗時(shí)部分，引入OpenMP技術(shù)，實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)分塊并行壓縮OMP-LASzip算法，提高點(diǎn)云數(shù)據(jù)處理效率.實(shí)驗(yàn)結(jié)果表明，與原串行算法相比，并行算法在損失少量壓縮率的情況下，壓縮速度顯著提升，保持負(fù)載均衡，同時(shí)隨著核數(shù)增加，加速比也在增加.實(shí)驗(yàn)結(jié)果顯示，當(dāng)單位點(diǎn)云數(shù)量n=5，000，000，壓縮線程為4時(shí)運(yùn)行效果最佳，驗(yàn)證了該算法的可行性、有效性和可擴(kuò)展性，解決了現(xiàn)有點(diǎn)云壓縮方法處理效率低、實(shí)時(shí)性差的問(wèn)題.