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

A fast algorithm for the minimax flow problem with 0/1 weights

APPLIED MATHEMATICS LETTERS 1997年第1期10卷 11-16页

作者： Han, CC Real-Time Computing Laboratory Department of Electrical Engineering and Computer Science The University of Michigan Ann Arbor MI 48109-2122 U.S.A.

In this paper, we define the minimax flow problem and design an O(k . M(n, m)) time optimal algorithm for a special case of the problem in which the weights on arcs are either O or 1, where n is the number of vertices, m is the number of arcs, k (where 1 less than or equal to k less than or equal to m) is the number of arcs with nonzero weights, and M(n;m) is the best time bound for finding a maximum flow in a network.

关键词： design and analysis of algorithms f-saturated critical arcs maximum flow minimax flow residual network

来源：评论

学校读者我要写书评

暂无评论

QoS negotiation in real-time systems and its application to automated flight control

QoS negotiation in real-time systems and its application to ...

引用

3rd IEEE real-time Technology and Applications Symposium

作者： Abdelzaher, TF Atkins, EM Shin, KG Real- Time Computing Laboratory Department of Electrical Engineering and Computer Science University of Michigan Ann Arbor MI 48109-2122 United States

ISBN: (纸本)0818680164

We propose a model for quality-of-service (QoS) negotiation in building real-time services to meet both predictability and graceful degradation requirements. QoS negotiation is shown to (i) outperform conventional ''binary'' admission control schemes (either guaranteeing the required QoS or rejecting the service request), and (ii) achieve higher application-perceived system utility. We incorporated the proposed QoS-negotiation model into an example realtime middleware service, called RTPOOL, which manages a distributed pool of shared computing resources (processors) to guarantee timeliness QoS for real-time applications. The efficacy and power of QoS negotiation are demonstrated for an automated flight control system implemented on a network of PCs running RTPOOL. This system is used to fly an F-16 fighter aircraft modeled using the Aerial Combat (ACM) F-16 Flight Simulator. Experimental results indicate that QoS negotiation, while maintaining real-time guarantees, enables graceful QoS degradation under conditions in which traditional schedulability analysis and admission control schemes fail.

关键词： real time systems

来源：评论

学校读者我要写书评

暂无评论

An efficient semaphore implementation scheme for small-memory embedded systems

An efficient semaphore implementation scheme for small-memor...

引用

3rd IEEE real-time Technology and Applications Symposium

作者： Zuberi, KM Shin, KG Real-Time Computing Laboratory Department of Electrical Engineering and Computer Science University of Michigan Ann Arbor MI 48109-2122 United States

ISBN: (纸本)0818680164

In object-oriented programming, updates to the state variables of objects (by the methods of the object) have to be protected through semaphores to ensure mutual exclusion. Semaphore operations are invoked each time an, object is accessed, and this represents significant run-time overhead. This a's of special concern in cost-conscious, small-size embedded systems such as those used in automotive applications - where costs must be kept to an absolute minimum. Object-oriented programming can be feasible an such applications only if the OS provides efficient, lour-overhead semaphores. We present a new semaphore implementation scheme which saves one context switch per semaphore lod operation in most circumstances and gives performance improvements of 18-25% over traditional semaphore implementation schemes.

关键词： Object oriented programming

来源：评论

学校读者我要写书评

暂无评论

Comment on a pre-run-time scheduling algorithm for hard real-time systems

引用

IEEE Transactions on Software Engineering 1997年第9期23卷 599-600页

作者： Abdelzaher, Tarek F. Shin, Kang G. Real-Time Computing Laboratory Department of Electrical Engineering and Computer Science University of Michigan Ann Arbor MI 48109 United States

In Shepard and Gagne [1], a branch-and-bound implicit enumeration algorithm is described whose purpose is to generate a feasible schedule, if any, for each processor on a multiprocessing node running hard real-time processes. The optimization criterion is to minimize process lateness defined as the difference between the process completion time and deadline. We show in this correspondence that this algorithm does not always succeed in finding a feasible solution, and describe the reason why the algorithm might fail. © 1997 IEEE.

关键词： Branch and bound scheduling algorithm Hard real-time systems Multiprocessors Pre-run-time scheduling Precedence constraints

来源：评论

学校读者我要写书评

暂无评论

Experimental evaluation of failure-detection schemes in real-time communication networks 27

Experimental evaluation of failure-detection schemes in real...

引用

27th Annual International Symposium on Fault-Tolerant computing, FTCS 1997

作者： Han, Seungjae Shin, Kang G. Real-Time Computing Laboratory Department of Electrical Engineering and Computer Science University of Michigan Ann ArborMI48109-2122 United States

ISBN: (纸本)0818678313

An effective failure-detection scheme is essential for reliable communication services. Most computer network rely on behavior-based detection schemes: each node uses heartbeats to detect the failure of its neighbor nodes, and the transport protocol (like TCP) achieves reliable communication by acknowledgment/retransmission. In this paper, we experimentally evaluate the effectiveness of such behavior-based detection schemes in real-time communication. Specifically, we measure and analyze the coverage and latency of two failure-detection schemes-neighbor detection and end-to-end detection-through fault-injection experiments. The experimental results have shown that a significant portion of failures can be detected very quickly by the neighbor detection scheme, while the end-to-end detection scheme uncovers the remaining failures with larger detection latencies. © 1997 IEEE.

关键词：

来源：评论

学校读者我要写书评

暂无评论

A language support environment for complex distributed real-time applications 3

A language support environment for complex distributed real-...

引用

3rd IEEE International Conference on Engineering of Complex computer Systems (ICECCS 97)

作者： Stoyen, AD Marlowe, TJ Younis, M Petrov, P Real- Time Computing Laboratory Department of Computer and Information Science New Jersey Institute of Technology Newark 07102 NJ United States Department of Mathematics and Computer Science Seton Hall University South Orange 07079 NJ United States AlliedSignal Aerospace Microelectronics and Technology Center 9140 Old Annapolis Road/MD 108 Columbia 21045 MD United States

ISBN: (纸本)0818681268

Engineering of complex distributed real-time applications is one of the hardest tasks faced by the software profession today. All aspects of the process, from design to implementation, are made more difficult by the interaction of behavioral and platform constraints. Providing tools for this task is likewise not without major challenges. In this paper, we discuss a tool suite at New Jersey Institute of Technology's real-time computing Lab which supports the development of complex distributed real-time applications in a suitable high-level language (CRL). The suite's component tools include a compiler, a transformer-optimizer, an allocator-migrator, schedulability analyzers, a debugger-monitor, a kernel and a (simulated) network manager. The overall engineering approach supported by the suite is to provide as simple and natural an integrated development paradigm as possible. The suite tools address complexity due to distribution, scheduling, allocation and other sources in an integrated manner (largely) transparent to the developer. To reflect the needs of propagation of functional and non-functional requirements throughout the development process, a number of robust code transformation and communication mechanisms have been incorporated into the suite. To facilitate practical use of the suite, the developed programs compile-transform to a safe subset of C++ with appropriate libraries and runtime support.

关键词： Cosine transforms

来源：评论

学校读者我要写书评

暂无评论

COMPASS: A comprehensible assertion method 7th

引用

7th International Joint Conference on Theory and Practice of Software Development, TAPSOFT 1997

作者： Bonnier, Staffan Heyer, Tim Stora Badhusgatan 18-20 GÖteborgzS-411 21 Sweden Real-Time Systems Laboratory Department of Computer and Information Science LinkÖping University LinkÖpingS-581 83 Sweden

ISBN: (纸本)9783540627814

We present an approach for automatically generating relevant, focused questions to be asked during code inspection sessions. The method is based on Hoare-logic. The novel key idea is the introduction of informal predicates, which, though not having a formal definition, may have a perfectly legal and unique informal interpretation. Such predicates make it easier to express requirements in terms of assertions, while still allowing for the automatic derivation of verification conditions. Moreover, informal predicates enable reasoning about assertions and verifying verification conditions at a level which is suitable for man rather than machine. © Springer-Verlag Berlin Heidelberg 1997.

关键词： Artificial intelligence

来源：评论

学校读者我要写书评

暂无评论

Exact and efficient analysis of schedulability in fixed-packet networks: a generic approach

Exact and efficient analysis of schedulability in fixed-pack...

引用

IEEE Annual Joint Conference: INFOCOM, IEEE computer and Communications Societies

作者： S. Gorinsky S. Baruah T.J. Marlowe A.D. Stoyenko Real Time Computing Laboratory Department of Computer and Information Science New Jersey Institute of Technology Newark NJ USA Department of Computer Science and Electrical Engineering University of Vermont Burlington VT USA Department of Mathematics and Computer Science Seton Hall University South Orange NJ USA Real Time Computing Laboratory Department of Computer and Information Science New Jersey Institute of Technology Newark NJ USA

A general model for traffic flows on packet-switched, virtual-circuit based, fixed-packet networks is introduced, and an exact schedulability test is obtained for systems of such flows. Rules are derived that make the evaluation of this schedulability test feasible and efficient under certain circumstances. The practical relevance of this approach is demonstrated by applying it to a number of standard traffic models.

关键词： Intelligent networks Processor scheduling Telecommunication traffic Traffic control computer networks Delay Laboratories information science computer science real time systems

来源：评论

学校读者我要写书评

暂无评论

Fast restoration of real-time communication service from component failures in multi-hop networks 97

Fast restoration of real-time communication service from com...

引用

Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication

作者： Seungjae Han Kang G. Shin Real-Time Computing Laboratory Department of Electrical Engineering and Computer Science The University of Michigan Ann Arbor Michigan

ISBN: (纸本)9780897919050

For many applications it is important to provide communication services with guaranteed timeliness and fault-tolerance at an acceptable level of overhead. In this paper, we present a scheme for restoring real-time channels, each with guaranteed timeliness, from component failures in multi-hop networks. To ensure fast/guaranteed recovery, backup channels are set up a priori in addition to each primary channel. That is, a dependable real-time connection consists of a primary channel and one or more backup channels. If a primary channel fails, one of its backup channels is activated to become a new primary channel. We describe a protocol which provides an integrated solution to the failure-recovery problem (i.e., channel switching, resource re-allocation, ...). We also present a resource sharing method that significantly reduces the overhead of backup channels. The simulation results show that good coverage (in recovering from failures) can be achieved with about 30% degradation in network utilization under a reasonable failure condition. Moreover, the fault-tolerance level of each dependable connection can be controlled, independently of other connections, to reflect its criticality.

关键词：

来源：评论

学校读者我要写书评

暂无评论

An efficient semaphore implementation scheme for small-memory embedded systems

An efficient semaphore implementation scheme for small-memor...

引用

real-time Technology and Applications Symposium

作者： K.M. Zuberi K.G. Shin Real Time Computing Laboratory Department of Electrical Engineering and Computer Science University of Michigan Ann Arbor MI USA

In object-oriented programming, updates to the state variables of objects (by the methods of the object) have to be protected through semaphores to ensure mutual exclusion. Semaphore operations are invoked each time an object is accessed, and this represents significant run-time overhead. This is of special concern in cost-conscious, small-size embedded systems-such as those used in automotive applications-where costs must be kept to an absolute minimum. Object-oriented programming can be feasible in such applications only if the OS provides efficient, low-overhead semaphores. The authors present a new semaphore implementation scheme which saves one context switch per semaphore lock operation in most circumstances and gives performance improvements of 18-25% over traditional semaphore implementation schemes.

关键词： Embedded system Costs real time systems Object oriented programming Automotive applications Switches Microcontrollers Yarn Embedded computing Laboratories

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：