• Vector and Numerics Group이 제공하는 것들
  • Accelerate Framework -> 이미지, 신호 처리등
    • vImage
    • vDSP
    • vForce
    • BLAS
    • LAPACK
    • Linear Algebra
    • Sparse BLAS(new)
  • Libraries
    • libm
    • simd(updated)
    • compression(new)
• compression

  • 무손실 압축을 위한 라이브러리

  • 알고리즘 선택 기능

  • 통일된 API

  • 에너지 효율 및 속도면에서 좋음

  • 알고리즘 속도 비교

    • 밸런스파: zlib, lzfse
    • 압축률 높고, 느림: lzma
    • 압축률 낮고 빠름: lz4

  • 위 알고리즘은 모두 라이브러리에서 제공되며, 애플 하드웨어에 최적화되어 있음 -> 코드 변경 없이 자동으로 성능 향상과 보안 강화 가능

    

  • lzfse의 등장 - 애플에서 만든 압축 알고리즘

    • zlib의 압축 알고리즘이 더이상 최적화할 여지가 보이지 않았음
      • entropy 부분인 hufmann이 병목이자, 개선하기 힘든 부분
    • 그래서 허프만 부분을 finite-state-entropy라는 기술로 교체
      • LZFSE = Lempel-Ziv + Finite State Entropy
    • 그래서 zlib과 호환되지만 좀더 빠르고 효율적인 알고리즘이 됨
    • 최신 마이크로 아키텍쳐 구조에 좀 더 알맞음(zlib에 비해)

  • API 종류

    • Buffer

#include <compression.h>

// encoding
const unit8_t * src; // 압축할 데이터
size_t src_size; // src의 크기
uint8_t * dst; // 결과를 받을 포인터
size_t dst_capacity; // dst에 할당된 포인터
compression_algorithm algorithm = COMPRESSION_LZFSE;

size_t dst_size = compression_encode_buffer(
		dst, dst_capacity,
		src, src_size.
		NULL, algorithm
		);

// decoding 
#include <compression.h>

const_uint8_t *src; // data to decompress
size_t src_size;
uint8_t * dst;
size_t dst_capacity;
compression_algorithm algorithm = COMPRESSION_LZFSE;

// 할당량이 부족하면 결과값이 잘린다.
size_t dst_size = compression_decode_buffer(
				dst, dst_capacity,
				src, src_size,
				NULL, algorithm
			);

• Stream API
  • init -> (process)* -> destroy

# include <compression.h>

// encode
// init
compression_stream stream;
compression_stream_operation op = COMPRESSION_STREAM_ENCODE;
compression_algorithm algorithm = COMPRESSION_LZFSE;

int status = compression_stream_init(&stream, op, algorithm)

// COMPRESSION_STATUS_OK: success
// COMPRESSION_STATUS_ERROR: an error occurred

// process
stream.src_ptr = src;
stream.src_size = src_size;
stream.dst_ptr = dst;
stream.dst_size = dst_capacity;

int status = compression_stream_process(&stream, 0);

// COMPRESSION_STATUS_OK: src empty or dst full, more calls needed
// COMPRESSION_STATUS_ERROR: an error occurred

// src_ptr, src_size, dst_ptr, dst_size가 업데이트 되었다.

// process(end)
stream.src_ptr = src;
stream.src_size = src_size;
stream.dst_ptr = dst;
stream.dst_size = dst_capacity;

int status = compression_stream_process(&stream, COMPRESSION_STREAM_FINALIZE);

// COMPRESSION_STATUS_OK: src empty or dst full, more calls needed
// COMPRESSION_STATUS_END: all data has been processed
// COMPRESSION_STATUS_ERROR: an error occurred

// src_ptr, src_size, dst_ptr, dst_size가 업데이트 되었다.
(destroy)
int status = compression_stream_destroy(&stream);

// COMPRESSION_STATUS_OK: success
// COMPRESSION_STATUS_ERROR: an error occurred

// decode도 encode와 유사

• SIMD
  • basic
    • 2,3,4 차원 벡터와 행렬을 다루는 라이브러리
    • C, C++, Objective-C에서 지원 -> Swift도 지원
    • Metal shading language를 거의 미러링하고 있음
  • 다른 라이브러리에 비해 가지는 강점
    • 명시적인 포인터 연산 없음
    • 간결한 사용법
  • vector
    • float, double, 32비트 정수
    • 2,3,4 중 하나의 길이를 가짐
    • 기본적인 연산(원소별 덧셈, 스칼라 배, 내적, 외적)

func replect(x: float3, y: float3) -> float3 {
	return x- 2 * dot(x,n) * n
}

• 수많은 기하, 셰이더, 수학 함수 기본 지원
• Matrix Types
  • float NM, double NM 지원
  • N,M은 2,3,4중 하나
  • column major방식의 인덱스
  • objective-C와 swift가 동일한 메모리 레이아웃을 가짐
• LAPACK
  • 선형대수를 위한 산업 표준 인터페이스
  • FORTRAN의 후계
  • 복잡한 인터페이스를 가지나, 이후에 좀 더 다듬어서 개편됨
  • 직접 호출하는 것보다도 Accelerate를 통해서 호출하는 게 훨씬 빠르고 효율적임
• BLAS(Basic Linear Algebra Subprograms) for sparse matrix
  • sparse matrices를 위해 사용
  • 단일 정밀도와 배수 정밀도 지원
  • 왜 sparse용 라이브러리를 따로 써야 되나?
    • 머신러닝에서 쓰는 행렬은 엄청난 크기를 가지나, 밀도는 별로 크지 않다.
    • dense matrix용 표현을 쓰면, 엄청난 양의 메모리가 필요하다.
  • 무엇이 가능한가?
    • Products
    • Triangular solves
    • Norms
    • Trace
    • Permutes
    • Insert/Extract
  • 형식
    • sparse <-> dense의 전환이 가능해야 함
    • non-zero 값의 인덱스와 값을 가지고 있는 것
    • sparse vector의 집합으로 표현할 수 있음
    • 그 외에도 다양한 방법이 있음
    • 이 과정을 쉽게 하기 위해 Opaque pointer 형태의 data type을 제공
      • Data buffer/ memory, 저장 포맷, 세부 사항등을 자동으로 관리해줌 -> 수행하는 연산에 따른 자동 변환까지도 해줌

sparse_matrix_float A = sparse_matrix_create_float(M,N);
sparse_insert_entry_float(A, 2.0, row, col);

float val[] = { ... };
sparse_index indx[] = { ... };

sparse_dimension nz = sizeof(val)/sizeof(*val);
sparse_insert_row_float(A, row, nz,val,indx);
spard_insert_col_float(A, col,nz, val, indx);

sparse_commit(A); // batch 처리를 위해 commit 전까지 실제 처리가 유보됨. operation을 하면 자동으로 수행됨
...

sparse_destroy(A);

• 연산 예시
  • Product(C = AB)
    • Inner
      • A: Sparse
      • B: Sparse/Dense
      • C: 단일 값
    • outer
      • A: Dense
      • B: Sparse
      • C: Sparse
    • matrix * vector
      • A: Sparse
      • B: Dense
      • C: Dense
    • matrix * matrix
      • A: Sparse
      • B: Dense
      • C: Dense
      • sparse * sparce는 미지원

// C = aAB+C
sparse_status sparse_matrix_product_dense_float (
	enum CBLAS_ORDER order,
	enum CBLAS_TRANSPOSE transa,
	sparse_dimension nCol,
  float alpha,
  sparse_matrix_float A,
  const float *B,
  sparse_dimension ldb,
	float * C,
	sparse_dimension ldc
);

• riangular solves
  • X에 대한 문제 aTX = B 를 해결하는 것
  • T는 upper/lower 삼각 행렬
  • B는 dense vector/matrix
  • T에서 upper,lower 프로퍼티는 데이터를 넣기전에 세팅될 필요가 있다.

sparse_matrix_float T = sparse_matrix_create_float(M, M)
sparse_set_matrix_property(T, SPARSE_UPPER_TRIANGULAR);
// T에 데이터 넣기
...

sparse_matrix_triangular_solve_dense_float(
	CblasRowMajor, CblasNoTrans, nCol, alpha, T, B, ldb);