EFFICIENT SCHEDULING ALGORITHMS FOR ROBOT INVERSE DYNAMICS COMPUTATION ON A MULTIPROCESSOR SYSTEM

被引:31
作者
CHEN, CL [1 ]
LEE, CSG [1 ]
HOU, ESH [1 ]
机构
[1] PURDUE UNIV, DEPT ELECT ENGN, INDIANAPOLIS, IN 46223 USA
来源
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS | 1988年 / 18卷 / 05期
关键词
Computer Systems; Digital--Parallel Processing - Control Systems; Nonlinear - Control Systems; Optimal - Equations of Motion - Systems Science and Cybernetics--Heuristic Programming;
D O I
10.1109/21.21600
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
The problem of scheduling the robot inverse dynamics computation consisting of m computational modules to be executed on a multiprocessor system consisting of p identical homogeneous processors to achieve a minimum-schedule length is examined. This scheduling problem is known to be NP-complete. To achieve the minimum computation time, the Newton-Euler equations of motion are expressed in the homogeneous linear recurrence form that results in achieving maximum parallelism. To speed up the searching for a solution, a heuristic search algorithm called dynamical highest-level-first/most-immediate-successors-first (DHLF/MISF) is first proposed to find a fast but suboptimal schedule. For an optimal schedule the minimum-schedule-length problem can be solved by a state-space search method - the A* algorithm coupled with an efficient heuristic function derived from the Fernandez and Bussell bound. An objective function is defined in terms of the task execution time, and the optimization of the objective function is based on the minimax of the execution time. The proposed optimization algorithm solves the minimum-schedule-length problem in pseudopolynomial time and can be used to solve various large-scale problems in a reasonable time.
引用
收藏
页码:729 / 743
页数:15
相关论文
共 21 条
[1]   COMPARISON OF LIST SCHEDULES FOR PARALLEL PROCESSING SYSTEMS [J].
ADAM, TL ;
CHANDY, KM ;
DICKSON, JR .
COMMUNICATIONS OF THE ACM, 1974, 17 (12) :685-690
[2]  
BARHEN J, 1985, 1985 P ASME INT C CO, V3, P415
[3]  
CHEN CL, 1987, TREE8727 TECH REP
[4]  
Coffman E.G., 1976, COMPUTER JOB SHOP SC
[5]   BOUNDS ON NUMBER OF PROCESSORS AND TIME FOR MULTIPROCESSOR OPTIMAL SCHEDULES [J].
FERNANDEZ, EB ;
BUSSELL, B .
IEEE TRANSACTIONS ON COMPUTERS, 1973, C-22 (08) :745-751
[6]   PERFORMANCE GUARANTEES FOR SCHEDULING ALGORITHMS [J].
GAREY, MR ;
GRAHAM, RL ;
JOHNSON, DS .
OPERATIONS RESEARCH, 1978, 26 (01) :3-21
[7]  
GONZALEZ MJ, 1977, COMPUT SURV, V9, P173, DOI 10.1145/356698.356700
[8]  
KANADE T, 1984, DEC P IEEE C DEC CON, P1345
[9]  
KASAHARA H, 1984, IEEE T COMPUT, V33, P1023, DOI 10.1109/TC.1984.1676376
[10]  
Kasahara H., 1985, IEEE Journal of Robotics and Automation, VRA-1, P104, DOI 10.1109/JRA.1985.1087004