Code Compression for Embedded Systems Using Separated Dictionaries
Abstract : Engineers must consider performance, power consumption, and cost when designing embedded digital systems; furthermore, memory is a key factor in such systems. Code compression is a technique used in embedded systems to reduce the memory usage. BitMask-based code compression is a modified version of dictionary-based code compression. The basic purpose of BitMask is to record mismatched values and their positions to compress a greater number of instructions; it can be used exclusively or incorporated with the reference instructions to decode the codewords. In this paper, we applied a small separated dictionary, and variable mask numbers were used with the BitMask algorithm to reduce the codeword length of highfrequency instructions. In addition, a novel dictionary selection algorithm was proposed to increase the instruction match rates. The fully separated dictionary method was used to improve the performance of the decompression engine without affecting the compression ratio (CR) (the compressed code size divided by original code size). Based on the experimental results, the proposed method can achieve a 7.5% improvement in the CR with nearly no hardware overhead.
? Due to the constraints stated above most of the existing state of art algorithms cannot be used directly.
? We can use well-characterized existing processor pipelines, take advantage of existing programming development tools, use existing workstations as development platforms, etc.
? It is optimized for single-chip implementations and has several attributes that set it apart from existing RISC processors.
? They developed a compression algorithm to unify the duplicated instructions existing in the embedded program and assign a compressed object code to such an instruction.
? The new compact form of instruction format requires less number of bits than the original one and consequently, it reduces the code size.
? To overcome this problem, these high-frequency instructions are separated into another small dictionary to obtain shorter codeword lengths.
? The fully separated dictionary architecture is proposed as a solution to this problem.
? There are two ways to solve such problem: 1) modify the compiler to increase the decompression level parallelism and 2) lose some CR to increase the decompression level parallelism by duplicating some instructions into the different dictionaries.
? A large LUT has several disadvantages: it requires a large chip area, additional power consumption, a long LUT latency, and a long codeword length.
• We propose two algorithms to compress code in a space-efficient and simple to decom- press way, one which is independent of the instruction set and another which depends on the instruction set.
• Several heuristics for parsing have been proposed with greedy parsing being the most popular due to its simplicity and speed.
• Their proposed framework and algorithm for combining both schemes achieved at least the same reduction in code size as operand parameters, but enabled more efficient coding of the dictionary allowing for a more efficient implementation.
• It seemed that after several years of research in the field, in most recent years research in this area almost diminished since improvements were marginal because of sophisticated code compression schemes that had been proposed.
? The research in code compression has been conducted to reduce the code size and power consumption, as well as to improve the performance.
? The complexity and performance requirements for embedded programs grow rapidly, which results in additional memory usage and power consumption.
? Although several existing code compression algorithms have exhibited favorable compression performance, no single compression algorithm has efficiently worked for all kinds of benchmarks.
? The dictionary-based compression methods often yield a single decoding table and this structure hazard restricts the performance of decompression engine.
|