Achieving high system throughput for limited- feedback communications against the time-varying channel effect is rather crucial in modern mobile system designs. Within the beamforming setup, this paper derives analytic throughput results for both the "more feedback less often" and "less feedback more often" scenarios. More specifically, under the assumptions that (i) the channels over two consecutive time slots follow the first-order Markov model and (ii) in each time slot, reliable feedback of a fixed amount of bits is allowed, the achievable system throughput over two consecutive time slots in both scenarios are characterized. In particular, while the exact throughput is in an integral form, we derive the associated closed-form approximate formulae which facilitate throughput evaluation without resorting to numerical integration. The analytic results also lead to a very low-complexity throughput-based mode selection scheme. Simulation study shows that: (1) the derived closed-form approximation is quite accurate; (2) with the aid of the proposed mode selection method, the throughput performance is robust against the channel temporal variation.

The paper addresses two important issues associated with load sharing (LS) in hypercube-connected multicomputers: (1) ordering fault-free nodes as preferred receivers of "overflow" tasks for each overloaded node and (2) developing an LS mechanism to handle node failures. Nodes are arranged into preferred lists of receivers of overflow tasks in such a way that each node will be selected as the kth preferred node of one and only one other node. Such lists are proven to allow the overflow tasks to be evenly distributed throughout the entire system. However, the occurrence of node failures will destroy the original structure of a preferred list if the failed nodes are simply dropped from the list, thus forcing some nodes to be selected as the kth preferred node of more than one other node. The authors propose three algorithms to modify the preferred list such that its original features can be retained regardless of the number of faulty nodes in the system. It is shown that the number of adjustments or the communication overhead of these algorithms is minimal. Using the modified preferred lists, they also proposed a simple mechanism to tolerate node failures. Each node is equipped with a backup queue which stores and updates the information on the tasks arriving/completing at its most preferred node.

In this paper a wavelet based algorithm, its architecture and VLSI implementation for a hierarchical image coding technique is presented. The algorithm is based on a biorthogonal expansion involving a pair of mother wavelets, which are 2D discrete pyramid-shaped versions of the piecewise linear B-spline. The implementation is block oriented and includes a post-processing zerotree coding scheme to obtain further compression. The wavelet transform is computed using a previously designed array of replicated cells. The complementary architecture for the zerotree coding scheme is introduced in this paper.

Uneven task arrivals in a hypercube-connected multicomputer may temporarily overload some nodes while leaving others underloaded. This problem can be solved or alleviated by load sharing (LS); that is, some of the tasks arriving at overloaded nodes, called overflow tasks, are transferred to underloaded nodes. One important issue in LS is to locate underloaded nodes to which the overflow tasks can be transferred. This is termed the location policy. Any efficient location policy should distribute the overflow tasks to the entire system instead of 'dumping' them on a few underloaded nodes. To reduce the overhead for collecting state information and transferring tasks, each node is required to maintain the state information of only those nodes in its proximity, called a buddy set. Several location policies-random probing, random selection, preferred lists, and bidding algorithm-are analyzed and compared for hypercube-connected multicomputer systems. Under the random-selection and preferred-list policies, an overloaded node can select, without probing other nodes, an underloaded node within its buddy set, while under the random probing policy and the bidding algorithm the overloaded node needs to probe other nodes before transferring the overflow task. Task collision(s) is said to occur if two or more overflow tasks are transferred (almost) simultaneously to the same underloaded node. The performances of these location policies are analyzed and compared in terms of the average number of task collisions. Our analysis shows that use of preferred lists allows the overflow tasks to be shared more evenly throughout the entire hypercube than the other two location policies.>

This paper considers the problem of scheduling both periodic and aperiodic tasks in real-time systems. A new algorithm, called reservation-based (RB), is proposed for ordering the execution of real-time tasks. This algorithm can guarantee all periodic-task deadlines while minimizing the probability of missing aperiodic-task deadlines. Periodic tasks are scheduled according to the rate monotonic priority algorithm (RMPA), and aperiodic tasks are scheduled by utilizing the processor time left unused by periodic tasks in each unit cycle. The length, u, of a unit cycle is defined as the greatest common divisor of all task periods, and a task is assumed to be invoked at the beginning of a unit cycle. For a set S of periodic tasks, the RB algorithm reserves a fraction R/sub s/ of processor time in each unit cycle for executing aperiodic tasks without missing any periodic-task deadline. The probability of meeting aperiodic-task deadlines is proved to be a monotonic increasing function of R/sub s/. We derive the value of R/sub s/ that maximizes the processor time reservable for the execution of aperiodic tasks without missing any periodic-task deadline. We also show that if the ratio of the computation time to the deadline of each aperiodic task is bounded by R/sub s/, the RB algorithm can meet the deadlines of all periodic and aperiodic tasks. Our analysis and simulation results show that the RB algorithm outperforms all other scheduling algorithms in meeting aperiodic-task deadlines.

The module-sliced approach is realized in a reconfigurable fault-tolerant segmented array processor (RFTSAP). The basic building block of RFTSAP is a node which consists of a processor, local memory, and a programmable I/O unit (PIOU). The PIOU allows any group of processors to be combined to perform the functions of a large processor module. The yield of a large processor module can be improved 2 to 4 times compared to that of approaches not using the module-sliced method.>

A decentralized, dynamic load sharing (LS) method based on state-change broadcasts is proposed for a distributed real-time system. Whenever the state of a node changes from underloaded to fully loaded and vice versa, the node broadcasts this change to a set of nodes, called a buddy set, in the system. The performance of the method is evaluated with both analytic modeling and simulation. It is modeled first by an embedded Markov chain for which numerical solutions are derived. The model solutions are then used to calculate the distribution of queue lengths at the nodes and the probability of meeting tasks deadlines. The analytical results show that buddy sets of ten nodes outperform those of less than ten nodes, and the incremental benefit gained from increasing the buddy set size beyond 15 nodes is insignificant. These and other analytical results are verified by simulation. The proposed LS method is shown to meet task deadlines with a very high probability.>