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

IMPROVED TASK-ALLOCATION ALGORITHMS TO MAXIMIZE RELIABILITY OF REDUNDANT distributed computing systemS

IEEE TRANSACTIONS ON RELIABILITY 1995年第4期44卷 575-586页

作者： KARTIK, S MURTHY, CSR INDIAN INST TECHNOL DEPT COMP SCI & ENGN MADRAS 600036 TAMIL NADU INDIA

This paper considers the problem of finding an optimal & sub-optimal task-allocation (assign the processing node for each module of a task or program) in redundant distributed computing systems, with the goal of maximizing system-reliability (probability that the system completes the entire task successfully). Finding an optimal task-allocation is NP-hard in the strong sense. An efficient algorithm is presented for optimal task-allocation in a distributed computing system with level-2 redundancy. The algorithm, a) uses branch & bound with underestimates for reducing the average time complexity of optimal task-allocation computations, and b) reorders the list of modules to allow a subset of modules that does not intra-communicate to be assigned last, for further reduction in the computations of optimal task-allocation for maximizing reliability. An efficient heuristic algorithm is given which obtains sub-optimal solutions in a reasonable computation time. The performance of our algorithms is given over a wide range of parameters such as: number of modules, number of processing nodes, ratio of average execution cost to average communication cost, and connectivity of modules. The effectiveness of the optimal task-allocation algorithm is demonstrated by comparing it to a recent competing optimal task-allocation algorithm, for maximizing reliability. The performance of our algorithm improves very much when the difference between the number of modules and the connectivity increases. Our heuristic algorithm produced optimal solutions in 24% of the cases and found allocations within 1.5 times the optimal in about 86% of the cases.1

关键词： TASK ALLOCATION distributed computing system system RELIABILITY OPTIMALITY SEARCH TREE HEURISTIC

来源：评论

学校读者我要写书评

暂无评论

STATIC TASK ALLOCATION OF CONCURRENT PROGRAMS FOR distributed computing systemS WITH PROCESSOR AND RESOURCE HETEROGENEITY

引用

PARALLEL computing 1994年第6期20卷 835-851页

作者： SELVAKUMAR, S MURTHY, CSR INDIAN INST TECHNOL DEPT COMP SCI & ENGNMADRAS 600036TAMIL NADUINDIA UNIV MASSACHUSETTS DEPT COMP SCIAMHERSTMA 01003

In this paper, we investigate the problem of static task allocation of concurrent programs for distributed computing systems with processor and resource heterogeneity, i.e. given a set of concurrent communicating modules and a two processor distributed computing system, in which processors may have differing speeds and each processor may have certain resources not available with the other processor (i.e. unique resources), to which processor should each module be assigned so as to minimize the completion time? This task allocation problem is NP-hard and hence, we provide an efficient heuristic algorithm for obtaining satisfactory suboptimal solution to it in a reasonable amount of computation time and demonstrate the effectiveness of our algorithm with simulation studies. Our algorithm works by constructing an augmented task graph and taking a load balanced mincut on it and has a time complexity of O((m + u)2) where m is the number of concurrent communicating modules and u is the total number of unique resources in the two processor system. Finally, we extend our heuristic algorithm to solve the problem of static task allocation of concurrent programs to an n processor distributed computing system with processor and resource heterogeneity.

关键词： distributed computing system TASK GRAPH TASK ALLOCATION RESOURCE ALLOCATION HEURISTICS

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT TASK MIGRATION ALGORITHM FOR distributed systemS

引用

IEEE TRANSACTIONS ON PARALLEL AND distributed systemS 1992年第4期3卷 488-499页

作者： SUEN, TTY WONG, JSK Department of Computer Science Iowa State University Ames IA USA

It is desirable for the workload in a distributed computing system to be evenly distributed. The objective of this paper is to achieve balanced load among the processors and to reduce the communication overhead of the load balancing algorithm. By balancing the load among processors, resource utilization can be improved and, in general, result in better average response time. A communication protocol and a fully distributed algorithm for dynamic load balancing through task migration in a connected N-processor network are proposed. Each processor communicates its load directly with only a subset (of size square-root N) of processors, reducing communication traffic and average response time. We prove that the given algorithm will perform task migration even if there is only one light load processor and one heavy load processor in the system. Simulation results show that the proposed scheme can save up to 60% of the protocol messages used by the broadcast algorithms and can reduce the average response time.

关键词： COMMUNICATION PROTOCOL COMPUTER NETWORK distributed ALGORITHM distributed computing system DYNAMIC LOAD BALANCING TASK MIGRATION

来源：评论

学校读者我要写书评

暂无评论

ON THE NUMBER OF ACCEPTABLE TASK ASSIGNMENTS IN distributed computing systemS

引用

IEEE TRANSACTIONS ON COMPUTERS 1990年第1期39卷 99-110页

作者： SHIN, KG CHEN, MS IBM CORP THOMAS J WATSON RES CTRYORKTOWN HTSNY 10598

A distributed computing system and cooperating tasks can be represented by a processor graph Gp=(Vp, Ep) and a task graph GT=(VT, E T), respectively. An edge between a pair of nodes in GT represents the existence of direct communications between the two corresponding tasks. The maximal number of hops between two processors in Gp to which two adjacent tasks in GT are assigned is called dilation of that assignment. Characterization and use of the number of acceptable assignments for given GT and GP are treated. Assignments with the dilation less than or equal to one are considered. This dilation constraint represents a special case in which two adjacent tasks in GT must be assigned to either a single processor or two adjacent processors in Gp. For the case where N(GT, GP ) denotes the numbers of acceptable assignments under this constraint, N(GT, GP) are derived for arbitrary GT and GP , and a recursive expression is formulated for N(G T, GP) when GT is a tree. For some restricted cases, either closed-form or recursive-form expressions of N(GT, G P) are derived. The results on N(GT, GP) are extended to the completely general case, assignments with dilations greater than one, where two adjacent tasks in GT can be assigned to any two processors in GP which are not necessarily adjacent to each other

关键词： Hypertrophy Humulus distributed computing system direct communication Uniprocessor Neighbor Dilatation Less than or equal to PROCESSOR Religious Missions

来源：评论

学校读者我要写书评

暂无评论

AN ARCHITECTURE FOR REAL-TIME MULTIMEDIA COMMUNICATION-systemS

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 1990年第3期8卷 391-400页

作者： NICOLAOU, C Computer Laboratory University of Cambridge Cambridge UK

A multimedia communication system includes both the communication protocols used to transport the real-time data and the distributed computing system (DCS) within which any applications using the protocols must execute. The architecture presented attempts to integrate these communications protocols with the DCS in a smooth fashion in order to ease the writing of multimedia applications. Two issues are identified as being essential to the success of this integration: the synchronization of related real-time data streams, and the management of heterogeneous multimedia hardware. The synchronization problem is tackled by defining explicit synchronization properties at the presentation level and by providing control and synchronization operations within the DCS which operate in terms of these properties. The heterogeneity problems are addressed by separating the data transport semantics (protocols themselves) from the control semantics (protocol interfaces).

关键词： direct current ARCHITECTURE Communication protocols semiotics Semantics Building construction data transmission distributed computing system real-time data

来源：评论

学校读者我要写书评

暂无评论

EFFECTS OF RESPONSE AND STABILITY ON SCHEDULING IN distributed computing systemS

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 1988年第11期14卷 1578-1588页

作者： CASAVANT, TL KUHL, JG UNIV IOWA DEPT ELECT & COMP ENGNIOWA CITYIA 52242

An examination is made of the effects of response and stability on scheduling algorithms for general-purpose distributed computing systems. Response characterizes the time required, following a perturbation in the system state, to reach a new equilibrium state. Stability is a measure of the ability of a mechanism to detect when the effects of further actions will not improve the system state as defined by a user-defined objective. These results have implications for distributed computations in general. Analysis is based on formal communicating finite automata models of two distinct approaches to the scheduling problem, each using the objective of global optimal load balancing. The results indicate that absolute stability is not always necessary in dynamic systems for the same reasons that relatively small amounts of instability are tolerated in the design of analog control systems. It is shown that response is a very important first-order metric of dynamic scheduling behavior, and that response and stability are related.

关键词： Load balancing analog controls Scheduling algorithms Dynamic systems absolute stability distributed computing system perturbation

来源：评论

学校读者我要写书评

暂无评论

FAST BRIDGE FOR EFFICIENT LAN-LAN COUPLING

引用

IEE PROCEEDINGS-E COMPUTERS AND DIGITAL TECHNIQUES 1988年第5期135卷 273-277页

作者： SANTANA, MJ SANTANA, RHC ZALUSKA, EJ Department of Electronics and Computer Science University of Southampton Southampton UK

Describes the design of a fast bridge between two Cambridge ring local area networks. The main requirements are high speed, a flexible addressing range and high reliability. The bridge implemented is in day to day use as part of TRICE, the distributed computing system implemented at the Department of Electronics and Computer Science at Southampton University. The performance and reliability obtained in service are discussed.

关键词： Fasting Electronics computer science distributed computing system Local Area Networks

来源：评论

学校读者我要写书评

暂无评论

EVALUATING RESPONSE-TIME IN A FAULTY distributed computing system

引用

IEEE TRANSACTIONS ON COMPUTERS 1985年第2期34卷 101-109页

作者： GARCIAMOLINA, H KENT, J Department of Electrical Engineering and Computer Science Princeton University

This paper presents an evaluation technique which is useful for studying both the performance and the reliability of a distributed computing system. The distributed system is evaluated the point of view of a user who submits a request for service. Our technique computes the average time to successful completion of this request, taking into account the system failures or repairs which may occur before the request is completed. Given a model of the system and its failures, the performance-reliability measures are computed in an automatic numerical fashion. The technique is computationally intensive, so it is limited to relatively small systems. However, it can produce results for many interesting cases without an inordinate amount of computation.

关键词： distributed computing system failure models graceful degradation performance evaluation reliability evaluation response time

来源：评论

学校读者我要写书评

暂无评论

ON THE DESIGN OF A distributed OPERATING system USING A HIGH-LEVEL distributed-PROGRAMMING LANGUAGE

MICROPROCESSING AND MICROPROGRAMMING

引用

MICROPROCESSING AND MICROPROGRAMMING 1982年第4期10卷 247-254页

作者： ARORA, RK SHARMA, NK Computer Centre Indian Institute of Technology Delhi Hauz Khas New Delhi 110016 India

A methodology to design a distributed operating system is presented. The advantage of using a high-level distributed programming language as a design, documentation, and implementation tool is illustrated.

关键词： distributed computing system distributed operating system distributed programming language

来源：评论

学校读者我要写书评

暂无评论

Language Structures and Management Method in a distributed Real-Time Environment

引用

IFAC Proceedings Volumes 1981年第1期14卷 103-113页

作者： M. Tsukamoto Electrotechnical Laboratory Tsukuba Ibaraki 305 Japan

Recent advances in hardware technology have made it economically feasible to construct micro computer controlled subsystems and to connect them to distributed real-time control systems. However it is difficult to integrate and develop the potential of subsystems without understanding or changing the existing systems. In this paper, we will introduce a new language concept and a management method to overcome the difficulties. Firstly, a concurrent programming concept, the guarding process (GP), is introduced. In the concept a program consists only of modules, each of which defines objects and servers. Using the concept, programs are described in a structured manner allowing the modules to detect incorrect sequences of interactions. Secondly, a management method that guarantees timing and response to modules, the deadline monitor (DM), is introduced. Servers may be specified with requirements of timing and response. DM fills these requirements and monitors servers' behavior. Finally, in order to deal with the exceptions raised by GP and DM, the exception handler is introduced. In the testing phase, GP reports to the handler why the algorithm is wrong nd how to use the module. The concepts are presented in a programming language and augmented by the implementation of a distributed robot system.

关键词： distributed computing system distributed computer control concurrent programming distributed programming modular programming path expression error detection exception handling critical real-time deadline mechanism performance monitor robot

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：