parallel high-performance computing is gaining momentum as a computing platform for many applications. In recent years, the research in software support for parallel computers has mainly addressed scientific and infor...
详细信息
The delivery delay in a point-to-point packet switching network is difficult to control due to the contention among randomly-arriving packets at each node and multihops a packet must travel between its source and dest...
详细信息
The delivery delay in a point-to-point packet switching network is difficult to control due to the contention among randomly-arriving packets at each node and multihops a packet must travel between its source and destination. Despite this difficulty, there are an increasing number of applications that require packets to be delivered reliably within prespecified delay bounds. This paper shows how this can be achieved by using real-time channels which make "soft" reservation of network resources to ensure the timely delivery of real-time packets. We first present theoretical results and detailed procedures for the establishment of real-time channels and then show how the basic real-time channels can be enhanced to be fault-tolerant using the multiple disjoint paths between a pair of communicating nodes. The contribution of the former is a tighter schedulability condition which makes more efficient use of network resources than any other existing approaches, and that of the latter is a significant improvement in fault tolerance over the basic real-time channel, which is inherently susceptible to component failures.
We rigorously analyze load sharing (LS) in a distributedreal-time system, called HARTS (Hexagonal Architecture for real-timesystems), while considering LS-related communication activities, such as task transfers and...
详细信息
We rigorously analyze load sharing (LS) in a distributedreal-time system, called HARTS (Hexagonal Architecture for real-timesystems), while considering LS-related communication activities, such as task transfers and state-change broadcasts. First, we give an overview of the general distributedreal-time LS approach described in [1], [2], and then adapt it to HARTS by exploiting the topological properties of HARTS. Second, we model task arrival/completion/transfer activities in HARTS as a continuous-time Markov chain from which we derive the distribution of queue length and the rate of generating LS-related traffic-task transfer-out rate and state-region change broadcast rate. Third, we derive the distribution of packet delivery time as a function of LS-related traffic rates by characterizing the hexagonal mesh topology and the virtual cut-through capability of HARTS. Finally, we derive the distribution of task waiting time (the time a task is queued for execution plus the time it would spend if the task is to be transferred), from which the probability of a task failing to complete in time, called the probability of dynamic failure, can be computed. The results obtained from our analytic models are verified through event-driven simulations, and can be used to study the effects of varying various design parameters on the performance of LS while considering the details of LS-related communication activities.
We propose FIT, a flexible, lightweight, and real-time scheduling system for wireless sensor platforms. There are three salient features of FIT. First, its two-tier hierarchical framework supports customizable applica...
详细信息
We propose FIT, a flexible, lightweight, and real-time scheduling system for wireless sensor platforms. There are three salient features of FIT. First, its two-tier hierarchical framework supports customizable application-specific scheduling policies, hence, FIT is very flexible. Second, FIT is lightweight in terms of minimizing the thread number to reduce preemptions and memory consumption while at the same time ensuring system schedulability. We propose a novel Minimum Thread Scheduling Policy ( MTSP) exploration algorithm within FIT to achieve this goal. Finally, FIT provides a detailed real-time schedulability analysis method to help check if application's temporal requirements can be met. We implemented FIT on MicaZ motes and carried out extensive evaluations. Results demonstrate that FIT is indeed flexible and lightweight for implementing real-time applications, at the same time, the schedulability analysis provided can predict the real-time behavior. FIT is a promising scheduling system for implementing complex real-time applications in sensor networks.
Scientific workflows are a topic of great interest in the Grid community that sees in the workflow model an attractive paradigm for programming distributed wide-area Grid infrastructures. Traditionally, the Grid workf...
详细信息
Scientific workflows are a topic of great interest in the Grid community that sees in the workflow model an attractive paradigm for programming distributed wide-area Grid infrastructures. Traditionally, the Grid workflow execution is approached as a pure best effort scheduling problem that maps the activities onto the Grid processors based on appropriate optimization or local matchmaking heuristics such that the overall execution time is minimized. Even though such heuristics often deliver effective results, the execution in dynamic and unpredictable Grid environments is prone to severe performance losses that must be understood for minimizing the completion time or for the efficient use of high-performance resources. In this paper, we propose a new systematic approach to help the scientists and middleware developers understand the most severe sources of performance losses that occur when executing scientific workflows in dynamic Grid environments. We introduce an ideal model for the lowest execution time that can be achieved by a workflow and explain the difference to the real measured Grid execution time based on a hierarchy of performance overheads for Grid computing. We describe how to systematically measure and compute the overheads from individual activities to larger workflow regions and adjust well-known parallel processing metrics to the scope of Grid computing, including speedup and efficiency. We present a distributed online tool for computing and analyzing the performance overheads in realtime based on event correlation techniques and introduce several performance contracts as quality-of-service parameters to be enforced during the workflow execution beyond traditional best effort practices. We illustrate our method through postmortem and online performance analysis of two real-world workflow applications executed in the Austrian Grid environment.
This paper presents a new language that integrates the real-time and distributed paradigms within the framework of a concurrent logic language. Concurrent logic languages (CLLs) are capable of expressing concurrence, ...
详细信息
This paper presents a new language that integrates the real-time and distributed paradigms within the framework of a concurrent logic language. Concurrent logic languages (CLLs) are capable of expressing concurrence, communication and nondeterminism in a natural way. That is, the intrinsic parallel semantics of the concurrent logic languages makes them well-suited for distributed programming. The proposed language is particularly suitable for loosely coupled systems and it contains mechanisms for distributed and real-time process control. A new execution model for concurrent logic languages is presented, which enables efficient distributed execution and real-time control. The model is introduced by giving an operational semantics for the language and the new model's implementation is discussed, including the definition of a new abstract machine and its implementation on a network of Unix workstations. Although the sequential core is not optimized, some previous results are discussed, showing the feasibility of the language's execution model for distributedreal-timesystems. The language is currently being used as the kernel language for a distributed simulation and validation tool for communication protocols. (C) 1997 Elsevier Science Ltd. All rights reserved.
Of critical importance to any real-time system is the issue of predictability. We divide overall system predictability into two parts: algorithmic and systemic. Algorithmic predictability is concerned with ensuring th...
ISBN:
(纸本)0769516084
Of critical importance to any real-time system is the issue of predictability. We divide overall system predictability into two parts: algorithmic and systemic. Algorithmic predictability is concerned with ensuring that the parallel simulation engine and model from a complexity point of view are able to consistently yield results within a real-time deadline. Systemic predictability is concerned with ensuring that OS scheduling, interrupts and virtual memory overheads are consistent over a real-time period. To provide a framework for investigating systemic predictability, we define a new class of parallel simulation called Extreme Simulation or XSim. An XSim is any analytic parallel simulation that is able to generate a statistically valid result by a real-time deadline. Typically, this deadline is between 10 and 100 milliseconds. XSims are expected to provide decision support to existing complex, realtimesystems. As a new design and implementation methodology for realizing XSims, we embed a state-of-the-art optimistic simulator into the Linux operating system. In this operating environment, OS scheduling and interrupts are disabled. Given a 50 millisecond model completion deadline, we observe that the XSim has a systemic predictability, measure of 98% compared with only 56% for the same time Warp system operating in user-level.
A candidate network function is accurately defined for real-timeparallel computers. A concise, time-driven, flit-based, priority-driven, wormhole-routed, network simulator has been designed. Experimentation is perfor...
详细信息
We present several efficient online and offline strategies for assigning periodic tasks to the nodes of a distributed system, such that the tasks can be feasibly scheduled by the node using some local static/dynamic p...
详细信息
作者：
GOSCINSKI, ADepartment of Computer Science
University College The University of New South Wales Australian Defence Force Academy Canberra Australian Capital Territory Australia
Two algorithms developed utilizing a priority-based event-ordering which manage mutual exclusion in distributedsystems—computer networks—are proposed. In these systems, processes communicate only by messages and do...
详细信息
Two algorithms developed utilizing a priority-based event-ordering which manage mutual exclusion in distributedsystems—computer networks—are proposed. In these systems, processes communicate only by messages and do not share memory. The computer network functions either (a) in an environment requiring priorities or (b) in a real-time environment. The algorithms are based on broadcast requests and token passing service approach, but the token need not be passed if no process wishes to enter the critical section. These algorithms are fully distributed and are insensitive to the relative speeds of node computers and communication links. They use only N messages per critical section, where N is the number of nodes (processes). The algorithms are optimal in the sense that a symmetrical, distributed algorithm cannot use fewer messages if requests are processed by each node computer concurrently. Both algorithms ensure freedom from starvation. There are mechanisms to handle node insertion and removal, node failure, the loss of the token, the existence of more than one token, and delivery of messages out of order.
暂无评论