The Experts below are selected from a list of 43308 Experts worldwide ranked by ideXlab platform
Shaoyi Chien - One of the best experts on this subject based on the ideXlab platform.
-
an h 264 avc scalable extension and high profile hdtv 1080p encoder chip
Symposium on VLSI Circuits, 2008Co-Authors: Yihau Chen, Tzuder Chuang, Yujen Chen, Chiajung Hsu, Shaoyi ChienAbstract:The first single-chip H.264/AVC HDTV 1080 p encoder for scalable extension (SVC) with high profile is implemented on a 16.76 mm2 die with 90 nm process. It dissipates 349/439 mW at 120/166 MHz for high profile and SVC encoding. The proposed frame-parallel architecture halves external Memory bandwidth and operating frequency. Moreover, the prediction architecture with inter-layer prediction tools are applied to further save 70% external Memory bandwidth and 50% Internal Memory access.
-
hardware architecture for global motion estimation for mpeg 4 advanced simple profile
International Symposium on Circuits and Systems, 2004Co-Authors: Chingyeh Chen, Weimin Chao, Shaoyi Chien, Yuwen HuangAbstract:Global motion estimation and compensation (GME/GMC) is a new and important coding tool in MPEG-4 Advanced Simple Profile (ASP). The coding gain of GME/GMC is 1-1.6 dB compared to that without GMC. However, because of the irregular Memory access and huge Memory bandwidth of GME/GMC, few hardware architectures have been proposed. In this paper, we proposed an algorithm which can save 87.27% Memory bandwidth compared to that of the original algorithm. By the proposed arrangement of Memory, the impact of the irregular Memory access is reduced, and four neighboring pixels, which are used for the interpolation of GMC, can be accessed in one cycle. Finally, we also proposed a hardware architecture for GME in MPEG-4 ASP@L5. The total gate count is 131 K, at 100 MHz and the Internal Memory size is about 10.8 Kb. It is reasonable to be integrated into MPEG-4 ASP encoders.
Jeffrey Scott Vitter - One of the best experts on this subject based on the ideXlab platform.
-
efficient maximal repeat finding using the burrows wheeler transform and wavelet tree
IEEE ACM Transactions on Computational Biology and Bioinformatics, 2012Co-Authors: M O Kulekci, Jeffrey Scott VitterAbstract:Finding repetitive structures in genomes and proteins is important to understand their biological functions. Many data compressors for modern genomic sequences rely heavily on finding repeats in the sequences. Small-scale and local repetitive structures are better understood than large and complex interspersed ones. The notion of maximal repeats captures all the repeats in the data in a space-efficient way. Prior work on maximal repeat finding used either a suffix tree or a suffix array along with other auxiliary data structures. Their space usage is 19-50 times the text size with the best engineering efforts, prohibiting their usability on massive data such as the whole human genome. We focus on finding all the maximal repeats from massive texts in a time- and space-efficient manner. Our technique uses the Burrows-Wheeler Transform and wavelet trees. For data sets consisting of natural language texts and protein data, the space usage of our method is no more than three times the text size. For genomic sequences stored using one byte per base, the space usage of our method is less than double the sequence size. Our space-efficient method keeps the timing performance fast. In fact, our method is orders of magnitude faster than the prior methods for processing massive texts such as the whole human genome, since the prior methods must use external Memory. For the first time, our method enables a desktop computer with 8 GB Internal Memory (actual Internal Memory usage is less than 6 GB) to find all the maximal repeats in the whole human genome in less than 17 hours. We have implemented our method as general-purpose open-source software for public use.
-
algorithms and data structures for external Memory
2008Co-Authors: Jeffrey Scott VitterAbstract:Data sets in large applications are often too massive to fit completely inside the computer's Internal Memory. The resulting input/output communication (or I/O) between fast Internal Memory and slower external Memory (such as disks) can be a major performance bottleneck. In this manuscript, we survey the state of the art in the design and analysis of algorithms and data structures for external Memory (or EM for short), where the goal is to exploit locality and parallelism in order to reduce the I/O costs. We consider a variety of EM paradigms for solving batched and online problems efficiently in external Memory. For the batched problem of sorting and related problems like permuting and fast Fourier transform, the key paradigms include distribution and merging. The paradigm of disk striping offers an elegant way to use multiple disks in parallel. For sorting, however, disk striping can be nonoptimal with respect to I/O, so to gain further improvements we discuss distribution and merging techniques for using the disks independently. We also consider useful techniques for batched EM problems involving matrices, geometric data, and graphs. In the online domain, canonical EM applications include dictionary lookup and range searching. The two important classes of indexed data structures are based upon extendible hashing and B-trees. The paradigms of filtering and bootstrapping provide convenient means in online data structures to make effective use of the data accessed from disk. We also re-examine some of the above EM problems in slightly different settings, such as when the data items are moving, when the data items are variable-length such as character strings, when the data structure is compressed to save space, or when the allocated amount of Internal Memory can change dynamically. Programming tools and environments are available for simplifying the EM programming task. We report on some experiments in the domain of spatial databases using the TPIE system (Transparent Parallel I/O programming Environment). The newly developed EM algorithms and data structures that incorporate the paradigms we discuss are significantly faster than other methods used in practice.
-
external Memory algorithms and data structures dealing with massive data
ACM Computing Surveys, 2001Co-Authors: Jeffrey Scott VitterAbstract:Data sets in large applications are often too massive to fit completely inside the computers Internal Memory. The resulting input/output communication (or I/O) between fast Internal Memory and slower external Memory (such as disks) can be a major performance bottleneck. In this article we survey the state of the art in the design and analysis of external Memory (or EM) algorithms and data structures, where the goal is to exploit locality in order to reduce the I/O costs. We consider a variety of EM paradigms for solving batched and online problems efficiently in external Memory. For the batched problem of sorting and related problems such as permuting and fast Fourier transform, the key paradigms include distribution and merging. The paradigm of disk striping offers an elegant way to use multiple disks in parallel. For sorting, however, disk striping can be nonoptimal with respect to I/O, so to gain further improvements we discuss distribution and merging techniques for using the disks independently. We also consider useful techniques for batched EM problems involving matrices (such as matrix multiplication and transposition), geometric data (such as finding intersections and constructing convex hulls), and graphs (such as list ranking, connected components, topological sorting, and shortest paths). In the online domain, canonical EM applications include dictionary lookup and range searching. The two important classes of indexed data structures are based upon extendible hashing and B-trees. The paradigms of filtering and bootstrapping provide a convenient means in online data structures to make effective use of the data accessed from disk. We also reexamine some of the above EM problems in slightly different settings, such as when the data items are moving, when the data items are variable-length (e.g., text strings), or when the allocated amount of Internal Memory can change dynamically. Programming tools and environments are available for simplifying the EM programming task. During the course of the survey, we report on some experiments in the domain of spatial databases using the TPIE system (transparent parallel I/O programming environment). The newly developed EM algorithms and data structures that incorporate the paradigms we discuss are significantly faster than methods currently used in practice.
-
A Simple and Efficient Parallel Disk Mergesort
ACM, 1999Co-Authors: Rakesh D. Barve, Jeffrey Scott VitterAbstract:External sorting---the process of sorting a massive data set that is too large to fit into the computer's Internal Memory and must be stored externally on disks---is a fundamental primitive in database systems and serves in addition as a core subroutine in many other database operations [Gra93, IBM90]. Technology trends indicate that developing techniques that effectively use multiple disks in parallel in order to speed up the performance of external sorting is of prime importance. The simple randomized merging (SRM ) mergesort algorithm proposed by Barve et al. [BGV97] is the first parallel disk sorting algorithm that requires a provably optimal number of passes and that is fast in practice. Knuth [Knu98, Section 5.4.9] recently identified SRM (which he calls "randomized striping") as the method of choice for sorting with parallel disks
-
external Memory computational geometry
Foundations of Computer Science, 1993Co-Authors: Michael T Goodrich, Jyhjong Tsay, Darren Erik Vengroff, Jeffrey Scott VitterAbstract:In this paper we give new techniques for designing efficient algorithms for computational geometry problems that are too large to be solved in Internal Memory. We use these techniques to develop optimal and practical algorithms for a number of important large-scale problems. We discuss our algorithms primarily in the context of single processor/single disk machines, a domain in which they are not only the first known optimal results but also of tremendous practical value. Our methods also produce the first known optimal algorithms for a wide range of two-level and hierarchical multilevel Memory models, including parallel models. The algorithms are optimal both in terms of I/O cost and Internal computation. >
Tian-sheuan Chang - One of the best experts on this subject based on the ideXlab platform.
-
Memory Analysis for H.264/AVC Scalable Extension Decoder
2016Co-Authors: Po-yuan Hsu, Tian-sheuan ChangAbstract:Abstract — In this paper, a systematic analysis for Memory usage in H.264/AVC scalable extension (SVC) decoder is presented. This paper analyzes the Memory requirements with three different decoding flows, macroblock, row and frame based, to find out a best method which can achieve optimal trade-off between Internal Memory usage and external Memory access. The analysis shows that the SVC decoding needs 88 % to 110 % extra Memory bandwidth compared to single layer H.264 decoding due to inter-layer prediction disregarding of decoding flow. However, extra Internal Memory storage by inter-layer prediction varies a lot according to the flow. This analysis could provide as a foundation to design a SVC decoder for further step. Index Terms — scalable video coding (SVC), decode
-
A Memory Efficient Fine Grain Scalability Coefficient Encoding Method for H.264/AVC Scalable Video Extension
2015Co-Authors: Meng-wei Shen, Tian-sheuan ChangAbstract:Abstract—In this paper, a Memory efficient Fine Grain Scalability (FGS) coefficient encoding method is proposed to reduce the external Memory access requirement. In the H.264/AVC Scalable Video Extension, the FGS coefficients encoding is frame based. However, the frame based mechanism results in the difficulty of hardware implementation due to large Internal Memory requirements and external Memory accesses. Therefore, a non-uniform Memory size design which can achieve low external Memory access is proposed to realize the macroblock based FGS coefficients encoding. Compared to previous work, our proposed method can save at least 38KB external Memory accesses per frame in average. I
-
vlsi architecture for real time hd1080p view synthesis engine
IEEE Transactions on Circuits and Systems for Video Technology, 2011Co-Authors: Yingrung Horng, Yucheng Tseng, Tian-sheuan ChangAbstract:This paper presents a real-time HD1080p view synthesis engine based on the reference algorithm from 3-D video coding team by solving high computational complexity and high Memory cost problems. For the computational complexity, we propose the bilinear interpolation to simplify the hole filling process, and the Z scaling method with floating-point format to reduce the cost of homography calculation. For the Memory cost, we propose the frame-level pipelining to reduce the requirement of warped depth maps, and the column-order warping method to remove the Z-buffer in occlusion handling. With the 90 nm complementary metal-oxide-semiconductor technology, our view synthesis engine can archive the throughput of 32.4 f/s for HD1080p videos with the gate count of 268.5 K and the Internal Memory of 69.4 kbytes. The experimental result shows our implementation has the similar synthesis quality as the original reference algorithm.
Yuwen Huang - One of the best experts on this subject based on the ideXlab platform.
-
hardware architecture for global motion estimation for mpeg 4 advanced simple profile
International Symposium on Circuits and Systems, 2004Co-Authors: Chingyeh Chen, Weimin Chao, Shaoyi Chien, Yuwen HuangAbstract:Global motion estimation and compensation (GME/GMC) is a new and important coding tool in MPEG-4 Advanced Simple Profile (ASP). The coding gain of GME/GMC is 1-1.6 dB compared to that without GMC. However, because of the irregular Memory access and huge Memory bandwidth of GME/GMC, few hardware architectures have been proposed. In this paper, we proposed an algorithm which can save 87.27% Memory bandwidth compared to that of the original algorithm. By the proposed arrangement of Memory, the impact of the irregular Memory access is reduced, and four neighboring pixels, which are used for the interpolation of GMC, can be accessed in one cycle. Finally, we also proposed a hardware architecture for GME in MPEG-4 ASP@L5. The total gate count is 131 K, at 100 MHz and the Internal Memory size is about 10.8 Kb. It is reasonable to be integrated into MPEG-4 ASP encoders.
-
analysis and hardware architecture for global motion estimation in mpeg 4 advanced simple profile
International Symposium on Circuits and Systems, 2003Co-Authors: Shaoli Chien, Chingyeh Chen, Weimin Chao, Yuwen HuangAbstract:Global motion estimation (GME) and compensation is one of the key modules in MPEG-4 Advanced Simple Profile (ASP). However, there are no hardware architectures for GME since existing algorithms are not suitable for hardware implementation. In this paper, GME in MPEG-4 ASP is analyzed, and a hardware-oriented GME algorithm is proposed according to the analysis results, which is a combination of a feature points based algorithm and a novel iterative sprite point matching algorithm. The associated hardware architecture is also proposed. Simulation results show that the performance of the proposed algorithm is the same as that of MPEG-4 Verification Model. The implementation results show the proposed hardware architecture can achieve the requirements of MPEG-4 ASP@L3 with 66K gates and 31Kb Internal Memory at 100 MHz working frequency.
Elaine Shi - One of the best experts on this subject based on the ideXlab platform.
-
lower bounds for external Memory integer sorting via network coding
Communications of The ACM, 2020Co-Authors: Alireza Farhadi, Mohammadtaghi Hajiaghayi, Kasper Green Larsen, Elaine ShiAbstract:Sorting extremely large datasets is a frequently occurring task in practice. These datasets are usually much larger than the computer's main Memory; thus, external Memory sorting algorithms, first introduced by Aggarwal and Vitter, are often used. The complexity of comparison-based external Memory sorting has been understood for decades by now; however, the situation remains elusive if we assume the keys to be sorted are integers. In Internal Memory, one can sort a set of n integer keys of Θ(lg n) bits each in O(n) time using the classic Radix Sort algorithm; however, in external Memory, there are no faster integer sorting algorithms known than the simple comparison-based ones. Whether such algorithms exist has remained a central open problem in external Memory algorithms for more than three decades.In this paper, we present a tight conditional lower bound on the complexity of external Memory sorting of integers. Our lower bound is based on a famous conjecture in network coding by Li and Li, who conjectured that network coding cannot help anything beyond the standard multicommodity flow rate in undirected graphs.The only previous work connecting the Li and Li conjecture to lower bounds for algorithms is due to Adler et al. Adler et al. indeed obtain relatively simple lower bounds for oblivious algorithms (the Memory access pattern is fixed and independent of the input data). Unfortunately, obliviousness is a strong limitation, especially for integer sorting: we show that the Li and Li conjecture implies an Ω(n lg n) lower bound for Internal Memory oblivious sorting when the keys are Θ(lg n) bits. This is in sharp contrast to the classic (nonoblivious) Radix Sort algorithm. Indeed, going beyond obliviousness is highly nontrivial; we need to introduce several new methods and involved techniques, which are of their own interest, to obtain our tight lower bound for external Memory integer sorting.
-
lower bounds for external Memory integer sorting via network coding
arXiv: Data Structures and Algorithms, 2018Co-Authors: Alireza Farhadi, Mohammadtaghi Hajiaghayi, Kasper Green Larsen, Elaine ShiAbstract:Sorting extremely large datasets is a frequently occuring task in practice. These datasets are usually much larger than the computer's main Memory; thus external Memory sorting algorithms, first introduced by Aggarwal and Vitter (1988), are often used. The complexity of comparison based external Memory sorting has been understood for decades by now, however the situation remains elusive if we assume the keys to be sorted are integers. In Internal Memory, one can sort a set of $n$ integer keys of $\Theta(\lg n)$ bits each in $O(n)$ time using the classic Radix Sort algorithm, however in external Memory, there are no faster integer sorting algorithms known than the simple comparison based ones. In this paper, we present a tight conditional lower bound on the complexity of external Memory sorting of integers. Our lower bound is based on a famous conjecture in network coding by Li and Li, who conjectured that network coding cannot help anything beyond the standard multicommodity flow rate in undirected graphs. The only previous work connecting the Li and Li conjecture to lower bounds for algorithms is due to Adler et al. Adler et al. indeed obtain relatively simple lower bounds for oblivious algorithms (the Memory access pattern is fixed and independent of the input data). Unfortunately obliviousness is a strong limitations, especially for integer sorting: we show that the Li and Li conjecture implies an $\Omega(n \log n)$ lower bound for Internal Memory oblivious sorting when the keys are $\Theta(\lg n)$ bits. This is in sharp contrast to the classic (non-oblivious) Radix Sort algorithm. Indeed going beyond obliviousness is highly non-trivial; we need to introduce several new methods and involved techniques, which are of their own interest, to obtain our tight lower bound for external Memory integer sorting.