A latency-hiding MIMD wavelet transform

The discrete wavelet transform (DWT) may be used for applications in which real time execution is critical but data sizes are very large. Real-time execution can only be achieved through a parallel implementation. Published parallel implementations are suitable only for systems with very many (SIMD) processors or very few, specialized (systolic) processors. Neither approach is satisfactory for most MIMD systems, for which the algorithm used should be scalable across small to medium numbers of processors. The DWT has a tree-based structure which lends itself naturally to data-parallel SIMD implementations. Such implementations involve large amounts of synchronous, fine-grained communication. MIMD systems, especially those based on message-passing, cannot efficiently support the levels of communication demanded by SIMD algorithms without retailoring of the algorithm. A data driven algorithm which masks communication latency with computation is proposed as an alternative