Reducing code size is crucial in embedded systems as well as in high-performance systems to overcome the communication bottleneck between memory and CPU, especially with VLIW (Very Long Instruction Word) processors that require a high-bandwidth instruction prefetching. This paper presents two new approaches for dictionary-based code compression in VLIW processor-based systems.
The first approach uses opcode-isomorphism and operand-isomorphism among instruction words. After instruction words are divided into two groups, one for an opcode group and the other for an operand group, the proposed compression algorithm is applied to each group to obtain maximal code compression. Frequently-used instruction words are extracted from the original code to be mapped into two dictionaries, an it opcode dictionary and an it operand dictionary. According to the SPEC95 benchmarks, the proposed technique has achieved an average code compression ratio of 61.56%, 61.3%, and 57.98% in 4-issue, 8-issue, and 12-issue VLIW architectures, respectively and our scheme provide a good trade-off between code compression ratio and the decoding logic delay. Moreover, opcode-isomorphic or operand-isomorphic instruction words achieve the power reduction by 39.93%, 39.40%, and 44.31% in 4-issue, 8-issue, and 12-issue VLIW architectures, respectively.
As the second approach, we propose a code compression method based on the dictionary-based code compression, which uses the mobility of instructions to enhance the code compression ratio compared to the first isomorphism method. In the compilation phase, instructions in a basic block can be rescheduled using their mobility. This rescheduling helps to find more identical or opcode-isomorphic/operand-isomorphic instruction words. To implement this scheme, we have used the two-phase algorithm, making global compaction information and compacting the instructions. This scheme improves the code compression ratio by about 10% compared to that of the previous scheme using opcode-isomorphism and operand-isomorphism. Moreover, the scheme does not induce additional hardware overhead in co-application with the hardware code compression scheme at the expense of increased compilation time.
프로그램의 크기를 줄이는 것은 메모리와 CPU 사이의 통신 병목현상을 제거하기 위해 고성능 시스템 뿐만 아니라 임베디드 시스템에서도, 특히 높은 명령어 bandwidth를 필요로 하는 VLIW (Very Long Instruction Word)에서 필수적이다. 본 논문에서는 VLIW를 기반으로 하는 시스템에서 dictionary 구조를 이용한 두가지 새로운 코드 압축 방법을 제안한다.
첫번째 방법은 명령어 간에 동형이질성(isomorphism)을 이용한다. 명령어들을 opcode 그룹과 operand 그룹으로 나눈 후, 최대한의 코드 압축율을 얻기 위해 제안된 압축 알고리즘을 각각의 그룹에 적용한다. 원래의 코드에서 자주 사용되는 명령어들을 추출하여 그들은 opcode dictionary와 operand dictionary 두 개의 dictionary로 변환시킨다. SPEC95를 이용한 실험에서 이렇게 제안된 방법이 4개의 issue, 8개의 issue, 12개의 issue에서 각각 평균 61.56%, 61.3%, 57.98%의 코드 압출율을 나타냈다. 즉, 이러한 방법은 코드 압출율과 디코딩 지연시간사이의 좋은 trade-off인 것이다. 한편, 같은 issue 구조에서 각각 39.93%, 39.40%, 44.31%의 전력 소모의 감소도 보였다.
두번째 방법은 역시 dictionary 구조하에서 명령어간의 mobility를 이용한 명령어의 스케쥴링에 의해 코드를 압축하는 방법이다. 이러한 스케쥴링은 더욱 많은 동일 명령어나 동형이질의 명령어를 찾을 수 있게 한다. 이를 위해 전역적인 밀집 정보를 얻은 단계와 이를 바탕으로 명령어를 밀집시키는 두 단계로 알고리즘을 구성하였다. 두번째 방법은 첫번째 방법에 비해 약 10%정도의 코드 압축율 향상을 보였다. 더욱이, 두번째 방법은 어떠한 하드웨어의 추가를 필요로 하지 않는다는 점에서 큰 장점을 지닌다.
