检索结果-内蒙古大学图书馆

An optimal two-processor scheduling for a class of SWITCH-less program nets with combined OR-nodes

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2002年第6期E85A卷 1274-1280页

作者： Ge, QW Yamaguchi Univ Fac Educ Yamaguchi 7538513 Japan

This paper deals with two-processor nonpreemptive scheduling problem for acyclic SWITCH-less program nets including two types of nodes: AND-node and OR-node. Compared with task graphs that are a special case of acyclic SWITCH-less program nets and include only AND-nodes, the multiprocessor scheduling problem of general acyclic SWITCH-less program nets is more complicated. Since multiprocessor scheduling problem for general task graphs is NP-hard, so is for acyclic SWITCH-less program nets generally. In this paper, we suppose the acyclic SWITCH-less program nets satisfy: (i) each AND-node and OR-node have 1 and 0 node firing time, respectively;(ii) each AND-node possesses single input edge. For such a class of acyclic SWITCH-less program nets, we first propose a hybrid priority list L that consists of both dynamic and static sub-lists. Then we prove that, for a given acyclic SWITCH-less program net to be executed by two identical processors, the schedule generated by L is optimal.

关键词： program net two-processor scheduling hybrid priority list combined OR-node optimality

来源：评论

学校读者我要写书评

暂无评论

Sensitivity analysis of tree scheduling on two machines with communication delays

引用

PARALLEL COMPUTING 2004年第1期30卷 103-120页

作者： Guinand, F Moukrim, A Sanlaville, E Univ Havre Lab Informat Havre EA 3219 F-76058 Le Havre France

This paper presents a sensitivity analysis for the problem of scheduling trees with communication delays on two identical processors, to minimize the makespan. Tasks are supposed to have unit execution time (UET), and the values associated to communication delays are supposed unknown before the execution. The paper compares the optimal makespans with and without communication delays. The results are used to obtain sensitivity bounds for algorithms providing optimal schedules for graphs with unit execution and communication times (UECT). The notion of processor-ordered schedules, for two-processor systems, is introduced. It describes schedules in which all communications are oriented from one processor to the other. It is shown that these schedules are dominant for unit delays, for zero delays, but not for delays of less than or equal to one. We establish that algorithms building optimal processor-ordered schedules for UECT graphs admit an absolute sensitivity bound equal to the difference between the maximum and the minimum actual communication delays: omega-omega* less than or equal to c-c. This bound is tight. (C) 2003 Elsevier B.V. All rights reserved.

关键词： uncertain communication delays trees unit execution and communication times sensitivity analysis two-processor scheduling

来源：评论

学校读者我要写书评

暂无评论

two-processor scheduling of general acyclic SWITCH-less program nets via hybrid priority lists

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2000年第3期E83A卷 471-479页

作者： Ge, QW Yamaguchi Univ Fac Educ Yamaguchi 7538513 Japan

This paper deals with two-processor scheduling for general acyclic SWITCH-less program nets with random node firing times. First, we introduce a hybrid priority list L* that has been shown to generate optimal schedules for the acyclic SWITCH-less program nets with unity node firing times, of which AND-nodes possess at most single input edge. Then considering the factors of existence of the AND-nodes with two input edges as well as random node firing times, we extend L* to design a new dynamic priority list Ld and four static priority lists {L-si\i=1, 2, 3, 4};and then combining L-d and L-si (i=1,2,3,4) we propose four hybrid priority lists {L-i*\i=1, 2, 3, 4}. Finally, ive apply genetic algorithm to evaluate the schedules generated by the four lists through simulations on 400 program nets. Our simulation results show two of the four lists can generate reasonably good schedules.

关键词： data-flow program program net two-processor scheduling hybrid priority list genetic algorithm performance evaluation

来源：评论

学校读者我要写书评

暂无评论

On two-processor scheduling and maximum matching in permutation graphs

引用

INFORMATION PROCESSING LETTERS 1996年第6期57卷 321-327页

作者： Ramnath, S Sunder, S UNIV DELAWARE DEPT COMP SCINEWARKDE 19716

This paper gives an O(n log n) algorithm for computing the two-processor schedule fora set of n tasks, when the precedence constraints are specified by a transitively oriented permutation graph. This implies an O(n log n) algorithm for finding the maximum matching in a permutation graph, improving the O(n log(2) n) algorithm of Bauernoppel et al. (1995).

关键词： algorithms two-processor scheduling maximum matching permutation graphs

来源：评论

学校读者我要写书评

暂无评论

On considering communication in scheduling task graphs on parallel processors

引用

Parallel Algorithms and Applications 1994年第3-4期3卷 177-191页

作者： El-Rewini, Hesham Ali, Hesham H. Department of Computer Science University of Nebraska at Omaha Omaha NE 68182 United States

The problem of scheduling task graphs on multiprocessor systems is known to be NP-complete in its general form as well as many restricted cases. Few polynomial algorithms have been developed for solving special cases of this problem when the communication cost is ignored. The complexity of the problem rises even further when communication among tasks is considered. Several different models have been used by researchers to compute the communication cost. The complexity of the problem changes based on which cost model is used to estimate the communication cost. Several versions of the scheduling problem with communication were proven to be NP-complete using different models [10, 11]. In this paper, we first survey the different communication models. Focusing on one of these models, we study the effect of considering communication on the relationship between the two-processor scheduling problem and the problem of finding maximum matching in the complement of the task graph. We introduce the idea of augmented task graphs and show that in some cases scheduling an augmented graph without considering communication is equivalent to scheduling the original task graph with communication. We show that the problem of scheduling an arbitrary task graph with communication on two processors can be reduced to the problem of constructing an augmented graph. We introduce a polynomial algorithm to optimally schedule a tree-structured task graph with communication on two processors by the construction of its augmented graph. We also prove the optimality of the introduced algorithm. © 1994, Taylor & Francis Group, LLC. All rights reserved.

关键词： Augmented task graphs Communication models Maximum matching Parallel and distributed computers scheduling algorithms Task graphs Tree-structured graphs two-processor scheduling

来源：评论

学校读者我要写书评

暂无评论

COMPUTING THE BUMP NUMBER WITH TECHNIQUES FROM 2-processor scheduling

引用

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS 1988年第2期5卷 131-141页

作者： SCHAFFER, AA SIMONS, BB STANFORD UNIV DEPT COMP SCISTANFORDCA 94305 IBM RES ALMADEN RES CTRSAN JOSECA 95120

Let (X, x 1, x 2, ... has a bump whenever x ix i+1, and it has a jump whenever x iand x i+1are incomparable. The problem of finding a linear erxtension that minimizes the number of jumps has been studied extensively; ... 详细信息

Let (X, x ₁, x ₂, ... has a bump whenever x _ix _i+1, and it has a jump whenever x _iand x _i+1are incomparable. The problem of finding a linear erxtension that minimizes the number of jumps has been studied extensively; Pulleyblank shows that it is NP-complete in the general case. Fishburn and Gehrlein raise the question of finding a linear extension that minimizes the number of bumps. We show that the bump number problem is closely related to the well-studied problem of scheduling unit-time tasks with a precedence partial order on two identical processors. We point out that a variant of Gabow's linear-time algorithm for the two-processor scheduling problem solves the bump number problem. Habib, M?hring, and Steiner have independently discovered a different polynomial-time algorithm to solve the bump number problem.

关键词： Primary 06A10 Secondary 68R99 68Q20 Partially ordered set bump number linear extensions two-processor scheduling

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：