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

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

来源：评论

学校读者我要写书评

暂无评论

PARAdeg-processor scheduling for acyclic SWITCH-less program nets

引用

JOURNAL OF THE FRANKLIN INSTITUTE-ENGINEERING AND APPLIED MATHEMATICS 1999年第7期336卷 1135-1153页

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

This paper deals with multiprocessor scheduling for acyclic SWITCH-less program nets that is a graph representation of a data-flow program. A task graph is a special case of acyclic SWITCH-less net PN and the important difference is that a program net allows nodes to fire more than once while a task graph asks its each node to fire exactly once. Hence scheduling problem for program nets is NP-hard in a stronger sense. In this paper, we first extend CP (critical path) method by taking firing numbers of nodes into account to propose extended critical path (ECP) method. Based on this we further propose ORF/ECP (OR-node First/ECP), and LTF/ECP (Larger node firing Time First/ECP) methods, by taking notice of firings of OR-nodes and node firing times, respectively. Then using priority lists as populations, we propose two genetic algorithms n-GA and 1-GA, by, respectively, requiring all and only initial populations satisfying precedence relation of nodes. Our experiments show that: (i) precedence relation of nodes is no more important for scheduling of program nets;(ii) 1-GA gives the best results, and LTF/ECP is next to 1-GA and is effective when node firing numbers are not large. (C) 1999 The Franklin Institute. Published by Elsevier Science Ltd. All rights reserved.

关键词： data-flow program program net multiprocessor scheduling list scheduling GA scheduling evaluation

来源：评论

学校读者我要写书评

暂无评论

On verification of token self-cleanness of data-flow program nets

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 1996年第6期E79A卷 812-817页

作者： Ge, QW Onaga, K Yamaguchi Univ Yamaguchi-shi Japan

A data-flow program net is a graph representation of data-flow programs consisting of three types of nodes, AND-node, OR-node and SWITCH-node, which represent arithmetic/logical, data merge and context switch operations respectively. Token self-cleanness is an important property of a dataflow program and is such that if date-flow programs satisfy the property then a date-flow computer can efficiently withdraw copies from given programs during executions. In this paper, we classify program nets into SWITCH-less, OR-less and general nets, and analyse structures of data-flow program nets to propose verification methods of token self-cleanness by investigating token numbers appearing on the edges. As a result, a necessary and sufficient condition is proposed for SWITCH-less data-flow program nets and sufficient conditions are given for OR-less and general data-flow program nets.

关键词： data-flow program program net token self-cleanness verification

来源：评论

学校读者我要写书评

暂无评论

Computation of minimum firing time for general self-cleaning SWITCH-less program nets

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 1998年第6期E81A卷 1072-1078页

作者： Ge, QW Yanagida, H Onaga, K Yamaguchi Univ Fac Educ Yamaguchi 7530841 Japan Fujitsu Ten Ltd Kobe Hyogo 6528510 Japan Univ Ryukyus Fac Engn Okinawa 9030129 Japan

A data-flow program net is a graph representation of data-Row programs consisting of three types of nodes, AND-node, OR-node and SWITCH-node, which represent arithmetic/logical, data merge and context switch operations respectively. Minimum firing (completion) time (T) under bar of a program net is an important element in computing parallel degree PARAdeg residing in a data-flow program and is defined as the minimum time when the program net is executed by enough many processors. In this paper, we propose algorithms to efficiently compute (T) under bar by contracting AND-nodes generally for self cleaning SWITCH-less program nets with arbitrary node firing time and give the experimental results of the algorithms to show the efficiency.

关键词： data-flow program program net minimum firing time node contraction

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：