Using two branch-and-bound (B&B) algorithms, an optimal solution is proposed to the problem of allocating (or assigning with the subsequent scheduling considered) periodic tasks to a set of heterogeneous processin...
详细信息
Using two branch-and-bound (B&B) algorithms, an optimal solution is proposed to the problem of allocating (or assigning with the subsequent scheduling considered) periodic tasks to a set of heterogeneous processing nodes (PNs) of a distributed real-time system. The allocation objective is to minimize the maximum normalized task response time, called the system hazard, subject to precedence constraints among the tasks to be allocated. First, the task system is modeled with a task graph, which describes computation and communication modules as well as the precedence constraints among them. Second, the exact system hazard of a complete assignment is determined so that an optimal assignment can be derived. This exact cost is obtained by optimally scheduling the modules assigned to each PN with a B&B algorithm guided by the dominance relationship between simultaneously schedulable modules. Third, to reduce the amount of computation needed for an optimal assignment, a lower-bound system hazard that is obtainable with a polynomial time algorithm is derived.< >
The authors propose a clock distribution scheme that minimizes the difference in the length of clock lines, which is the foremost factor responsible for clock skew in a VLSI circuit. The scheme uses the hierarchy crea...
详细信息
The authors propose a clock distribution scheme that minimizes the difference in the length of clock lines, which is the foremost factor responsible for clock skew in a VLSI circuit. The scheme uses the hierarchy created by the clock buffers to parallelize the distribution of the clock signal. At each hierarchical level, an exhaustive search of paths with intelligent pruning is used to determine the optimal layout of clock lines at that level. Unlike other related work in this area, both delay and skew are taken into account in determining the layout.< >
The design and implementation of a VLSI routing controller for use in the Hexagonal Architecture for Real-time Systems (HARTS), which is currently being built, are presented. The routing controller is a microprogramme...
详细信息
The design and implementation of a VLSI routing controller for use in the Hexagonal Architecture for Real-time Systems (HARTS), which is currently being built, are presented. The routing controller is a microprogrammed unit designed to function as an intelligent front-end interface for the interconnection network. Unlike other routine controllers known to date, this routing controller allows for the flexibility to investigate several low-level routing algorithms by downloading the appropriate microcode into the routing controller. The design was carried out using the combination of Seattle Silicon Technology's silicon compiler and Mentor Graphic's schematic capture and simulation tools. The implementation is targeted for a 64-pin package using a 1.2- mu m CMOS process.< >
The issues involved in providing hardware communication support at each mode in a distributed real-time system are studied. First, a general architecture for each node of the system is described. An algorithm for mess...
详细信息
The issues involved in providing hardware communication support at each mode in a distributed real-time system are studied. First, a general architecture for each node of the system is described. An algorithm for message handling by dedicated hardware called a communication processor (CP) is proposed, to maximize the number of requests handled over the various constraints. A floating CP architecture is proposed, to maximize the number of requests handled under the various constraints. A floating CP architecture is proposed to maximize the utilization of the processors at a node and provide greater fault-tolerance in the system.< >
Allocation and deallocation of subcubes usually result in a fragmented hypercube where even if a sufficient number of hypercube nodes are available, they do not form a subeube large enough to execute an incoming task....
详细信息
Allocation and deallocation of subcubes usually result in a fragmented hypercube where even if a sufficient number of hypercube nodes are available, they do not form a subeube large enough to execute an incoming task. As the fragmentation in conventional memory allocation can be handled by memory compaction, the fragmentation problem in a hypercube can be solved by task migration, i.e., relocating tasks within the hypercubc to remove the fragmentation. The procedure for task migration closely depends on the subcube allocation strategy used, since active tasks must be relocated in such a way that the availability of subcubcs can be detected by that allocation strategy. In this paper, we develop a task migration strategy for the sub cube allocation policy based on the binary reflected Gray code. A goal configuration (of destination subeubes) without fragmentation is determined first. Then, the node-mapping between the source and destination subcubes is derived. Finally, a routing procedure to achieve shortest deadlock-free paths for relocating tasks is developed.
The problem of allocation and release of subcubes from a hypercube with node failures is addressed. Two algorithms are presented, both based on the Buddy allocation scheme for memory management which is also used by t...
详细信息
This paper describes an embedding of Triple Modular Redundancy (TMR) into a binary hypercube. The goal is to improve fault tolerance by masking any single-point faults. Each module of an application task is triplicate...
详细信息
ISBN:
(纸本)0897912780
This paper describes an embedding of Triple Modular Redundancy (TMR) into a binary hypercube. The goal is to improve fault tolerance by masking any single-point faults. Each module of an application task is triplicated and executed in parallel on three nodes of a 2-dimensional subcube (Q2) of the hypercube. Each of these nodes also executes a voter process. The remaining node is used for message passing only. All outputs from the triplicated modules are voted on, and the voting results are transmitted to the appropriate destination. Thus, all interunit messages are also triplicated. We propose an embedding of TMR into a hypercube which can be implemented in a manner transparent to the application program. Subcubes are allocated so that the address space for the TMR units is also a hypercube. Hence, the subcube allocation and intermodule communication schemes are defined to be analogous to the schemes used in the nonre-dundant system. The embedded system is proven to mask all single-point faults.
A connected hypercube containing faulty components (nodes or links) is called an injured hypercube. To enable non-faulty nodes to communicate with each other in an injured hypercube, the information of component failu...
详细信息
ISBN:
(纸本)0897912780
A connected hypercube containing faulty components (nodes or links) is called an injured hypercube. To enable non-faulty nodes to communicate with each other in an injured hypercube, the information of component failures must be made available to those non-faulty nodes for them to route messages around the faulty components. We develop a fault-tolerant routing scheme which requires each node to know only the information on the failure of its own links. Performance of this scheme is rigorously analyzed. This scheme is not only shown to be capable of routing messages successfully in injured hypercubes when the number of component failures is less than n, but also proved to be able to choose a shortest path with a very high probability.
An approach to checkpointing and rollback recovery in a distributed computing system using a common time base is proposed. First, a common time base is established in the system using a hardware clock synchronization ...
详细信息
An approach to checkpointing and rollback recovery in a distributed computing system using a common time base is proposed. First, a common time base is established in the system using a hardware clock synchronization algorithm. This common time base is coupled with a pseudorecovery block approach to develop a checkpointing algorithm that has the following advantages: (i) maximum process autonomy, (ii) no wait for commitment for establishing recovery lines, (iii) fewer messages to be exchanged, and (iv) less memory requirement.< >
It is shown how to determine closed-form expressions for task scheduling delay and active task time distributions for any real-time system application, given a scheduling policy and task execution time distributions. ...
详细信息
It is shown how to determine closed-form expressions for task scheduling delay and active task time distributions for any real-time system application, given a scheduling policy and task execution time distributions. The active task time denotes the total time a task is executing or waiting to be executed, including scheduling delays and resource contention delays. The distributions are used to determine the probability of dynamic failure and processor utilization, where the probability of dynamic failure is the probability that any task will not complete before its deadline. The opposing effects of decreasing the probability of dynamic failure and increasing utilization are also addressed. The analysis first addresses workloads where all tasks are periodic, i.e., they are repetitively triggered at constant frequencies. It is then extended to include the arrival of asynchronously triggered tasks. The effects of asynchronous tasks on the probability of dynamic failure and utilization are addressed.< >
暂无评论