논문 및 사진 출처

Han, Meng, et al. “QuickFPS: Architecture and Algorithm Co-Design for Farthest Point Sampling in Large-Scale Point Clouds.” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (2023).

0. Abstract

Farthest point sampling은 point cloud processing을 위한 critical kernel임
point cloud의 scale으로 인해서 FPS는 엄청나게 많은 메모리를 사용하고, 이에 따라 large-scale point cloud를 processing하는데에 방해가 됨
본 연구에서는 QuickFPS 구조와 point coulds을 위한 large scale 알고리즘을 제안함
- 먼저, FPS의 특성을 systemically analyze하고, bucket-based FPS 알고리즘을 제안함
  - 해당 알고리즘은 two level tree data 구조를 사용해서 large-scale point cloud들을 multiple bucket으로 organize함
  - bucket을 위한 merged computation 과 implicit computation 을 통해서 메모리 사용량과 computational cost을 확연하게 줄일 수 있었음

1. Introduction

전형적인 point cloud는 매 1/10th 초 마다 120,000개의 point들을 생성하고, 기술이 진보됨에 따라서 point cloud의 개수는 기하급수적으로 늘고 잇음
Large scale point cloud에서 downsampling은 필수적인 step임.
- Farthest point sampling (FPS) algorithm은 downsampling 방법들 중 가장 광범위하게 사용되고 있는 기법으로, original spatial characteristics을 최대한 남겨줄 수 있음.
  - 이전 연구들은 large scale point clouds에서는 random sampling보다 FPS가 더 좋은 성능을 보임을 확인해 줬음.
    - 그럼에도 불구하고 FPS은 너무 많은 computation을 요하기 때문에 전체 프로세스에 bottleneck이 될수밖에 없음.
    - 이러한 issue를 해결하기 위해서 case study를 본 연구에서 진행했고, 16,384개의 input point가 neural networks(NN)에 들어왔을 때 FPS를 사용하면 30~70%의 runtime을 FPS 처리를 위해서 사용해야한다는 것을 발견했음.
  - FPS는 루프로 이루어진 2개의 레이어로 구성된다.
    - inner loop은 높은 computational paralleism을 요함
      - 가장 common하게 사용되는 해결 방안은, FPS를 고사양 GPS를 사용해서 처리하게끔 하는 건데.. 불행히도 만약 point cloud의 scale이 커지면, 상당한 서은ㅇ 차이를 보이게됨.
        
        본 연구에서는 point cloud 10^6 개에서 10%의 pints들을 고사양 gpu를 사용한 FPS를 가지고 sampling하려고 했음.
        
        대부분의 computation은 memory trnasaction에서 발생했다는 것을 확인하고, 가장 주된 이유가 높은 메모리 footprint때문이라고 파악함.
    - domain-specific hardware acclerator들은 co-designing 구조 및 알고리즘을 통해서 performance gap을 줄여줄 수 있음. 몇몇의 hardware accelerator들은 point cloud processing을 위해서 제안되었음.
    - 하지만 본 저자들의 knowledge에 한해서는 FPS를 위한 유일한 accelerator은 pointACC임.
      - Point ACC는 MPU, MMU, systolic carray 의 6 stage pipeline으로 구성되어 있고, 모든 point cloud가 on-chip buffer에 load되었을 때에만 효과적으로 FPS를 처리할 수 있다는 limitation이 존재함.
        
        하지만, PointACC는 point size의 크기가 on-chip memory capacity를 초과했을 때, on-chip SRAM과 off-chip DRAM 사이에서 데이터 교환이 자주 일어나야함.
        
        즉, 효과적으로 FPS를 처리하기 힘들다는걸 말하고 싶었던 것 같음
위와 같은 문제점을 해결하기 위한 방안으로 QuickFPS를 제안함.

QuickFPS은 architecture이자 co-design hardware accelerator 알고리즘임.
- 먼저 저자들은 FPS의 특성을 systematically 분석했음. 그 결과, 각 iteration마다 오직 작은 개수의 point들만이 processed 된다는 것을 발견함.
- 두번째로, bucket based algorithm은 two-level tree 알고리즘을 사용해서 large scale point cloud들을 여러개의 point bucket들로 나누었음. 이후, spatial geometric 특성을 기준으로 오직 소수의 necessary한 bucket들만 process되도록 함.
- 마지막으로, bucket based FPS의 장점을 극대화하기 위해서, QuickFPS라는 효과적인 알고리즘 및 co-design accelerator을 제안함.
  - QuickFPS는 bucket-level pipeline들과 point level 병렬화를 처리함.
  - 더 specific하게는 accelerator는 4 sage pipeline을 통해서 노드 처리 필요성을 판단했음.
    - 데이터 병렬성을 활용하기 위한 PE와 mesh를 통합하기도 함.
      - 이거 무슨말인지 자세히 이해는 안됨

2. BACKGROUND AND MOTIVATION

2.A Point cloud data

point cloud P는 point들로 이루어져 3D scene이나 물리적인 object를 represent함
P는 (x,y,z)의 cartesian coordinate 시스템으로 represent됨.
image와 달리, point cloud는 object간의 scene이나 spatial relationship에 관한 3D geometric information을 직접적으로 보존함.

2.B Farthest Point Sampling

FPS는 original spatial charcteristic 을 보존해줌과 동시에 효과적으로 point의 개수를 감소시켜줌
FPS는 반복적으로 point를 선택하면서 point cloud의 subset을 생성하는 알고리즘임.
- 이번 iteration에서 sampled된 point으로부터 더 먼 곳의 point들이 다음 iteration에서 sampling됨
일반적으로 FPS는 두가지 key step을 매 iteration마다 실행함.
1. samped된 point에서 모든 point들로의 거리를 dist 함수를 통해서 구함
2. argmax함수를 통해서 maximum distnace를 구함.
3. k iteration이후, sampled point set이 생성됨
point cloud P에서 sample set S_k가 아래와 같이 주어졌을 때, dist(q, S_k)는 point q와 이전에 sample된 point들인 Sk간의 거리를 define해줌
\[dist(q,S_k) = min(d(q,s_i))),S_k = \left\{ s_i|i = 1...k\right\}\]
- 다음 샘플링 포인트는 point p에서 발생해야함. p는 이전 sample들에서 가장 먼 거리에 위치한 point
  \[p = argmax(dist(q, S_k))\]
- 모든 sampled point에 대한 거리를 계산하는 것 대신에, 아래 식으로 대체될 수 있음
  - 임시변수 d(q, Sk-1)와 d(q, Sk-1) 사이의 최소값인 d(q, Sk)의 거리 계산으로 단순화할 수 있다는 것을 설명한 것
    - Figure 1에서 이를 확인할 수 있음.
      - 본 예제에서는 S2 ={P4, P10}이 샘플링 된 상황임.(P4는 첫번째 random point이고, P10는 P4로부터 가장 멀리 떨어져 있는 포인터임)
      - 이후, 각 point p에서 샘플링된 point으로 까지의 거리를 계산하고, 최종적으로 P3이 선택됨.
    - 식 3으로 인해서 computational cost가 줄어들기는 했지만, 계속 반복적인 작업이 진행되어야 하는 알고리즘의 본질적인 특성으로 인한 문제점이 있음.
      - 만약 우리가 size N인 point cloud들로부터 K개의 point들을 sampling하고자 한다면, 적어도 K-1번 의 전체 point cloud으로의 엑세스가 발생해야함.

2.C Performace characterizations

FPS를 characterize하믕로서 bottleneck을 이해하고 optimization 기회를 엿보고자 했음.

Workload Breakdown

Figure 2는 3개의 point cloud NN에 관한 FPS의 time distribustion을 나타냈음.
- 각 point cloud NN은 16,384 point들을 input으로 가졌고, processing동안 model들은 몇번의 FPS operation을 통해서 point cloud을 small scale으로 downsampling했음.
- (a)에서 확인할 수 있듯, FPS는 전체 operation들 중 상당히 높은 time distribution percentage를 보이고 있음.

Runtime Analysis

Figure 2(b)의 수평적인 dashed line은 point cloud의 생성 frequency를 나타냄. 즉, point cloud의 처리는 real-time requirement를 충족해야함. 수직 dashed line은 Semantic KITTI datset에 포함된 point cloud의 평균 size을 나태내고, 이를 통해서 확인할 수 있는 것은, 적어도 4.8x의 gap이 존재하다는 것임.

Latency breakdown

Figure 3은 point cloud들의 크기에 따라서 gpu 실행 시간을 Memory, execution, control, other 부분으로 나눈 것
- Figure에서 확인할 수 있듯, memory operation이 가장 큰 bottleneck 이 memory operation이라는 것을 알 수 있고, point의 개수가 증가함에 따라 memory operation 에 대한 latency는 기하급수적으로 늘어남을 확인할 수 있음.

Memory access

큰 memory footprint는 큰 memory access을 요함. FPS에서는 각 pint들은 12 byte정도가 소요되고, 이전 샘플링된 점과의 거리를 나타내는데에는 4 바이트가 사용됨.
백만개의 point을 사용하면, FPS를 위한 memory footprint는 15.26MB가 사용될 것.

2.D Prior works

이전 연구들이 point cloud accelerator들을 제안했지만, fPS operation에 대해서 point cloud accelerator을 제안한 연구는 PointACC뿐이었음.
- PointACC는 mapping unit architecture을 사용해서 FPS를 가속화했음.
  - mapping unit architecture of Point ACC
    - aprallel distance calculatoin unit을 통해서 multiple points으로부터의 거리를 simultanelously하게 계산할 수 있도록 함.
    - fetch-calculate-sort pipeline을 통해서 on chip memory access랑 계산 작업을 오버플로우 함.
      - 여기서 overflow란, 데이터 패치나 계산 정렬에 대한 지연 없이 평소 메모리 용량을 초과하는 데이터 작업량을 처리할 수 있도록 한것.. 이라고 gpt가 설명해줌
    - 근데 Point ACC는 memory 사용량이 너무 많다는 것이 단점이. 따라서, large-scale point cloud들에 대해서 적용하기에는 무리가 있음.
    - 좀 더 자세하게는 point cloud의 사이즈가 acclerator의 on chip 용량보다 커지면, Point ACC는 on-chip SRAM과 off-chip DRAM 사이에서 data의 교환이 이루어져야하고, 이는 latency와 energy cost를 발생하게 함.
- random sampling을 통해서 point cloud downsampling을 할수도 있지만, FPS보다 정확도가 너무너무 떨어짐..

2.E Opportunity for memory access reduction

이전의 FPS 방법은 각 point 에 대한 distance 정보를 업데이트 하기 위해서 DRAM에 있는 모든 point cloud들을 loading 해야하기 때문에, 엄청나게 많은 memory accesses가 발생했음.
근데, 위의 식 3에서도 확인할 수 있듯, 아래 경우에만 샘플링된 거리를 업데이트 해주면 됨.
- 가장 최근에 샘플링 된 점까지의 거리 < 이전에 샘플링된 점까지의 거리
case study에서 확인할 수 있듯, 대부분의 iteration에서는 오직 작은 숫자의 pont들만 distance의 update이 발생함.
- 아래 figure은 distance 정보가 바뀐 point의 비율을 나타낸 plot으로, sampled points==iteration이라고 봐도 무방함.
- 따라서, 본 연구에서는 정렬되지 않은 point cloud들을 여러개의 bucket으로 나누고, 만약 해당 버킷이 특정한 조건에 만족되면 메모리 access을 하지 않도록 해당 bucket을 버리는 방법을 제안함.

3. Bucket-based Farthest point sampling

3.A Point Bucket

point bucket은 point cloud의 bounding box임
아래 figure과 같이, point cloud는 4개의 독립적인 그룹으로 분리됨.
아래 figure은 point cloud의 two-level tree 를 나타냄
- first level(==bucket-level)에는 현재 bucket의 중요한 정보를 저장함.
- second level(==point-level)에는 버킷 속에 들어있는 포인트들의 배열임

Building a two-level tree

K-d tree를 사용해서 point cloud를 split했음
- K-d tree는 binary tree로 point cloud space를 작은 영역으로 나누어줌(거의 같은 수의 point들로 나누어질 수 있도록)
- 방법
  1. maximum range에서 dimension에 따라서 point들을 정렬함
  2. 두개의 group으로 분리함
    1. splitting process는 원하는 버킷의 수가 생성될 때까지 반복됨

Bucket far point

sampled point set S_k와 ,bucket B_i 그리고 point cloud P가 주어진 경우
- bucket far point는 버킷 내부에서 S_k에서 제일 먼 point으로 정의됨
FPS 가 가장 먼 거리에 있는 포인트를 sampled point로 선택하기 때문에, 다음 sampled point는 bucket far point 중에서 선택되게 됨.
- 각 버킷 속 point q와 Sk의 max값들을 계산하고, sampled point set Sk와 bucket 의 bucket far point과 Sk의 거리중 가장 최대값을 반환함.
bucket 의 상세한 데이터 구조는 아래와 같음
- boundary
  - bucket의 minimum, maximum 좌표가 포함됨
    \[[(x_{min}, x_{max}), (y_{min}, y_{max})]\]
- pointsPtr
  - 현재 bucket의 point data에 대한 DRAM의 시작 주소를 포함함
- farpoint
  - 퍼킷 안에 있는 점들 중 sampled point으로부터 가장 멀리 떨어져 있는 point를 나타냄
- merge buffer
  - 이후 iteration들에서 처리되어야하는 sampled points들이 저장됨

3.B Bucket-Based computation framework

불필요한 연산을 발견하고 제거하는 것이 key idea
merged computation과 implicit computation을 bucket-based framework에서 제안함
- merged computation
  - bucket 의 거리 계산을 postponing 및 merging 하며 memory access cost 를 줄여줌
  - 현재 iteration에서 몇몇의 bucket에 대한 거리 계산은 필수적이지 않을 수 있음.
    - m^b_{i}s{k-1}
  - dist → m~와 이전 sampled point인 Sk-1와의 거리를 나타냄
  - d → distance
    - 식 5를 식 3에 대입해서 생각해보면, 만약 dist()가 d()보다 작으면, $dist(m^{B_i}{S{k-1}},S_{k-1})$가 $dist(m^{B_i}{S{k-1}},S_{k})$와 같아짐
      - 따라서, far point of bucket b_i under S_k-1은 far point under S_k와 같음.
      - 일반적으로, 다음 sampled point S_k+1을 얻기 위해서는, 각 버킷의 bucket far point m_sk^bi을 얻고, 그중에서 가장 먼 point를 선택해야함.
      - 근데 식 5번을 만족하는 경우 bucket Bi에 대한 계산을 지연시키고, 가장 최근의 sampled point을 merge buffer으로 보냄.
    - Figure 7(a)가 이에 대한 예시임
      - 5<8 이기 때문에, Sk만 merge buffer으로 보내서 거리에 대한 계산이 이루어지도록 함
- implicit computation
  - 마지막으로 샘플링된 point는 bucket에서의 모든 point으로부터 떨어져 있기 때문에, distance metric에 대한 거리는 바뀌지 않음.
  - 이러한 경우, distance calculation을 건너뛸 수 있음.
  - 이러한 goal을 이루기 위해서 bucketDist(p,Bi)를 정의함.
    - bucketDist(p,Bi)는 point p와 bucket Bi의 bounding box간의 최소 거리를 의미함.
    - 특히, bucket distance는 point가 bucket의 bounding box 속에 포함된 경우 0이 됨
  - sampled point set Sk와 point bucket Bi에 대해서, implicit computation의 boundary condition은 아래와 같이 정의될 수 있음.
    - 기본적으로, 좌변은 bucket Bi에 있는 모든 point간의 거리의 상한선(가장 먼 거리)를 의미함. 우변은 최소 거리니까.. Bi와 마지막으로 sampling된 sk point간의 최소 거리를 의미함.
      - 만약 식 6번이 충족되면, Bi에 있는 point들은 latest sampled point으로부터 멀리 떨어져 있다는 것을 의미하고, S_k-1까지의 거리와 S_k까지의 거리가 같게됨을 의미함.
        
        익
      - 예를 들어 , 아래 figure을 참고할 수 있음.
        
        빨간색 : sampled point
        
        노란색 : buket far point
        
        bucket Bi에 있는 모든 point과 sampled된 점들 간의 거리로 따졌을 때, 가장 멀리 떨어져 있는 점
        
        bucket dist
        
        bucket Bi와 마지막으로 샘플링된 point sk간의 거리들 중 최소값 (수직으로 내린 선의 거리)
        
        예시와 같이 6<7이라는 것은,.. sk와 Bi속의 포인트들이 충분히 멀다는 것
        
        왜냐하면 st가 sampling되었다는 것은.. 이미 먼 점이라고 판단되었다는건데, 이거보다 sk와 Bi간의 거리가 더 머니까 ㅇㅇ
        
        따라서 dist(~,S_k-1)은 dist(~,S_k)와 동일한 값을 가지게 됨
        
        왜냐? S_k-1 집합에 S_k가 포함되어 있기 때문
        
        그래서 Bi 속의 point들과 sk에 대한 연산을 안해도 됨. pass가능
  # 개념 정리