The Experts below are selected from a list of 243 Experts worldwide ranked by ideXlab platform
Haris Lekatsas - One of the best experts on this subject based on the ideXlab platform.
-
Code Compression for embedded vliw processors using variable to fixed coding
IEEE Transactions on Very Large Scale Integration Systems, 2006Co-Authors: Wayne Wolf, Haris LekatsasAbstract:In embedded system design, memory is one of the most restricted resources, posing serious constraints on program size. Code Compression has been used as a solution to reduce the Code size for embedded systems. Lossless data Compression techniques are used to compress instructions, which are then decompressed on-the-fly during execution. Previous work used fixed-to-variable coding algorithms that translate fixed-length bit sequences into variable-length bit sequences. In this paper, we present a class of Code Compression techniques called variable-to-fixed Code Compression (V2FCC), which uses variable-to-fixed coding schemes based on either Tunstall coding or arithmetic coding. Though the techniques are suitable for both reduced instruction set computer (RISC) and very long instruction word (VLIW) architectures, they favor VLIW architectures which require a high-bandwidth instruction prefetch mechanism to supply multiple operations per cycle, and fast deCompression is critical to overcome the communication bottleneck between memory and CPU. Experimental results for a VLIW embedded processor TMS320C6x show that the Compression ratios using memoryless V2FCC and Markov V2FCC are around 82.5% and 70%, respectively. DeCompression unit designs for memoryless V2FCC and Markov V2FCC are implemented in TSMC 0.25-/spl mu/m technology.
-
coco a hardware software platform for rapid prototyping of Code Compression technologies
Design Automation Conference, 2003Co-Authors: Haris Lekatsas, Jorg Henkel, Srimat T Chakradhar, Venkata Jakkula, Murugan SankaradassAbstract:In recent years, instruction Code Compression/deCompression technologies have emerged as an efficient way to: a) reduce the memory usage of an embedded system, b) to improve performance through effective higher bandwidths and/or to c) reduce the overall power consumption of a system processing compressed Code. We have presented efficient Code Compression/deCompression techniques and architectures in the past. For the commercialization phase, we designed a novel hardware/software Code Compression/deCompression platform (CoCo). It consists of a software platform that prepares, optimizes, compresses and compiles instruction Code and a generic, parameterizable FPGA-based hardware architecture in form of a hardware platform that allows to rapidly evaluate prototypes of diverse Compression/deCompression technologies. We show the flexibility of CoCo, its ability to achieve Code Compression ratios (parameterizable) of up to 50% with a slight system performance gain and its ability to apply Compression in a real-world compiled Code without any limitations where others have made implicit software-restrictive assumptions.
-
Code Compression using variable to fixed coding based on arithmetic coding
Data Compression Conference, 2003Co-Authors: Yuan Xie, Wayne Wolf, Haris LekatsasAbstract:Embedded computing systems are space and cost sensitive. Memory is one of the most restricted resources that post serious constraints on program size. Code Compression, which is a special case of data Compression where the input source is in machine instructions, has been proposed as a solution to this problem. Previous work in Code Compression has focused on either fixed-to-variable coding or dictionary-based algorithms. Code Compression schemes that use variable-to-fixed (V2F) length coding were proposed, based on arithmetic coding. Experiments have shown that the Compression ratio, using memoryless V2F coding for the TMS320C6x processor, have an average of 82.5% and deCompression can be parallelized. A Markov-based V2F coding based on arithmetic coding has achieved an average Compression ratio of 72% for TMS320C6x while deCompression cannot be parallelized. Furthermore, the given experiments have shown that arithmetic coding based V2F coding has similar Compression performance to Tunstall coding. Finally, a power reduction scheme for the instruction bus using the V2F coding scheme was presented.
-
Code Compression for vliw processors using variable to fixed coding
International Symposium on Systems Synthesis, 2002Co-Authors: Yuan Xie, Wayne Wolf, Haris LekatsasAbstract:Memory has been one of the most restricted resources in the embedded computing system domain. Code Compression has been proposed as a solution to this problem. Previous work used fixed-to variable coding algorithms that translate fixed-length bit sequences into variable-length bit sequences. In this paper, we propose Code Compression schemes that use variable-to-fixed (V2F) length coding. We also propose an instruction bus encoding scheme, which can effectively reduce the bus power consumption. Though the Code Compression algorithm can be applied to any embedded processor, it favors VLIW architectures because VLIW architectures require a high-bandwidth instruction pre-fetch mechanism to supply multiple operations per cycle. Experiments show that the Compression ratios using memoryless V2F coding for IA-64 and TMS320C6x are around 72.7% and 82.5% respectively. Markov V2F coding can achieve better Compression ratio up to 56% and 70% for IA-64 and TMS320C6x respectively. A greedy algorithm for Codeword assignment can reduce the bus power consumption and the reduction depends on the probability model used.
-
design of an one cycle deCompression hardware for performance increase in embedded systems
Design Automation Conference, 2002Co-Authors: Haris Lekatsas, Jorg Henkel, Venkata JakkulaAbstract:Code Compression is known as an effective technique to reduce instruction memory size on an embedded system. However Code Compression can also be very effective in increasing process-or-to-memory bandwidth and hence provide increased system performance. In this paper we describe our design and design methodology of the first running prototype of a one-cycle Code deCompression unit that decompresses compressed instructions on-the-fly. We describe in detail the architecture that enables deCompression of multiple instructions in one cycle and we present the design methodologies and tools used. The stand-alone deCompression unit does not require any modifications on the processor core. We observed up to 63% performance increase with 25% in average over a wide variety of applications running on the hardware prototype under various system configurations.
Wayne Wolf - One of the best experts on this subject based on the ideXlab platform.
-
Code Compression for vliw embedded systems using a self generating table
IEEE Transactions on Very Large Scale Integration Systems, 2007Co-Authors: Chang Hong Lin, Yuan Xie, Wayne WolfAbstract:We propose a new class of methods for VLIW Code Compression using variable-sized branch blocks with self-generating tables. Code Compression traditionally works on fixed-sized blocks with its efficiency limited by their small size. A branch block, a series of instructions between two consecutive possible branch targets, provides larger blocks for Code Compression. We compare three methods for compressing branch blocks: table-based, Lempel-Ziv-Welch (LZW)-based and selective Code Compression. Our approaches are fully adaptive and generate the coding table on-the-fly during Compression and deCompression. When encountering a branch target, the coding table is cleared to ensure correctness. DeCompression requires a simple table lookup and updates the coding table when necessary. When decoding sequentially, the table-based method produces 4 bytes per iteration while the LZW-based methods provide 8 bytes peak and 1.82 bytes average deCompression bandwidth. Compared to Huffman's 1 byte and variable-to-fixed (V2F)'s 13-bit peak performance, our methods have higher decoding bandwidth and a comparable Compression ratio. Parallel deCompression could also be applied to our methods, which is more suitable for VLIW architectures.
-
Code Compression for embedded vliw processors using variable to fixed coding
IEEE Transactions on Very Large Scale Integration Systems, 2006Co-Authors: Wayne Wolf, Haris LekatsasAbstract:In embedded system design, memory is one of the most restricted resources, posing serious constraints on program size. Code Compression has been used as a solution to reduce the Code size for embedded systems. Lossless data Compression techniques are used to compress instructions, which are then decompressed on-the-fly during execution. Previous work used fixed-to-variable coding algorithms that translate fixed-length bit sequences into variable-length bit sequences. In this paper, we present a class of Code Compression techniques called variable-to-fixed Code Compression (V2FCC), which uses variable-to-fixed coding schemes based on either Tunstall coding or arithmetic coding. Though the techniques are suitable for both reduced instruction set computer (RISC) and very long instruction word (VLIW) architectures, they favor VLIW architectures which require a high-bandwidth instruction prefetch mechanism to supply multiple operations per cycle, and fast deCompression is critical to overcome the communication bottleneck between memory and CPU. Experimental results for a VLIW embedded processor TMS320C6x show that the Compression ratios using memoryless V2FCC and Markov V2FCC are around 82.5% and 70%, respectively. DeCompression unit designs for memoryless V2FCC and Markov V2FCC are implemented in TSMC 0.25-/spl mu/m technology.
-
lzw based Code Compression for vliw embedded systems
Design Automation and Test in Europe, 2004Co-Authors: Chang Hong Lin, Yuan Xie, Wayne WolfAbstract:We propose a new variable-sized-block method for VLIW Code Compression. Code Compression traditionally works on fixed-sized blocks and its ef.ciency is limited by the smallblock size. Branch blocks -- instructions between two consecutive possible branch targets -- provide larger blocks for Code Compression. We propose LZW-based algorithms to compress branch blocks. Our approach is fully adaptive and generates coding table on-the-fly during Compression and deCompression. When encountering a branch target,the coding table is cleared to ensure correctness. DeCompression requires only a simple lookup and update when necessary. Our method provides 8 bytes peak deCompression bandwidth and 1.82 bytes in average. Compared to Huffman's 1 byte and V2F's 13-bit peak performance, our methods have higher decoding bandwidth and comparable Compression ratio. Parallel deCompression could also be applied to our methods, which is more suitable for VLIW architecture.
-
Code Compression using variable to fixed coding based on arithmetic coding
Data Compression Conference, 2003Co-Authors: Yuan Xie, Wayne Wolf, Haris LekatsasAbstract:Embedded computing systems are space and cost sensitive. Memory is one of the most restricted resources that post serious constraints on program size. Code Compression, which is a special case of data Compression where the input source is in machine instructions, has been proposed as a solution to this problem. Previous work in Code Compression has focused on either fixed-to-variable coding or dictionary-based algorithms. Code Compression schemes that use variable-to-fixed (V2F) length coding were proposed, based on arithmetic coding. Experiments have shown that the Compression ratio, using memoryless V2F coding for the TMS320C6x processor, have an average of 82.5% and deCompression can be parallelized. A Markov-based V2F coding based on arithmetic coding has achieved an average Compression ratio of 72% for TMS320C6x while deCompression cannot be parallelized. Furthermore, the given experiments have shown that arithmetic coding based V2F coding has similar Compression performance to Tunstall coding. Finally, a power reduction scheme for the instruction bus using the V2F coding scheme was presented.
-
Code Compression for vliw processors using variable to fixed coding
International Symposium on Systems Synthesis, 2002Co-Authors: Yuan Xie, Wayne Wolf, Haris LekatsasAbstract:Memory has been one of the most restricted resources in the embedded computing system domain. Code Compression has been proposed as a solution to this problem. Previous work used fixed-to variable coding algorithms that translate fixed-length bit sequences into variable-length bit sequences. In this paper, we propose Code Compression schemes that use variable-to-fixed (V2F) length coding. We also propose an instruction bus encoding scheme, which can effectively reduce the bus power consumption. Though the Code Compression algorithm can be applied to any embedded processor, it favors VLIW architectures because VLIW architectures require a high-bandwidth instruction pre-fetch mechanism to supply multiple operations per cycle. Experiments show that the Compression ratios using memoryless V2F coding for IA-64 and TMS320C6x are around 72.7% and 82.5% respectively. Markov V2F coding can achieve better Compression ratio up to 56% and 70% for IA-64 and TMS320C6x respectively. A greedy algorithm for Codeword assignment can reduce the bus power consumption and the reduction depends on the probability model used.
Prabhat Mishra - One of the best experts on this subject based on the ideXlab platform.
-
bitmask based Code Compression for embedded systems
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008Co-Authors: Seokwon Seong, Prabhat MishraAbstract:Embedded systems are constrained by the available memory. Code-Compression techniques address this issue by reducing the Code size of application programs. It is a major challenge to develop an efficient Code-Compression technique that can generate substantial reduction in Code size without affecting the overall system performance. We present a novel Code-Compression technique using bitmasks, which significantly improves the Compression efficiency without introducing any deCompression penalty. This paper makes three important contributions. 1) It develops an efficient bitmask-selection technique that can create a large set of matching patterns. 2) It develops an efficient dictionary-selection technique based on bitmasks. 3) It proposes a dictionary-based Code-Compression algorithm using the bitmask- and dictionary-selection techniques that can significantly reduce the memory requirement. To demonstrate the usefulness of our approach, we have performed Code Compression using applications from various domains and compiled for a wide variety of architectures. Our approach outperforms the existing dictionary-based techniques by an average of 20%, giving a Compression ratio of 55%-65%.
-
an efficient Code Compression technique using application aware bitmask and dictionary selection methods
Design Automation and Test in Europe, 2007Co-Authors: Seokwon Seong, Prabhat MishraAbstract:Memory plays a crucial role in designing embedded systems. A larger memory can accommodate more and large applications but increases cost, area, as well as energy requirements. Code Compression techniques address this problem by reducing the size of the applications. While early work on bitmask-based Compression has proposed several promising ideas, many challenges remain in applying them to embedded system design. This paper makes two important contributions to address these challenges by developing application-specific bitmask selection and bitmask-aw are dictionary selection techniques. The authors applied these techniques for Code Compression of TI and MediaBench applications to demonstrate the usefulness of the approach
-
an efficient Code Compression technique using application aware bitmask and dictionary selection methods
Design Automation and Test in Europe, 2007Co-Authors: Seokwon Seong, Prabhat MishraAbstract:Memory plays a crucial role in designing embedded systems. A larger memory can accommodate more and large applications but increases cost, area, as well as energy requirements. Code Compression techniques address this problem by reducing the size of the applications. While early work on bitmask-based Compression has proposed several promising ideas, many challenges remain in applying them to embedded system design. This paper makes two important contributions to address these challenges by developing application-specific bitmask selection and bitmask-aware dictionary selection techniques. We applied these techniques for Code Compression of TI and MediaBench applications to demonstrate the usefulness of our approach.
-
a bitmask based Code Compression technique for embedded systems
International Conference on Computer Aided Design, 2006Co-Authors: Seokwon Seong, Prabhat MishraAbstract:Embedded systems are constrained by the available memory. Code Compression techniques address this issue by reducing the Code size of application programs. Dictionary-based Code Compression techniques are popular because they offer both good Compression ratio and fast deCompression scheme. Recently proposed techniques [8, 9] improve standard dictionary-based Compression by consideringmismatches. This paper makes two important contributions: i) it provides a cost-benefit analysis framework for improving the Compression ratio by creating more matching patterns, and ii) it develops an efficient Code Compression technique using bitmasks to improve the Compression ratio without introducing any deCompression penalty. To demonstrate the usefulness of our approach we have used applications from various domains and compiled for a wide variety of architectures. Our approach outperforms the existing dictionary-based techniques by an average of 15%, giving a Compression ratio of 55% - 65%.
-
a bitmask based Code Compression technique for embedded systems
International Conference on Computer Aided Design, 2006Co-Authors: Seokwon Seong, Prabhat MishraAbstract:Embedded systems are constrained by the available memory. Code Compression techniques address this issue by reducing the Code size of application programs. Dictionary-based Code Compression techniques are popular because they offer both good Compression ratio and fast deCompression scheme. Recently proposed techniques by J. Prakash et al. (2003) improve standard dictionary-based Compression by considering mismatches. This paper makes two important contributions: i) it provides a cost-benefit analysis framework for improving the Compression ratio by creating more matching patterns, and ii) it develops an efficient Code Compression technique using bitmasks to improve the Compression ratio without introducing any deCompression penalty. To demonstrate the usefulness of our approach we have used applications from various domains and compiled for a wide variety of architectures. Our approach outperforms the existing dictionary-based techniques by an average of 15%, giving a Compression ratio of 55% - 65%
Niko Lukač - One of the best experts on this subject based on the ideXlab platform.
-
Can burrows-Wheeler transform be replaced in chain Code Compression?
Information Sciences, 2020Co-Authors: Borut Žalik, Domen Mongus, Niko Lukač, Krista Rizman ŽalikAbstract:Abstract Burrows-Wheeler Transform, followed by Move-To-Front Transform, are often used transformation techniques in data Compression. They may reduce the information entropy of the input sequence, which becomes more compressible in this way. This paper suggests an alternative, a Prediction-based Move-To-Front Transform, which may replace the aforementioned transformations. According to the context, consisting of a few already seen symbols, the Prediction-based Move-To-Front Transform selects an appropriate ordered domain of symbols to achieve a better match with the currently transforming symbol. Freeman chain Code in four and eight directions, Three-Orthogonal chain Code, and Vertex Chain Code were used for experiments. We confirmed that the proposed approach, when using an appropriate length of context, reduces the information entropy to a similar extent as the Burrows-Wheeler Transform followed by the Move-To-Front Transform on chain Code data. Both approaches led to a very similar Compression efficiency on 32 testing shapes when an arithmetic Coder was used in the final stage. The proposed approach turned out to be more efficient when longer chain Code sequences were used, obtained by merging all the testing chain Codes of the same type.
-
Efficient chain Code Compression with interpolative coding
Information Sciences, 2018Co-Authors: Borut Žalik, Domen Mongus, Niko Lukač, Krista Rizman ŽalikAbstract:Abstract This paper considers the use of interpolative coding for lossless chain Code Compression. The most popular chain Codes are used, including Freeman chain Code in eight (F8) and four directions (F4), Vertex Chain Code (VCC), and three-orthogonal chain Code (3OT). The whole Compression pipeline consists of the Burrows–Wheeler transform, Move-To-Front transform and the interpolative coding, which was improved by FELICS and new Ψ-coding. The approach was compared with the state-of-the-art chain Code Compression algorithms. For VCC, 3OT and F4, the obtained results are slightly better than the existing approaches. However, an important improvement was achieved with F8 chain Code, where the presented approach is considerably better.
-
chain Code Compression using string transformation techniques
Digital Signal Processing, 2016Co-Authors: Borut Žalik, Domen Mongus, Krista Rizman Žalik, Niko LukačAbstract:Abstract This paper considers the suitability of string transformation techniques for lossless chain Codes' Compression. The more popular chain Codes are compressed including the Freeman chain Code in four and eight directions, the vertex chain Code, the three orthogonal chain Code, and the normalised directional chain Code. A testing environment consisting of the constant 0-symbol Run-Length Encoding ( RLE 0 L ), Move-To-Front Transformation (MTFT), and Burrows–Wheeler Transform (BWT) is proposed in order to develop a more suitable configuration of these techniques for each type of the considered chain Code. Finally, a simple yet efficient entropy coding is proposed consisting of MTFT, followed by the chain Code symbols' binarisation and the run-length encoding. PAQ8L compressor is also an option that can be considered in the final Compression stage. Comparisons were done between the state-of-the-art including the Universal Chain Code Compression algorithm, Move-To-Front based algorithm, and an algorithm, based on the Markov model. Interesting conclusions were obtained from the experiments: the sequential uses of MTFT, RLE 0 L , and BWT are reasonable only in the cases of shorter chain Codes' alphabets as with the vertex chain Code and the three orthogonal chain Code. For the remaining chain Codes, BWT alone provided the best results. The experiments confirm that the proposed approach is comparable against other lossless chain Code Compression methods, while in total achieving higher Compression rates.
-
chain Code lossless Compression using move to front transform and adaptive run length encoding
Signal Processing-image Communication, 2014Co-Authors: Borut Alik, Niko LukačAbstract:Chain Codes are the most size-efficient representations of rasterised binary shapes and contours. This paper considers a new lossless chain Code Compression method based on move-to-front transform and an adaptive run-length encoding. The former reduces the information entropy of the chain Code, whilst the latter compresses the entropy-reduced chain Code by coding the repetitions of chain Code symbols and their combinations using a variable-length model. In comparison to other state-of-the-art Compression methods, the entropy-reduction is highly efficient, and the newly proposed method yields, on average, better Compression.
Krista Rizman Žalik - One of the best experts on this subject based on the ideXlab platform.
-
Can burrows-Wheeler transform be replaced in chain Code Compression?
Information Sciences, 2020Co-Authors: Borut Žalik, Domen Mongus, Niko Lukač, Krista Rizman ŽalikAbstract:Abstract Burrows-Wheeler Transform, followed by Move-To-Front Transform, are often used transformation techniques in data Compression. They may reduce the information entropy of the input sequence, which becomes more compressible in this way. This paper suggests an alternative, a Prediction-based Move-To-Front Transform, which may replace the aforementioned transformations. According to the context, consisting of a few already seen symbols, the Prediction-based Move-To-Front Transform selects an appropriate ordered domain of symbols to achieve a better match with the currently transforming symbol. Freeman chain Code in four and eight directions, Three-Orthogonal chain Code, and Vertex Chain Code were used for experiments. We confirmed that the proposed approach, when using an appropriate length of context, reduces the information entropy to a similar extent as the Burrows-Wheeler Transform followed by the Move-To-Front Transform on chain Code data. Both approaches led to a very similar Compression efficiency on 32 testing shapes when an arithmetic Coder was used in the final stage. The proposed approach turned out to be more efficient when longer chain Code sequences were used, obtained by merging all the testing chain Codes of the same type.
-
Efficient chain Code Compression with interpolative coding
Information Sciences, 2018Co-Authors: Borut Žalik, Domen Mongus, Niko Lukač, Krista Rizman ŽalikAbstract:Abstract This paper considers the use of interpolative coding for lossless chain Code Compression. The most popular chain Codes are used, including Freeman chain Code in eight (F8) and four directions (F4), Vertex Chain Code (VCC), and three-orthogonal chain Code (3OT). The whole Compression pipeline consists of the Burrows–Wheeler transform, Move-To-Front transform and the interpolative coding, which was improved by FELICS and new Ψ-coding. The approach was compared with the state-of-the-art chain Code Compression algorithms. For VCC, 3OT and F4, the obtained results are slightly better than the existing approaches. However, an important improvement was achieved with F8 chain Code, where the presented approach is considerably better.
-
chain Code Compression using string transformation techniques
Digital Signal Processing, 2016Co-Authors: Borut Žalik, Domen Mongus, Krista Rizman Žalik, Niko LukačAbstract:Abstract This paper considers the suitability of string transformation techniques for lossless chain Codes' Compression. The more popular chain Codes are compressed including the Freeman chain Code in four and eight directions, the vertex chain Code, the three orthogonal chain Code, and the normalised directional chain Code. A testing environment consisting of the constant 0-symbol Run-Length Encoding ( RLE 0 L ), Move-To-Front Transformation (MTFT), and Burrows–Wheeler Transform (BWT) is proposed in order to develop a more suitable configuration of these techniques for each type of the considered chain Code. Finally, a simple yet efficient entropy coding is proposed consisting of MTFT, followed by the chain Code symbols' binarisation and the run-length encoding. PAQ8L compressor is also an option that can be considered in the final Compression stage. Comparisons were done between the state-of-the-art including the Universal Chain Code Compression algorithm, Move-To-Front based algorithm, and an algorithm, based on the Markov model. Interesting conclusions were obtained from the experiments: the sequential uses of MTFT, RLE 0 L , and BWT are reasonable only in the cases of shorter chain Codes' alphabets as with the vertex chain Code and the three orthogonal chain Code. For the remaining chain Codes, BWT alone provided the best results. The experiments confirm that the proposed approach is comparable against other lossless chain Code Compression methods, while in total achieving higher Compression rates.