Due to the exponential growth of data utilized and generated by key workloads, accessing and storing data have emerged as primary bottlenecks in modern computing systems. To mitigate the overheads associated with data handling, compression-based architectures have been widely used in various domains. Irrespective of hardware domains, optimizing compression-based architectures requires two essential factors: 1) minimizing the compression and decompression overheads and 2) maximizing a compression effect. To achieve these goals, this dissertation utilizes two kinds of cross-layer optimizations: 1) harnessing software-layer characteristics and 2) redefining the boundary between hardware and software.
First, we leverage software-layer characteristics to optimize the code compression algorithm and the hardware components. To optimize the code compression algorithm, we analyze the entropy of instruction encoding and discover that certain bits within the 32-bit instruction encoding in RISC ISAs have high entropy due to several characteristics of high-level languages, such as reusability and the calling convention. Based on this observation, we co-design the code compression algorithm and the hardware components of the code compression support architecture. As a result of cross-layer optimization and co-design, we achieve a higher code compression effect and reduce the total energy consumption and the area of the code compression support architecture, compared to the state-of-the-art architectures.
Second, we conduct a detailed bit-level analysis of data patterns in software to overcome the limitations of previous intra- and inter-block compression techniques. Consequently, we identify two types of low-entropy among blocks. The first type is naturally observed low-entropy among memory blocks with the same word layout. The second type is artificially generated low-entropy through our proposed three optimization techniques. Based on these two low-entropy types, we propose an entropy-based inter-block pattern compression (EPC) technique. To efficiently manage inter-block patterns, we propose hardware-based and profiling-based pattern selection methods. Moreover, we present a hybrid approach that leverages both intra- and inter-block compression techniques. As a result, EPC achieves higher speedup and DRAM energy consumption reduction while significantly reducing the hardware area for supporting an inter-block compression, compared to the state-of-the-art inter-block compression technique.
Lastly, we redefine the boundary between hardware and software for tiling in sparse matrix multiplication. To minimize data movements in sparse matrix multiplication, the state-of-the-art accelerator atiles the input matrix by software preprocessing. However, this software-based tiling generates a compression format for each tile and does not provide any data-skipping information for the other input matrix. Consequently, the software-based tiling incurs huge memory overheads and ineffectual accesses. To overcome these limitations, we introduce Hardware-based Pseudo-Tiling (HARP), which performs the tiling process in hardware instead of software. HARP logically tiles the input matrix as if it were tiled, while preserving the original compression format for the input matrix. To realize pseudo-tiling, we propose Runtime Operand Descriptor (ROD) to point to effectual elements in a particular pseudo-tile. By utilizing RODs, HARP not only accesses effectual elements in a pseudo-tile but also can naturally skip ineffectual accesses. As a result, HARP achieves higher speedup and energy efficiency compared to the state-of-the-art accelerator, CPU, and GPU.
The cross-layer optimizations introduced in this dissertation will enable the development of more efficient compression-based architectures and inspire advancements in other domains of compression-based architecture. Given the anticipated increase in data utilization and generation, ongoing research into optimizing compression-based architecture remains essential.
현재 워크로드에서 발생하는 데이터 액세스 및 생성의 폭발적인 증가로 인해 데이터 접근 및 저장은 현대 컴퓨팅 환경에서 주요 병목으로 작용하고 있다. 이러한 데이터 처리의 오버헤드를 줄이기 위해서 압축 기반 아키텍처들이 다양한 도메인에서 폭넓게 활용되고 있다. 이러한 압축 기반 아키텍처들을 최적화하기 위해서는 도메인에 관계없이 다음 두 가지 핵심 조건이 필요하다. 첫째, 압축 및 압축 해제에 필요한 오버헤드 최소화하기. 둘째, 압축 효과를 극대화하기. 본 학위 논문은 이러한 목표들을 달성하기 위해서 소프트웨어 계층의 특성을 활용하거나 하드웨어와 소프트웨어의 경계 재설정을 통한 계층 교차 최적화 방법들을 활용하였다.
첫째, 소프트웨어 계층의 특성을 활용하여 코드 압축 기법과 관련된 하드웨어 요소들을 최적화하였다. 코드 압축 기법을 최적화하기 위해 명령어 인코딩의 엔트로피를 분석하였고, 그 결과 고수준 언어의 재사용성, 호출 규약과 같은 특징으로 인해서 RISC ISA의 32비트 명령어 인코딩 내에서 특정 비트들이 높은 엔트로피를 가진다는 것을 발견하였다. 이 관찰을 기반으로 코드 압축 기법과 코드 압축을 지원하기 위한 하드웨어 요소들을 공동 설계하였다. 이러한 계층 교차 최적화와 공동 설계 결과, 최신 아키텍처들보다 더 높은 코드 압축 효과와 더 낮은 에너지 소비 및 면적을 가진 하드웨어 아키텍처를 개발하였다.
둘째, 과거 제안된 블록 내 압축 기법들과 블록 간 압축 기법들의 한계점을 극복하기 위해 소프트웨어의 데이터 패턴들을 비트 레벨 단위로 분석하였다. 그 결과, 다음 두 가지 블록 간 낮은 엔트로피 종류들을 발견하였다. 첫째, 배열이 같은 블록 간에서 자연적으로 발견되는 낮은 엔트로피. 둘째, 제안한 세 가지 최적화 기법을 통해 인위적으로 생성한 낮은 엔트로피. 이러한 두 가지 엔트로피 타입들을 이용하여 블록 간 패턴들을 생성하여 활용하는 EPC 압축 기법을 제안하였다. 효율적으로 블록 간 패턴들을 관리하기 위해 하드웨어 기반 및 프로파일링 기반 패턴 선택 기법들도 제안하였다. 추가로, 블록 내 압축 기법과 블록 간 압축 기법을 동시에 활용하는 하이브리드 기법도 제안하였다. 그 결과, 제안한 EPC는 최신 블록 간 압축 기법보다 더 빠른 실행 속도, 더 낮은 DRAM 에너지 소비, 더 적은 추가 면적 오버헤드를 얻었다.
마지막으로, 희소 행렬 곱셈을 위한 타일링의 하드웨어와 소프트웨어의 경계를 재설정하였다. 희소 행렬 곱셈의 데이터 이동을 최소화하기 위해 최신 가속기는 소프트웨어 전처리를 통해서 입력 행렬을 타일링하였다. 그러나 이러한 방식은 타일마다 압축 포맷을 생성하고 다른 입력 행렬의 데이터 스킵 정보를 제공하지 않는다. 그 결과, 해당 방식은 큰 메모리 오버헤드와 불필요한 데이터 접근이 발생하게 된다. 이러한 방식의 한계점을 극복하기 위해 소프트웨어 대신 하드웨어적으로 타일링 과정을 처리하는 HARP를 제안하였다. 제안한 HARP는 입력 매트릭스의 본래의 압축 포맷을 유지하면서 타일링이 된 것처럼 논리적으로 해당 행렬을 타일링한다. 해당 기법을 구현하기 위해 특성 pseudo-tile의 필요한 데이터들을 가리키는 Runtime Operand Descriptor (ROD)을 제안하였다. 제안한 ROD들을 활용하여 HARP는 자연스럽게 불필요한 데이터 접근들을 생략하면서 필요한 데이터들만 접근할 수 있게 된다. 그 결과, 제안한 HARP는 최신 가속기, CPU, GPU보다 더 빠른 실행속도와 더 높은 에너지 효율성을 가진다.
본 학위 논문에서 제안한 계층 교차 최적화들은 더 효율적인 압축 기반 아키텍처 개발을 가능하게 하며, 다른 도메인에서의 압축 기반 아키텍처들의 발전에 영감을 줄 것으로 기대된다. 데이터의 활용과 생성이 계속해서 증가할 것이므로, 압축 기반 아키텍처 연구는 계속적으로 중요할 것이다.
