Degree of parallelism (DoP) is an essential complexity metric that characterizes the number of independent operation sets (IOSs) that can be concurrently executed within an algorithm. This paper presents a generic framework to identify IOSs and to quantify the DoP based on rank theorem in linear algebra. This framework is applied to extract algorithmic parallelisms at various granularities, namely, multigrain parallelism. Our parallelism is intrinsic and platform independent and can provide insights into architectural information, thus facilitating mapping onto generic platforms and early back annotation for modifying algorithms. It plays a significant role in the concurrent optimization of both algorithms and architectures, referred to as Algorithm/Architecture Coexploration (AAC), by trading off between the DoP and the number of operations (NoO). This paper reports three case studies for AAC. The case study on an IDCT reveals that our framework accurately quantifies the parallelism for mapping the algorithm onto generic platforms, including FPGA and multicore systems. The IDCT parallelized by our technique surpasses a conventional spectral parallelization. By exploiting fine-grain parallelism, this paper presents a better porting of a discrete wavelet transform (DWT) onto single instruction multiple data (SIMD) machines compared with a commercial compiler. A high-quality deinterlacer is implemented on a low-cost multicore platform for real-time high-definition applications by analyzing the multigrain parallelism. These case studies reveal the effectiveness of our parallel analysis framework which is applicable to generic systems. Compared with traditional graph traversal techniques, our linear algebraic approach impressively features low complexity and is practical for complicated algorithms.

In this paper, an area efficient reconfigurable inverse transformation architecture for multiple standards is proposed. We present a top-down design methodology with complexity analysis, commonalities extraction, and dataflow modeling to systematically design reconfigurable architecture. By exporting and sharing the commonalities, the adder usage of the proposed reconfigurable inverse transform processing element can be reduced 44% compared with the total amount of adders in performing target inverse transform types. Then, the reconfigurable architecture is synthesized using TSMC 0.18 urn library. The working frequency is 108Mhz, which is derived from the dataflow scheduling. The area synthesis result is 32k gates, which indicates that the proposed design has more efficient area than other documented design in VLSI implementation. In addition, the proposed architecture also satisfies the accuracy requirement. Therefore, the proposed design have lower cost and enough flexibility for multi-standard purposes with 1920×1088 resolution and 64 frames per second and the color format is 4:2:0 for real time processing.