BitMagic 다운로드 - BitMagic 소스 코드 다운로드

비트매직

C# 소스 코드

v.7.13.4

다운로드

BitMagic C++ 라이브러리

BitMagic은 정보 검색을 위한 집합 대수 툴킷으로 만들어졌지만 현재는 간결한 데이터 벡터의 메모리 컴팩트 구조 및 알고리즘을 위한 보다 일반적인 데이터 과학 구성 요소 라이브러리로 발전했습니다. BitMagic은 메모리 압축 모델에 대한 비트 분할 변환, 순위 선택 압축 및 논리 컴퓨팅 아이디어를 기반으로 압축된 비트 벡터 및 컨테이너(벡터)를 구현합니다.

모든 BitMagic 간결 컨테이너는 효율적인 저장 및 네트워크 전송을 위해 직렬화 가능합니다(최첨단 바이너리 보간 코딩을 사용한 압축 포함). 모든 컨테이너는 압축된 형태로 빠르게 검색 가능합니다.

BitMagic은 HPC 기술을 사용하여 즉시 메모리를 절약하고(따라서 하나의 계산 단위에 더 많은 데이터를 넣을 수 있음), 데이터 벡터와 모델을 파일이나 객체에 저장할 때 스토리지 및 트래픽 패턴을 개선하도록 애플리케이션을 설계하는 방법 및 도구 세트를 제공합니다. 저장(SQL 또는 noSQL)을 수행하고 낮은 수준(CPU 캐시)에서 네트워크 및 스토리지 교환까지 시스템 대역폭을 최적화합니다.

BitMagic은 두 가지 큰 시나리오 클래스를 촉진합니다.

제한된 RAM 애플리케이션(WebAssembly, IoT, Edge 컴퓨팅, 데스크톱/워크스테이션 앱)
데이터 양이 천문학적이며 계산 및 저장이 분산되어야 하고(효율적인 전송이 필요함) 대역폭에 최적화되어야 하는 빅 데이터 HPC(페타바이트 문제).

애플리케이션 및 사용 사례

BitMagic은 다음을 위한 빌딩 블록으로 사용되었습니다.

IR, 데이터베이스 반전 인덱스 구성 또는 인덱스 없는 컬럼형 DB에 대한 집합의 대수학
논리 체계 시뮬레이션(FPGA)
압축 세트의 다차원 이진 거리 데이터 과학, 이진 클러스터화를 위한 빌딩 블록, 자체 구성 맵
메모리 압축 생물정보학 모델 구축
- 서열 정렬
- 변형 및 SNP 모음
- 시퀀스 읽기 압축
- k-mer 분류 시스템
메모리가 제한된 엣지 구성(에지 컴퓨팅, IoT, WebAssembly)에서 데이터 세트 시각화
그래프 및 트리 분석, 압축 연관 행렬 구축
웹 및 애플리케이션 로그 분석, 신뢰성 자동화 시스템
대기 시간이 짧은 작업 스케줄링(오케스트레이션) 시스템

사용 사례 노트를 방문하세요: http://bitmagic.io/use-case.html

최적화 및 SIMD

BitMagic 라이브러리는 다양한 플랫폼 및 빌드 대상에 대한 최적화를 구현하는 고성능 라이브러리입니다.

x86(플랫폼별로 사용 가능한 비트 스캔 명령어)
x86 SIMD: SSE2, SSE4.2(POPCNT, LZCNT), AVX2(BMI1/BMI2), AVX-512(작업 진행 중)
팔 SIMD: 네온
WebAssembly(WebAsm 내장 및 플랫폼별 트릭 사용)
웹어셈블리 SIMD

BitMagic은 최고의 단일 스레드 성능을 제공할 뿐만 아니라 다중 코어 시스템에서 고도의 병렬 컴퓨팅을 촉진한다는 목표로 데이터 병렬 벡터화 설계를 사용합니다.

압축 알고리즘

BitMagic은 일련의 압축 알고리즘, 필터 및 변환을 사용하여 메모리 공간, 스토리지 비용 및 네트워크 데이터 전송을 줄입니다. http://bitmagic.io/design.html

비트 벡터의 계층적 압축
비트 블록의 D-GAP(RLE)
이진 간섭 코딩(BIC)
엘리아스 감마 코딩
벡터에 대한 비트별 전치(비트 평면 코딩 또는 비트 슬라이싱이라고도 함)
XOR 압축 필터
빈도 기반 사전 재매핑(허프만 코드와 유사)

tech.notes를 방문하세요: http://bitmagic.io/articles.html

주요 기능(bm::bVector<>)

압축된 비트 벡터 컨테이너
iterator(bm::bVector<>::enumerator - 비트 세트를 정수로 디코딩함)
대수 연산 설정: 비트 벡터 및 정수 집합에 대한 AND, OR, XOR, MINUS, NOT
비트 벡터 순회를 위한 빠른 비트 벡터 반복자(열거자), 펑터 기반 순회를 위한 알고리즘(std::for_each와 유사)
정수 목록의 빠른 가져오기(압축)(C++ 스타일 Bulk_insert_iterator 또는 C 배열 사용)
집계자: 비트 벡터 그룹에 대한 빠른 벡터화된 논리 AND, OR, AND-MINUS 연산
지속성(또는 RAM 내 압축)을 위해 비트 벡터 컨테이너를 압축된 BLOB로 직렬화/하이버네이션
압축된 BLOB에 대한 대수 연산 설정(대수 설정 기능을 사용한 즉석 역직렬화)
유사성 및 거리 메트릭을 효율적으로 구성하고 비트 벡터, 정수 세트 및 압축된 BLOB 간의 유사성을 측정하는 통계 알고리즘
순위를 사용한 작업: 비트 벡터의 인구 수 거리. 순위 선택 작업은 간결한 데이터 구조에서 자주 사용되며, BitMagic은 SIMD 및 BMI(PDEP)로 가속화된 컴팩트 RS 인덱스를 구현합니다.

범위 및 간격(bmintervals.h)

BitMagic은 0과 측면에 있는 1의 겹치지 않는 범위 모음(예: 011110110)으로 비트 벡터의 재해석을 지원합니다. 일반 집합 함수는 집합 교차/합집합 역추적 작업을 통해 간격 반복자를 구현하고 간격 경계를 검색합니다. 범위와 간격은 생물정보학에서 매우 유용합니다. 왜냐하면 게놈 데이터는 좌표 범위로 주석이 추가되는 경우가 많기 때문입니다. BitMagic은 비트 벡터로 인코딩된 간격에 대한 효율적인 작업을 위한 빌딩 블록을 제공합니다(간격 시작/끝 찾기, 범위가 inetrval인지 확인, 간격 반복)

3개 값 논리(bm3vl.h)

BitMagic은 Kleene의 정의에 따라 반전, AND, OR 연산을 지원하는 컴팩트한 2비트 벡터 표현에서 True/False/Unknown(3항 논리, 3가, 3항)의 3값 논리에 대한 논리 연산을 구현합니다. https://github.com/tlk00/BitMagic/tree/master/samples/bv3vlogic

압축을 통한 직렬화

BitMagic은 2단계 직렬화-역직렬화 개념을 사용합니다. 초점은 빠른 역직렬화에 있습니다. BitMagic은 빠른 벡터 범위 역직렬화를 위한 API를 구현하고 압축된 BLOB의 역직렬화를 수집합니다. BitMagic의 궁극적인 특징은 압축된 데이터로 작업하는 능력입니다.

1단계: 간결한 기억

이는 벡터가 메모리 컴팩트 형식으로 유지되는 주요 RAM 내 작동 상태입니다. 간결함은 압축이 아닙니다. 컨테이너의 임의 요소에 액세스하고, 블록을 디코딩하고, 벡터를 반복하고, 업데이트하고, 검색 알고리즘을 실행하는 것이 가능합니다. Stage One은 투명한 사용을 제공하며 벡터는 STL과 매우 유사합니다. Succinct는 메모리가 컴팩트하지만 완전히 압축되지는 않습니다.

2단계: 압축

BitMagic은 경험적 방법과 코덱 블록을 기반으로 한 추가 압축을 통해 모든 컨테이너와 벡터를 직렬화할 수 있습니다. 대표적인 코딩 기술로는 BIC(Binary Interpolative Coding)와 Elias Gamma가 있습니다.

BitMagic 컨테이너는 "희소" 벡터라고 불리지만 실제로 그 압축 방식은 희소 데이터와 밀집 데이터 모두에 적합합니다.

BitMagic은 반전된 목록과 다수의 독점 데이터 세트로 구성된 Gov2 벤치마크 세트에서 테스트되었습니다. http://bitmagic.io/bm5-cmpr.html

감압

역직렬화는 항상 1단계로 돌아가므로 데이터가 완전히 디코딩되지는 않지만 대신
RAM에서는 간결합니다. 여기서 우리의 목표는 애플리케이션 메모리 공간을 줄이고 역직렬화 대기 시간을 개선하는 것입니다. 압축 해제 알고리즘은 임의 범위의 역직렬화를 지원하거나 심지어 요소의 역직렬화를 수집합니다.

간결한 벡터

BitMagic은 비트 전치 변환을 기반으로 간결한(메모리 컴팩트) 벡터를 지원합니다.
BPC(비트 슬라이싱)와 Rank-Select 압축이라고도 합니다. BitMagic 간결한 벡터는 "희소"라고 잘못 표시되어 있지만 조밀한 벡터에는 잘 작동합니다.

비트 전치는 사용되지 않은 비트 플레인을 해제하고 규칙성과 엔트로피를 별도의(희소) 비트 벡터로 분리하는 두 가지 목적을 해결합니다. 비트 평면의 압축은 뛰어난 메모리 성능과 빠른 검색을 모두 제공합니다. 빠른 벡터화 논리 연산을 사용하여 간결한 벡터에 대해 인덱스 없는 검색을 수행하는 것이 설계 목표 중 하나입니다.

BitMagic 간결한 벡터는 메모리 압축 형식으로 인덱스 없이 검색 가능합니다. 빠르다!

간결한 비트 전치 구현은 정수 벡터(부호 있는 또는 부호 없는)와 문자열 벡터 모두에 적합합니다. 이는 접두사 트리와 같은 다른 간결한 체계와 경쟁합니다. 간결한 벡터는 정렬되거나 정렬되지 않을 수 있습니다. 여기서의 아이디어는 Apache Arrow-Parquet와 유사하지만 비트 평면 압축과 가속화된 Rank-Select 압축의 광범위한 사용을 통해 더 발전했습니다.

비트 전치 표현은 데이터가 제한적이거나 가변적인 비트 전송률을 갖는 숫자를 사용할 때 숫자 벡터에 대한 최상의 메모리 공간을 제공합니다. 데이터에 27비트만 필요한 경우 간결한 벡터는 가장 가까운 자연 32비트 유형이 아닌 바로 이를 사용합니다. 적응형이며 완전 자동입니다.
문자열 벡터가 특정 위치의 문자(DNA 문자열, 미소의 화학 화합물 등)를 표현하는 데 몇 비트만 필요한 경우 BitMagic에는 투명한 재매핑을 수행할 수 있는 옵션이 있으므로 DNA 문자열 벡터는 2-3비트만 사용합니다(ATGCN의 경우). 알파벳), 리매핑은 주파수를 분석하며 Huffman과 유사합니다.
순위 선택 접근 방식을 통해 모든 NULL 값을 축소하고 RAM을 절약할 수 있습니다.
더 깊은 압축을 위해 BitMagic은 엔트로피를 줄이기 위해 비트 평면 간의 가능한 상관 관계를 찾는 XOR 필터도 구현합니다. http://bitmagic.io/bm-xor.html

주요 기능

메모리 내 열 구조 구성을 위한 NULL 값(할당되지 않음) 지원과 함께 비트 슬라이스의 개별 압축 및 비트 슬라이스를 사용하는 기본 int 유형에 대한 희소 벡터입니다. 비트 전치 희소 벡터는 천문학, 분자 생물학 또는 기타 데이터의 즉석 압축, 그래프에 대한 효율적인 연관 저장 등에 사용될 수 있습니다.
정렬된 및 정렬되지 않은 간결한 벡터(정수 또는 문자열의 벡터)에 대한 검색 알고리즘
희소 벡터에 대한 알고리즘: 동적 범위 클리핑, 검색, 그룹 이론 이미지(재매핑).
모든 컨테이너는 압축(XOR 코딩, 이진 보간 코딩, 엘리아스 감마 코딩)으로 직렬화 가능합니다.
간결한 불변 벡터를 지원합니다. 벡터는 읽기 전용으로 전환될 수 있으며, 희소 메모리 블록은 힙 조각 모음, 메모리 절약 및 더 나은 CPU 캐시 결과를 촉진하기 위해 재배치될 수 있습니다.

직렬화 및 버전 관리

BitMagic은 직렬화(프로토콜) 발전을 지원합니다. 직렬화 형식이 변경되면 이전에 저장된 데이터는 새 코드에서 계속 읽을 수 있습니다. 이전 코드는 새 BLOB를 읽을 수 없습니다. BitMagic은 직렬화 형식이 변경되면 주요 버전 번호를 변경합니다.

메모리 프로파일링/모니터링

BitMagic은 모든 벡터에 대한 메모리 프로파일링 호출을 구현합니다. 모든 벡터는 메모리 공간에 대해 샘플링될 수 있으므로 최상위 시스템은 런타임 메모리 프로파일링을 기반으로 메모리 관리를 조정할 수 있습니다. 일반적인 사용 사례는 RAM으로 압축한 다음 리소스 소비 및 비용(수요와 공급의 동적 균형)을 기반으로 디스크로 제거하는 개체의 메모리 캐시입니다.

64비트와 32비트

예! BitMagic은 64비트를 지원하며 32비트 주소 공간(오버헤드가 적음) 또는 전체 64비트 주소 공간과 함께 사용할 수 있습니다. 32비트 주소 공간은 기본 모드입니다. 2^31-1 요소는 단거리 및 중거리 IR 및 데이터 과학 시스템에 적합합니다. 64비트 주소 모드는 #define BM64ADDR 또는 #include "bm64.h"를 사용하여 사용할 수 있습니다. 현재 64비트 구현에서는 대규모 시스템에 대해 2^48-1 벡터 요소를 허용합니다.

웹어셈블리와 웹어셈블리 SIMD

BitMagic은 WebAssmbly(emscripten)를 사용하여 컴파일하고 작동합니다. 최신 버전에는 플랫폼에 특정한 여러 가지 조정이 포함되어 있습니다. 성능 수치는 SIMD가 없는 네이티브 코드에 가깝습니다(때때로 그 이후). 샘플 컴파일 라인은 다음과 같습니다:

emcc -std=c++17 -s ALLOW_MEMORY_GROWTH=1 -O2 -s WASM=1 ...

WebAssembly SIMD는 지원되지만 기본적으로 켜져 있지 않습니다. 활성화하려면 #define BMWASMSIMDOPT 사용하세요. Emscripten cmd 예:

emcc -std=c++17 -s ALLOW_MEMORY_GROWTH=1 -O2 -msse4.2 -msimd128 -D BMWASMSIMDOPT -s WASM=1 -s DISABLE_EXCEPTION_CATCHING=0 -fno-rtti

현재 구현에서는 SSE4.2 트랜스 컴파일(내장 기능을 통해)을 사용하므로 -msse4.2 가 필요합니다.

팔

BitMagic은 ARM CPU를 완벽하게 지원합니다. 모든 릴리스는 Raspberry Pi 4를 사용하여 스트레스 테스트를 거쳤습니다. BitMagic은 ARM에 특정한 몇 가지 알고리즘 조정 및 개선 사항(예: LZCNT 명령어 사용)을 구현합니다. BitMagic의 간결한 컨테이너는 사용 가능한 메모리 양이 제한된 엣지 컴퓨팅용 임베디드 시스템에 매우 유용할 수 있습니다.

Arm Neon SIMD 지원이 가능합니다(SSE2NEON 라이브러리를 통해).

C 라이브러리 인터페이스:

BitMagic 라이브러리는 "진정한 C" 라이브러리로 구축되는 C 라이브러리 래퍼를 제공합니다. 재배포의 경우 STL, C++ 메모리 할당(연산자 new) 또는 예외를 사용하지 않고 컴파일하므로 C++ 런타임이 필요하지 않습니다. 여기서 우리의 목표는 궁극적으로 JNI를 통해 다른 데이터 과학 언어(Python) 및 엔터프라이즈 규모 개발 언어(Java, Scala)에 대한 연결을 제공하는 것입니다.

진행 중인 기능:

엔터티 관계 가속화, 그래프 작업, 소셜 분석, 구체화된 RDBMS 조인 등을 위한 압축된 이진 관계형 및 인접 행렬과 행렬에 대한 작업

BitMagic을 어떻게 시작하나요?

BitMagic C++는 헤더 전용 라이브러리(프로젝트에서 쉽게 구축하고 사용할 수 있음)이며 일련의 예제가 함께 제공됩니다. 라이브러리 사용을 연구하기 위한 코드 예제로 테스트를 사용하는 것은 권장되지 않습니다. 테스트는 최상의 사용 패턴과 모델을 보여주지 못하며 종종 의도적으로 비효율적입니다.

API 문서 및 예제: http://www.bitmagic.io/apis.html

집합 대수학 튜토리얼: http://bitmagic.io/set-algebra.html

사용 사례 및 애플리케이션 노트: http://bitmagic.io/use-case.html

성능 최적화에 대한 기술 노트: http://bitmagic.io/articles.html

Doxygen: http://bitmagic.io/doxygen/html/modules.html

특허:

아파치 2.0.

중요한! 파생 작업이나 게시된 자료에서 BitMagic 프로젝트를 명시적으로 언급해 주시기 바랍니다. 제품/프로젝트 페이지의 올바른 참조는 BitMagic 라이브러리를 사용하기 위한 요구 사항입니다.

품질 보증:

BitMagic 라이브러리는 코드 품질과 테스트 범위에 심각한 주의를 기울입니다.
빌딩 블록 라이브러리로서 BitMagic이 유용하려면 안정적이고 적합해야 합니다.

우리는 단위 테스트에만 의존하지 않고, 스트레스 테스트가 무작위로 생성된 세트와 무작위 작업을 기반으로 하는 "카오스 테스트" (일명 퍼징)를 사용하는 경우가 많습니다. 우리는 다양한 SIMD 최적화 조합을 위해 릴리스 및 디버그 모드용 테스트 슈트를 정기적으로 구축하고 실행합니다.

모든 테스트 빌드 변형은 실행하는 데 며칠이 걸리므로 작업 중인 마스터 브랜치가 항상 완벽하다고 보장할 수는 없습니다. 제작을 위해서는 SourceForge의 안정적인 github 릴리스 브랜치나 배포판을 사용하세요: https://sourceforge.net/projects/bmagic/files/

BitMagic 라이브러리에 기여하거나 지원하고 싶다면:

GitHub 마스터는 패치 요청을 수락합니다. 우리의 분기 정책은 마스터가 릴리스 간에 완전히 안정적인 것으로 간주될 수 없다는 것입니다. (생산 안정성을 위해 릴리스 버전을 사용하십시오)
Python 및 기타 언어에 대한 매핑에 도움이 필요합니다(BitMagic에는 C 바인딩이 있습니다).

BitMagic C++ 라이브러리를 구축하는 방법:

BitMagic C++는 헤더 전용 소프트웨어 패키지이므로 소스를 가져와 프로젝트에 직접 넣을 수 있습니다. 모든 C++ 라이브러리 소스/헤더는 src 디렉토리에 있습니다.

그러나 makefile을 사용하려면 다음의 간단한 지침을 따라야 합니다.

유닉스:

기존(내부 빌드)

프로젝트 루트 디렉터리에서 bmenv.sh를 실행하여 몇 가지 환경 변수를 적용합니다.

 $ source ./bmenv.sh

(루트 환경 변수를 적용하려면 "." "./bmenv.sh"를 사용하십시오)

설치를 빌드하려면 GNU make(gmake)를 사용하십시오.

 $make rebuild

또는 (디버그 버전)

 $gmake DEBUG=YES rebuild

Unix 및 CygWin의 기본 컴파일러는 g++입니다. 기본값을 변경하려면 makefile.in에서 변경할 수 있습니다(매우 쉬울 것입니다).

CMake 기반 빌드 프로젝트에는 이제 cmake용 makefile 세트가 함께 제공됩니다. cmake 지원 환경에 맞게 빌드하거나 프로젝트 파일을 생성할 수 있습니다.

윈도우:

cygwin 설치를 사용하는 경우 일반적인 Unix 권장 사항을 따르십시오. MSVC - 솔루션 및 프로젝트는 CMAKE를 통해 사용할 수 있습니다.

맥OS

Xcode - 프로젝트 파일은 CMAKE를 통해 사용할 수 있습니다.

C 및 JNI 매핑용 BitMagic 라이브러리.

BitMagic 라이브러리는 C 언어에서 사용할 수 있습니다(이 작업은 진행 중입니다). C 빌드의 주요 목표는 BitMagic을 다른 프로그래밍 언어에 연결하는 것입니다. C 빌드는 "lang-maps" 하위 디렉터리에 있습니다.

C 빌드는 SSE 및 AVX용 BitMagic 빌드 버전을 생성하고 CPU 식별을 추가하므로 상위 수준 시스템은 동적 CPU 식별 및 코드 디스패치를 지원할 수 있습니다.

C 빌드는 C++ 컴파일러를 사용하지만 RTTI, 예외(롱 점프로 시뮬레이션) 및 C++ 메모리 관리를 사용하지 않으므로 런타임 종속성이 없고 C++ 언어 중립적입니다. 알고리즘과 동작은 C와 C++ 간에 공유됩니다.

현재 개발 상태:

C 인터페이스를 통해 비트 벡터 기능을 사용할 수 있습니다.

파이썬 지원

Python 지원이 보류 중이므로 여기에 도움이 필요합니다. Python에 대해 열정이 있고 도움을 줄 수 있다고 생각한다면 다음 주소로 연락하십시오: anatoliy.kuznetsov @ yahoo dot com

#정의하다	설명	너비
BMSSE2OPT	SSE2 코드 최적화	128비트
BMSSE42OPT	SSE4.2 코드 최적화 및 POPCNT, BSF 등	128비트
BMAVX2OPT	AVX2, POPCNT, LZCNT, BMI1, BMI2 최적화	256비트
BMAVX512OPT	AVX-512, (실험용)	512비트
BMWASMSIMDOPT	WebAssembly SIMD 최적화(SSE4.2를 통해)	128비트
DBMNEONOPT	Arm Neon SIMD 최적화(SSE2 변환을 통해)	128비트

비트매직