Vectorized transforms in scalar processors

摘要

We disclose a generalized approach to creating efficientnimplementations of linear, orthogonal transforms, with specific examplesndiscussed for the 8 x 8 DCT used in image compression. We connect thisnwith a method for performing signed, parallel processing in scalar,noff-the-shelf processors for integer transforms. Uniform data precisionnmay be used, but is not required for the method. The coefficientsnresulting from the new algorithm converge more quickly than thenapproximation made to the coefficients. Furthermore, the new algorithmnallows more control of the specific representation chosen for thencoefficients, as is detailed below. The methods described were designednfor addressing this need with two's-complement arithmetic. Data that cannbe processed in parallel, because of the algorithm structure, are packednin a "vector" format, described, into registers. Many signed arithmeticnoperations can be performed on these vectors, including addition,nsubtraction, multiplication by scalars, shifting, and others. When thenparallel processing is completed, the vectors can be unpacked intonscalar values for storage or subsequent processing. The importance ofnthese methods lies in their handling of carries and borrows in thenpacked vector format. The generalized method is described. Notation isngiven at the beginning to establish consistency through the article. Wendiscuss a generalized approach to integer transforms, using the DCT as anspecific example. Then we detail the vector format, which allows vectorncomputation in scalar processors of parallelizable algorithms. The IDCTnis used as a numerical example in the discussion of the vector format.nThe results were developed for high-end printers (e.g., more than 100npages per minute), where image compression and decompression must benperformed in real time, either in FPGAs, or in embedded processors;nhowever, the methods are applicable to a broad range of signalnprocessing systems