Search

Abstract: A technique for scheduling and processor allocation leading to the synthesis of integrated heterogeneous pipelined processing elements, implementing digital signal processing applications, is proposed. The proposed technique achieves efficient hardware implementations at the logic-level by minimizing the number of processing units used, without compromising the rate and delay optimality criteria. The proposed algorithm is found to outperform algorithms resulting in homogeneous implementations, as it gives schedules with lower iteration periods, requires less hardware resources, and has lower time complexity at design time. In comparison with the already existing heterogeneous algorithms, the proposed algorithm produces schedules of lower time complexity and lower iteration period for some applications. The optimal performance of the proposed algorithm has been verified on several benchmarks. [Copyright &y& Elsevier]

This paper introduces a novel technique to obtain a schedule for a cyclic data-flow graph (DFG) onto a multiprocessor system. The optimality criteria considered in this scheduling technique are the maximum throughput, minimum input–output (I/O) delay, and minimum hardware resources. In this technique, an all-pair longest path algorithm is used to evaluate the relative firing times of the nodes of the given DFG. The proposed technique for finding these times is quite simple to implement and it has lower time complexity than all the previously proposed techniques. The technique is tested on various benchmark problems to demonstrate its optimal performance. All the optimality criteria are achieved on all the tested benchmarks. However, finding a minimum hardware resource schedule is an NP complete problem, and thus cannot be theoretically ensured. A formal proof of achieving both the throughput and the I/O delay optimality simultaneously is given, and an efficient technique to ensure this is also presented. This technique is quite simple and can be used to ensure delay optimality in any scheduling technique. [ABSTRACT FROM PUBLISHER]