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

MICROPROCESSING AND MICROPROGRAMMING 1986年第1期17卷 29-40页

作者： RAO, SU MAJUMDAR, AK INDIAN INST TECHNOL DEPT COMP SCI & ENGNKHARAGPUR 721302W BENGALINDIA TATA IRON & STEEL CO DIV BEARINGSDEPT SYSTKHARAGPUR 721301INDIA

Microcode compaction is an essential tool for efficient translation of microprograms in computers. This paper describes and compares the performance of a few list scheduling algorithms for local microcode compaction. A new approach to utilize resource conflict information in microcode compaction has been development and a dynamic modification of the microoperation weights has been suggested. The dynamic modification approach has been found to be efficient (worst case computational complexity of order N 3 ), and is capable of handling long microprogram graphs. Simulation results comparing the performance of the list scheduling algorithms are also reported.

关键词： Horizontal microprogramming Code optimization Parallel processing list scheduling algorithms Data dependency Microcode compaction Resource conflict

来源：评论

学校读者我要写书评

暂无评论

The equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays

引用

JOURNAL OF scheduling 2017年第3期20卷 303-311页

作者： Carlier, Aurelien Hanen, Claire Kordon, Alix Munier UPMC Univ Paris 06 Sorbonne Univ CNRS LIP6UMR 7606 4 Pl Jussieu F-75005 Paris France Univ Paris Ouest Nanterre Def Univ Paris Lumieres F-92000 Paris France

We consider a finite set of unit time execution tasks with release dates, due dates and precedence delays. The machines are partitioned into k classes. Each task requires one machine from a fixed class to be executed. The problem is the existence of a feasible schedule. This general problem is known to be -complete;many studies were devoted to the determination of polynomial time algorithms for some special subcases, most of them based on a particular list schedule. The Garey-Johnson and Leung-Palem-Pnueli algorithms (respectively GJ and LPP in short) are both improving the due dates to build a priority list. They are modifying them using necessary conditions until a fixed point is reached. The present paper shows that these two algorithms are different implementations of the same generic one. The main consequence is that all the results valid for GJ algorithm are also for LPP and vice versa.

关键词： list scheduling algorithms Polynomial subproblems Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Stochastic machine scheduling with precedence constraints

引用

SIAM JOURNAL ON COMPUTING 2005年第4期34卷 788-802页

作者： Skutella, M Uetz, M Univ Dortmund Fachbereich Math D-44227 Dortmund Germany Univ Maastricht Fac Econ & Business Adm NL-6200 MD Maastricht Netherlands

We consider parallel, identical machine scheduling problems, where the jobs are subject to precedence constraints and release dates, and where the processing times of jobs are governed by independent probability distributions. Our objective is to minimize the expected value of the total weighted completion time. Building upon a linear programming relaxation by Mohring, Schulz, and Uetz [ J. ACM, 46 ( 1999), pp. 924 - 942] and a delayed list scheduling algorithm by Chekuri et al. [SIAM J. Comput., 31 ( 2001), pp. 146 - 166], we derive the first constant-factor approximation algorithms for this model.

关键词： approximation algorithms stochastic scheduling parallel machines precedence constraints release dates list scheduling algorithms LP-relaxation

来源：评论

学校读者我要写书评

暂无评论

scheduling unitary task systems with zero-one communication delays for quasi-interval orders

引用

DISCRETE APPLIED MATHEMATICS 2003年第3期127卷 461-476页

作者： Moukrim, A Univ Technol Compiegne UMR CNRS 6599 HeuDiaSyC Ctr Rech RoyallieuBP20529 F-60205 Compiegne France

The class of quasi-interval orders contains properly two rich families of precedence graphs: interval orders and a subclass of series-parallel orders. In this paper, we consider the problem of scheduling unitary task systems with zero-one communication delays in order to minimize the total elapsed time for the execution of all the tasks. This problem is known to be NP-complete on an unlimited number of processors even for interval orders. When the precedence constraints are given by a quasi-interval order G and the communication delays are locally identical (which includes the UET-UCT case), we show that an optimal static scheduling can be determined in O(n log n + e) time where n denotes the number of tasks and e denotes the number of the precedence constraints in the transitive closure of G. Some extensions are discussed for nonquasi-interval orders. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： scheduling with communication delays list scheduling algorithms interval orders series-parallel orders quasi-interval orders

来源：评论

学校读者我要写书评

暂无评论

A duplication heuristic for static scheduling of tasks on distributed memory multiprocessors

引用

JOURNAL OF THE CHINESE INSTITUTE OF ENGINEERS 1995年第6期18卷 845-855页

作者： Chung, YC Liu, CC Liu, JS Department of Information Engineering Feng Chia University Taichung 407 Taiwan

A task duplication heuristic, DSH, was proposed in [11]. The underlying concept of the task duplication heuristic is duplicating some tasks on processors such that the earliest start time of tasks on processors can be reduced, that is, tasks on processors can be executed sooner. This leads to a better scheduling length. In this paper, we propose a more general task duplication heuristic,bottom-up top-down duplication heuristic (BTDH), for static scheduling of directed-acyclic graphs (DAGs) on distributed memory multiprocessors. The key difference between BTDH and DSH is the method used for duplicating tasks. BTDH allows tasks to be duplicated on processors even though the duplication of tasks will temporarily increase the earliest start time of some tasks. DSH only allows those duplications which will reduce the earliest start time of tasks. Simulation results show that, for coarse-grain DAGs, the scheduling length of BTDH is almost the same as the scheduling length of DSH. However, for medium-grain and fine-grain DAGs, BTDH produces better scheduling length than DSH.

关键词： distributed memory multiprocessors scheduling length grain size list scheduling algorithms task duplication

来源：评论

学校读者我要写书评

暂无评论

Optimal scheduling on parallel machines for a new order class

引用

OPERATIONS RESEARCH LETTERS 1999年第1-2期24卷 91-95页

作者： Moukrim, A Univ Clermont Ferrand 2 LIMOS F-63177 Clermont Ferrand France

This paper addresses the problem of scheduling n unit length tasks on in identical machines under certain precedence constraints. The aim is to compute minimal length nonpreemptive schedules. We introduce a new order class which contains properly two rich families of precedence graphs: interval orders and a subclass of the class of series parallel orders. We present a linear time algorithm to find an optimal schedule for this new order class on any number of machines. (C) 1999 Published by Elsevier Science B.V. All rights reserved.

关键词： nonpreemptive scheduling parallel machines list scheduling algorithms interval orders series-parallel orders

来源：评论

学校读者我要写书评

暂无评论

scheduling DEPENDENT TASKS ON IDENTICAL MACHINES USING A NOVEL HEURISTIC CRITERION - A ROBOTIC COMPUTATION EXAMPLE

引用

JOURNAL OF INTELLIGENT & ROBOTIC SYSTEMS 1995年第3期12卷 229-237页

作者： TZAFESTAS, S TRIANTAFYLLAKIS, A RIZOS, G Intelligent Robotics and Control Unit Department of Electrical and Computer Engineering National Technical University of Athens Zografou Greece

The problem of scheduling n dependent tasks, with arbitrary processing times, on m identical machines so as to minimize the makespan criterion is considered. Since this problem is NP-hard in the strong sense, it can be solved only suboptimally using heuristic approaches. Two new heuristic algorithms (dispatching rules), namely MVT/MISF acid DMVT/MISF algorithms, for this problem are proposed. These algorithms are then used, together with the existing ones CP/MISF and DHLF/MISF, as a dispatching rule base of a new adaptively weighted combinatorial dispatching (AWCD) rule. This combinatorial dispatching rule has a superior behaviour compared to simple dispatching rules. Extended experimentation with these algorithms supports this argument. Here a representative robotic dynamics computation example is included. In addition, some empirical rules are derived and proposed for the selection of a simple dispatching rule (heuristic) if such a selection is required, for each particular input data set. These methods, as well as the existing optimal algorithms for special solvable cases of the considered problem, have been integrated in a decision support system (DSS).

关键词： scheduling PROBLEMS DISPATCHING RULES HEURISTIC algorithms DEPENDENT TASKS MAKESPAN CRITERION list scheduling algorithms

来源：评论

学校读者我要写书评

暂无评论

Analysis of Process scheduling Algorithm for Multiprocessor System 7

Analysis of Process Scheduling Algorithm for Multiprocessor ...

引用

7th International Conference on Reliability, Infocom Technologies and Optimization - Trends and Future Directions (ICRITO)

作者： Suman, Chandresh Kumar, Gaurav RTU Univ Coll Engn Dept Comp Sci & Engn Kota India

ISBN: (纸本)9781538646922

The scheduling of tasks in heterogeneous and homogeneous multiprocessor environment has been a topic of interest for the scholars and researcher for a long time. list task scheduling helps to develop various scientific appliances. It is NP-complete problem finding an optimal solution;hence it pairs low complexity with better results. The goal of scheduling task is the minimization of the total computation time. For multiple processor environments, list task scheduling is depicted using Directed Acyclic Graph (DAG) and described in both dynamic and static scheduling algorithms. In this literature review, we have discussed various algorithms to schedule the tasks which are a kind of static task scheduling algorithm for both homogeneous multiprocessor scheduling and heterogeneous multiprocessor scheduling environment. The comparative study of scheduling algorithm is based on the performance matrices termed as efficiency, scheduling length, load balancing, and Speedup.

关键词： list scheduling algorithms DAG Homogeneous multiprocessor scheduling Heterogeneous multiprocessor scheduling

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：