It is desirable in a distributed system to have the system load balanced evenly among the nodes so that the mean job response time is minimized. In this paper, we present.a dynamic load balancing mechanism (DLB). It adopts a centralized approach and is network topology independent. The DLB mechanism employs a set of thresholds which are automatically adjusted as the system load changes. lt also provides a simple mechanism for the system to switch between periodic and instantaneous load balancing policies wi…

We consider a distributed unicasting algorithm for hypercubes with faulty nodes (including disconnected hypercubes) using the safety level concept. The safety level of each node in an n-dimensional hypercube is an approximated measure of the number and distribution of faulty nodes in the neighborhood and it can be easily calculated through n - 1 rounds of information exchange among neighboring nodes. Optimal unicasting between two nodes is guaranteed if the safety level of the source node is no less than th…

It is relatively clear how to map regular, repetitive or grid oriented computations onto SIMD architectures. It is not so clear, however, how to do this for irregular computations even though there may be significant amounts of intrinsic parallelism in branch free code. We study compilation techniques for this type of code when targeted to SIMD computers and illustrate their use on a simple model architecture.In this paper, we present one of the compilation techniques, global mpister allocation,we have deve…

Loop transformations, such as loop interchange, reversal and skewing, have been unified under linear matrix transformations. A legal transformation matrix is usually generated based upon distance vectors or direction vectors. Unfortunately, for some nested loops, distance vectors may not be computable and direction vectors, on the other hand, may not contain useful information. We propose the use of linear equations or inequalities of distance vectors to approximate data dependence. This approach is advanta…

In solving application problems, many largesscale nonlinear systems of equations result in sparse Jacobian matrices. Such nonlinear systems are called sparse nonlinear systems. The irregularity of the locations of nonzero elements of a general sparse matrix makes it very difficult to generally map sparse matrix computations to multiprocessors for parallel processing in a well balanced manner. To overcome this difficulty, we define a new storage scheme for general sparse matrices in this paper. With the new…

The matrir analytic analysis of queues with complex arrival, vacation and service characteristics requires the solution of nonlinear matrir equation. The complexity and large dimensionality of the model require an efficient and smart algorithm for the so-lution. In this paperl we propose an efficient Adaptive Newton-Kantorovich (ANK)method for speeding up the algorithm solving the nonlinear matrir equation which is an inevitable step in the analysis of the queue with embedded Markov chain such as BMAP/SMSP/…

3-D task space in modeling and animation is usually reduced to the separate control dimensions supported by conventional interactive devices. This limitation maps only patial view of the problem to the device space at a time, and results in tedious and un natural interface of control. This paper uses the DataGlove interface for modeling and animating scene behaviors. The modeling interface selects, scales, rotates, translates,copies and deletes the instances of the prindtives. These basic modeling processes…

With the advent of optical fiber and other advanced technologies in solid state,pipelining signals at the wire (or transmission line) level has become possible. This has, in turn, made the slotted bus a potential candidate for interconnection networks (IN) for tightly coupled multiprocessor systetns. However, a bus can provide only lboted bandwidth. Though slotted bus can provide considerably more bandwidth in comparison to the traditional non-slotted bus, it is not enough for fine-grain parallel applicatio…

Earlier performance studies of multiple-bus multiprocessor systetns assume a ran-dom selection of competing requests for bus assignment and ignore the effects of realistic bus arbitration schemes on the performance of such systetns. In this paper, we present performance analysis of the multiple-bus systems with different arbitration protocols.The priority protocols considered are random selection, fixed priority, rotating priority, roundrobin and FIFO. Analytica1 models are developed for each of these five …

Many reconfiguration schemes for fault-tolerant binary tree architectures have been proposed in the lite..t.re[1-6]. The VLSI layouts of most previous studies are based on the classical H-tree layout, resulting in low area utilization and likely an unnecessarily high manufacturing cost simply due to the waste of a significaot portion of silicon area. In this paper, we present an area-efficient approach to the reconfigurable binary tree architecture. Area utilization and interconnection complexity of our des…