PARALLEL ALGORITHMS FOR REDUNDANT PRECEDENCE RELATIONS ELIMINATION IN TASK SYSTEMS

被引：3
作者：
MAHJOUB, Z
KAROUISAHTOUT, F
机构：
[1] Faculté des Sciences de Tunis, Département Informatique, Belvédère
来源：
PARALLEL COMPUTING | 1991年 / 17卷 / 4-5期
关键词：
TASK AND PRECEDENCE GRAPHS AND SYSTEMS; REDUNDANT PRECEDENCE RELATIONS ELIMINATION; WEAK TRANSITIVE CLOSURE; TRIANGULAR TASK GRAPH; TASK ASSIGNMENT; PROCESSOR SCHEDULING;
D O I：
10.1016/S0167-8191(05)80149-8
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We present in this paper some properties of task graphs used in algorithm parallelization and study the problem of redundant precedence relations in the associated task systems. We then analyze the parellelization of three redundanct elimination algorithms based on the weak transitive closure of the precedence partial order. Optimal results on complexity, task assignment and processor scheduling are discussed in detail.
引用
收藏
页码：471 / 481
页数：11
相关论文
共 12 条
  • [1] BAALA H, 1989, METHODOLOGIE PARALLE
  • [2] BERGE C, 1973, GRAPHES HYPERGRAPHES
  • [3] BOITTIAUX J, 1970, MATH INFORMATIQUE, V2
  • [4] CHARTRAND G., 1977, INTRO GRAPH THEORY
  • [5] Coffman Jr E. G., 1973, OPERATING SYSTEMS TH
  • [6] COSNARD M, 1987, TSI-TECH SCI INF, V6, P115
  • [7] COSNARD M, 1987, PARALLELISATION ALGO
  • [8] Knuth D.E, 1975, ART COMPUTER PROGRAM, V1
  • [9] KUMAR SP, 1982, THESIS WASHINGTON ST
  • [10] SOLVING LINEAR ALGEBRAIC EQUATIONS ON AN MIMD COMPUTER
    LORD, RE
    KOWALIK, JS
    KUMAR, SP
    [J]. JOURNAL OF THE ACM, 1983, 30 (01) : 103 - 117
12