Loeffler discrete cosine transform (DCT) algorithm is recognized as the most efficient one because it requires the theoretically least number of multiplications. However, many applications still encounter difficulty in performing the 11 multiplications required by the algorithm to calculate a 1D eight-point DCT. To avoid expensive multipliers in the hardware, we used two design methods, namely, distributed arithmetic (DA) and shift-and-add (SAA) methods, to design the DCT accelerator. The memory bandwidth is 60 bits: 24 bits for reads of the R(red), G(green), and B(blue) data of a pixel and 36 bits for writes of three corresponding 12-bit DCT coefficients. Thus, the 1D eight-point DCT accelerator for each of R, G, and B can have one 12-bit input port and one 12-bit output port so that it can calculate a 2D DCT by row-column decomposition method. The designs are adjusted to produce the same latency and interval. DA seems promising because Loeffler DCT requires only three small tables with four input bits. However, our experiments using Xilinx Vivado HLS show that the SAA design is better than the DA design for the considered applications. Furthermore, simulation results suggest that the optimal accelerator design can be obtained by adjusting the SAA design to the considered applications. The resultant SAA design requires only 13 adders (per color component) and can calculate one DCT coefficient per clock cycle. The precision of the internal hardware has been adjusted, such that the reconstructed images have PSNR values of at least 39.1 dB for all test images (Lenna, Pepper, House, and Cameraman). If a precision of 13bits is allowed, PSNR becomes at least 44.8 dB. Our presentation describes the architecture and operation of the optimized SAA design.

We examine the wormhole routing problem in terms of the "congestion" c and "dilation" d for a set of packet paths. We show, with mild restrictions, that there is a simple randomized algorithm for routing any set of P packets in O(cd/spl eta/+d/spl eta/ log P) time with high probability, where L is the number of flits in a packet, and /spl eta/=min {d, L}; only a constant number of flits are stored in each queue at any time. Using this result, we show that a fat tree network of area /spl ominus/(A) can simulate wormhole routing on any network of comparable area with O(log/sup 3/ A) slowdown, when all worms have the same length. Variable length worms are also considered. We run some simulations on the fat tree which show that not only does wormhole routing tend to perform better than the more heavily studied store and forward routing in this context, but that performance superior to our provable bound is attainable in practice.