TASK ALLOCATION AND SCHEDULING MODELS FOR MULTIPROCESSOR DIGITAL SIGNAL-PROCESSING

被引:12
作者
KONSTANTINIDES, K
KANESHIRO, RT
TANI, JR
机构
[1] Hewlett-Packard Laboratories, Palo Alto
来源
IEEE TRANSACTIONS ON ACOUSTICS SPEECH AND SIGNAL PROCESSING | 1990年 / 38卷 / 12期
关键词
D O I
10.1109/29.61542
中图分类号
O42 [声学];
学科分类号
070206 ; 082403 ;
摘要
This paper presents models and techniques for the task allocation and scheduling problem, subject to task precedence, memory requirements, and interprocessor communication costs. Traditional models assume sequential I/O and computing activities, and linear memory requirements. The new models take into account the special characteristics of new architectures and may handle both sequential I/O and program execution and parallel I/O and program execution within a processor. Furthermore, both linear and nonlinear memory requirements may be modeled. The models also take into special consideration the unique requirements and characteristics of digital signal processing applications. By distinguishing between tasks that require all the output data from a predecessor before they begin execution (for example, an FFT) and tasks that require only partial data (for example, filtering applications), our models are more realistic and the accuracy and efficiency of our schedules are further improved. Both periodic and nonperiodic schedules are considered. Periodic schedules maximize the throughput, while nonperiodic schedules minimize the computation time. A simple branch and bound technique is presented, and it is applied to the solution of the task allocation problem. The algorithm incorporates simple forward and backward searching techniques from the theory of 0-1 linear programming, and can easily be adapted to fit any of the scheduling models by simply modifying its cost function. Various examples are also presented. © 1990 IEEE
引用
收藏
页码:2151 / 2161
页数:11
相关论文
共 27 条
[1]  
BLAZEWICZ J, 1979, PEROFRMANCE COMPUTER
[2]  
BLAZEWICZ J, 1986, IEEE T COMPUT C MAY, V35
[3]  
Chang H., 1986, Proceedings of the Real-Time Systems Symposium (Cat. No.86CH2351-5), P175
[4]  
Chu W. W., 1980, IEEE COMPUT NOV, P57
[5]  
Coffman E.G., 1976, COMPUTER JOB SHOP SC
[6]  
Dasarathy B., 1984, Proceedings of the Real-Time Systems Symposium (Cat. No. 84CH2105-5), P135
[7]  
EFE K, 1982, IEEE COMPUTER JUN, P50
[8]   DESIGN AND EVALUATION OF AN ARCHITECTURE FOR A DIGITAL SIGNAL PROCESSOR FOR INSTRUMENTATION APPLICATIONS [J].
FELLMAN, RD ;
KANESHIRO, RT ;
KONSTANTINIDES, K .
IEEE TRANSACTIONS ON ACOUSTICS SPEECH AND SIGNAL PROCESSING, 1990, 38 (03) :537-546
[9]  
Garfinkel R. S., 1972, INTEGER PROGRAMMING
[10]   INTEGER PROGRAMMING BY IMPLICIT ENUMERATION AND BALAS METHOD [J].
GEOFFRION, AM .
SIAM REVIEW, 1967, 9 (02) :178-+